《信息安全技术》课件第4章.ppt

1、4.1 Hash函数4.2 消息认证码4.3 MD5算法4.4 SHA-1算法4.5 Hash函数的攻击分析小结习题消息摘要函数、散列函数或杂凑函数，记为h=H(M)。我们把Hash函数值h称为输入数据M的“数字指纹”。Hash函数的这种单向性特征和输出数据长度固定的特征使得它可以用于检验消息的完整性是否遭到破坏。如果消息或数据被篡改，那么数字指纹就不正确了。4.1 Hash函数函数 用做消息认证的Hash函数具有如下一些性质:(1)消息M可以是任意长度的数据。(2)给定消息M，计算它的Hash函数值h=H(M)是很容易的。(3)任意给定，则很难找到M使得h=H(M)，即给出Hash函数值，要

2、求输入M在计算上是不可行的。这说明Hash函数的运算过程是不可逆的，这种性质被称为函数的单向性。(4)给定消息M和其Hash函数值H(M)，要找到另一个M，且MM，使得H(M)=H(M)在计算上是不可行的，这条性质被称为抗弱碰撞性。抗弱碰撞性保证对于一个消息M及其Hash函数值，无法找到一个替代消息M，使它的Hash函数值与给定的Hash函数值相同。这条性质可用于防止伪造。抗强碰撞性对于消息Hash函数的安全性要求更高。这条性质保证了对生日攻击方法的防御能力。碰撞性是指对于两个不同的消息M和M，如果它们的摘要值相同，则发生了碰撞。虽然可能的消息是无限的，但可能的摘要值却是有限的。如Hash函数

3、MD5，其Hash函数值长度为128位，不同的Hash函数值个数为2128。因此，不同的消息可能会产生同一摘要，碰撞是可能存在的。但是，Hash函数要求用户不能按既定需要找到一个碰撞，意外的碰撞更是不太可能的。显然，从安全性的角度来看，Hash函数输出的比特越长，抗碰撞的安全强度越大。4.1.1 一个简单的一个简单的Hash函数函数基于安全强度的需要，现有的Hash函数一般都十分复杂。本节我们介绍一个简单的Hash函数，便于建立对Hash函数的感性认识。对于明文m，按每组n比特进行划分，如果最后一组长度不够，则补充0。不妨设划分为r组，mi=mi1，mi2，min，1ir，mij=0或1，然后

4、将各分组逐比特进行模2加运算，则输出为h=h1，h2，hn，其中h1=m11+m21+mr1(mod 2)，hn=m1n+m2n+mm(mod 2)。从定义可见，hi表示所有分组的第i比特进行模2加，因此，若消息改变，摘要值也会随之改变。一个例外的情况是，若消息出错，而摘要值仍然不变的概率为2-n。当n充分大时，出错的概率或者说消息被篡改的概率非常小，视为小概率事件，可忽略不计。4.1.2 完整性检验的一般方法完整性检验的一般方法消息完整性检验的一般机制如图4-1-1所示。无论是存储文件还是传输文件，都需要同时存储或发送该文件的数字指纹;验证时，对于实际得到的文件重新产生其数字指纹，再与原数字

5、指纹进行对比，如果一致，则说明文件是完整的，否则，是不完整的。图 4-1-1 消息完整性检验的一般机制 在4.1节中我们简单介绍了消息的完整性检验，这只能检验消息是否是完整的，不能说明消息是否是伪造的。因为，一个伪造的消息与其对应的数字指纹也是匹配的。消息认证具有两层含义:一是检验消息的来源是真实的，即对消息的发送者的身份进行认证;二是检验消息是完整的，即验证消息在传送或存储过程中未被篡改、删除或插入等。4.2 消消 息息 认认 证证 码码 产生消息的数字指纹的方法很多。当需要进行消息认证时，仅有消息作为输入是不够的，需要加入密钥K，这就是消息认证的原理。能否认证，关键在于信息发送者或信息提供

