[forward] 生日攻击 Alice & Bob

gistfile1.txt

hash碰撞，数字签名，生日攻击——Alice怎样才能被Bob骗去签巨额的合同
作者 :  余昊男
这里有一个合同交易的故事。
假设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！