何潤民，馬 俊

（陜西工業(yè)職業(yè)技術(shù)學(xué)院 基礎(chǔ)部,陜西 咸陽 712000）

SHA-256算法的安全性分析

何潤民，馬 俊

（陜西工業(yè)職業(yè)技術(shù)學(xué)院 基礎(chǔ)部,陜西 咸陽 712000）

現(xiàn)有算法MD5、SHA-1等的相繼破譯，嚴重威脅到SHA-256、SAH-384等算法的安全性。本文介紹了SHA-256的算法邏輯及壓縮函數(shù)的構(gòu)造，探討了生日攻擊碰撞閾值和攻擊步驟，分析了SHA-256在生日攻擊下的安全性。通過對Chabaud-Joux攻擊SHA-256的分析，找到了一個部分碰撞，其復(fù)雜度為 ，卻無法找到SHA-256的一個整體碰撞。所以，在抵抗生日攻擊和抵御現(xiàn)有差分攻擊方面，SHA-256比MD5和SHA-1等具有更高的安全性。

Hash 函數(shù)；SAH-256；生日攻擊；差分攻擊

單向Hash 函數(shù)（也稱雜湊函數(shù)）是密碼學(xué)和信息安全領(lǐng)域中的一個非常重要的基本算法，它把任意長的消息轉(zhuǎn)化為較短的、固定長度的消息摘要的算法。

SHA 安全加密標準，是至今國際上使用最為廣泛的較為安全的壓縮算法之一，由美國NIST和NSA兩個組織共同開發(fā)的，此算法于1993年5月11日被美國NIST和NSA設(shè)定為加密標準。為了提高Hash函數(shù)的安全性能，陸續(xù)發(fā)布了改進的Hash密碼算法SHA-1、SHA-224、SHA-256、SHA-384及SHA-512[1]等。但隨著2004年中國密碼專家王小云教授研究小組宣布對MD5、SHA-1[2]等加密算法的破解，隨著密碼學(xué)研究的不斷深入和計算機技術(shù)的快速發(fā)展，美國政府計劃從2010年起不再使用SHA-1，全面推廣使用SHA-256、SHA-384和SHA-512等加密算法。由此可見，為了適應(yīng)更高的信息安全需要，今后幾年人們對SHA-2系列的研究將更為積極深入。

1 SHA-256算法

SHA-256算法使用了一組6個邏輯函數(shù)及一組常數(shù) Kt，采用512比特的消息塊，每一個消息塊xi分成16個32比特的字M0，M1，…, M15下面簡要給出SHA-256值的計算過程。

1）初始化；

3）用每一輪的散列值的中間結(jié)果初始化8個工作變量A、B、C、D、E、F、G、H。初始定義由H0(0)～H7

(7)給出。

5）每個分組的中間散列值的計算方法：

算法中使用了6個邏輯函數(shù)：

2 SHA-256的安全性分析

Hash函數(shù)的安全性很大程度上取決于抗強碰撞的能力，即攻擊者找出兩個涓息M和 M'(M≠M'),使得H(M)=HM' 。因此，評價一個Hash函數(shù)的安全性，就是看攻擊者在現(xiàn)有的條件下，是否能找到該函數(shù)的一對碰撞。目前已有的對Hash函數(shù)攻擊的方法包括生日攻擊、彩虹表攻擊、差分攻擊等 。下面主要討論SHA-256在生日攻擊和差分攻擊下的安全性。

2.1 生日攻擊

生日攻擊是一種可用于攻擊任何類型Hash函數(shù)的攻擊方法。從攻擊原理上看，它沒有利用Hash函數(shù)的結(jié)構(gòu)和任何代數(shù)弱性質(zhì)，只依賴于Hash值的長度。因此，抵御生日攻擊最有效的方法是Hash值必須有足夠的長度。

2.1.1 生日攻擊的知識基礎(chǔ)

生日悖論表明：在任意抽取的k個人中，至少出現(xiàn)兩個人生日相同的概率大于0.5時，k的最小值是多少？假定在365天中每個人生日出現(xiàn)的概率是相同的，那么兩個人生日相同的概率為；

通過計算，當(dāng)k=23時P(365,23)=0.507 3 ，即在任意抽取的23人中，可能有兩個人生日相同的概率超過0.5，當(dāng)k=100時，出現(xiàn)兩個人生日相同的概率將超過0.999 997。通過計算可看出，當(dāng)任意抽取的人數(shù)k確定時，出現(xiàn)至少有兩個人生日相同的概率比想象的要大得多。

將生日悖論推廣到Hash函數(shù)的碰撞攻擊中，假設(shè)Hash函數(shù)的輸出值均勻分布，消息摘要的位數(shù)為m比特，則Hash值有n=2m種可能的輸出,任選k(k≤n)個隨機輸入，則至少有一個碰撞的概率為：

根據(jù)上面計算可知，如果Hash函數(shù)有m比特的輸出摘要，那么只需進行k=2m/2次嘗試，就會有一個碰撞產(chǎn)生的概率至少為50%。

2.1.2 SHA-256在生日攻擊下的安全性

生日攻擊步驟：

發(fā)送方用私鑰對256位的Hash值加密，并將加密結(jié)果附于消息之后一并提交給接收者，攻擊者可按如下步驟實施攻擊：

