密码学是理论计算机的一个很大的方向。之前准备先写密码学概论再提在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的碰撞。
上面的方法,只供参考和学术用途,实际使用所引起的后果概不负责。
相关推荐
王小云教授的论文(e文) 两个md5 相同的程序
( 王小云破解MD5How to Break MD5 and Other Hash Functions.pdf )
md5和sha-1算法代码及验证文件 在vc6.0调试运行无误,
hash函数对于从事计算机安全和网络安全的工作的朋友们一定不陌生,网上也有很多人写过这个程序,本程序附有自己的详细注释,对那些对md5函数不是很了解的朋友会大有帮助……
5.2 Hash函数MD5 5.2.1 MD5算法 5.2.2 MD5的安全性 5.3 安全Hash算法SHA-1 5.3.1 SHA-1算法步骤 5.3.2 SHA-1和MD5的比较 5.4 基于分组密码与离散对数的Hash函数 5.4.1 利用分组密码算法构造Hash函数 5.4.2 基于...
用C语言实现MD5哈希函数,它是将文件的每一行进行MD5加密,输出一个128位的哈希值。
本程序是c++程序,实现MD5的hash摘要
MD5生成hash序列MD5生成hMD5生成hash序列MD5生成hash序列ash序列MD5生成hash序列MD5生成hash序列
MD5CryptoServiceProvider md5 = new MD5CryptoServiceProvider();...string str = BitConverter.ToString(md5.ComputeHash(UTF8Encoding.Default.GetBytes(str))); C#的md5 ComputeHash方法,C语言实现
MD5加密解密工具,就我所知,MD5的目标是生成摘要。...据说有个叫王小云的女数学家破解了MD5算法,我觉得应该是看到一个MD5编码,就可以找到一个序列,生成的MD5编码刚好是被破解的那个MD5编码,这样的吧
Hash是一款小巧好用的哈希计算器,也是一款md5校验工具。支持文件拖放,速度很快,可以计算文件的 MD5、SHA1、CRC32 的值。 Hash md5校验工具在论坛上、软件发布时经常用,是为了保证文件的正确性,防止一些人盗用...
hash函数MD5算法,是对数据取摘要的密码算法,这里提供了它的源程序
Hash函数和数字签名 Hash函数和数字签名 Hash函数和数字签名
System.out.println(" 5. BKDR-Hash Function Value: " + ghl.BKDRHash(key)); System.out.println(" 6. SDBM-Hash Function Value: " + ghl.SDBMHash(key)); System.out.println(" 7. DJB-Hash Function Value: ...
关于hash函数的ppt
Hash算法MD5
md5校验器Hashmd5校验器Hashmd5校验器Hashmd5校验器Hashmd5校验器Hashmd5校验器Hashmd5校验器Hashmd5校验器Hashmd5校验器Hash
Hash MD5查看
hash函数之md5程序,可运行,包含testbench
但单从1991年到2001年这10年间,竟没有出现替代MD5算法的MD6或被叫做其他什么名字的新算法这一点,我们就可以看出这个瑕疵并没有太多的影响MD5的安全性。上面所有这些都不足以成为MD5的在实际应用中的问题。并且,...