网络安全-12：Hash函数

Chapter12Hash函数《密码编码学与网络安全》2020/3/8西安电子科技大学计算机学院3Hash函数用途举例用途一：公平提交方案Alice猜测了一个号码x1，但不知道中奖号码x2；Bob设置了中奖号码x2，但不知道Alice猜测的号码x1。Alice希望首先获得x2，然后重新确定x1使得x1=x2。Bob希望首先获得x1，然后重新确定x2使得x2≠x1。防止两人作弊的方案称为“公平提交方案”。两人使用一个公开的杂凑函数y=H(x)。方案如下：2020/3/8西安电子科技大学计算机学院4Hash函数用途举例（1）Alice计算y1=H(x1)，并将y1发送给Bob。（2）Bob计算y2=H(x2)，并将y2发送给Alice。（3）Alice收到y2后，将x1发送给Bob。（4）Bob收到y1后，将x2发送给Alice。（5）Alice收到x2后，检验是否y2=H(x2)，若是则x2是真实的中奖号码。（6）Bob收到x1后，检验是否y1=H(x1)，若是则x1是Alice的真实的猜测号码。2020/3/8西安电子科技大学计算机学院5Alice(5):验证是否y2=H(x2)Bob(6):验证是否y1=H(x1)(1):y1=H(x1)(2):y2=H(x2)(4):x2(3):x1Hash函数用途举例2020/3/8西安电子科技大学计算机学院6方案分析Alice发送y1给Bob，Bob发送y2给Alice，这叫做承诺。Alice发送x1给Bob，Bob发送x2给Alice，这叫做践诺。当承诺值确定以后，无法改变践诺值。当对方发送来了承诺值以后，己方无法计算出对方的践诺值，因而无法“随机应变地”确定自己的践诺值，以重合或避开对方的践诺值。综上所述，杂凑函数阻止了双方作弊。Hash函数用途举例2020/3/8西安电子科技大学计算机学院7Hash算法结构P248YL-1CVL-1压缩算法…2020/3/8西安电子科技大学计算机学院8哈希函数的应用三个重要的hash函数MD5SHA-1RIPEMD-160HMACCMAC2020/3/8西安电子科技大学计算机学院9§12.1MD5消息摘要算法由RonaldRivest设计MD2(1989),MD4(1990),MD5(1991)产生128-bit的hash值直到现在仍是被广泛使用的hash算法最近已受到穷举攻击和密码分析攻击作为互联网的RFC1321标准2020/3/8西安电子科技大学计算机学院10MD5Overview2020/3/8西安电子科技大学计算机学院11MD5概览1.增加填充位。使得填充后的消息长度比512的某整数倍少64位（即长度＝448mod512，64位用于存放消息的长度mod264的结果）2.填充长度（填充前消息的长度为K位，将mod264的结果填充到第一步的最后，最低有效位在前。）3.初始化MD缓冲区(A,B,C,D):4个字共128-bit，每字32bit.A=67452301B=EFCDAB89C=98BADCFED=103254764.以16个字（512bits）为分组处理消息用4轮（64次迭代）以16位操作对消息分组和缓冲区进行处理把输出与缓冲输入相加作为新的缓冲值5.把最后的缓冲值作为hash输出值（128比特）2020/3/8西安电子科技大学计算机学院12MD5处理过程CV0=IVCVq+1=SUM32[CVq,RFI(Yq,RFH(Yq,RFG(Yq,RFF(Yq,CVq))))]MD=CVL-1其中：IV=第三步定义的缓冲区ABCD的初值Yq=消息的第q个512位分组L=消息分组的个数（包括填充位和长度域）CVq=处理消息的第q个分组时所使用的链接变量RFx=使用基本逻辑函数x的轮函数MD=消息摘要SUM32=对输入字分别执行模232加法2020/3/8西安电子科技大学计算机学院132020/3/8西安电子科技大学计算机学院14MD5压缩函数每一个轮循环左移2020/3/8西安电子科技大学计算机学院15MD5压缩函数每一轮都由16步迭代构成:a=b+((a+g(b,c,d)+X[k]+T[i])s)a,b,c,d表示缓冲区的4个32位字,按照一定次序随迭代步骤而变化每次迭代只更新缓冲区中的一个字a16次迭代后，每个字被更新4次其中g(b,c,d)表示每一轮的非线性函数，四轮依次为(F,G,H,I)s：32位的变量循环左移s位X[k]=M[q×16+k]=消息第q个512位分组的第k个32位字T[i]是由sin导出的32bit的常量+：模232加法2020/3/8西安电子科技大学计算机学院162020/3/8西安电子科技大学计算机学院172020/3/8西安电子科技大学计算机学院182020/3/8西安电子科技大学计算机学院192020/3/8西安电子科技大学计算机学院202020/3/8西安电子科技大学计算机学院212020/3/8西安电子科技大学计算机学院22MD4在MD5之前提出输出128-bithash值16次迭代进行3轮，而MD5是4轮。MD5中使用了4个基本逻辑函数，每轮用一个，而MD4中仅有3个。其它细节上的差别2020/3/8西安电子科技大学计算机学院23MD5的强度MD5的hash值依赖于消息的所有比特位Rivest声称它对于已知攻击安全性足够好:Berson92采用差分的方法对单轮的攻击Boer&Bosselaers93说明了如何找到碰撞Dobbertin96提出的攻击对MD5最具威胁，可使MD5压缩函数产生碰撞。结论是MD5似乎不久就会有风险2020/3/8西安电子科技大学计算机学院242020/3/8西安电子科技大学计算机学院25§12.2安全Hash算法(SHA-1)SHA由NIST和NSA在1993年提出,修订版于1995年发布，称作SHA-1作为美国DSA数字签名方案的标准FIPS180-11995,InternetRFC3174注意：算法是SHA,标准称为SHS产生160-bithash值现在作为建议的hash算法基于MD4的设计2020/3/8西安电子科技大学计算机学院26SHA概览1.增加填充位2.填充长度3.初始化5个字(160-bit)缓冲区(A,B,C,D,E)为(67452301,efcdab89,98badcfe,10325476,c3d2e1f0)4.以16个字（512-bit）为分组处理消息:将分组的16个字扩充为80个字用于压缩过程中4轮，每轮20步迭代把输出和输入相加以形成新的缓冲区取值5.将最后缓冲区的值作为hash值输出2020/3/8西安电子科技大学计算机学院272020/3/8西安电子科技大学计算机学院28SHA-1压缩函数每轮20步迭代:(A,B,C,D,E)-(E+f(t,B,C,D)+(A5)+Wt+Kt),A,(B30),C,D)a,b,c,d,e指缓冲区的5个字t是迭代步数，0≤t≤79f(t,B,C,D)为第t步所用的非线性函数Wt从当前消息分组中导出的32位的字Kt加法常量2020/3/8西安电子科技大学计算机学院29SHA-1压缩函数循环左移5位循环左移30位加法常量2020/3/8西安电子科技大学计算机学院302020/3/8西安电子科技大学计算机学院312020/3/8西安电子科技大学计算机学院32SHA-1versesMD5穷举攻击更加困难（SHA-1:160,MD5:128）对已知攻击不存在风险(与MD4/5相比)（SHA-1的设计原则尚未公开）速度比MD5慢(80步，64步)两者设计都很简单紧凑低位结构和高位结构MD5:低位结构SHA-1:高位结构2020/3/8西安电子科技大学计算机学院33SHA的修改NIST1981年已经发布了FIPS180-2除SHA-1外，新增加了3个hash算法：SHA-256,SHA-384,SHA-512，消息摘要的长度分别为：256，384，512与AES增强安全性相适应结构和细节与SHA-1相似与SHA-1具有相同的抗密码分析攻击的能力2020/3/8西安电子科技大学计算机学院342020/3/8西安电子科技大学计算机学院35推荐的SHA标准2020/3/8西安电子科技大学计算机学院36§12.3RIPEMD-160RIPEMD-160消息摘要算法是欧洲RIPE下一组研究人员设计的这些人员曾对MD4/5进行了一些成功的攻击从最初的128位增强为160，即RIPEMD-160RIPEMD(MD4的增强)；RIPEMD-160(RIPEMD的增强)；RIPEMD-128(RIPEMD的代替)有点象MD5/SHA采用两个并行的，5轮的处理过程，每轮16步输出160-bithash值速度慢,但有可能比SHA安全2020/3/8西安电子科技大学计算机学院38RIPEMD-160Round2020/3/8西安电子科技大学计算机学院39RIPEMD-160压缩函数2020/3/8西安电子科技大学计算机学院452020/3/8西安电子科技大学计算机学院47§12.4HMAC密码hash函数作为MAC：不用分组密码，而用hash函数来产生MAC因为hash函数一般都较快hash函数不依赖于秘密钥，所以不能直接用于MAC建议:KeyedHash=Hash(Key|Message)这种方法存在一些缺点人们一直试图开发各种HMAC,其中HMAC就是一个现用方案2020/3/8西安电子科技大学计算机学院48HMAC作为RFC2104HMACK=Hash[(K+XORopad)||Hash[(K+XORipad)||M)]]其中K+为在K左边填充0后所得的b位长的结果（b为每一消息分组的位数）opad,ipad都是指定的填充常量多执行了3次hash压缩函数算法可用于MD5,SHA-1,RIPEMD-160中的任何一个2020/3/8西安电子科技大学计算机学院49HMAC的结构⊕⊕2020/3/8西安电子科技大学计算机学院50⊕⊕HAMC的有效实施方案2020/3/8西安电子科技大学计算机学院51HMAC的安全性HMAC的安全性依赖于hash算法的安全性攻击HMAC需要下列之一:对密钥进行穷举攻击生日攻击从速度与安全制约，选择恰当的hash函数2020/3/8西安电子科技大学计算机学院522020/3/8西安电子科技大学计算机学院532020/3/8西安电子科技大学计算机学院54一些单向hash函数的比较2020/3/8西安电子科技大学计算机学院55CMAC简介见课本270页2020/3/8西安电子科技大学计算机学院56小结三个重要的hash函数MD5SHA-1RIPEMD-160HMACCMAC2020/3/8西安电子科技大学计算机学院57第12章作业思考题：12.4或12.5