654321

MD5介绍以及如何破解MD5算法

详细可参考原⽂。

-------------------------------------------------------------------------------------------------------

MD5

全称是Message-DigestAlgorithm5（信息-摘要算法5），理论上是⼀种单向的哈希散列，

特性：

输⼊任意长度的信息，经过处理，输出为128位的⼤整数（数字指纹）（32位16进制数）；

不同的输⼊⼀般得到不同的结果（唯⼀性）；

根据128位的输出结果不可能反推出输⼊的信息（不可逆）；

强抗碰撞：想找到两个不同的数据，使它们具有相同的MD5值，是⾮常困难的。

MD5⽤途：

1、防⽌被篡改：

1）⽐如发送⼀个电⼦⽂档，发送前，我先得到MD5的输出结果a。然后在对⽅收到电⼦⽂档后，对⽅也得到⼀个MD5的输出结果b。

如果a与b⼀样就代表中途未被篡改。

2）⽐如我提供⽂件下载，为了防⽌不法分⼦在安装程序中添加⽊马，我可以在⽹站上公布由安装⽂件得到的MD5输出结果。

3）SVN在检测⽂件是否在CheckOut后被修改过，也是⽤到了MD5.

2、防⽌直接看到明⽂：

现在很多⽹站在数据库存储⽤户的密码的时候都是存储⽤户密码的MD5值。这样就算不法分⼦得到数据库的⽤户密码的MD5值，也⽆

法知道⽤户的密码(其实这样是不安全的，后⾯我会提到)。（⽐如在UNIX系统中⽤户的密码就是以MD5（或其它类似的算法）经加密后存

储在⽂件系统中。当⽤户登录的时候，系统把⽤户输⼊的密码计算成MD5值，然后再去和保存在⽂件系统中的MD5值进⾏⽐较，进⽽确定

输⼊的密码是否正确。通过这样的步骤，系统在并不知道⽤户密码的明码的情况下就可以确定⽤户登录系统的合法性。这不但可以避免⽤户

的密码被具有系统管理员权限的⽤户知道，⽽且还在⼀定程度上增加了密码被破解的难度。）

3、防⽌抵赖（数字签名）：

这需要⼀个第三⽅认证机构。例如A写了⼀个⽂件，认证机构对此⽂件⽤MD5算法产⽣摘要信息并做好记录。若以后A说这⽂件不是他

写的，权威机构只需对此⽂件重新产⽣摘要信息，然后跟记录在册的摘要信息进⾏⽐对，相同的话，就证明是A写的了。这就是所谓的“数

字签名”。

MD5算法过程：

对MD5算法简要的叙述可以为：MD5以512位分组来处理输⼊的信息，且每⼀分组⼜被划分为16个32位⼦分组，算法的输出由四个

32位分组组成，将这四个32位分组级联后将⽣成⼀个128位散列值。基本操作，求余、取余、调整长度、与链接变量进⾏循环运算。

第⼀步、填充：如果输⼊信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余的结果等于448。填充的⽅法是填充⼀

个1和n个0。填充完后，信息的长度就为N*512+448(bit)；

第⼆步、记录信息长度：⽤64位来存储填充前信息长度。这64位加在第⼀步结果的后⾯，这样信息长度就变为N512+448+64=

(N+1)512位。

**第三步、装⼊标准的幻数（四个整数）：**标准的幻数（物理顺序）是（A=(01234567)16，B=(89ABCDEF)16，C=

(FEDCBA98)16，D=(76543210)16）。如果在程序中定义应该是

（A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L）。

第四步、四轮循环运算：循环的次数是分组的个数（N+1）

MD5安全性：

-------------------------------------------------------------------------------------------------------

⼩明：⽼师，上次您讲了MD5算法。⽤它⽣成的信息摘要，真的可以被破解吗？

⽼师：有很多种⽅法可以破解，不过需要明确⼀点，这⾥所谓的破解，并⾮把摘要还原成原⽂。为什么呢？因为固定128位的摘要是有穷

的，⽽原⽂数量是⽆穷的，每⼀个摘要都可以由若⼲个原⽂通过Hash得到。

⼩明：如果是这样的话，⽹上所说的MD5破解到底是怎么回事呢？

⽼师：对于MD5的破解，实际上都属于【碰撞】。⽐如原⽂A通过MD5可以⽣成摘要M，我们并不需要把X还原成A，只需要找到原⽂B，

⽣成同样的摘要M即可。

设MD5的哈希函数是H（X），那么：

H(A)=M

H(B)=M

任意⼀个B即为破解结果。

B有可能等于A，也可能不等于A。

⽤⼀个形象的说法，A和B的MD5结果“殊途同归”。

MD5碰撞通常⽤于登陆密码的破解。应⽤系统的数据库中存储的⽤户密码通常都是原密码的MD5哈希值，每当⽤户登录时，验签过程如

下：

如果我们得到了⽤户ABC的密码哈希值E10ADC3949BA59ABBE56E057F20F883E，并不需要还原出原密码123456，只需要“碰

撞”出另⼀个原⽂654321（只是举例）即可。登录时，完全可以使⽤654321作为登陆密码，欺骗过应⽤系统的验签。

⼩明：那么，具体如何来实现MD5摘要的碰撞呢？

⽼师：MD5碰撞的⽅法有很多，主要包括暴⼒枚举法、字典法、彩虹表法等等。

暴⼒枚举法：

⽼师：暴⼒枚举法顾名思义，就是简单粗暴地枚举出所有原⽂，并计算出它们的哈希值，看看哪个哈希值和给定的信息摘要⼀致。这种⽅法

虽然简单，但是时间复杂度极⾼。想象⼀下，仅仅长度8位的密码就有多少种排列组合的可能性？

