C++博客-无题http://www.cppblog.com/forxidian/zh-cnThu, 09 Apr 2026 05:38:19 GMTThu, 09 Apr 2026 05:38:19 GMT60KMP算法详解【转】http://www.cppblog.com/forxidian/archive/2010/04/07/111885.htmlMoonlitMoonlitWed, 07 Apr 2010 11:24:00 GMThttp://www.cppblog.com/forxidian/archive/2010/04/07/111885.htmlhttp://www.cppblog.com/forxidian/comments/111885.htmlhttp://www.cppblog.com/forxidian/archive/2010/04/07/111885.html#Feedback0http://www.cppblog.com/forxidian/comments/commentRss/111885.htmlhttp://www.cppblog.com/forxidian/services/trackbacks/111885.html如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。

    我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”
    解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多“最坏情况”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设 m<=n），即传说中的KMP算法。
    之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。这时，或许你突然明白了AVL 树为什么叫AVL，或者Bellman-Ford为什么中间是一杠不是一个点。有时一个东西有七八个人研究过，那怎么命名呢？通常这个东西干脆就不用人名字命名了，免得发生争议，比如“3x+1问题”。扯远了。
    个人认为KMP是最没有必要讲的东西，因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到“移动(shift)”、“Next函数”等概念，这非常容易产生误解（至少一年半前我看这些资料学习KMP时就没搞清楚）。在这里，我换一种方法来解释KMP算法。

    假如，A="abababaababacb"，B="ababacb"，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B = a b a b a c b
    j = 1 2 3 4 5 6 7

    此时，A[6]<>B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j'。j'可能是多少呢？仔细想一下，我们发现，j'必须要使得B[1..j]中的头j'个字母和末j'个字母完全相等（这样j变成了j'后才能继续保持i和j的性质）。这个j'当然要越大越好。在这里，B [1..5]="ababa"，头3个字母和末3个字母都是"aba"。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了 4：

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =     a b a b a c b
    j =     1 2 3 4 5 6 7

    从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
    再后来，A[7]=B[5]，i和j又各增加1。这时，又出现了A[i+1]<>B[j+1]的情况：

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =     a b a b a c b
    j =     1 2 3 4 5 6 7

    由于P[5]=3，因此新的j=3：

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =         a b a b a c b
    j =         1 2 3 4 5 6 7

    这时，新的j=3仍然不能满足A[i+1]=B[j+1]，此时我们再次减小j值，将j再次更新为P[3]：

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =             a b a b a c b
    j =             1 2 3 4 5 6 7

    现在，i还是7，j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样，j必须减小到P[1]，即0：

    i = 1 2 3 4 5 6 7 8 9 ……
    A = a b a b a b a a b a b …
    B =               a b a b a c b
    j =             0 1 2 3 4 5 6 7

    终于，A[8]=B[1]，i变为8，j为1。事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1]（比如A[8]="d"时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A[i]=B[1]为止。
    这个过程的代码很短（真的很短），我们在这里给出：

j:=0;
for i:=1 to n do
begin
   while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
   if B[j+1]=A[i] then j:=j+1;
   if j=m then
   begin
      writeln('Pattern occurs with shift ',i-m);
      j:=P[j];
   end;
end;

    最后的j:=P[j]是为了让程序继续做下去，因为我们有可能找到多处匹配。
    这个程序或许比想像中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串A，并更新可以匹配到B的什么位置。

    现在，我们还遗留了两个重要的问题：一，为什么这个程序是线性的；二，如何快速预处理P数组。
    为什么这个程序是O(n)的？其实，主要的争议在于，while循环使得执行次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略，简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行了n次。按照摊还分析的说法，平摊到每次for循环中后，一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。
    预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通过P[1],P[2],...,P[j-1]的值来获得P[j]的值。对于刚才的B="ababacb"，假如我们已经求出了P[1],P[2],P[3]和P[4]，看看我们应该怎么求出P[5]和P[6]。P[4]=2，那么P [5]显然等于P[4]+1，因为由P[4]可以知道，B[1,2]已经和B[3,4]相等了，现在又有B[3]=B[5]，所以P[5]可以由P[4] 后面加一个字符得到。P[6]也等于P[5]+1吗？显然不是，因为B[ P[5]+1 ]<>B[6]。那么，我们要考虑“退一步”了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到，即是否P[6]=P[ P[5] ]+1。这里想不通的话可以仔细看一下：

        1 2 3 4 5 6 7
    B = a b a b a c b
    P = 0 0 1 2 3 ?

    P[5]=3是因为B[1..3]和B[3..5]都是"aba"；而P[3]=1则告诉我们，B[1]、B[3]和B[5]都是"a"。既然P[6]不能由P[5]得到，或许可以由P[3]得到（如果B[2]恰好和B[6]相等的话，P[6]就等于P[3]+1了）。显然，P[6]也不能通过P[3]得到，因为B[2]<>B[6]。事实上，这样一直推到P[1]也不行，最后，我们得到，P[6]=0。
    怎么这个预处理过程跟前面的KMP主程序这么像呢？其实，KMP的预处理本身就是一个B串“自我匹配”的过程。它的代码和上面的代码神似：

