5.1 消息鉴别

消息鉴别（Message Authentication）是一个证实收到的消息来自可信的源点且未被篡改的过程。鉴别的主要目的有两个。第一，验证信息的发送者是真正的，而不是冒充的，此为信源识别；第二，验证信息的完整性，在传送或存储过程中未被篡改、重放或延迟等。

5.1.1 鉴别系统模型

图5.1给出了一个单纯鉴别系统的模型。鉴别编码器和鉴别译码器可抽象为鉴别函数。一个安全的鉴别系统，需满足下列要求：意定的接收者能够检验和证实消息的合法性、真实性和完整性；消息的发送者和接收者不能抵赖；除了合法的消息发送者，其他人不能伪造合法的消息。为了达到以上目的，通常的做法是先选好恰当的鉴别函数，该函数产生一个鉴别标识，然后在此基础上，给出合理的鉴别协议（Authentication Protocol），使接收者完成消息的鉴别。

用于产生鉴别符的鉴别函数分为以下三类：

（1）消息加密函数：用完整消息的密文作为对消息的鉴别。

（2）消息鉴别码（Message Authentication Code, MAC）函数：是一个密钥控制的公开函数，对变长的报文产生一个固定长度的数值。

（3）散列函数（Hash Function）：一个散列函数是一个公开的函数，以一个变长的报文作为输入，并产生一个固定长度的散列码作为输出，该输出有时也称为报文摘要。

5.1.2 消息加密

消息自身的加密可以作为一个鉴别的度量，在对称密钥和公开密钥两种模式下有所不同。

5.1.2.1 对称加密

如果用对称密钥加密，在提供机密性保护的同时，的确可以提供一定程度的内容和来源的真实性。这基于通信双方有共享密钥KAB，第三方没有该密钥的前提。如果用户B收到A发给他的密文，他能够用与A共享的密钥KAB解密的话，他相信消息的确来自A，传输中没有被更改，因为不知道他们共享密钥KAB的人无法产生可以用KAB加密的密文。人可以直接判断收到的密文是否被解密为有意义的明文，但是如何让机器自动确定这一点呢？分组加密算法相当于一个数学映射，对于任意的b位输入都可以产生b位输出，如果没有额外信息的话，机器无法知道解密出来的明文是否为可懂的明文。一种解决办法是强制明文有某种结构，例如，可以在加密前对每个消息附加一个错误检测码，也称为帧校验序列（Frame Check Sequence，FCS）或校验和。在接收端，机器对解密后的消息应用同样的校验函数，若得到的校验和与收到的一致，则认为消息是真实的。事实上，在要发送的信息中加入任何类型的结构信息都会增强鉴别的能力，如在TCP协议中，为了防止TCP数据报被篡改，TCP数据报的头部包含校验和，并且对于给定连接，连续的TCP数据报是按顺序编号的，防止攻击者进行延时、删除、重放等形式的篡改。

加密与FCS执行的顺序很重要，先计算FCS再加密被称为内部差错控制，由于攻击者不知道密钥，很难产生解密后校验和正确的密文。先加密再计算FCS被称为外部差错控制，攻击者就可以构造具有正确校验和的消息，虽然攻击者在不知道密钥的情况下，他也不知道构造的密文解密后的明文是什么，但可以造成混淆从而破坏通信。

5.1.2.2 公钥加密

如果使用公开密钥加密，前提是知道对方的公钥，各自的私钥保密。用公钥对信息加密提供机密性，不能保证发送方的真实性，任何用户都可以假冒A用B的公钥对消息加密。用私钥对信息数字签名，不提供机密性，如果其他用户收到用户A签名的消息，并且可以用A的公钥验证签名的正确性的话，他就可以相信消息的确来自A，因为只有A拥有能产生正确签名的私钥，并且信息在传输中没有被篡改。如果既要提供机密性，又要提供鉴别，用户A就需要先用自己的私钥签名，再用用户B的公钥加密，一次通信中就要进行四次复杂的加解密。

5.1.3 消息鉴别码MAC

5.1.3.1 消息鉴别码的需求

使用一个密钥生成一个固定大小的小数据块，并加入到消息中，称为消息鉴别码（MAC）或密码校验和（Cryptographic checksum）。它由如下形式的函数产生：

