第3章1 杂凑函数

1、第3章 网络安全认证3.1 杂凑函数杂凑函数3.1.1 杂凑函数基础杂凑函数基础1. 杂凑函数概念杂凑函数概念 定义：杂凑函数就是把任意长的输入串杂凑函数就是把任意长的输入串M变化成固变化成固定长的输出串定长的输出串h的一种函数，是多对一的函数。的一种函数，是多对一的函数。别称：称为别称：称为哈希（哈希（Hash）函数、散列函数）函数、散列函数。结果值的名称：结果值的名称：杂凑值、消息摘要、数据指纹杂凑值、消息摘要、数据指纹。杂凑函数的特点：给定的输入计算杂凑值是很容易的，杂凑函数的特点：给定的输入计算杂凑值是很容易的，但求逆是比较困难的，因此，又被称为单向杂凑函数。但求逆是比较困难的，因此，

2、又被称为单向杂凑函数。杂凑函数的形式为：杂凑函数的形式为：h=H(M)杂凑函数的目的就是要产生文件、报文或其他数据块杂凑函数的目的就是要产生文件、报文或其他数据块的的“指纹指纹” 。23.1 杂凑函数杂凑函数杂凑函数的计算过程可归纳如下：杂凑函数的计算过程可归纳如下：hash函数的输入为任意长度的报文函数的输入为任意长度的报文M，它，它由分组由分组 组成，可能需要填充；组成，可能需要填充；计算步骤为：计算步骤为：011,LMMM0CVIV n 位 初 始 值11(,)1iiiCVf CVMi L ()LH MCV33.1 杂凑函数杂凑函数2. 杂凑函数性质杂凑函数性质 基本性质：基本性质：必须

3、可应用于任意大小的数据块并产必须可应用于任意大小的数据块并产生定长的输出；生定长的输出；对任何给定的对任何给定的M，用硬件和，用硬件和/或软件均或软件均比较容易实现计算比较容易实现计算H(M)。 43.1 杂凑函数杂凑函数杂凑函数还要满足以下性质：杂凑函数还要满足以下性质：单向性：对任何给定的杂凑值单向性：对任何给定的杂凑值h，找到满足，找到满足H(M)=h的的M在计算上是不可行的。在计算上是不可行的。抗弱碰撞性：对任何给定的分组抗弱碰撞性：对任何给定的分组M，找到满，找到满足足 且且 的的 在计算上是不可在计算上是不可行的。行的。抗强碰撞性：找到任何满足抗强碰撞性：找到任何满足 的偶的偶对对

4、 在计算上是不可行的。在计算上是不可行的。MM ()()H MH MM12()()H MH M1212,M MMM53.1 杂凑函数杂凑函数3. 生日攻击生日攻击(1) 第第I类生日攻击类生日攻击 已知一杂凑函数已知一杂凑函数H有有n个可能的输个可能的输出，出，H(M)是一个特定的输出，如果对是一个特定的输出，如果对H随机取随机取k个输入，则至少有一个输入个输入，则至少有一个输入N使得使得H(N)=H(M)的概率为的概率为0.5时，时，k有多大？有多大？k=n/2。我们称这类寻找为第。我们称这类寻找为第I类生日类生日攻击。攻击。(找到弱碰撞找到弱碰撞)63.1 杂凑函数杂凑函数(2) 生日悖论

5、生日悖论 生日悖论考虑这样一个问题：在生日悖论考虑这样一个问题：在k个人中至少有两个人的生日相同的个人中至少有两个人的生日相同的概率大于概率大于1/2时，时，k至少多大？至少多大？k=1.18365 （找到强碰撞）（找到强碰撞）73.1 杂凑函数杂凑函数(3) 第第类生日攻击类生日攻击（生日攻击）（生日攻击） 生日攻击基于下述结论：设杂凑函生日攻击基于下述结论：设杂凑函数数H有有 个可能的输出（即输出长个可能的输出（即输出长m比特）。如果比特）。如果H的的k个随机输入中至少个随机输入中至少有两个产生相同输出的概率大于有两个产生相同输出的概率大于1/2，则则 我们称寻找函数我们称寻找函数H的具有

