MD5散列算法的研究

姜学军，曹 烨

(沈阳理工大学 信息科学与工程学院，辽宁 沈阳 110159)

随着计算机技术、网络通信技术的快速发展和日益广泛应用，人们对信息安全的要求也越来越高，密码技术作为信息安全的基石和核心，成为众多学者研究的重点。散列函数是密码学的重要分支，其中以MD5、SHA-1为代表的MDx系列散列算法[1]是最典型、应用最广泛的散列算法，它们在数字签名、身份认证、消息鉴别等领域有着重要的作用。当前计算机网络中使用的重要安全协议[2]，如SSL、PGP等都利用散列算法进行数字签名来保证信息在传递过程中的机密性和完整性，但由于散列算法本质上是一种“多对一”的函数，因此，从信息论的观点看其不可避免会发生碰撞[3]，从而严重威胁信息系统的安全，故对散列算法安全性的研究主要集中在其碰撞攻击方面。2004年王小云[4]利用差分攻击算法首次得到MD5碰撞消息对，2006年Yu Sasaki[5]给出了已知差分路径构造充分条件的算法，2009年Stevens[6]对算法进一步修正并优化了MD5碰撞算法的充要条件集。

本文提出一种改进的基于M.M.J.Stevens碰撞思路和算法的MD5算法，该算法针对传统算法[7]代码编写非常繁琐的缺点，重新编写了算法中的核心循环，使其更简洁，可读性更好。同时，由于产生碰撞的整个过程的核心代码采用DLL动态链接库进行封装，可以单独调用，也可以配合其他项目应用，从而解决了运行平台差异的问题，提高了系统的可移植性。

1 MD5算法

1.1 MD5算法原理[8]

MD5对报文分块计算，每块报文的长度为64字节，若最后一个分块不足64字节则必须进行填充，每一个分块又被划分成16个4字节的子块。MD5消息摘要的计算是一个累加过程，第n块报文摘要的计算要以第n-1块报文摘要为初始值，最后一块报文的摘要值即为整个报文的消息摘要。每块报文摘要的计算分为64步[9]，每一步计算都涉及与、或、非、异或、循环左移等逻辑运算，且每一步计算都与前一步相关。

1.2 传统算法与改良算法的比较

传统MD5算法循环部分采用64×1循环模式[10]，用C语言编写，尽管书写上非常繁琐，但由于该程序在编写中使用了C语言的预处理功能，且程序大部分采用内存直接寻址方式，所以在计算速度方面的优势无可与其相比。

论文中提出的改良MD5算法虽然在计算速度上无法与传统算法相比，但核心循环部分的代码在很大程度上得到简化，故可读性更强。该算法把MD5的4种循环分开，有针对地对公共循环代码进行提取、合并，实现了代码的复用。同时，由于产生碰撞的整个过程的核心代码采用DLL动态链接库进行封装，有助于多个应用程序共享数据和资源；不同功能的模块放在数个动态链接库中，无需重新生成或安装整个程序就可以应用更新在不同的运行平台，从而解决了运行平台差异的问题，提高了系统的可移植性。

1.3 改进的MD5算法

该算法使用Windows平台，应用程序开发环境Visual Studio 2010，支持.NET Framework4.0框架，采用C#语言编写代码。该算法重新编写了MD5算法中的核心循环，主要提供一对MD5碰撞产生的过程以及MD5碰撞的完成。改进的MD5算法循环部分使用4×16循环模式，具体实现如下：

UInt32[]IV=new UInt32[4];

this.MD5IV.CopyTo(IV,0);

for (inti=0;i<4;i++){

for (intj=16;j>0;j--){

MD5_STEP(i,ref IV[(j& 0x3)],IV[((j+1) & 0x3)],IV[((j+2) & 0x3)],IV[((j+3) & 0x3)],MM[m[i,16-j]],ti[(i<<4)-j+16],s[i,(16-j) & 0x3]);

}

}

this.MD5IV[0]+=IV[0];

this.MD5IV[1]+=IV[1];

this.MD5IV[2]+=IV[2];

this.MD5IV[3]+=IV[3];

该算法主循环位运算有4种，可以使用每一层循环变量i来标记当前处于哪一种循环。代码中使用的主方法MD5_STEP()如下:

void MD5_STEP(intk,ref UInt32a,UInt32b,UInt32c,UInt32d,UInt32m,UInt32ac,intrc) {

a+=f(k,b,c,d)+m+ac;

a=(a<> (32-rc))+b;

}

MD5_STEP()方法使用标记过的f()返回位运算结果,该算法的核心在于对数组IV的合理操作，并利用变量j来控制MD5_STEP()方法对MD5IV数组的影响，从而得到最终结果。

最后将计算MD5的方法封装成一个类，这样做的好处是，当需要使用MD5值的时候，不需要了解整个MD5的计算过程，只需对结果进行分析即可。其中MD5IV[4]存放a,b,c,d数据；length[8]为数据的长度，使用8个8位无符号字节保存；b_10[57]= {0x80,0,0……0}用来补位。在计算过程中由于涉及到多种数据类型，故对hash()函数进行了重载；同时计算所得结果是4个32位无符号整型数据且不以级联方式存在，故需要使用result()方法对结果数据进行返回处理。FFGGHHII()定义了主循环部分，其中采用了两套循环体，并使用预处理方式进行选择。hash()函数的重载如下:

