在我的上一篇文章《MD5算法,看这篇就够了》中,我描述了md5算法的基本步骤,今天跟大家分享一下破解md5的原理。参考文献在文末,有兴趣的读者可以读读。
文本中出现诸如M0,M1,以粗体字母+非粗体数字组合的符号等同于公式中该字母和以该数字作为下标的符号。
首先我们来大概回顾一下MD5算法。
上述迭代的过程我们称之为杂凑运算。可以描述成这样:
公式中的Mi表示为M中下标为i的元素,H0是缓存器中的初始值(A,B,C,D),Hi表示第i-1轮中缓存器中的结果,四轮运算我们抽象成函数f。
哈希函数最重要的分析方法是差分攻击,同时也是分析分组密码最重要的方法之一。差分攻击大部分是使用异或运算的异或差分攻击,由Eli Biham和Adi Shamir在分析类似DES加密体系的安全性中提出的,他们描述差分密码分析是一种分析纯文本对(原文)中的特殊差异对产生的密码文本对的差异的影响的方法。
在本文中,我们使用整数模减((A-B) mod C)来进行差分分析。
两个数之间的差我们表示为:
对于M=(M0,M1,M2,....,M(N-1))和M'=(M0',M1',M2',....,M(N-1)')。哈希函数的整个过程的差我们可以表示为:
在上式中,△H0表示初始值(A,B,C,D)之间的差,显然是0。△H表示最终两个消息之间的差,△Hi表示在第i次迭代之后结果的差,当然也是下次迭代的初始差值。我们的目标很简单,假如我们使得最终的结果△H=0的话,也就是M和M'的哈希结果是一样的,M和M'就产生了碰撞。
要想使得碰撞发生,即△H为0,需要满足的充分条件多达290多条(N=2),分布在每一轮运算的计算上,附录中给出了表格。要想满足这些条件,提高碰撞的可能性,我们使用消息修改技术。有两种修改方式。
1、对于任意的消息块(Mi,Mi')第一轮运算的非0“差”。
其中△R,第二个下标表示轮数。我们通过修改Mi的值,保证在第一轮运算中满足差分的条件。
2、使用多消息修改机制,我们不仅能保证第一轮运算满足充分条件,同时也能都大幅提高第二轮运算条件满足的几率。
对于MD5的差分攻击,同其他哈希函数大同小异。这里我们攻击的目标是1024位M=(M0,M1)的消息体。我们的目的就是根据差分值计算M'=(M0',M1'),使得MD5(M)=MD5(M')。
步骤描述如下:
该攻击方法只用于寻找产生碰撞的消息对,对于实际应用来说,满足差分的充分条件的几率很小。
摘自王小云论文
摘自王小云论文
关注技术大白,带你阅读技术书籍,了解技术内幕!