第八章 信息认证和散列函数 （Message Authentication and Hash Functions) 1 信息认证 网络系统安全要考虑两个方面。一方面，用密码保护传 送的信息使其不被破译；另一方面，就是防止对手对系统进 行主动攻击，如伪造，篡改信息等。认证（authentication） 则是防止主动攻击的重要技术，它对于开放的网络中的各种 信息系统的安全性有重要作用。认证的主要目的有二： 第一，验证信息的发送者是真正的，而不是冒充的，此 为信源识别； 第二，验证信息的完整性，在传送或存储过 程中未被篡改，重放或延迟等。

保密和认证同时是信息系统安全的两个方面，但它们 是两个不同属性的问题，认证不能自动提供保密性，而 保密性也不能自然提供认证功能。一个纯认证系统的模 型如下图所示： 窜扰者 信源 认证编码器 认证译码器 信宿 信道 安全信道 密钥源

在这个系统中的发送者通过一个公开的无扰信道将消息 送给接收者，接收者不仅想收到消息本身，而且还要验证消 息是否来自合法的发送者及消息是否经过篡改。系统中的密 码分析者不仅要截收和破译信道中传送的密报，而且可伪造 密文送给接收者进行欺诈，将其称为系统的窜扰者(tamper) 更加合适。实际认证系统可能还要防止收方、发方之间的相 互欺诈。 上述标出的认证编码器和认证译码器可抽象为认证函数。 一个安全的认证系统，首先要选好恰当的认证函数，然后在 此基础上，给出合理的认证协议(Authentication Protocol)。

2 认证函数 （Authentication Functions) 可用来做认证的函数分为三类： (1) 信息加密函数(Message encryption) 用完整信息的密文作为对信息的认证。 (2) 信息认证码MAC(Message Authentication Code) 是对信源消息的一个编码函数。 (3) 散列函数(Hash Function) 是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。

对于（1），用信息加密函数作认证的方式，教材 P239-242，给出明白的叙述。信息加密函数分二种，一种 是常规的对称密钥加密函数，另一种是公开密钥的双密 钥加密函数。下图的通信双方是，用户A为发信方，用户 B为接收方。用户B接收到信息后，通过解密来判决信息 是否来自A，信息是否是完整的，有无窜扰。 信源 信宿 M E Ek(M) D A方 B方 k Dk(Ek(M)) (a) 常规加密：具有机密性，可认证

M E D A方 B方 DkRb (b) 公钥加密：具有机密性 M E D A方 B方 KRa KUa (c) 公钥加密：认证和签名 EKUb(M) D A方 B方 DkRb KUb(B方的公钥) (b) 公钥加密：具有机密性 M E EkRa(M) D A方 B方 KRa KUa (c) 公钥加密：认证和签名

M E EkRa(M) EKUb(EkRa(M)) A方 KRa KUb D B方 KRb KUa (d) 公钥加密：机密性，可认证和签名

对于（2），信息认证码(MAC) 设S为通信中的发方A发送的所有可能的信源集合。 为了达到防窜扰的目的，发方A和收方B设计一个编码法 则。发方A根据这个法则对信源S进行编码，信源经编码 后成为消息，M表示所有可能的消息集合。发方A通信时， 发送的是消息。用简单的例子说明：设S={0,1}, M={00,01,10,11}, 定义四个不同的编码法则e0,e1,e2,e3: 00 01 10 11 e0 0 1 e1 0 1 e2 0 1 e3 0 1

这样就构成一个认证码MAC。发方A和收方B在通信前先 秘密约定使用的编码法则。例如，若决定采用e0，则以 发送消息00代表信源0；发送消息10代表信源1，我们称 消息00和10在e0之下是合法的。而消息01和11在e0之下不 合法，收方将拒收这二个消息。 信息的认证和保密是不同的两个方面，一个认证码 可具有保密功能，也可没有保密功能。 认证编码的基本方法是要在发送的消息中引入多余 度，使通过信道传送的可能序列集Y大于消息集X。对于 任何选定的编码规则(相应于某一特定密钥):发方从Y中选 出用来代表消息的许用序列，即码字；收方根据编码规 则唯一地确定出发方按此规则向他传来的消息。窜扰者 由于不知道密钥，因而所伪造的假码字多是Y中的禁用序

