5.2 散列算法

1990年，Ron Rivest采用Merkle-Damgård结构第一个直接设计了散列算法MD4。与分组密码相似的进展，强力攻击能力的提高，导致了算法的改进。分组密码从DES发展到AES，散列算法也从MD4和MD5发展到SHA-1、RIPEMD-160以及SHA-2系列。1992年，Ron Rivest在MIT设计了MD5（RFC 1321），在SHA-1之前，MD5是最主要的散列算法。它的输入是任意长度的消息，输出是128位的消息摘要，以512位输入数据块为单位进行处理。安全散列算法（SHA）是由NIST设计，并于1993年作为联邦信息处理标准FIPS 180发布，修订版（FIPS 180-1）发布于1995年，通常称为SHA-1。SHA-1是美国DSA签名方案（Internet RFC 3174）使用的标准算法，它的输入是最大长度为264-1位的消息，输出是160位的消息摘要，以512位数据块为单位进行处理。RIPEMD-160是著名的密码工程欧洲RIPE（RACE Integrity Primitives Evaluation，RIPE）工程的结果，最早为128位RIPEMD，后改进成为160位消息摘要，它的基础是MD5，输入是最大长度为264-1位的消息，输出是长度为160位的消息摘要，以512位数据块为单位进行处理。

2001年5月30日，NIST发布了修订版本FIPS 180-2，增加了三个附加的散列算法，SHA-256，SHA-384和SHA-512，统称为SHA-2系列。与AES密码的安全性相兼容，结构与细节类似于SHA-1。SHA算法的参数比较参见表5.1。表中安全性是指对输出长度为m比特的散列函数的生日攻击产生碰撞的工作量为2m/2。

基于MD4算法的框架结构，人们设计的一系列散列算法，包括MD5，HAVAL，RIPEMD，SHA-0，SHA-1，SHA-2等，被统称为MD4系列的散列算法。根据消息分布或扩展方式的不同，MD4系列的散列函数又可分为MDx类和SHAx类。2004年8月17日，在美国加州圣·巴巴拉召开的国际密码学会议（Crypto'2004）上，我国密码学家王小云教授宣布了包括MD4，MD5，HAVAL-128以及RIPEMD在内的碰撞实例，立即引起密码学界、信息安全界和民众的轰动。该结果被认为是近年来密码学界最具突破性的结果，攻击的具体方法——比特追踪法正式发表在2005年的欧洲密码会上，它建立了对MD4类散列算法进行碰撞攻击的新理论，开创了散列函数研究的新高潮。在此之前，SHA-1嵌入诸如加密软件（PGP）和安全套接层协议（SSL）等使用广泛的程序中。王小云教授等人公布的成果，证明MD5已被破解，不能再被实际使用。对于SHA-1算法，碰撞攻击所需要的运算次数从原来设计时估算的280次降为261次。这些工作迫使美国国家标准与技术研究所（NIST）不得不采取一系列应对措施，2005年，NIST宣布了逐步停止使用SHA-1的意图，到2010之后使用SHA-2系列的版本。在2010之后，SHA-1应该只用于HMAC、随机数的产生和密钥推导函数（Key Derivation Functions，KDF）等。2006年，NIST开始启动为期6年的公开征集新散列算法标准SHA-3的计划。目前，有14个候选算法进入了SHA-3公开征集的第二轮评估。

表5.1 SHA参数比较

我国的《电子签名法》于2005年4月1日刚刚开始实施，在法律上确定了电子签名的有效性。电子签名的主体算法是RSA，ECC和DSA等公钥算法，而MD5和SHA-1等摘要算法是辅助算法，但起重要作用。算法的破解不会影响电子签名的法律效力，只是表明某种具体的电子签名算法需要替换，技术需要更新。