姜學(xué)軍，曹 燁

(沈陽理工大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽 110159)

隨著計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)通信技術(shù)的快速發(fā)展和日益廣泛應(yīng)用，人們對信息安全的要求也越來越高，密碼技術(shù)作為信息安全的基石和核心，成為眾多學(xué)者研究的重點(diǎn)。散列函數(shù)是密碼學(xué)的重要分支，其中以MD5、SHA-1為代表的MDx系列散列算法[1]是最典型、應(yīng)用最廣泛的散列算法，它們在數(shù)字簽名、身份認(rèn)證、消息鑒別等領(lǐng)域有著重要的作用。當(dāng)前計(jì)算機(jī)網(wǎng)絡(luò)中使用的重要安全協(xié)議[2]，如SSL、PGP等都利用散列算法進(jìn)行數(shù)字簽名來保證信息在傳遞過程中的機(jī)密性和完整性，但由于散列算法本質(zhì)上是一種“多對一”的函數(shù)，因此，從信息論的觀點(diǎn)看其不可避免會發(fā)生碰撞[3]，從而嚴(yán)重威脅信息系統(tǒng)的安全，故對散列算法安全性的研究主要集中在其碰撞攻擊方面。2004年王小云[4]利用差分攻擊算法首次得到MD5碰撞消息對，2006年Yu Sasaki[5]給出了已知差分路徑構(gòu)造充分條件的算法，2009年Stevens[6]對算法進(jìn)一步修正并優(yōu)化了MD5碰撞算法的充要條件集。

本文提出一種改進(jìn)的基于M.M.J.Stevens碰撞思路和算法的MD5算法，該算法針對傳統(tǒng)算法[7]代碼編寫非常繁瑣的缺點(diǎn)，重新編寫了算法中的核心循環(huán)，使其更簡潔，可讀性更好。同時(shí)，由于產(chǎn)生碰撞的整個(gè)過程的核心代碼采用DLL動(dòng)態(tài)鏈接庫進(jìn)行封裝，可以單獨(dú)調(diào)用，也可以配合其他項(xiàng)目應(yīng)用，從而解決了運(yùn)行平臺差異的問題，提高了系統(tǒng)的可移植性。

1 MD5算法

1.1 MD5算法原理[8]

MD5對報(bào)文分塊計(jì)算，每塊報(bào)文的長度為64字節(jié)，若最后一個(gè)分塊不足64字節(jié)則必須進(jìn)行填充，每一個(gè)分塊又被劃分成16個(gè)4字節(jié)的子塊。MD5消息摘要的計(jì)算是一個(gè)累加過程，第n塊報(bào)文摘要的計(jì)算要以第n-1塊報(bào)文摘要為初始值，最后一塊報(bào)文的摘要值即為整個(gè)報(bào)文的消息摘要。每塊報(bào)文摘要的計(jì)算分為64步[9]，每一步計(jì)算都涉及與、或、非、異或、循環(huán)左移等邏輯運(yùn)算，且每一步計(jì)算都與前一步相關(guān)。

1.2 傳統(tǒng)算法與改良算法的比較

傳統(tǒng)MD5算法循環(huán)部分采用64×1循環(huán)模式[10]，用C語言編寫，盡管書寫上非常繁瑣，但由于該程序在編寫中使用了C語言的預(yù)處理功能，且程序大部分采用內(nèi)存直接尋址方式，所以在計(jì)算速度方面的優(yōu)勢無可與其相比。

論文中提出的改良MD5算法雖然在計(jì)算速度上無法與傳統(tǒng)算法相比，但核心循環(huán)部分的代碼在很大程度上得到簡化，故可讀性更強(qiáng)。該算法把MD5的4種循環(huán)分開，有針對地對公共循環(huán)代碼進(jìn)行提取、合并，實(shí)現(xiàn)了代碼的復(fù)用。同時(shí)，由于產(chǎn)生碰撞的整個(gè)過程的核心代碼采用DLL動(dòng)態(tài)鏈接庫進(jìn)行封裝，有助于多個(gè)應(yīng)用程序共享數(shù)據(jù)和資源；不同功能的模塊放在數(shù)個(gè)動(dòng)態(tài)鏈接庫中，無需重新生成或安裝整個(gè)程序就可以應(yīng)用更新在不同的運(yùn)行平臺，從而解決了運(yùn)行平臺差異的問題，提高了系統(tǒng)的可移植性。

