第3章-单向散列函数ppt课件.ppt

《第3章-单向散列函数ppt课件.ppt》由会员分享，可在线阅读，更多相关《第3章-单向散列函数ppt课件.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3 3章章 单向散列函数单向散列函数1Network and Information Security第第3章章单向散列函数单向散列函数3.1 3.1 单向散列函数概述单向散列函数概述3.2 MD53.2 MD5算法算法3.3 SHA-13.3 SHA-1算法算法3.4 3.4 消息认证码消息认证码(MAC)(MAC)3.5 3.5 对单向散列函数的攻击对单向散列函数的攻击第第3 3章章 单向散列函数单向散列函数2Network and Information Security随着以随着以InternetInternet为基础的电子商务技术的迅猛发展为基础的电子商务技术的迅猛发展,以以公钥

2、密码、公钥密码、数字签名数字签名等为代表的加密安全技术已成为等为代表的加密安全技术已成为研究的热点。研究的热点。单向散列函数是数字签名单向散列函数是数字签名中的一个关键环节中的一个关键环节,可以大大可以大大缩短签名时间缩短签名时间并提高安全性并提高安全性,另外在另外在消息完整性检测消息完整性检测,内存的散布分配内存的散布分配,软件系统中软件系统中帐号口令帐号口令的安全存储单向的安全存储单向散列函数也有重要应用。散列函数也有重要应用。第第3 3章章 单向散列函数单向散列函数3Network and Information Security3.1 3.1 单向散列函数概述单向散列函数概述所所谓谓的

3、的单单向向散散列列函函数数(Hash(Hash FunctionFunction，又又称称哈哈希希函函数数、杂杂凑凑函函数数)，是是将将任任意意长长度度的的消消息息M M映映射射成成一一个个固固定定长长度度散散列列值值h h(设长度为设长度为m)m)的函数的函数H H：h=H(M)h=H(M)散列函数要具有单向性，则必须满足如下特性：散列函数要具有单向性，则必须满足如下特性：给定给定M M，很容易计算，很容易计算h h。给定给定h h，根据，根据H(M)=hH(M)=h反推反推M M很难。很难。给定给定M M，要找到另一消息，要找到另一消息MM并满足并满足H(M)=H(M)H(M)=H(M)很

4、难。很难。在某些应用中，单向散列函数还需要满足抗碰撞在某些应用中，单向散列函数还需要满足抗碰撞(Collision)(Collision)的条件：要找到的条件：要找到两个随机的消息两个随机的消息M M和和MM，使，使H(M)=H(M)H(M)=H(M)很难。很难。第第3 3章章 单向散列函数单向散列函数4Network and Information Security HashHash函数的良好性质函数的良好性质（1）广泛的应用性Hash函数能用于任何大小的消息。（2）定长输出将消息集合中的任意长度的消息映射为长度为的消息摘要。（3）实现性对Hash函数的一个非常重要的要求是简单易实现性。（4

5、）单向性质要求Hash函数是单向函数。给定h值，求信息M（是一对多的关系），只有通过枚举，在现有的计算环境下是不可行的。第第3 3章章 单向散列函数单向散列函数5Network and Information Security（5 5）抗弱对抗性抗弱对抗性 确确定定与与x x有有相相同同位位数数的的y y,使使H(x)=H(y),H(x)=H(y),在在现现有有的的计计算算环环境境下下是是不不可可行的行的。（6 6）抗强对抗性抗强对抗性 找找到到两两个个不不同同位位数数信信息息x,yx,y,使使H(x)=H(y)H(x)=H(y)，在在现现有有的的计计算算环环境境下下是是不不可行的。可行的。注

6、：以上两种，哪一种更容易找？注：以上两种，哪一种更容易找？（7 7）独立性独立性哈希函数值哈希函数值“不依赖输入信息不依赖输入信息”，从，从某种程度上说是某种程度上说是由算法决定的。由算法决定的。（8 8）抗近冲突）抗近冲突HashHash函函数数满满足足独独立立性性，输输入入信信息息某某一一位位的的变变化化，应应该该引引起起平平均均一一半半的输出位的变化。的输出位的变化。（9 9）安全性安全性在很广泛的条件下在很广泛的条件下,Hash,Hash值值()的分布是均匀分布的的分布是均匀分布的.第第3 3章章 单向散列函数单向散列函数6Network and Information Securit