6、者是否拥有密钥K。消息认证码(Message Authentication Code，MAC)通常表示为MAC=CK(M)其中:M是长度可变的消息;K是收、发双方共享的密钥;函数值CK(M)是定长的认证码，也称为密码校验和。MAC是带密钥的消息摘要函数，即一种带密钥的数字指纹，它与不带密钥的数字指纹是有本质区别的。1.消息认证认证码被附加到消息后以MMAC方式一并发送，接收方通过重新计算MAC以实现对M的认证，如图4-2-1所示。图 4-2-1 消息认证假定收、发双方共享密钥K，如果接收方收到的MAC与计算得出的MAC一致，那么可以得出如下结论:(1)接收方确信消息M未被篡改。此为完整性验证。

7、(2)接收方确信消息来自所声称的发送者，因为没有其他人知道这个共享密钥，所以其他人也就不可能为消息M附加合适的MAC。此为消息源验证。2.消息认证与保密在消息认证中，消息以明文方式传送，这一过程只提供认证而不具备保密性。如图4-2-2所示提供了一种既加密又认证的方式，发送方发送EK2(M)CK1(M)。该种处理方式除具备息认证的功能外，还具有保密性。图 4-2-2 消息认证与保密3.密文认证密文认证改变消息认证与保密中加密的位置，得到另外一种消息保密与认证方式，即密文认证，如图4-2-3所示。该种处理方式先对消息进行加密，然后再对密文计算MAC，传送EK2(M)CK1(EK2(M)给接收方。接

8、收方先对收到的密文进行认证，认证成功后，再解密。图 4-2-3 密文认证MD表示消息摘要(Message Digest，MD)。MD4算法是1990年由Ron Rivest设计的一个消息摘要算法，该算法的设计不依赖于任何密码体制，采用分组方式进行各种逻辑运算而得到。1991年MD4算法又得到了进一步的改进，改进后的算法就是MD5算法。MD5算法以512 bit为一块的方式处理输入的消息文本，每个块又划分为16个32 bit的子块。算法的输出是由4个32 bit的块组成的，将它们级联成一个128 bit的摘要值。MD5算法如图4-3-1所示，包括以下几个步骤。4.3 MD5算法算法 图 4-3-

9、1 MD5算法(1)填充消息使其长度正好为512 bit的整数倍L。首先在消息的末尾处附上64 bit的消息长度的二进制表示，大小为n(mod 264)，n表示消息长度。然后在消息后面填充一个“1”和多个“0”，填充后的消息恰好是512 bit的整数倍长L。Y0，Y1，YL-1表示不同的512 bit长的消息块，用M0，M1，MN1表示各个Yq中按32 bit分组的字，N一定是16的整数倍。(2)初始化缓冲区。算法中使用了128 bit的缓冲区，每个缓冲区由4个32 bit的寄存器A、B、C、D组成，先把这4个寄存器初始化为A=01 23 45 67 B=89 AB CD EFC=FE DC

10、BA 98D=76 54 32 10(3)处理512 bit消息块Yq，进入主循环。主循环的次数正好是消息中512 bit的块的数目L。先从Y0开始，上一循环的输出作为下一循环的输入，直到处理完YL-1为止。消息块Yq的处理，以当前的512 bit数据块Yq和128 bit缓冲值A、B、C、D作为输入，并修改缓冲值的内容。消息块的处理包含4轮操作，每一轮由16次迭代操作组成，上一轮的输出作为下一轮的输入，如图4-3-2所示。4轮处理具有相似的结构，但每轮处理使用不同的非线性函数，如图4-3-3所示。图 4-3-2 消息块处理的主循环图 4-3-3 某一轮的执行过程4个非线性函数分别为F(X，Y

11、，Z)=(XY)(Z)G(X，Y，Z)=(XZ)(Y)H(X，Y，Z)=XYZI(X，Y，Z)=Y(X)各种运算符号的含义:XY表示X与Y按位逻辑“与”;XY表示X与Y按位逻辑“或”;XY表示X与Y按位逻辑“异或”;表示X按位逻辑“补”;X+Y表示整数模232加法运算;Xs表示将X循环左移s个位置。XZZ常数表Ti(1i64)共有64个元素，每个元素长为32 bit，Ti232ABS(sin(i)，其中i是弧度。处理每一个消息块Yi时，每一轮使用常数表Ti中的16个，正好用4轮。(4)输出。每一轮不断地更新缓冲区A、B、C、D中的内容，4轮之后进入下一个主循环，直到处理完所有消息块为止。最后输

12、出的就是运算结束时缓冲区中的内容。SHA(Secure Hash Algorithm，SHA)由美国NIST开发，作为联邦信息处理标准于1993年发表，1995年修订后，成为SHA1版本。SHA1算法在设计方面基本上是模仿MD5算法，如图4-4-1所示，包含以下几个过程。4.4 SHA-1算法算法图 4-4-1 SHA1算法(1)填充消息。首先将消息填充为512的整数倍，填充方法与MD5算法相同。与MD5算法不同的是SHA-1的输入为长度小于264 bit的消息。(2)初始化缓冲区。初始化160 bit的消息摘要缓冲区(即设定IV值)，该缓冲区用于保存中间和最终摘要结果。每个缓冲区由5个32

13、bit的寄存器A、B、C、D、E组成，初始化为 A=67 45 23 01 B=EF CD AB 89 C=98 BA DC FE D=10 32 54 76 E=C2 D2 E1 F0(3)处理512 bit消息块Yq，进入主循环。主循环的次数正好是消息中512 bit的块的数目L。先从Y0开始，以上一循环的输出作为下一循环的输入，直到处理完YL-1为止。主循环有4轮，每轮20次操作(MD5算法有4轮，每轮16次操作)。每次操作对A、B、C、D和E中的3个做一次非线性函数运算，然后进行与MD5算法中类似的移位运算和加运算。四个非线性函数为ft(X，Y，Z)=(XY)(Z)(0t19)ft(X

14、，Y，Z)=XYZ (20t39)ft(X，Y，Z)=(XY)(XZ)(YZ)(40t59)ft(X，Y，Z)=XYZ (60t79)该算法使用了常数序列Kt(0t79)，分别为Kt=5a827999 (0t19)Kt=6ed9eba1 (20t39)Kt=8f1bbcdc (40t59)Kt=ca62c1d6 (60t79)X 用下面的算法将消息块从16个32 bit子块变成80个32 bit子块(W0到W79):Wt=Mt (0t15)Wt=(Wt-3Wt-8Wt-14Wt-16)1 (16t79)该算法主循环4轮，每轮20次，0t79，每一次的变换的基本形式是相同的:A(E+ft(B，C

15、，D)+(A5)+Wt+KtB=AC=(B30)D=CE=D其中:(A5)表示寄存器A循环左移5 bit，(B30)表示寄存器K循环左移30 bit。80次处理完后，处理下一个512 bit的数据块，直到处理完YL-1为止。最后输出ABCDE级联后的结果。SHA-1算法与MD5算法的比较如表4-4-1所示。表表4-4-1 SHA-1算法与算法与MD5算法的比较算法的比较 Hash函数须满足4.1节的5条性质，然而，抗强碰撞性对于消息Hash函数的安全性要求是非常高的。例如，MD5算法输出的Hash函数值总数为2128，SHA-1算法输出的Hash函数值总数为2160，这说明可能Hash函数值是

16、有限的，而输入的消息是无限的，因此，函数的碰撞性是可能存在的。评价Hash函数的一个最好的方法是看攻击者找到一对碰撞消息所花的代价有多大。一般地，假设攻击者知道Hash函数，攻击者的主要目标是找到一对或更多对碰撞消息。目前已有一些攻击Hash函数的方案和计算碰撞消息的方法，这些方法中的生日攻击方法可用于攻击任何类型的Hash函数方案。4.5 Hash函数的攻击分析函数的攻击分析 生日攻击方法只依赖于消息摘要的长度，即Hash函数值的长度。生日攻击给出消息摘要长度的一个下界。一个40 bit长的消息摘要是很不安全的，因为仅仅用220(大约一百万)次Hash函数值的随机计算就可至少以1/2的概率找到一对碰撞。为了抵抗生日攻击，通常建议消息摘要的长度至少应为128 bit，此时生日攻击需要约264次Hash函数值的计算。除生日攻击法外，对一些类型的Hash函数还有一些特殊的攻击方法，例如，中间相遇攻击法、修正分组攻击法和差分分析法等。值得一提的是，山东大学王小云教授等人于2004年8月在美国加州召开的国际密码大会(Crypto2004)上所做的Hash函数研究报告中指出，他们已成功破译了MD