理论计算机初步：从hash函数到王小云的MD5破解
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在hash函数破解上做出重大贡献的王小云教授的工作，不过前两天王小云获得求是杰出科学家奖以及100万奖金，在媒体上又掀起了一轮宣传狂潮，但是有些报道极端弱智，错误百出，所以我趁机纠正一下，并介绍密码学的一个组成部分——hash函数，以及王小云在这上面的工作。
王小云的主要工作是关于hash函数的破解工作。她在2005一个密码学会议上宣布破解了SHA-1，震惊了全世界。所以要介绍和理解她的工作，先看一下hash函数具体是怎么回事。
简单的说，hash函数就是把任意长的输入字符串变化成固定长的输出字符串的一种函数。通俗得说，hash函数用来生成信息的摘要。输出字符串的长度称为hash函数的位数。
目前应用最为广泛的hash函数是SHA-1和MD5，大多是128位和更长。
hash函数在现实生活中应用十分广泛。很多下载网站都提供下载文件的MD5码校验，可以用来判别文件是否完整。另外，比如在WordPress的数据库，所有密码都是保存的MD5码，这样即使数据库的管理员也无法知道用户的原始密码，避免隐私泄露（很多人在不同地方都是用的同一个密码）。
如果两个输入串的hash函数的值一样，则称这两个串是一个碰撞(Collision)。既然是把任意长度的字符串变成固定长度的字符串，所以，必有一个输出串对应无穷多个输入串，碰撞是必然存在的。
一个“优良”的hash函数 f 应当满足以下三个条件：
- 任意y，找x，使得f(x)=y，非常困难。
- 给定x1，找x2，使得f(x1)=f(x2)，非常困难。
- 找x1，x2，使得f(x1)=f(x2)，非常困难。
上面的“非常困难”的意思是除了枚举外不可能有别的更快的方法。比如第3条，根据生日定理，要想找到这样的x1，x2，理论上需要大约2^(n/2)的枚举次数。
几乎所有的hash函数的破解，都是指的破坏上面的第三条性质，即找到一个碰撞（前两条都能被破坏的hash函数也太弱了点，早就被人抛弃了）。在密码学上还有一个概念是理论破解，指的是提出一个算法，使得可以用低于理论值得枚举次数找到碰撞。
王小云的主要工作是给出了MD5，SHA-0的碰撞，以及SHA-1的理论破解，她证明了160位SHA-1，只需要大约2^69次计算就能找出来，而理论值是2^80次。她的寻找MD5碰撞的方法是极端高效的。传说王小云当时在会议上把碰撞写出来，结果被下面的人验证发现不对，原来她把MD5算法的一个步骤弄错了。但是她立马联系她的当时留在中国的学生，修正算法，并找到一个新的碰撞。这一个是对的。
看到这里，那些认为中国国安局应该将这些结果封存作为秘密武器甚至幻想用这些成果来袭击美国之徒可以停住你们的YY了。这种形式上的破解，在大多数情况下没有实际性的作用。更别提MD5早就被美国人抛弃了。
但是，说这种破解一点实际意义都没有，那就侮辱了广大密码学家的智商，密码学家不会无缘无故的弄出碰撞这么一个概念来。下面简单的介绍一下在特定情况下，怎么利用给定的碰撞来做坏事(翻译自Attacking Hash Functions)：
Caesar给实习生Alice叫写了一封推荐信(letter)。同一天，Alice叫Caesar在推荐信上数字签名，并提供了一份推荐信的电子板。Caesar打开文件，发现和原件一模一样。所以他在文件上签了名。
几个月后，Caesar发现他的秘密文件被非法察看。这到底是怎么回事呢？
a25f7f0b 29ee0b39 68c86073 8533a4b9
事实上，Alice要求Caesar签名的文件letter已经被Alice做了手脚，准确地说，Alice还准备了另外一个文件order，它们的MD5码完全一致。而Caesar的数字签名还依赖于MD5算法，所以Alice用order文件替换Letter文件之后，Caesar的数字签名依然有效。那封order给Alice提供了察看秘密文件的权限。
具体的实现方法可见Hash Functions and the Blind Passenger Attack。我在这里简单的解释一下(只是大致思路，具体实现方式，需要对文件结构信息有所了解)：
letter文件的内容是：
if(x1==x1) show "letter" else show "order"
order文件的内容是：
if(x2==x1) show "letter" else show "order"
其中字符串"letter"和"order"代表两封信实际显示的内容。x1，x2是一个MD5的碰撞。
上面的方法，只供参考和学术用途，实际使用所引起的后果概不负责。
参考：
- Attacking Hash Functions by Poisoned Messages "The Story of Alice and her Boss"
- Hash function, wikipedia
- SHA, wikipedia
- Interview with Yiqun Lisa Yin concerning the attack on SHA-1
PS：我跟王小云老师的接触很少，上过俩次她的讨论班而已，亦感觉到王小云老师的严谨和耐心。在去年一个Turing奖获得者的演讲上，王小云提问的时候竟口而出“I ask who”的中式英语，在引起哄笑的同时，我也极端佩服她的勇气。也许只有这样才能做出非常好的工作吧。
PS2: wikipedia在国内可以通过free_door浏览。
嗯,知道了什么叫hash函数,呵呵
问一个浅显的问题
我现在Rss Reader换用FeedDemon了,发现FD本地保存的文件都是xxx-xxx-xxx-xxx.rss,文件名的长度也的确都一致,这个是不是用的hash函数?
应该就是的。hash函数的应用极为广泛，我上面只随便挑了两个说说。
这个是GUID全球唯一编码
这个写的不错，图文并茂：）
鼓鼓掌！
这里的东西越来越深奥了
明白了，这么说来那些BT或者电驴就是用HASH函数来保证文件没被修改的。
我也明白了，MD5
赶快出MD5的破解软件吧
其实理论上没有绝对安全的密码算法
在发生破坏之前把已经找到的相互碰撞的字符禁用
”Caesar发现他的秘密文件被非法察看“ 这里的秘密文件是指哪个？？？
比如说公司的秘密文档，是一个泛指。
你可以点letter和order链接看一下里面的具体内容，发现它们一个是推荐性，另外一个则是一封授权书，但它们的MD5码一模一样。
王老师是我们学校数学院的，有幸见过，看起来很普通的人。不过做学问的大抵如此。
山东大学？现在不是了
对不起，我想问一下：按照上面的例子，Alice是如何“凑”出那份order的？
因为按照Hash的三个条件的第二条：
现在Alice只是拿到了x1（即letter），按道理她是很难找出x2（order）的呀？
因为现在MD5破解打破的是第三条，即“找x1，x2，使得f(x1)=f(x2)，非常困难”。
如果letter（x1）和order（x2）都是Alice自己写的，她是可以使得这两个发生“碰撞”，但是问题现在x1是由她的导师Caesar写的啊。
您能解释一下吗？
那封letter虽然是Caesar写的，Alice在里面添了一些不可见的东西，具体说了，她把letter变成了 if(x1==x1) show "letter" else show "order"，这样一来，Caesar看到的就是letter的内容，所以就没有疑心的签了名，但这封letter此时的MD5码与 if(x2==x1) show "letter" else show "order"这个文件order的MD5是一样的，但后者实际显示的是order的内容。
你可以把那两个东西下载回来看一看，很神奇的。王小云的MD5碰撞绝对不只只有理论价值。
顺便说一下，你的blog很不错，我已经收藏 ;-)
是啊 ，很棒啊，可惜我搞一个相册，通宵，还没有搞定，唉。对我来说太难了。
呵呵，不是很明白~~回去再想一想`~谢谢~~~
真是特别的佩服，ZHIQIANG的文章写的让我们这些完全的门外汉似乎都理解了王老师的工作。
希望王老师的工作会有更大的突破！