Birthday Attack and Wagner Attack
Table of Contents
1. Birthday Attack
生日问题(Birthday Problem)是指:一个有 30 名学生的班级,存在两名学生同一天生日的概率是多少?答案是 70.63%,这是一个很可能发生的事件了,因为概率已经超过 50% 了,由于这个结论不符合人的直觉(直觉往往认为概率要比 70.63% 小得多,毕竟一年有 365 天),所以也称为“生日悖论”。
生日问题也可以换一种问法:在一个班级中,最少需要几人,当中两名学生同一天生日的概率才会过半?答案是 23 人。
这里省略具体的推导过程,可参考:阮一峰的网络日志,哈希碰撞与生日攻击 。
1.1. 相关密码学攻击
利用生日问题对密码学设施进行的攻击被称为生日攻击(Birthday Attack)。
比如,对于 64-bit 的哈希函数,有大概
又如,Pollard's kangaroo algorithm 和 Pollard's rho algorithm for logarithms 都是利用了生日攻击来尝试破解离散对数问题。
2. Wagner's Generalized Birthday Attack
2002 年,David Wagner 在论文 A Generalized Birthday Problem 中把生日问题进行了推广。
2.1. k-sum 问题
Wagner 提出了一个更加一般化的生日问题(“k-sum 问题”):设有
当
2.2. k-tree 算法(Wagner Attack)
对于 k-sum 问题,Wagner 给出了方法,并称之为 k-tree 算法(其它人一般叫它为 Wagner's Generalized Birthday Attack,简称 Wagner Attack),其中时间复杂度为
下面以
每个元素都有 比特位,首先我们从 中寻找部分低比特位(如低位置的 个比特位)相同的那些元素 ,也就是说寻找满足 的 ,我们得到新列表 ;- 使用和上一步类似的方法处理
,得到满足 的新列表 ; - 在
和 中寻找满足 的元组。由于 的低 个比特位已经都为 ,只需要检查剩下的 个比特位是否相同。一旦找到这样的 ,对应的 显然会满足 。
Figure 1: A pictorial representation of k-tree algorithm for the 4-sum problem
当
需要指出的是:k-sum 问题中
2.3. 相关密码学攻击
Wagner Attack 告诉我们: 如果一些随机串(比如 16 个)相加会得到某一个数,那么在不知道原始随机串情况下寻找出满足这个约束(即相加为某个指定数)的另外一些随机串并不是那么难,可以在亚指数时间(
Wagner 在论文的第 4 节给出了受 k-tree 算法影响的协议,比如:
- Schnorr blind signatures
- Incremental hash (NASD incremental hashing, AdHash, The PCIHF hash)
- Low-weight parity checks
- Group signatures