第3章 单向散列函数 3.1 单向散列函数概述 3.2 MD5算法 3.3 SHA-1算法 3.4 消息认证码(MAC) 第3章 单向散列函数 3.1 单向散列函数概述 3.2 MD5算法 3.3 SHA-1算法 3.4 消息认证码(MAC) 3.5 对单向散列函数的攻击

导言 随着以Internet为基础的电子商务技术的迅猛发展,以公钥密码、数字签名等为代表的加密安全技术已成为研究的热点。 单向散列函数是数字签名中的一个关键环节,可以大大缩短签名时间并提高安全性,另外在消息完整性检测,内存的散布分配,软件系统中帐号口令的安全存储单向散列函数也有重要应用。

3.1 单向散列函数概述 所谓的单向散列函数(Hash Function，又称哈希函数、杂凑函数)，是将任意长度的消息M映射成一个固定长度散列值h(设长度为m)的函数H：h=H(M) 散列函数要具有单向性，则必须满足如下特性： ● 给定M，很容易计算h。 ● 给定h，根据H(M)=h反推M很难。 ● 给定M，要找到另一消息M'并满足H(M)=H(M')很难。 在某些应用中，单向散列函数还需要满足抗碰撞(Collision)的条件：要找到两个随机的消息M和M'，使H(M)=H(M')很难。

Hash函数的良好性质 （ 1 ）广泛的应用性 Hash函数能用于任何大小的消息。 （ 2 ） 定长输出 将消息集合∑中的任意长度的消息Ｍ映射为长度为ｍ的消息摘要。 （ 3 ） 实现性 对Hash函数的一个非常重要的要求是简单易实现性。 （ 4 ） 单向性质 要求Hash函数是单向函数。给定h值，求信息M （是一对多的关系） ，只有通过枚举，在现有的计算环境下是不可行的。

（ 5 ） 抗弱对抗性 确定与x有相同位数的y,使H(x)=H(y), 在现有的计算环境下是不可行的。 （ 6 ） 抗强对抗性 找到两个不同位数信息x,y,使H(x)=H(y)，在现有的计算环境下是不可行的。 注：以上两种，哪一种更容易找？ （ 7 ） 独立性 哈希函数值“不依赖输入信息”，从某种程度上说是由算法决定的。 （ 8 ）抗近冲突 Hash函数满足独立性，输入信息某一位的变化，应该引起平均一半的输出位的变化。 （9 ） 安全性 在很广泛的条件下, Hash值Ｈ(Ｍ)的分布是均匀分布的.

散列函数工作模式 图3-1 单向散列函数工作模式

3.2 MD5 算 法 3.2.1 算法 MD表示消息摘要(Message Digest)。MD5是MD4的改进版，该算法对输入的任意长度消息产生128位散列值(或消息摘要) 。MD5算法可用图3-2表示。

4) 按512位的分组处理输入消息 1) 附加填充位 2) 附加长度64 3) 初始化MD缓冲区 5) 输出 图3-2 MD5算法

由上图可知，MD5算法包括以下五个步骤。 1) 附加填充位 首先填充消息，使其长度为一个比512的倍数小64位的数。填充方法：在消息后面填充一位1，然后填充所需数量的0。填充位的位数从1～512。 填充消息长度=512-(k+64) mod 512 2) 附加长度 将原消息长度的64位表示附加在填充后的消息后面。当原消息长度大于264时，用消息长度mod 264填充。这时，总长度恰好是512的整数倍。令M[0 1…N−1]为填充后消息的各个字(每字为32位)，N是16的倍数。

初始化用于计算消息摘要的128位缓冲区。这个缓冲区由四个32位寄存器A、B、C、D表示。寄存器的初始化值为(按低位字节在前的顺序存放)： 3) 初始化MD缓冲区 初始化用于计算消息摘要的128位缓冲区。这个缓冲区由四个32位寄存器A、B、C、D表示。寄存器的初始化值为(按低位字节在前的顺序存放)： A: 01 23 45 67 B: 89 ab cd ef C: fe dc ba 98 D: 76 54 32 10 4) 按512位的分组处理输入消息 这一步为MD5的主循环，包括四轮，如图3-3所示。每个循环都以当前的正在处理的512比特分组Yq和128比特缓冲值ABCD为输入，然后更新缓冲内容。

