第4讲消息认证技术new2

第4章消息认证技术Hash函数消息认证码MD5算法SHA-1算法Hash函数的攻击分析为什么要进行消息认证？信息在传输过程中有可能被改变！主动攻击——篡改消息截获Bob发出的消息，篡改后再转发给Alice3BobAliceEve通信网络如何确认消息来自发送方？IloveyouIdon’tloveyou完整性需要验证：信息发送方是否真实？接收方是否真实？信息在传输过程中是否被改变？信息的到达时间是否在指定的期限内？消息认证是指对消息的真实性和完整性的验证。对消息的真实性的验证，也称为消息源认证，即验证消息发送者或消息的来源是真实的。对消息的完整性验证，也称为消息完整性认证，即验证消息在传送或存储过程中未被篡改、重放、删除或插入等。4.1Hash函数Hash函数，就是将一种任意长度的消息压缩成某一固定长度的消息摘要的函数，又称消息摘要函数，散列函数或杂凑函数，记为：h=H(M)。我们把Hash值称为输入数据M的“数字指纹”。Hash函数的这种单向性特征和输出数据长度固定的特征使得它可以用于检验消息的完整性是否遭到破坏。如果消息或数据被篡改，那么数字指纹就不正确了。4.1Hash函数用作消息认证的Hash函数具有如下一些性质：(1)消息M可以是任意长度的数据。(2)给定消息M，计算它的Hash值h=H(M)是很容易的。(3)任意给定h，则很难找到M使得h=H(M)，即给出Hash值，要求输入M在计算上是不可行的，即运算过程是不可逆的，这种性质称为函数的单向性。(4)给定消息M和其Hash值H(M)

，要找到另一个

M’，且M

≠M’，使得H(M)=H(M’)在计算上是不可行的，这条性质被称为抗弱碰撞性。(5)对于任意两个不同的消息

M

≠M’，它们的摘要值不可能相同，这条性质被称为抗强碰撞性。4.1Hash函数弱抗碰撞性保证对于一个消息M及其Hash值，无法找到一个替代消息M’

，使它的Hash值与给定的Hash值相同。这条性质可用于防止伪造。强抗碰撞性对于消息Hash函数的安全性要求更高，这条性质保证了对生日攻击的防御能力。碰撞性是指对于两个不同的消息M和M’，如果它们的摘要值相同，则发生了碰撞。虽然可能的消息是无限的，但可能的摘要值却是有限的。因此，不同的消息可能会产生同一摘要，碰撞是可能存在的。但是，Hash函数要求用户不能按既定需要找到一个碰撞，意外的碰撞更是不太可能的。显然，从安全性的角度来看，Hash函数输出的比特越长，抗碰撞的安全强度越大。4.1.1一个简单的Hash函数4.1.1一个简单的Hash函数

