周战军?程璐

摘 要：Hash函数，又称哈希函数、散列函数或杂凑函数，是密码体制中常用的一类公开函数。Hash函数主要用于消息完整性检测和消息认证等。由于MD-5、SHA-1等标准算法的安全性受到了严重的威胁，2012年10月，美国国家标准与技术研究所推选出Keccak为新的杂凑函数标准SHA-3的算法。本文主要对Keccak的竞选、实现过程、安全性以及攻击现状进行分析和研究。

关键词：Hash函数；Keccak；SHA-3

1 背景介绍

1.1 散列函数的安全威胁

随着对杂凑函数安全性分析不断深入，传统杂凑函数（MD4、 MD5、SHA-1、SHA-2等）安全性受到重大威胁。山东大学的王小云教授在美洲密码年会（Crypot2004）上做了攻击MD5、MD4、HAVAL-128和RIPEMD算法的报告，公布了MD系列算法的破解结果。对于MD5的攻击，报告中给出了一个具体的碰撞例子。MD5的安全性受到了严重的威胁。在安全强度要求较高的系统中，应避免MD5的使用。2005年2月，王小云教授等专家学者再次发表论文，证明SHA-1在理论上是可以破解的。虽然到目前为止，没有找到可攻破SHA-1算法的碰撞实例。但是，SHA-1算法甚至SHA-2算法的安全性都己经受到严重的威胁。

1.2 SHA-3计划与Keccak

NIST于2007年12月仿照AES的征集过程公开征集新的杂凑函数标准算法SHA-3。NIST提出的对候选算法的主要要求包括：（1）算法应该能够广泛地应用在常用的软件和硬件平台上安全高效地实现；（2）算法提供的消息摘要长度为：224比特、256比特、384比特和512比特，能够压缩的最大消息长度应至少为-1比特；（3）算法必须有效抵抗碰撞攻击、原象攻击及第二原象攻击、长度扩展攻击等常见的攻击方法，对于n比特长度的摘要，其碰撞攻击的复杂度应该至少为原象攻击至少为，对长度小于的消息其第二原象攻击复杂度应至少为；……