雜湊函數(shù)結(jié)構(gòu)研究現(xiàn)狀及新的結(jié)構(gòu)設(shè)計(jì).pdf

1、密碼雜湊函數(shù)是一類基礎(chǔ)密碼算法，在現(xiàn)代通信、金融、安全計(jì)算等許多領(lǐng)域有著極為廣泛的應(yīng)用。它可以用來提供數(shù)據(jù)完整性檢測如篡改檢測碼MDC，消息認(rèn)證碼MAC，不可否認(rèn)性如數(shù)字簽名等安全性質(zhì)，成為保障電子簽名、身份認(rèn)證等多種密碼系統(tǒng)安全的關(guān)鍵技術(shù)。
　　 雜湊函數(shù)設(shè)計(jì)方式通常有兩種，一種是使用成熟的分組密碼來構(gòu)造雜湊函數(shù)。如，串聯(lián)和并聯(lián)的Davies-Meyer結(jié)構(gòu)，以及MDC-2和MDC-4等。這類雜湊函數(shù)都是基于成熟的分組算法，它

2、們的運(yùn)行效率很低，在遇到海量數(shù)據(jù)時，這種雜湊函數(shù)便不能滿足應(yīng)用需求。這類雜湊函數(shù)的安全性分析主要側(cè)重于對結(jié)構(gòu)的分析。另一類是專用的安全高效的雜湊函數(shù)。1989年，Merkle[19]和Damg(a)rd[7]分別給出了利用輸入長度固定的壓縮函數(shù)構(gòu)造雜湊函數(shù)的方法，其目的是使雜湊函數(shù)的抗碰撞性等價于壓縮函數(shù)的抗碰撞性，這樣雜湊函數(shù)的設(shè)計(jì)就集中于固定長度的壓縮函數(shù)的設(shè)計(jì)，這種結(jié)構(gòu)稱為MD結(jié)構(gòu)。最具代表性的是MDx系列雜湊函數(shù)，這一系列雜湊函

3、數(shù)主要包括MD4，MD5，HAVA，SHA-0，SHA-1，SHA-2，RIPEMD-160等[26，27，22，23，24，37]。這些雜湊函數(shù)都是在MD4設(shè)計(jì)思想的基礎(chǔ)上，加入了新的設(shè)計(jì)理念，用以提高算法的安全性，統(tǒng)稱為MDx系列雜湊函數(shù)。直到2004年，MD5與SHA-1一直是計(jì)算機(jī)網(wǎng)絡(luò)世界普遍使用的兩大雜湊函數(shù)標(biāo)準(zhǔn)。
　　 對專用的雜湊函數(shù)的安全性分析，開始于1992年。在Eurocrypt1993上，Boer和Boss

4、e laers首次給出了MD5的一條偽碰撞路線[2]。在Eurocrypt1996上，Dobbertin給出了在非標(biāo)準(zhǔn)的初始值下MD5的碰撞攻擊實(shí)例[9]。同年，在FSE1996上，Dobbertin首次給出了MD4碰撞的有效攻擊[10]，這是MD系列的第一個理論攻擊，也是有效的實(shí)際攻擊。
　　 1997年王小云教授首次使用“比特追蹤法”來分析SHA-0，理論上破解了SHA-0[30]。第二年，她使用“消息修改”技術(shù)極大的改進(jìn)了

5、這一結(jié)果[31]。同年，在Crypto1998上，Chabaud和Joux使用差分分析技術(shù)給出了SHA-0的理論分析結(jié)果[5]。在Crypto2004上，王小云教授公布了MD4、MD5、HAVAL和RIPEMD的碰撞實(shí)例[32，34]，具體攻擊方法--比特追蹤法和及攻擊細(xì)節(jié)[33]等首次在Eurocrypt2005上發(fā)表，這也是破解包括MD5、SHA-1在內(nèi)的多數(shù)MDx系列雜湊函數(shù)的理論基礎(chǔ)。在Crypto2005上，王小云教授還公布了

6、SHA-1全算法的碰撞攻擊[35]。這些都說明當(dāng)前使用的MDx系列雜湊函數(shù)是不安全的。
　　 本文回顧了各種雜湊函數(shù)的結(jié)構(gòu)和對結(jié)構(gòu)的攻擊方法，尤其是針對MD結(jié)構(gòu)的攻擊方法。同時研究了近幾年新出現(xiàn)的HAIFA[1]，sponge結(jié)構(gòu)[3]，寬管道結(jié)構(gòu)[18]等，并概要的總結(jié)了這些新的結(jié)構(gòu)設(shè)計(jì)特點(diǎn)。在此基礎(chǔ)上提出雙管道結(jié)構(gòu)的加強(qiáng)版本一雙管道加強(qiáng)。
　　 早期的MD結(jié)構(gòu)由于其迭代的性質(zhì)而容易受到長度擴(kuò)展攻擊，二次碰撞攻擊等，M

