论文部分内容阅读
近几年关于Hash函数的碰撞攻击取得了举世瞩目的成果。我国学者王小云等提出的基于模减的差分分析方法有效地攻破了MD4,MD5,RIPMD,HAVAL和SHA-0等一系列Hash函数。已经发现MD5算法的两个不同的3-bit碰撞差分,其中一个由王小云于2004年发现并被最终改进至采用普通PC机一分钟内可生成一对碰撞数据;另一个由谢涛于2007年发现,稍后被改进至半个小时之内即可产生一对碰撞数据。本文正是针对MD5函数的碰撞攻击做进一步分析和研究。本文在抽象出MD5算法可行碰撞差分路径性质的基础上,讨论了设计输入差分的一些基本原则,给出了部分构成可行碰撞差分的1～3-bit输入差分。独立推导了一个1-MSB输入差分的差分链。主要的研究成果如下:(1)详细介绍了如何寻找MD5碰撞,包括明文修改技术、从差分特征推导充分条件的方法。由于王小云教授给出的导出条件不是充分的,即这些条件不足以保持碰撞差分链,因此,补充了一些条件并放宽一些导出条件从而扩大碰撞集合。(2)讨论了设计输入差分的一些基本原则和设计差分链的基本原则。给出部分构成可行碰撞差分的1～3-bit输入差分。(3)对一个1-MSB输入差分进行了详细的分析。按照模减差分分析方法独立推导出了一条2-block的MD5模减碰撞差分链。虽然目前还不能够根据这条碰撞差分链构造出高效的攻击算法,但是它至少说明了设计输入差分和差分链的基本原则在分析MD5函数方面是非常有效的。(4)讨论MD结构的致命缺陷,基于这一缺陷甚至可以构造出在实际应用中的Hash值碰撞实例;并分析最新提出的构造Hash函数的各种改进方案的优缺点。