2．Hash函数及其研究现状

2.1 Hash函数简介

一个密码Hash函数是一个映射H:{0，1}*→{0，1}n，其中{0，1}*代表任意长度的比特串的集合，消息M∈{0，1}*的像H(M)被称为M的Hash值或杂凑值。从数学上看，由于原像空间比像空间大，碰撞一定是存在的，也就是说存在两个不同的消息，它们具有相同的Hash值。从安全性上考虑，一个Hash函数必须满足下面三条基本的属性：

1．抗原像攻击：对任一预先给定的输出y，寻找一个消息x使得h(x)=y，在计算上不可行。

2．抗第二原像攻击：对任一输入x，寻找另一个不同于x的消息x′，使得h(x)=h(x′)，在计算上不可行。

3．抗碰撞攻击：找两个不同的消息x和x′，使得它们具有相同的Hash值，即h(x)=h(x′)，在计算上不可行。

所谓计算不可能可以理解计算所需要的时间和空间超过了现有的可获得的资源。到目前为止，280的计算复杂度被认为是绝对“计算不可行”。

2.2 现有Hash函数的设计原则

大多数Hash函数h的设计采用Merkle和Damgård（MD）迭代结构[Mer90][Dam90]，该设计原则是基于压缩函数的迭代，每次处理一个固定长度的消息分组。设f :{0，1}n×{0，1}m→{0，1}n是一个具有固定输入长度的压缩函数，消息x在被压缩前首先被划分成长度为m比特的消息分组x0，x1，…，xl，其压缩过程如图2所示[42]。

2.3 Hash函数的攻击种类

一般来说，对Hash函数的攻击主要有以下几类：

碰撞攻击（Collision Attack）：寻找两个不同的消息M和M′，使得H(M)=H(M′)。

原像攻击（Preimage Attack）：给定一随机数Y{0，1}n∈，寻找消息M，使得H(M)=Y。

第二原像攻击（Second Preimage Attack）：给定一个消息M，寻找另一个不同于M的消息M′，使得H(M)=H(M′)。

多碰撞攻击（k-collision attack）：对于k≥2，寻找k 个不同的消息Mi，使得H(M1)=…=H(Mk)。

k向原像攻击（k-way preimage attack）：给定Y，寻找k 个不同的消息Mi，使得H(Mi)=Y。

k向第二原像攻击（k-way preimage attack）：给定消息M，寻找k个不同的消息Mi（Mi ≠M），使得H(Mi)=H(M)。

对于一个理想的Hash函数H:{0，1}*→{0，1}n，根据生日攻击，寻找一对碰撞的复杂度为2n/2，寻找一个k-collision的复杂度为2(k-1)·n/k，寻找原像和第二原像的复杂度为2n，寻找k向原像和第二原像的复杂度为k·2n。由于数字签名以及Hash函数其他一些重要应用都基于碰撞攻击，所以对Hash函数的攻击更多地集中在碰撞攻击上。

2.4 早期Hash函数的分析

Dobbertin对早期Hash函数的分析做出了杰出的贡献。1996年，Dobbertin用数学的方法对MD4进行成功的破解，计算复杂度是222[17]；1998年证明了前两轮的MD4算法不是单向的（MD4共有三轮），也就是存在着原像和第二原像攻击[18]；1996年给出了MD5的伪碰撞实例，也就是两个不同的消息在错误的初始值条件下，具有相同的MD5 Hash值[19]。

1997年，王小云首次使用“比特追踪法”来分析SHA-0，给出了一个优于生日攻击的结果，该攻击的复杂度为258，理论上破解了SHA-0 [20]。在1998年，王使用“消息修改技术”极大地改进了这一结果，采用消息修改技术把攻击的效率提高到245[21]。同年，Chahaud和Joux使用差分分析的方法，也给出了SAH-0的理论分析结果，这是国际上首次对SHA-0的公开分析结果，这一结果发表在1998年的美密会上[22]。“比特追踪法”是现今分析MD4系列Hash函数广泛使用的有效方法，它的技术细节在2005年欧密会上公开，又称为“模差分方法”[43]，它是破解包含MD5和SHA-1在内的多数MD4系列Hash函数的理论基础。2003年，Rompay等给出了HAVAL-128的碰撞攻击实例，该攻击的复杂度为229[44]。

2.5 Hash函数的最新研究进展

2.5.1 MD5的破解