7、y散列函数工作模式散列函数工作模式图3-1 单向散列函数工作模式第第3 3章章 单向散列函数单向散列函数7Network and Information Security 3.2.1 算法算法MD表表示示消消息息摘摘要要(MessageDigest)。MD5是是MD4的的改改进进版版，该该算算法法对对输输入入的的任任意意长长度度消消息息产产生生128位位散散列列值值(或或消消息息摘摘要要)。MD5算法可用图算法可用图3-2表示。表示。3.2MD5算算法法第第3 3章章 单向散列函数单向散列函数8Network and Information Security图3-2MD5算法 1)附加填充位附

8、加填充位 2)附加长度附加长度64 3)初始化初始化MD缓冲区缓冲区 5)输出输出 4)按按512位的分组处位的分组处理输入消息理输入消息第第3 3章章 单向散列函数单向散列函数9Network and Information Security由上图可知，由上图可知，MD5算法包括以下五个步骤。算法包括以下五个步骤。1)附加填充位附加填充位首首先先填填充充消消息息，使使其其长长度度为为一一个个比比512的的倍倍数数小小64位位的的数数。填填充充方方法法：在在消消息息后后面面填填充充一一位位1，然然后后填填充充所所需需数数量的量的0。填充位的位数从。填充位的位数从1512。填充消息长度填充消息长

9、度=512-(k+64)mod5122)附加长度附加长度将将原原消消息息长长度度的的64位位表表示示附附加加在在填填充充后后的的消消息息后后面面。当当原原消消息息长长度度大大于于264时时，用用消消息息长长度度mod264填填充充。这这时时，总总长长度度恰恰好好是是512的的整整数数倍倍。令令M01N1为为填填充充后后消消息的各个字息的各个字(每字为每字为32位位)，N是是16的倍数。的倍数。第第3 3章章 单向散列函数单向散列函数10Network and Information Security3)初始化初始化MD缓冲区缓冲区初初始始化化用用于于计计算算消消息息摘摘要要的的128位位缓缓冲

10、冲区区。这这个个缓缓冲冲区区由由四四个个32位位寄寄存存器器A A、B B、C C、D D表表示示。寄寄存存器器的的初初始始化值为化值为(按低位字节在前的顺序存放按低位字节在前的顺序存放)：A:01234567B:89abcdefC:fedcba98D:765432104)按按512位的分组处理输入消息位的分组处理输入消息这一步为这一步为MD5的主循环，包括四轮，如图的主循环，包括四轮，如图3-3所示。所示。每个循环都以当前的正在处理的每个循环都以当前的正在处理的512比特分组比特分组Yq和和128比特缓冲值比特缓冲值ABCDABCD为输入，然后更新缓冲内容。为输入，然后更新缓冲内容。第第3

11、3章章 单向散列函数单向散列函数11Network and Information Security图3-3单个512比特分组的MD5主循环处理第第3 3章章 单向散列函数单向散列函数12Network and Information Security图3-3中，四轮的操作类似，每一轮进行16次操作。各轮的操作过程如图3-4所示。图3-4MD5某一轮的1次执行过程j:015,i:164(共四轮，每一轮用的都不同)第第3 3章章 单向散列函数单向散列函数13Network and Information Security四四轮轮操操作作的的不不同同之之处处在在于于每每轮轮使使用用的的非非线线性性

