摘要
最近做CTF题目的时候又遇见了MD5碰撞,但是依然不懂那个所谓的可能性是如何计算出来的,于是打算自己花一两个小时的时间,把MD5的原理稍稍的梳理一下。
正文
MD5是全称是Message-Digest Algorithm5(信息-摘要算法),由MD2、MD3、MD4发展而来的公开算法。
MD5是一种哈希算法,任意长度的输入经过处理后输出为128位的信息,且尽量使结果不冲突和信息不可逆。
MD5算法过程:
MD5以512位为一个分组处理输入,每个分组分成16个32位的子分组,经过处理后,输出四个32位分组,这四个32位分组级联后生成一个128位的MD5值。
一、填充:如果输入信息长度(以bit记)模512不余448,那就要对输入信息进行填充,填充一个1和若干个0,使得信息长度变成512N+448,*若消息长度本身即为448,仍要填充512位,使其长度变成960**
二、记录:用64位记录输入信息的长度,然后添加到第一步的信息中,形成(N+1)*512的信息;
三、装入默认值:A=0x01234567,B=0x89ABCDEF,C=0xFEDCBA98,D=0x76543210。这里每个缓存均为32位(16进制四位,八个数)
四、分组:将512一组的数据进行分组,分成16个32位的子分组,将与幻数进行循环运算。
五、循环运算:这里借用一张MD5原理图进行说明
A、B、C、D四个寄存器默认的值进行运算,获得A‘,B’,C‘,D’,这是一步的运算。对于每一个分组512bit的消息,均要进行四轮,每轮十六步的运算,得到这一分组的128位结果,然后再以这个结果存入寄存器,作为下一组分组的初始值,直到最后一组的结果,即为MD5值。
图为四个逻辑函数,即MD5原理图中的“F”,四轮即分别使用四个函数,每个函数使用十六次。
第一轮用F,第二轮用G,第三轮用H,第四轮用I
MD5原理图中的田字表示的是模2^32加法,为的是F的结果与A运算后仍为32位。
Mi即为分组的消息,最初是分成512一组,然后再分到组内32bit一组共16组,每一轮16步,要将16组消息全部用上。
第一轮中使用顺序为
$$
P_1(i)=i
$$
即i为多少就用第几个分组
第二轮中使用顺序为
$$
P_2(i)=(1 + 5i)\mod 16
$$
由于3、5、7、11、13与16互质,因此当i遍历1-16时,1+k*i是一个完全剩余系,即同样遍历1-16没有重复
第三轮中使用顺序为
$$
P_3(i)=(5 + 3i)\mod 16
$$
第四轮中使用顺序为
$$
P_3(i)=7i\mod 16
$$
ki是固定常数,当然也可以通过计算获得。
在MD5原理图中,最后再次与B做模加运算之前,还有一次循环左移。这个也是有规定的
PS:图均来自于我们杭电伟大的胡耿然老师的密码学ppt,吹爆!
至此,MD5的原理就全部讲解完毕。个人懒而且菜,没有尝试去实现MD5算法,无法贴源码/(ㄒoㄒ)/~~
MD5截断攻击
下面进入正题,继续研究MD5截断。
Code: md5(code)[:6] ==d131dd
MD5截断诸如此类,需要你提供一个字符串code,然后通过md5计算并截取前N位字符,使得其与给定的md5字符相同。
据我查阅得,大多数MD5截断的CTF姿势都是暴力,当然我也没有看过传说人物王小云的文章,也只能跟随着暴力……只是因为困惑于可能性的多少,所以写这篇文章探索一下。
MD5一般是一个128位的二进制序列,但是大多数MD5为了方便显示,通常写成16进制形式,即32位十六进制数。如果需要截取前N个,再加上十六进制的可能性为2^4,那就是2^4N种可能。对于这个六位的形式,粗略估计应该有一两千万种可能性。所以,如果写一个脚本,生成超过三千万的MD5值,应该可以找到任意前六位与给定字符相同的原字符。大概三千万*128bit,粗略估计就是3.57G……
还是精确计算吧。2^24*2^7/2^30=2,就是2G。再加上要存储对应的原字符,差不多3G左右的文本肯定够了。
附一段网上的脚本:参考链接:【CTF】MD5截断比较
1 | # -*- coding: utf-8 -*- |
解释:对数字1-10亿(丧心病狂的十亿爆破……)的哈希值计算,并将计算结果存储在gen_md5.txt里
由于可能存在哈希碰撞,所以理论上来说,数据还是要设的比2^24要大一些的,但这个一百倍……反正我还没有把结果跑出来过,反而跑炸了一次,CPU 100%卡死了……
寻找结果的话就自己写Python脚本或者用cat命令吧,打死也不可能用txt打开的,内存放3G文本受不了……
- 本文作者: crlwebby
- 本文链接: https://crlwebby.github.io/security/crypto/md5/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!