md5是一种广泛使用的密码学hash函数，由Ronald Rivest于1992年提出。密码学hash函数主要用于完整性校验，即检测消息传输过程中是否被篡改；以及作为底层原语构造消息认证码MAC。针对md5存在多种攻击，特别是XiaoyunWang'05[1]，时至今日，MD5已经不再安全，其生成的消息摘要也只能用来做checksum检测无意的消息修改(基于MD5设计的MAC算法如HMAC-MD5暂未证实存在安全风险，但新协议也不应再使用)。

本文分以下几个部分，第一部分介绍密码学hash函数的安全性定义；第二部分介绍md5算法；第三部分介绍生日攻击；第四部分介绍md5的长度扩展攻击；第五部分介绍彩虹表攻击；第六部分介绍王小云[1]的攻击；第七部分介绍TaoXie, DengguoFeng[2]的工作。

1 security of cryptographic hash function

密码学hash函数的安全性由其抗碰撞性(collision resistance)衡量。准确的说，密码学安全的hash函数要求，不存在多项式复杂度的算法找出hash函数的一个碰撞。实际上，由于密码学hash函数输入通常是任意长度而输出是固定长度的串，由鸽巢原理，碰撞一定存在，这里只是要求碰撞难以找到即可。

密码学hash函数的抗碰撞性很难达成，但是在一些场景下只需要满足更松的要求即可，为此通常进一步讲抗碰撞性分为以下三个层次：

1.1 Collision resistance

Collision Resistance指找到\(x, x'\)使得\(H(x)=H(x')\)，即找到hash值相等的一对输入。

1.2 Second preimage resistance

Second preimage resistance指对于任意给定的\(x\)找到\(x'\)使得\(H(x')=H(x)\)，即找到另外一个输入与给定输入有相同的hash值。

1.3 Preimage resistance

Preimage resistance指对于任意给定的hash值\(y\)找到\(x\)使得\(H(x)=y\)，即找到产生某个hash值的一个输入。

从密码学hash函数的设计角度来讲，显然collision resistance是最难达成的目标。由定义也不难看出，如果一个hash函数是collision resistant的，则它也是second preimage resistant的。同样的，如果hash函数是second preimage resistant的，那它也是preimage resistant的。

2 md5

md5对任意长度输入产生一个128bit的摘要输出，算法过程如下。

1. Padding: padding将输入填充为若干以512bit长度的块，如下图，即先补一个1bit的1，后续填充足够数量的0，最后64bit填上padding前的消息长度模\(2^64\)的值。

2. 512bit的块处理：将512bit的块分成4个128bit的小块进行处理。

3. 128bit的块处理：将128bit的块分成4个32bit的小块进行处理，如下图，图中ABCD都是32bit，是算法的内部状态，初值为一组常数，\(M_i\)为原消息切分后的32bit小块，\(K_i\)是一组常数，\(<<<_s\)表示循环左移\(s\)-bit。

3 birthday attack

生日攻击是一种通用攻击方法，任何有随机性要求的密码学工具都能基于此构造攻击，其原理基于生日悖论。生日悖论指这样一个与直觉不符的结论，假定每个人的生日为一年365天中任一天是等概率的，那么23个人中有两个人同一天生日的概率就达到50%了，这一概率达到99%也只需要57个人。这一概率计算不复杂，先算其对立事件，即所有人生日不同的概率为，然后用1减去，所以，\(n\)个人中有两个人生日同一天的概率为 \[ p(n)=1-\frac{365*364...*(365-n+1)}{365^n} \]

结果如图：

更一般的，假定有独立同分布的随机变量\(r_1, r_2,...,r_n\in U\)，则当\(n=1.2\times |U|^{1/2}\)，\(Pr[\exists i\neq j: r_i=r_j]\ge 1/2\)。

4 length extension attack

一些系统错误使用md5或者sha1来生成MAC，具体做法是\(H(secret||message)\)，此方法易受到长度扩展攻击。所谓长度扩展攻击，指在知道\(message\)，\(H(secret||message)\)和\(secret||message\)长度的情况下，可以构造出合法的\(H(secret||message||append)\)。由前所述md5的算法过程不难看出，md5是由消息不断迭代改变其内部状态最终得到结果。反过来，在知道\(secret||message\)长度的情况下，从最终输出倒推回去也能够得到padding前的内部状态，在此基础上继续迭代想要附加的消息继续处理即可得到扩展后的消息\(secret||message||append\)的md5值。消息扩展能够攻击那些支持参数覆盖的协议，例如HTTP请求的参数，假设原请求参数为"count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo"，攻击者可以利用长度扩展攻击的得到"count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege"，由于HTTP支持参数覆盖，waffle的值变为liege。

chosen-prefix collisions