hash碰撞,生日攻击

这里有一个合同交易的故事。
假设Bob和Alice在谈一桩生意。最后两人把价格谈好了,100万美元。Bob为Alice起草了一份合同,合同的内容就是Alice从Bob那里以100万美元的价格买下一件产品。
按照通常的程序,如果双方都同意一份合同有效,这份合同就会先用一个安全系数很高的hash函数映射到一串长度为n的二进制值(也就是说hash值的理论个数为2^n)。然后Alice和Bob对这个hash值进行数字签名(digital signature)。
一个hash函数的特点就是可以把任意长度的文档(或二进制串,以下直接称文档)映射到长度为n的二进制值,这种映射是多对一和单向的。安全性好的hash函数H应当具备以下三个特点:
1. 给定任意一个二进制串b,找到hash之前的文档t(也就是说使得H(t)=b)非常困难。这里的困难指的是如果用计算机枚举,将会花费大把时间,基本上在允许的时间范围内不可行。
2. 给定任意一个文档 t1,找到另外一个文档 t2,使得用hash函数之后得到的两个二进制值相同(H(t1)=H(t2))非常困难。
3. 找到t1和t2,使得H(t1)=H(t2)非常困难。这个条件也称为hash碰撞。
由于密码学中的hash函数具有以上特点,人们经常对文档应用hash函数,用hash值来证明文档的存在性。
比如一个科学家在某个时间点发现了自然界一个重大规律,但是他又不想把这个规律公开给全世界,同时他得证明他确实发现了这个东西并记录到了一个文档中,防止今后有人发现同样的规律被抢了成果。那么他就可以对自己的文档应用hash函数,然后把hash值在某个时间点公布。以后有人要他证明之前已经发现了这个规律,他可以把自己的文档再用相同的hash函数求值,如果得到的hash值和之前公布的值一样,说明他的确很早以前发现了这个规律。这种技术称为time-stamp,在学术界应用广泛,比如上传到arxiv的文章都会关联到一个time-stamp。这种技术行得通的一个很重要原因就是从某个文档得到的hash值通常情况下只有再对这个文档应用hash函数才能得到相同的值。虽然理论上肯定有其他文档也具有同样的hash值,但是找到那些文档的计算复杂度相当高以至于基本不可行。

回到问题中,假如Bob和Alice暂时不想公开合同的内容(如果以后需要第三方的公证),他们就可以在合同的hash值上签字。合同的任何一方持有者可以对合同应用hash函数从而证明合同的合法性。
但是现在贪财而邪恶的Bob想骗取Alice为这件产品签下价格为1000万美元的合同。Bob目前手头有一台牛逼的计算机,他愿意付出O(2^(n/2))的计算时间去赢取那额外的900万美元(注意n是hash值的二进制长度)。而且实际情况是,Bob成功的机会非常高。那么他会怎么做?

现在暂时跳出这个问题,我们来看看怎样攻击hash函数的第三个特点。第三个特点比前面两个条件都宽松了许多,因为前面两个都是给定一个值,找到另一个hash值相同的。而第三个特点只要求我们找出存在的一对t1和t2,使得H(t1)=H(t2)。
相信大家都听过生日悖论(birthday paradox)。如果一个房间里有23个或23个以上的人,那么至少有两个人的生日相同的概率要大于50%。这个结果和直觉不太相符,不相信的人可以拿笔算算。这说明,如果我们挑选出了一组文档,那么其中至少有两个文档的hash值相同的概率将会大大提高(假设一个文档被映射到任何一个hash值的概率相同)。
现在来算一下一个例子。假设我们有两组文档X和Y,每一组里都有m=2^(n/2)个文档,那么X组里至少有一个文档会和Y组里某个文档发生hash碰撞的概率是:
对Y组里的第一个文档进行考察,它和X组里的第一个文档发生hash碰撞的概率是1-1/(2^n)。由于2^n >> 2^(n/2) (一般情况下对于一个安全的hash函数n>=128),因此Y组的第一个文档不和X组里任意文档发生碰撞的概率约为( 1-1/(2^n) )^m。那么Y组中所有文档都不和X组中文档发生碰撞的概率是( ( 1-1/(2^n) )^m )^m 约等于 e^-1。所以Y组中至少有一个文档和X中某个文档发生hash碰撞的概率是1-e^-1 = 0.63 > 0.5。
这个例子说明的问题就是,如果我们能枚举两组文档,每组文档的个数为2^(n/2),其中n是hash值的二进制长度,那么两组文档发生hash碰撞的概率大于0.5。

有了这个关键的结论,现在我们来看看Bob怎么让 Alice签下1000万美元的合同。
首先Bob起草两份合同,一份上面写100万美元(A),另一份上面写1000万美元(B)。这个时候如果用hash函数,这两份合同的hash值肯定不同。所以Bob不能直接让Alice签了A然后跑到法院去说她签了B,因为H(B)的值和当时两人签字的值H(A)不一样。
Bob现在拿出他的牛逼计算机,首先枚举一个长度为n/2的二进制串,枚举的复杂度为2^(n/2)。然后将这个二进制串转化为ASCII码。这样就可以得到一串比较奇怪但是很短小的字符串。然后把这2^(n/2)个字符串分别插入A和B中,得到2 * 2^(n/2)个变种合同,其中有2^(n/2)份上面写着100万美元(记为X组),另外2^(n/2)份上面写着1000万美元(记为Y组)。之后就可以进行生日攻击了,对所有的变种合同求hash值(2*2^(n/2)复杂度),根据之前计算的结果,有0.63的概率X组的某个合同和Y组的某个合同有相同的hash值。求完之后,对X和Y组里的hash值排序,则只需要2*2^(n/2)步就可以找到相同的hash值。
现在最关键的一步来了。Bob得到了写着100万美元的合同A',同时也有写着1000万美元的合同B',最为重要的是,我们知道H(A')=H(B')。那么他只需要给Alice看合同A'。一般合同都是又长又臭,很多法律专业术语,Bob之前只插入了一个长度为n/16的ASCII字符串(我们假设n=128,那么这个字符串的长度只有8!,并且Bob可以分散字符串的内容将字符一个个插入不同的位置)。Alice在某个点忽略了那可疑的8个字符,签了100万美元的合同A'。然后双方在hash值H(A')上签了字。
之后Bob就可以大摇大摆地拿着合同B'去法院要求Alice支付1000万美元,因为他可以拿出合同B',上面写着1000万,然后应用hash函数,得到的hash值将会和他们两人当时签名时的hash值一样。
可怜的Alice!


Comments are closed.