public string hash(byte[]array)//对无符号字进行hash

public string hash(string s)//对字符串进行hash

public string hash(FileStream inputstream)//对文件进行hash

2 MD5碰撞的实现

2.1 开发环境和工具

1)硬件环境CPU：Inter Pentium (R) D CPU 3.42GHz；内存：3G；显卡：512M。

2)软件工具操作系统：Windows XP；软件开发平台：Visual Studio 2010，.NET Framework4.0；编程语言：C#，Visual Basic。

2.2 实验结果及分析

改进的MD5碰撞算法是根据王小云教授[11]提出的差分碰撞路径原理，修改随机产生的消息，并对消息进行强制性约束，并且算法还借鉴了Stevens[12]对碰撞路径的修改和补充，从而完善了算法。改进的碰撞算法运行结果如图1和图2所示。

图1 计算MD5值

图2 MD5碰撞结果

图1部分使用MD5计算工具集实现，其中MD5散列值的计算使用第2章介绍的自定义的MD5算法实现，SHA-1散列值的计算采用Security.Cryptography.SHA-1完成，之所以增加SHA-1的计算是因为在计算得到不同信息具有相同MD5值的同时，可以更直观地看出这两个文件是不同的报文；对于文件信息，如文件名、创建日期。最后修改日期都由fileinfo类完成；计算功能的实现用到了MD5类中的hash()方法并且重载了3次。

对图2的几点说明：

⑴通过两条原始报文的十六进制表示说明这是两条不同的信息(画圈部分表示两条报文共有6个不同之处)。

⑵经过计算得到这两条信息各自不同的SHA-1散列值也再次证明它们是不同的报文。

⑶通过FMD5类中的find_block()方法计算得到这两条不同报文各自的MD5散列值是相同的，均为4CA5AF5760883B5B07C955A93CEF9213，这表明使用改进的MD5散列算法已经找到了一对碰撞。

碰撞过程可以概括为：产生随机数，对随机数进行约束，验证随机数，如果符合所有条件，即得到一条差分路径，产生碰撞报文的前半部分，这是该算法的核心部分，因为数据限定的好坏直接决定了能否产生碰撞以及产生一对碰撞所需要的时间。然后进行验证，只有当所有条件都满足了，算法才会根据上述步骤寻找第二条差分路径，产生碰撞报文的后半部分。

在随机进行的50次实验中，每次实验找到一对碰撞信息所用时间均不多于60s，根据概率统计数据可以得出结论：利用改进的MD5碰撞算法实现一次信息碰撞所用时间不多于60s。

3 结束语

提出一种改进的MD5碰撞算法，与传统算法相比该算法在程序的可读性和可移植性方面有所改进，算法最后封装成DLL动态链接库，还可为日后应用到实际工程中提供便利。实验验证平均在60s内可以寻找到一对碰撞消息，通过对碰撞过程和碰撞结果的分析可以更好地研究MD5算法给密码学以及信息安全领域带来的安全隐患[13]。但该算法基于对运行环境和编程语言的要求，在程序运行速度和效率上还有待提高。

[1]毛明,秦志光,陈少晖.破译MD5算法关键技术研究[J].计算机应用,2009,(12):3174-3177.

[2]周荣华.散列函数密码分析的研究[D].武汉：华中科技大学,2006:51-54.

[3]张栋.密码学杂凑函数的碰撞性分析研究[D].西安：西安电子科技大学,2009:10-12.

[4]Xiaoyun Wang,Hongbo Yu.How to break MD5 and other hash functions[DB/OL].In EUROCRYPT,2005,http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf.

[5]Sasaki Y,Wang L.Security of MD5 Challenge and Response:Extension of APOP Password Recovery Attack[DB/OL].CT-RSA 2008,LNCS 4964:1-18.

[6]Stevens M,Sotirov A.Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate[DB/OL].Cryptology ePrint Archive,Report，2009.

[7]林蔚.MD5安全性分析[D].北京：北京邮电大学,2009:25-28.

[8]梁杰.MD5-Hash函数的安全性分析[D].上海：上海交通大学,2007:15-19.

[9]Bai H H.The Study of Quick MD5 Collision Algorithms[D].Zhejiang University，2010.

[10]Tao Xie,Fanbao Liu,Dengguo Feng.Could The 1-MSB Input Difference Be The Fastest Collision Attack For MD5[DB/OL].Cryptology ePrint Archive,Report 2008.http://eprint.iacr.org/.

[11]Xiaoyun Wang,Xuejia Lai,et al.Collisions for hash functions MD4,MD5,HAVAL-128 and RIPEMD[DB/OL].Cryptology ePrint Archive,Report 2004.http://eprint.iacr.org/2004/199.

[12]Marc Stevens,Arjen Lenstra,Benne de Weger.Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities[J].EUROCRYPT 2007,LNCS,Springer,2007,45(15):1-22.

[13]刘凡保,谢涛.MD5碰撞攻击的差分路径构建[C].第八届全国信息隐藏与多媒体安全学术大会湖南省计算机学会第十一届学术年会论文集,2009.