1）攻擊者生成出消息M的2128種不同的消息變形，每一種消息變形都與原消息M具有相同的含義，同時攻擊者再偽造一個假冒的消息M'，并對假冒的消息生成出 2128個不同消息，其目的是試圖用假冒的消息替代真實消息。

2）比較上述兩個集合，找出具有相同Hash值的一對消息Mi和M'j，依照生日悖論原理，攻擊者找到碰撞的概率大于0.5。如果沒找到，則重新偽造一個消息，并生成 2128個變形，直至找到碰撞為止。

3）攻擊者將消息Mi（與偽造消息M'j有相同Hash值）提交給A請求簽名，后將該簽名連同偽造消息M'j一起發(fā)送給接收者。

表1 常用Hash函數(shù)的碰撞閾值Tab.1 Common threshold value of collision for the Hash function

2.2 差分攻擊

差分攻擊是目前破譯迭代Hash函數(shù)最有效的手法之一，其基本方法是利用明文的輸入差值對輸出差值的影響，運用差分的高概率的繼承或者消除來產(chǎn)生最終的相同輸出。2004年以來，隨著我國密碼專家王小云利用差分攻擊和明文修改技術(shù)對MD5、SHA-1等進行了破譯，人們對SHA-256、SHA-384等的安全性研究將成為今后一個時期新的熱點。2005年Biryukon和Yoshida從差分入手在34步以內(nèi)找到了SHA-256的一個變種的偽碰撞 。2003年Handschuh和Gilbert 利用Chabaud-Joux 攻擊，給出了SHA-256的一個9步迭代差分方法，理論上得到了SHA-256的一個部分碰撞，給出了部分碰撞復(fù)雜度為266[6-7]，并證明了SHA-256可抵御Chabaud-Joux攻擊。以下是利用Chabaud-Joux對SHA-256實施攻擊的描述：

3 結(jié) 論

用于消息唯一性和數(shù)據(jù)完整性驗證的Hash函數(shù)，其安全性依賴于函數(shù)本身的屬性和對碰撞的抵抗。Hash函數(shù)的算法結(jié)構(gòu)特點和Hash值的長度是決定函數(shù)抗碰撞性的主要因素，Hash值越長，越能抵御生日攻擊。SHA-256有256比特Hash值，MD5和SHA-1分別有128和160比特的Hash值。因此，SHA-256比MD5和SHA-1能抵抗生日攻擊。通過對Chabaud-Joux攻擊SHA-256的分析，找到了SHA-256的一個部分碰撞，其復(fù)雜度為 266，但無法找到SHA-256的一個整體碰撞，因此，SHA-256也能抵御現(xiàn)有的差分攻擊。由此可見，在抵抗生日攻擊和抵御已知差分攻擊方面，SHA-256比現(xiàn)在廣泛使用的MD5和SHA-1等更具安全性。

[1] FIPS 180-1.Secure hash standard[S].NIST,US Department of Commerce.Washington D C:Springer-Verlag,1996.

[2] Hsu W H,Tung M C,W u L Y.An integrated end to-end QoS anycast routing on DiffServ net works[J].Computer Commun cations.2007,30(6):1406-1418.

[3] 葛輝.一種256位hash函數(shù)算法[J].大眾科技,2005,5 (57):107-108.

GE Hui. A kind of 256 bit Hash function algorithm[J].Popular Science & Technology, 2005,5(57):107-108.

[4] 黃月江,祝世雄.信息安全與保密[M].北京:國防工業(yè)出版社,2008.

[5] 楊曉元,魏立線.計算機密碼學(xué)[M].西安:西安交通大學(xué)出版社,2007.

[6] GLBERT H，HANDSCHUH H.Security analys is of SHA-256 and sisters [C] // Selected Areas in Cryptography'03, Lecture Notes inComputer Science,2003,(3006):175-193.

[7] Chabaud F,Joux A,Differential collisions in SHA -0[C] // Advances in Crypyology-CRYPYO'98,Lecture Notes in com puter Science,1998,(1462):56-71.

[8] YOSH DA H,BRYUKOV A. Analysis of a SHA-256 variant [C]//Selected Areas in Cryptography (SAC2005),Kingston On tario,2005:245-260.

Analysis safety of SHA-256 algorithm

HE Run-min, MA Jun
（Department of Basic,Shaanxi Polytechnic Insitiute, Xianyang ,712000,China）

Existing algorithms MD5, SHA-1 etc. have been deciphered,itis a serious threat to the SHA-256, SAH-384 algorithms such as security. This article describes the SHA-256 algorithm logic and structure of the compression function, explores the collision threshold birthday attack and attack procedures, and analyzesthe security of SHA-256 in birthday attack security.After analysis Chabaud-Joux attack by the SHA-256 analysis,that it find a part of the collision, its complexity is , but it could not find a whole SHA-256 collisions. So, in the resistance birthday attack and defend against the existing differential attacks, so SHA-256 has higher security than MD5 、SHA-1 and so on.

Hash function; SAH-256; birthday attack; differential attack

TN701

A

1674-6236(2014)03-0031-03

2013–06–08 稿件編號：201306052

何潤民(1961—)，男，陜西戶縣人，碩士，副教授。研究方向：密碼理論與網(wǎng)路安全 。