12、函函数数不不同同，在在第第一一轮轮操操作作之之前前，首首先先把把A A、B B、C C、D D复复制制到到另另外外的的变变量量a a、b b、c c、d d中中。这这四四个个非非线线性性函函数数分分别别为为(其其输入输入/输出均为输出均为32位字位字)：F(X,Y,Z)=(XY)(X)Z)G(X,Y,Z)=(XZ)(Y(Z)H(X,Y,Z)=X Y ZI(X,Y,Z)=Y(X(Z)其其中中，表表示示按按位位与与；表表示示按按位位或或；表表示示按按位位反；反；表示按位异或。表示按位异或。第第3 3章章 单向散列函数单向散列函数14Network and Information Security此

13、外，由图3-4可知，这一步中还用到了一个有64个元素的表T1.64，Ti=232abs(sin(i)，i的单位为弧度。根据以上描述，将这一步骤的处理过程归纳如下：fori=0toN/161do/*每次循环处理16个字，即512字节的消息分组*/*把A存为AA，B存为BB，C存为CC，D存为DD*/AA=ABB=BCC=CDD=D第第3 3章章 单向散列函数单向散列函数15Network and Information Security/*第一轮第一轮*/*令令abcdksi表示操作表示操作b=b+(a+F(b,c,d)+Mk+Ti)s)其中，其中，Ys表示表示Y循环左移循环左移s位位*/*完成

14、下列完成下列16个操作个操作*/ABCD071DABC1122CDAB2173BCDA3224ABCD475DABC5126CDAB6177BCDA7228ABCD879DABC91210CDAB101711BCDA112212ABCD12713DABC131214CDAB141715BCDA152216第第3 3章章 单向散列函数单向散列函数16Network and Information Security/*第二轮第二轮*/*令令abcdksi表示操作表示操作b=b+(a+G(b,c,d)+Mk+Ti)s)*/*完成下列完成下列16个操作个操作*/ABCD1517DABC6918CDAB

15、111419BCDA02020ABCD5521DABC10922CDAB151423BCDA42024ABCD9525DABC14926CDAB31427BCDA82028ABCD13529DABC2930CDAB71431BCDA122032第第3 3章章 单向散列函数单向散列函数17Network and Information Security/*第三轮第三轮*/*令令abcdkst表示操作表示操作b=b+(a+H(b,c,d)+Mk+Ti)s)*/*完成以下完成以下16个操作个操作*/ABCD5433DABC81134CDAB111635BCDA142336ABCD1437DABC41

16、138CDAB71639BCDA102340ABCD13441DABC01142CDAB31643BCDA62344ABCD9445DABC121146CDAB151647BCDA22348第第3 3章章 单向散列函数单向散列函数18Network and Information Security/*第四轮第四轮*/*令令abcdkst表示操作表示操作b=b+(a+I(b,c,d)+Mk+Ti)s)*/*完成以下完成以下16个操作个操作*/ABCD0649DABC71050CDAB141551BCDA52152ABCD12653DABC31054CDAB101555BCDA12156ABCD8

17、657DABC151058CDAB61559BCDA132160ABCD4661DABC111062CDAB21563BCDA92164A=A+AAB=B+BBC=C+CCD=D+DDend/*i循环*/第第3 3章章 单向散列函数单向散列函数19Network and Information Security5)输出输出由由A、B、C、D四四个个寄寄存存器器的的输输出出按按低低位位字字节节在在前前的的顺顺序序(即即以以A的的低低字字节节开开始始、D的的高高字字节结束节结束)得到得到128位的消息摘要。位的消息摘要。以以上上就就是是对对MD5算算法法的的描描述述。MD5算算法法的的运算均为基本

18、运算，比较容易实现且速度很快。运算均为基本运算，比较容易实现且速度很快。第第3 3章章 单向散列函数单向散列函数20Network and Information Security3.2.2举例举例我们以求字符串“abc”的MD5散列值为例来说明上面描述的过程。“abc”的二进制表示为011000010110001001100011。1填充消息消息长24，先填充1位1，然后填充423位0，再用消息长24，即0 x0000000000000018填充，则：M0=61626380M1=00000000M2=00000000M3=00000000M4=00000000M5=00000000M6=00

19、000000M7=00000000M8=00000000M9=00000000M10=00000000M11=00000000M12=00000000M13=00000000M14=00000000M15=000000182初始化A:01234567B:89abcdefC:fe dcba98D:765432103主循环利用3.2.1节中描述的过程对字块1（本例只有一个字块）进行处理。变量a、b、c、d每一次计算后的中间值不再详细列出。4输出消息摘要=900150983cd24fb0d6963f7d28e17f72第第3 3章章 单向散列函数单向散列函数21Network and Informa

