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

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

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

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

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

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

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

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

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

9、算法的一些性質(zhì)，改進(jìn)了對(duì)43-輪SHACAL-2的相關(guān)密鑰矩形攻擊，該攻擊的明文復(fù)雜度是2240.38個(gè)選擇明文，計(jì)算復(fù)雜度是2480.4次43-輪SHACAL-2加密運(yùn)算，需要約2245.38個(gè)字節(jié)存儲(chǔ)。該攻擊利用的差分特征基于[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。因?yàn)镈2=Bo，H2=F0，根據(jù)加密算法以及條件B0,i=-F0,i(i=18，29)，第2步成立的概率增加到2-10。從[58]我們知道從第2步到第24步成立的概率是2-37，故第一個(gè)差分特征成立的概率是2-46。第二個(gè)差分特征成立的概率是2-63.38。故35-輪相關(guān)密鑰矩形差分特征成立的概率是2-474.76。根據(jù)泊阿松