Le espace de Kei

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://keilt.blogbus.com/logs/27179841.html

最近中文媒体上,MD5和SHA-1被"破解"的消息很盛行,主角是一个伟大的女性,山东大学教授,王小云博士.那么MD5和SHA-1真的就这样被破解了吗?我这几天在家有空,于是研究了一下王小云博士的几篇论文.

首先弄清楚什么是MD5,通俗的讲,MD5就像是人类的指纹一样,是一种消息摘要,可以把任意长度的消息依靠某种算法迭代生成固定长度的摘要.就像人类通过指纹来区分不同的人一样,我们也可以通过消息的MD5值来区分不同的消息.MD5的设计者,让MD5有了这样的一种性质,即对消息的任何小小的修改,都会造成最终MD5值的极大改变(传说中的雪崩效应),这可以在消息传递过程中防止消息被轻易篡改.SHA-1同这类似,下文都是对MD5的分析.

其次,弄清楚什么叫"破解",在密码学中,如果找到一种算法,使其他人能轻易的从密文算出明文,那么这个密码体制才能叫破解.注意"轻易的"三个字,因为有的密码体制,是建立在现实的难题之上的(例如前面我写到过的Diffie-Hellman难计算假设),这样会造成一种结果,就是,这种算法在理论上是存在逆向算法的,但是正向计算很容易,逆向计算就需要耗费非常大的计算资源,这样也不能说是破解.

那么MD5真的被破解了吗?

首先,从Shannon的信息论角度分析,MD5实际上是一种从任意长度消息到固定长度摘要的一个映射,一般这个摘要长度都会远远小于原消息长度(要不是用MD5就没意义了),对于这个摘要,熵是一定的,也就是说,当消息长度超过一定值的时候,产生摘要(MD5值)的过程一定会损失信息,即MD5值中包含的信息量是小于消息中包含的信息量的.而我们都知道,信息是不可能无端端"产生"的,也就是说,我们无法通过一个包含较少信息量的摘要来恢复出一个包含较多信息量的消息.

其次,从概率论的角度分析,MD5对于任何长度的消息都会产生一个相同长度的摘要,也就是说摘要的样本空间是固定的,对于128位的MD5,这个数值是2的128次方(really huge),而对于消息本身,没有任何限制,也就是说,消息的样本空间是无穷大.可以认为MD5的摘要产生是在消息的样本空间中等概率分布的,这样,平均到每个MD5值上的消息个数,就是无穷个(无穷大除以一个有限的数还是无穷大),假使我们试图通过一个确定的MD5值来恢复消息本身,就会遇上一个问题,有无穷个消息可以产生这个MD5值,是哪一个?我们不知道(究其原因,就是因为上面说到的"信息丢失了").只能去"尝试",而这样尝试找到原消息的概率,就是无穷大分之一,即是0.(当然,概率为0并不意味着没有可能)

最后,通过研究王小云博士的论文,我们可以看到,王小云博士整篇论文都是在attack(攻击),而不是crack(破解),她才用的方法,是MD5的差分分析(极其类似于我在前面几篇文章中写到过的DES差分分析),这样实际上产生的是一种非特定碰撞(两个不通消息产生同一个MD5值,叫collision,碰撞),而不是伪造签名需要产生的一个特定碰撞.比如说,我在某个网站上发布一个应用程序,为了防止心怀不轨者用一个恶意软件假冒我这个程序,我可以在网站上同时附上这个程序的MD5值(实际上,多数下载站就是这么做的,例如doute).下载者下载文件后,可以验证这个下载下来的文件MD5值和我在网站上提供的MD5值匹不匹配,若匹配,就放心安装,若不匹配,就说明这个文件有问题了.这种情况下,假若真有心怀不轨者想打着这个应用文件的幌子传播木马,他必须找到一个第二原象(即是另一个有着相同MD5值的不同程序),这个程序不仅要有相同的MD5值,还得能干他想要干的坏事(要不就没意义了).这就是一个典型的特定碰撞,这在王小云博士的研究成果中,是无法实现的.当然作为一个研究成果,它当然是有价值的,产生非特定碰撞,这在某些不需要找到原消息的地方,已经可以颠覆安全机制了,例如Linux的用户密码验证机制(Thank God, Windows没采用这种验证机制).Linux中,用户的密码是通过MD5值存储的硬盘中的(很容易获得),用户输入密码后,Linux计算出MD5值,然后和硬盘中的数据比较,判断输入密码对不对,这在王小云博士研究成果面世之前,是安全的,因为当时人们即使获得了密码的MD5值,也不能轻易计算出能产生这个MD5值的字符串(不一定需要和原密码相同,因为产生MD5值相同就会被Linux认为密码正确),王小云博士的研究成果面世后,人们可以请以计算出这个MD5值的一个非特定碰撞(同样,不一定需要和原密码相同),然后用这个产生的字符串,就可以当作正确密码登陆了.

综上三点,"破解"实际上是扯淡,也是误导,王小云博士的研究成果,远远没有达到"破解"的程度.当然,我们也不能否认她所做的贡献,她的成果,确实是对MD5密码分析上的一个跨越,用它的方法,至少,可以使搜寻MD5非特定碰撞的效率大大加快(现在要产生一个非特定碰撞,在主流pc机上,只需要秒这个数量级的时间了),而且,这对未来非对称密码体制的设计,也起到一个提醒作用,让设计者能把这种攻击考虑在内,设计出能抵抗这种差分攻击的密码体制,这也是密码学的一种进步. Anyway, looking forward to seeing that day....

下面的下载地址貌似被GFW墙掉了，如果你身在中国又需要下载，请挂国外代理访问。

P.S.1 王小云博士的三篇论文,我这几天在家仔细研究了很长时间
How to break MD5 and other hash functions [pdf]
Finding collision in the full SHA-1 [pdf]
Collision search attack on SHA-1 [pdf]

P.S.2 两个产生碰撞的能正常运行的程序实例,这也算一个特定碰撞吧,这还是我第一次看见,可以自行下载试验
2 collision applications

P.S.3 如有不妥,欢迎指出