SHA-256算法的安全性分析

何潤(rùn)民，馬 俊

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

SHA-256算法的安全性分析

何潤(rùn)民，馬 俊

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

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

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

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

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

1 SHA-256算法

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

1）初始化；

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

(7)給出。

5）每個(gè)分組的中間散列值的計(jì)算方法：

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

2 SHA-256的安全性分析

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

2.1 生日攻擊

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

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

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

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

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

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

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

生日攻擊步驟：

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

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

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

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

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

2.2 差分攻擊

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

3 結(jié) 論

用于消息唯一性和數(shù)據(jù)完整性驗(yàn)證的Hash函數(shù)，其安全性依賴(lài)于函數(shù)本身的屬性和對(duì)碰撞的抵抗。Hash函數(shù)的算法結(jié)構(gòu)特點(diǎn)和Hash值的長(zhǎng)度是決定函數(shù)抗碰撞性的主要因素，Hash值越長(zhǎng)，越能抵御生日攻擊。SHA-256有256比特Hash值，MD5和SHA-1分別有128和160比特的Hash值。因此，SHA-256比MD5和SHA-1能抵抗生日攻擊。通過(guò)對(duì)Chabaud-Joux攻擊SHA-256的分析，找到了SHA-256的一個(gè)部分碰撞，其復(fù)雜度為 266，但無(wú)法找到SHA-256的一個(gè)整體碰撞，因此，SHA-256也能抵御現(xiàn)有的差分攻擊。由此可見(jià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].北京:國(guó)防工業(yè)出版社,2008.

[5] 楊曉元,魏立線.計(jì)算機(jī)密碼學(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 稿件編號(hào)：201306052

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