在1998～2003年这段时间里，Hash函数的研究处于一个低谷时期。2004年是Hash函数发展史上不同寻常的一年，这一年在美国的圣芭芭拉召开的美密会上，来自中国的王小云宣布了包括MD4，MD5，HAVAL-128以及RIPEMD在内的碰撞实例[23]，引起密码学界的极大关注。与此同时，Biham宣布了40步SHA-1的分析结果；Joux提高了2004年美密会上Biham和Chen的对SHA-0分析结果[BC04]，给出了具有4个消息分组的SHA-0的实际碰撞[25]。

王等对MD5的破解标志着Hash函数分析的新方法和新理论的建立。该理论的关键技术为“比特追踪法”，“消息修改技术”和“多消息分组组合成碰撞理论”。

比特追踪法是通过提炼Hash函数的数学特征，利用比特进位产生有用的非零比特抵消因子，从而寻找有效的碰撞路线。并且通过Hash函数使用的布尔函数的特性，确定出碰撞攻击路线成立的前提条件。

一般密码算法分析具有两种标志。一种为理论上的突破，即找到攻击方法以低于搜索时间（强力攻击）的运行效率破译该算法。一种是实际有效攻击，即找到攻击方法在计算机有效的运行时间内破译该算法。王小云的比特追踪法在攻击具有强雪崩效应的Hash函数，如MD5和SHA-1，最初取得了理论破解结果。为了将理论攻击改进成为实际攻击，王还提出了另外一种关键技术——消息修改技术。消息修改技术包括：

1）基本消息修改技术：王小云破译的MDx的碰撞概率等于比特追踪法找到的碰撞差分的概率。一般Hash函数算法包含3～4圈，不妨假设4圈，因此碰撞差分的概率为4圈的差分概率的乘积。基本修改技术可以使修改后的两个消息在第一圈的差分以1的概率成立。因此经过基本消息修改技术后碰撞概率仅相当于三圈的差分成立概率。

2）高级消息修改技术：高级消息修改技术是极具创新性的一种提高碰撞概率的方法。高级修改技术的关键思想是在修改消息时，保证第一圈的差分不变的前提下，将第二圈的多数条件或者部分条件经过修改后满足碰撞要求。

这种修改技术的重要性不仅仅在于提高Hash函数碰撞概率，也提出了Hash函数安全的一种评估标准。如对于MD4而言，含有3圈（48步）碰撞概率通过明文修改技术后碰撞概率成为仅一圈的碰撞概率。这意味着，MD4算法由人们心中48步的安全性降低到16步（一圈）的安全性。这种安全性的降低是设计新的Hash函数算法时必须考虑的问题。

在使用比特追踪法确定差分路线后，消息修改技术尤其是高级消息修改技术是提高攻击效率的关键。王等在2004年美密会上提供的MD5碰撞的搜索时间大约为15分钟。MD5结果公布后，许多密码学家都在原有MD5路线的基础上，使用消息修改技术对MD5的碰撞攻击效率进行改进[45，46，47，48]。到目前为止，在普通的PC上，找到一对MD5碰撞仅需要几秒钟的时间。

多个消息分组组合成碰撞理论：MD4类Hash函数总体设计原则是基于MD迭代结构，一次迭代仅压缩一个消息分组。在MD4，HAVAL-128，RIPEMD的碰撞分析过程中，很容易找到一次迭代的碰撞，即一个消息分组的碰撞。长期以来，分析者们很难打破仅寻找具有一个消息分组碰撞的局限性。但是在分析MD5碰撞攻击过程中，由于MD5的强雪崩效应，很难找到具有一个消息分组的碰撞。通过大量分析发现容易找到一种特殊的差分，该差分组合多个消息分组而构成碰撞。这种技术在2004年美密会上也由Joux和Biham独立发现，用来寻找具有4个消息分组的SHA-0的碰撞[25]。

2.5.2 MD5的破解对实际应用的影响

MD5的破解引起了国际密码学界的高度重视，国际密码学家一致认为基于MD5的实际应用的理论基础已经不再存在。但在应用领域，随机碰撞能否构成实际的攻击，这是MD5破解后信息安全领域一直关注的问题。

在2005年欧密会的非正式会议上，Lucks和Magnus利用MD5的随机碰撞构造了两份内容完全不同的PS格式文件[30]，它们具有相同的MD5校验和（见图3）。它们的构造主要是利用了PS软件格式上的冗余，具体构造方法见http://www.cits.rub.de/MD5Collisions/。Gebhardt等人则进一步把文件格式扩展到PDF，TIFF和Word97[31]。