P[1]:=0;
j:=0;
for i:=2 to m do
begin
   while (j>0) and (B[j+1]<>B[i]) do j:=P[j];
   if B[j+1]=B[i] then j:=j+1;
   P[i]:=j;
end;

    最后补充一点：由于KMP算法只预处理B串，因此这种算法很适合这样的问题：给定一个B串和一群不同的A串，问B是哪些A串的子串。

    串匹配是一个很有研究价值的问题。事实上，我们还有后缀树，自动机等很多方法，这些算法都巧妙地运用了预处理，从而可以在线性的时间里解决字符串的匹配。我们以后来说。

    昨天发现一个特别晕的事，知道怎么去掉BitComet的广告吗？把界面语言设成英文就行了。
    还有，金山词霸和Dr.eye都可以去自杀了，Babylon素王道。

Matrix67原创
转贴请注明出处

Moonlit 2010-04-07 19:24 发表评论
]]>MD5破译技术综述【转】http://www.cppblog.com/forxidian/archive/2010/04/05/MD5crackme.htmlMoonlitMoonlitSun, 04 Apr 2010 17:51:00 GMThttp://www.cppblog.com/forxidian/archive/2010/04/05/MD5crackme.htmlhttp://www.cppblog.com/forxidian/comments/111638.htmlhttp://www.cppblog.com/forxidian/archive/2010/04/05/MD5crackme.html#Feedback0http://www.cppblog.com/forxidian/comments/commentRss/111638.htmlhttp://www.cppblog.com/forxidian/services/trackbacks/111638.html

这几天看了些关于MD5的资料，林林总总，汇总如下。

虽然努力了不少时间，但中间的硬骨头（破译的数学原理）还是没能消化，所以中间的原理部分，建议直接去读论文啊。

由于自己写综述的水平尚处于初级阶段（堆积资料+没有骨头），难免错误，大家多指正啊。

==================================

MD5破译技术综述

2008210759 陈凤娟 chenfj04@gmail.com 2009/4/14

摘要

本文简要分析了MD5算法的安全性，阐述了碰撞攻击（Collision Attack）方面的破译手段。重点分析王小云教授等在2004年发表的MD5破译算法的原理、局限、影响等，并以一个应用实例描述了如何利用MD5碰撞进行攻击，最后总结了MD5破译技术的发展和最新进展。

一、MD5的安全性分析

MD5是由Ronald Lynn Rivest于1992提出来的一种散列算法(Hash function) ，它的作用是将一个任意长度的消息散列成一串固定长度(比如128byte)的数字信息，称为散列值(或哈希值、消息摘要)。

MD5产生报文摘要的过程如下：

image

MD5算法有四轮，每轮16次迭代，单步流程如下：

image

一个安全的散列算法具有如下特点：

（1）仅从散列值无法反推出原信息；

（2）两个不同数字信息产生同样的散列值的概率是非常小的，几乎为零；

（3）原信息的微小改变（哪怕只改变一位），将导致散列值的很大变化。

对于特点（2），需要明确的是，散列算法是一个将无穷维空间的信息映射到有限维空间的变换，不是一个一一映射。实际上一个散列值可能对应有无穷多个数字信息，换言之，会有无穷多个数字信息产生同样一个散列值。产生相同散列值的两个不同的消息被称为碰撞（Collision），所以，散列函数存在碰撞是必然的。我们定义一个“安全”的散列算法，主要是指在以下三种意义上是“计算安全”的：

Ø 其一：//Preimage Attack（原像攻击）

