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

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

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

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

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

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

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

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

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