中国女教授破解国际通用密码算法 各国震惊（zz）

farmer

中国女教授破解国际通用密码算法 各国震惊（zz）
留言人：  IP:[192.168.29.234]  Email:  日期：2005-3-27:13:12:36

  

   
发信人: mathematics (TouchDown~Enjoy Her), 信区: PhD
标  题: 中国女教授破解国际通用密码算法 各国震惊
发信站: BBS 水木清华站 (Fri Mar 25 15:00:54 2005), 站内

【 以下文字转载自 THUExpress 讨论区 】
发信人: mathematics (TouchDown~Enjoy Her), 信区: THUExpress
标  题: 中国女教授破解国际通用密码算法 各国震惊
发信站: BBS 水木清华站 (Fri Mar 25 14:54:22 2005), 站内

这个报道以前看到过,哪位懂行的给评价一下里面的内容?



随着电子商务的发展，网上银行、网上合同、电子签名等的应用越来越广泛，网络已经成为我们生活中不可或缺的一部分。电子商务在给我们的工作生活带来便捷的同时，也存在着安全隐患。一直在国际上广泛应用的两大密码算法MD5、SHA－1，近期宣布被一名中国密码专家破解。这一消息在国际社会尤其是国际密码学领域引起极大反响，同时也再次敲响了电子商务安全的警钟。

　　从密码分析上找出这两大国际通用密码漏洞的是一位土生土长的中国专家——山东大学信息安全所所长王小云。

　　新闻世界密码大厦轰然倒塌

　　40岁的王小云，毕业于山东大学数学系，师从于著名数学家潘承洞、于秀源教授，是一位外表普通却充满自信的中国女性。

　　在去年8月之前，国际密码学界对王小云这个名字并不熟悉。2004年8月，在美国加州圣芭芭拉召开的国际密码大会上，并没有被安排发言的王小云教授拿着自己的研究成果找到会议主席，要求进行大会发言。就这样，王小云在国际会议上首次宣布了她及她的研究小组近年来的研究成果——对MD5、HAVAL－128、MD4和RIPEMD等四个著名密码算法的破译结果。




　　在公布到第三个成果的时候，会场上已经是掌声四起，报告不得不一度中断。报告结束后，所有与会专家对她们的突出工作报以长时间的掌声。

　　王小云的研究成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准MD5大厦轰然倒塌，引发了密码学界的轩然大波。这次会议的总结报告这样写道：“我们该怎么办？MD5被重创了，它即将从应用中淘汰。SHA－1仍然活着，但也见到了它的末日。现在就得开始更换SHA－1了。”

　　事实上，在MD5被王小云为代表的中国专家破译之后，世界密码学界仍然认为SHA－1是安全的。今年2月7日，美国国家标准技术研究院发表申明，SHA－1没有被攻破，并且没有足够的理由怀疑它会很快被攻破，开发人员在2010年前应该转向更为安全的SHA－256和SHA－512算法。而仅仅在一周之后，王小云就宣布了破译SHA－1的消息。

　　因为SHA－1在美国等国家有更加广泛的应用，密码被破的消息一出，在国际社会的反响可谓石破天惊。换句话说，王小云的研究成果表明了从理论上讲电子签名可以伪造，必须及时添加限制条件，或者重新选用更为安全的密码标准，以保证电子商务的安全。

　　最近国际密码学家Lenstra利用王小云提供的MD5碰撞，伪造了符合X.509标准的数字证书，这就说明了MD5的破译已经不仅仅是理论破译结果，而是可以导致实际的攻击，MD5的撤出迫在眉睫。王小云说，目前SHA－1在理论上已经被破译，离实际应用也为期不远。

　　评论这几位研究人员太疯狂了

　　MD5、SHA－1等国际通用密码被破译，在国际密码学界引发强烈“地震”。

　　国际顶级密码学家Shamir评论道：“这是近几年密码学领域最美妙的结果，我相信这将会引起轩然大波，设计新的Hash函数算法极其重要。”

　　MD5的设计者Rivest评论道，“SHA－1的破译令人吃惊”，“数字签名的安全性在降低，这再一次提醒需要替换算法”。

　　美国国家标准技术研究院和几大知名公司也做出积极反应。

　　希捷科技（Seagate Technology）的一位安全问题研究总监Mark Willet表示，“现在美国国家标准技术研究院可能需要将更新密码的日程提前。”

　　此外，微软、SUN和Atmel等几家知名公司的专家也发表了他们的应对之策。一位美国律师协会顾问说：“中国的这几位研究人员太疯狂了。”

　　幕后不可思议的女子解码团队