给定明文M1，找到另一明文M2(不等于M1），使得hash(M1)=hash(M2)；

Ø 其二： //Second Preimage Attack（次原像攻击）

给定明文M1，找到另一明文M2(不等于M1），使得hash(M1)=hash(M2)；

Ø 其三：//Collision Attack(碰撞攻击)

找到两个不同的M1和M2，使得hash(M1)=hash(M2)。

对于原像攻击（Preimage Attack），实际应用中最常见的是采用“字典法”，将明文和密文对存储起来，使用时只需查询出来即可。这种方法看似技术含量不高，事实上确实最具威胁性。目前互联网上已经有近百个此类查询站点了。

对于次原像攻击（Second Preimage Attack），目前密码学界尚未有突破性进展，可以认为是MD5算法是“计算安全”的。

下文重点讨论碰撞攻击。散列算法的安全性从理论上来说与消息摘要的长度是成正比的，对于具有128位消息摘要的MD5，理论上要找到一对碰撞的时间复杂度是O(2^N)，基本是不可行的。也因此MD5曾一度被认为牢不可破，是安全的，加之MD5算法简单紧凑，易于实现，因而被广泛应用在各类安全协议或应用程序中。

各国著名密码学家、数学家和顶级黑客们对MD5进行了多年的密码学分析和攻击，提出了著名的“生日攻击”（Birthday Attack）、“代数攻击”（Algebraic Attack）等手段。根据“生日攻击”的数学原理 ，寻找散列函数的碰撞对的复杂度可以降至1.25*2^（N/2）。

2004年的Crypto2004会议上，王小云教授做了关于破译 MD5、HAVAL-128、 MD4和RIPEMD算法的报告，提出一种可在1个小时左右找到MD5 Collision的方法，将复杂度降为了2^39。王小云、冯登国、来学嘉、于红波四人共同完成的文章，囊括了对MD5、HAVAL-128、 MD4和RIPEMD四个著名HASH算法的破译结果【2】。会上，世界信息安全方面的专家们对王小云教授等人的论文给予高度评价。MD5的设计者Ronald Rivest在邮件中写道：“这些结果无疑给人非常深刻的印象，她应当得到我最热烈的祝贺。当然，我并不希望看到MD5就这样倒下，但人必须尊崇真理。”随后，国外的许多密码专家对王小云等的算法进行分析和应用实践的研究。待王等的破译算法的细节【3】发表后，更多的改进算法也被提出来。

二、MD5破译原理

Ø 原理

下面简略分析王小云等MD5破译的原理，更多细节和数学证明请参考【3】。

王小云等人的破译算法可以找到一对碰撞两个1024bit的消息M1和M2，使MD5(M1) = MD5(M2)

其中M1=M||N 和 M2 = M’||N’

M’=M+C1 //C1是预定义的常数向量；

N’ = N+C2 // C2 = -C1 mod 232

找到block M（512bit）（即iteration 1）用IBM P690大型机需要约1个小时的时间；找到block N（512tit）（即iteration 2）只需15s到5min。算法适用于对任意给定的IV0。

image

该算法使用的是“差分攻击”（differential attack），有两种差分方式：

一种是“整数模减”（integer modular subtraction），即(A-B) mod 232；一种是异或（XOR），即A XOR B。

破译有二次iteration：

（1）任选一个M0消息，藉由修改消息技术，其中含Single-message Modification(符合MD5前16个step所有的condition)及Mulit-message Modification(符合MD5前32个steps部份的condition)两部份。把M0消息，对每个step的前14个words只需使用一次single-message modification，而最后两个words只需使用二次single-message modification运算，经处理后会产生，并可藉由MD5 Hash公式所有可能发生的differential位表内，测试所有保留的特性，以精确地的找到第一个block M。

（2）任选一个M1消息，藉由修改消息技术后，和iteration1产生的第一个block M运算处理后会产生，亦即发生collision情况，接着再测试是否发生collision，以得到结果。

其中“差分攻击”的作用是：可以找到两次iteration的collision；可以有更多的给予differential值的限制；可以找到足够可能differential的状况；可以使用modification技术改善collision发生机率。简单的说是让两个message(1024bits)在运算后，更有效率产生差分结果为0的值(也就是产生collision情况)。

Ø 算法的局限性：

王小云教授的破解算法是一个概率性的破解算法，只对部分信息集合适用。2004年10月，Hawks等人通过原始数据，分析了王的MD5破解方法，他们得出来已公布的碰撞对满足的差分模式，并解释了要满足这种差分模式消息需要满足的一系列条件——ft-和Tt-条件（多于200条）。

根据MD5破解算法，对一个信息A及其散列值H，我们有可能推出另一个信息B，它的MD5散列值也是H。现在的问题是，如果A是一个符合预先约定格式的、有一定语义的信息，那么推出的信息B将不是一个符合约定格式、有语义的信息。比如说，A是一个Word文档的、有语义的电子合同，而B却不可能是一个刚好符合Word格式的文档，只能是一堆乱码，也就是说，B不可能是一个有效的、有意义的并且符合伪造者期望的电子合同。再比如说，A是一个符合X509格式的数字证书，那么我们推出的B不可能刚好也是一个符合X509格式而且是伪造者希望的数字证书。

还有我们知道，电子合同是需要双方、甚至多方电子签名的。对于双方签名，这相当于我们先产生A的散列值H1，然后对A和H1合起来的信息进一步产生散列值H2。我们目前的研究发现还无法找到一个方法，推出一个信息B刚好产生同样的H1和H2。

Ø MD5应用改进策略

寻找一个MD5的碰撞已经解决了，那一组呢？就不那么容易了，在找不到更合适的替代算法之前，不妨使用以下方案：

散列向量组，具体的办法是依次取Message内容的一半，或者特定交叉部分，形成一个散列向量组来替代原来的散列值。

Ø 影响：

理论上，王小云教授等对MD5算法的破解，找到一对碰撞（Collision）不需要理论上的2^64次MD5运算，而只需要2^39次MD5运算。这个意味在MD5在防止Collision攻击方面已是“计算不安全”。

实际应用中，由于王小云等的破解算法并不能够为已知明文M1找到和它散列值一样的M2（即次原像攻击），只是较快地找到了一对碰撞——可能是没有任何现实意义的两个数，并不能够直接利用。然而进一步利用找到的MD5 Collision精心构造恶意程序或进行商业诈骗已是可能（见第三部分实战应用），严重威胁信息系统安全，使目前广泛应用的电子签名的技术体系和法律效力受到挑战。将来，随着计算速度的加快，散列算法的更换是不可避免的，由此带来系统重建等成本将是非常大的。

总之，这里MD5算法的破解对实际应用的冲击要远远小于它的理论意义，不会造成PKI、数字签名认证体系的崩溃（由于破解算法的局限性和散列算法应用方式的改进）。王小云教授的算法是密码学安全界的一场地震。

三、MD5碰撞的实战应用

现在，用笔记本在1个小时之内就能找到MD5的collision。这意味着什么？有很多人认为collision毫无意义，因为在实际应用中M1和M2无法任意指定。其实这是只知其一不知其二。和其他流行的HASH算法一样，MD5有一个众所周知的弱点，叫做长度拓展（length extension），即：

若MD5(M1) = MD5(M2) 则MD5(M1||M’) = MD5(M2||M’)     其中||代表串连接。

目前的collision搜索算法可以任意指定初始hash状态，这意味着可任意构造前缀。另外length extension意味着可以任意构造后缀。因此基于任意一对碰撞R1和R2，我们可以构造出两个MD5 散列值相同的串，使得：

MD5(preamble+R1+suffix) = MD5(preamble+R2+suffix)，

其中，MD5(preamble+R1) = MD5(preamble+R2)

下面以如何利用MD5 Collision构造两个功能不同而MD5值相同的程序为例说明：

“Practical Attacks on Digital Signatures Using MD5 Message Digest【5】”一文阐述了对数字签名的实际攻击：利用一对MD5碰撞值，就能够构造出一系列具有相同Hash值的消息对或程序，并进一步被利用来在分布式系统中安装后门，甚至可以用于伪造证书。其基本原理图如下：

image

程序只需要通过比较data.pak中的第一块128byte的Colliding block进行比对，如果相等，后面的流程实现功能一，如果不相等实现功能二。这样就实现了任意功能的两个程序，并保持他们的MD5相同。基本代码流程如下，具体实例可参考【5】。

unsigned int MD5_CollisionOffset = MAGIC_OFFSET;

//colliding string的位置

unsigned int MD5_CollisionBitMask = MAGIC_BITMASK;

//两个Colliding string的不同bit的位置

bool decision()//比对两个Colliding string的不同位

{ return (

MD5_CollisionBlock[MD5_CollisionOffset] &

MD5_CollisionBitMask);

}

void some_function() //通过decision()来决定使用哪个文件

{

if (decision()) do_good_thing(); else do_bad_thing();

}

由此可以看出，利用MD5 Collision Attack可以构造是实际可行的攻击，而且实现上并不复杂；不过若想要真正有效，需要利用其他技术或社会工程之类的手段减少攻击程序的可疑性。

四、MD5破译技术研究动态

随着时间的推移，MD5安全性显得越来越脆弱了：

ü 1993: 找到两个不同初始向量IV可产生相同的散列值

ü 1996: 找到压缩函数（MD5中的主要函数）的碰撞

ü 2004: 利用生日攻击原理采用分布式系统成功破译MD5

ü 2004-8: 用IBM P690大型机在1个小时内找到MD5碰撞

ü 2005-3: 用笔记本在几个小时内找到MD5碰撞【4】

ü 2006-3: 用笔记本在1分钟内找到MD5碰撞（见【10】）

ü 2007-12: 用Chosen-Prefix Collision构造出可用的X.509证书

ü 2008: 荷兰的科学家实现了2个可执行文件的MD5碰撞

ü 2008-12：利用MD5碰撞，创造了一个假的来自可信CA的数字证书

ü 现在：互联网上有几百个站点提供MD5 Dictionary来反查MD5散列值

ü 互联网上还有“Rainbow Tables”来帮助破译MD5（见【9】）

自2004年王小云等的算法公布后，2005年，“Finding MD5 Collisions – a Toy For a Notebook”【4】中，利用大致与王的算法相同的Differential Attack思想，作者的团队用普通的笔记本只花了2min就找到M块，但他的算法中要找到N需要8hours。2006年， “Tunnels in Hash Functions: MD5 Collisions Within a Minute”【10】作者优化了寻找N块的算法，最终他的算法能在1min左右，用普通的笔记本就能找到MD5碰撞。 2006年，Efficient Hash Collision Search Strategies on Special-Purpose Hardware【6】综述了hash 碰撞搜索的三种策略，并给出了硬件设计方案进一步加速搜索。至此，寻找MD5 碰撞的算法的时间、空间复杂度都已降至实用水平，MD5破译技术的研究者们开始重点关注MD5 Collision的实际应用了。

事实上，早在2005年，On the possibility of constructing meaningful hash collisions for public keys【7】提出了一种利用MD5 Collision构造PKI证书的方法，并且构造出了两个散列值一样，而公钥不同X.509证书，以最直接的方式强调了现行PKI系统的脆弱性。2007年，Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities【12】中用特定前缀的MD5碰撞对，为不同ID构造出具有相同MD5值的X.509证书。 2008年12月，25th CCC（Chaos Communication Congress）会上，研究人员里用MD5碰撞创造假的数字证书认证（certificate authority），利用200台PS3，他们能在短时间破解SSL加密。安全研究人员利用200台PS3攻击MD5算法，创造了一个假的来自可信CA的数字证书。Perspectives for Cryptographic Long-term Security 【8】讨论在hash函数碰撞威胁下该如何改变PKI系统以抵御攻击。

一篇比较好的MD5碰撞数学原理的综述性文章是【11】，更多的破译技术动态资讯请参考，http://www.win.tue.nl/hashclash/.

五、结论

王小云教授的密码破译技术具有非常重要的理论意义，对密码学本身的发展具有一定的推动作用，为散列函数的密码分析学提供了一条道路。这一成果说明了MD5已经不能用身份验证或数字签名，另外在理论上说明了数字摘要算法用于数据的完整性鉴别具有缺陷。另一方面，由于方法上的限制，要构造具有特定语义的碰撞几乎是不可能的，因此并不是所有的采用MD5算法的应用都因此彻底失效。在实际中，MD5和SHA-1算法经常与其它算法一起使用，或者进行了很多变形，简单地找到MD5碰撞对并没有实际性的威胁；然而，若是将MD5碰撞对和其他技术结合起来，就有可能构造出威胁性很大的攻击来。

既王小云教授的开创性工作之后，MD5碰撞的研究成了一个不小的热点。国内外学者的研究集中在了寻找更快的MD5碰撞算法、利用MD5碰撞进行实际应用、以及当前PKI、数字签名等安全技术与系统应对MD5等散列算法的碰撞威胁方面的对策三个方面。

可以预见的是密码算法或散列算法的设计者和破译者都将面对越来越tough and tense的挑战！

六、参考资料

【1】 生日攻击http://en.wikipedia.org/wiki/Birthday_attack

【2】 Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD，王小云、冯登国、来学嘉、于红波，Crypto’2004

【3】 How to Break MD5 and other Hash Functions，王小云等，2004

【4】 Finding MD5 Collisions--a Toy For a Notebook, Vlastimil Klíma, 2005.3

【5】 Practical Attacks on Digital Signatures Using MD5 Message Digest, Ondrej Mikle, 2004 http://crypto-world.info/klima/2004/MD5-POC.pdf

【6】 On the possibility of constructing meaningful hash collisions for public keys, Arjen Lenstra and Benne de Weger, 2005

【7】 Efficient Hash Collision Search Strategies on Special-Purpose Hardware，Sven Schäge, 2006.12

【8】 Perspectives For Cryptographic Long-term Security, Johannes Buchmann, Alexander May, Ulrich Vollmer

【9】 Attacks on MD5 Hashed Passwords, Antony G. Robertiello, Kiran A. Bandla, 2005

【10】 Tunnels in Hash Functions: MD5 Collisions Within a Minute, Vlastimil Klima 2006.4

http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip 
http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5_source.zip

【11】 On Collisions for MD5, Master Thesis of Marc M.J. Stevens, 2007.7

【12】 Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities, 2007, EruoCrpt07 Proceedings

http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/

【13】 MD5 Collision create rouge Certificate Authority

http://www.crunchgear.com/2008/12/30/md5-collision-creates-rogue-certificate-authority/

【14】 The MD5 Message Digest Algorithm, RFC1321, April 1992, Ronald Rivest,

ftp://ftp.rfc-editor.org/in-notes/rfc1321.txt

【15】 网络安全课程课件，第三讲--密码技术与应用，段海新

七、附录：MD5碰撞对实例

例1：MD5碰撞实例，标准初始向量IV0

IV0:

context->state[0] = 0×67452301;

context->state[1] = 0xefcdab89;

context->state[2] = 0×98badcfe;

context->state[3] = 0×10325476;

First message:

0xA6,0×64,0xEA,0xB8,0×89,0×04,0xC2,0xAC,

0×48,0×43,0×41,0×0E,0×0A,0×63,0×42,0×54,

0×16,0×60,0×6C,0×81,0×44,0×2D,0xD6,0×8D,

0×40,0×04,0×58,0×3E,0xB8,0xFB,0×7F,0×89,

0×55,0xAD,0×34,0×06,0×09,0xF4,0xB3,0×02,

0×83,0xE4,0×88,0×83,0×25,0×71,0×41,0×5A,

0×08,0×51,0×25,0xE8,0xF7,0xCD,0xC9,0×9F,

0xD9,0×1D,0xBD,0xF2,0×80,0×37,0×3C,0×5B,

0×97,0×9E,0xBD,0xB4,0×0E,0×2A,0×6E,0×17,

0xA6,0×23,0×57,0×24,0xD1,0xDF,0×41,0xB4,

0×46,0×73,0xF9,0×96,0xF1,0×62,0×4A,0xDD,

0×10,0×29,0×31,0×67,0xD0,0×09,0xB1,0×8F,

0×75,0xA7,0×7F,0×79,0×30,0xD9,0×5C,0xEB,

0×02,0xE8,0xAD,0xBA,0×7A,0xC8,0×55,0×5C,

0xED,0×74,0xCA,0xDD,0×5F,0xC9,0×93,0×6D,

0xB1,0×9B,0×4A,0xD8,0×35,0xCC,0×67,0xE3.

Second message:

0xA6,0×64,0xEA,0xB8,0×89,0×04,0xC2,0xAC,

0×48,0×43,0×41,0×0E,0×0A,0×63,0×42,0×54,

0×16,0×60,0×6C,0×01,0×44,0×2D,0xD6,0×8D,

0×40,0×04,0×58,0×3E,0xB8,0xFB,0×7F,0×89,

0×55,0xAD,0×34,0×06,0×09,0xF4,0xB3,0×02,

0×83,0xE4,0×88,0×83,0×25,0xF1,0×41,0×5A,

0×08,0×51,0×25,0xE8,0xF7,0xCD,0xC9,0×9F,

0xD9,0×1D,0xBD,0×72,0×80,0×37,0×3C,0×5B,

0×97,0×9E,0xBD,0xB4,0×0E,0×2A,0×6E,0×17,

0xA6,0×23,0×57,0×24,0xD1,0xDF,0×41,0xB4,

0×46,0×73,0xF9,0×16,0xF1,0×62,0×4A,0xDD,

0×10,0×29,0×31,0×67,0xD0,0×09,0xB1,0×8F,

0×75,0xA7,0×7F,0×79,0×30,0xD9,0×5C,0xEB,

0×02,0xE8,0xAD,0xBA,0×7A,0×48,0×55,0×5C,

0xED,0×74,0xCA,0xDD,0×5F,0xC9,0×93,0×6D,

0xB1,0×9B,0×4A,0×58,0×35,0xCC,0×67,0xE3.

Common MD5 hash:

0×2B,0xA3,0xBE,0×5A,0xA5,0×41,0×00,0×6B,

0×62,0×37,0×01,0×11,0×28,0×2D,0×19,0xF5.

例2：MD5碰撞实例，任意选定IV

IV0:

context->state[0] = 0xabaaaaaa;

context->state[1] = 0xaaacaaaa;

context->state[2] = 0xaaaadaaa;

context->state[3] = 0xaaaaaaea;

First message:

0×9E,0×83,0×2A,0×4C,0×95,0×64,0×5E,0×2B,

0×2E,0×1B,0xB0,0×70,0×47,0×1E,0xBA,0×13,

0×7F,0×1A,0×53,0×43,0×22,0×34,0×25,0xC1,

0×40,0×04,0×58,0×3E,0xB8,0xFB,0×7F,0×89,

0×55,0xAD,0×34,0×06,0×09,0xF4,0xB3,0×02,

0×83,0xE4,0×88,0×83,0×25,0×71,0×41,0×5A,

0×08,0×51,0×25,0xE8,0xF7,0xCD,0xC9,0×9F,

0xD9,0×1D,0xBD,0xF2,0×80,0×37,0×3C,0×5B,

0×89,0×62,0×33,0xEC,0×5B,0×0C,0×8D,0×77,

0×19,0xDE,0×93,0xFA,0xA1,0×44,0xA8,0xCC,

0×56,0×91,0×9E,0×47,0×00,0×0C,0×00,0×4D,

0×40,0×29,0xF1,0×66,0xD1,0×09,0xB1,0×8F,

0×75,0×27,0×7F,0×79,0×30,0xD5,0×5C,0xEB,

0×42,0xE8,0xAD,0xBA,0×78,0xCC,0×55,0×5C,

0xED,0xF4,0xCA,0xDD,0×5F,0xC5,0×93,0×6D,

0xD1,0×9B,0×0A,0xD8,0×35,0xCC,0xE7,0xE3.

Second message:

0×9E,0×83,0×2A,0×4C,0×95,0×64,0×5E,0×2B,

0×2E,0×1B,0xB0,0×70,0×47,0×1E,0xBA,0×13,

0×7F,0×1A,0×53,0xC3,0×22,0×34,0×25,0xC1,

0×40,0×04,0×58,0×3E,0xB8,0xFB,0×7F,0×89,

0×55,0xAD,0×34,0×06,0×09,0xF4,0xB3,0×02,

0×83,0xE4,0×88,0×83,0×25,0xF1,0×41,0×5A,

0×08,0×51,0×25,0xE8,0xF7,0xCD,0xC9,0×9F,

0xD9,0×1D,0xBD,0×72,0×80,0×37,0×3C,0×5B,

0×89,0×62,0×33,0xEC,0×5B,0×0C,0×8D,0×77,

0×19,0xDE,0×93,0xFA,0xA1,0×44,0xA8,0xCC,

0×56,0×91,0×9E,0xC7,0×00,0×0C,0×00,0×4D,

0×40,0×29,0xF1,0×66,0xD1,0×09,0xB1,0×8F,

0×75,0×27,0×7F,0×79,0×30,0xD5,0×5C,0xEB,

0×42,0xE8,0xAD,0xBA,0×78,0×4C,0×55,0×5C,

0xED,0xF4,0xCA,0xDD,0×5F,0xC5,0×93,0×6D,

0xD1,0×9B,0×0A,0×58,0×35,0xCC,0xE7,0xE3.

Common hash:

0xef,0×2e,0xae,0×54,0xe0,0×34,0×70,0×7c,

0xa2,0×6e,0xb0,0×9b,0×45,0xc7,0xe4,0×87.


转自http://course.ccert.edu.cn/blog/chenfengjuan



Moonlit 2010-04-05 01:51 发表评论
]]>