图3-3 单个512比特分组的MD5主循环处理

图3-3中，四轮的操作类似，每一轮进行16次操作。各轮的操作过程如图3-4所示。 j:0—15, i:1—64(共四轮， 每一轮用的都不同) 图3-4 MD5某一轮的1次执行过程

四轮操作的不同之处在于每轮使用的非线性函数不同，在第一轮操作之前，首先把A、B、C、D复制到另外的变量a、b、c、d中。这四个非线性函数分别为(其输入/输出均为32位字)： F(X,Y,Z) = (X ٨ Y)٧ ((～X) ٨ Z) G(X,Y,Z) = (X ٨ Z) ٧(Y ٨ (～Z)) H(X,Y,Z) = X  Y Z I(X,Y,Z) = Y (X ٧(～Z)) 其中， ٨表示按位与； ٧表示按位或；～表示按位反； 表示按位异或。

此外，由图3-4可知，这一步中还用到了一个有64个元素的表T[1..64]，T[i]=232×abs(sin(i))，i的单位为弧度。 根据以上描述，将这一步骤的处理过程归纳如下： for i = 0 to N/16−1 do /* 每次循环处理16个字， 即512字节的消息分组*/ /*把A存为AA，B存为BB，C存为CC，D存为DD*/ AA = A BB = B CC = C DD = D

b = b + ((a + F(b,c,d) + M[k] + T[i]) <<< s)  /* 第一轮*//* 令[abcd k s i]表示操作 b = b + ((a + F(b,c,d) + M[k] + T[i]) <<< s) 其中，Y<<<s表示Y循环左移s位*/ /* 完成下列16个操作*/ [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]

b = b + ((a + G(b,c,d) + M[k] + T[i]) <<< s)*/ /* 第二轮*/ /*令[abcd k s i]表示操作 b = b + ((a + G(b,c,d) + M[k] + T[i]) <<< s)*/ /*完成下列16个操作*/ [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]

b= b + ((a + H(b,c,d) + M[k] + T[i]) <<< s)*/ /*第三轮*/ /*令[abcd k s t]表示操作 b= b + ((a + H(b,c,d) + M[k] + T[i]) <<< s)*/ /*完成以下16个操作*/ [ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36] [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40] [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]

b = b + ((a + I(b,c,d) +M[k] + T[i]) <<< s) */ /*第四轮*/ /*令[abcd k s t]表示操作 b = b + ((a + I(b,c,d) +M[k] + T[i]) <<< s) */ /*完成以下16个操作*/ [ABCD 0 6 49] [DABC 7 10 50] [CDAB14 15 51][BCDA 52 1 52] [ABCD 12 6 53] [DABC 310 54][CDAB10 15 55][BCDA1 21 56] [ABCD 8 6 57] [DABC15 10 58][CDAB 6 15 59][BCDA13 21 60] [ABCD 4 6 61] [DABC11 10 62][CDAB 2 15 63][BCDA 9 21 64] A = A + AA B = B + BB C = C + CC D = D + DD end /*i循环*/

5) 输出 由A、B、C、D四个寄存器的输出按低位字节在前的顺序(即以A的低字节开始、D的高字节结束)得到128位的消息摘要。 以上就是对MD5算法的描述。MD5算法的运算均为基本运算，比较容易实现且速度很快。

