MD4Collison

MD4碰撞攻击

目的：以论文梳理为主，回顾总结课程学习。

参考论文：2005年王小云教授等人发表的 Cryptanalysis of the Hash Functions MD4 and RIPEMD

MD4算法

MD4是较早出现的hash函数，在MD4后出现了MD5,HAVAL,RIPEMD，RIPEMD-160，SHA-1,SHA-256等更加复杂的hash函数，但设计原理和结构与MD4类似（碰撞原理也类似）。

消息摘要函数MD4将任意长度的消息压缩至128bit。算法对一个消息做如下操作：

step 1（填充）:将消息m填充至512的倍数（如果本身是512bit的消息，仍要填充，因为必须有64bit放消息长度）

填充部分：|m | 100… | len

对应长度：| 448bit | 64bit

step2（压缩）:填充完后，对每一个512bit消息块使用压缩函数将其压缩成128bit，最后一个消息块压缩完后得到的压缩值为整个消息的压缩值。

压缩函数有3轮：

Notes:

① mk：一个512bit块

mi为32bit，共16个，每一步操作中用到不同的mi（即mk），据表5得到具体值。

② a,b,c,d：链变量（具体操作见下）

③ F,G,H：3个非线性bool函数

X，Y，Z为32bit消息字,三个函数是按位操作，进行与、或、非和异或运算

④ s:循环左移位数，据表5可得到具体值。

⑤ 两个16进制数：无具体含义，指定好的。

压缩过程：

设填充后消息

M为中一个512bit块，且，mi每个32bit，共16个。

① 输入链变量：设（aa,bb,cc,dd）为输入链变量，若M是的第一个512bit块，则输入链变量等于给定的初始值，其后的消息块的输入链变量（aa,bb,cc,dd）为上一块的压缩值。

② 使用压缩函数：对每一个512bit消息块M，3轮压缩函数每轮进行16步，共48步，每一步中有一个链变量被更新,注意顺序是a、d、c、b：（注：wi即为上述的mk）

w与s由表5得具体值，设输入链变量a0,d0,c0,b0，48步产生的链变量为a1,d1,c1,b1,a2,d2,…,a12,d12,c12,b12,实际上a1-b12的链变量更新，使用到的是其往前数的4个值，如d1的产生用到了d0,a1,b0,c0

③ 反馈过程： 48步操作完后，加入当前块的输入链变量，得到的结果才是当前块的最终链变量

如果已经是最后一个512bit的压缩了，则

作为整个消息的压缩值，否则（aa,bb,cc,dd）作为下一个512bit消息块的输入链变量。

####攻击思路

碰撞是指不同的消息得到相同hash值，那么实际上，如果能够找到两个512bit消息m和m’产生碰撞，便可以构造m|s和m‘|s（s为任意串），两者一定产生碰撞。所以研究时只简化考虑512bit的消息。

完整的想法应该是先确定好两个消息的差分，然后找一条最后能产生碰撞的差分路线。再找一组满足该差分路线的充分条件，根据这组条件修改消息以满足路线。在已经有了本论文的差分路线的前提下，找512bit消息的碰撞:首先找到两个满足消息差分的512bit消息。论文中的表6是使得表5差分路线成立的一组充分条件，接着我们按照表6修改链变量，再根据链变量修改消息。

准备工作

1.有用的bool函数性质（x,y,z是对位的操作）

如F中第一条：当y与z在第i位相同时，x的第i位改变并不影响F得到的结果。利用这些性质可以合适的构造差分路线。

2.论文中使用的符号

为了方便描述构造的差分路线，先定义一些符号。

1.和代表两个512bit消息。

2.消息M压缩过程中产生的链变量，从a0,d0,c0,d0..a12,d12,b12,c12

3.消息M’压缩过程中产生的链变量，从a’0…c’12。

4.很直观，代表小消息块（32bit）的差分。

5.表示ai，bi，ci，di的第j个bit（1<=j<=32）。

6.(x为a,b,c,d中任一个)，前者表示将x的第j位由0改为1，其他位保持不变后得到的对应结果值，后者是x第j位由1改为0，其他位保持不变得到的结果值。

7.按照上述规则，对x（a/b/c/d）修改j1,j2..jl位，并让其他位保持不变得到的结果值。

例子🌰：在使用中，如对两个消息中c2的差分，用符号可以表示为，因为该差分实际上可由c2修改第19位（1->0），第22位（0->1）产生的c’2，两者相减得到。为什么是19和22位呢？因为第一位是2^0。再进一步，由于bit只有0和1，差分是可以被扩散的，也就是说两个链变量的差分-2^18=-2^19+2^18=-2^20+2^19+2^18=…可以一直扩散下去，当然具体扩散到哪里，这就是论文给出的“精确的”差分路线了。如最后是修改c2的19，20，21，22，位得到c’2.