浅析MD5加密算法

tekin

摘要： MD5即“Message-Digest Algorithm 5（报文摘要算法）”，它与SHA加密算法一起被誉为国际加密大厦的两大奠基石。本文对MD5加密算法作了详细的分析研究，对MD5加密算法被破解一说提出不同看法，并总结了几种提高MD5强度的有效对策。

关键词：哈希函数；MD5算法

A survey of Research Work on   Message-Digest Algorithm 5

Abstract:MD5(Message-Digest Algorithm 5), together with SHA,is regarded to be the base of encryption. Discussing the feature of MD5 ,this paper do not agree to the argument that MD5 should be abandoned. At last, it put forward some feasible  methods  to improve MD5’s security.

Key words: hash function;MD5

1         引言

  2004年召开的国际密码学年会（Crypto 2004）上，来自中国山东大学的王小云教授的一篇《散列（哈希）函数 MD4、MD5、HAVAL-128 和 RIPEMD 中的碰撞》的报告轰动了全场，一时之间，国内外多家媒体纷纷称赞王小云教授的研究成果为密码学领域的重大发现，宣告了固若金汤的世界通行密码标准MD５大厦轰然倒塌。

   然而，本人认为，他们的研究虽然使密码研究者认识到MD5自身仍存在很大缺陷，但对于在实际应用中破解MD5算法尚无太大的帮助。目前提出MD5大厦倒塌为时尚早。最后，我们提出了加强MD5加密算法强度的几点建议。

2         MD5简介

MD5是一种不可逆的加密算法，应用极为广泛，主要的应用领域包括数字签名、数据库中的信息加密以及通信信息的加密。下面就MD5加密算法的特点、功能作一分析，并对如何加强信息的保密提出对策

2。1  MD5加密算法的由来

  MD5即“Message-Digest Algorithm 5（报文摘要算法）”，它由MD2、MD3、MD4发展而来的一种单向Hash函数算法，它是国际著名的公钥加密算法标准RSA的第一设计者Ron Rivest于1991年发布的。

   单向Hash函数有很多名字：散列函数、压缩函数、缩短函数、消息摘要、指纹，它是现代密码学的中心。Hash函数长期以来一直在计算机科学中使用，无论从数学上或别的角度看，Hash函数就是把可变输入长度串（叫做预映射）转换成固定长度（经常更短）输出串（叫做hash值）的一种函数。哈希函数有如下特点：

   (1) 已知哈希函数的输出，要求它的输入是困难的，即已知c=Hash（m），求m是困难的。这表现了函数的单向性。

   (2) 已知m，计算Hash（m）是容易的。这表现了函数的快速性。

   (3) 已知Hash(m1)=c1，构造m2使Hash（m2）=c1是困难的。这是函数的抗碰撞性。
   (4) c=Hash（m），c的每一比特都与m的每一比特有关，并有高度敏感性。即每改变m的一比特，都将对c产生明显影响。这就是函数的雪崩性。
   (5) 作为一种数字签名，还要求哈希函数除了信息m自身之外，应该基于发信方的秘密信息对信息m进行确认。
   (6) 接受的输入m数据没有长度限制；对输入任何长度的m数据能够生成该输入报文固定长度的输出
   (7) Hash函数是公开的，对处理过程不用保密。
    MD5就是当前应用最广泛的Hash算法之一，它将任意长度的原文映射成为一个128位的摘要信息串。

2.2  MD5算法的应用范围
    M当前D5算法的实际应用极为广泛，常见的Unix系统口令以及多数论坛、社区系统的口令都是经MD5处理后保存其摘要信息串；在互联网上，很多文件在开放下载的同时都提供一个MD5的信息摘要，使下载方(通过MD5摘要计算)能够确认所下载的文件与原文件一致，以此来防止文件被篡改。
    此外，MD5的还有两个极为重要的应用就是电子商务中的电子签名和数据库中关键信息的加密存储。数字签名就是通过一个单向Hash函数对要传送的报文进行处理得到的用以认证报文来源并核实报文是否发生变化的一个字母数字串。用这几个字符串来代替书写签名或印章，起到与书写签名或印章同样的法律效用。MD5是目前电子签名的法律效力和技术体系的有力保障之一。