20、tion Security3.3安全散列函数安全散列函数(SHA-1)3.3.1 算法算法SHA是是美美国国NIST和和NSA共共同同设设计计的的安安全全散散列列算算法法(Secure Hash Algorithm)，用用 于于 数数 字字 签签 名名 标标 准准DSS(DigitalSignatureStandard)。SHA的的修修改改版版SHA1于于1995年年作作为为美美国国联联邦邦信信息息处处理理标标准准公公告告(FIPSPUB1801)发布。发布。SHA1产生消息摘要的过程类似产生消息摘要的过程类似MD5，如图，如图3-5所示。所示。第第3 3章章 单向散列函数单向散列函数22Ne

21、twork and Information Security图3-5SHA1算法第第3 3章章 单向散列函数单向散列函数23Network and Information SecuritySHASHA1 1的的输输入入为为长长度度小小于于264位位的的消消息息（若若大大于于，用用mod mod 即即可可），输输出出为为160位位的的消消息息摘摘要要。具具体体过过程如下。程如下。1)填充消息填充消息首首先先将将消消息息填填充充为为512位位的的整整数数倍倍，填填充充方方法法和和MD5完完全全相相同同：先先填填充充一一个个1，然然后后填填充充一一定定数数量量的的0，使使其其长长度度比比512的的倍

22、倍数数少少64位位；接接下下来来用用原原消消息息长长度度的的64位位表表示示填填充充。这这样样，消消息息长长度度就就成成为为512的的整整数数倍倍。以以M0、M1、Mn-1表表示示填填充充后后消消息的各个字块息的各个字块(每字块为每字块为16个个32位字位字)。第第3 3章章 单向散列函数单向散列函数24Network and Information Security2)初始化缓冲区初始化缓冲区在运算过程中，在运算过程中，SHA要用到两个缓冲区，要用到两个缓冲区，两个缓两个缓冲区均有五个冲区均有五个32位的寄存器位的寄存器。第一个缓冲区标记为第一个缓冲区标记为A A、B B、C C、D D、E

23、 E；第二个缓冲区标记为；第二个缓冲区标记为H0、H1、H2、H3、H4。此外，运算过程中还用到一个标记为。此外，运算过程中还用到一个标记为W0、W1、W79的的80个个32位字序列和一个单字的缓冲区位字序列和一个单字的缓冲区TEMP。在。在运算之前，初始化运算之前，初始化Hj：H0=0 x67452301 H1=0 xEFCDAB89 H2=0 x98BADCFE H3=0 x10325476 H4=0 xC3D2E1F0第第3 3章章 单向散列函数单向散列函数25Network and Information Security3)按按512位的分组处理输入消息位的分组处理输入消息SHA运运

24、算算主主循循环环包包括括四四轮轮，每每轮轮20次次操操作作。SHA用用到到一一个个逻逻辑辑函函数数序序列列f0、f1、f79。每每个个逻逻辑辑函函数数的的输输入入为为三三个个32位位字字，输输出出为为一一个个32位位字字。定义如下(B、C、D均为32位字)：ft(B,C,D)=(BC)(BD)(0t19)ft(B,C,D)=BCD(20t39)ft(B,C,D)=(BC)(BD)(CD)(40t59)ft(B,C,D)=BCD(60t79)其中，运算符的定义与其中，运算符的定义与3.1节中节中MD5运算中的相同。运算中的相同。第第3 3章章 单向散列函数单向散列函数26Network and

25、Information SecuritySHA运运算算中中还还用用到到了了常常数数字字序序列列K0、K1、K79，其值为，其值为 Kt=0 x5A827999(0t19)Kt=0 x6ED9EBA1(20t39)Kt=0 x8F1BBCDC(40t59)Kt=0 xCA62C1D6(60t79)第第3 3章章 单向散列函数单向散列函数27Network and Information SecuritySHA算法按如下步骤处理每个字块算法按如下步骤处理每个字块Mi：(1)把把Mi分为分为16个字个字W0、W1、W15，其中，其中，W0为最左边的字。为最左边的字。(2)fort=16to79dol