MAC = C（K，M）

其中M是一个变长的消息，K是收发双方共享的密钥，C（K，M）是定长的鉴别符。消息和MAC被一起发送给接收方。接收方对收到的消息用相同的密钥进行相同的计算得出新的MAC，与接收到的MAC相比较，如果两者相等，接收者可以确信消息M未被改变，并且消息来自所声称的发送者，如果消息中包含顺序码（如X.25，TCP中使用的序列号），则接收者可以保证消息的正常顺序。MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少。

对称加密可以提供鉴别，且已被广泛应用，为什么还要使用单独的消息鉴别码呢？因为，机密性与真实性是两个不同的概念，从根本上讲，信息加密提供的是机密性而非真实性。首先，加密运算的代价很大，公钥算法代价更大；其次，鉴别函数与加密函数的分离能提供功能上的灵活性，可以把加密和鉴别功能独立地实现在通信的不同传输层次；再次，能够在目标系统中延长对消息的保护时间，因为加密只保证传输中的机密性，一旦消息到达接收者的机器并被解密后，就不能保护消息不被修改；此外，某些信息只需要真实性，不需要机密性，比如：广播的信息，信息量大，难以使用加密；政府/权威部门的公告和网络管理信息等只需要保证真实性。

MAC的基本用法有三种：

（1）MAC直接附加在消息之后

A→B：M || MACK（M）

MAC基于A和B共享的密钥K生成。如果B对收到的消息生成的MAC与收到的MAC相同，他可以确认消息一定来自A，且没有被篡改。这个过程没有提供对消息的保密。

（2）MAC直接附加在消息之后，并对整体进行加密

A→B: 2EK[M || MA 1CK（M）]

这里密钥K1用于生成鉴别码，提供对消息的鉴别，消息的机密性由A和B共享的密钥K2提供。

（3）先对消息加密，再对密文生成鉴别码

A→B: 2EK[M] || MA 1CK（2EK[M]）

这种方法也同时提供保密和鉴别，一般来说，将MAC附加于明文之后更好一些。

5.1.3.2 基于对称分组密码的消息鉴别码

消息鉴别码最初主要是基于对称分组密码算法而设计的，一个使用广泛的数据鉴别算法（Data Authentication Algorithm），也被称为CBC-MAC（密文分组链接消息鉴别码），定义于标准ANSI X9.9，FIPS PUB 113和ISO/IEC 9797中，它使用分组长度为b位的对称分组密码算法的CBC（Cipher Block Chaining）工作模式对消息进行加密，并取最后一个密文分组最左边的M位作为MAC值，M的大小可由通信双方约定，如图5.2所示。首先将数据按b位分组，假设消息被划分为N个分组：D1，D2，…，DN，如果消息不是分组长度的整数倍，最后一个数据块用一个1和若干个0向右填充。运用加密算法E和密钥k，消息鉴别码（MAC）的计算如下：

基于CFB工作模式下的对称分组密码算法也可以构造MAC，如图5.3所示。

在散列函数提出之前，基于DES的MAC获得广泛应用，但MAC需要对全部数据进行加密，速度很慢，由此导致了直接设计散列函数对给定数据生成鉴别码的研究。

5.1.4 散列函数

5.1.4.1 散列函数的用途

散列值h由下述形式的函数H生成：

h = H（M）

H的输入为任意长度的消息M，输出为一个固定长度的散列值h，称为消息摘要（Message Digest）。这个散列值是消息M所有位的函数。它能够提供错误检测能力，因为消息中的任何一位或多位的变化都将导致该散列值的变化。消息摘要函数在不同的场合有不同的名称，它的音译是哈希函数。因为它可以像指纹一样代表一串数据，也被称为数字指纹（Digital finger print）。因为它对任意长度的输入产生固定长度的输出，也被称为压缩（Compression）函数或紧缩（Contraction）函数。当它用于数据篡改的检验时，也被称为数据鉴别码 DAC（Data Authentication Code）或篡改检验码MDC（Manipulation Detection Code）。

散列函数的两个主要用途是消息的完整性检测和数字签名。数字签名是一种给数字形式存储的消息签名的方法，我们在下一节进行介绍。