2.3  MD5算法的描述
    对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。
    (1) 补位：
    MD5算法先对输入的数据进行补位，使得数据位长度LEN对512求余的结果是448。即数据扩展至K*512+448位。即K*64+56个字节，K为整数。
具体补位操作：补一个1，然后补0至满足上述要求。
    (2) 补数据长度：
    用 一个64位的数字表示数据的原始长度B，把B用两个32位数表示。这时，数据就被填补成长度为512位的倍数。
    (3) 初始化MD5参数：
    四个32位整数 A,B,C,D称为链接变量（Chaining Variable），用来计算信息摘要，初始化使用的是十六进制表示的数字：
　　A=0X01234567　　B=0X89abcdef
　　C=0Xfedcba98　　D=0X76543210
    (4) 理位操作函数：
　　X，Y，Z为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))
　 （&是与，|是或，~是非，^是异或）
    (5) 主要变换过程：
    算法的主循环次数是信息中512位信息分组的数目。主循环有四轮，每轮循环都进行16次（四种）操作。
    将上面四个链接变量复制到另外四个变量中：A到a，B到b，C到c，D到d，
    设Mj表示消息的第j个子分组（从0到15），<< s表示循环左移s位，则四种操作为：
　　　FF(a,b,c,d,Mj,s,ti)表示a=b+((a+(F(b,c,d)+Mj+ti)<<s)
  　　GG(a,b,c,d,Mj,s,ti)表示a=b+((a+(G(b,c,d)+Mj+ti)<<s)
  　　HH(a,b,c,d,Mj,s,ti)表示a=b+((a+(H(b,c,d)+Mj+ti)<<s)
　　　II(a,b,c,d,Mj,s,ti)表示a=b+((a+(I(b,c,d)+Mj+ti)<<s)

tekin

这四轮（64步）是：  

第一轮
　　　FF(a,b,c,d,M0,7,0xd76aa478)
　　　FF(d,a,b,c,M1,12,0xe8c7b756)
　　　FF(c,d,a,b,M2,17,0x242070db)
      FF(b,c,d,a,M3,22,0xc1bdceee)
　　　FF(a,b,c,d,M4,7,0xf57c0faf)
　　　FF(d,a,b,c,M5,12,0x4787c62a)
　　　FF(c,d,a,b,M6,17,0xa8304613)
　　　FF(b,c,d,a,M7,22,0xfd469501)
　　　FF(a,b,c,d,M8,7,0x698098d8)
　　　FF(d,a,b,c,M9,12,0x8b44f7af)
　　　FF(c,d,a,b,M10,17,0xffff5bb1)
　　　FF(b,c,d,a,M11,22,0x895cd7be)
　　　FF(a,b,c,d,M12,7,0x6b901122)
　　　FF(d,a,b,c,M13,12,0xfd987193)
　　　FF(c,d,a,b,M14,17,0xa679438e)
　　　FF(b,c,d,a,M15,22,0x49b40821)
　　第二轮
　　　GG(a,b,c,d,M1,5,0xf61e2562)
　　　GG(d,a,b,c,M6,9,0xc040b340)
　　　GG(c,d,a,b,M11,14,0x265e5a51)
　　　GG(b,c,d,a,M0,20,0xe9b6c7aa)
　　　GG(a,b,c,d,M5,5,0xd62f105d)
　　　GG(d,a,b,c,M10,9,0x02441453)
　　　GG(c,d,a,b,M15,14,0xd8a1e681)
　　　GG(b,c,d,a,M4,20,0xe7d3fbc8)
　　　GG(a,b,c,d,M9,5,0x21e1cde6)
　　　GG(d,a,b,c,M14,9,0xc33707d6)
　　　GG(c,d,a,b,M3,14,0xf4d50d87)
　　　GG(b,c,d,a,M8,20,0x455a14ed)
　　　GG(a,b,c,d,M13,5,0xa9e3e905)
　　　GG(d,a,b,c,M2,9,0xfcefa3f8)
　　　GG(c,d,a,b,M7,14,0x676f02d9)
　　　GG(b,c,d,a,M12,20,0x8d2a4c8a)
　　第三轮
　　　HH(a,b,c,d,M5,4,0xfffa3942)
　　　HH(d,a,b,c,M8,11,0x8771f681)
　　　HH(c,d,a,b,M11,16,0x6d9d6122)
　　　HH(b,c,d,a,M14,23,0xfde5380c)
　　　HH(a,b,c,d,M1,4,0xa4beea44)
　　　HH(d,a,b,c,M4,11,0x4bdecfa9)
　　　HH(c,d,a,b,M7,16,0xf6bb4b60)
　　　HH(b,c,d,a,M10,23,0xbebfbc70)
　　　HH(a,b,c,d,M13,4,0x289b7ec6)
　　　HH(d,a,b,c,M0,11,0xeaa127fa)
　　　HH(c,d,a,b,M3,16,0xd4ef3085)
　　　HH(b,c,d,a,M6,23,0x04881d05)
　　　HH(a,b,c,d,M9,4,0xd9d4d039)
　　　HH(d,a,b,c,M12,11,0xe6db99e5)
　　　HH(c,d,a,b,M15,16,0x1fa27cf8)
　　　HH(b,c,d,a,M2,23,0xc4ac5665)
　　第四轮
　　　II(a,b,c,d,M0,6,0xf4292244)
　　　II(d,a,b,c,M7,10,0x432aff97)
　　　II(c,d,a,b,M14,15,0xab9423a7)
　　　II(b,c,d,a,M5,21,0xfc93a039)
　　　II(a,b,c,d,M12,6,0x655b59c3)
　　　II(d,a,b,c,M3,10,0x8f0ccc92)
　　　II(c,d,a,b,M10,15,0xffeff47d)
　　　II(b,c,d,a,M1,21,0x85845dd1)
　　　II(a,b,c,d,M8,6,0x6fa87e4f)
　　　II(d,a,b,c,M15,10,0xfe2ce6e0)
　　　II(c,d,a,b,M6,15,0xa3014314)
　　　II(b,c,d,a,M13,21,0x4e0811a1)
　　　II(a,b,c,d,M4,6,0xf7537e82)
　　　II(d,a,b,c,M11,10,0xbd3af235)
　　　II(c,d,a,b,M2,15,0x2ad7d2bb)
　　　II(b,c,d,a,M9,21,0xeb86d391)

常数ti可以如下选择：
　　在第i步中，ti是4294967296*abs(sin(i))的整数部分，i的单位是弧度，4294967296等于2的32次方。
    所有这些完成之后，将A、B、C、D分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是A、B、C、D的级联。

2.4  MD5加密算法的关键价值
    Hash函数产生定长的数字签名，其结果是个有限的集合，而待签名的明文信息可以是计算机网络上传输的任意信息，也就是说，明文信息是一个无限集合，两个集合之间其实无法构成一一对应的关系，总会有多个明文信息产生相同Hash值的情况发生，这就是所谓的“碰撞”。不过Hash函数的可靠性在概率上仍可以算法的健壮性来保证，数字签名类似指纹，只要选择足够安全的算法，产生碰撞的概率就会足够小，可令现代最先进的计算设备也找不出“碰撞”，这样算法就不会被破解了。因此MD5以及SHA-1、SHA-2等Hash函数加密算法的价值关键之一在于算法的抗碰撞性，也就是算法的强度。
    Hash函数是一个单向算法，由预映射产生Hash值的运算过程中会丢失部分信息，对于任意给定的一个Hash值，要求出其预映射值在计算上是很困难的，也就是利用现有的计算设备和技术手段求出其预映射值在时间上是不可接受的。因此MD5以及SHA-1、SHA-2等Hash函数加密算法的价值关键之二在于算法的抗可逆性，也就是单向性。

3  MD5大厦离倒塌之日为时尚早
    2004年召开的国际密码学年会（Crypto 2004）上，来自中国山东大学的王小云教授的一篇《散列（哈希）函数 MD4、MD5、HAVAL-128 和 RIPEMD 中的碰撞》的报告轰动了全场，一时之间，国内外多家媒体纷纷称赞王小云教授的研究成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准MD５大厦轰然倒塌。

MD5算法真的就被破解了吗？根据王小云教授所作的报告，我们可以得到如下认识：
      在IBM P690（大约2千亿次/秒，128G内存）上用近一个小时的时间可以寻找到特定的M 和 M'，使得MD5（M）=MD5（M'），接下来用很短的时间就可以找到一对特定的Ni和Ni'，此时MD5(M, Ni)= (M', Ni') ，其中，M' = M + ΔC1，ΔC1 = (0，0，0，0，2³¹，…，2¹⁵，…，2³¹，0)
      Ni' = Ni + ΔC2，ΔC2 = (0，0，0，0，2³¹，…，-2¹⁵，…，2³¹，0)
   （位置4、11和14非零，M加上N的总长度为1024位。）
    基于上述认识，我们能够得出以下结论：
    (1) 碰撞的产生为非特定性的，能够满足碰撞路线的明文条件还很复杂。对于任意给出的明文，还不能在短时间内找到碰撞，而要伪造签名和破解Hash值密码必须形成特定碰撞。
    (2) MD5加密算法的价值在于其具有非常高的抗攻击成本，文中所提到的攻击方法只是降低了产生碰撞的成本，但余下的攻击成本仍旧很高。现在的破译计算时间仍然是2的69次方。这是个相当大的计算量，如果有一百万台快速计算机，要花几十年的时间才能实际破译这一算法。
    (3) 报告中产生特定碰撞的明文长度有限，如果采用较长文件加密（一般大于128字节）的方式，则MD5算法仍然有着足够强的抗碰撞性。
    (4) MD5加密算法至今还无法由输出求出明文，仍然具备单向性。在MD5加密算法的实际应用中，明文是应该妥善保管的，在没有给定明文而只有Hash值的情况下，是不会形成碰撞的。因此对于电子签名来说，MD5依旧是安全可靠的。
    (5) 文中的讨论仅仅是在寻求“碰撞”上的突破，任何文章、有意义的文献，它还隐含着逻辑和语义上的关系。比如有一个合同，做了数字签名，我们在二进制空间寻求它的一个有逻辑、语义的碰撞仍然是不可能的。
    (6) Hash函数算法通常与其他的密码技术混合使用，因此利用新发现的漏洞进行恶意的破坏还不太实际，即便是应用大量的计算能力也是如此。

综上所述，目前王教授的算法对于在实际应用中破解MD5算法尚无太大的帮助。不过她们的研究成果是若干年来密码学获得的重大突破，通过他们的研究，使密码研究者认识到对于MD5这样的算法，自身仍存在很大缺陷，未来的密码设计人员，要避开这些缺陷，设计出更强大，更安全，更保密的算法。

4 加强MD5加密算法在实际应用中的安全性的有效对策
    随着科学技术的不断进步，计算机性能和攻击技术水平随之不断提高，各种攻击技术的时间成本和设备成本也随之不断降低，因此对于各种加密技术而言，同时也应当不断提高其抗攻击能力。
    由于MD5加密算法是目前应用最为广泛的一个Hash函数，在其自身的完善和采用更强的加密算法之前，我们应当结合MD5加密算法的特点，从以下几个方面来着手来加强MD5算法的抗攻击能力：
    (1) 增加明文的长度。无论是特定碰撞还是非特定碰撞，明文长度的增加都可以使得碰撞的产生在时间上成几何倍数的增长，从而增加了攻击技术的时间成本和设备成本，相应的也就提高了加密技术的可靠性。
    (2) 复合使用加密算法。由于Hash函数同时具备单向性和快速性，因此加密算法的复合使用不会带来太多的开销，却可以使得从学术理论上降低攻击成本的方法更加难以形成，使得碰撞的产生更加困难，这是我们在具体编写应用程序时的一个行之有效的策略。
    (3) 混合使用多种密码技术。将多种密码技术混合使用同样可以大大增加实现成功攻击的成本。

5  总结
    密码学理论体系的不断前进和计算机性能的不断提高，使得采用暴力破解当今各种信息保密系统成为可能，信息安全体系面临着前所未有的严峻挑战，但同时又为我们构筑更加可靠的信息安全体系提供了有力保障。这是一对永恒的作用力与反作用力，它推动着人类密码学理论的不断前进。

参考文献：

[1] 王小云、冯登国、来学嘉、于红波，散列函数中的碰撞 http://www.cstc.net.cn/docs/docs.php?id=323；

[2] MD5加密算法的ASP实现，Sunrise_Chen， http://www.ccopus.com/code/MD5.asp；

[3] 卢开澄，计算机密码学,清华大学出版社；2001

[4] 加密算法之MD5算法，http://ntsafe.heut.edu.cn/list.asp?classid=44&articleid=445