对于明文m，按每组n比特进行划分，如果最后一组长度不够，则补充0。不妨设划分为r组，mi={mi1，mi2，…，min}，1≤i≤r，mij=0或1，然后将各分组逐比特进行模2加运算，则输出为h={h1，h2，…，hn}，其中h1=m11+m21+…+mr1(mod2)，…，hn=m1n+m2n+…+mm(mod2)。从定义可见，hi表示所有分组的第i比特进行模2加，因此，若消息改变，摘要值也会随之改变。一个例外的情况是，若消息出错，而摘要值仍然不变的概率为2-n。当n充分大时，出错的概率或者说消息被篡改的概率非常小，视为小概率事件，可忽略不计。4.1.2完整性检验一般方法消息完整性检验的一般机制如图所示。无论是存储文件还是传输文件，都需要同时存储或发送该文件的数字指纹；验证时，对于实际得到的文件重新产生其数字指纹，再与原数字指纹对比，如果一致，则说明文件是完整的。否则，是不完整的。4.2消息认证码消息的完整性检验，只能检验消息是否是完整的，不能说明消息是否是伪造的。因为，一个伪造的消息与其对应的数字指纹也是匹配的。消息认证具有两层含义：一是检验消息的来源是真实的，即对消息的发送者的身份进行认证；二是检验消息是完整的，即验证消息在传送或存储过程中未被篡改、删除或插入等。当需要进行消息认证时，仅有消息作为输入是不够的，需要加入密钥k，这就是消息认证的原理。能否认证，关键在于信息发送者或信息提供者是否拥有密钥k。消息认证码(MessageAuthenticationCode，MAC)通常表示为MAC=CK(M)其中M是可变长的消息，K是收发双方共享的密钥，函数值CK(M)是定长的认证码，也称为密码校验和。MAC就是带密钥的消息摘要函数，其实就是一种带密钥的数字指纹，它与不带密钥的数字指纹是有本质区别的。4.2消息认证码1.消息认证认证码被附加到消息后以M||MAC方式一并发送，收方通过重新计算MAC以实现对M的认证。如图所示。假定收、发双方共享密钥k，如果收到的MAC与计算得出的MAC一致，那么可以得出如下结论：①接收方确信消息M未被篡改。此为完整性验证。②接收方确信消息来自所声称的发送者，因为没有其他人知道这个共享密钥，其他人也就不可能为消息M附加合适的MAC。此为消息源验证。4.2消息认证码2.消息认证与保密在(1)中，消息以明文方式传送，这一过程只提供认证而不具备保密性。如图4-2-2所示提供一种即加密又认证的方式，发送方发送Ek2[M||Ck1(M)]。该种处理方式除具备(1)的功能外，还具有保密性。4.2消息认证码3.密文认证改变(2)中加密的位置，得到另外一种消息保密与认证方式，如图所示。该种处理方式先对消息进行加密，然后再对密文计算MAC，传送Ek2(M)||Ck1(Ek2(M))给接收方。接收方先对收到的密文进行认证，认证成功后，再解密。4.3MD5算法MD表示消息摘要(MessageDigest，简记为MD)，MD5以512比特一块的方式处理输入的消息文本，每个块又划分为16个32比特的子块。算法的输出是由4个32比特的块组成，将它们级联成一个128比特的摘要值。MD5算法如图所示，包括以下几个步骤。4.3MD5算法(1)填充消息使其长度正好为512位的整数倍L首先在消息的末尾处附上64比特的消息长度的二进制表示，大小为，n表示消息长度。然后在消息后面填充一个“1”和多个“0”，填充后的消息恰好是512比特的整倍长L。Y0，Y1，…，YL-1表示不同的512比特长的消息块，用M[0]，M[1]，…，M[N－1]表示各个Yq中按32比特分组的字，N一定是16的整数倍。(2)初始化缓冲区算法中使用了128位的缓冲区，每个缓冲区由4个32比特的寄存器A，B，C，D组成，先把这4个寄存器初始化为：A=01234567

B=89ABCDEF