3.2.2 举例 我们以求字符串“abc”的MD5散列值为例来说明上面描述的过程。“abc”的二进制表示为01100001 01100010 01100011。 1．填充消息 消息长24，先填充1位1，然后填充423位0，再用消息长24，即0x00000000 00000018填充，则： M[0]=61626380 M[1]=00000000 M[2]=00000000 M[3]=00000000 M[4]=00000000 M[5]=00000000 M[6]=00000000 M[7]=00000000 M[8]=00000000 M[9]=00000000 M[10]=00000000 M[11]=00000000 M[12]=00000000 M[13]=00000000 M[14]=00000000 M[15]=00000018 2．初始化 A:01 23 45 67 B:89 ab cd ef C:fe dc ba 98 D:76 54 32 10 3．主循环：利用3.2.1节中描述的过程对字块1（本例只有一个字块）进行处理。变量a、b、c、d每一次计算后的中间值不再详细列出。 4．输出 消息摘要=90015098 3cd24fb0 d6963f7d 28e17f72

3.3 安全散列函数(SHA-1) 3.3.1 算法 SHA是美国NIST和NSA共同设计的安全散列算法(Secure Hash Algorithm)，用于数字签名标准DSS(Digital Signature Standard)。SHA的修改版SHA–1于1995年作为美国联邦信息处理标准公告(FIPS PUB 180–1)发布。 SHA–1产生消息摘要的过程类似MD5，如图3-5所示。

图3-5 SHA–1算法

SHA–1的输入为长度小于264位的消息（若大于， 用mod 即可），输出为160位的消息摘要。具体过程如下。 1) 填充消息 首先将消息填充为512位的整数倍，填充方法和MD5完全相同：先填充一个1，然后填充一定数量的0，使其长度比512的倍数少64位；接下来用原消息长度的64位表示填充。这样，消息长度就成为512的整数倍。以M0、M1、…、Mn-1表示填充后消息的各个字块(每字块为16个32位字)。

2) 初始化缓冲区 在运算过程中，SHA要用到两个缓冲区，两个缓冲区均有五个32位的寄存器。第一个缓冲区标记为A、B、C、D、E；第二个缓冲区标记为H0、H1、H2、H3、H4。此外，运算过程中还用到一个标记为W0、W1、…、W79的80个32位字序列和一个单字的缓冲区TEMP。在运算之前，初始化{Hj}： H0 = 0x67452301 H1 = 0xEFCDAB89 H2 = 0x98BADCFE H3 = 0x10325476 H4 = 0xC3D2E1F0

3) 按512位的分组处理输入消息 SHA运算主循环包括四轮，每轮20次操作。SHA用到一个逻辑函数序列f0、f1、…、f79。每个逻辑函数的输入为三个32位字，输出为一个32位字。定义如下(B、C、D均为32位字)： ft (B,C,D) = (B ٨ C) ٧(~B ٨ D) (0≤t≤19) ft (B,C,D) = B  C  D (20≤t≤39) ft (B,C,D) = (B ٨ C) ٧(B ٨ D) ٧(C ٨ D) (40≤t≤59) ft (B,C,D) = B  C  D (60≤t≤79) 其中，运算符的定义与3.1节中MD5运算中的相同。

SHA运算中还用到了常数字序列K0、K1、…、K79，其值为 Kt = 0x5A827999 (0≤t≤19) Kt = 0x6ED9EBA1 (20≤t≤39) Kt = 0x8F1BBCDC (40≤t≤59) Kt = 0xCA62C1D6 (60≤t≤79)

SHA算法按如下步骤处理每个字块Mi： (1) 把Mi分为16个字W0 W1…W15，其中，W0为最左边的字。 (2)  for t =16 to 79 do let Wt =(Wt−3 Wt−8 Wt−14 Wt−16)<<<1 (3)  Let A =H0，B =H1，C =H2，D =H3，E =H4 (4)  for t =0 to 79 do TEMP = (A<<<5)+ft (B, C, D)+E +Wt +Kt ; E =D; D =C; C =(B<<<30); B = A; A = TEMP; (5)Let H0 =H0 +A, H1 =H1 +B, H2 =H2 +C, H3 =H3 +D, H4 =H4 +E 4) 输出-- 在处理完Mn后，160位的消息摘要为H0、H1、H2、H3、H4级联的结果。

