1．引言

密码学上的Hash函数也称杂凑函数、哈希函数或单向散列函数，它可以将任意长度的消息压缩成固定长度的Hash值。Hash值也被称为杂凑值、杂凑码、消息摘要或数字指纹。就像每个人都拥有唯一的“指纹”，Hash函数的重要之处就是能够赋予每个消息唯一的“数字指纹”。即使更改该消息的一个比特，对应的Hash值也会变为截然不同的“指纹”。

早期的Hash函数用于非密码领域[1]。20世纪70年代中期，Hash函数用于在时间共享计算机系统中避免储存口令，该思想来源于Needham[2]与Evans，Kantrowitz，Weiss[3]。到70年代末，Wegmen等开始认识到Hash函数在密码学中的重要用途[4]。今天，Hash函数已经成为密码学一个较为独立且极其重要的研究领域，不仅本身是一类基础的密码算法，而且也是设计其他许多密码算法与协议的基本工具。具体表现在：（1）Hash函数作为三类基础密码算法之一可以用于数据的完整性检测，即检测数据是否被修改和伪造；（2）Hash函数最重要的用途是用在数字签名中，它是保证数字签名方案安全而有效的必要条件。通常用公钥密码算法进行数字签名时，一般不是对消息直接签名，而是对消息的Hash值进行签名，这样既可以大大提高签名效率，也可以破坏数字签名算法的某些代数结构。不带Hash函数的一般的数字签名方案大都存在潜在的伪造攻击，如RSA、ELGamal等数字签名方案。虽然有些不带Hash函数的数字签名方案是安全的，但运行速度较慢，如基于树结构的数字签名方案；（3）一个安全的Hash函数是许许多多基于Hash函数的密码算法与协议安全的必要条件之一，如基于Hash函数的各种密码算法：数字签名、盲签名、组签名、群签名、电子钱币、电子选举等，基于Hash函数的各种协议：如比特委托、抛币、鉴别等协议。因此，对Hash函数的研究在密码分析领域具有重要意义。

Hash函数有两种基本的构造方法：基于分组密码的构造法和直接构造法。最初Hash函数的设计主要围绕在基于分组密码的设计[5]，其目的是通过一些现成的分组密码算法改造成Hash函数算法。如果算法的整体结构设计合理，并且分组算法是安全的，这些Hash函数也是安全的。随着Hash函数应用的不断深入，1990年Rivest第一个直接设计了Hash函数MD4 [6]，它不基于任何别的密码体制。MD4之后，又有许多直接构造的Hash函数先后被提出，如MD5[7]，HAVAL[8]，RIPEMD[9]，RIPEMD-160[10]，SHA-0[11]，SHA-1[12]，SHA-2[13]等，尽管这些Hash函数通常比MD4更复杂，但是它们都与MD4具有相似的结构框架，所以这类Hash函数被统称为MD4系列的Hash函数（见图1）。根据消息分布或扩展方式的不同，MD4系列Hash函数又可分为MDx类和SHAx类。其中MD5与SHA-1是国际通用的两大Hash函数算法，这两大算法十多年来经受了众多密码学家的攻击，成为世界各国在银行、证券、电子商务中保证电子签名、身份验证、数字证书等方面安全的核心技术。

图1 MD4类Hash函数算法

最早对Hash函数MD4和MD5进行分析的有Merkle（未发表），den Boer和Bosselaers [14，15]以及Vaudenay[16]。随后Dobbertin提出了一种新的数学分析方法，1996年他应用该方法成功破解了MD4，其计算复杂度是222[17]，1998年他证明了前两轮的MD4算法不是单向的（MD4共有三轮）[18]；在MD5攻击方面，1996年Dobbertin则给出了MD5的伪碰撞攻击实例[19]，也就是在错误的初始值下，找到了两个不同的消息，它们具有共同的Hash值。但这种伪碰撞攻击并没有影响MD5在实际中的应用。

1997年王小云首次使用“比特追踪法”来分析SHA-0，给出了一个优于生日攻击的结果，理论上破解了SHA-0 [20]；1998年，王使用“消息修改技术”极大地改进了这一结果[21]；王的这两个结果仅在国内交流，并且得到中国密码学家的认可。“比特追踪法”和“消息修改技术”是现今分析MD4系列Hash函数所使用的最为广泛有效的方法，它的技术细节在2005年欧密会上公开，是破解包含MD5和SHA-1在内的多数MD4系列杂凑算法的理论基础。1998年，Chahaud和Joux使用差分分析的方法，也给出了SHA-0的优于生日攻击的理论分析结果，这是国际上首次对SHA-0的公开分析结果[22]。