26、etWt=(Wt3Wt8Wt14Wt16)1(3)LetA=H0，B=H1，C=H2，D=H3，E=H4(4)fort=0to79doTEMP=(A5)+ft(B,C,D)+E+Wt+Kt;E=D;D=C;C=(B30);B=A;A=TEMP;(5)LetH0=H0+A,H1=H1+B,H2=H2+C,H3=H3+D,H4=H4+E4)输输出出-在在处处理理完完Mn后后，160位位的的消消息息摘摘要要为为H0、H1、H2、H3、H4级联的结果。级联的结果。第第3 3章章 单向散列函数单向散列函数28Network and Information Security 3.3.2 举例我们以求字符串

27、我们以求字符串abc的的SHA1散列值为例来散列值为例来说明上面描述的过程。说明上面描述的过程。abc的二进制表示为的二进制表示为abc011000010110001001100011。(2)初始化：初始化：H0=0 x67452301 H1=0 xEFCDAB89H2=0 x98BADCFE H3=0 x10325476H4=0 xC3D2E1F0(1)填充消息：消息长填充消息：消息长l=24，先填充，先填充1位位1，然后填充，然后填充423位位0，再用消息长，再用消息长24，即，即0 x0000000000000018（64位）位）填充。填充。第第3 3章章 单向散列函数单向散列函数29N

28、etwork and Information Security(3)主主循循环环：处处理理消消息息字字块块1(本本例例中中只只有有1个个字字块块)，分分成成16个字：个字：（01100001011000100110001124）W0=61626380W1=00000000W2=00000000W3=00000000W4=00000000W5=00000000W6=00000000W7=00000000W8=00000000W9=00000000W10=00000000W11=00000000W12=00000000W13=00000000W14=00000000W15=00000018然然后后

29、根根据据3.2.1节节中中描描述述的的过过程程计计算算，其其中中，循循环环“fort=0to79”中，各步中，各步A、B、C、D、E的值如下：的值如下：第第3 3章章 单向散列函数单向散列函数30Network and Information Security A B C D Et=0:0116FC3367452301 7BF36AE2 98BADCFE 10325476t=1:8990536D0116FC33 59D148C0 7BF36AE2 98BADCFEt=2:A1390F088990536D C045BF0C 59D148C0 7BF36AE2t=3:CDD8E11BA1390F0

30、8 626414DB C045BF0C 59D148C0t=4:CFD499DECDD8E11B 284E43C2 626414DB C045BF0Ct=5:3FC7CA40 CFD499DE F3763846 284E43C2 626414DBt=6:993E30C1 3FC7CA40 B3F52677 F3763846 284E43C2t=7:9E8C07D4 993E30C1 0FF1F290 B3F52677 F3763846t=8:4B6AE328 9E8C07D4 664F8C30 0FF1F290 B3F52677t=9:8351F929 4B6AE328 27A301F5 66

31、4F8C30 0FF1F290t=10:FBDA9E89 8351F929 12DAB8CA 27A301F5 664F8C30第第3 3章章 单向散列函数单向散列函数31Network and Information Security字块1处理完后，Hi的值为：H0=67452301+42541B35=A9993E36H1=EFCDAB89+5738D5E1=4706816AH2=98BADCFE+21834873=BA3E2571H3=10325476+681E6DF6=7850C26CH4=C3D2E1F0+D8FDF6AD=9CD0D89D(4)输出：消息摘要=A9993E364706

