SHA-256算法的安全性分析

何润民，马 俊

（陕西工业职业技术学院 基础部,陕西 咸阳 712000）

SHA-256算法的安全性分析

何润民，马 俊

（陕西工业职业技术学院 基础部,陕西 咸阳 712000）

现有算法MD5、SHA-1等的相继破译，严重威胁到SHA-256、SAH-384等算法的安全性。本文介绍了SHA-256的算法逻辑及压缩函数的构造，探讨了生日攻击碰撞阈值和攻击步骤，分析了SHA-256在生日攻击下的安全性。通过对Chabaud-Joux攻击SHA-256的分析，找到了一个部分碰撞，其复杂度为 ，却无法找到SHA-256的一个整体碰撞。所以，在抵抗生日攻击和抵御现有差分攻击方面，SHA-256比MD5和SHA-1等具有更高的安全性。

Hash 函数；SAH-256；生日攻击；差分攻击

单向Hash 函数（也称杂凑函数）是密码学和信息安全领域中的一个非常重要的基本算法，它把任意长的消息转化为较短的、固定长度的消息摘要的算法。

SHA 安全加密标准，是至今国际上使用最为广泛的较为安全的压缩算法之一，由美国NIST和NSA两个组织共同开发的，此算法于1993年5月11日被美国NIST和NSA设定为加密标准。为了提高Hash函数的安全性能，陆续发布了改进的Hash密码算法SHA-1、SHA-224、SHA-256、SHA-384及SHA-512[1]等。但随着2004年中国密码专家王小云教授研究小组宣布对MD5、SHA-1[2]等加密算法的破解，随着密码学研究的不断深入和计算机技术的快速发展，美国政府计划从2010年起不再使用SHA-1，全面推广使用SHA-256、SHA-384和SHA-512等加密算法。由此可见，为了适应更高的信息安全需要，今后几年人们对SHA-2系列的研究将更为积极深入。

1 SHA-256算法

SHA-256算法使用了一组6个逻辑函数及一组常数 Kt，采用512比特的消息块，每一个消息块xi分成16个32比特的字M0，M1，…, M15下面简要给出SHA-256值的计算过程。

1）初始化；

3）用每一轮的散列值的中间结果初始化8个工作变量A、B、C、D、E、F、G、H。初始定义由H0(0)～H7

(7)给出。

5）每个分组的中间散列值的计算方法：

算法中使用了6个逻辑函数：

2 SHA-256的安全性分析

Hash函数的安全性很大程度上取决于抗强碰撞的能力，即攻击者找出两个涓息M和 M'(M≠M'),使得H(M)=HM' 。因此，评价一个Hash函数的安全性，就是看攻击者在现有的条件下，是否能找到该函数的一对碰撞。目前已有的对Hash函数攻击的方法包括生日攻击、彩虹表攻击、差分攻击等 。下面主要讨论SHA-256在生日攻击和差分攻击下的安全性。

2.1 生日攻击

生日攻击是一种可用于攻击任何类型Hash函数的攻击方法。从攻击原理上看，它没有利用Hash函数的结构和任何代数弱性质，只依赖于Hash值的长度。因此，抵御生日攻击最有效的方法是Hash值必须有足够的长度。

2.1.1 生日攻击的知识基础

生日悖论表明：在任意抽取的k个人中，至少出现两个人生日相同的概率大于0.5时，k的最小值是多少？假定在365天中每个人生日出现的概率是相同的，那么两个人生日相同的概率为；

通过计算，当k=23时P(365,23)=0.507 3 ，即在任意抽取的23人中，可能有两个人生日相同的概率超过0.5，当k=100时，出现两个人生日相同的概率将超过0.999 997。通过计算可看出，当任意抽取的人数k确定时，出现至少有两个人生日相同的概率比想象的要大得多。

将生日悖论推广到Hash函数的碰撞攻击中，假设Hash函数的输出值均匀分布，消息摘要的位数为m比特，则Hash值有n=2m种可能的输出,任选k(k≤n)个随机输入，则至少有一个碰撞的概率为：

根据上面计算可知，如果Hash函数有m比特的输出摘要，那么只需进行k=2m/2次尝试，就会有一个碰撞产生的概率至少为50%。

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

生日攻击步骤：

发送方用私钥对256位的Hash值加密，并将加密结果附于消息之后一并提交给接收者，攻击者可按如下步骤实施攻击：

1）攻击者生成出消息M的2128种不同的消息变形，每一种消息变形都与原消息M具有相同的含义，同时攻击者再伪造一个假冒的消息M'，并对假冒的消息生成出 2128个不同消息，其目的是试图用假冒的消息替代真实消息。

2）比较上述两个集合，找出具有相同Hash值的一对消息Mi和M'j，依照生日悖论原理，攻击者找到碰撞的概率大于0.5。如果没找到，则重新伪造一个消息，并生成 2128个变形，直至找到碰撞为止。

3）攻击者将消息Mi（与伪造消息M'j有相同Hash值）提交给A请求签名，后将该签名连同伪造消息M'j一起发送给接收者。

表1 常用Hash函数的碰撞阈值Tab.1 Common threshold value of collision for the Hash function

2.2 差分攻击

差分攻击是目前破译迭代Hash函数最有效的手法之一，其基本方法是利用明文的输入差值对输出差值的影响，运用差分的高概率的继承或者消除来产生最终的相同输出。2004年以来，随着我国密码专家王小云利用差分攻击和明文修改技术对MD5、SHA-1等进行了破译，人们对SHA-256、SHA-384等的安全性研究将成为今后一个时期新的热点。2005年Biryukon和Yoshida从差分入手在34步以内找到了SHA-256的一个变种的伪碰撞 。2003年Handschuh和Gilbert 利用Chabaud-Joux 攻击，给出了SHA-256的一个9步迭代差分方法，理论上得到了SHA-256的一个部分碰撞，给出了部分碰撞复杂度为266[6-7]，并证明了SHA-256可抵御Chabaud-Joux攻击。以下是利用Chabaud-Joux对SHA-256实施攻击的描述：

3 结 论

用于消息唯一性和数据完整性验证的Hash函数，其安全性依赖于函数本身的属性和对碰撞的抵抗。Hash函数的算法结构特点和Hash值的长度是决定函数抗碰撞性的主要因素，Hash值越长，越能抵御生日攻击。SHA-256有256比特Hash值，MD5和SHA-1分别有128和160比特的Hash值。因此，SHA-256比MD5和SHA-1能抵抗生日攻击。通过对Chabaud-Joux攻击SHA-256的分析，找到了SHA-256的一个部分碰撞，其复杂度为 266，但无法找到SHA-256的一个整体碰撞，因此，SHA-256也能抵御现有的差分攻击。由此可见，在抵抗生日攻击和抵御已知差分攻击方面，SHA-256比现在广泛使用的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函数算法[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].北京:国防工业出版社,2008.

[5] 杨晓元,魏立线.计算机密码学[M].西安:西安交通大学出版社,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—)，男，陕西户县人，硕士，副教授。研究方向：密码理论与网路安全 。