在现代密码学中，杂凑函数占据基础而又重要的地位。密码学杂凑函数也称Hash函数、哈希函数或单向散列函数，它可以将任意长度的消息压缩到固定长度的杂凑值。杂凑值也被称为杂凑码、杂凑结果、消息摘要或数字指纹。杂凑函数的重要之处就是能够赋予每个消息唯一的“数字指纹”。例如，杂凑值“72c067b50c90837c95186d019f686700”可以看作是使用MD5算法对字符串“Cryptanalysis of Hash Functions and HMAC/NMAC”生成的“数字指纹”，即使更动该消息串的一个字母，对应的杂凑值也会变为截然不同的“指纹”。杂凑函数在现代密码学中有着极其重要的用途，它不仅在安全通信中起着重要的作用，而且是许多密码算法与密码协议安全的基本前提条件。杂凑函数的最重要用途之一是用在数字签名中，它是保证数字签名方案安全而有效的充分必要条件。通常用公钥密码算法进行数字签名时，一般不是对消息直接签名，而是对消息的杂凑值进行签名，这样既可以减少计算量、提高效率，也可以破坏数字签名算法的某些代数结构。因此，对杂凑函数的研究在密码分析领域具有重要意义。除了数据压缩、易于计算这两个基本属性之外，杂凑函数还需要满足下面三个安全属性：·抗原根攻击：对任一预先给定的输出y，寻找—个消息x使得h（x）=y，在计算上不可行。·抗第二原根攻击：对任—输入x，寻找另—个不同于x的消息x′，使得h（x）=h（x′），在计算上不可行。·抗碰撞攻击：找两个不同的消息x和x′，使得它们具有相同的杂凑值，即h（x）=h（x′），在计算上不可行。杂凑函数有两种基本的构造方法—基于分组密码的构造法和直接构造法。1990年Rivest设计了第一个直接构造的杂凑函数MD4，它不基于任何别的密码体制，只使用了基本的模整数加运算、布尔运算和移位运算。MD4之后，又有许多直接构造的杂凑函数先后被提出，如MD5，HAVAL，RIPEMD，RIPEMD-160，SHA-1，SHA-2等，尽管这些杂凑函数比MD4更复杂，但是他们与MD4有相似的结构和相同的设计理念，所以这类杂凑函数被统称为MD4系列的杂凑函数。其中MD5与SHA-1是国际通用的两大杂凑函数算法，被广泛使用于银行、安全通讯以及电子商务中．而SHA-1被认为是现代网络安全的基石。最早对杂凑函数MD4和MD5进行分析的有Merkle（未发表），den Boer和Bosselaers以及Vaudenay。随后Dobbertin提出了一种新的分析方法，应用该分析方法在1996年他成功破解了MD4，其计算复杂度是2²²；1998年证明了前两轮的MD4算法不是单向的（MD4共有三轮）；在MD5攻击方面，1996年则给出了自由初始值下MD5的碰撞实例，也就是在初始值可自由选择的情况下，能够找到两个不同的消息，它们具有共同的杂凑值。在1997年王小云首次使用“比特追踪法”来分析SHA-0，给出了一个优于生日攻击的结果，理论上破解了SHA-0。在1998年，王使用“消息修改技术”极大的改进了这一结果。同年，Chahaud和Joux使用差分分析的方法，也给出了SAH-0的理论分析结果，这一结果发表在1998年的美密会上。“比特追踪法”是现今分析MD4系列杂凑函数所使用的最为广泛有效的方法，它的技术细节在2005年欧密会上公开，是破解包含MD5和SHA-1在内的多数MD4系列杂凑算法的理论基础。在过去三年里，密码学界对杂凑函数的设计与分析给予了更加广泛的关注。在2004年美密会上，王小云等宣布了包括MD4，MD5，HAVAL-128以及RIPEMD在内的碰撞实例，该结果被认为是2004年密码学界最具突破性的结果。与此同时，Biham宣布了40步SHA-1的分析结果；Joux提高了2004年欧密会上Biham和Chen的对SHA-0分析结果，给出了具有4个消息分组的SHA-0的实际碰撞。最为重要的是，王小云和于红波对广泛使用的杂凑函数MD5的破解不仅具有重要的理论意义，而且在实际应用领域也产生了巨大的影响。在2005年，Lenstra等使用该破解结果伪造了两个X.509证书，它们使用的公钥不同但具有相同的签名。随后受王小云教授思想的启发，他们又进一步成功伪造了两个具有相同的签名、不同的公钥以及不同的名称识别段的X.509证书。Lucks与Magnus则构造出MD5的“有意义的碰撞”，使两份Postscript格式的文件虽然内容不同但杂凑值相同。Gebhardt等人则进一步把文件格式扩展到PDF，TIFF和Word97。王小云等人在杂凑函数发展方面的另外一个突破性结果是找到SHA-1的碰撞，最近她们将碰撞攻击的复杂度从2⁶⁹提高到2⁶³，这个结果已经达到了使用现有计算资源可实际破解的临界值。由于王小云等人揭示出SHA-1的脆弱性，美国国家标准与技术研究所（NIST）计划举行杂凑函数标准的公开征集活动，整个流程类似高级加密标准AES的征集和评选过程。本文中将给出针对MD4，4-Pass HAVAL，5-Pass HAVAL以及基于HAVAL的HMAC／NMAC的攻击方法，本文由六部分组成。第一章介绍杂凑函数的定义和属性，描述MD4系列杂凑函数的结构，同时还介绍本论文所重点分析的杂凑函数MD4和HAVAL。第二章系统地描述了针对MD4系列的杂凑函数进行碰撞攻击的比特追踪法，该方法在2005年欧密会上正式发表时被称为模差分方法。模差分是一种精确差分，它不同于一般差分攻击里面使用的异或差分，它能准确表达整数模减差分和异或差分这两种信息。利用模差分方法对杂凑函数进行攻击有四个步骤：第一步是选择合适的消息差分，它决定了攻击成功的概率；第二步是针对选择的消息差分寻找可行的差分路线，这是模差分攻击的关键一步，也是最难的一步，它需要聪明的分析、熟练的技术、持久的耐心以及一定的运气；第三步就是推导出保证差分路线可行的充分条件，在寻找差分路线的过程中，链接变量的条件也可以被确定下来，一个可行的差分路线就意味着从路线上推导出来的所有链接变量的条件相互之间没有冲突；最后一步就是使用消息修改技术，使得被修改的消息满足尽可能多的充分条件。第三章给出了完整版本的4-Pass和5-Pass HAVAL的碰撞攻击。对于4-PassHAVAL，首次给出了一个复杂度为2³⁶的具有两个消息分组的碰撞，使用更复杂的消息修改技术，该攻击的复杂度能够降低到2³⁰；对于5-pass HAVAL，首次给出了一种优于生日攻击的理论攻击方法，复杂度小于2¹²³。到目前为止，这是针对4和5-PassHAVAL碰撞攻击所得到的最好结果。表5给出了一个4-Pass HAVAL碰撞的实例。第四章是对MD4算法进行第二原根攻击。理想情况下，对于给定的消息，找出一个第二原根需要2¹²⁸的计算复杂度，也就是穷举搜索方法的复杂度。但是对于有些消表5：具有两个消息分组的4-Pass HAVAL的碰撞实例息，存在有比暴力破解更有效的攻击方法来找出其第二原根，这样的消息被称为“弱消息”。在2005年欧密会上，王小云等人首次使用模差分的方法对MD4进行高效的碰撞攻击，该攻击中使用的差分路线还能够以微弱的优势对MD4进行第二原根攻击，这也是首次给出的对MD4第二原根的理论攻击．与此同时，王小云教授指出可以找出一条更好的专门针对MD4第二原根攻击的差分路线。在王教授第二原根思想的指导下，本章找到了一条新的适合第二原根攻击的碰撞差分路线，使用该路线，可以证明对于任意随机给出的消息，它是弱消息的概率仅为2^-56，这已经达到了实际可攻击的范围；进一步对任意的随机消息，平均只需2²⁷的MD4计算就能将之转化为弱消息，而且原始消息与最终的弱消息非常接近，它们的汉明距离大约是44。此外本章还首次提出对基于MD4设计的消息鉴别算法，弱消息可以用来区分、伪造和密钥恢复攻击。由Contini等人和Kim等人提出的对基于MD4的消息鉴别算法HMAC和NMAC的攻击，都使用了本章所提出的差分路线。第五章提出了一种新的直接对杂凑函数的压缩函数进行多碰撞攻击的方法。一个K型多碰撞是由K个具有相同杂凑值的不同消息构成，通常表示为K-碰撞。当K=2时就是我们通常所说的碰撞（成对碰撞）。我们的攻击方法不同于Joux等人提出的利用杂凑函数的迭代结构组合成对碰撞为多碰撞的方法，而是直接构造杂凑函数最基本的组成部分一压缩函数的多碰撞。这种新的攻击方法的基本思想就是使用t个不同的路线通过叠加产生一个2^t-碰撞。而这t个路线的寻找方法正是使用模差分方法。对于理想的杂凑函数，找到一个K-碰撞，计算复杂度为O(2^{（k-1）/k n}，其中n是杂凑值的长度。然而，使用我们新的攻击方法，找到MD4压缩函数的4-碰撞所需计算复杂度为2¹⁹；对于3-pass HAVAL，找到4-碰撞所需计算复杂度为2²⁸，找到8-几乎碰撞所需计算复杂度为2⁹。表6和表7给出了MD4和HAVAL多碰撞的实例。表6：MD4压缩函数4-碰撞实例表7：3-Pass HAVAL压缩函数4-碰撞实例第六章分析了基于完整版本的3-Pass和4-Pass HAVAL的消息鉴别算法HMAC和NMAC。一个基于杂凑函数的消息鉴别码（MAC）可以看作是具有两个不同功能输入的杂凑函数，一个输入变量是消息，另一个是密钥。HMAC是标准化的基于杂凑函数的MAC算法，它并被广泛使用的MAC算法，也常作为伪随机函数发生器来使用。本章使用了两种类型的识别器：差分识别器和矩形识别器对HMAC／NMAC进行攻击。在[26]中，Kim等人仅使用矩形识别器来鉴别基于3-Pass和101步的4-PassHAVAL（共128步）的HMAC。据我们分析认为，对于基于HAVAL的HMAC的攻击，差分识别器比矩形识别器更有效。为了方便对两者进行比较，本章给出了两种方法的分析结果。对于差分识别器，本章使用两条新的碰撞差分路线对基于3-Pass和4-Pass HAVAL的HMAC给出了识别、伪造和密钥恢复攻击，这两条新路线的概率分别是2^-96.26和2^-121.27。在HMAC内部和外部函数的输出长度都是256位的情况下，我们的伪造攻击比生日攻击具有更大的优势。对于矩形识别器，也给出了3-Pass和4-Pass HAVAL的两条新的近似碰撞差分路线，其概率分别是2^-64.5和2^-95.5，利用该路线对HMAC进行矩形攻击，其结果优于Kim等人[26]的结果。NMAC是HMAC更一般的版本，它们具有相似的结构，本章对HMAC所有的攻击对NMAC都同样有效。本章的主要分析结果见表8。表8：基于HAVAL的HMAC／NMAC分析结果总之，本文基于在参与破解MD5和SHA-1等工作中积累的理论基础和方法，对杂凑函数MD4，HAVAL进行了碰撞攻击以外的更深度的攻击：第二原根攻击，多碰撞攻击和对基于这两个函数的消息鉴别算法HMAC／NMAC的攻击。这些攻击的理论和方法对新的杂凑函数标准的建立具有指导意义。