32、816ABA3E25717850C26C9CD0D89D也就是说abc的散列函数值为：第第3 3章章 单向散列函数单向散列函数32Network and Information Security3.3.3 SHA1与MD5的比较SHA1与MD5的比较如表3-1所示。表3-1SHA-1与MD5的比较SHA-1MD5Hash值长度160bit128bit分组处理长512bit512bit步数80(420)64(416)最大消息长264bit不限非线性函数3(第第2、4轮轮相同相同)4常数个数464ft(B,C,D)=(BC)(BD)(0t19)ft(B,C,D)=B C D(20t39)ft(B,

33、C,D)=(BC)(BD)(CD)(40t59)ft(B,C,D)=B C D(60t79)F(X,Y,Z)=(XY)(X)Z)G(X,Y,Z)=(XZ)(Y(Z)H(X,Y,Z)=X Y ZI(X,Y,Z)=Y(X(Z)第第3 3章章 单向散列函数单向散列函数33Network and Information Security根据各项特征，简要地说明它们间的不同。根据各项特征，简要地说明它们间的不同。（1）安全性：SHA-1所产生的摘要较MD5长32位。若两种散列函数在结构上没有任何问题的话，SHA-1比MD5更安全。（2）速度：两种方法都考虑了以32位处理器为基础的系统结构，但SHA-1的

34、运算步骤较MD5多了16步，而且SHA-1记录单元的长度较MD5多了32位。因此若是以硬件来实现SHA-1，其速度大约较MD5慢25%。（3）简易性：两种方法都相当的简单，在实现上不需要很复杂的程序或是大量的存储空间。然而总体上来讲，SHA-1每一步的操作都较MD5简单。第第3 3章章 单向散列函数单向散列函数34Network and Information Security3.4 消息认证码消息认证码(MAC)与与密密钥钥相相关关的的单单向向散散列列函函数数通通常常称称为为MAC，即即消消息息认证码：认证码：MAC=CK(M)其其中中，M为为可可变变长长的的消消息息；K为为通通信信双双方方

35、共共享享的的密密钥钥；C为单向函数。为单向函数。MAC可可为为拥拥有有共共享享密密钥钥的的双双方方在在通通信信中中验验证证消消息息的的完完整整性性；也也可可被被单单个个用用户户用用来来验验证证他他的的文文件件是是否否被被改改动动，如图如图3-6所示。所示。第第3 3章章 单向散列函数单向散列函数35Network and Information Security图3-6MAC应用于消息认证若没有若没有K，能否验证消息的完整性？能否验证消息的完整性？不能不能如攻击者将消息如攻击者将消息M和摘要都替换了，将不能验证原消息的完整性和摘要都替换了，将不能验证原消息的完整性第第3 3章章 单向散列函数单

36、向散列函数36Network and Information SecurityRFC 2104定义的HMAC算法HMAC全称为Keyed-Hash MessageAuthenticationCode，它用一个秘密密钥来产生和验证MACHMAC中用到的参数和符号：B：计算消息摘要时输入块的字节长度(如对于SHA-1,B=64)。H：散列函数，如SHA-1，MD5等。ipad：将数值0 x36重复B次。opad：将数值0 x5c重复B次。K：共享密钥。K0：在密钥K的左边附加0使其长为B字节的密钥。L：消息摘要的字节长度(如对于SHA-1，L=20)。t：MAC的字节数。第第3 3章章 单向散列函

37、数单向散列函数37Network and Information Securitytext：要要计计算算HMAC的的数数据据。数数据据长长度度为为n字字节节，n的最大值依赖于采用的的最大值依赖于采用的hash函数。函数。X|Y：将将字字串串连连接接起起来来，即即把把字字串串Y附附加加在在字字串串X后面。后面。：异或。：异或。密密钥钥K的的长长度度应应大大于于或或等等于于L/2。当当使使用用长长度度大大于于B的的密密钥钥时时，先先用用H对对密密钥钥求求得得散散列列值值，然然后后用用得得到到的的L字节结果作为真正的密钥。字节结果作为真正的密钥。利利用用HMAC函函数数计计算算数数据据text的的M

38、AC过过程程如如图图3-7所示。所示。第第3 3章章 单向散列函数单向散列函数38Network and Information Security图3-7HMAC结构第第3 3章章 单向散列函数单向散列函数39Network and Information Security由图可知，由图可知，HMAC执行的是如下操作：执行的是如下操作：MAC(text)t=HMAC(K,text)t=H(K0opad)|H(K0ipad)|text)t具体操作步骤如下：具体操作步骤如下：(1)如如果果K的的长长度度等等于于B，设设置置K0=K并并跳跳转转到到第第(4)步。步。(2)如果如果K的长度的长度大于大

39、于B，对，对K求散列值：求散列值：K0=H(K)。(3)如如果果K的的长长度度小小于于B，在在K的的左左边边附附加加0得得到到B字字节的节的K0。(4)执行执行K0ipad。第第3 3章章 单向散列函数单向散列函数40Network and Information Security(5)将数据将数据text附加在第附加在第(4)步结果的后面：步结果的后面：(K0ipad)|text(6)将将H应用于第应用于第(5)步的结果：步的结果：H(K0ipad)|text)(7)执行执行K0opad。(8)把把第第(6)步步的的结结果果附附加加在在第第(7)步步的的结结果果后面：后面：(K0opad)|

