分享

      前一阵子在《弯曲评论》上的讨论中，大家谈到了密码学和协议的安全性问题。目前广泛使用的MD5、SHA-1、AES等算法都是公开的，这会不会导致这些算法不安全呢？而国内的众多媒体渲染的，“山东大学王小云教授破解MD5加密算法”究竟是何种成就？看大部分中文媒体是基本得不出结论的，因为许多记者喜欢用劳动人民喜闻乐见的词语把一件事情说得惊天动地来装噱头，而真正的专业知识几乎找不到。正好前几天杰夫的文章《百万美元悬赏：求解七大世纪难题》提到了徐迟写《哥德巴赫猜想》的事情。当年徐迟虽然有点夸大哥德巴赫猜想在数学界的地位，可是在专业上是一丝不苟的——数学不是徐迟的专业，可是也一点不敢马虎，生怕报道出现什么硬伤。王小云的成就也需要一些一丝不苟的文章来说明。

      从头说起，密码学（Cryptography）这个词源于希腊语kryptós（意即“隐藏的”）和gráphein（意即“书写”）。望名知意，密码学是研究如何隐密地传递信息的学科。在现代特别指对信息以及其传输的数学性研究，常被认为是数学和计算机科学的分支，和信息论也密切相关。

      二战以前，经典密码学的研究往往只考虑信息的机密性（confidentiality）：如何将可理解的信息转换成难以理解的信息，并且使得知道如何转换的人能够逆向回复，但不知道如何转换的拦截者或窃听者则无法解读。用行话说，这个“转换”就是加密算法。经典密码学拼命的研究更优秀的基于文本语言的加密算法，而知道了加密法就能一览无余的破译密电。这就是为什么描述以前战争的电影中，那个“码本”总是非常关键，我军打入国军内部的红色间谍工作都围绕它展开。

      十九世纪以来，学者们开始认识到算法保密并非理想的防护手段。柯克霍夫原则（Kerckhoffs’ principle）就明确提出，“即使密码系统的任何细节已为人悉知，它也得是安全的。”信息论鼻祖香农也有句近似的话“敌人了解系统”。于是密码学开始研究更“好”的加密算法——用这种加密算法产生密钥（key）来加密要保护的内容，安全寄托在密钥上而不是算法上。即使敌人知道了使用何种加密算法，只要密钥未泄露，理应足以保障资料的机密性。通常认为，1970年代中期当时的美国国家标准局（现在是国家标准技术研究所NIST）公布由IBM开发的DES这一事件推动了现代密码学的公开学术研究。

      现代密码学的主要领域包括：密码学原理（如探索单向函数、求解椭圆曲线函数等）、密码分析学（发现密码机制的弱点，如加快求解整数分解问题的速度）、公钥密码学（主要成果如RSA、DSA、椭圆曲线密码）、密码协议（如MIT开发的Kerberos）等等。

      好了，现在可以说到王小云教授的研究领域了：密码分析，简而言之就是找别人算法的漏洞破密。为什么这个研究课题会有存在的必要呢？这又要扯回去谈几句。现代密码学开始在加密算法公开的条件下，研究如何保护和传递密钥。也就是说，保密性不再寄托在算法上，而在密钥上。试想，如果保密性寄托在算法上，算法一泄漏，整个系统的保密性就没有了。如果保密性基于密钥，密钥泄露了信息也可能泄密，但是泄露一个密钥对系统的影响小多了——每个加密都选不同的密钥，互不干扰，一个泄露不影响另一个；其次密钥可以随着时间不断地变，把泄漏受影响数据的时间窗降到秒级。

      这样看起来，破解单单某一个密钥没什么用，要破还是要破解算法（注意这里说的是破解，不是说知道算法，算法是公开的）。二战以后，计算机与电子学的发展也促进了破密分析的发展，抵消了某些加密算法的优势。不过，优良的加密算法仍保持领先，通常好的加密算法都相当有效率（快速且使用少量资源），而破解它需要许多级数以上的资源，使得破密变得不可行。王小云教授做的，就是分析这些算法的漏洞，比如证明其理论上不够严密，比如找到方法使得破解它的资源大大减少使得破解可行。

      下面该谈到更具体的技术了。在现代密码学体系结构中，hash函数是一个很重要的部分。关于它的译法，有说杂凑函数，有说哈希函数，有称散列函数，笔者这里保持原始英文名称。Hash函数和许多重要的密码算法相关，被普遍应用于数字安全的几乎所有方面。美国著名密码学家Bruce Schneier 这样说：“在我设计密码协议的时候，我处处都用到Hash函数，他们就象万灵药一样。”

      依照数据结构的简单定义，hash函数描述一种映射关系，将输入数据映射成输出的hash值，通常hash值比输入数据要短得多，例如，在数据库中把数据通过hash映射成其存储地址。在密码学中，hash函数的作用是把任意长的输入字符串映射成固定长的输出字符串。这个过程可以描述成：hash函数用来生成信息的摘要。输出字符串的长度称为hash函数的位数。目前应用最为广泛的hash函数是SHA-1（160位）和MD5（128位）。顺便说一句，SHA家族的五个算法是SHA-1, SHA-224, SHA-256, SHA-384, 和 SHA-512，由美国国家安全局 (NSA) 所设计，国家标准技术研究所发布。至于SHA-0，1993年发布后就很快被撤回，从未正式进入SHA家族。

      如果两个不同的串经hash函数计算得出完全相同的hash值，则称这两个串是一个冲突(Collision)。既然没有长度限制的串都经过hash产生一个相同长度的串，那么根据鸽笼原理（中国学生更熟悉的译法是抽屉原理，简单描述是：若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子），这个hash函数就一定会有冲突。冲突后会怎样？举个例子，如果两个指令“向目标发射核弹”和“给我订午饭”冲突，它们的hash值，即摘要，对接收方放而言是一致的。如果接收方把后者当成前者执行……

      一个“好”的hash函数，要（1）保证输入串和输出串没有统计上的相关性，（2）也无法从hash值得到原串，（3）而且要让冲突的发生非常困难。几乎所有的hash函数的破解，都是指的找到一个冲突（前两条都能被破坏的hash函数也太弱了点，属于第一时间就要抛弃的）。一直以来，对于公认的“好”hash函数，并非无法冲突，而是业界都认为要任意制造出冲突需要的时间太长，在实际情况上不可能发生——比如，通过强力攻击（brutal force）来穷举，SHA-1算法是160位的。如果用它来验证2^160+1个字符串，根据鸽笼原理，会有至少两个串的校验码是一样的。这样就找到了一个冲突。实际上，因为算法的特殊性，概率上只需要2^80次计算。想找到这样一个冲突，计算者可能要鞠躬尽瘁了。算个一万年才找到冲突，猴子都进化成人了。而且，找到了冲突不等于找到了一个有用的冲突。

      而王小云教授的发现可能会打破这个必然性。王小云从事的是理论破解，她致力于提出算法使得可以用低于理论值的穷举次数找到冲突。她的主要贡献是给出了MD5，SHA-0的冲突，以及SHA-1的理论破解。

      2004年8月在加州Santa Barbara举行的国际密码讨论年会（CRYPTO）上，王小云及其同事展示了MD5和SHA-0的hash冲突。她不仅能在2^37次计算后找到冲突，而且已经在她的实验室里用计算机找到了冲突。这个成果当时就震惊了全世界。

      2005年2月，在美国旧金山举行的 RSA 年会上，王小云教授宣布他们证明了160位SHA-1，只需要大约2^69次计算就能找出冲突，而如前所述，理论值是2^80次。由于SHA-1函数广泛应用于现今的主流产品，其影响可想而知。这还不是对SHA-1直接的威胁——还没有人真正计算出SHA-1的冲突。王小云所发现的只是一种快于强力攻击的方法。但是，这意味着，还没有被真正破解的SHA-1，其防护壁上已经被人凿出了凹洞。来自ICSA 实验室的密码学家Mark Zimmerman 说：“这不是世界末日，但确实是漂亮的一击。”

      2005年8月，王小云、姚期智，以及姚期智妻子姚储枫（香港城市大学教授，为Knuth起名高德纳的人）联手于当年国际密码讨论年会（还是在加州Santa Barbara）提出SHA-1函数hash冲突算法的改良版。此改良版使破解SHA-1时间缩短为2^63步。

      2005年之后到目前为止，还没有人能够找到一种方法可以利用王小云教授的破解。这也许是因为密码学家们才刚刚开始做她的后续工作。无论如何，王小云教授已经站在了密码学界的顶峰。

      唠唠叨叨了这么多，笔者最后要重申一句，MD5，SHA-0，SHA-1等hash算法都是公开的。因为“加密算法不公开”而声称自己是安全的协议，恐怕在两个世纪前还可行。在今天的密码学研究背景下，这个论断看起来非常可笑。

分享