C=FEDCBA98D=765432104.3MD5算法(3)处理512位消息块Yq，进入主循环主循环的次数正好是消息中512位的块的数目L。先从Y0开始，上一循环的输出作为下一循环的输入，直到处理完YL-1为止。消息块Yq的处理，以当前的512位数据块Yq和128位缓冲值A，B，C，D作为输入，并修改缓冲值的内容。消息块的处理包含4轮操作，每一轮由16次迭代操作组成，上一轮的输出作为下一轮的输入，如图所示。4.3MD5算法4轮处理具有相似的结构，但每轮处理使用不同的非线性函数，如图所示。4个非线性函数分别为：常数表T[i]()共有64个元素，每个元素32位长，T[i]＝232abs(sin(i)),其中i是弧度。处理每一个消息块Yi时，每一轮使用常数表T[i]中的16个，正好用4轮。4.3MD5算法(4)输出每一轮不断地更新缓冲区A，B，C，D中的内容，4轮之后进入下一个主循环，直到处理完所有消息块为止。最后输出就是结束时缓冲区中的内容。4.4SHA-1算法SHA（SecureHashAlgorithm，SHA）是由美国NIST开发，作为联邦信息处理标准于1993年发表，1995年修订，成为SHA-1版本。SHA-1在设计方面基本上模仿MD5，如图所示。4.4SHA-1算法(1)填充消息首先将消息填充为512的整数倍，填充方法与MD5相同。与MD5不同的是SHA-1的输入为长度小于2的64次方比特的消息。(2)初始化缓冲区初始化160位的消息摘要缓冲区（即设定IV值），该缓冲区用于保存中间和最终摘要结果。每个缓冲区由5个32比特的寄存器A，B，C，D，E组成，初始化为：A=67452301B=EFCDAB89C=98BADCFED=10325476E=C2D2E1F04.4SHA-1算法(3)处理512位消息块Yq，进入主循环主循环的次数正好是消息中512位的块的数目L。先从Y0开始，上一循环的输出作为下一循环的输入，直到处理完YL-1为止。主循环有四轮，每轮20次操作（有四轮，每轮16次操作）。每次操作对A、B、C、D和E中的三个做一次非线性函数运算，然后进行与MD5中类似的移位运算和加运算。四个非线性函数为用下面的算法将消息块从16个32比特子块变成80个32比特子块（W0到W79）：4.4SHA-1算法该算法主循环4轮，每轮20次，0≤t≤79，每一次的变换的基本形式是相同的：其中(A<<5)表示寄存器A循环左移5比特，(B<<30)表示寄存器K循环左移30比特。80次处理完后，处理下一个512位的数据块，直到处理完YL-1为止。最后输出A║B║C║D║E级联后的结果。4.4SHA-1算法SHA－1与MD5的比较如表所示。4.5Hash函数的攻击分析问题：在一个教室中最少应有多少学生才使得至少有两个学生的生日在同一天的概率不小于1/2？忽略闰年，假设所有的生日都是等可能的答案是234.5Hash函数的攻击分析考虑23个人的情况，计算他们生日互不相同的概率。将他们列成一行。第一个人的生日用了一天，因此第二个人生日是另一天的概率是(1－1/365)。对第三人来说，已经有两天用过了，第三个生日和前两个不同的概率是(1－2/365)。因此，三个人生日互不相同的概率是(1－1/365)(1－2/365)。如此继续，可以得到23个人生日互不相同的概率是0.493因此，至少有两个人有相同生日的概率是1－0.493＝0.507。4.5Hash函数的攻击分析所以，屋子里有23个人，其中两人生日相同的概率略大于50%。如果是30人，概率大约是70%。这是个看起来有些让人吃惊的结论，称为生日悖论（birthdayparadox）生日攻击这个术语来自于生日悖论。生日攻击方法可用于攻击任何类型的Hash方案。生日攻击方法只依赖于消息摘要的长度，即Hash函数值的长度。生日攻击给出消息摘要的长度的一个下界。4.5Hash函数的攻击分析除生日攻击法外，对一些类型的Hash函数还有一些特殊的攻击方法，例如，中间相遇攻击、修正分组攻击和差分分析法等。山东大学王小云教授等于2004年8月在美国加州召开的国际密码大会(Crypto’2004)上所做的Hash函数研究报告中指出，她们已成功破译了MD4、MD5、HAVAL-128、RIPEMD-128等Hash算法。2006年，王小云宣布了攻破SHA-1的消息。她的研究成果表明了从理论上讲电子签名可以伪造，必须及时添加限制条件，或者重新选用更为安全的密码标准，以保证电子商务的安全。小结1．用作消息认证的摘要函数具有单向性、抗碰撞性。单向函数的优良性质，使其成为公钥密码、消息压缩的数学基础。2．消息认证码特指使用收发双方共享的密钥K和可变长的消息M，输出长度固定的函数值MAC，也称为密码校验和。MAC就是带密钥的消息摘要函数，或称为一种带密钥的数字指纹，它与普通摘要函数(Hash函数)是有本质区别的。小结3．消息完整性校验的一般准则是将实际得到的消息的数字指纹，与原数字指纹进行匹配。如果一致，则说明消息是完整的