基于中間相遇的哈希函數(shù)原像攻擊.pdf

1、密碼哈希函數(shù)（簡稱哈希函數(shù)）是密碼學(xué)領(lǐng)域三大原語之一（其他兩個分別是加密算法與簽名算法），它在現(xiàn)代通信、金融以及安全計算等領(lǐng)域起著基礎(chǔ)作用。哈希函數(shù)的傳統(tǒng)而且重要的安全性質(zhì)是抗碰撞性、抗第二原像性與抗原像性。本文使用中間相遇方法對六個哈希函數(shù)MD4、Extended MD4、3輪HAVAL、SM3、DHA-256與SShash的抗第二原像性與抗原像性進行了分析。
　　MD4是由Ronald L.Rivest設(shè)計的在1990年CRY

2、PTO會議上提出的哈希函數(shù)，許多重要的哈希函數(shù)比如廣泛應(yīng)用的MD5、SHA-1與SHA-2的設(shè)計理念都是來源于MD4。MD4目前仍在被使用。我們提出了中間相遇原像攻擊MD4的復(fù)雜度計算公式，提出了多中性字部分固定技術(shù)并設(shè)計了自動化計算復(fù)雜度的算法，對Kazumaro Aoki等人在SAC2008會議上提出的一塊的MD4原像攻擊進行了改進，由原先的2107的時間復(fù)雜度改進為295。Extended MD4是MD4的256比特的擴展版本，我

3、們也應(yīng)用類似的方法對Yu Sasaki等人在ACISP2009會議提出的對Extended MD4偽原像與原像攻擊進行了改進，時間復(fù)雜度分別降低了225.2與212.6。這是目前最好的MD4與Extended MD4原像攻擊。一塊的原像攻擊沒有利用Merkle-Damg(a)rd性質(zhì)，它直接攻擊的是壓縮函數(shù)，這是令人興趣的地方。
　　HAVAL是鄭玉良等人在1992年AUSCRYPT會議上提出的哈希函數(shù)，包括3輪、4輪與5輪的版本

4、。我們組合了各種方法，對Yu Sasaki等人在ASIACRYPT2008會議中的對3輪的HAVAL的偽原像與原像攻擊進行了改進，相應(yīng)的時間復(fù)雜度由原先的2192與2225分別降低到2172與2209.6。
　　SM3是中國國家密碼管理局在2010年12月發(fā)布的國家標(biāo)準(zhǔn)哈希算法，總共64步，哈希輸出256位。我們提出了對30步的SM3的原像攻擊，這是對SM3抗原像性分析的第一個結(jié)果。
　　DHA-256是由Jesang Le

5、e等人在2005年11月由美國國家標(biāo)準(zhǔn)技術(shù)研究院主辦的密碼哈希算法的討論會上提出的哈希函數(shù)，總共64步，哈希輸出256位。我們分別提出了對一塊的27步的DHA-256與兩塊的35步的DHA-256的原像攻擊。這是對DHA-256的抗原像性進行分析的第一個結(jié)果。
　　SShash是由Somitra Kumar Sanadhya等人在ASIACCS2009會議上提出的哈希函數(shù)，包括SShash-256與SShash-512，分別包含6