助推现代密码学发展
密码杂凑算法在电子签名和数据完整性机制中具有广泛应用，是一种非线性迭代函数，可将任意长度的消息压缩成一定长度的一段数字摘要，使之满足抗可逆性分析与抗碰撞性分析等密码学特性。
MD5算法与SHA-1算法是计算机网络信息系统中的事实国际标准密码杂凑算法，在SSL/TLS、SSH、IPSec以及其他密码协议中已经得到广泛使用，在时间戳机制、计划承诺、在线软件完整性检测、分布式文件系统、伪随机数发生器等领域也是一种常用算法。
其中，MD5算法是由美国著名密码学家Ronald Rivest于1992年设计的。Ronald Rivest是计算机科学领域最高荣誉图灵奖获得者、美国国家科学院与国家工程院院士，同时也是RSA公钥密码算法、RCx分组加密算法以及MDx杂凑算法的设计者；SHA-1算法是由美国国家标准技术局与美国国家安全局于1995年联合设计的美国国家标准密码杂凑算法，并于2002年推出了安全强度更高的SHA-2算法。MD5算法与SHA-1算法的设计原理已经成为密码杂凑算法的经典设计思想而被其他国家标准广泛采用，如RIPEMD、HAVAL与HAS等系列标准密码杂凑算法。
自MD5算法与SHA-1算法正式发布以来，国际密码学界对其安全性展开了持久的分析工作，其中作出突出贡献的密码分析学家有德国学者Hans Dobbertin、法国学者Antoine Joux、差分分析创始人Eli Biham以及中国学者王小云等。
密码杂凑算法的碰撞攻击问题是指，利用计算机产生具有同一杂凑值的消息对，从而使其数据完整性确认机制失去效用，这是所有密码杂凑算法设计时必须确保避免的一个计算不可行的基本性质。自王小云教授于2004年突破MD5算法的碰撞攻击问题以来，国际密码学界掀起了新一轮密码杂凑算法的设计与分析热潮，其中以下几个问题是国际密码学界十分关注并困扰至今的问题。
1)MD5的可行碰撞差分究竟是如何选择的？到底存在多少可行碰撞差分？
2)差分路径是如何设计的？如何设计一条最优的差分路径？能否由机器自动设计最优差分路径？
3)给定一条可行碰撞差分路径，如何提高碰撞攻击算法的效率，或者碰撞攻击算法的效率极限是什么？
4)差分碰撞分析技术可否推广至其他密码杂凑算法以至分组密码算法的分析领域？
近日，中国科学院信息安全国家重点实验室高级访问学者谢涛博士和冯登国研究员通过紧密合作，在国家“973”计划项目资助下，在MD5和SHA1的碰撞分析方面取得了一系列新的突破性进展，主要包括：提出了分析密码杂凑算法的“分而治之”的新思想，借此可实现MD5算法符号差分路径的分段解耦或SHA1算法消息路径与状态路径之间的结构解耦，从而显著提高了碰撞攻击效率；给出了MD5可行碰撞差分必须满足的基本性质，列出了1～3-bit所有可行碰撞差分共95组，其中94组为首次发现；在进一步完善符号差分理论的基础上，抽象并归纳出基本的符号差分路径设计规则；完成了两个具体碰撞差分的完整差分路径设计与碰撞攻击算法设计，其中一个为1-MSB单点输入差分，其碰撞搜索算法的计算复杂度小于MD5压缩函数计算，采用普通PC机（主频2.66Ghz）平均0.45秒钟可产生一对碰撞数据，并且以一定概率可在毫秒级生成碰撞数据，是当前已经公开的MD5碰撞算法中最快的算法；在SHA-1算法理论分析方面取得了明显进展，实现了SHA-1算法的状态路径与消息路径的高效结构解耦。
在2008年11月举办的专家研讨会上，中国工程院院士蔡吉人、周仲义、林永年、魏振耀，上海交通大学教授来学嘉等国内外学者一致认为，谢涛等在密码杂凑算法分析方面的研究成果处于国际先进水平，其中在MD5算法的差分漏洞分析、差分路径设计和碰撞攻击算法设计方面处于国际领先水平。
据悉，目前该课题组已公开部分研究成果，其他成果将视情况逐步向外公布。这些研究成果可以进一步提高我国在密码杂凑算法方面的设计分析能力与国际学术地位，推进差分碰撞分析技术在原象实际攻击以及其他认证码的实际攻击与分析研究，积极推动SHA-3系列国际密码标准杂凑算法的设计与分析工作，并可能产生对实际密码协议的新的攻击方式。
据介绍，该成果公开的部分已被Eurocrypt2009（第28届欧洲密码学年会）录用。欧洲密码学年会简称欧密会，是由国际密码学研究协会（IACR）组织的三大密码学学术年会（欧密会、美密会与亚密会）之一，一般每年定于4至5月在欧洲国家举行，主要涉及密码学各领域的最新理论研究成果与密码分析最新成果报道，其评审程序十分严格，评审结果具有权威性，每年最多录用30篇论文。Eurocrypt2009将于今年4月在德国科隆举行，届时谢涛将应大会主席Antoine Joux邀请正式宣布部分研究成果。
据权威专家透露，在密码杂凑算法分析领域，国际密码学界目前正在对以下几个问题展开深入研究。
1)SHA-1算法的实际碰撞攻击，希望构造首对SHA-1碰撞数据；
2)差分路径的机器设计，希望通过计算机算法解决自动差分碰撞路径的设计问题；
3)MD5算法的原象攻击，成功的原象攻击将导致计算机网络信息系统的灾难性后果；
4)对基于MD5或SHA-1的消息认证码算法以及实际安全协议的分析与攻击，如HMAC与NMAC消息认证码算法以及POP协议等；
5)对已经公开的第三代密码杂凑算法SHA-3标准的侯选算法进行评选。
中国科学院信息安全国家重点实验室在密码杂凑算法分析领域已经取得的研究成果将会对这些问题的研究产生积极的推动作用，其中在任何一个问题上的突破性进展都将成为推动现代密码学发展的重要标志。
《科学时报》 (2009-2-27 A1 要闻)