在过去三年里，密码学界对Hash函数的设计与分析给予了更加广泛的关注。在2004年美密会上，王小云等宣布了包括MD4，MD5，HAVAL-128以及RIPEMD在内的碰撞实例[23]，该结果被认为是2004年密码学界最具突破性的结果。王和于对MD5破解结果正式发表在2005年的欧密会上，它建立了对现有Hash函数算法进行碰撞攻击的新理论，开创了Hash函数研究的新高潮。与此同时，Biham[Bih04]宣布了40步SHA-1的分析结果；Joux提高了2004年美密会上Biham和Chen的对SHA-0分析结果[24]，给出了具有4个消息分组的SHA-0的实际碰撞[25]。

MD5的破解不仅具有重要的理论意义，也对基于它的实际应用造成威胁。基于王等破解MD5的理论与技术，2005年Lenstra等使用MD5的碰撞伪造了两个X．509证书[26，27]，它们使用的公钥不同但具有相同的签名。在2006年RSA大会报告上，王提出了在任意两个不同的初始值下构造MD5的碰撞的思想和解决方案[28]，使用该方案Lenstra等成功地构造了具有8个消息分组的任意两个不同的初始值下的MD5碰撞；他们进一步使用该碰撞伪造了两个具有相同的签名、不同的公钥以及不同的名称识别段的X．509证书[29]。Lucks与Magnus则构造出MD5的“有意义的碰撞”，使两份Postscript格式的文件虽然内容不同但Hash值相同[30]。Gebhardt等人则进一步把文件格式扩展到PDF，TIFF和Word97[31]。

Hash函数发展方面的另一重要研究进展是2005年2月王等人对SHA-1的碰撞攻击，该攻击的计算复杂度为269，这是首次对SHA-1的理论破解[32]。半年后，王等将碰撞攻击的复杂度从269提高到263 [33]，这个结果已经达到了使用现有计算资源可实际破解的临界值。在2006年，De Canniere等人进一步给出了64步SHA-1（共80步）的碰撞实例[34]，2007年，他们又给出了70步SHA-1碰撞的实例[35]。

基于王、于等对SHA-1的攻击，NIST发表正式声明，推动在新的Hash函数的标准没有建立之前暂时使用SHA-2来取代SHA-1（http://csrc.nist.gov/groups/ST/hash/）。到目前为止，公开的对SHA-2的攻击还没有威胁到它的安全，但SHA-2继承了许多MD4类Hash函数的设计理念，对SHA-2的进一步分析对推动Hash函数分析的进展具有重要的意义。

Whirlpool是Rijmen等设计的一个Hash函数算法[36]，它在压缩函数的设计上与MD4类的Hash函数有本质的不同，使用了分组密码设计的一些技术，但是这个算法的安全性有待于进一步的研究。

一个带密钥的Hash函数通常用来作为消息认证码，简称MAC，它是消息和密钥的公开函数。基于Hash函数的MAC算法主要有密钥前缀的MAC、密钥后缀的MAC，MDx-MAC[37]，HMAC、NMAC[38]等。HMAC[38]是一个被提议为FIPS标准的MAC算法，也是目前被广泛使用的MAC算法。

由于Hash函数的破解，基于这些Hash函数设计的MAC算法的分析也成为近三年密码学研究的热点。MD4、MD5、SHA-0、SHA-1等Hash函数已不再安全，那么基于这些Hash函数的HMAC是否安全呢？2006年，Contini等利用碰撞攻击证明了基于MD4的HMAC是不安全的[39]，可以对其进行鉴别、伪造和部分密钥恢复攻击。利用同样的方法，通过寻找高概率的差分路线，于红波等证明了基于HAVAL的HMAC是不安全的[40]。Kim等人对基于MD4、MD5、SHA-0、SHA-1的HMAC安全性进行分析[41]。所有的这些分析结果都是基于Hash函数的碰撞或几乎碰撞的存在，鉴于目前的分析方法，HMAC的安全性严重依赖于它所使用的Hash函数的安全性。

基于目前Hash函数的研究现状，美国国家标准与技术研究所（NIST）已于2007年11月2日正式宣布举行Hash函数标准的公开征集工程http://csrc.nist.gov/groups/ST/hash/，该工程从2008年到2012年，共计5年的时间，整个流程类似高级加密标准AES的征集和评选过程。