密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在 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
Q. E. D.
