第5章消息认证-资料课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第5章 消息认证,8/8/2024,1,第5章 消息认证8/20/20231,主要内容,消息认证基本概念,消息加密认证,消息认证码,hash函数,8/8/2024,2,主要内容消息认证基本概念 8/20/20232,概 念,认证(Authentication)：即鉴别、确认，它是证实某事是否名副其实，或是否有效的一个过程。,认证与加密的区别：,加密用以确保数据的保密性，阻止对手的被动攻击，如截取、窃听。,认证用以确保报文发送者和接收者的真实性以及报文的完整性，阻止对手的主动攻击，如冒充、篡改、重播等。,认证往往是应用系统中安全保护的第一道防线，,极为重要,。,8/8/2024,3,概 念认证(Authentication)：即鉴别、确,基本思想,通过验证称谓者(人或事)的一个或多个,参数,的真实性和有效性，来达到验证称谓者是否名副其实的目的。,常用的参数有：口令、标识符、密钥、信物、智能卡、指纹、视网纹等。,利用人的生理特征参数进行认证的安全性高，但技术要求也高，至今尚未普及。目前广泛应用的还是,基于密码,的认证技术。,8/8/2024,4,基本思想通过验证称谓者(人或事)的一个或多个参数的真实性和有,没有消息认证的通信系统是极为危险的,8/8/2024,5,没有消息认证的通信系统是极为危险的 8/20/20235,消息认证(Message Authentication),消息认证用于抗击主动攻击,验证接收消息的真实性和完整性,真实性,的确是由所声称的实体发过来的,完整性,未被篡改、插入和删除,验证消息的顺序性和时间性（未重排、重放和延迟）,8/8/2024,6,消息认证(Message Authentication)消,需求,泄密：将消息透露给没有合法秘密钥的任何人或程序。,传输分析：分析通信双方的通信模式，如连接频率，时间等,伪装：攻击者产生一条消息并声称来自某合法实体,内容修改：对消息进行插入、删除、转化、修改,顺序修改：对消息顺序进行插入、删除、重新排序,计时修改：对消息的延时和重放,发送方否认,接受方否认,对付1、2可用加密；,对付3、4、5、6可用消息认证；,对付7、8可用数字签名,8/8/2024,7,需求泄密：将消息透露给没有合法秘密钥的任何人或程序。8/20,消息认证的基本概念,消息认证,：验证所收到的消息确定是来自真正的发送方且未被修改过。,认证符,：一个用来认证消息的值。由消息的发送方产生认证符，并传递给接收方。,认证函数,：产生认证符的函数，认证函数实际上代表了一种产生认证符的方法。,可提供认证功能的认证码的函数可分为三类：,1、,消息加密,2、,消息认证码,3、,Hash函数,8/8/2024,8,消息认证的基本概念消息认证：验证所收到的消息确定是来自真正的,1,消息加密-在对称加密体制下,由于攻击者不知道密钥K，他也就不知道如何改变密文中的信息位才能在明文中产生预期的改变。,接收方可以根据解密后的明文是否具有合理的语法结构来进行消息认证。,但有时发送的明文本身并没有明显的语法结构或特征，例如二进制文件，因此很难确定解密后的消息就是明文本身。,M,E,K,E,K,(M),D,K,M,8/8/2024,9,1 消息加密-在对称加密体制下由于攻击者不知道密钥K，他,根据明文M和公开的函数F产生FCS，即错误检测码，或帧校验序列，校验和。,把M和FCS合在一起加密，并传输。,接收端把密文解密，得到M。,根据得到的M，按照F计算FCS，并与接收到的FCS比较是否相等。,M,F,F,M,FCS,比较,E,K,D,K,M,FCS,内部错误控制,8/8/2024,10,根据明文M和公开的函数F产生FCS，即错误检测码，或帧校验序,攻击者可以构造具有正确错误控制码的消息，虽然攻击者不知道解密后的明文，但可以造成混淆并破坏通信。,M,F,FCS,E,K,D,K,M,外部错误控制,F,比较,8/8/2024,11,攻击者可以构造具有正确错误控制码的消息，虽然攻击者不知道解密,1,消息加密-在公钥加密体制下,由于大家都知道B的公钥，所以这种方式不提供认证，只提供加密。,M,E,K,Ub,E,KUb,(M),D,K,Rb,M,I,.普通加密,A,B,8/8/2024,12,1 消息加密-在公钥加密体制下由于大家都知道B的公钥，所,1,消息加密-在公钥加密体制下,由于只有A有用于产生E,KRa,(M)的密钥，所以此方法提供认证。,由于大家都有K,Ua,，所以此方法不提供加密。,M,E,K,Ra,E,KRa,(M),D,K,Ua,M,II,.认证和签名,A,B,8/8/2024,13,1 消息加密-在公钥加密体制下由于只有A有用于产生EKR,1,消息加密-在公钥加密体制下,提供认证和加密。,一次通信中要执行四次复杂的公钥算法。,M,E,K,Ra,E,KRa,(M),D,K,Ua,M,III,.加密认证和签名,A,B,E,K,Ub,E,KUb,(E,KRa,(M),D,K,Rb,E,KRa,(M),8/8/2024,14,1 消息加密-在公钥加密体制下提供认证和加密。MEKRa,2,消息认证码(MAC),Message Authenticaion Code,消息认证码是消息和密钥的公开函数，它产生定长的值，以该值作为认证符。,利用密钥和消息生成一个固定长度的短数据块，并将其附加在消息之后。,通信双方共享密钥K,8/8/2024,15,2 消息认证码(MAC)Message Authentic,2,消息认证码用于认证,A和B共享密钥K,A计算MAC=C,k,(M),M和MAC一起发送到B,B对收到的M，计算MAC，比较两个MAC是否相同。,M,C,MAC,K,C,比较,K,MAC,如果两个MAC相等，则：,接收方可以相信消息未被修改，因为如果攻击者改变了消息，由于不知道k，无法生成正确的MAC。,接收方可以相信消息的确来自确定的发送方。因为其他人不能生成和原始消息相应的MAC。,8/8/2024,16,2 消息认证码用于认证A和B共享密钥KMCMACKC比较KM,MAC函数与加密函数的区别,MAC函数与加密函数类似，都需要明文、密钥和算法的参与。,但MAC算法不要求可逆性，而加密算法必须是可逆的。,例如：使用100比特的消息和10比特的MAC，那么总共有2,100,个不同的消息，但仅有2,10,个不同的MAC。也就是说，平均每2,90,个消息使用的MAC是相同的。,因此，认证函数比加密函数更不易被攻破，因为即便攻破也无法验证其正确性。关键就在于加密函数是一对一的，而认证函数是多对一的。,8/8/2024,17,MAC函数与加密函数的区别MAC函数与加密函数类似，都需要明,消息认证码的基本用途,只提供消息认证，不提供保密性。（见前）,提供消息认证和保密性：,M,|,C,K,1,C,M,C,K1,(M),K,1,比较,E,K,2,D,K,2,A,B,A和B共享K1和K2,K1：用于生成MAC,K2：用于加密,与明文有关的认证,8/8/2024,18,消息认证码的基本用途只提供消息认证，不提供保密性。（见前）M,消息认证码的基本用途,提供消息认证和保密性：,A,B,A和B共享K1和K2,K1：用于生成MAC,K2：用于加密,与密文有关的认证,M,|,C,K,1,C,K,1,比较,E,K,2,D,K,2,8/8/2024,19,消息认证码的基本用途提供消息认证和保密性：ABA和B共享K1,对MAC的攻击攻击密钥,已知消息M,1,和MAC算法C，以及MAC,1,=,C,k1,(M,1,),，现要破解k,1,。密钥为k个bit，MAC为n个bit。,当,kn：,可能的密钥个数为2,k,。可能的MAC个数为2,n,个。,所以许多不同的密钥(约2,k-n,个)，计算出来的MAC都等于MAC,1,。这些密钥中哪一个是正确的密钥不得而知。这时需要新的M-MAC对来测试这2,k-n,个密钥，于是有如下的,重复攻击,：,8/8/2024,20,对MAC的攻击攻击密钥已知消息M1和MAC算法C，以及MA,重复攻击,Step 1:,给定,M,1,和MAC,1,=,C,k1,(M,1,),对所有2,k,个密钥，判断MAC,i,=,C,ki,(M,1,),匹配数约为：2,k-n,Step 2:,给定,M,2,和MAC,2,=,C,k2,(M,1,),对所有2,k-n,个密钥，判断MAC,i,=,C,ki,(M,2,),匹配数约为：2,k-2n,平均来讲，若,k,=,x*n,，则需,x,次循环才能找到正确的密钥。,所以，用穷举法攻破MAC比攻破加密算法要困难得多。,8/8/2024,21,重复攻击Step 1:8/20/202321,对MAC的攻击攻击算法,考虑下面的算法：,消息M=(X,1,X,2,X,m,)是由64比特长的分组X,i,(i=1,m)链接而成,MAC算法是：,加密算法是DES。因此，密钥长为56比特。,如果敌手得到MC,K,(M)，那么敌手使用穷搜索攻击寻找K将需做2,56,次加密。,很困难!,但攻击者可以改变M的内容，却使MAC正确。,方法如下：,8/8/2024,22,对MAC的攻击攻击算法考虑下面的算法：8/20/20232,用Y,1,替换X,1,，Y,2,替换X,2,，Y,m,替换X,m,，其中Y,1,，Y,2,，Y,m,是攻击者编造的假消息。且,Y,m,=Y,1,Y,2,Y,m-1,(M),，,当接收者收到这个消息,：,M=(Y,1,Y,2,Y,m,),则,(M)=,Y,1,Y,2,Y,m,=,(M),所以：,C,K,(M)=C,K,(M)通过了验证，攻击得逞。,8/8/2024,23,用Y1替换X1，Y2替换X2，Ym替换Xm，其,MAC函数应具有的性质,若攻击者已知M和,C,K,(M),，则他构造满足：,C,K,(M)=C,K,(M)的消息M在计算上不可行,C,K,(M)应是均匀分布的，即对于随机消息M和M，,C,K,(M)=C,K,(M)的概率是2,-n,，n是MAC的位数,8/8/2024,24,MAC函数应具有的性质若攻击者已知M和CK(M)，则他构造满,基于DES的消息认证码,使用最广泛的MAC算法之一：数据认证算法,过程：,把需要认证的数据分成连续的64位的分组。,若最后一个分组不是64位，则填0,利用DES加密算法E和密钥K，计算认证码。,8/8/2024,25,基于DES的消息认证码使用最广泛的MAC算法之一：数据认证算,数据认证算法似乎可以满足前面提出的要求。,DAC M-bits,(16 to 64 bits),8/8/2024,26,数据认证算法似乎可以满足前面提出的要求。DAC M-bits,为什么不直接使用加密而使用分离的消息认证码？,保密性与真实性是两个不同的概念,根本上,信息加密提供的是保密性而非真实性,加密代价大(公钥算法代价更大),鉴别函数与保密函数的分离能提供功能上的灵活性,某些信息只需要真实性,不需要保密性,广播的信息难以使用加密(信息量大),网络管理信息等只需要真实性,政府/权威部门的公告,8/8/2024,27,为什么不直接使用加密而使用分离的消息认证码？保密性与真实性是,3 Hash函数(杂凑函数、散列函数),Hash的特点：,与消息认证码一样，hash函数的输入是可变的消息M，输出是固定大小的hash码H(M)，或称消息摘要,(Message Digest),、hash值。,与消息认证码不同的是，hash码的产生过程中并不使用密钥。,Hash码是所有消息的函数，改变消息的任何一位或多位，都会导致hash码的改变。,Hash算法通常是公开的。,又称为：哈希函数、数字指纹（,Digital finger print),、压缩（,Compression),函数、紧缩（,Contraction,）函数、数据鉴别码,DAC,（,Data authentication code,）、篡改检验码,MDC(Manipulation detection code),8/8/2024,28,3 Hash函数(杂凑函数、散列函数)Hash的特点：8/2,h=H(M),假定两次输入同样的数据，那么散列函数应该能够生成相同的散列值。输入数据中的一位发生了变化，会导致生成的散列值完全不一样。,散列函数有个非常重要的特性为单向性，也就是从M计算h容易，而从h计算M不可能。,8/8/2024,29,h=H(M)假定两次输入同样的数据，那么散列函数应该能够生,散列函数H必须满足以下几个性质,H对于任何大小的数据分组，都能产生定长的输出。,对于任何给定的M，H(M)要相对易于计算。,单向性：,对于任何给定的hash值h，计算出M在计算上不可行。,弱无碰撞性：,对任何给定的M1，寻找M2，使H(M1)=H(M2)在计算上不可行。,强无碰撞性：,寻找任何的（M1，M2），使H(M1)=H(M2)在计算上不可行。,8/8/2024,30,散列函数H必须满足以下几个性质 H对于任何大小的数据分组，都,8/8/2024,31,8/20/202331,8/8/2024,32,8/20/202332,8/8/2024,33,8/20/202333,8/8/2024,34,8/20/202334,Hash,与,MAC,的区别,MAC需要对全部数据进行加密,MAC速度慢,Hash是一种直接产生鉴别码的方法,Hash可用于数字签名,8/8/2024,35,Hash与MAC的区别8/20/202335,常用Hash算法,8/8/2024,36,网络工程08级,常用Hash算法 8/20/202336网络工程08级,迭代型hash函数的一般结构,目前使用的大多数杂凑函数如MD5、SHA，其结构都是迭代型的，如下图所示。其中函数的输入M被分为L个分组Y,0,Y,1,Y,L-1,，每一个分组的长度为b比特，最后一个分组的长度不够的话，需对其做填充。最后一个分组中还包括整个函数输入的长度值，这样一来，将使得敌手的攻击更为困难，即敌手若想成功地产生假冒的消息，就必须保证假冒消息的杂凑值与原消息的杂凑值相同，而且假冒消息的长度也要与原消息的长度相等。,8/8/2024,37,迭代型hash函数的一般结构目前使用的大多数杂凑函数如MD5,迭代型hash函数的一般结构,f,f,f,Y,0,Y,1,Y,L-1,b,b,b,n,n,n,n,n,IV=CV,0,CV,1,CV,L-1,CV,L,明文M被分为L个分组,Y,0,Y,1,Y,L-1,b:明文分组长度,n:输出hash长度,CV：各级输出，最后,一个输出值是hash值,无碰撞压缩函数f是设计的关键,8/8/2024,38,迭代型hash函数的一般结构fffY0Y1YL-1bbbnn,算法中重复使用一压缩函数f（注意，有些书将Hash函数也称为压缩函数，在此用压缩函数表示Hash函数中的一个特定部分），f 的输入有两项，一项是上一轮（第i-1轮）输出的n比特值CV,i-1,，称为链接变量，另一项是算法在本轮（第i轮）的b比特输入分组Y,i,。f 的输出为n比特值CV,i,，CV,i,又作为下一轮的输入。算法开始时还需对链接变量指定一个初值IV，最后一轮输出的链接变量CV,L,即为最终产生的Hash值。通常有bn，因此称函数f为压缩函数。算法可表达如下：,CV,0,=IV=n比特长的初值；,CV,i,=f(CV,i-1,Y,i-1,)；1iL；,H(M)=CV,L,8/8/2024,39,算法中重复使用一压缩函数f（注意，有些书将Hash函数也称为,迭代型hash函数,这种结构的hash函数已被证明是合理的，如果采用其他结构，不一定安全。,设计新的hash函数只是改进这种结构，或者增加hash码长。,算法的核心技术是设计无碰撞的压缩函数f，而敌手对算法的攻击重点是f 的内部结构，由于f 和分组密码一样是由若干轮处理过程组成，所以对f 的攻击需通过对各轮之间的位模式的分析来进行，分析过程常常需要先找出f 的碰撞。由于f 是压缩函数，其碰撞是不可避免的，因此在设计f 时就应保证找出其碰撞在计算上是不可行的。,8/8/2024,40,迭代型hash函数这种结构的hash函数已被证明是合理的，如,MD5 hash算法MD5 Hash Algorithm,MD4是MD5杂凑算法的前身，由Ron Rivest于1990年10月作为RFC提出，1992年4月公布的MD4的改进（RFC 1320，1321）称为MD5。,8/8/2024,41,网络工程08级,MD5 hash算法MD5 Hash Algorithm,MD5的算法框图,输入消息可任意长，压缩后输出为128bits。,8/8/2024,42,MD5的算法框图输入消息可任意长，压缩后输出为128bits,算法,步骤,(1),分组填充,消息,1000,64bit,消息长度,填充图样,L512bit,Kbit,如果消息长度大于2,64,，则取其对2,64,的模。,执行完后，消息的长度为512的倍数（设为L倍），则可将消息表示为分组长为512的一系列分组Y,0,，Y,1,，Y,L-1,，而每一分组又可表示为16个32比特长的字，这样消息中的总字数为N=L16，因此消息又可按字表示为M0,N-1。,8/8/2024,43,算法步骤(1)分组填充 消息100064bit消息长度填,算法,步骤,(2),缓冲区初始化,hash函数的中间结果和最终结果保存于128位的缓冲区中，缓冲区用32位的寄存器表示。可用4个32bits字表示：,A,B,C,D,。初始存数以十六进制表示为,A,=01234567,B,=89,ABCDEF,C,=,FEDCBA,98,D,=76543210,8/8/2024,44,算法步骤(2)缓冲区初始化 hash函数的中间结果和,算法步骤(3)-,H,MD5,运算,以分组为单位对消息进行处理,每一分组Y,q,(q=0,L-1)都经一压缩函数H,MD5,处理。H,MD5,是算法的核心，其中又有4轮处理过程。,H,MD5,的4轮处理过程结构一样，但所用的逻辑函数不同，分别表示为F、G、H、I。每轮的输入为当前处理的消息分组Y,q,和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、D。,每轮又要进行16步迭代运算，4轮共需64步完成。,第四轮的输出与第一轮的输入相加得到最后的输出。,8/8/2024,45,算法步骤(3)-HMD5运算以分组为单位对消息进行处理,每,8/8/2024,46,8/20/202346,压缩函数中的一步迭代,8/8/2024,47,压缩函数中的一步迭代8/20/202347,基本逻辑函数定义,轮,基本函数,g,g(b,c,d),f,F,F(,b,c,d),(,b,c),V,(,b,d),f,G,G(,b,c,d),(,b,d),V,(c,d),f,H,H(,b,c,d),b,c,d,f,I,I(,b,c,d),c,(,b,V,d),8/8/2024,48,基本逻辑函数定义轮基本函数gg(b,c,d)fFF(b,Xk,当前分组的第k个32位的字。,第1轮,x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,第2轮,x1,x6,x11,x0,x5,x10,x15,x4,x9,x14,x3,x8,x13,x2,x7,x12,第3轮,x5,x8,x11,x14,x1,x4,x7,x10,x13,x0,x3,x6,x9,x12,x15,x2,第4轮,x0,x7,x14,x5,x12,x3,x10,x1,x8,x15,x6,x13,x4,x11,x2,x9,8/8/2024,49,Xk当前分组的第k个32位的字。第1轮x0 x1x,Ti,T,1,64为64个元素表，分四组参与不同轮的计算。,T,i,为2,32,abs(Sin(,i,)的整数部分，,i,是弧度。T,i,可用32 bit二元数表示，,T,是32 bit随机数源。,8/8/2024,50,TiT1,64为64个元素表，分四组参与不同轮的,T1=d76aa478,T17=,f61e2562,T33=,fffa3942,T49=,f4292244,T2=e8c7b756,T18=,c040b340,T34=,8771f681,T50=,432aff97,T3=242070db,T19=,265e5a51,T35=,6d9d6122,T51=,ab9423a7,T4=c1bdceee,T20=,e9b6c7aa,T36=,fde5380c,T52=,fc93a039,T5=f57c0faf,T21=,d62f105d,T37=,a4beea44,T53=,655b59c3,T6=4787c62a,T22=,02441453,T38=,4bdecfa9,T54=,8f0ccc92,T7=a8304613,T23=,d8a1e681,T39=,f6bb4b60,T55=,ffeff47d,T8=fd469501,T24=,e7d3fbc8,T40=,bebfbc70,T56=,85845dd1,T9=698098d8,T25=,21e1cde6,T41=,289b7ec6,T57=,6fa87e4f,T10=8b44f7af,T26=,c33707d6,T42=,eaa127fa,T58=,fe2ce6e0,T11=ffff5bb1,T27=,f4d50d87,T43=,d4ef3085,T59=,a3014314,T12=895cd7be,T28=,455a14ed,T44=,04881d05,T60=,4e0811a1,T13=6b901122,T29=,a9e3e905,T45=,d9d4d039,T61=,f7537e82,T14=fd987193,T30=,fcefa3f8,T46=,e6db99e5,T62=,bd3af235,T15=a679438e,T31=,676f02d9,T47=,1fa27cf8,T63=,2ad7d2bb,T16=49b40821,T32=,8d2a4c8a,T48=,c4ac5665,T63=,eb86d391,8/8/2024,51,T1=d76aa478T17=f61e2562T,CLS,s,：循环左移s位,第一轮：7、12、17、22,第二轮：5、9、14、20,第三轮：4、11、16、23,第四轮：6、10、15、21,8/8/2024,52,CLSs：循环左移s位第一轮：7、12、17、228/20,MD-5的安全性,MD-5的输出为128-bit，若采用纯强力攻击寻找一个消息具有给定Hash值的计算困难性为2,128,，用每秒可试验1 000 000 000个消息的计算机需时1.0710,22,年。,采用生日攻击法，找出具有相同杂凑值的两个消息需执行2,64,次运算。,8/8/2024,53,MD-5的安全性MD-5的输出为128-bit，若采用纯强力,SHA 算法,Secure Hash Algorithm,8/8/2024,54,网络工程08级,SHA 算法Secure Hash Algorithm8/2,算法简介,美国标准与技术研究所NIST设计,1993年成为联邦信息处理标准(FIPS PUB 180),基于MD4算法，与之非常类似。,输入为小于2,64,比特长的任意消息,分组512bit长,输出160bit,8/8/2024,55,算法简介美国标准与技术研究所NIST设计8/20/20235,迭代型hash函数的一般结构,f,f,f,Y,0,Y,1,Y,L-1,b,b,b,n,n,n,n,n,IV=CV,0,CV,1,CV,L-1,CV,L,明文M被分为L个分组,Y,0,Y,1,Y,L-1,b:明文分组长度,n:输出hash长度,CV：各级输出，最后,一个输出值是hash值,无碰撞压缩函数f是设计的关键,8/8/2024,56,迭代型hash函数的一般结构fffY0Y1YL-1bbbnn,算法描述,消息填充：与MD5完全相同,附加消息长度：64bit长度,缓冲区初始化,A67452301,BEFCDAB89,C98BADCFB,D10325476,EC3D2E1F0,8/8/2024,57,算法描述消息填充：与MD5完全相同8/20/202357,分组处理,模2,32,加,8/8/2024,58,分组处理模232加8/20/202358,SHA-1压缩函数（单步）,8/8/2024,59,SHA-1压缩函数（单步）8/20/202359,f,t,-基本逻辑函数,8/8/2024,60,ft-基本逻辑函数8/20/202360,CLS,5,：32位的变量循环左移5位。,CLS,30,：32位的变量循环左移30位。,8/8/2024,61,CLS5：32位的变量循环左移5位。8/20/202361,W,t,-,从当前512位输入分组导出的32位字,前16个值（即W,0,W,1,W,15,）直接取为输入分组的16个相应的字，其余值（即W,16,W,17,W,79,）取为,8/8/2024,62,Wt-从当前512位输入分组导出的32位字前16个值（,K,t,-,加法常量,步骤,十六进制,0t19,K,t,=5A827999,20t39,K,t,=6ED9EBA1,40t59,K,t,=8F1BBCDC,60t79,K,t,=CA62C1D6,8/8/2024,63,Kt-加法常量步骤十六进制0t19Kt=5A827,SHA与MD5的比较,抗穷举搜索能力,寻找指定hash值，SHA：O(2,160,)，MD5：O(2,128,),生日攻击：SHA：O(2,80,)，MD5：O(2,64,),抗密码分析攻击的强度,SHA似乎高于MD5,速度,SHA较MD5慢,简捷与紧致性,描述都比较简单，都不需要大的程序和代换表,8/8/2024,64,SHA与MD5的比较抗穷举搜索能力8/20/202364,其它hash算法,MD4,MD4使用三轮运算，每轮16步；MD5使用四轮运算，每轮16步。,MD4的第一轮没有使用加法常量，第二轮运算中每步迭代使用的加法常量相同，第三轮运算中每步迭代使用的加法常量相同，但不同于第二轮使用的加法常量；MD5的64部使用的加法常量Ti均不同。,MD4使用三个基本逻辑函数，MD5使用四个。,MD5中每步迭代的结果都与前一步的结果相加，MD4则没有。,MD5比MD4更复杂，所以其执行速度也更慢，Rivest认为增加复杂性可以增加安全性。,8/8/2024,65,其它hash算法MD4 8/20/202365,RIPEMD-160,欧共体RIPE项目组研制。,输入可以是任意长的报文，输出160位摘要。,对输入按512位分组。以分组为单位处理。,算法的核心是具有十轮运算的模块，十轮运算分成两组，每组五轮，每轮16步迭代。,8/8/2024,66,RIPEMD-160欧共体RIPE项目组研制。8/20/20,对Hash函数的攻击,对一个hash算法的攻击可分三个级别：,预映射攻击（Preimage Attack）：给定Hash值h，找到其所对应的明文M，使得Hash(M)=h，这种攻击是最彻底的，如果一个hash算法被人找出预映射，那这种算法是不能使用的。,次预映射攻击（Second Preimage Attack）：给定明文M1，找到另一明文M2（M1M2），使得hash(M1)=hash(M2)，这种攻击其实就是要寻找一个弱碰撞；,碰撞攻击(Collision Attack)：找到M1和M2，使得hash(M1)=hash(M2)，这种攻击其实就是要寻找一个强碰撞。,8/8/2024,67,对Hash函数的攻击 对一个hash算法的攻击可分三个级别：,生日攻击,给定一个散列函数,H和某hash值H(x)，假定H,有,n,个可能的输出,。,如果,H,有,k,个随机输入,k,必须为多大才能使至少存在一个输入,y,使得,H(y)=H(x),的概率大于,0.5？,K=n/2,8/8/2024,68,生日攻击给定一个散列函数H和某hash值H(x)，假定H有n,结论,如果hash码为m位，则有2,m,个可能的hash码。,如果给定h=H(X)，要想找到一个y，使H(y)=h的概率为0.5，则要进行多次的尝试，尝试的次数k=2,m,/2=2,m-1,所以，对于一个使用64位的hash码，攻击者要想找到满足H(M)=H(M)的M来替代M，平均来讲，他要找到这样的消息大约要进行2,63,次尝试。,但是，存在一种攻击，称为“生日攻击”，却可以大大减小尝试的次数，对于64位的hash码，所需的代价仅为2,32,次。,8/8/2024,69,结论如果hash码为m位，则有2m个可能的hash码。8/2,生日悖论,一个教室中，最少应有多少学生，才使至少有两人具有相同生日的概率不小于,1/2,？,概率结果与人的直觉是相违背的,.,实际上只需,23,人,即任找,23,人，从中总能选出两人具有相同生日的概率至少为,1/2,。,8/8/2024,70,生日悖论一个教室中，最少应有多少学生，才使至少有两人具有相同,实施生日攻击,前面提到过，对于一个使用64位的hash码，攻击者要想找到满足H(M)=H(M)的M来替代M，平均来讲，他要找到这样的消息大约要进行2,63,次尝试。这太困难了！,8/8/2024,71,实施生日攻击前面提到过，对于一个使用64位的hash码，攻击,设M和hash算法生成64位的hash值。,攻击者可以根据M，产生2,32,个表达相同含义的变式(例如在词与词之间多加一个空格)。,同时准备好伪造的消息M，产生2,32,个表达相同含义的变式。,在这两个集合中，找出产生相同hash码的一对消息M,1,和M,1,。根据生日悖论，找到这样一对消息的概率大于0.5。,最后，攻击者将拿M,1,给发送者签名，但发送时，把M,1,和经加密的hash码一起发送。,8/8/2024,72,设M和hash算法生成64位的hash值。8/20/2023,Birthday Attacks:example,A,准备两份合同,M,和,M,，一份,B,会同意，一份会取走他的财产而被拒绝,A,对,M,和,M,各做,32,处微小变化,(,保持原意,),分别产生,2,32,个,64,位,hash,值,根据前面的结论,超过,0.5,的概率能找到一个,M,和一个,M,它们的,hash,值相同,A,提交,M,经,B,审阅后产生,64,位,hash,值并对该值签名,返回给,A,A,用,M,替换,M,8/8/2024,73,Birthday Attacks:exampleA准备两份,