第五章 信息安全原理与技术ch05-Hash函数和数字签名

信息安全原理与技术郭亚军宋建华李莉清华大学出版社2019/8/22Ch5-消息认证与数字签名第5章消息认证与数字签名•主要知识点：--认证--认证码--散列函数--MD5--SHA-512--数字签名2019/8/23Ch5-消息认证与数字签名认证•认证则是防止主动攻击的重要技术，可以防止如下一些攻击：–伪装：攻击者生成一个消息并声称这条消息是来自某合法实体，或者攻击者冒充消息接收方向消息发送方发送的关于收到或未收到消息的欺诈应答。–内容修改：对消息内容的修改，包括插入、删除、转换和修改。–顺序修改：对通信双方消息顺序的修改，包括插入、删除和重新排序。–计时修改：对消息的延迟和重放。在面向连接的应用中，攻击者可能延迟或重放以前某合法会话中的消息序列，也可能会延迟或重放是消息序列中的某一条消息。2019/8/24Ch5-消息认证与数字签名认证的目的•第一，验证消息的发送者是合法的，不是冒充的，这称为实体认证，包括对信源、信宿等的认证和识别；•第二，验证信息本身的完整性，这称为消息认证，验证数据在传送或存储过程中没有被篡改、重放或延迟等。2019/8/25Ch5-消息认证与数字签名认证的目的•可提供认证功能的认证码的函数可分为三类：–加密函数：使用消息发送方和消息接收方共享的密钥对整个消息进行加密，则整个消息的密文作为认证符。–消息认证码：它是消息和密钥的函数，产生定长度值，该值作为消息的认证符。–散列函数：它是将任意长的消息映射为定长的hash值的函数，以该hash值作为认证符。2019/8/26Ch5-消息认证与数字签名基本的认证系统模型信源认证符生成验证认证符攻击者安全信道密钥信宿2019/8/27Ch5-消息认证与数字签名消息认证码•消息认证码，简称MAC(MessageAuthenticationCode)，是一种使用密钥的认证技术，它利用密钥来生成一个固定长度的短数据块，并将该数据块附加在消息之后。•在这种方法中假定通信双方A和B共享密钥K。若A向B发送消息M时，则A使用消息M和密钥K，计算MAC＝C(K,M)2019/8/28Ch5-消息认证与数字签名消息认证码的使用MMCKMACMCKMAC比较传输发送者A接收者B2019/8/29Ch5-消息认证与数字签名消息认证码的使用（续）MCK1发送者A||EK2DK2MMACCK1比较接收者B2019/8/210Ch5-消息认证与数字签名MAC的安全要求•MAC中使用了密钥，这点和对称密钥加密一样，如果密钥泄漏了或者被攻击了，则MAC的安全性则无法保证。•在基于算法的加密函数中，攻击者可以尝试所有可能的密钥以进行穷举攻击，一般对k位的密钥，穷举攻击需要2(k-1)步。2019/8/211Ch5-消息认证与数字签名对MAC的攻击第一轮·给定M1,MAC1＝CK(M1)·对所有2k个密钥判断MACi＝CKi(M1)·匹配数2(k-n)。第二轮·给定M2,MAC2＝CK(M2)·对循环1中找到的2(k-n)个密钥判断MACi＝CKi(M2)·匹配数2(k-2n)。•攻击者可以按此方法不断对密钥进行测试，直到将匹配数缩写到足够小的范围。平均来讲，若k=an,则需a次循环2019/8/212Ch5-消息认证与数字签名针对MAC算法的攻击•攻击者针对下面的MAC算法，则不需要使用穷举攻击即可获得密钥信息。•设消息M＝(X1||X2||…||Xm)，即由64位分组Xi联结而成。定义Δ(M)＝X1X2…XmCk(M)=EK[Δ(M)]攻击者可以用任何期望的Y1至Ym-1替代X1至Xm-1，用Ym替代Xm来进行攻击，其中Ym如下计算的：Ym＝Y1Y2…Ym-1Δ(M)攻击者可以将Y1至Ym-1与原来的MAC连结成一个新的消息M’，接收方收到(M’,Ck(M))时，由于Δ(M’)=Y1Y2…Ym=Δ(M)，因此Ck(M)=EK[Δ(M’)]，接受者会认为该消息是真实。用这种办法，攻击者可以随意插入任意的长为64(m-1)位的消息。2019/8/213Ch5-消息认证与数字签名MAC的性质•一个安全的MAC函数应具有下列性质：–若攻击者知道M和Ck(M)，则他构造满足Ck(M’)=Ck(M)的消息M’在计算上是不可行的。–Ck(M)应是均匀分布的，即对任何随机选择的消息M和M’,Ck(M)=Ck(M’)的概率是2-n,其中n是MAC的位数。–设M’是M的某个已知的变换，即M’=f(M)，则Ck(M)=Ck(M’)的概率为2-n。2019/8/214Ch5-消息认证与数字签名基于DES的消息认证码D1(64位)D2(64位)DES加密DES加密O1(64位)K(56位)+O2(64位)D1(64位)D2(64位)DES加密DES加密ON-1K+ON…+KK2019/8/215Ch5-消息认证与数字签名Hash函数•Hash函数(也称散列函数或杂凑函数)是将任意长的输入消息作为输入生成一个固定长的输出串的函数，即h=H(M)。这个输出串h称为该消息的散列值（或消息摘要，或杂凑值）。2019/8/216Ch5-消息认证与数字签名安全的Hash函数的要求•H可以应用于任意长度的数据块，产生固定长度的散列值；•对每一个给定的输入m，计算H(m)是很容易的；•给定Hash函数的描述，对于给定的散列值h，找到满足H(m)=h的m在计算上是不可行的；•给定Hash函数的描述，对于给定的消息m1，找到满足m2m1且H(m2)=H(m1)的m2在计算上是不可行的；•找到任何满足H(m1)=H(m2)且m1m2的消息对(m1,m2)在计算上是不可行的。2019/8/217Ch5-消息认证与数字签名安全的Hash函数的要求•H可以应用于任意长度的数据块，产生固定长度的散列值；•对每一个给定的输入m，计算H(m)是很容易的；•给定Hash函数的描述，对于给定的散列值h，找到满足H(m)=h的m在计算上是不可行的；•给定Hash函数的描述，对于给定的消息m1，找到满足m2m1且H(m2)=H(m1)的m2在计算上是不可行的；•找到任何满足H(m1)=H(m2)且m1m2的消息对(m1,m2)在计算上是不可行的。2019/8/218Ch5-消息认证与数字签名Hash的一般结构fIV=CV0nbY0CV1Y1nCVL-1fbYL-1nCVLfnbnIV=初始值CV=链接值Yi=第i个输入分组f=压缩算法L=输入分组数n=散列值的位长b=输入分组的位长2019/8/219Ch5-消息认证与数字签名M发送者A||EK比较接收者BHHMDKM发送者A||EPRa比较接收者BHHMDPUaM发送者A||EKDKM比较接收者BHH（a）（b）（c）2019/8/220Ch5-消息认证与数字签名Hash函数的安全要求•1．单向性：对任何给定的散列码h，找到满足H(x)＝h的x在计算上是不可行的。•2．抗弱碰撞性：对任何给定的消息x，找到满足y≠x且H(x)=H(y)的y在计算上是不可行的。•3．抗强碰撞性：找到任何满足H(x)=H(y)的偶对(x,y)在计算上是不可行的。2019/8/221Ch5-消息认证与数字签名生日攻击（BirthdayAttack）•如果攻击者希望伪造消息M的签名来欺骗接收者，则他需要找到满足H(M’)=H(M)的M’来替代M。对于生成64位散列值的散列函数，平均需要尝试263次以找到M’。但是建立在生日悖论上的生日攻击法，则会更有效。•对于上述问题换种说法：假设一个函数有n个函数值，且已知一个函数值H(x)。任选k个任意数作为函数的输入值，则k必须为多大才能保证至少找到一个输入值y且H(x)=H(y)的概率大于0.5?2019/8/222Ch5-消息认证与数字签名生日悖论•我们可以如下描述这类问题：k为多大时，在k个人中至少找到两个人的生日相同的概率大于0.5？不考虑二月二十九日并且假定每个生日出现的概率相同。2019/8/223Ch5-消息认证与数字签名•首先k个人的生日排列的总数目是365k。这样，k个人有不同生日的排列数为：•因此，k个人有不同生日的概率为不重复的排列数除以总数目，得到：•则，k个人中，至少找到两个人同日出生的概率是：2019/8/224Ch5-消息认证与数字签名Yuval的生日攻击•(1)合法的签名方对于其认为合法的消息愿意使用自己的私钥对该消息生成的m位的散列值进行数字签名。•(2)攻击者为了伪造一份有(1)中的签名者签名的消息，首先产生一份签名方将会同意签名的消息，再产生出该消息的2m/2种不同的变化，且每一种变化表达相同的意义（如：在文字中加入空格、换行字符）。然后，攻击者再伪造一条具有不同意义的新的消息，并产生出该伪造消息的2m/2种变化。2019/8/225Ch5-消息认证与数字签名Yuval的生日攻击（续）•(3)攻击者在上述两个消息集合中找出可以产生相同散列值的一对消息。根据“生日悖论”理论，能找到这样一对消息的概率是非常大的。如果找不到这样的消息，攻击者再产生一条有效的消息和伪造的消息，并增加每组中的明文数目，直至成功为止。•(4)攻击者用第一组中找到的明文提供给签名方要求签名，这样，这个签名就可以被用来伪造第二组中找到的明文的数字签名。这样，即使攻击者不知道签名私钥也能伪造签名。2019/8/226Ch5-消息认证与数字签名中间相遇攻击法（MeetintheMiddleAttack）•(1)根据已知数字签名的明文，先产生散列函数值h。•(2)再根据意图伪造签名的明文，将其分成每个64位长的明文分组：Q1,Q2,…,QN-2。Hash函数的压缩算法为：hi=EQi[hi-1]，1iN-2。•(3)任意产生232个不同的X，对每个X计算EX[hN-2]。同样的，任意产生232个不同的Y，对每个Y计算DY[G]，D是相对应E的解密函数。2019/8/227Ch5-消息认证与数字签名中间相遇攻击法（MeetintheMiddleAttack）-续•(4)根据“生日悖论”，有很大的概率可以找到一堆X及Y满足EX[hN-2]=DY[G]。•(5)如果找到了这样的X和Y，攻击者重新构造一个明文：Q1,Q2,…,QN-2,X,Y。这个新的明文的散列值也为h，因此攻击者可以使用已知的数字签名为这个构造的明文伪造新的明文的签名。2019/8/228Ch5-消息认证与数字签名MD5•MD5（Message-DigestAlgorithm5）是由RonaldL.Rivest（RSA算法中的“R”）这90年代初开发出来的，经MD2、MD3和MD4发展而来。它比MD4复杂，但设计思想类似，同样生成一个128位的信息散列值。其中，MD2是为8位机器做过设计优化的，而MD4和MD5却是面向32位的计算机。•2004年8月，在美国召开的国际密码学会议（Crypto’2004）上，王小云教授给出破解MD5、HAVAL-128、MD4和RIPEMD算法的报告。给出了一个非常高效的寻找碰撞的方法，可以在数个小时内找到MD5的碰撞。2019/8/229Ch5-消息认证与数字签名MD5算法步骤•1）填充消息：任意长度的消息首先需要进行填充处理，使得填充后的消息总长度与448模512同余（即填充后的消息长度448mod512）。填充的方法是在消息后面添加一位“1”，后续都是“0”。•2）添加原始消息长度：在填充后的消息后面再添加一个64位的二进制整数表示填充前原始消息的长度。这时经过处理后的消息长度正好是512位的倍数。•3）初始值（IV）的初始化：MD5中有四个32位缓冲区，用（A,B,C,D）表示，用来存储散列计算的中间结果和最终结果，缓冲区中的值被称为链接变量。首先将其分别初始化为为：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。2019/8/230Ch5-消息认证与数字签名MD5算法步骤-续•4）以512位的分组为单位对消息进行循环散列计算：经过处理的消息，以512位为单位，分成N个分组