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

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

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

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

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

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