40、H(K0ipad)|text)第第3 3章章 单向散列函数单向散列函数41Network and Information Security(9)将将H应用于第应用于第(8)步的结果：步的结果：H(K0opad)|H(K0ipad)|text)(10)选选择择第第(9)步步结结果果的的最最左左边边t字字节节作作为为MAC。HMAC算算法法可可以以和和任任何何密密码码散散列列函函数数结结合合使使用用，而而且且对对HMAC实实现现作作很很小小的的修修改改就就可可用用一一个个散散列列函函数数H代代替替原原来来的的散散列函数列函数H。第第3 3章章 单向散列函数单向散列函数42Network and I

41、nformation Security3.5 对单向散列函数的攻击对对单单向向散散列列函函数数攻攻击击的的目目的的在在于于破破坏坏单单向散列函数的某些特性向散列函数的某些特性.比比如如可可以以根根据据输输出出求求得得输输入入，找找到到一一条条新新消消息息使使它它的的输输出出与与原原消消息息的的输输出出相相同同，或或者者找找到到不不同同的的两两个个消消息息，使使它它们们的的输输出相同。出相同。第第3 3章章 单向散列函数单向散列函数43Network and Information Security3.5.1 3.5.1 字典攻击字典攻击字典攻击，对用单向散列函数加密的口令文件特别有效。攻击者编

