Busted! A crisis in Cryptography
Celeste Biever
摘自第2530期新科学家杂志第44页,2005年12月17日
美国国家标准与技术研究院的密码学家 William Burr 在谈到中国密码学家王小云教授的时候说: "去年,我还庆幸地说还好她没有把 SHA-1 也破解了,但是现在,她真的这样做了"。现就任于清华大学的王小云教授在2004年破解了被广泛用于计算机安全系统的 MD5 函数,震惊了整个国际密码学界。2005年,她再次作出惊人之举,然而这一次,她又进了一步。
SHA-1 函数可以说是计算安全系统的基石,它由美国国家安全协会发明并认可,是计算机安全系统应用非常普遍的函数。但很快,这种情况将会被改变。Burr 称:"这就好比水管有了个裂缝开始渗水,结果很可能不是继续渗漏,而是导致整体的崩溃。"
SHA 是"安全散列算法"的首字母缩写。散列算法(Hash 算法)是一个有神奇作用的数学过程,它能把任意长度的数字信息变成某个固定长度的二进制字符串,不管原来的信息是一个字符还是几十页的文章。这个算法把原文件中的数位和其他随机选择的数位混合起来,从中提取特定长度的字符串即散列值。虽然散列值本身是无意义的,但它为验证原文件(也可能是签名,密钥)的完整性提供了捷径。
Hash 算法,或称 Hash 函数,被普遍应用于数字安全的几乎所有方面。登录办公室局域网、进入个人邮箱和安全页面都要用它来保护用户的密码;电子签名系统利用它来认证客户及其发来的信息;法律文书、财务信息和有版权的重要文件用它作为时间戳来确保数据不被篡改;银行系统使用它在用户输入信用卡密码之前确保网页的安全……总的说来,密码学家可以在他们设计的协议中灵活地使用它来增加安全性。美国著名密码学家 Bruce Schneier 这样说:"在我设计密码协议的时候,我处处都用到 Hash 函数,他们就象万灵药一样。"
Hash 函数的种类很多,而王教授破解的正是使用最广泛的两种。由麻省理工大学的 Ronald Rivest 教授于1991年设计的 Hash 函数 MD5,至今仍被应用于较早期的安全系统中。而由美国国家安全协会于1995年发明的 SHA-1 则正在为最新与最安全的系统服务。
是什么使得这两种函数得以普及呢?首先,它们非常复杂。用密码学家的话说就是"计算不可能"的----从计算量上来讲,无法由 Hash 值逆推得到原始的数据,这是一个相当理想的特点。此外,更为巧妙的是,以现有的计算能力不可能找到产生相同的 Hash 值的任何两组数据。
Hash 值都比较简短,例如 MD5 只输出128位的 Hash 值。因此足够大量的数据总能产生相同的 Hash 值。这些数据就产生"碰撞"。但 Hash 算法的设计使得以现在的计算能力几乎无法找到碰撞,更不要说由此来篡改数据或者签名了。就拿 MD5 来说,平均要264次猜测才能找到一组碰撞。
SHA-1 的位数要长一些,共有160位。它平均需要280次计算才能找到具有相同 Hash 值的两个数据。即使使用目前世界上最强大的计算机也需要数百万年的时间才能做到。至少人们都是这样认为的。但现在,王小云改写了这个数字。
她通过分析算法中各个阶段的数据变化来找出碰撞。当一个文件(或称为"信息")在进入演算过程的时候,数据就会在每一步中改变。如果用两个原来只差几个数位的信息进行运算,然后观察它们在每一步的变化,就有可能找到某种数学上的规律,从而发现可能产生碰撞的数列。但这可不简单,这需要有出众的思维能力。不过王教授正是这样的人。
"王教授拥有令人惊讶的能力,她能够看到演算的下几步,而且她具有一种直觉,能从成千上万的可能性中挑选出最好的路径。"清华大学的姚期智教授这样说。 IBM Watson 研究院的密码学家 Charanjit Jutla 认为王小云超凡的能力是对密码学界的一种警示,他说:"破解 Hash 函数非常艰难,但有的人就是会迎难而上的。就好比一个太复杂的谜,大多数人弄累了就放弃了,但是她没有。"
事实上,王小云发现对某些算法,只要找出碰撞路经就足以破解这种算法了。1997年,她通过成功地找出碰撞路径只用258次计算就破解了本需要280次的 SHA-0(SHA-1 的前身)。
至于 MD5,王小云发现它混合数据的步骤并不象 SHA-0 那样规律,要找出碰撞的途径比较困难。不过在中科院冯登国教授、上海交大来学家教授和她的博士生于红波的共同协助下,她还是成功地破解了 MD5。更重要的是,他们发现了一种能够自动修改那些不符合碰撞路径的消息的算法。通过这种方法,他们能够用改良了的信息得到碰撞。王小云教授在圣巴巴拉举行的2004年世界密码学大会上宣布了这一突破:她不仅能在237次计算后找到碰撞,而且已经在她的实验室里用计算机找到了碰撞。当时,全场的科学家们都震惊了。大会主席、普林斯顿 Hewlett-Packard 实验室教授 Stuart Haber 形容道:"这真是一个极具冲击力和令人鼓舞的结果,全场掌声雷动。"
好戏还在后头。现居美国 Greenwich 的华人研究员尹依群,在得知王教授破解 MD5 的方法后,也加入了王教授的研究团队,对 SHA-1 发起了攻击。
当然这次尝试更加艰难。SHA-1 的第一步就是"消息扩展",原本512位的信息块膨胀成2560位的信息。MD5 虽然也有"信息膨胀"的阶段,但那只是一些数位的重复。而 SHA-1 中原来的512位信息在进行一系列运算(加、减、各种轮换)的过程后衍生出新的复杂的数列组合。
但这些困难是无法击退王教授和她的合作者的。他们发现了这个函数的一个数学弱点,这使他们得以用计算机程序找到这样的信息对:经过信息扩展后的2560位信息中,不同的地方仅有44个位置。相异信息的大量减少使他们找到可能产生"碰撞"的信息更加容易。他们还应用了破解 MD5 时所用到的"明文修改"技术来增加找到"碰撞"的可能性。在2005年2月美国旧金山举行的 RSA 年会上,他们宣布他们发明了一种攻击方法,产生两个具有相同 SHA-1 输出值的消息仅用269次尝试,而不是人们预计的280次。
这一次,密码学家们完全慑服了。"这是密码研究学界的危机。"RSA 实验室主任 Burt Kaliski 在会议现场接受《新科学家》访问时表示。然而,王小云表现得更加谨慎,她说:"我认为这是一个好的消息,人们能够了解到现在的 Hash 函数的安全性,并设计出更安全的 Hash 函数。"
虽然这还不是一个直接的威胁--还没有人真正计算出 SHA-1 的碰撞。王小云所发现的只是一种快于强力攻击的方法。但是,不同于 MD5 的破解,还没有人真正破解 SHA-1。Burt Kaliski 说:"当一个密码学家说一种密码被破解,并不意味着所有人都能破开它,而是破解这种密码比原来应该需要的工作量要少。"来自 ICSA 实验室的密码学家 Mark Zimmerman 说:"这不是世界末日,但确实是漂亮的一击。"
然而,自从二月份宣布这个消息以来,在王小云与姚期智教授和香港城市大学的储风教授的共同研究下,他们再次降低了找到碰撞所需的计算量。目前的次数为 263次,这是一个重要的数字。因为如果用多台计算机来进行并行计算的话,只需一个月左右的时间就能找到产生碰撞的"信息对"了。哥伦比亚大学教授 Stephen Bellovin 说"虽然工作量很大,但这是完全可能实现的。"
在2005年十月底,Burr 在 Gaithersburg 召集了众多密码学家来讨论王教授的发现并研究对应的办法。许多与会的专家都想竭力证明王教授的发现是否真的有效。虽然这种攻击需要分布式计算,而且大量的网络计算机已经准备好实施这个任务了,但 Burr 并不鼓励这么做。他持有疑虑是因为一旦这个计划付诸实施并公布出结果,那么随便谁都能利用王的攻击了。
Burr 指出,电脑黑客不大可能依靠自己的力量找出碰撞,因为这需要借助数目庞大的个人电脑才有可能实现。尽管利用黑客程序控制大量的连网电脑有可能做到,但这种情况出现的可能性不大。如果研究者们完善了王小云的密码协议并发表了结果,它很可能会被黑客所利用。Burr 称:"如果你生成了碰撞,你等于替黑客们抬走了他们抬不动的大石头。"
针对王教授对 MD5 的攻击,人们已经开始利用她的碰撞了。例如一些密码学研究者已经向我们展示了在 PS,PDF 和 TIFF 文件中如何假造数字签名。这意味着经过 Hash 算法的数字签名附在一个合同上声明"约翰欠保罗100美元"可以被加在一个假冒的合同上,写着"约翰欠保罗50000美元"。不论使用什么样的方法来隐藏它的弱点,相同的攻击同样可以用在 SHA-1 上。
但是假冒的数字签名还不是最坏情况下的假设,有了原根的碰撞,很可能会有从 Hash 值逆推出明文消息的方法。Bellovin 说"是该意识到危机的时候了。"
如果 Hash 函数是可逆的,许多的"安全"应用,比如说安全的网络站点(一个以 https 而不是 http 开头的网络地址)将会突然的变得非常的不安全:你浏览器上的那个小小的封闭的挂锁可能什么用处都没有了。与此相似的是,密码和其他几乎每一个数字安全方面(的做法)都变成易受攻击的。"单向是非常关键的。"Schneier 说道。
到目前为止,还没有人能够找到一种方法可以利用王的破解。这也许是因为密码学家们才刚刚开始做她的后续工作。美国国家标准技术所的 John Kelsey 认为不能等待别人来找到彻底破解的方法。他说:"我担心等到别人公布出原根的攻击方法可能就已经太晚了。"
这种攻击将把数字安全推向何方?一种选择是把 SHA-1 函数变化一下,使之更加安全。Jutla 已经研发了一种技术,它使得 SHA-1 函数的消息扩展部分复杂了许多,从而让王的攻击失效。他说如果硬件和软件不作任何变化的话,这种技术仅仅使 SHA-1 函数慢了百分之五而已。而 RSA 的 Yin 和 Michael Szydlo 找到一种消息预处理技术,通过在进行 Hash 运算之前引入一个新的步骤使王的攻击失效。但那些试图延长 SHA-1 函数生命的做法是愚蠢的,也是危险的。"SHA-1 函数已被攻破,就像一条受伤的鱼会引来那些猎食的鲨鱼。" 微软的一位研究者 Niels Ferguson 这样形容道。
Ferguson 并不是唯一有这样想法的人;Gaitherburg 会议上的绝大多数人一致认为SHA-1 函数应该被尽快的逐渐淘汰。但这又提出了一个非常困难的问题:谁将取而代之?
一个很自然的选择是 SHA-256。SHA-256 是由 NSA 专门为在2020年取代 SHA-1 而设计的算法。因为预计那时已经有足够的计算能力来强力攻击 SHA-1 函数了。但有些人认为即使这样也不安全。"所有的设计都是相似的,"Schneier 说道,"从某方面来讲它是好的,因为我们对它的了解很多。但是,这也可能很糟糕,我们可能会被蒙蔽。"有些密码学家认为近期在 Hash 函数上取得的迅速的成功(近18个月来有5个算法被攻破)意味着它们整体都存在弱点。
不管最终的解决办法是什么,它一定很复杂。使用新的 Hash 函数算法将需要改变密码学、数字签名、电子商务和虚拟专用网络方面的大多数协议。在加州和 Eric Rescorla 一起工作的安全顾问 Bellovin 预计这将花费8年时间。其他分析员认为这个估计过于的乐观了,花费20年可能更加的现实一些。
尽管这样,没有什么是一定能得到保证的。也许另一个像王教授的这样的意外又会在什么地方发生。Schneier 认为这几乎是不可避免的。"攻击总是变得越来越好,"他这样说道,"它们决不可能变得越来越差。"
评论 (0)