一般来说,对一个HASH算法的攻击可分三个级别:
1,Preimage attack(原像攻击?):给定h,找到明文M,使得h=hash(M),如果一个HASH算法
被人找出preimage attack,那这种算法也就完蛋了;
2,Second preimage attack(次原像攻击?):给定明文M1,找到另一明文M2(不等于M1),
使得hash(M1)=hash(M2);
3,collision attack(碰撞攻击):找到M1和M2,使得hash(M1)=hash(M2)。
关于MD5,王小云教授的成果是实现了在可计算时间内实现找到collision。目前的进展是,基于王晓云教授论文的改进算法,有人可以做到 用笔记本在几小时之内找到collision。这意味着什么?有很多人认为collision毫无意义,因为在实际应用中M1和M2无法任意指定。其实这 是只知其一不知其二。和其他流行的HASH算法一样,MD5有一个众所周知的弱点,叫做length extension,可用数学语言描述如下:
若,MD5(M1) = MD5(M2)
则,MD5(M1||M') = MD5(M2||M')
其中||代表串连接。
目前的collision搜索算法可以任意指定初始hash状态,这意味着可任意构造前缀。另外length extension意味着可以任意构造后缀。因此基于任意collision,我们可以构造出两个MD5 hash相同的串,使得:
MD5(preamble+R1+suffix) = MD5(preamble+R2+suffix),
其中,MD5(preamble+R1) = MD5(preamble+R2)
如何利用collision attack?一个例子是利用随机collision构造两个不同功能的应用程序,并保持他们的
MD5相等。我们知道Windows上的应用程序用的是PE格式。PE程序一般由以下几部分构成:
PE header,PE文件头
.text section,代码段
.data section,数据段
other sections (.reloc, .rdata, .tls, etc)
构造过程如下:
1,编写应用程序,在其中实现你想要的两种不同功能。
2,手工调整PE文件,使得其layout如下:
PE header
Reserved block1
.text section
Reserved block2
.data section
Other sections
3,以PE header为preamble,搜索随机collision,使得:
X1 = PE header || R1;
X2 = PE header || R2;
MD5(X1) = MD5(X2)
4,将R1内容填入reserved block2,然后将R1和R2内容分别添入reserved block1处,得到两个应用程序文件,其layout如下:
文件1 文件2
PE header PE header
R1 R2
.text section .text section
R1 R1
.data section .data section
other sections other sections
5,在应用程序的开始代码处,拿Reserved block2处的内容和Reserved block1处的内容比较,如果相等后面的流程实现功能一,如果不相等实现功能二。这样就实现了任意功能的两个程序,并保持他们的MD5相同。
6,这其中,
Preamble = PE header
MD5(PE header || R1) = MD5(PE header || R2)
Common suffix = .text section || R1 || .data section || other sections
可以设想,如果功能一是很吸引人的某种正常用途,功能二实现某种木马,会带来什么后果。
目前正在上演的围绕著名游戏Diablo的外挂攻防大战中,就有可能用到这种攻击,因为Diablo中最著名的外挂Maphack就以MD5为数字签名,检查服务器端传送过来的外挂检测代码特征。
另外,上也给出了一个示例,里面演示了如何利用碰撞骗得老板的数字签名,并拿签名用在别的用途。其做法简单描述如下:
1,选择一种高级文档语言(比如postscript);
2,基于postscript的要求构造preamble,在此基础上寻找MD5随机collision:
X1 = preamble; put(R1);
X2 = preamble; put(R2);
MD5(X1) = MD5(X2)
3,给X1和X2添加相同后缀S,显然:
MD5(X1||S) = MD5(X2||S)
4,准备两份文本T1和T2,T1是正常文本(用来骗取签名),T2是其他用途文本。
5,最后形成两份postscript文档:
Y1 = preamble; put(R1); put(R1); if(=) then T1 else T2
Y2 = preamble; put(R2); put(R2); if(=) then T1 else T2
这样,打开Y1时,看到的是文本T1;打开Y2时,看到的是文本T2。而Y1和Y2的MD5 HASH是相同的。
总之,就目前而言,“MD5 is definitely not practically collision-free”。虽然只是collision attack,但在攻击者能控制并任意构造明文时,这种攻击就是实际可行的。王小云教授成果的意义在于找到了一种实际可行的collision搜索算法, 当然她的工作也是建立在其他人的基础上的。
阅读(1249) | 评论(0) | 转发(0) |