理论计算机初步：从hash函数到王小云的MD5破解

zhiqiang九月 18, 2006
密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在hash函数破解上做出重大贡献的王小云教授的工作，不过前两天，在媒体上又掀起了一轮宣传狂潮，但是有些报道极端弱智，错误百出，所以我趁机纠正一下，并介绍密码学的一个组成部分——hash函数，以及王小云在这上面的工作。
王小云的主要工作是关于hash函数的破解工作。她在2005一个密码学会议上宣布破解了SHA-1，震惊了全世界。所以要介绍和理解她的工作，先看一下hash函数具体是怎么回事。
简单的说，hash函数就是把任意长的输入字符串变化成固定长的输出字符串的一种函数。通俗得说，hash函数用来生成信息的摘要。输出字符串的长度称为hash函数的位数。
目前应用最为广泛的hash函数是和，大多是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-1的理论破解，她证明了160位SHA-1，只需要大约2^69次计算就能找出来，而理论值是2^80次。她的寻找MD5碰撞的方法是极端高效的。传说王小云当时在会议上把碰撞写出来，结果被下面的人验证发现不对，原来她把MD5算法的一个步骤弄错了。但是她立马联系她的当时留在中国的学生，修正算法，并找到一个新的碰撞。这一个是对的。
看到这里，那些认为中国国安局应该将这些结果封存作为秘密武器甚至幻想用这些成果来袭击美国之徒可以停住你们的YY了。这种形式上的破解，在大多数情况下没有实际性的作用。更别提MD5早就被美国人抛弃了。
但是，说这种破解一点实际意义都没有，那就侮辱了广大密码学家的智商，密码学家不会无缘无故的弄出碰撞这么一个概念来。下面简单的介绍一下在特定情况下，怎么利用给定的碰撞来做坏事(翻译自)：
Caesar给实习生Alice叫写了一封推荐信(letter)。同一天，Alice叫Caesar在推荐信上数字签名，并提供了一份推荐信的电子板。Caesar打开文件，发现和原件一模一样。所以他在文件上签了名。
几个月后，Caesar发现他的秘密文件被非法察看。这到底是怎么回事呢？

a25f7f0b 29ee0b39 68c86073 8533a4b9
事实上，Alice要求Caesar签名的文件已经被Alice做了手脚，准确地说，Alice还准备了另外一个文件，它们的MD5码完全一致。而Caesar的数字签名还依赖于MD5算法，所以Alice用order文件替换Letter文件之后，Caesar的数字签名依然有效。那封order给Alice提供了察看秘密文件的权限。
具体的实现方法可见。我在这里简单的解释一下(只是大致思路，具体实现方式，需要对文件结构信息有所了解)：
letter文件的内容是：
if(x1==x1) show "letter" else show "order"
order文件的内容是：
if(x2==x1) show "letter" else show "order"
其中字符串"letter"和"order"代表两封信实际显示的内容。x1，x2是一个MD5的碰撞。
上面的方法，只供参考和学术用途，实际使用所引起的后果概不负责。
参考：
, wikipedia
, wikipedia
PS：我跟王小云老师的接触很少，上过俩次她的讨论班而已，亦感觉到王小云老师的严谨和耐心。在去年一个Turing奖获得者的演讲上，王小云提问的时候竟口而出“I ask who”的中式英语，在引起哄笑的同时，我也极端佩服她的勇气。也许只有这样才能做出非常好的工作吧。
PS2: wikipedia在国内可以通过浏览。
关于, , , , ,  »
题外话：此篇隶属于理论计算机(TCS)系列。 昨天，RSA实验室的首席科学家Burt Kaliski（同时也是副总裁）给我们做了一个讲座，关于最新的One-Time Password...
在从hash函数到王小云的MD5破解我们介绍了hash函数的一些基本概念和MD5碰撞的一个“应用”，最近在这个问题上又有了新的进展。 Marc Stevens, Arj...
这段时间Blog的更新频率大大降低，因为发现没啥好写的，也没有写文章的欲望。前段时间提到了我加入中国赛客联盟，而且给的说明语是"算机|数学|算...
P = NP? 这个问题，作为理论计算机科学的核心问题，其声名早已经超越了这个领域。它是Clay研究所的七个百万美元大奖问题之一，在2006国际数学家大...
上篇文章已经提到，P vs NP是理论计算机科学的核心问题。从数学的角度来说，它和其他历史上有名的数学问题一样，给与人们一个智力上重大的挑战。...
前面已经提到了显示中大多数难解问题问题最后都被证明是NP-完全问题。这意味着，除非NP=P，它们是不可能有多项式时间算法的（而且，在这篇文章提...