在同一年，Lenstra等使用王、于提供的MD5碰撞实例伪造了两个X．509证书[26，27]，它们使用的公钥不同但具有相同的签名。

在2006年RSA大会报告上，王提出了在任意两个不同的初始值下构造MD5的碰撞的思想和解决方案，使用该方案，Lenstra等成功地构造了具有8个消息分组的任意两个不同初始值下的MD5碰撞。进一步，他们利用该碰撞伪造了两个具有相同的签名、不同的公钥以及不同的名称识别段的X．509证书，其技术细节见[29]。

Lucks和Lenstra等的工作进一步证实，Hash函数MD5的破解不仅具有重要的理论意义，而且对基于它的实际应用产生了巨大的威胁。目前基于MD5的许多应用仍在使用之中，如The Debian Packet Format，The RPM packet Format，Open BSD，MySQL[49]等，我们呼吁立即停止MD5在这些密码技术和密码产品中的使用。

2.5.3 SHA-1的破解

SHA-1是由美国NIST提出的Hash函数标准，是使用最广泛的Hash函数。一直到2005年早期，没有对SHA-1全算法进行攻击的文章，SHA-1仍然被认为是安全的。2005年2月的RSA大会上，图灵奖获得者Rivest、Shamir以及公钥密码学的创始人Diffie等五位密码学家公布了Hash函数发展史上的重要研究进展——前一天他们收到了来自中国的三位女研究者对SHA-1全算法的碰撞攻击。

王、于等对SHA-1的攻击效率为269，优于280的理论值，并给出了58步（共80步）的碰撞实例。在他们对SHA-1的分析中除了比特追踪法、消息修改技术以及多消息分组组合成碰撞理论外，SHA-1分析的困难之处是第一圈存在着不可能差分，以至于难以找到SHA-1的高概率的差分路线。不可能差分现象是破解SHA系列的Hash函数算法的理论难点。王首次提出了将不可能差分转换成确定概率差分的思想，完成了不可能差分到确定概率差分的转化，找到了SHA-1的碰撞路线，并提高了SHA-0的碰撞效率[50]。

SHA-1的破解引起了国内外密码学界的极大关注。Shamir认为“这会引起轩然大波，对指导设计新的Hash函数算法极其重要”。Rivest认为：“SHA-1的破译令人吃惊……，数字签名的安全性在降低，这再次提醒需替换算法”。

著明的科学杂志《Science》评论指出，中国密码学家首次成功对SHA-1进行了攻击，虽然269的计算超出了现有计算能力的范围，但足以引起密码学家的担忧[51]。半年后，王小云等对这一结果进行了改进，新的攻击结果的计算复杂度为263[33]，这已经达到了使用现有计算资源可实际破解的临界值，实现了从理论攻击到实际攻击的跨越。

在2006年，Canniere等在王的基础上，结合差分路线的自动寻找技术，进一步给出了64步SHA-1（共80步）的碰撞实例[34]，采用同样的方法，2007年他们又给出了70步SHA-1碰撞的实例[35]。

2.6 第二原像攻击

理想情况下对于给定的消息M，找到另一个消息M′≠M，使得H(M)=H(M′)的计算复杂度为2n（n为Hash函数的输出长度），也就是穷举搜索的复杂度。2005年于和王等证明了对于MD4，在256的消息空间中存在着一个消息M，攻击者能够以1的概率找到它的第二原像[YWZW05]。除了MD4外，到目前为止还没有找到有效的方法寻找MD5、SHA-1等较为复杂的Hash函数的第二原像的方法。

2.7 多碰撞攻击

对一个具有n比特输出长度的理想安全的Hash函数，找到一对碰撞的复杂度为O(2n/2)，而找到一个k-碰撞的复杂度为O(2n(k-1)/k)。一个k型多碰撞是由k个具有相同杂凑值的不同消息构成，通常表示为k-碰撞。当k=2时就是我们通常所说的碰撞（成对碰撞）。

在2004年美密会上，Joux利用Hash函数迭代结构的弱点，提出了一种利用Hash函数的成对碰撞（2-碰撞）构造2t-碰撞的方法。Joux证明对任意基于迭代结构的Hash函数，寻找一个2t-碰撞是相对容易的，它所用的时间仅为寻找一对普通的成对碰撞的t倍。利用该结果，Joux证明多个Hash函数的连接不能够增加它的安全性[52]。Joux的多碰撞结构如图4所示：

2007年，于、王提出了一种利用（成对）碰撞直接构造Hash函数的压缩函数的多碰撞（或几乎多碰撞）的方法，利用该方法能够有效地寻找MD4压缩函数的4-碰撞和3-Pass Haval压缩函数的4-碰撞和8-几乎碰撞实例[53]。