图5.4给出了使用Hash函数进行完整性检测的模型。发送者要发送的明文消息为x，他应用散列函数H生成x的消息摘要H（x），把消息x和消息摘要H（x）的密文y通过公开信道同时发送给接收者，接收者对接收到的消息x′生成消息摘要H（x′），与通过对y解密得到的消息摘要H（x）进行比较，如果两者相等，就可以确认x′=x，消息x在传输中没有被篡改。

将消息摘要用于消息鉴别的具体方法，可以总结为以下6种。

（1）用对称密码对消息及附加在其后的消息摘要加密

A→B：EK [M|| H（M）]

这种方式提供了机密性，因为消息M用A和B共享的密钥K加密。如果B使用密钥K对接收到的密文解密，再对得到的消息生成消息摘要，如果与解密得到的原始消息摘要相同，他可以确认消息一定来自A，且没有被篡改。

（2）用对称密码只对消息摘要加密

A→B：M || EK [H（M）]

这种方法只提供真实性保护，消息摘要H（M）用A和B共享的密钥K加密。如果B对接收到的消息生成消息摘要，与解密得到的原始消息摘要相同，他可以确认消息一定来自A，且没有被篡改。

（3）仅用发送方的私钥对消息摘要签名

A→B：M || EKRa[H（M）]

这种方法提供真实性保护和数字签名。首先，同方法（2）一样，该方法提供真实性保护，如果B能用A的公钥验证签名的正确性，他可以确认消息一定来自A，且没有被篡改。其次，因为只有A能生成这样的签名，所以该方法也提供了不可否认保护。

（4）用发送方的私钥对消息摘要签名，再对全部消息加密

A→B：EK[M || EKRa[H（M）]]

该方法既提供对消息的保密，又提供数字签名，比较常用。

（5）该方法使用散列函数，但不使用加密函数来进行消息鉴别

A→B：M || H（M || S）

因为双方共享秘密值S，B也可以计算散列值，并验证正确性，而不知道秘密值的攻击者不能伪造和篡改消息。

（6）如果对整个消息和消息摘要加密，方法（5）在提供消息鉴别的同时，也可以提供机密性

A→B：EK[M||H（M||S）]]

上述方法中，方法（5）避免了对加密函数的使用，引起了人们的极大关注。避免使用加密函数的原因有：加密软件很慢；加密硬件的开销很大；加密是对大长度数据进行优化的；加密算法可能受专利保护；加密算法可能受出口的限制。

5.1.4.2 对散列函数的要求

在第4章介绍了基于RSA的数字签名算法，这样的签名算法存在以下弱点：

● 假设用户B的公钥KUb = e，私钥KRb = d，任何人能通过对某一给定的y计算x = EKUb（y）=y e mod n，伪造一个B对随机消息x的签名，因为y = SigKRb（x）=（y e）d = y ed mod n。

● 如果消息x1，x2的签名分别是y1和y2，则拥有x1，x2，y1，y2的任何人可伪造B关于消息x1 x2的签名y1 y2，因为SigKRb（x1x2）=（x1x2）d mod n=x1dx2d mod n =（x1d mod n）（x2d mod n）= SigKRb（x1）SigKRb（x2）。

● 签名者每次只能签log2n 比特长的消息，获得同样长的签名。如果消息很长，需要逐组签名。然而，这样做，速度慢，签名长。

解决以上问题的办法是引入可公开的散列函数。它将取任意长度的消息做自变量，结果产生规定长度的消息摘要。例如，使用数字签名标准DSS，一个消息摘要为160 bit，对消息摘要进行签名，结果如下：

使用散列函数进行数字签名的好处有：由于把对原始消息的签名替换成了对消息的短的消息摘要的签名，提高数字签名的速度；无须泄露签名所对应的消息，可将签名泄露，如对消息x的签名是y = Sigk（z），其中z = H（x），可将（z，y）公开，而保密x；可将签名变换和加密变换分开，在OSI的不同层提供消息的完整性和机密性。

用以鉴别的散列函数，能否减弱鉴别方案的安全性？这个问题是要分析的。签名的对象由完整消息变成消息摘要，这就有可能出现伪造。下面分析可能的伪造方式。