3.3.2 举例 我们以求字符串‘’abc‘’的SHA–1散列值为例来说明上面描述的过程。‘abc’的二进制表示为 a b c 3.3.2 举例 我们以求字符串‘’abc‘’的SHA–1散列值为例来说明上面描述的过程。‘abc’的二进制表示为 a b c 01100001 01100010 01100011。 (1) 填充消息：消息长l=24，先填充1位1，然后填充423位0，再用消息长24，即0x00000000 00000018（64位）填充。 (2) 初始化： H0 = 0x67452301 H1 = 0xEFCDAB89 H2 = 0x98BADCFE H3 = 0x10325476 H4 = 0xC3D2E1F0

(3) 主循环：处理消息字块1(本例中只有1个字块)，分成16个字： （01100001 01100010 01100011 24） W[0]=61626380 W[1]=00000000 W[2]=00000000 W[3]=00000000 W[4]=00000000 W[5]=00000000 W[6]=00000000 W[7]=00000000 W[8]=00000000 W[9]=00000000 W[10]=00000000 W[11]=00000000 W[12]=00000000 W[13]=00000000 W[14]=00000000 W[15]=00000018 然后根据3.2.1节中描述的过程计算，其中，循环“for t = 0 to 79”中，各步A、B、C、D、E 的值如下：

A B C D E t=0: 0116FC33 67452301 7BF36AE2 98BADCFE 10325476 t=1: 8990536D 0116FC33 59D148C0 7BF36AE2 98BADCFE t=2: A1390F08 8990536D C045BF0C 59D148C0 7BF36AE2 t=3: CDD8E11B A1390F08 626414DB C045BF0C 59D148C0 t=4: CFD499DE CDD8E11B 284E43C2 626414DB C045BF0C t=5: 3FC7CA40 CFD499DE F3763846 284E43C2 626414DB t=6: 993E30C1 3FC7CA40 B3F52677 F3763846 284E43C2 t=7: 9E8C07D4 993E30C1 0FF1F290 B3F52677 F3763846 t=8: 4B6AE328 9E8C07D4 664F8C30 0FF1F290 B3F52677 t=9: 8351F929 4B6AE328 27A301F5 664F8C30 0FF1F290 t=10:FBDA9E89 8351F929 12DAB8CA 27A301F5 664F8C30

字块1处理完后，{Hi}的值为： H0 = 67452301 + 42541B35 = A9993E36 H1 = EFCDAB89 + 5738D5E1 = 4706816A H2 = 98BADCFE + 21834873 = BA3E2571 H3 = 10325476 + 681E6DF6 = 7850C26C H4 = C3D2E1F0 + D8FDF6AD = 9CD0D89D (4) 输出：消息摘要 = A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D 也就是说abc的散列函数值为：

3.3.3 SHA–1与MD5的比较 SHA–1与MD5的比较如表3-1所示。 表3-1 SHA-1与MD5的比较 ft (B,C,D) = (B ٨ C) ٧(~B ٨ D) (0≤t≤19) ft (B,C,D) = B  C  D (20≤t≤39) ft (B,C,D) = (B ٨ C) ٧(B ٨ D) ٧(C ٨ D) (40≤t≤59) ft (B,C,D) = B  C  D (60≤t≤79) F(X,Y,Z) = (X ٨ Y)٧ ((～X) ٨ Z) G(X,Y,Z) = (X ٨ Z) ٧(Y ٨ (～Z)) H(X,Y,Z) = X  Y Z I(X,Y,Z) = Y (X ٧(～Z))   SHA-1 MD5 Hash值长度 160 bit 128 bit 分组处理长 512 bit 步数 80(4×20) 64(4×16) 最大消息长 ≤264 bit 不限 非线性函数 3(第2、4轮相同) 4 常数个数 64 表3-1 SHA-1与MD5的比较

根据各项特征，简要地说明它们间的不同。 （1）安全性：SHA-1所产生的摘要较MD5长32位。若两种散列函数在结构上没有任何问题的话，SHA-1比MD5更安全。 （2）速度：两种方法都考虑了以32位处理器为基础的系统结构，但SHA-1的运算步骤较MD5多了16步，而且SHA-1记录单元的长度较MD5多了32位。因此若是以硬件来实现SHA-1，其速度大约较MD5慢25%。 （3）简易性：两种方法都相当的简单，在实现上不需要很复杂的程序或是大量的存储空间。然而总体上来讲，SHA-1每一步的操作都较MD5简单。

