哈希函數(shù)設(shè)計(jì)與分析.pdf

1、在現(xiàn)代密碼學(xué)中，哈希函數(shù)扮演著非常重要的角色。它不僅在安全通信中起著重要的作用，而且是許多密碼算法和協(xié)議的基本結(jié)構(gòu)模塊。密碼學(xué)哈希函數(shù)又被稱為單向散列函數(shù)，它可以將任意長(zhǎng)度的消息散列為固定長(zhǎng)度的哈希值。哈希值也被稱為消息摘要、數(shù)字指紋、密碼校驗(yàn)和、信息完整性檢驗(yàn)碼、操作檢驗(yàn)碼等。哈希函數(shù)能夠賦予每個(gè)消息唯一的“指紋”。例如，哈希值“607364dea1d44b43e9898437b6d7e223”可以看作是使用MD5算法給論文題目“Re

2、searchondesignandanalysisofcryotographichashfunctions”生成的“指紋”。如果對(duì)字符串進(jìn)行稍加改動(dòng)，即使只是一個(gè)字母，對(duì)應(yīng)的哈希值也會(huì)千差萬別。如字符串“researchondesignandanalysisofcryptographichashfunctions”的哈希值為“5cea4844e982080b258cf144853603ec”。 由于近年來對(duì)哈希函數(shù)的一系列成功攻

3、擊，美國國家標(biāo)準(zhǔn)與技術(shù)研究所(NIST)已正式面向全世界征集新的安全哈希函數(shù)標(biāo)準(zhǔn)。哈希函數(shù)的研究目前已成為密碼學(xué)一個(gè)最重要、最活躍、最富有挑戰(zhàn)性的研究領(lǐng)域。本文的研究工作正是在這一背景下展開的。本文的主要工作可分為兩類，一類是研究專門哈希函數(shù)的設(shè)計(jì)與安全性分析，另一類是對(duì)目標(biāo)碰撞穩(wěn)固(TCR)哈希函數(shù)的分析研究。所取得的研究成果如下： 1、針對(duì)MD4，給出了7條新的碰撞模差分路徑?？尚械牟罘致肪€是模差分攻擊的關(guān)鍵步驟。由于實(shí)際使

4、用的哈希函數(shù)都是基于MD4設(shè)計(jì)的，因此對(duì)MD4的深入分析對(duì)更好地分析這些哈希函數(shù)是非常必要的。此外，給定任意消息差分，給出了用計(jì)算機(jī)搜索MD4碰撞(含有指定消息差分)的算法思想，指出了進(jìn)一步研究的方向。 2、對(duì)NIST哈希標(biāo)準(zhǔn)征集的候選算法NaSHA進(jìn)行了攻擊分析，發(fā)現(xiàn)在NaSHA-384和NaSHA-512中的擬群運(yùn)算參數(shù)只依賴于部分狀態(tài)字；并且從消息字到狀態(tài)字的擴(kuò)散效果不是非常好，不同的比特之間沒有相互影響。利用這些發(fā)現(xiàn)，給

5、出了一個(gè)針對(duì)NaSHA-384和NaSHA-512的碰撞攻擊，攻擊復(fù)雜度為2128，遠(yuǎn)小于生日攻擊復(fù)雜度。該攻擊是目前對(duì)此哈希函數(shù)最有效的攻擊。 3、提出了一個(gè)新的迭代結(jié)構(gòu)，CMD迭代結(jié)構(gòu)。在深入分析MD迭代結(jié)構(gòu)及其它迭代結(jié)構(gòu)的設(shè)計(jì)合理性和攻擊方法后，對(duì)EMD結(jié)構(gòu)和MDP結(jié)構(gòu)進(jìn)行了分析，指出它們并不能提供比MD結(jié)構(gòu)更高的安全性。之后，提出了一個(gè)CMD迭代結(jié)構(gòu)，并證明了該結(jié)構(gòu)能夠保持壓縮函數(shù)的抗碰撞性。利用已知對(duì)MD迭代結(jié)構(gòu)的攻擊

6、方法，對(duì)CMD迭代結(jié)構(gòu)進(jìn)行了分析，結(jié)果表明CMD結(jié)構(gòu)能夠抵抗這些攻擊。 4、設(shè)計(jì)了一個(gè)快速抗碰撞的壓縮函數(shù)Crazy。Crazy的設(shè)計(jì)目標(biāo)是它的結(jié)構(gòu)需要能夠抵抗所有已知攻擊以及當(dāng)使用MD迭代結(jié)構(gòu)時(shí)，它的性能應(yīng)該優(yōu)于SHA-256。Crazy的主要特點(diǎn)是：(1)使用步函數(shù)來幫助消息擴(kuò)展；(2)初始值被用來輔助消息擴(kuò)展；(3)消息擴(kuò)展字在兩步之后影響所有的寄存器；(4)消息擴(kuò)展字不直接作用在任意一個(gè)寄存器上。利用已知的攻擊分析手段，

7、差分分析、線性近似、弱常量等對(duì)Crazy進(jìn)行了分析。除了實(shí)際的攻擊分析手段，還利用統(tǒng)計(jì)測(cè)試方法對(duì)Crazy進(jìn)行了統(tǒng)計(jì)測(cè)試。通過分析，可以認(rèn)為Crazy能夠抵抗目前已知的對(duì)壓縮函數(shù)的攻擊。此外使用MD迭代結(jié)構(gòu)，Crazy的軟件性能比SHA.256快50％。 5、對(duì)隨機(jī)構(gòu)造Hcr(M)=Hc(r｜Hc(M()r))進(jìn)行了深入地安全性歸約分析。給出了當(dāng)?shù)讓訅嚎s函數(shù)滿足何種性質(zhì)時(shí)，該構(gòu)造是TCR或者eTCR的，并和RMX算法進(jìn)行了對(duì)比分

8、析。結(jié)論是，對(duì)于TCR性質(zhì)，Hcr和RMX是等價(jià)的；而當(dāng)它們都是eTCR時(shí)，Hcr具有比RMX更高的安全性。此外，對(duì)隨機(jī)哈希在簽名中的應(yīng)用進(jìn)行了仔細(xì)分析。解決了當(dāng)簽名者不被消息提供者信任的簽名問題。通過改變隨機(jī)數(shù)的選取方式以及增加消息提供者的驗(yàn)證過程對(duì)使用隨機(jī)哈希的簽名算法進(jìn)行了改進(jìn)。改進(jìn)后的隨機(jī)哈希簽名算法可以不需要假定簽名者是誠實(shí)的，并且安全性不依賴于底層哈希函數(shù)的離線碰撞穩(wěn)固性。 6、利用改進(jìn)的隨機(jī)哈希簽名算法和百萬富翁問