伪造方式一：Oscar以一个有效签名（x，y）开始，此处y = Sigk（H（x））。首先他计算z = H（x），并企图找到一个x′满足H( )x′ = H（x）。若他做到这一点，则（x′，y）也将被识别为有效签名。为防止这一点，要求函数H具有无碰撞特性。

散列函数H称为是弱无碰撞的，是指对给定消息x∈X，在计算上几乎找不到不同于x的x′∈X使H（x）= H（x′）。

伪造方式二：Oscar首先找到两个消息x≠x′，满足H（x）= H(x′)，然后Oscar把x给Bob且使他对x的摘要H（x）签名，从而得到y，那么（x′，y）就是一个有效的伪造。为防止这一点，要求函数H具有强无碰撞特性。

散列函数H被称为是强无碰撞的，是指在计算上几乎不可能找到相异的x和x′，使得H（x）= H( )x′。

这里，强无碰撞自然含弱无碰撞。因为很显然，如果找不到任意的（x，y）满足条件的话，给定x也一定找不到。

伪造方式三：在散列函数的用法（5）中，秘密值S本身并不发送，如果散列函数不是单向的，攻击者截获到M和H（M||S），然后通过某种逆变换获得M||S，这样攻击者就可以得到S。为防止这一点，要求函数H具有单向性。

称散列函数H为单向的，是指计算散列函数H的逆函数H-1在计算上不可行。

综上所述，我们认为散列函数需要满足如下性质：

（1）H可以作用于一个任意长度的数据块。

（2）H产生一个固定长度的输出。

（3）对任意给定的x，H（x）的计算相对容易，无论是软件还是硬件实现。

（4）对任意给定散列码h，找到x满足H（x）= h具有计算不可行性，这被称为单向性（抗原像攻击）。

（5）对任意给定的数据块x，找到满足H（y）= H（x）的y≠x具有计算不可行性，这被称为弱无碰撞性（抗第二原像攻击）。

（6）找到任意数据对（x，y），满足H（x）=H（y）是计算不可行的，这被称为强无碰撞性。

前三条要求散列函数具有计算可行性，第4条是单向性质，即给定消息可以产生一个散列码，而给定散列码不可能产生对应的消息。第5条性质是保证给定一个消息，不能找到与之散列码相同的另外一个消息，即防止伪造。第6条则保证了一种被称为生日攻击的方法无法奏效。

近年来，随着散列函数分析技术的进步，出现了一些新的攻击方式，如长消息的第二原像攻击和选择前缀的原像攻击，因此，NIST在全球范围内征集新的散列函数时，增加了抗长度扩展攻击（Length-extension attack）的安全属性：给定H(M)和M的长度，对于任意的消息M′，即使当M未知，可以直接利用H(M)来计算H(M )M′ 是困难的。

理想情况下，还有一些更强的条件和要求，如对于攻击者来说找到两个具有大体相似的消息摘要的消息是不可能的，或者给定消息摘要，从中推出任何有用的消息也是不可能的。因此，密码学意义上的散列函数还应该具有尽量多的随机函数特性。一些校验和算法，如CRC32及其他循环冗余校验序列就不适合作为密码学意义上的散列函数。

5.1.4.3 散列函数的安全性

散列函数是一种多对一函数，理论上一定存在碰撞。假定使用64位的散列码，是否安全？如果传输的是加密的散列码和不加密的报文M，对手需要找到M′，使得H( )M′ = H（M），就可以使用替代报文来欺骗接收者。一种基于生日悖论的攻击可能做到这一点。

与生日悖论相关的生日问题是：一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于1/2？一年有365天，如果有366人的话，至少两人的生日相同。直觉上这个数字不会小，而概率结果与人的直觉是相违背的，从这个意义上，它被称为悖论。实际上只需23人，即任找23人，其中两人具有相同生日的概率至少为1/2。

一个与生日问题类似的散列函数问题是：给定一个散列函数和散列值H（x），假定H有 n种可能的输出，如果H有k个随机输入，k必须为多大才能使至少存在一个输入y，使得H（y）=H（x）的概率大于0.5。

