关于MD5摘要算法

发布:admin | 发布时间: 2010年2月21日

MD5的全称是Message-Digest algorithm 5（信息-摘要算法），MD5是一种不可逆的算法，即对生成的密文求逆，对应着无穷个逆。它是在MD4基础上发展而来的，由于MD4可以在几分钟内找到一个冲突，所以很快就被淘汰了。现在，对MD5安全性的问题越来越被重视，甚至有的人就认为：MD5将很快走入历史。那么，事实情况是否如此，MD5真的不安全了吗？
　　本文主要探讨几个容易对MD5产生误解的几个问题。
　　误区一：碰撞随时可能发生
　　如果对MD5摘要算法不了解，便误以为发现碰撞等同于破解，这种误解导致了很多人拼命地去寻找解密算法，最后只能无功而返。碰撞的发生是两个运动的过程，两个被改变的结果存在某种联系就是碰撞。MD5碰撞的发生主要是由于散列算法本身缺陷所导致的，并非MD5所独有，而MD5最大的好处应该是大大降低了这种碰撞被发现的几率和时间周期。只要拖延了足够的时间，MD5的价值也就得到了实现。问题是，随着计算机硬件技术的不断发展，这种靠时间延迟的摘要算法无法解决大大提高了的碰撞几率，也就使这种算法变得危险起来。
　　但是，碰撞的发生是需要一定条件，不是随意产生的，不是每一个MD5的散列都能找到或者很快地找到碰撞。密码学方面的专家对MD5产生碰撞的条件所做的的研究证明：使用循环左移和模2n减法运算等16个条件集可以得到碰撞的产生。不考虑是否有冗余条件的存在，但是可以说明，碰撞发生是需要非常严格的条件，不是随意就能出现的，而这些充要条件集需要充分的推算。鉴于此：想要找到MD5的碰撞并非那么容易。
　　误区二：更换算法结构不会被发现
　　MD5算法运算中，有4个32位整数参数的链接变量（Chaining Variable），他们分别为：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，有程序开发者认为更改这4个变量可以提高算法的安全性,也有人认为可以增加Hash 运算的轮数来达到破解的难度。这种对MD5本身算法规则作出变更的做法，副作用是显而易见的:1、经过运算的算法摘要可移植性大大降低，比如网站后台的会员密码很难再和其他程序或CMS进行整合；2、链接变量是一个稳定的参数，随便修改会导致算法的安全性和稳定性降低；3、算法结构的改变会导致程序代码运行的效率，势必增加运算的周期，不利于算法的推广的应用。
　　另外，从密码爆破角度来说，4个整形参数的调整只需要在爆破函数中把它们改成变量即可。设md5其它过程保持不变，若md5(A·B·C·D·x1)=y1, Δmd5(A′·B′·C′·D′·x1)=y2，y1为原散列，y2为修改参数链接变量的新散列值，那么，在破解程序的制作过程中，只需要让A′、B′、C′、D′用32位整形参数来逐个代替尝试即可，而且这个过程只需要成功运行一次，即可确定这四个被修改的新变量值。由此可见，更换算法结构不一定能使得算法更可靠。
　　误区三：散列值越长越安全
　　摘要算法（又称哈希算法、杂凑算法）最大的优点在于其不可逆性，但是最大缺点也正是由此而导致的散列值长度的固定性。那么，增加散列值的长度是否有助于增加算法的安全性呢？一般来说，MD5经过对原始数据经过一系列处理后会产生一个128位散列值，更安全的SHA算法则增加到了160位、256位。但是，在实际应用中，MD5只用到了32位或16位，SHA也只用到了40位或64位。有限的散列值引起的问题是，只要计算机的运算速度足够快，并发进程足够多，那么快速寻找碰撞值就不是难事，由于超级计算机运算碰撞的时间可以忽略不计，所以散列算法的长度更长并不能带来足够的安全。在大型的科研和国防安全中，这种算法的使用无疑是极其不安全的，即使面对日益强大的个人电脑，这种算法得到一个碰撞结果也只是个时间问题。
　　误区四：原始信息越复杂则输出散列越安全
　　由于碰撞现象的存在，尽管其碰撞产生非常严格，但是碰撞时存在的。在MD5算法运算过程中，一般人认为：被MD5处理的原始信息越复杂，那么原始信息就越安全。如前文所述，散列算法产生的散列指总数是有限的，那么原始值究竟有多少，只要找到其中一个原始值就宣告碰撞产生。例如：md5(x1)=md5(x2)=md5(x3)=……=Y，其中Y为散列值，则只需要得到其中一个碰撞原始信息值x1，那么x2 ，x3，……则毫无意义。所以，MD5原始信息的复杂程度对于安全程度没有多大影响，只是对于个人电脑爆破枚举得到碰撞有一定的拖延作用，对于高速多进程的超级计算机则不存在问题。
　　误区五：多重加密更安全
　　在MD5的实际应用中，很多人喜欢对算法进行多次引用，如在asp程序中，可以使用：md5(md5(x)), md5(md5(md5(x)))……等多次引用算法来提高安全性。这样做的后果是：势必导致程序循环次数增加，计算速度变慢，导致程序响应减缓，增加CPU负担等问题。从安全上来说，因为MD5是摘要算法，这种多重加密只是对一个固定散列加密。以广泛使用的32位的MD5算法为例，理论上出现的散列值共有3632=6.3×1049个散列值，只要有足够大的数据库来存放这些散列，那么无论引用多少次加密算法，都只是从这些数集中取值，MD5散列数组是固定不变的，这样一来，多重加密后的结果，其安全强度值得怀疑。
　　误区六：可以利用文件MD5值随意进行碰撞攻击
　　目前，已经有密码学家证明的碰撞的存在并能加以利用，使用的是“构造前缀碰撞法”（chosen-prefix collisions）来进行此次攻击，并且编写了“快速 MD5 碰撞生成器”，这样可以随意构造与已知文件完全不同但却MD5值相同的文件。那么这些文件是否就可以用来随意植入不安全信息并且构造出合法的可执行文件呢？一个可执行文件中包含文件头，BSS段，DATA段、TEXT段等信息，理论上是可以把一段恶意代码植入一个正常的EXE文件中的，但是植入后新文件还需要再构造才能形成一个与原文件MD5相同的新文件。除了构造过程复杂，文件的大小会也发生很大的变化，文件二进制的特征码也会产生变异，很容易被反攻击软件捕获拦截，最后的达到攻击的效果也就非常差或者达不到攻击的效果。
　　一般说来即使碰撞随意发生，不容易将需要的篡改文字或有害代码插入文件，从而不能达到伪造的目的，顶多是证明了碰撞的产生。当然由于指纹碰撞几率大大增加，MD5 算法不应再被用于任何软件完整性检查或代码签名的用途，但是这并非说明：文件碰撞的产生可以随意用于攻击破坏。
　　防止伪造MD5指纹应对策略：用MD5和SHA1以及长度计算多重验证
　　误区七：MD6算法一定会取代MD5算法
　　随着MD5安全性越来越受到质疑和挑战，MD5算法的作者又提出了MD6算法，其安全性似乎大大提高，但是这种算法仍然是对MD5算法的改良，只是在散列长度、算法规则做了某些微调，并未改变摘要算法的根本特性。另外，MD6算法尚处在试验阶段，并无法完全用于实际应用， MD6取代MD5还是个未知数。考虑到效率、易移植性、兼容性等因素，MD6被广泛普及还需要很长时间。当然，我们期待有更好更强更安全的摘要算法出现。
　　从MD5方面来说，在实际的安全应用中，同等于MD5（A）= MD5（B）的A、B值几率较小，即使能够建立囊括所有32位MD5散列值6.3×1049行的数据库，要想找到所有其对应的任意一个原始信息则非常困难。
　　小结:MD5摘要算法虽然存在很多局限性，但是在很多重要领域还是可以放心应用。摘要算法加密不可逆、结果简单、易于存储、易于移植等特性，在信息指纹识别、水印认证、程序信息注册、网站账户存储等领域还是有很大的前景，甚至可以结合其他安全策略联合应用，不必一味担心MD5安全性随时受到威胁。