深圳官方网站建设,厦门方易网站制作有限公司,上海企业网络维护,福建网站建设公转载自 玻璃猫 程序员小灰
在之前的漫画中#xff0c;我们介绍了MD5算法的基本概念和底层原理#xff0c;没看过的小伙伴们可以点击下面的链接#xff1a;《漫画#xff1a;什么是MD5算法#xff1f;》
这一次#xff0c;我们来讲解如何破解MD5算法。 设MD5的哈希函数是…转载自 玻璃猫 程序员小灰
在之前的漫画中我们介绍了MD5算法的基本概念和底层原理没看过的小伙伴们可以点击下面的链接《漫画什么是MD5算法》
这一次我们来讲解如何破解MD5算法。 设MD5的哈希函数是HX那么
H(A) M
H(B) M
任意一个B即为破解结果。
B有可能等于A也可能不等于A。
用一个形象的说法A和B的MD5结果“殊途同归”。
MD5碰撞通常用于登陆密码的破解。应用系统的数据库中存储的用户密码通常都是原密码的MD5哈希值每当用户登录时验签过程如下 如果我们得到了用户ABC的密码哈希值E10ADC3949BA59ABBE56E057F20F883E并不需要还原出原密码123456只需要“碰撞”出另一个原文654321只是举例即可。登录时完全可以使用654321作为登陆密码欺骗过应用系统的验签。 暴力枚举法 字典法 彩虹表法 HX生成信息摘要的哈希函数比如MD5比如SHA256。
RX从信息摘要转换成另一个字符串的衰减函数Reduce。其中RX的定义域是HX的值域RX的值域是HX的定义域。但要注意的是RX并非HX的反函数。
通过交替运算H和R若干次可以形成一个原文和哈希值的链条。假设原文是aaaaaa哈希值长度32bit那么哈希链表就是下面的样子 这个链条有多长呢假设HX和RX的交替重复K次那么链条长度就是2K1。同时我们只需把链表的首段和末端存入哈希表中 给定信息摘要920ECF10
如何得到原文呢只需进行RX运算
R920ECF10 kiebgt
查询哈希表可以找到末端kiebgt对应的首端是aaaaaa因此摘要920ECF10的原文“极有可能”在aaaaaa到kiebgt的这个链条当中。
接下来从aaaaaa开始重新交替运算RX与HX看一看摘要值920ECF10是否是其中一次HX的结果。从链条看来答案是肯定的因此920ECF10的原文就是920ECF10的前置节点sgfnyd。 需要补充的是如果给定的摘要值经过一次RX运算结果在哈希表中找不到可以继续交替HXRX直到第K次为止。 给定信息摘要FB107E70
经过多次RXHX运算得到结果kiebgt
通过哈希表查找末端kiebgt可以找出首端aaaaaa
但是FB107E70并不在aaaaaa到kiebgt的哈希链条当中这就是RX的碰撞造成的。 这个问题看似没什么影响既然找不到就重新生成一组首尾映射即可。但是想象一下当K值较大的时候哈希链很长一旦两条不同的哈希链在某个节点出现碰撞后面所有的明文和哈希值全都变成了一毛一样的值。
这样造成的后果就是冗余存储。原本两条哈希链可以存储 2K个映射由于重复真正存储的映射数量不足2K。 2004年王小云教授提出了非常高效的MD5碰撞方法。
2009年冯登国、谢涛利用差分攻击将MD5的碰撞算法复杂度进一步降低。 几点补充
对于单机来说暴力枚举法的时间成本很高字典法的空间成本很高。但是利用分布式计算和分布式存储仍然可以有效破解MD5算法。因此这两种方法同样被黑客们广泛使用。
—————END—————