列，收方将以很高的概率将其检测出来而被拒绝。认证 系统设计者的任务是构造好的认证码(Authentication Code),使接收者受骗概率极小化。 令x ∈X为要发送的消息，k ∈K为发方选定的密钥， y=A(x,k) ∈Y是表示消息X的认证码字，Ak={y=A(x,k)|x ∈X}为认证码。Ak是Y中的许用(合法)序列集，易见 Y=Ak∪Ak。接收者知道认证编码A(.,.)和密钥k,故从收到 的y, 唯一确定出消息x。窜扰者虽然知道X,Y,y,A(.,.),但不 知具体密码k, 他的目的是想伪造出一个假码字y*，使y* ∈Ak, 以使接收者收到y*后可用密钥k解密，得到一个合 法的消息x*。这样，窜扰者欺诈成功。

消息认证 消息认证是使意定的消息接收者能够检验收到的消 息是否真实的方法。检验内容应包括： (1)证实报文的源和宿； (2)报文内容是否曾受到偶然的或有意的篡改； (3)报文的序号和时间栏。 总之，消息认证使接收者能识别： 消息的源，内容的真伪，时间性和意定的信宿。 这种认证只在相应通信的双方之间进行，而不允许 第三者进行上述认证。认证不一定是实时的。 可用消息认证码MAC对消息做认证。

利用函数f和密钥k，对要发送的明文x或密文y变换成r bit的消息认证码f(k,x)(或f(k,y))，将其称为认证符附加在x(或y)之后发出，以x//As(或y//As)表示，其中“//”符号表示数字的链接。接收者收到发送的消息序列后，按发方同样的方法对接收的数据(或解密后)进行计算，应得到相应的r bit数据。 两种实用的MAC算法 (一)十进制移位加MAC算法 Sievi于1980年向ISO提出一项消息认证法的建议[Davies等1984]，这种认证法称为十进制移位加算法(Decimal Shift and Add Algorithm)，简记为DSA。它特别适用于金融支付中的数值消息交换业务。 消息按十位十进制数字分段处理，不足十位时在右边以0补齐，下面举例说明。令x1=1583492637是要认证的第一组消息，令b1=5236179902和b2=4893524771为认证用的密钥。DSA算法是以b1和b2并行对x1进行运算。 .

先算x1+b1, x1+b2(mod 1010), 而后根据b2的第一位数值4 对x1+b2循环左移4位，记作R(4)(x1+b1)再与(x1+b1)相加得 R(4)(x1+b1)+(x1+b1)P1(mod 1010) 类似地，右路在b1的第一位数值5控制下运算结果为 R(5)(x1+b2)+(x1+b2)=Q1(mod 1010) 表： 左路 右路 第 b1=5236179902 b2=4893224771 一 + x1=1583492637 + x1=1583492637 轮 b1+x1=6819672539 b2+x1=6477017408 +R(4)(b1+x1)=2539681976 +R(5)(b2+x1)=1740864770 P1=9359354506 Q1=8217882178

结果又分别以P1和Q1的第一位控制循环移位后进行相加 得到P2和Q2，依此类推。直至进行十轮后得P10和Q10。 第 + x2=5283586900 + x2=5283586900 二 P1+x2=4642941406 Q1+x2=3501469078 轮 +R(8)(P1+x2)=4294140646 +R(9)(Q1+x2)=7835014690 P2=8937082052 Q2=1336483768 …. …. 第 P10=7869031447 Q10=3408472104 十 P10+Q10=1277403551 (mod 1010) 轮 403551 + 1277 认证符 404828 (mod 1010) 将第二组消息x2=528358586900分别与P1和 Q1相加，其 结果又分别以P1和Q1的第一位控制循环移位后进行相加 得到P2和Q2，依此类推。直至进行十轮后得P10和Q10。 计算P10+Q10 (mod 1010),并将结果的后6位数与前4位数在