　　让世界震惊的是，绝大多数密码专家认为固若金汤的两大密码算法，最终被一位中国女子带领的女子团队无情地击倒，而且这个过程看起来似乎并不是太难，SHA－1的破解只用了两个多月的时间，很多密码学界的专家认为“这听起来简直有些不可思议”。

　　王小云1990年在山东大学师从著名数学家潘承洞教授攻读数论与密码学专业博士，在潘承洞、于秀源、展涛等多位名师的指导下，她成功将数论知识应用到密码学中，并从上世纪90年代末开始进行Hash函数的研究。

　　王小云在成功之前一直默默无闻，同行评价她，从不急功近利，没有新思想新进展的论文她是绝对不主张发表的，平时对一些耽误研究工作时间的荣誉或应酬也没有热情。她不赞同大批量的阅读文献，主张抓住几篇经典的论文仔细研究，吃透论文思想，然后自己独立思考，寻找突破性的方法，迅速将自己的方法进行实验。她就是这样周而复始地在数字王国里进行着钻研。

　　参与破译密码SHA－1的研究小组是以王小云为首的一支3人女子团队，其中包括王小云的一名博士生于红波，另一位合作者是来自清华大学的一位女研究人员。“我的8名博士生里面有6个是女性，她们在密码学领域表现出不凡的才能。很多人觉得密码学是很玄妙的学问，而我们觉得它非常有趣。因为我们习惯于用数学方式思维，而一旦养成了这种思维方式，数字在我们眼中就变成了美妙的音符，我们的研究就象音乐创作一样有趣。”王小云说。（据新华社专稿）

　　■相关链接

　　国际两大密码城堡

　　MD5、SHA－1是当前国际通行的两大密码标准。据了解，MD5由国际著名密码学家图灵奖获得者兼公钥加密算法RSA的创始人Rivest设计，SHA－1是由美国专门制定密码算法的标准机构——美国国家标准技术研究院（NIST）与美国国家安全局（NSA）设计。

　　两大算法是目前国际电子签名及许多其它密码应用领域的关键技术，广泛应用于金融、证券等电子商务领域。其中，SHA－1早在1994年便为美国政府采纳，目前是美国政府广泛应用的计算机密码系统。

　　王小云介绍说，世界上由于没有两个完全相同的指纹，因此手印成为人们身份惟一和安全的标志。在网络安全协议中，使用Hash函数来处理电子签名，以便产生理论上独一无二的“指纹”，形成“数字手印”。按照理想安全要求，经过Hash函数产生的指纹，原始信息即使只改变一位，其产生的“指纹”也会截然不同。如果能找到Hash函数的碰撞，就意味着两个不同的文件可以产生相同的“指纹”，这样就可以伪造签名。

　　王小云剪影

　　综合新华社消息，整日埋头密码研究的王小云并不是记者想象中的“陈景润”式的学者，她穿戴得体，看起来稳重而又时尚，镜片后面的眼睛透露出坚定而又自信的目光。

　　公布破解MD5报告前，王小云曾跟丈夫开玩笑说，“我作完这次报告后，你猜我的名字会不会出现在Google（著名搜索引擎）里？”果然，在她公布了破解MD5的报告后，国外的很多网站上有了关于王小云破解MD5的消息，Google里关于王小云的检索条也多达数千条。

　　默默无闻的王小云一鸣惊人，山东大学信息安全实验室一夜之间成为让世界注目的科研机构。

farmer

关于王小云破解MD5之我见
CSDN一篇报道说中国数学家王小云等在Crypto 2004上提出一种能成功攻破MD5的算法，GIGIX和王兄都在BLOG里引用了相关的报道。

MD5是一种摘要算法，所以理论上是不可能从签名取得原文（见下面说明）。认为要从MD5的结果中取得原文才算破解，本身就是对摘要算法的误解。它通常应用于数字签名中，用于标识原文的原始性--即在签名后未作任何的修改。如果可以用不同的原文可以产生相同的签名，这也就意味着签名可能失效，就已经可以证明这种摘要算法的不安全。

RL提供的王小云的报告我看了一下，因为我不是做这方面的，所以对MD5算法本身的实现，以及文中所引用的之前别人的理论都并不了解，所以不是很明白。在这份报告中，介绍MD5破解的部分只有一页半，并未细说具体的算法，但在末尾附了两对1024位原文的碰撞例子，较之96年别人提出的512位碰撞有了很大的进步，并且计算量据说在一个小时左右。

这些都是进步，如果把这说成是吹嘘就未免有点妄自菲薄了。