对于一个输出值h为m比特的散列函数，共有n = 2m种可能的输出，在理想状态下，对任何输入，h应均匀地在整数0到2m-1之间取值，也就是说，散列函数输出恰好是给定输出值的概率是1/n。因此，任取一个y，H（y）= H（x）的概率为1/n，反过来H（y）≠H（x）的概率为1-（1/n）。如果产生k个随机值y，他们的消息摘要都不等于H（x）的概率等于每个个体不匹配概率的乘积，即[1-（1/n）]k，这样，至少有一个匹配的概率为1-[1-（1/n）]k≈1-[1-（k/n）]=k/n。若要概率等于0.5，只需k = n/2。若要概率等于1，只需k = n。

因此，我们有如下结论：对长度为m位的散列码，共有2m个可能的散列值，给定H（x），若要找到一个y，使得H（y）= H（x）的概率为0.5，只需要k的值为：k = 2m-1。若要上述概率为1，只需要k的值为：k = 2m。

更进一步，有下面的结论：对长度为m位的散列码，共有2m个可能的散列值，若要使任意的x，y有H（x）= H（y）的概率为0.5，只需k = 2m/2。

基于上述结论，攻击者可以进行这样一种攻击，因为它建立在生日悖论的基础之上，被称为生日攻击。

（1）攻击者产生一个有效消息的2m/2种变化，每一个消息具有同样的意义。

（2）攻击者也产生一个期望的欺骗性消息的2m/2种变化。

（3）比较两组消息，找到具有同样散列值的消息对，根据生日悖论，找到的概率大于0.5。

（4）让用户签署有效的文件，然后用欺骗性消息进行替代，因为两者的消息摘要相同，因此对有效文件的签名也是对欺骗性消息的有效签名。

一个生日攻击的例子是：

（1）A准备两份合同M和M′，一份B会同意，一份让他转让他的全部财产而被他拒绝。

（2）A对M和M′各构造32处微小变化，比如在某处添加一个空格，改变某处的行间距或字间距，这种变化不会改变合同的原意，选择进行或不进行这32处修改，可以得到232个保持原意但有微小变化的合同文本，分别产生232个64位散列值。

（3）根据前面的结论，超过0.5的概率能找到一个M和一个M′，它们的散列值相同。

（4）A提交M，经B审阅后产生64位散列值并对该值签名，返回给A。

（5）A用M′替换M。

综上，可以得出结论，散列函数要满足单向性、弱无碰撞性和强无碰撞性，散列值必须足够长。

5.1.4.4 散列函数的构造

散列函数的构造方法有三种，一种是基于数学难题的构造方法，这种方法构造的散列函数计算速度慢，不实用。第二种是利用对称密码体制来设计散列函数，第三是直接设计。

用对称加密算法构造散列函数的一种做法是把消息 M 分成长度相同的分组，M =（M1，M2，…，Mt），H0为初始值，Hi = f（Mi，Hi-1），例如Hi =EMi（Hi-1），散列值为Ht。这种方法速度慢，且有许多这样的散列函数被证明是不安全的，其安全性与E的安全性无关。下面的四种可能是安全的：

①

②

③

④

1989年，Merkle和Damgård分别独立地提出一种与分组密码类似的通用迭代结构，它利用输入消息长度是固定的定长压缩函数来构造散列函数，人们称这种结构为Merkle-Damgård结构，如图5.5所示。该结构的具体做法是：

（1）把原始消息M分成L个固定长度的块Yi-1，1≤i≤L。

（2）对最后一块填充并使其包含消息M的长度。

（3）设定初始值CV0。

（4）f为压缩函数，m为散列码的长度，b为输入块的长度，用初始向量CV0与第一块报文计算散列值产生CV1，然后由CVi-1与第 i-1块计算CVi，CVi = f（CVi-1，Yi-1），1≤ i≤ L。

（5）最后一个CVi为消息的散列值，H（M）= CVL。

如果压缩函数具有抗碰撞迭代的能力，那么迭代散列函数也具有抗碰撞的能力，具体散列函数之间的不同之处在于计算CV的函数f。

目前，国际上给出了针对迭代结构的一些新的攻击方式，如比特迫踪法、多碰撞攻击、长消息的第二原像攻击等，并证明Merkle-Damgård结构不是可证明安全的，并提出了一些改进的Merkle-Damgård结构，如宽轨道、HAIFA、Sponge等。对散列函数的结构研究正成为国际研究的热点。