⼩明：只考虑⼤⼩写字母和数字，每⼀位有62种可能，那么8位密码的排列组合就是62的8次⽅，21834，约等于⼆百万

亿！

⽼师：是的，这样的数据量如果使⽤普通的单机来破解，恐怕头发⽩了也破解不完。不过，我们也可以做⼀些取巧，优先尝试⽣⽇和有意义

的单词，这样就可以把穷举范围缩⼩很多。

字典法：

⽼师：如果说暴⼒枚举法是ongoing时间换空间，那么字典法则是⽤空间换时间。⿊客利⽤⼀个巨⼤的字典，存储尽可能多的原⽂和对应的

哈希值。每次⽤给定的信息摘要查找字典，即可快速找到碰撞的结果。

不过，这样做虽然每次破解速度很快，但是⽣成字典需要巨⼤的空间。仍然以8位密码举例，需要多⼤空间呢？

⼩明：刚才计算过有21834种可能性，每⼀对映射占192（128+64）bit。那么⼤约需要4.65PB的存储空间。

⽼师：没错，这样做的存储成本实在太⼤了。当然，我们同样可以取巧，优先存储那些常⽤的密码及其摘要。

⼩明：那么，有没有什么⽅法可以做到时间和空间的均衡呢？

⽼师：有⼀种⽅法可以，那就是下⾯我要介绍的【彩虹表发】。

彩虹表法：

⽼师：彩虹表法可以说是对字典法的优化，它采⽤了⼀种有趣的数据结构：【彩虹表】。在学习彩虹表之前，我们先来了解两个基本函数：

H(X)和R(X)。

H（X）：⽣成信息摘要的哈希函数，⽐如MD5，⽐如SHA256。

R（X）：从信息摘要转换成另⼀个字符串的衰减函数（Reduce）。其中R（X）的定义域是H（X）的值域，R（X）的值域是H（X）的

定义域。但要注意的是，R（X）并⾮H（X）的反函数。

通过交替运算H和R若⼲次，可以形成⼀个原⽂和哈希值的链条。假设原⽂是aaaaaa，哈希值长度32bit，那么哈希链表就是下⾯的样⼦：

这个链条有多长呢？假设H（X）和R（X）的交替重复K次，那么链条长度就是2K+1。同时，我们只需把链表的⾸段和末端存⼊哈希表

中：

⼩明：这什么跟什么啊，衰减函数和哈希链条，到底是⼲什么⽤的？

⽼师：别急，我们来演⽰⼀次破解过程，你就明⽩它们的意义了。

给定信息摘要：920ECF10

如何得到原⽂呢？只需进⾏R（X）运算：

R（920ECF10）=kiebgt

查询哈希表可以找到末端kiebgt对应的⾸端是aaaaaa，因此摘要920ECF10的原⽂“极有可能”在aaaaaa到kiebgt的这个链条当中。

接下来从aaaaaa开始，重新交替运算R（X）与H（X），看⼀看摘要值920ECF10是否是其中⼀次H（X）的结果。从链条看来，答案是

肯定的，因此920ECF10的原⽂就是920ECF10的前置节点sgfnyd。

需要补充的是，如果给定的摘要值经过⼀次R（X）运算，结果在哈希表中找不到，可以继续交替H（X）R（X）直到第K次为⽌。

简单来说，哈希链表代表了⼀组映射关系，其中每组包含K对映射，但只需要存储链条⾸位两个字符串。假设K=10，那么存储空间只有全

量字典的⼗分之⼀，代价则是破解⼀个摘要的运算次数也提⾼了⼗倍。这就是时间和空间的取舍。虽然做了取舍，但是哈希链条存在⼀个致

命的缺陷：R（X）函数的可靠性。虽然我们尽量把R（X）设计成结果均匀分布的函数，但是再完美的函数也难免会有碰撞的情况，⽐如下

⾯这样：

给定信息摘要：FB107E70

经过多次R（X），H（X）运算，得到结果kiebgt

通过哈希表查找末端kiebgt，可以找出⾸端aaaaaa

但是，FB107E70并不在aaaaaa到kiebgt的哈希链条当中，这就是R（X）的碰撞造成的。

这个问题看似没什么影响，既然找不到就重新⽣成⼀组⾸尾映射即可。但是想象⼀下，当K值较⼤的时候，哈希链很长，⼀旦两条不同的哈

希链在某个节点出现碰撞，后⾯所有的明⽂和哈希值全都变成了⼀⽑⼀样的值。

这样造成的后果就是冗余存储。原本两条哈希链可以存储2K个映射，由于重复，真正存储的映射数量不⾜2K。

这个时候，我们设计了彩虹表。彩虹表对哈希链进⾏了改进，把原先的R（X）的函数改进成从R1（X）到Rk（X）⼀共K个衰减函数。这

样⼀来虽然也可能发⽣碰撞，但是碰撞只会发⽣在同⼀级运算，如R1和R1碰撞，R3和R3碰撞，⼤⼤减⼩了存储重复的⼏率。

⼩明：好复杂，听的头都晕了。那想要破解MD5算法，有没有⽐彩虹表更厉害的⽅法呢？

⽼师：还真有。

2004年，王⼩云教授提出了⾮常⾼效的MD5碰撞⽅法。

2009年，冯登国、谢涛利⽤差分攻击，将MD5的碰撞算法复杂度进⼀步降低。

有兴趣的⼩伙伴可以通过资料进⾏更深⼊的学习。

⼏点补充：

对于单机来说，暴⼒枚举法的时间成本很⾼，字典法的空间成本很⾼。但是利⽤分布式计算和分布式存储，仍然可以有效破解MD5算法。

因此这两种⽅法同样被⿊客们⼴泛使⽤。