王小云的发现证明了有方法可以产生碰撞，但正如GIGIX那边一位匿名兄所说，这只是非特定碰撞，而要伪造签名则必须能产生特定碰撞。所以说MD5并未被完全攻破，但也已经是一个重大的突破了。

因为我手头没有像《应用密码学》这样的介绍具体密码算法的书，只有一本卢开澄的《计算机密码学》，主要是从数学的角度介绍了几类密码算法的原理及其适用领域。不过因为密码学是基于较为高深的数学理论，比如数论、群论、有限域等，但俺的数学不行，所以具体理论也说不出个一二三四来，只能泛泛地说个五六七八。^O^

首先要说的是为什么需要使用密码？因为我们通常的通信环境是不安全的。

那什么是不安全的通信环境呢？不安全至少表现在两个方面：一是通信的内容可能被窃取；二是通信的内容可能被篡改。

通常的密码使用就是为这解决这两方面的问题。

而如果有方法使某种密码的作用失效，就可以说这种密码被破解了。

当然不安全还有一些其它的方面，那些问题通常除了需要密码以外，还需要用一些特别的协议，很少碰到，这里就不提了。

常用的密码有很多种类，其中最常用的是这三种：
1、对称密码
2、非对称密码
3、摘要

对称密码的特点是：加密与解密用相同的密钥，甚至可能用相同的算法。比如从最简单的异或，到常用的DES、BLOWFISH、IDEA等。它们通常的用途是这样的：

发送方将源文（M）用密钥（K）加密：E=ENC（M，K）
然后将E通过不安全网络传给接收方，接收方用相同的密钥（K）解密：M=DEC（E，K）

只要算法足够好，并且保管好密钥（K），就可以保证这种通信是安全的，因为别人即使知道了密文（E）和算法ENC/DEC，也无法知道明文（M）。

对于这种密码来说，如果有方法可以从密文（E）和算法ENC/DEC中导到密钥（K）或明文（M），则意味这种密码被破解。比如简单异或算法就可以用统计分析法简单地破解掉。但即使是现在被认为不够安全的DES算法（已经有近三十年历史了），也需要有大量的明文/密文对（2的数十次方对），并需要大量的计算时间才能求得其密钥（K）。

非对称密码是因为这样的原因：因为在对称密码中，通信双方需要约定一个共同的密钥（K），如果这个约定过程也不安全，就可能出现密钥的泄露，而对于对称算法来说，密钥一旦泄露，之后的通信过程也就不攻自破了。

通常的非对称密码就是所谓的公钥密码算法，比如现在最常用的RSA（由R. L. Rivest和A. Shamir等人基于大数的因数分解极为困难的原理而创建），或是最近更为时髦的“椭圆曲线”，因为我的数学水平太差，具体算法也说不清楚，只知道大致是这样的：

顾名思义，它所用的算法特点在于加密与解密用的密钥是不一样的。做法大致如下：

发送方自己生成一对密钥：私钥（KA）和公钥（KPA）
接收方也生成一对密钥：（KB）和（KPB）
其中（KPA）和（KPB）是公开的
发送方用算法：E=ENC（ENC（M，KA），KPB）
进行两次加密，接收方用算法：M=DEC（DEC（E，KB），KPA）
进行两次解密，即可得到原文。
而其中双方都不需要知道对方的私钥，这就避免了约定密钥导致的不安全。
非对称密码的算法本身又决定了用私钥加密的内容必须用公钥才能解，反之亦然，并且算法还保证仅知道公钥和密文无法导出私钥，由此决定了通信的安全。

当然，如果有方法可以从公钥导出私钥来，则这种算法即告被破解。但至少目前RSA还是安全的，因为从现在的数学理论上可以证明RSA的算法是一类NPC（NP完备）类问题，只要密钥足够长（RSA要求至少是10的100次方以上，实际使用时更要大得多），以现在最先进的计算机来算，其时间成本也是不可能达到的。

摘要算法则与上面两种完全不同，前面两种密码是用于防止信息被窃取，而摘要算法的目标是用于证明原文的完整性，也就是说用于防止信息被篡改。通常也被称为：HASH算法、杂凑算法、签名算法。它的特点是：从不定长的原文中产生一个固定长度（如MD5是128位）的结果，称为“签名”（S），这个签名必须对原文非常敏感，即原文即使是有少量的变化，也会导致这个签名面目全非。比如传统的CRC或是现在要说的MD5、SHA等都是这类算法。

摘要算法的用途通常是这样的：

比如用户密码验证：如Linux或一些论坛用的方法，用户设置密码时，服务端只记录这个密码的MD5，而不记录密码本身，以后验证用户身份时，只需要将用户输入的密码再次做一下MD5后，与记录的MD5作一个比较即可验证其密码的合法性。

