王小云老师破解MD5算法到底是怎么回事啊，有没有人给我们这些外行科普下？

本人在两年前系统学过密码分析的相关内容，当时的确是懂了，不过现在已经有些忘记了，如果有误可以在评论区指出。

我们要首先脱去所有的hash函数的外壳，在不考虑特殊构造的hash的情况下，hash函数本质是一个布尔方程组。

这句话什么意思呢?我们定义如下的式子就叫做 苏迟但到hash 吧。

我们假设 是代表第i项输入, 是代表第i项输出。

hash函数的本质就是定义了若干个这个式子。

当然现实生活中的式子都特别长，长到里面的项数可能是2^80的级别。

1.为什么可以做到那么长？

这是由于hash函数的迭代性质产生的。你可以重新看上面的公式，在第二轮的时候output又会变成x重新输入，那么代入第一轮的式子是不是就变得非常长，相当于乘上了一个原有的系数项的数量。

2.王小云想要破解什么？

王小云想要构造出一个碰撞对，换句话说就是实现在不同的输入但是相同的输出。

3.在原来我们碰撞一个hash对需要多少的计算量?

我们不考虑某个具体hash函数的性质，假设它的输出是随机的，长度为n，它的输出空间是 。那么大概平均需要遍历 才能找到一个碰撞对。在这里就是 .

有几点要声明：1.n要足够大的情况下，才符合这个近似公式。

2.平均是指多次实验之后求平均值，在某一次你可能第一次就抽中了一个碰撞对，也可能你遍历完所有空间才抽中。这是一个期望值。

4.差分是什么？

输入差分是指存在一对输入

而这里的 。

我们在这里要引入一个知识，就是mod2下的加法和异或等价。也就是上式子可以写作 。

在后文我会省略mod2，同时加法和异或混用，你可以均看作加法即可(我主要是为了节约括号）。

我们会保持着m不变，而改变x的值，当然x'也会随之改变。

输出差分是指

注意，当m全部为0的时候，那么这个差分是平凡的差分，因为输出的值肯定相等，那么输出也全是0，所以我们不考虑这种情况。

5.魔力的一刻来了。

现在我们只关注output2.

现在我们发现输出的差分值可以被表示为 。

而 有一个性质就是当 的时候就等于0。

6.当我们设定了一个输入差分值为(0,1,1)。

我们惊奇的发现，在保持着这个差分的前提下，最后的一个输出值总是保持着0。

7.恭喜你.

你从密码学的角度成功破解了 苏迟但到hash 。

你成功发现了它的不均匀性，使得它不再是一个完美的hash函数。

因为我们保持这个输入差分的情况下，前面两个比特位的输出空间只有2*2，那么碰撞复杂度只需要根据生日攻击原理，对输出空间进行开根号，也就是 。

但是这一步还不能够破解。

8.遍历，我们需要将 从000遍历到111，当然我们也要同步计算 。

那么你就可以成功找到一个碰撞对。

在实际情况中，对于某一个输入差分对的输出差分是一个概率分布。

我们可以通过数学分析也可以通过遍历来实现对这个概率分布求解。当这个偏差足够大的时候就可以为破解提供条件。

对于多轮而言，这个偏差就是乘积形式存在，所以当轮次过多的时候它就被搅拌的足够均匀了，那么差分攻击的威力就没有那么强了。