6、相同输出的具有相同输出的两个任意输入的攻击方式为第的两个任意输入的攻击方式为第类类生日攻击。生日攻击。 2m/222mmk 83.1 杂凑函数杂凑函数4. 杂凑函数应用杂凑函数应用 杂凑函数可以用于提供报文认证、杂凑函数可以用于提供报文认证、数字签名以及保密等功能。数字签名以及保密等功能。93.1 杂凑函数杂凑函数3.1.2 经典杂凑函数经典杂凑函数-MD5MD5算法步骤如下：算法步骤如下：步骤步骤1：填充报文。：填充报文。步骤步骤2：初始化缓冲区。：初始化缓冲区。步骤步骤3：执行算法主循环（具体细节见后：执行算法主循环（具体细节见后面分析）。面分析）。步骤步骤4：输出。：输出。10(1) (

7、1) 填充消息使其长度正好为填充消息使其长度正好为512 bit512 bit的整的整数倍数倍L L倍。倍。 首先在消息的末尾处附上首先在消息的末尾处附上64 bit64 bit的消息的消息长度的二进制表示（最低有效位在前），长度的二进制表示（最低有效位在前），大小为大小为n(mod 2n(mod 26464) )，n n表示消息长度。然后表示消息长度。然后在消息后面填充一个在消息后面填充一个“1”1”和多个和多个“0”0”，填充后的消息恰好是填充后的消息恰好是512 bit512 bit的整数倍长的整数倍长L L。Y Y0 0，Y Y1 1，Y YL-1L-1表示不同的表示不同的512 bi

8、t512 bit长的长的消息块，用消息块，用M M0 0，M M1 1，M MN N1 1表示各个表示各个YqYq中按中按32 bit32 bit分组的字，分组的字，N N一一定是定是1616的整数倍。的整数倍。(2) (2) 初始化缓冲区。初始化缓冲区。 算法中使用了算法中使用了128 bit128 bit的缓冲区，每个缓的缓冲区，每个缓冲区由冲区由4 4个个32 bit32 bit的寄存器的寄存器A A、B B、C C、D D组成，组成，先把这先把这4 4个寄存器初始化为个寄存器初始化为 A=01 23 45 67 A=01 23 45 67 B=89 AB CD EFB=89 AB CD

9、 EF C=FE DC BA 98C=FE DC BA 98 D=76 54 32 10 D=76 54 32 10(1) (1) 处理处理512 bit512 bit消息块消息块Y Yq q，进入主循环。，进入主循环。主循环的次数正好是消息中主循环的次数正好是消息中512 bit512 bit的块的数目的块的数目L L。先从。先从Y Y0 0开始，上一循环的输出作为下一循开始，上一循环的输出作为下一循环的输入，直到处理完环的输入，直到处理完Y YL-1L-1为止。为止。对消息块对消息块Y Yq q的处理过程是这样的，以当前的的处理过程是这样的，以当前的512 512 bitbit数据块数据块

10、Y Yq q和和128 bit128 bit缓冲值缓冲值A A、B B、C C、D D作为作为输入，处理结果存放在输入，处理结果存放在A A、B B、C C、D D中。消息块中。消息块Y Yq q的处理包含的处理包含4 4轮操作，每一轮由轮操作，每一轮由1616次迭代操次迭代操作组成，上一轮的输出作为下一轮的输入，如作组成，上一轮的输出作为下一轮的输入，如图图3-13-1所示。所示。4 4轮处理具有相似的结构：轮处理具有相似的结构：A A，B B，C C，D-DD-D，B+(A+g(B,C,D)+Mk+TI)SB+(A+g(B,C,D)+Mk+TI)S，B B，C)C)如图如图3-23-2所示

