随笔档案

这几天看了些关于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产生报文摘要的过程如下：

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

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

（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 2³²

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

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

一种是“整数模减”（integer modular subtraction），即(A-B) mod 2³²；一种是异或（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值的消息对或程序，并进一步被利用来在分布式系统中安装后门，甚至可以用于伪造证书。其基本原理图如下：

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

由此可以看出，利用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月，25^th 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碰撞实例，标准初始向量IV₀

IV₀:

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

IV₀:

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