摘 要：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等）安全性受到重大威胁。山东大学的王小云教授在美洲密码年会（Crypot’2004）上做了攻击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比特长度的摘要，其碰撞攻击的复杂度应该至少为原象攻击至少为，对长度小于的消息其第二原象攻击复杂度应至少为；（4）算法要能支持PRF、 HMAC和随机化； （5）算法在保持SHA-2的一些性能参数等性质外，要能够确保替换SHA-2参与具体应用；（6）算法的设计要简单灵活，能够通过并行实现获得较高的效率和更好的性能；（7）算法有安全的可调节的参数，可以调和运行性能及安全强度和；（8）算法可以使用新的迭代结构，，尽量避免老式结构（如MD结构）的通用攻击。

2007年，NIST在全球范围内公开征集SHA-3算法标准。2008年10月提交结束，共收到64个算法，其中有51个算法通过审查作为第一轮的候选算法。2009年7月，在第一轮的51个算法中有14个算法通过筛选进入了第二轮。2010年12月，NIST宣布通过最后一轮的5个算法，分别是Keccak、JH、Skein、Grstl和BLAKE。2012年10月2日，NIST公布了SHA-3标准算法。经过三轮的筛选，最终选定Keccak成为SHA-3的标准算法。NIST的安全专家说，Keccak的优势在于它与SHA-2设计上存在极大差异，使用于SHA-2的攻击方法将对无效。

2 Keccak算法介绍

2.1 Sponge结构简介

Keccak在迭代结构上采用的是Sponge结构。Sponge结构与传统的MD迭代结构很不同，依赖一个固定长度的大置换。这就为算法提供了良好的实用性和可证明安全性，理论上可以证明在理想模型下该结构与随机预言是不可区分的。Sponge结构是针对一个固定置换f的迭代过程。置换输入/输出的二进制串称为状态，其长度b=r+c，其中r称比特率，与输入消息块长度相同，该部分比特称为外部状态；c称容量，该部分比特称为内部状态。算法的初始时状态为全零。

Keccak算法的Sponge结构

如图所示，Sponge结构分成吸收（abstracting）和挤压（squeezing）两个阶段。在吸收阶段，输入消息经过填充，分为长度为r的各块p0，…，pi，…，pm，每块分别与各次置换的输入状态的r长外部状态异或，而c长内部状态保持不变，形成作为本次置换f的输入。在挤压阶段，根据所需的输出长度，从各次置换的输出中分别提取z0，…，zi各子串，连接后形成算法之输出。Sponge结构可以产生任意长度输出。

2.2 Keccak算法分析

按照NIST的要求，算法的输出长度分为224bit、256bit、384bit和512bit 。由于Sponge结构是可以产生任意长度输出的，所以Keccak算法的消息块长度r是根据输出长度而变化的： 输出512bit时消息块长度r为576bit；输出384bit时r为832bit；输出256bit时r为1088bit；输出22bit4时r为1152bit。Keccak规定b=25 *，l= 0， 1， 2，…，6，因此b有{25，50，100，200，400，800，1600}共7种模型，在提交SHA-3的Keccak算法中b=1600bit。

Keccak的填充方式为：首先添加一个1，之后添加最少个数的0，最后添加一个1，即：10…01，其中0的个数应使扩展后的消息串S是消息分组长度r的整数倍。消息串S通过运算：S[ （5y + x） +z]= a[x][y][z]进入三维矩阵中进行变换（x和y的坐标都是模5之后的结果，z是模）。Keccak算法中置换f的输入表示为5*5*的三维比特数组a[x][y][z]，称为状态数组。当b=1600时，数组大小为5*5*64（l=6时）。算法将该数组分为六种单元：slice（各5*5*1 bit）、plane（各5*1*bit）、sheet（各1* 5* bit）、lane（各1* 1* bit）、row（各5* 1* lbit）和column（各1* 5* lbit）。而置换就是分别对这些单元的各比特进行12+2l轮迭代运算。

置换f，每一轮迭代的轮函数为5个变换的复合：R=ι?χ?π?ρ?θ，它们分别对三维数组的不同方向进行变换，以达到充分混淆和扩散的目的。5个变换分别为：

θ：a[x][y][z]←a[x][y][z]+ +。该变换是将每比特附近的两列（column）比特之和迭加到该比特上；

ρ： a[x][y][z]←a[x][y][其中0 ≤t