|
本帖最后由 snowyleaf 于 2011-9-29 00:25 编辑
(申明:本系列讲座内容大量使用互联网公开文献,为便于理解可能会对原文内容、行文方式进行不同程度的修改。本系列讲座为的是普及科学知识,传播先进技术,不涉及任何商业成分。再此对所有互联网公开文献作者致以崇高的敬意!)
Hash 算法,或称 Hash 函数,被普遍应用于数字安全的几乎所有方面。登录办公室局域网、进入个人邮箱和安全页面都要用它来保护用户的密码;电子签名系统利用它来认证客户及其发来的信息;法律文书、财务信息和有版权的重要文件用它作为时间戳来确保数据不被篡改;银行系统使用它在用户输入信用卡密码之前确保网页的安全……总的说来,密码学家可以在他们设计的协议中灵活地使用它来增加安全性。
Hash 函数的种类很多,1991年麻省理工大学Ronald Rivest 教授设计的 Hash 函数 MD5 和 美国国家安全协会于1995年发明的 SHA-1 为最为常用的两种。
是什么使得这两种函数得以普及呢?首先,它们非常复杂。用密码学家的话说就是"计算不可能"的----从计算量上来讲,无法由 Hash 值逆推得到原始的数据,这是一个相当理想的特点。此外,更为巧妙的是,以现有的计算能力不可能找到产生相同的 Hash 值的任何两组数据。
Hash 值都比较简短,例如 MD5 只输出128位的 Hash 值。因此足够大量的数据总能产生相同的 Hash 值。这些数据就产生"碰撞"。但 Hash 算法的设计使得以现在的计算能力几乎无法找到碰撞,更不要说由此来篡改数据或者签名了。就拿 MD5 来说,平均要2^64次猜测才能找到一组碰撞。 SHA-1 的位数要长一些,共有160位。它平均需要2^80次计算才能找到具有相同 Hash 值的两个数据。即使使用目前世界上最强大的计算机也需要数百万年的时间才能做到。至少人们都是这样认为的。
但现在,中国的王小云改写了这个数字。王小云发现对某些算法,只要找出碰撞路经就足以破解这种算法了。1997年,她通过成功地找出碰撞路径只用2^58次计算就破解了本需要2^80次的 SHA-0(SHA-1 的前身)。2004年的世界密码学大会上她更是宣布:对于MD5哈希算法,她不仅能在2^37次计算后找到碰撞,而且已经在她的实验室里用计算机找到了碰撞。在2005年2月美国旧金山举行的 RSA 年会上,她宣布:产生两个具有相同 SHA-1 输出值的消息仅用2^69次尝试,而不是理论上的2^80次。
最新的资料表明:产生两个具有相同 SHA-1 输出值消息的尝试次数已经降为了2^63次。虽然这还不是一个直接的威胁--还没有人真正计算出 SHA-1 的碰撞。王小云所发现的只是一种快于强力攻击的方法。但是,不同于 MD5 的破解,还没有人真正破解 SHA-1。SHA-1 Collision Search Graz项目则是尝试通过2^63次的尝试第一次破解 SHA-1,或者说产生两个具有相同 SHA-1 输出值的消息。
对于DistrRTgen项目,则更像是通过枚举法枚举出每一组数据的各种哈希值(MD5、SHA-1值等),建立起一个巨大的哈希枚举表,以供大家逆向查询某个的特定哈希值可能代表的原始信息。
或者换个通俗说法,如果说SHA-1 Collision Search Graz是试图在一大群人中找出身份证重号的人,那么DistrRTgen项目则更像是逐个登记每个人的身份证号以便用来找出某一特定身份证号的人(也包括可能有的重号的人)。但从本质上来说SHA-1 Collision Search Graz项目与DistrRTgen项目的实质都是相同的,都是寻找具有相同哈希输出值的消息。
理论上由于Hash算法是不可逆算法,因此对于哈希算法的逆运算不可能还原加密的原文。但是查找哈希值枚举表(这就是DistrRTgen项目的成果),确实可能查找出加密的原文。
但是无论是DistrRTgen还是SHA-1 Collision Search Graz,对于密码技术的发展都有相当巨大的意义。无论是通过碰撞尝试还是通过创建哈希值枚举表,每一次尝试都有可能发现两组(或者)更多具有相同哈希输出值的消息。这样的行动都将有利于人类密码水平的进步。 |
评分
-
查看全部评分
|