目前，我们生活在信息社会里。随着信息和通信技术的不断发展，这些技术正日益走入越来越多人的生活。这些发展和应用给我们带来了实质性的利益，但是同时也带了诸多危害，它使我们的私人信息易于泄露，身份被他人盗用以及数据被他人篡改。为了避免这些危害，我们需要建立和发展值得信赖的信息体制。这些可信赖的体制及建立它们的基石是密码学研究的主要课题。密码学是研究数学技术及相关的保密性、数据完整性、实体认证、数据源认证等信息安全各领域的综合性的学科。它运用了数论、概率论、统汁学、组合学等数学知识，并涉及信息论、计算复杂性、编码理论等学科知识。它不仅为信息安全提供服务和途径，而且还带来了一系列技术革新。Hash函数在现代密码学中起着重要的作用。它可以将任意长度的输入压缩为固定长度的值，输出值我们称为Hash值。根据其定义和性质，Hash函数可用于保证数据完整性和实体认证，同时也是多种密码体制和协议的安全保障，例如数字签名、消息认证码等。Hash函数用于数据签名可带来诸多好处：可破坏数字签名方案的某种数学结构；可提高数字签名速度；无需泄露签名所对应的消息；可将签名变换和加密变换分开。目前，标准的Hash函数分为两大类：MDx系列（MD4，MD5，HAVAL，RIPEMD，RIPEMD-128，RIPEMD-160等）和SHA系列（SHA-0，SHA-1，SHA-256，384，512等）。这些Hash算法体现了Hash函数的设计技术。MD4算法是较早出现的Hash函数算法，它使用了基本的算术和布尔运算，其设计原则采用了迭代结构的思想。在MD4算法公布后，许多Hash函数算法相继提出来，包括MD5、HAVAL、RIPEMD、IRIPEMD-128、RIPEMD-160、SHA-0和SHA-1等，它们的大多数算法也是基于MD4算法的设计原则。RIPEMD算法是欧洲计划RIPE的组成部分。RIPEMD-128算法是1996年由Hans Dobbertin，Antoon Bosselaers和Bart Preneel提出来的，用于替代RIPEMD算法，其输出Hash值为128比特。该算法由两个平行独立的操作部分组成，我们分别称为左路和右路，两部分都由四圈组成，每圈都包括一个圈函数，每个圈函数有不同的函数特性，用于以后的攻击中。两部分操作的输出结果进行运算用于生成Hash函数值。通常，我们讨论Hash函数的安全性，其包括三个特性，分别是抗原根性、抗第二原根性和抗碰撞性。所以对于不同特性在分析中存在多种不同的攻击方法。在近十几年里，对于Hash函数的分析取得了一些进展。生日攻击是一般的攻击方法，其名字来源于“生日问题”，可用于任何类型的Hash函数，其复杂性依赖于Hash值的长度。1996年，H．Dobbertin给出了一个对MD4算法全算法攻击，该攻击以2^-22的概率找到一个碰撞。1998年，H.Dobbertin证明了MD4算法的前两圈不是单向函数，这一结论意味着对于寻找原根和第二原根存在有效的攻击。对于RIPEMD算法，H.Dobbertin可以以2³¹的复杂性找到两圈RIPEMD的碰撞。随着MDx系列Hash函数的发展，对于这些函数的安全性分析也不断增加。B．den Boer和A．Bosselaers找到了针对MD5算法的一种伪碰撞，即同一明文在不同初始值下的Hash函数值相同。在1996年欧洲密码大会上，H．Dobbertin公开了另一种形式的伪碰撞，即在两个不同的初始值下的不同消息的一个碰撞。在1998年国际密码大会上，F，Chabaud和A．Joux证明了用差分攻击方法可以以2^-61的概率找到SHA-0的一个碰撞。2003年亚密会上，B．V．Rompay等人给出了以2^-29的概率针对HAVAL-128算法的碰撞攻击。一些针对Hash函数的强力有效的攻击方法及结果出现在2004年。Eli Biham和Rafi提出了对SHA-0算法的几乎碰撞。A．Joux给出了一个由4个明文构成的SHA-0的碰撞。这些结果中，最为显著的是在2004年国际密码学大会上，王小云等人宣布的对于一系列Hash函数的碰撞结果，包括MD4、MD5、HAVAL-128和RIPEMD算法，其可以找到MD4和RIPEMD算法碰撞的复杂性分别低于2⁸和2¹⁸。同时，王小云提出了一套新的针对MDx系列的Hash函数的分析技术，给出了得到满足差分路线的充分条件的方法，以及如何使用明文修改技术来提高碰撞攻击的成功概率。随后，在2005年，王小云等使用此技术对MD5、SHA-0、SHA-1算法进行攻击，取得了较好的结果，并证明这些技术对于Hash函数分析是十分有效的。此攻击方法还可以用于MD4算法的第二原根攻击，以及HMAC和NMAC的伪造攻击及部分密钥恢复攻击。差分分析是由E．Biham和A．Shamir于1990年提出的，它是针对对称密码体制（分组密码、流密码、Hash函数和MAC算法）的选择明文（或选择密文）攻击最有效的方法之一。它的主要思想是通过分析特定明文差分对对结果密文差分的影响来获得可能性最大的密钥。王小云等基于差分分析的思想，采用不同于传统异或差分的模减差分（H．Dobbertin也采用过此类差分），提出了一系列对标准Hash函数算法MD4，RIPEMD，HAVAL，MD5，SHA0，SHA1的攻击。在王小云等人的方法中，经过对Hash函数算法的的明文差分通过每轮圈函数的整数模减差分和异或差分的分析，得到差分特征，以得到更多的信息来寻找碰撞。在本文中，我们详细介绍了Hash函数，包括Hash函数的基本定义、性质、设计原则、应用以及针对Hash函数的攻击方法等基本知识。本文的主要工作分为两部分。一是给出了针对RIPEMD-128算法后三圈的碰撞攻击。另一个是对HMAC-MD4内部函数的安全性分析。这两部分中的攻击都采用王小云等提出的对于国际通用标准Hash函数的攻击方法。在第四章中，我们定义整数模减差分为：对于两个输入X和X′，△X=X′-X。在此攻击中，我们采用的差分是带正负标记的整数模2³²的模差分和异或差分。其中，我们用带正负标记的比特位置来标记异或差分，对于X中比特值为0的比特位不带标记，X中比特为值1的定义为负标记。例如，对于差分-2²³，表示整数模减差分X′-X=-2²³，其中比特进位从第24比特到第29比特。X中第24比特到第28比特值为0，第29比特值为1，而对于X′，第24比特到第28比特值为1，第29比特值为0。异或差分就是这些由比特进位带来的差分。对算法的攻击过程包括以下三步：第一步选择满足后三圈RIPEMD-128算法的明文差分由于RIPEMD-128算法是由两部分平行且独立的操作组成的，所以选择明文差分，使其同时满足两部分操作以产生差分路线是比较困难的。通过分析明文分组在两部分中每圈中位置，以及非线性圈函数的性质，并考虑明文修改技术的操作特点，我们选择两比特的明文差分如下：△N₀=0（?）△H=0，△M=M′-M=(△m₀，△m₁，…，△m₁₅)，△m₁=2³¹，△m₁₄=2²³，△m_i=0，0≤i≤15，i≠1，14。对应的输出差分为：△a=△cc+△ddd=0，△b=△dd+△aaa=0，△c=△aa+△bbb=(2³¹+2³¹)mod 2³²=0，△d=△bb+△ccc=0。我们可以分别得到RIPEMD-128算法后三圈两部分操作的差分路线。关于左右两路的碰撞差分的差分特征见第四章表4．1和表4．2。第二步推导满足后三圈RIPEMD-128算法碰撞路线的充分条件。根据算法中布尔函数的性质和差分特性，我们将得到满足差分特征的碰撞路线充分条件，这个过程在我们的攻击中也是至关重要的。它与碰撞路线是密切相关的，若充分条件中有矛盾出现，不能满足满分特征，则表明碰撞路线是错误的，不能产生碰撞。我们将给出两个如何得到充分条件的实例。1．左路中第19步的差分路线如下：（d₅，a₅[31]，b₄[-4，25，31]，c₄[-4，-5，7，24]）→（c₅[11，-12，13，32]，d₅，a₅[31]，b₄[-4，25，31]），对于F₃（X，Y，Z）=（X∨（?）Y）⊕Z，根据命题3-3（a），若使F₃（x，y，0）=0且F₃（x，y，1）=1，当且仅当x=0且y=1，由充分条件d_5,25=0，a_5,25=1，和b_4,25=0得到F₃(d_5,25，a_5,25，b_4,25)=0且F₃(d_{5,25，a5,25，（?）b4,25}=1。所以圈函数的输出差分△f₁₉[25]=2²⁴。最后，△c₅[32]=((△c₄[24]+△m₁₄+△f₁₉[25])mod 2³²)（?）6=((2²³+2²³+2²⁴)mod 2³²)（?）6=2³¹。2．右路中第18步的差分路线如下：（a₅[5，-6]，b₄[-5，16，-17，-24]，c₄[-13，-26，-27，-28，29]，d₄）→（d₅[13，24，25，-26，31，-32]，a₅[5，-6]，b₄[-5，16，-17，-24]，c₄[-13，-26，-27，-28，29]），对于F₂（X，Y，Z）=（N∧Y）∨（（?）X∧Z），根据命题2-2（b），若使F₂（x，0，z）=0且F₂（x，1，z）=1，当且仅当x=1，由充分条件a_5,17=1 and b_4,17=1得到F₂(a_a,17，b_4,17，c_4,17)=1且F₂(a_5,17，（?）b_4,17，c_4,17)=0。所以变量输出差分为△d₅[24，25，-26]=-2²³。充分条件d_5,24=0，d_5,25=0，d_5,26=1确保d′₅=d₅[24，25，-26]。对于RIPEMD-128算法后三圈攻击的每步操作中得到充分条件的过程见表4．3和表4．4。满足差分特征的左右两路的充分条件见表4．5和4．6。通过以上过程，左路中产生了4-33步的一个内部碰撞，右路中产生了9-36步的一个内部碰撞。第三步对于明文M，通过简单明文修改技术，可以减少第一圈的充分条件，再通过高级明文修改技术，可以减少更多条件，并保证差分路线正确，且条件不产生矛盾，可将充分条件分别降为19和36个，总计55个。根据以上的攻击过程，我们可以以2^-55的碰撞概率，找到后三圈RIPEMD-128算法的碰撞，低于生日攻击的2^-64的碰撞概率。由于RIPEMD-128算法的由两条平行的操作组成，且其圈函数不同于其他标准Hash函数算法，所以找到该算法的碰撞路线及其满足给路线的充分条件都是比较困难的，本文中给出的攻击结果是首次对RIPEMD-128算法后三圈攻击的结果。第五章中，我们的分析基于对MD4算法的攻击。首先，给出差分路线。选择两个明文：M=(m₀，m₁，…，m₁₅]，M′=(m′₀，m′₁，…，m′₁₅)。则明文差分定义为：△M=M′-M=(△m₀，△m₁，…，△m₁₅)。在我们的攻击中，选择明文差分为：△m₇=2²¹，△mi=0，0≤i≤15，i≠7。表5．1给出了差分特征和差分路线。其次，根据圈函数的性质，表5．2给出了满足差分特征的所有充分条件。我们可以以概率为2^-54找到一个几乎碰撞。最后，我们利用MD4算法的几乎碰撞，对HMAC-MD4内部函数进行区分攻击和部分密钥恢复攻击。对于区分攻击，我们需要2⁵⁴ HMAC-MD4内部函数的消息对，得到0.63(1-e^-1)的成功概率。后者，从表5．2中，只有满足所有充分条件，才能得到几乎碰撞，通常，认为知道连续的四个链变量的值，可以将密钥恢复出来。我们可以利用（d₄[-7]，a₄，b₃[-28，-29，-30，-31，32]，c₃）中已知的22比特，通过穷尽搜索其余106比特，恢复出HMAC-MD4内部函数的密钥。