對雜湊函數(shù)和分組密碼算法的分析.pdf

1、雜湊函數(shù)和分組密碼在很多密碼安全協(xié)議中起著非常重要的作用。雜湊函數(shù)最初是為了實現(xiàn)消息的完整性檢測和起源認證檢測等目的而提出的。當設計出有效且安全的雜湊函數(shù)算法之后，人們逐漸認識到若假設雜湊函數(shù)是“隨機的”(輸入和輸出獨立，各輸出之間獨立等)，雜湊函數(shù)可用于其它很多地方，例如：保護口令，構(gòu)造有效的數(shù)字簽名方案，構(gòu)造諸如認證協(xié)議，密鑰分配協(xié)議，比特承諾等協(xié)議，構(gòu)造加密算法等。分組算法主要用來保密消息，包括在廣播消息和儲存消息時的保密，其安全

2、性主要依賴于算法能抵抗各種攻擊。分組算法的分析主要考慮算法的安全性，密碼學家用各種分析技巧分析算法，用以評估其安全性。每個分析技巧都使用不同的模型，試圖發(fā)現(xiàn)算法某方面的設計漏洞。 隨著MD4系列雜湊函數(shù)的破解，對基于雜湊函數(shù)的分組密碼的分析逐漸成為熱點。SHACAL-1是基于雜湊函數(shù)SHA-1的分組密碼算法，其分組長度為160比特，它是NESSIE工程第二階段評估后勝出的算法之一。以前對SHACAL-1的分析結(jié)果。給出了對完整S

3、HACAL-1算法的相關(guān)密鑰矩形攻擊，該攻擊的數(shù)據(jù)復雜度是2159.8(或2153.8)個選擇明文，計算復雜度是2420.0(或2501.2)。適用于該攻擊的弱密鑰數(shù)占總密鑰數(shù)的1/214。SHACAL-2[39]是基于雜湊函數(shù)SHA-2的分組密碼算法，其分組長度為256比特，它是NESSIE工程最終勝出的算法之一。以前對SHACAL-2的分析結(jié)果參見[40，42，58]。本文的主要工作分為三部分： 1.對前兩輪RIPEMD-1

4、28算法的碰撞攻擊在第4章，利用模差分方法，給出了雜湊函數(shù)算法RIPEMD-128前兩輪的碰撞攻擊，找到前兩輪碰撞的計算復雜度是228。到目前為止，這是對RIPEMD-128算法分析的最好結(jié)果。攻擊RIPEMD-128的難度是相當大的，從設計者公開該算法至今，還未發(fā)表過對完整算法的攻擊文章，即使對縮減的前n(n＜64)步算法，在本文的分析結(jié)果之前，也沒有公開的分析結(jié)果。目前對RIPEMD-128算法唯一公開的分析結(jié)果，其中給出了RIPE

5、MD-128后三輪的碰撞攻擊路線，理論上使其碰撞概率為2-55。利用模差分方法，結(jié)合雜湊函數(shù)RIPEMD-128算法的特點，通過尋找前兩輪操作1和操作2的幾乎碰撞差分特征，找到了前兩輪(32步)算法的理論破解路線并給出了碰撞實例。 2.對SHACAL-1的分析在第5章，受到模差分方法中尋找局部碰撞路線的啟發(fā)，我們發(fā)現(xiàn)以前所有對分組算法SHACAL-1的分析都存在錯誤和不足。[57]的分析不能對所有的密鑰都成立，而只能針對滿足一定

6、條件的密鑰(弱密鑰)進行：[46]的分析使用的差分特征成立的概率是零，而不是如作者所說的非零(與隨機的相比有一定的優(yōu)勢)；[57]在分析過程中存在漏洞，把許多錯誤的密鑰誤認為是正確的，因為用它們解密和用正確的密鑰解密能得到同樣多的期望中的“正確對/正確四元組”。利用相關(guān)密鑰矩形攻擊方法，我們改進了對完整SHACAL-1算法的攻擊，適用于該攻擊的弱密鑰數(shù)占總密鑰數(shù)的1/256(而以前最好的攻擊中的弱密鑰的比例是1/214)，該攻擊的明文復

7、雜度是2146個選擇明文(或2144個選擇明文)，計算復雜度是2465次SHACAL-1加密運算(或2494)，需要約2150.33個字節(jié)存儲。該攻擊利用表7和表8的66-輪相關(guān)密鑰矩形差分特征。第一個差分特征(見表7)的輸入差分是α=([-8，1]，[3]，[3，-20]，[16，31]，213-210-26)，輸出差分是β=(e10,0，e5，e30，0，0)，差分特征成立的概率是2-35。第二個差分特征的輸入差分是，γ=(e1，e

8、1，0，e30,31，e31)，輸出差分是δ=(0，e3,0，0，e0)，差分特征成立的概率是2-36。第二個差分特征用到了一組弱密鑰，其個數(shù)占總密鑰個數(shù)的2-8，對這些弱密鑰，第二個差分特征成立的概率增加到2-28(=2-36.28)。通過固定9比特的明文值)，第一個差分特征成立的概率可以提高29倍，提高之后第一個差分特征成立的概率是2-35. 3.對SHACAL-2的分析在第6章，我們找到SHACAL-2的新的差分特征，結(jié)合

9、算法的一些性質(zhì)，改進了對43-輪SHACAL-2的相關(guān)密鑰矩形攻擊，該攻擊的明文復雜度是2240.38個選擇明文，計算復雜度是2480.4次43-輪SHACAL-2加密運算，需要約2245.38個字節(jié)存儲。該攻擊利用的差分特征基于[58]，我們的差分特征第0步的輸入-輸出差分是(0，eM，e31，0，e9,13,19，e18,29，e31，Δi，j)→(0，0，eM，e31，0，e9,13,19，e18,29，e31)其中91(E0⊕

10、e9,13,19)-g1(E0)+Δi，j=0。如果固定如表6.2所示的一些明文比特值，則第0步成立的概率是1。因為D2=Bo，H2=F0，根據(jù)加密算法以及條件B0,i=-F0,i(i=18，29)，第2步成立的概率增加到2-10。從[58]我們知道從第2步到第24步成立的概率是2-37，故第一個差分特征成立的概率是2-46。第二個差分特征成立的概率是2-63.38。故35-輪相關(guān)密鑰矩形差分特征成立的概率是2-474.76。根據(jù)泊阿松