1.3 改進(jìn)的MD5算法

該算法使用Windows平臺，應(yīng)用程序開發(fā)環(huán)境Visual Studio 2010，支持.NET Framework4.0框架，采用C#語言編寫代碼。該算法重新編寫了MD5算法中的核心循環(huán)，主要提供一對MD5碰撞產(chǎn)生的過程以及MD5碰撞的完成。改進(jìn)的MD5算法循環(huán)部分使用4×16循環(huán)模式，具體實(shí)現(xiàn)如下：

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];

該算法主循環(huán)位運(yùn)算有4種，可以使用每一層循環(huán)變量i來標(biāo)記當(dāng)前處于哪一種循環(huán)。代碼中使用的主方法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()方法使用標(biāo)記過的f()返回位運(yùn)算結(jié)果,該算法的核心在于對數(shù)組IV的合理操作，并利用變量j來控制MD5_STEP()方法對MD5IV數(shù)組的影響，從而得到最終結(jié)果。

最后將計(jì)算MD5的方法封裝成一個(gè)類，這樣做的好處是，當(dāng)需要使用MD5值的時(shí)候，不需要了解整個(gè)MD5的計(jì)算過程，只需對結(jié)果進(jìn)行分析即可。其中MD5IV[4]存放a,b,c,d數(shù)據(jù)；length[8]為數(shù)據(jù)的長度，使用8個(gè)8位無符號字節(jié)保存；b_10[57]= {0x80,0,0……0}用來補(bǔ)位。在計(jì)算過程中由于涉及到多種數(shù)據(jù)類型，故對hash()函數(shù)進(jìn)行了重載；同時(shí)計(jì)算所得結(jié)果是4個(gè)32位無符號整型數(shù)據(jù)且不以級聯(lián)方式存在，故需要使用result()方法對結(jié)果數(shù)據(jù)進(jìn)行返回處理。FFGGHHII()定義了主循環(huán)部分，其中采用了兩套循環(huán)體，并使用預(yù)處理方式進(jìn)行選擇。hash()函數(shù)的重載如下:

public string hash(byte[]array)//對無符號字進(jìn)行hash

public string hash(string s)//對字符串進(jìn)行hash

public string hash(FileStream inputstream)//對文件進(jìn)行hash

2 MD5碰撞的實(shí)現(xiàn)

2.1 開發(fā)環(huán)境和工具

1)硬件環(huán)境CPU：Inter Pentium (R) D CPU 3.42GHz；內(nèi)存：3G；顯卡：512M。

2)軟件工具操作系統(tǒng)：Windows XP；軟件開發(fā)平臺：Visual Studio 2010，.NET Framework4.0；編程語言：C#，Visual Basic。

2.2 實(shí)驗(yàn)結(jié)果及分析

改進(jìn)的MD5碰撞算法是根據(jù)王小云教授[11]提出的差分碰撞路徑原理，修改隨機(jī)產(chǎn)生的消息，并對消息進(jìn)行強(qiáng)制性約束，并且算法還借鑒了Stevens[12]對碰撞路徑的修改和補(bǔ)充，從而完善了算法。改進(jìn)的碰撞算法運(yùn)行結(jié)果如圖1和圖2所示。

圖1 計(jì)算MD5值

圖2 MD5碰撞結(jié)果

