注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

dingchaoqun12 的博客

上海股票期货开户

 
 
 

日志

 
 
 
 

关于MD5破解这件事 - sting feng - 博客园  

2012-10-12 22:08:55|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

关于MD5破解这件事

Posted on 2008-10-16 10:50 sting feng 阅读(627) 评论(1) 编辑 收藏
前 几天在论坛上看到有人在讨论MD5的破解,很多人对MD5的理解让我大跌眼镜:有人认为MD5是一种加密算法,有人认为由于无法从MD5 hash回复出明文,因此对其破解的研究毫无意义,甚至因此置疑王小云教授的成果毫无意义,真是让人遗憾。 因此今天决定说说MD5的破解,算是义务普及。有关MD5的描述请参考Wikipedia/MD5,这里就不多废话了。
一般来说,对一个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为数字签名,检查服务器端传送过来的外挂检测代码特征。
 
另外,http://www.cits.rub.de/MD5Collisions/上也给出了一个示例,里面演示了如何利用碰撞骗得老板的数字签名,并拿签名用在别的用途。其做法简单描述如下:
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搜索算法, 当然她的工作也是建立在其他人的基础上的。



引文来源  关于MD5破解这件事 - sting feng - 博客园
  评论这张
 
阅读(351)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017