3.4 消息认证码(MAC) 与密钥相关的单向散列函数通常称为MAC，即消息认证码： MAC=CK(M) 其中，M为可变长的消息；K为通信双方共享的密钥；C为单向函数。 MAC可为拥有共享密钥的双方在通信中验证消息的完整性；也可被单个用户用来验证他的文件是否被改动，如图3-6所示。

图3-6 MAC应用于消息认证 若没有K， 能否验证消息的完整性？ 不能如攻击者将消息M 和摘要都替换了，将不能验证原消息的完整性

RFC 2104定义的HMAC算法HMAC全称为Keyed-Hash Message Authentication Code， 它用一个秘密密钥来产生和验证MAC B：计算消息摘要时输入块的字节长度(如对于SHA-1, B = 64)。 H：散列函数，如SHA-1，MD5等。 ipad：将数值0x36重复B次。 opad：将数值0x5c重复B次。 K：共享密钥。 K0 ：在密钥K的左边附加0使其长为B字节的密钥。 L：消息摘要的字节长度(如对于SHA-1，L = 20)。 t：MAC的字节数。

text：要计算HMAC的数据。数据长度为n字节，n的最大值依赖于采用的hash函数。 X || Y：将字串连接起来，即把字串Y附加在字串X后面。 ：异或。 密钥K的长度应大于或等于L/2。当使用长度大于B的密钥时，先用H对密钥求得散列值，然后用得到的L字节结果作为真正的密钥。 利用HMAC函数计算数据text的MAC过程如图3-7所示。

图3-7 HMAC结构

由图可知，HMAC执行的是如下操作： MAC(text)t = HMAC(K, text)t = H((K0 opad )|| H((K0 ipad) || text))t 具体操作步骤如下： (1) 如果K的长度等于B，设置K0 = K并跳转到第(4)步。 (2) 如果K的长度大于B，对K求散列值：K0 = H(K)。 (3) 如果K的长度小于B，在K的左边附加0得到B字节的K0。 (4) 执行K0 ipad。

(K0 opad) || H((K0 ipad) || text) (8) 把第(6)步的结果附加在第(7)步的结果后面： (K0 opad) || H((K0 ipad) || text)

H((K0 opad )|| H((K0 ipad) || text)) (10) 选择第(9)步结果的最左边t字节作为MAC。 HMAC算法可以和任何密码散列函数结合使用，而且对HMAC实现作很小的修改就可用一个散列函数H代替原来的散列函数H'。

3.5 对单向散列函数的攻击 对单向散列函数攻击的目的在于破坏单向散列函数的某些特性. 3.5 对单向散列函数的攻击 对单向散列函数攻击的目的在于破坏单向散列函数的某些特性. 比如可以根据输出求得输入，找到一条新消息使它的输出与原消息的输出相同，或者找到不同的两个消息，使它们的输出相同。

3.5.1 字典攻击 字典攻击，对用单向散列函数加密的口令文件特别有效。攻击者编制含有多达几十万个常用口令的表，然后用单向散列函数对所有口令进行运算，并将结果存储到文件中。 攻击者非法获得加密的口令文件后，将比较这两个文件，观察是否有匹配的口令密文。 字典式攻击，成功率非常高。这是因为大多数人缺乏安全意识和想象力，选择的口令过于简单。编制巨大的口令表是个问题吗？ 从网上就能找到，热心的黑客们已经把它完善得很好了。

对策 1、Salt(添加符)是使这种攻击更困难的一种方法。Salt是一随机字符串，它与口令连接在一起，再用单向散列函数对其运算。然后将Salt值和单向散列函数运算的结果存入主机数据库中。 攻击者必须对所有可能的Salt值进行计算。如果Salt的长度为64比特，那么攻击者的预计算量就增大了264倍，同时存储量也增大了264倍，使得字典攻击几乎不可能。 如果攻击者得知Salt值后进行攻击，那就不得不重新计算所有可能的口令，仍然是比较困难的。 2、另一个对策是增加单向散列函数处理次数。比如可以对口令用单向散列函数处理10次，这就大大增加了攻击者的预计算时间，但对正常用户没有明显影响。