11、所示, ,但每轮处理使用不同的非线性但每轮处理使用不同的非线性函数。函数函数。函数g g为以下为以下4 4个非线性函数之一：个非线性函数之一： F(XF(X，Y Y，Z)=(XY)(XZ) Z)=(XY)(XZ) G(XG(X，Y Y，Z)=(XZ)(YZ)Z)=(XZ)(YZ) H(XH(X，Y Y，Z)=XYZZ)=XYZ I(XI(X，Y Y，Z)=Y(XZ)Z)=Y(XZ) (4) (4) 输出。输出。 每一轮不断地更新缓冲区每一轮不断地更新缓冲区A A、B B、C C、D D中的内容，中的内容，4 4轮之后进轮之后进入下一个主循环，直到处理完入下一个主循环，直到处理完所有消息块为止。

12、最后输出的所有消息块为止。最后输出的就是运算结束时缓冲区中的内就是运算结束时缓冲区中的内容。容。3.1 杂凑函数杂凑函数(3) MD5的安全性的安全性 MD5算法中，杂凑函数的每一位都是输入的每算法中，杂凑函数的每一位都是输入的每一位的函数，逻辑函数一位的函数，逻辑函数F、G、H、I的复杂迭代使得的复杂迭代使得输出对输入的依赖非常小。输出对输入的依赖非常小。 但是，但是，Berson已经证明，对单轮的已经证明，对单轮的MD5算法，算法，利用差分密码分析，可以在合理时间内找出摘要相利用差分密码分析，可以在合理时间内找出摘要相同的两条报文。同的两条报文。MD5算法抗密码分析的能力较弱，对算法抗密码

13、分析的能力较弱，对MD5的生日攻的生日攻击所需代价是击所需代价是264。 2004年年8月月17日，在美国加州圣巴巴拉召开的日，在美国加州圣巴巴拉召开的美密会（美密会（Crypto2004）上，中国的王小云、冯登国、）上，中国的王小云、冯登国、来学嘉、于红波来学嘉、于红波4位学者宣布，只需位学者宣布，只需1小时就可找出小时就可找出MD5的碰撞。的碰撞。183.1 杂凑函数杂凑函数3.1.3. SHA-1 安全杂凑算法（安全杂凑算法（Secure hash algorithm，SHA）是由美国标准技术研究）是由美国标准技术研究所（所（NIST）设计并于）设计并于1993年公布的一种标准年公布的一

14、种标准算法（算法（FIPS PUB 180），），1995年又公布了年又公布了FIPS PUB 180-1，通常称之为，通常称之为SHA-1。其输。其输入为长度小于入为长度小于264位的报文，输出为位的报文，输出为160位的位的报文摘要，该算法对输入按报文摘要，该算法对输入按512位进行分组，位进行分组，并以分组为单位进行处理。并以分组为单位进行处理。 193.1 杂凑函数杂凑函数 SHA-1算法步骤算法步骤(1)(1)附加填补比特附加填补比特 在消息的后面填补一个“1”比特，然后填补“0”比特，直到该消息的比特长度模512余448。(2)(2)附加消息长度附加消息长度 用64比特表示消息长度

15、，放在填补比特之后。如果消息的长度大于264，则取其低位64比特。经过这步的操作，消息的比特数为512的倍数，其字(32比特) 数为16的倍数，把这些字记作M0,M1Mn-1 。20(3)(3)初始化寄存器初始化寄存器SHA-1算法用到了5个32比特的寄存器A、B、C、D、E计算消息压缩值。5个寄存器的初始值为：A：0 x67452301B：0 xefcdab89C：0 x98badcfeD：0 x10325476E：0 xc3d2elf021(4)(4)以以1616个字分组个字分组(512(512比特比特) )为单位对消息进行处理为单位对消息进行处理 整个算法由四层组成，每层包括整个算法由四