42、制含有多达几十万个常用口令的表，然后用单向散列函数对所有口令进行运算，并将结果存储到文件中。攻击者非法获得加密的口令文件后，将比较这两个文件，观察是否有匹配的口令密文。字典式攻击，成功率非常高。这是因为大多数人缺乏安全意识和想象力，选择的口令过于简单。编制巨大的口令表是个问题吗？从网上就能找到，热心的黑客们已经把它完善得很好了。第第3 3章章 单向散列函数单向散列函数44Network and Information Security1 1、Salt(Salt(添添加加符符)是是使使这这种种攻攻击击更更困困难难的的一一种种方方法法。SaltSalt是是一一随随机机字字符符串串，它它与与口口令令

43、连连接接在在一一起起，再再用用单单向向散散列列函函数数对对其其运运算算。然然后后将将SaltSalt值和单向散列函数运算的结果存入主机数据库中。值和单向散列函数运算的结果存入主机数据库中。攻攻击击者者必必须须对对所所有有可可能能的的SaltSalt值值进进行行计计算算。如如果果SaltSalt的的长长度度为为6464比比特特，那那么么攻攻击击者者的的预预计计算算量量就就增增大大了了2 26464倍倍，同时存储量也增大了同时存储量也增大了2 26464倍，使得字典攻击几乎不可能。倍，使得字典攻击几乎不可能。如如果果攻攻击击者者得得知知SaltSalt值值后后进进行行攻攻击击，那那就就不不得得不不

44、重重新新计计算所有可能的口令，仍然是比较困难的。算所有可能的口令，仍然是比较困难的。2 2、另另一一个个对对策策是是增增加加单单向向散散列列函函数数处处理理次次数数。比比如如可可以以对对口口令令用用单单向向散散列列函函数数处处理理1010次次，这这就就大大大大增增加加了了攻攻击击者者的的预预计计算算时时间间，但但对对正正常常用户没有明显影响。用户没有明显影响。对策第第3 3章章 单向散列函数单向散列函数45Network and Information Security3.5.2 生日攻击对单向散列函数有两种穷举攻击的方法。第一种是最明显的：给定消息M的散列值H(M)，破译者逐个生成其他消息M

45、，以使H(M)=H(M)。第二种攻击方法更巧妙：攻击者寻找两个随机的消息：M和M，并使H(M)=H(M)(这称为碰撞)，这就是所谓的生日攻击，它比第一种方法来得容易。第第3 3章章 单向散列函数单向散列函数46Network and Information Security生日悖论是一个标准的统计问题。房子里面应有多少人才能使至少一人与你生日相同的概率大于1/2呢？答案是253。既然这样，那么应该有多少人才能使他们中至少两个人的生日相同的概率大于1/2呢？答案出人意料地低：23人。若一个房子里面的人数有100人，有两人相同生日的概率是：0.9999997第第3 3章章 单向散列函数单向散列函数

46、47Network and Information Security寻寻找找特特定定生生日日的的某某人人类类似似于于第第一一种种方方法法；而而寻寻找找两两个个随随机机的的具具有有相同生日的两个人相同生日的两个人则是第二种攻击。这就是生日攻击名称的由来。则是第二种攻击。这就是生日攻击名称的由来。假假设设一一个个单单向向散散列列函函数数是是安安全全的的，并并且且攻攻击击它它最最好好的的方方法法是是穷穷举举攻击。攻击。假假定定其其输输出出为为m m比比特特，那那么么寻寻找找一一个个消消息息，使使其其散散列列值值与与给给定定散散列列值值相相同同则则需需要要计计算算2 2m m次次；而而寻寻找找两两个个

47、消消息息具具有有相相同同的的散散列列值值仅仅需要试验需要试验2 2m/2m/2个随机的消息。个随机的消息。每每秒秒能能运运算算一一百百万万次次单单向向散散列列函函数数的的计计算算机机得得花花600,000600,000年年才才能能找找到到一一个个消消息息与与给给定定的的6464比比特特散散列列值值相相匹匹配配。同同样样的的机机器器可可以以在在大约一个大约一个小时里小时里找到一对有相同散列值的消息。找到一对有相同散列值的消息。第第3 3章章 单向散列函数单向散列函数48Network and Information Security这这就就意意味味着着如如果果你你对对生生日日攻攻击击非非常常担担

48、心心，那那么么你你所所选选择择的的单单向向散散列列函函数数其其输输出出长长度度应应该该是是你你本本以以为为可可以以的的两两倍倍。例例如如，如如果果你你想想让让他他们们成成功功破破译译你你的的系系统统的的可可能能低低于于1/21/28080，那那么么应应该该使使用用输输出出为为160160比比特特的的单单向向散散列列函数。函数。令我们中国人骄傲的是，令我们中国人骄傲的是，山东大学数学院的王小云教山东大学数学院的王小云教授已经破解了授已经破解了MD5MD5和和SHA-1SHA-1这两大主流算法。这两大主流算法。这在国际这在国际社会尤其是国际密码学领域引起了极大反响，也敲响社会尤其是国际密码学领域引

49、起了极大反响，也敲响了电子商务安全的警钟。了电子商务安全的警钟。第第3 3章章 单向散列函数单向散列函数49Network and Information Security2004年8月17日，在美国加州圣巴巴拉召开的国际密码学会议上，王小云教授公布了MD5算法的破解成果。其后，密码学家Arjen Lenstra利用王小云教授的研究成果伪造了符合X.509标准的数字证书。这进一步说明了MD5的破译已经不仅仅是理论破译结果，而是可以导致实际的攻击。MD5的撤出迫在眉睫。王小云教授的攻击方法称为模差分。这种攻击是一种特殊的差分攻击，与其它差分攻击不同，它不使用异或作为差分手段，而使用整模减法差分作

50、为手段。这种方法可以有效地查找碰撞，使用这种攻击可在15分钟至1小时内查找到MD5碰撞。将这种攻击用于MD4,则能在不到一秒钟的时间内找到碰撞。这种攻击也可用于其它单向散列函数，如RIPEMD、HAVAL。第第3 3章章 单向散列函数单向散列函数50Network and Information Security更让密码学界震惊的是，2005年2月15日，王小云等人的论文证明SHA-1算法在理论上也被破解。这是继王小云破译MD5之后，国际密码学领域的又一突破性研究成果，而破译只用了两个多月的时间。需要指出的是，找到单向散列函数的碰撞并不能证明单向散列函数就彻底失效了。因为产生碰撞的消息可能是随