有二种基于DES的认证算法，一种按CFB模式，一种 按CBC模式运行。在CBC模式下，消息按64bit分组，不 (mod 1010)下相加，得6位认证符！ (二)采用DES的认证算法： 有二种基于DES的认证算法，一种按CFB模式，一种 按CBC模式运行。在CBC模式下，消息按64bit分组，不 足时以0补齐，送入DES系统加密，但不输出密文，只取 加密结果最左边的r位作为认证符。 64比特寄存器 y1,y2,…,yn(64bit数组) As (24bit or 32bit) (64bit) x1,..xn yn DES 选左r位 + 利用CBC模式下DES的认证法

r取大小可由通信双方约定。美国联邦电信建议采用 24bit[见FTSC-1026],而美国金融系统采用32bit [ABA,1986] 64bit寄存器 As k 选左边r位 DES 选左边k位 xi yi + 利用工作于CFB模式下DES

对于（3），散列函数(Hash Function) 若对相当长的文件通过签名认证怎么办？如一个合法文件有数兆字节长。自然按160比特分划成一块一块，用相同的密钥独立地签每一个块。然而，这样太慢。 解决的办法：引入可公开的密码散列函数(Hash function)。它将取任意长度的消息做自变量，结果产生规定长度的消息摘要。[如，使用数字签名标准DSS，消息摘要为160比特]，然后签名消息摘要。对数字签名来说，散列函数h是这样使用的： 消息： x 任意长 消息摘要： Z=h(x) 160bits 签名： y=sigk(Z) 320 bits (签名一个消息摘要)