圖1部分使用MD5計(jì)算工具集實(shí)現(xiàn)，其中MD5散列值的計(jì)算使用第2章介紹的自定義的MD5算法實(shí)現(xiàn)，SHA-1散列值的計(jì)算采用Security.Cryptography.SHA-1完成，之所以增加SHA-1的計(jì)算是因?yàn)樵谟?jì)算得到不同信息具有相同MD5值的同時(shí)，可以更直觀地看出這兩個(gè)文件是不同的報(bào)文；對于文件信息，如文件名、創(chuàng)建日期。最后修改日期都由fileinfo類完成；計(jì)算功能的實(shí)現(xiàn)用到了MD5類中的hash()方法并且重載了3次。

對圖2的幾點(diǎn)說明：

⑴通過兩條原始報(bào)文的十六進(jìn)制表示說明這是兩條不同的信息(畫圈部分表示兩條報(bào)文共有6個(gè)不同之處)。

⑵經(jīng)過計(jì)算得到這兩條信息各自不同的SHA-1散列值也再次證明它們是不同的報(bào)文。

⑶通過FMD5類中的find_block()方法計(jì)算得到這兩條不同報(bào)文各自的MD5散列值是相同的，均為4CA5AF5760883B5B07C955A93CEF9213，這表明使用改進(jìn)的MD5散列算法已經(jīng)找到了一對碰撞。

碰撞過程可以概括為：產(chǎn)生隨機(jī)數(shù)，對隨機(jī)數(shù)進(jìn)行約束，驗(yàn)證隨機(jī)數(shù)，如果符合所有條件，即得到一條差分路徑，產(chǎn)生碰撞報(bào)文的前半部分，這是該算法的核心部分，因?yàn)閿?shù)據(jù)限定的好壞直接決定了能否產(chǎn)生碰撞以及產(chǎn)生一對碰撞所需要的時(shí)間。然后進(jìn)行驗(yàn)證，只有當(dāng)所有條件都滿足了，算法才會根據(jù)上述步驟尋找第二條差分路徑，產(chǎn)生碰撞報(bào)文的后半部分。

在隨機(jī)進(jìn)行的50次實(shí)驗(yàn)中，每次實(shí)驗(yàn)找到一對碰撞信息所用時(shí)間均不多于60s，根據(jù)概率統(tǒng)計(jì)數(shù)據(jù)可以得出結(jié)論：利用改進(jìn)的MD5碰撞算法實(shí)現(xiàn)一次信息碰撞所用時(shí)間不多于60s。

3 結(jié)束語

提出一種改進(jìn)的MD5碰撞算法，與傳統(tǒng)算法相比該算法在程序的可讀性和可移植性方面有所改進(jìn)，算法最后封裝成DLL動(dòng)態(tài)鏈接庫，還可為日后應(yīng)用到實(shí)際工程中提供便利。實(shí)驗(yàn)驗(yàn)證平均在60s內(nèi)可以尋找到一對碰撞消息，通過對碰撞過程和碰撞結(jié)果的分析可以更好地研究MD5算法給密碼學(xué)以及信息安全領(lǐng)域帶來的安全隱患[13]。但該算法基于對運(yùn)行環(huán)境和編程語言的要求，在程序運(yùn)行速度和效率上還有待提高。

[1]毛明,秦志光,陳少暉.破譯MD5算法關(guān)鍵技術(shù)研究[J].計(jì)算機(jī)應(yīng)用,2009,(12):3174-3177.

[2]周榮華.散列函數(shù)密碼分析的研究[D].武漢：華中科技大學(xué),2006:51-54.

[3]張棟.密碼學(xué)雜湊函數(shù)的碰撞性分析研究[D].西安：西安電子科技大學(xué),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].北京：北京郵電大學(xué),2009:25-28.

[8]梁杰.MD5-Hash函數(shù)的安全性分析[D].上海：上海交通大學(xué),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碰撞攻擊的差分路徑構(gòu)建[C].第八屆全國信息隱藏與多媒體安全學(xué)術(shù)大會湖南省計(jì)算機(jī)學(xué)會第十一屆學(xué)術(shù)年會論文集,2009.