2.8 NIST针对SHA-1破解的应对措施

MD5、SHA-1破解后，NIST发表多次评论以及召开两次Hash函数研讨会来应对目前Hash函数的研究现状，其过程如下（http://csrc.nist.gov/groups/ST/hash/）：

—2004年8月25日，针对王小云教授在2004年美密会上公布的包括MD5在内的Hash函数的分析结果，NIST宣布SHA-1仍然是安全的，但是鉴于目前Hash函数的分析技术，决定在2010年逐步撤出SHA-1的使用。

—2005年2月18日，NIST发表声明宣布相信王小云教授等对SHA-1的破解结果，尽管269的计算复杂度似乎不能够影响基于SHA-1的数字签名以及HMAC在实际应用中的安全性，但鉴于计算能力的提高，NIST决定在2010年之前使用更强的Hash函数SHA-2（SHA-224，SHA-256，SHA-384和SHA-512）来取代SHA-1。

—2005年10月31日到11月1日，NIST举行了第一次Hash函数研讨会，此次研讨会的主要目的是讨论SHA-1的攻击方法，评估NIST支持的Hash函数算法（SHA-2）的安全性，讨论未来Hash函数发展的策略方针。在此次会议的报告中，一些新设计的Hash函数以及签名方案被提出。由于现有的数字签名方案依赖于Hash函数的碰撞攻击，MD5、SHA-1等碰撞的出现对使用它们的数字签名方案造成威胁。Halevi和Krawczyk提出了一种新的基于Hash函数的原像攻击而不基于碰撞攻击的数字签名方案，使得现在的碰撞攻击不影响它的安全性[54]。

—2006年3月15日，NIST公布了新的Hash函数使用政策：联邦机构在2010年之前必须停止SHA-1在电子签名、数字时间戳和其他一切需要抗碰撞安全的密码体制中。SHA-1只能够用于基于SHA-1的消息鉴别算法（HMACs）、密钥分配函数（KDFs）和随机数产生器（RNGs）中。

—2006年4月25日，NIST再次对SHA-1的攻击发表评论，评论中指出，对王小云等对SHA-1的碰撞攻击进行改进，改进的攻击把SHA-1碰撞攻击的复杂度由269提高到263，这已经到了已有资源可破解的临界值。针对这一结果，NIST宣布了三步应对措施：

1）在数字签名中快速实现从SHA-1到SHA-2的转化。尽管SHA-2可能会遭受与SHA-1相同的分析技术的攻击，但是SHA-2比SHA-1更安全。尽管SHA-2的使用受商业应用的限制，但无论如何，联邦机构一定要在2010年之前停止SHA-1在数字签名中的使用。

2）鼓励密码学家对Hash函数进行研究，以更好地理解Hash函数的设计和攻击方法，为最终的Hash函数设计做准备。密码领域正面临着一个Hash函数理论和分析的快速发展期，NIST计划举行更多的Hash函数的研讨会。

3）举办一次Hash函数的公开征集，整个过程类似与AES的征集和评估过程。这次征集的日程表还没有最终决定，需要等到Hash函数的理论和技术足够成熟和稳定。

—2006年7月12日，NIST公布了设计Hash函数标准的暂时时间表，并且规定了新的Hash函数设计方案的基本要求。该过程的具体时间表如下：

2008年第三季度，所有新设计的Hash函数完成提交；

2008年第四季度，审阅提交的Hash函数设计，选择符合基本要求的候选方案；举办首次Hash函数候选方案会议，宣布第一轮候选算法并向公众征求意见。

2009年第四季度，结束向公众征求意见。根据提交方案的数量和质量，NIST可能会延长向公众征求意见的时间，以方便公众有足够的时间对所有候选算法进行充分的分析；召开第二次Hash函数候选算法会议，讨论对第一轮候选算法的分析结果。

2010年，选择并宣布进入最后一轮的候选算法。

2011年，召开最后一次会议，选择最终的标准Hash函数算法。

2012年，出版标准草案。

—2006年8月24日至25日，NIST举办了第二次Hash函数研讨会，鉴于SHA-1的攻击，NIST继续推荐由SHA-1到SHA-2的转换。NIST还将长时间推动通过公开竞争的形式征集新的Hash函数算法。

—2007年11月2日，NIST宣布Hash函数标准的征集工作正式启动。征集论文的截至时间为2008年10月31日。