验证签名:(x,y),其中y= sigk(h(x))，使用公开的散列函数h，重构作Z'=h(x)。然后检验Verk(Z,y),来看Z=Z'。 (一)无碰撞的散列函数 用以认证的散列函数，能否减弱认证方案的安全性？这个问题是要分析的。签名的对象由完整消息变成消息摘要，这就有可能出现伪造。 (a)伪造方式一：Oscar以一个有效签名(x,y)开始，此处y= sigk(h(x))。首先他计算Z=h(x)，并企图找到一个x'=x满足h(x')=h(x)。若他做到这一点，则(x',y)也将为有效签名。为防止这一点，要求函数h具有无碰撞特性。 定义1(弱无碰撞)，散列函数h称为是弱无碰撞的，是指对给定消息x ∈ X，在计算上几乎找不到异与x的x' ∈ X使h(x)=h(x')。

(b)伪造方式二：Oscar首先找到两个消息x=x',满足h(x)=h(x'),然后Oscar把x 给Bob且使他对x的摘要h(x)签名，从而得到y,那么(x',y)是一个有效的伪造。 定义2(强无碰撞)散列函数h被称为是强无碰撞的,是指在计算上几乎不可能找到相异的x，x'使得h(x)=h(x')。 注：强无碰撞自然含弱无碰撞！ (c)伪造方式三：在某种签名方案中可伪造一个随机消息摘要Z的签名。若h的逆函数h-1是易求的，可算出 h-1(Z)=x, 满足x=h(Z)，则(x,y)(其中y=sigk(h(x)))为合法签名。 定义3(单向的)称散列函数h为单向的，是指计算h的逆函数h-1在计算上不可行。

下面要证明“强无碰撞特性包含有单向性”。为此，先对散列函数h做一规范说明： 首先h:X Z，这里设X,Z为有限集且|X|>=2|Z|。这是一个合理的假设：若X中的元素编码长度为log2|X|的比特串，Z中的元素编码长度为log2|Z|的比特串。那么消息摘要Z=h(x)至少比源消息X短一个比特。 定理：假设h:X Z为一个散列函数，这里|X| 和|Z|是有限的且|X|>=2|Z|。若h-1为h的逆函数，那么存在一个概率的Las Vegas算法，它能找到h的一个碰撞的概率至少为1/2。 证明：利用h的逆函数h-1来寻找h的碰撞的Las Vegas概率算法： (1) 随机选择x ∈ X (2)计算Z=h(x)

(3)计算X1= h-1(Z) (4)若X1=X,那么X1和X在h下碰撞成功。 否则，往复再来。来看成功的概率： 首先定义X中元素关于h的等价，若x1,x ∈ X,有 h(x)=h(x1), 则称x1与x等价；记为x等价于x1。 等价类[x]={x1 ∈X| x等价于x1} 因为，每一个等价类[x]由Z的元素的原象组成，所以等价 类的数目至多为|Z|。记等价类的集合为C。现假设x是第 一步选择的X中的元素。对这个x,在第(3)步中将返回 |[x]|个可能的x1值，而|[x]-1|个x1值将与x不同。于是在[x] 类内成功的概率为(|[x]-1)/|[x]|。 对于前述算法成功的概率是通过平均所有可能x的选 择来计算的：

P(成功)=(1/|X|) ∑((|[x]|-1)/|[x]|) =(1/|X|) ∑ ∑ ((|C|-1)/|C|) c ∈ C x ∈ C =(1/|X|) ∑( |C|- 1) c ∈ C =(1/|X|) (∑|C|-∑1) c ∈ C c ∈ C  (|X|-|Z|)/|X| (|X|-|X|/2)/|X|=1/2 因此，构造了一个成功率至少为1/2的Las Vegas算法。 注：说明强无碰撞与单向性的关系是，单向性含于强 无碰撞之中

(二)生日攻击： 任找23人，从中总能选出两人具有相同生日的概率至少为1/2。 假设h:X Z是一个散列函数，X和Z是有限的，且|X|>=2|Z|，记|X|=m和|Z|=n，易见至少有n个碰撞—问题是如何找到它们？ 自然的方法是，选择k个随机的不同元素x1,x2,…,xk ∈ X，计算Zi=h(xi)，1<=i<=k。 然后确定一个碰撞是否已发生(例如：通过分类Zi的值)。 这个过程类似于随机抛k个球进入n个箱子，然后检查一下是否有一些箱子包含了至少两个球(这k个球对应于k个随机值xi，且n个箱子对应于Z中n个元素） 用上述模型来计算一个碰撞的概率下界。这个下界仅依赖于k和n，但不依赖于m。预先做一个假设：

任意z ∈ Z,|h-1(Z)|≈m/n(这个假设是合理的，若对任意z ∈ Z的原象个数分布不均匀，则找1个碰撞的概率将增加)。由这些假设可推断xi的象h(xi)=Zi(i=1,2,…,k)也可视为Z中的随机元素。(这k个随机元，也可有相同的)。一个重要的问题是： 若计算这k个随机元素z1,z2,..,zk ∈ Z两两不同(无碰撞时)，对应于初始问题—无碰撞的概率： 考虑有序z1,z2,…,zk中的zi的选择可能，第一个选择z1是随机的，z2z1的概率为1-1/n;z3不同于z1和z2的概率为1-2/n,等等。 因此，无碰撞的概率为(随机抛k个球进入n个箱子,没有箱子被抛进两个以上的球的概率)

k-1 (1-1/n)(1-2/n)…(1-(k-1)/n)=∏(1-i/n)≈1-e(-(k(k-1)/(2n)) i=1 注：若设E=1- e(-(k(k-1)/(2n)) ,可解出k的关于n,E的函数，有 e(-(k(k-1)/(2n)) =1-E , (-(k(k-1)/(2n))≈ln(1-E), k2-k≈2nln(1-E)-1 若略去-k项，有k≈ (n(ln(1/(1-E))2)0.5 若取E=0.5,我们估计k≈1.17 n0.5≈ n0.5 说明，在集合X中，n0.5个随机元素散列的结果产生 一个碰撞的概率为50%! 所谓生日攻击就是：如果X为一些人的集合，Y是 一个非闰年的365天集合，h(x)表示x的生日。(x ∈ X)。 在上述估计式中取n=365, 得k≈22.3，即随机的23人中至 少有一个重复生日的概率至少为50%。

生日攻击给出消息尺寸的下界。一个40bit的消息摘要将是不安全的。因为k≈1. 17 （240)0 生日攻击给出消息尺寸的下界。一个40bit的消息摘要将是不安全的。因为k≈1.17 （240)0.5, 也就是≈220(大约100万)，即在100万个随机散列值中将找到一个碰撞的概率为1/2。通常建议，消息摘要的尺寸为128bits。