比如发布文件的完整性验证：比如发布一个程序，为了防止别人在你的程序里插入病毒或木马，你可以在发布这个程序的同时，公开这个程序文件的MD5码，这样别人只需要在任何地方下载这个程序后做一次MD5，然后跟公开的这个MD5作一个比较就知道这个程序是否被第三方修改过。

一个安全的摘要算法在设计时必须满足两个要求：其一是寻找两个输入得到相同的输出值在计算上是不可行的，这就是我们通常所说的抗碰撞的；其二是找一个输出，能得到给定的输入在计算上是不可行的，即不可从结果推导出它的初始状态。

反之，如果某种摘要算法不能同时满足上面两个条件，则它就是不安全的。其实主要还是前一个条件，因为从理论上很容易证明后面一个条件基本上都是可以满足的：

摘要算法对任意长的原文产生定长的签名，按照香农的信息论，当原文的长度超过一定的程度的时候，签名中就无法记录原文中的所有信息，这意味着存在着信息的丢失，所以我说理论上不可能从签名中恢复原文。

为什么说理论上呢？就是说当这种摘要算法被完全攻破时，也就是说可以从签名恢复出任意原文，注意：是任意原文，因为所有的摘要算法的特点就是存在着一个无穷大的碰撞原文的集合。而真正的原文只是其中一份。对应这个无穷大的集合来说，这就是一个无穷小，便是我曾经说过的：

可能性为零，不表示不可能。

解释得具体一点是这样：假设原文含有信息量（I），而签名的长度有限（如MD5的128位），则它的信息量只有(i)，因为通常 i < I （除非原文非常短），所以可以这么说：I=i+i&#39;。因为I没有限制，而i有限制，则 i&#39; 也是一个没有限制的量。当进行摘要算法后，i&#39; 信息就丢失了。

反过来，如果现在这种摘要算法被攻破了，可以从 i 反推回去，但因为 i&#39; 信息已经丢失，意味着 i + I&#39; （其中 I&#39; 为任意信息）都可能是 I （碰撞）。但 I&#39; 是一个无穷集合，并且 i&#39; 属于 I&#39;。这说明：理论上可以从 I&#39; 中找到 i&#39; 从而恢复出原文 I ，但是可能性为零（1/∞=0）。

但要做到前面一点就不容易了。因为绝对无碰撞的算法不可能是一个摘要算法，而只能是一个无损压缩算法。它必须包含原文的所有信息，也就意味着它一但被攻破，可以唯一地恢复出原文。并且它的结果肯定是不定长的，因为它需要包含原文的所有信息，当然会根据原文的长度而变。仅这两点就决定了，它不可能是一个好的签名算法。

最主要的一点是：摘要算法的用途决定了，它只要能找到碰撞就足以让它失效，并不需要找到原文。

以前面的两个例子来说：

比如Linux的用户安全机制，只要得到用户密码文件（其中记录了密码的MD5），然后随便生成一个碰撞的原文（不一定要跟原密码相同），就可以用这个密码登录了。

但后面的程序发布的例子就要难得多，因为它必须能生成特定的碰撞，即在程序中插入病毒或木马后再填充一些数据使之生成与原来相同的MD5。

不过我昨天仔细想了一下，以MD5为例，要产生特定的碰撞应该还是不太可能的，因为MD5的128位信息量已经有点大了，如果要产生特定碰撞，需要填充的数据可能非常之大，导致伪造的原文比真实的原文大得多，可能达到若干个数量级的差别，这样的伪造就已经失去意义了。

王小云的成果已经完全使Linux用的那种基于MD5的身份验证技术失效了，虽然从技术上说它被完全攻破，还为时尚早，但从法律角度上说，已经“动摇了差不多整个数字签名界的根基”（令狐语，全文如下）。

我所谓的“动摇根基”云云，是从法律失效的角度说的，而不是从纯技术角度说的。
举个昨天我举的例子来说明一下。比如昨天我说的，假如有两个人的指纹完全相同，而且我可以很快的找出这两个人，那么，在法律角度来说，我们就不能把指纹作为一个有效证据。虽然这两个同指纹的人并没有互相冒充的意思。

同样的，现在刻意去伪造文件并产生相同的MD5码还做不到，但是，现在可以在短时间内找到两份相同的档案，他们的MD5码相同，那么，MD5作为数字签名的“法律意义”便失去了。而数字签名是用来干吗的？就是让一个电子文档具有法律意义的。所以，我说，这个发现是动摇了数字签名的根基。

mofeisite

这是很早的消息了，能不能来点新的？