3.5.2 生日攻击 对单向散列函数有两种穷举攻击的方法。 3.5.2 生日攻击 对单向散列函数有两种穷举攻击的方法。 第一种是最明显的：给定消息M的散列值H(M)，破译者逐个生成其他消息M′，以使H(M)= H(M′)。 第二种攻击方法更巧妙：攻击者寻找两个随机的消息：M和M′，并使H(M)=H(M′)(这称为碰撞)，这就是所谓的生日攻击，它比第一种方法来得容易。

生日悖论是一个标准的统计问题。 房子里面应有多少人才能使至少一人与你生日相同的概率大于1/2呢？ 答案是253。 房间里应该有多少人才能使他们中至少两个人的生日相同的概率大于1/2呢？ 答案出人意料地低：23人。 若一个房子里面的人数有100人，有两人相同生日的概率是： 0.9999997

寻找特定生日的某人类似于第一种方法；而寻找两个随机的具有相同生日的两个人则是第二种攻击。这就是生日攻击名称的由来。 假设一个单向散列函数是安全的，并且攻击它最好的方法是穷举攻击。 假定其输出为m比特，那么寻找一个消息，使其散列值与给定散列值相同则需要计算2m次；而寻找两个消息具有相同的散列值仅需要试验2m/2个随机的消息。 每秒能运算一百万次单向散列函数的计算机得花600,000年才能找到一个消息与给定的64比特散列值相匹配。同样的机器可以在大约一个小时里找到一对有相同散列值的消息。

这就意味着如果你对生日攻击非常担心，那么你所选择的单向散列函数其输出长度应该是你本以为可以的两倍。例如，如果你想让他们成功破译你的系统的可能低于1/280，那么应该使用输出为160比特的单向散列函数。 令我们中国人骄傲的是，山东大学数学院的王小云教授已经破解了MD5和SHA-1这两大主流算法。这在国际社会尤其是国际密码学领域引起了极大反响，也敲响了电子商务安全的警钟。

2004年8月17日，在美国加州圣巴巴拉召开的国际密码学会议上，王小云教授公布了MD5算法的破解成果。其后，密码学家Arjen Lenstra利用王小云教授的研究成果伪造了符合X.509标准的数字证书。这进一步说明了MD5的破译已经不仅仅是理论破译结果，而是可以导致实际的攻击。MD5的撤出迫在眉睫。 王小云教授的攻击方法称为模差分。这种攻击是一种特殊的差分攻击，与其它差分攻击不同，它不使用异或作为差分手段，而使用整模减法差分作为手段。这种方法可以有效地查找碰撞，使用这种攻击可在15分钟至1小时内查找到MD5碰撞。将这种攻击用于MD4,则能在不到一秒钟的时间内找到碰撞。这种攻击也可用于其它单向散列函数，如RIPEMD、HAVAL。

更让密码学界震惊的是，2005年2月15日，王小云等人的论文证明SHA-1算法在理论上也被破解。这是继王小云破译MD5之后，国际密码学领域的又一突破性研究成果，而破译只用了两个多月的时间。 需要指出的是，找到单向散列函数的碰撞并不能证明单向散列函数就彻底失效了。因为产生碰撞的消息可能是随机的，没有什么实际意义。最致命的破解是对给定的消息M，较快地找到另一消息M'并满足H(M)=H(M')，当然M'应该有意义并最好符合攻击者的意图。

本章讨论与设计方向 - 实验二、密码口令安全分析与差分攻击 DES/AES算法实现与安全性分析 Md5算法原理与差分攻击（模差分） 数据库口令加密与安全设计 QQ口令安全机制研究 其他：RSA公钥密码安全性分析 2017/3/5