7、erkle對MD進(jìn)行了改進(jìn)，對消息進(jìn)行填充時，加入了消息的長度信息，提出了加強(qiáng)的MD結(jié)構(gòu)。但即使MD迭代結(jié)構(gòu)使用的壓縮函數(shù)是抗碰撞的，這類雜湊函數(shù)仍然容易受到攻擊。自2004年以來，密碼學(xué)界對MD迭代結(jié)構(gòu)的分析取得了突破性的研究進(jìn)展。Joux在Crypto2004上，使用生日攻擊，給出了對MD結(jié)構(gòu)的雜湊函數(shù)的多碰撞攻擊[14]，產(chǎn)生2t-碰撞的復(fù)雜度為t-2n/2，優(yōu)于搜索攻擊。在Eurocrypt2005上，Kelsey和Schnei

8、er提出了構(gòu)造可擴(kuò)展的消息，對長消息進(jìn)行第二原像攻擊的方法[16]，并分別使用Dean的固定點(diǎn)方法[8]和借鑒Joux的方法[14]構(gòu)造了可擴(kuò)展的消息，對長消息的第二原像進(jìn)行了攻擊。在Eurocrypt2006上，Kelsey和Kohno提出了對一個相關(guān)的短消息進(jìn)行原像攻擊的方法[15]，即選擇目標(biāo)固定前綴的原像攻擊，在這個攻擊中，攻擊者通過預(yù)計(jì)算，成功構(gòu)造了一個鉆石結(jié)構(gòu)，并給出目標(biāo)雜湊值。然后對挑戰(zhàn)者給出的前綴，尋找聯(lián)接消息，將前綴與

9、鉆石結(jié)構(gòu)聯(lián)接起來，從而得到目標(biāo)雜湊值的原像。這種攻擊可以用來做預(yù)言攻擊。
　　 最初的雜湊函數(shù)設(shè)計(jì)并不要求其滿足抗長度擴(kuò)展攻擊，但是如果雜湊函數(shù)不能抵抗長度擴(kuò)展攻擊，那么使用這種雜湊函數(shù)構(gòu)造的消息認(rèn)證碼就面臨受到偽造的風(fēng)險。因此NIST在SHA-3標(biāo)準(zhǔn)算法的征集中增加了抗長度擴(kuò)展攻擊的安全屬性。
　　 國際密碼領(lǐng)域又出現(xiàn)了許多新的雜湊函數(shù)結(jié)構(gòu)，這些新的結(jié)構(gòu)都力圖避免遭受針對MD結(jié)構(gòu)的攻擊。Asiacrypt2005上，L

10、ucks提出的寬軌道設(shè)計(jì)方法[18]，通過加長壓縮函數(shù)的鏈接變量，進(jìn)行迭代，最后在輸出摘要時，將長的鏈接變量進(jìn)行截?cái)嗷蚴遣捎脡嚎s函數(shù)壓縮到需要的輸出長度。這種使用長的鏈接變量進(jìn)行迭代，使得找到內(nèi)部的多碰撞和進(jìn)行長消息的第二原像攻擊的復(fù)雜度超過攻擊理想的雜湊函數(shù)的復(fù)雜度而導(dǎo)致攻擊的失敗。2005年，Rivest提出了在壓縮消息時，加入“無平方因子”的數(shù)字標(biāo)簽的方法[28]，這樣可以破壞引起第二原像攻擊的迭代結(jié)構(gòu)，但當(dāng)數(shù)字標(biāo)簽出現(xiàn)重復(fù)時，就

11、不能防止Kelsey等的構(gòu)造可擴(kuò)展的消息的方法，因而不能抵抗長消息的第二原像攻擊。2007年，Biham等提出了HAIFA結(jié)構(gòu)[1]，在迭代過程中，增加了數(shù)字標(biāo)簽和隨機(jī)數(shù)。增加數(shù)字標(biāo)簽，就不能再容易的使用Dean的固定點(diǎn)方法。增加隨機(jī)數(shù)，使得離線預(yù)計(jì)算不再可行，從而可以防止對選擇目標(biāo)的固定前綴攻擊等離線攻擊方法，同時，使用HAIFA的雜湊函數(shù)構(gòu)建的數(shù)字簽名方案中，簽名者可以選擇隨機(jī)數(shù)，攻擊者必須要考慮隨機(jī)數(shù)的因素才能進(jìn)行攻擊，從而增強(qiáng)了

12、數(shù)字簽名方案的安全性。2007年，Bertoni等人提出了一種可證明安全的Sponge結(jié)構(gòu)[3]，當(dāng)?shù)幕舅惴ㄊ请S機(jī)置換時，Sponge是可證明安全的[4]，但多數(shù)基于Sponge結(jié)構(gòu)的雜湊算法，利用簡化的分組密碼算法和簡單的置換作為基本算法，因而不能達(dá)到理想的安全強(qiáng)度。
　　 最后，通過分析最近幾年新出現(xiàn)的這些雜湊函數(shù)結(jié)構(gòu)的特點(diǎn)，借鑒寬管道結(jié)構(gòu)中，通過加長內(nèi)部狀態(tài)，用來阻止敵手尋找內(nèi)部碰撞的這種特點(diǎn)，本文提出對雙管道的改進(jìn)