SHA―3计划候选算法的安全策略剖析

SHA―3计划候选算法的安全策略剖析摘要：Hash函数是将任意长度的消息变换成为固定长度的摘要，在实现数据的消息认证、完整性检验、数字签名等领域有着十分重要的应用。本文对美国标准技术研究所（NIST）征集哈希函数的SHA-3计划进行了全面介绍，分析了SHA-3计划中最终5个候选算法的设计思想与策略，并对5个算法的安全性分析结果与SHA-2算法进行了简要比较。关键词：Hash函数；SHA-3；迭代结构1引言随着现代社会进入信息时代，战争的形式发生了根本性的变化。掌握信息的主动权就是获取胜利的保证。在军事领域，信息的争夺称为信息战，在作战时，战斗的双方都企图通过控制信息和情报的流动来把握战场的主动权，在情报的支持下，综合运用军事欺骗、作战保密、电子战和对敌信息系统的实体摧毁，阻断敌方信息流，并制造虚假信息来影响和削弱敌情报控制能力，同时确保自己的指挥控制系统免遭敌方类似的破坏。由此可知，信息的传输、变换、压缩和存储等信息处理的有效性、可靠性和安全性已成为当今信息处理中急待解决的重要问题，而各种形式的编码和密码则是解决上述问题的基本理论与方法。就保密通信而言，信息在从采集、处理、传输到最终应用的整个过程中，面临着被偷窃、截收、窜收、插入、删除、中断等多种安全威胁。信息安全技术是维护信息保密性、完整性和可靠性的重要手段，它包括保护信息免受非法修改、破坏和泄露的所有措施。密码技术是信息安全技术的核心，而密码技术中的数字签名技术可以有效保护信息的完整性和可靠性。在数字签名中，一个重要工具便是Hash函数。Hash函数被广泛用于消息的完整性检测和消息认证。2Hash函数的概念与SHA-3计划一个Hash函数：将任意长的消息映射到固定长的比特串。为简便叙述，做如下定义：k比特长消息块；表示消息与级联，表示消息的比特长度；消息表示填充的消息（），压缩函数：将定长消息块压缩到定长hash值。近几年来，Hash函数的密码分析已经取得了突破性的进展.在通行的世界Hash函数标准MD5和SHA-1君临天下很长的时间内，它曾被认为是非常安全的.然而，中国学者王小云找到了破解Hash函数的关键技术，成功地破解了MD5、SHA-1和其他几个Hash函数，震惊了世界[1][2]。这些研究成果一方面使人震惊，另一方面也促进了人们对Hash函数的更深入的研究[3]。基于王小云及其团队对MD5和SHA系列函数的分析结果，美国NIST从2008年起开始在全世界范围内征集新的Hash函数标准，这个计划被称为SHA-3计划[4]，在新标准确立之前，由SHA-2作为代替算法。SHA-3计划中，候选算法需要满足下列四个条件，否则将被淘汰：算法容易实现，占用资源少；算法能够抵抗已知的攻击，并且支持224bit、256bit、384bit和512bit四种长度的散列。算法必须接受来自于密码学界的分析，在分析过程中发现的任何缺陷要调整或者重新设计。算法不能使用Merkle-Damgard结构。2008年10月有64个算法正式向SHA-3提交了方案。经过初步评价，共有51个算法进入第一轮评估，算法通过对安全、消耗、和算法实现特点，特别是对算法的分析，2009年7月，只有14个算法进入了第二轮评估，2010年11月，NIST公布了进入第三轮的5个算法：JH算法[5]、Grstl算法[6]、Blake算法[7]、Keccak算法[8]和Skein算法[9]。经过密码学界的分析和测试，2012年10月，美国NIST选择了Keccak算法作为SHA-3的标准算法。3SHA-3计划候选算法的设计策略分析Hash函数的设计通常采用迭代结构，其迭代函数的设计又借鉴了很多分组密码的思想。JH算法采用了新的压缩函数结构，其核心压缩函数就是一个分组密码，该分组密码的设计与美国高级加密标准AES类似，通过固定密钥对消息加密，并将部分消息反馈以达到消息压缩的目的；Grstl算法压缩函数通过两个不同的分组密码来构造，而这两个分组密码又采用了与AES算法相同的S盒，如果假设这两个分组密码是理想分组密码，则可以给出Grstl算法的安全性证明；Blake算法采用了HAIFA迭代结构，只采用了模加、异或和循环移位等逻辑运算；Keccak算法Sponge结构，压缩函数基于模加、异或和循环移位构造；Skein算法其核心压缩函数为Threefish，也是只利用模加、异或和循环移位等逻辑运算来实现数据的混淆与扩散。这些Hash函数的压缩函数都可以单独作为分组密码来使用，而在这些算法中，JH和Grstl采用了“宽轨迹策略”来设计分组密码；Blake、Keccak和Skein都采用了模加、异或和循环移位来设计分组密码。实际上，MD5、SHA系列函数的压缩函数也可以看做是一个分组密码，但是这些分组密码没有明显的扩散层，因此密码分析者可以很容易地控制单个比特或少数几个比特的差分传播，从而得到碰撞或近似碰撞；与MD5、SHA系列Hash函数不同，JH等SHA3候选算法都采用了明显的扩散层，使得比特追踪法很难适用于这类Hash函数的安全性分析。对Hash函数的安全性分析主要包含两个方面：一是抗碰撞攻击的能力评估，二是抗原像攻击的能力评估。所谓碰撞攻击是指找到两个不同的消息，使得两个Hash值相同。在实际研究某个Hash函数抗碰撞攻击时，密码学者们提出了一些适当变形和推广，如伪碰撞攻击、近似碰撞和多碰撞攻击等。研究碰撞攻击最有效的方法是差分密码分析，通过研究算法的差分传播特性，当输出差分为0时，碰撞即可产生。早期对Hash函数的碰撞攻击都属于经典差分分析的范畴，如Biham等正是利用经典差分分析方法寻找到SHA0的碰撞和近似碰撞的；王小云教授对MD5等Hash函数的攻击方法称作“比特追踪法”，属于差分攻击的范畴，通过在输入明文出引入很少几个比特的差分，研究这些差分传播特性，结合“明文修改”技术，可以使得只有很少几个比特不同的两组消息具有相同的Hash值。与分组密码一样，能够抵抗经典差分密码分析并不能保证Hash函数能够抵抗其他类型的差分密码分析。对MD和SHA系列Hash函数的碰撞攻击，更多地体现了如何在“消息差分”、“链变量差分特征”、“消息块自由度”和“优化算法”取得一种有效的均衡，使得攻击变得可行，见下图。由于新的Hash函数的设计采用了新的设计理念，扩散层的扩散能力明显增强，因此“比特追踪法”很难对SHA-3候选算法形成威胁。对SHA-3计划进入第三轮的5个算法的攻击结果见下表所示。4总结本文对美国NIST征集哈希函数的SHA-3计划进行了全面介绍，分析了SHA-3计划中最终5个候选算法的设计思想与策略，并对5个算法的安全性分析结果与SHA-2算法进行了简要比较。参考文献[1]Wang，X.，Yu，H.：HowtobreakMD5andotherhashfunctions.EUROCRYPT2005.LNCS，vol.3494，pp.19?C35.Springer，Heidelberg（2005）[2]Wang，X.，Yin，Y.L.，Yu，H.：FindingCollisionsintheFullSHA-1.In：Shoup，V.（ed.）CRYPTO2005.LNCS，vol.3621，pp.17?C36.Springer，Heidelberg（2005）[3]YuSasakiandKazumaroAoki，FindingPreimagesinFullMD5FasterThanExhaustiveSearch，A.Joux（Ed.）：EUROCRYPT2009，LNCS5479，pp.134?C152，2009.[4]NationalInstituteofStandardsandTechnology.AnnouncingRequestforCandidateAlgorithmNominationsforaNewCryptographicHashAlgorithm（SHA?C3）Family72（212）ofFederalRegister（November2007）[5]H.Wu，“TheHashFunctionJH，”SubmissiontoNIST（Round3），2011，http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html[6]P.Gauravaram，L.R.Knudsen，K.Matusiewicz，F.Mendel，C.Rechberger，M.Schl?ffer，S.Thomsen，“Gr?stlASHA-3Candidate，”SubmissiontoNIST（Round3），2011，http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html[7]J.-P.Aumasson，L.Henzen，W.Meier，R.C.-W.Phan，“SHA-3proposalBLAKE，”SubmissiontoNIST（Round3），2011，http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html[8]G.Bertoni，J.Daemen，M.Peeters，G.V.Assche，“KeccakSpecifications，”SubmissiontoNIST（Round3），2011，http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html[9]N.Ferguson，S.Lucks，B.Schneier，D.Whiting，M.Bellare，T.Kohno，J.Callas，J.Walker，“TheSkeinHashFunctionFamily，”SubmissiontoNIST（Round3），2011，http：//csrc.nist.gov/groups/ST/hash/sha-3/Round3/submissions_rnd3.html