16、层组成，每层包括2020个独立的操作。个独立的操作。 每层用了一个辅助函数和一个常数如下：每层用了一个辅助函数和一个常数如下：F F0 0(X,Y,Z) = (X&Y) | (X,Y,Z) = (X&Y) | ( X&Z)X&Z)F F1 1(X,Y,Z) = XYZ(X,Y,Z) = XYZF F2 2(X,Y,Z) = (X&Y) | (Y&Z) | (X&Z)(X,Y,Z) = (X&Y) | (Y&Z) | (X&Z)F F3 3(X,Y,Z) = XYZ(X,Y,Z) = XYZK K0 0 = 0 x5

17、a827999 = 0 x5a827999K K1 1 = 0 x6ed9eba1 = 0 x6ed9eba1K K2 2 = 0 x8flbbcdc = 0 x8flbbcdcK K3 3 = 0 xca62cld6 = 0 xca62cld6由分组的由分组的1616个字个字M M0 0,M,M1 1.M.M1515产生出产生出8080个个3232比特字比特字( (随机组合随机组合)W)W0 0 W W7979对于对于t = 0 t = 0 1515，使得，使得Wt = MWt = Mt t。对于对于t = 16 t = 16 7979，使得，使得Wt = WWt = Wt-3t-3WWt-

18、8t-8WWt-14t-14WWt-16t-16令令AA = AAA = A，BB = B, CC = C, DD = D, EE = EBB = B, CC = C, DD = D, EE = E。22四层变换如下：For(i = 0; i 4; i+)For(i = 0; i 4; i+) For(j = 0; j 20; j+)For(j = 0; j 20; j+) TEMP = (A5) + FTEMP = (A5) + Fi i(B,C,D) + E + K(B,C,D) + E + Ki i + W + Wi i* *20+j20+j ; ;(A,B,C,D,E) = (TEMP

19、,A,B30,C,D);(A,B,C,D,E) = (TEMP,A,B30,C,D); 令令A = A + AAA = A + AA，B = B + BBB = B + BB，C = C + CCC = C + CC，D = D + DDD = D + DD，E = E = E + EEE + EE至此，16字的分组压缩变换就结束了，然后以五个寄存器的状态为初态对下一个16字分组进行变换，直至整个消息变换结束。(5)(5)输出输出将(A、B、C、D、E)作为消息压缩值输出，输出顺序为从A的最高字节开始到E的最低字节。上述5步完成了SHA算法。233.1 杂凑函数杂凑函数3.1.4、SHA-3S

20、HA-224、SHA-256、SHA-384，和，和SHA-512并称为并称为SHA-2。SHA-2并没有接受像并没有接受像SHA-1一样一样的公众密码社区做详细的检验，所以它们的密码的公众密码社区做详细的检验，所以它们的密码安全性还不被大家广泛的信任。虽然至今尚未出安全性还不被大家广泛的信任。虽然至今尚未出现对现对SHA-2有效的攻击，它的算法跟有效的攻击，它的算法跟SHA-1基本基本上仍然相似。上仍然相似。243.1 杂凑函数杂凑函数近年来，随着密码分析学的发展，通过对算法数近年来，随着密码分析学的发展，通过对算法数学分析攻击，已大大削弱了哈希算法的安全性。学分析攻击，已大大削弱了哈希算法的安全性。为了提高杂凑函数的安全性，为了提高杂凑函数的安全性，2007 年美国年美国 NIST 面向全球公开竞选面向全球公开竞选 SHA-3 算法。算法。2012年年10月月2日，日，Keccak算法成为算法成为SHA-3算法。算法。Keccak算法由意法半导体的算法由意法半导体的Guido Bertoni、Joan Daemen（AES算法合作者）和算法合作者）和Gilles Van Assche，以及恩智浦半导体的，以及恩智浦半导体的Michal Peeters联合开发。联合开发。25KeccakKeccak算法对于输出为算法对于输出为256位位Hash算法应算法应