markdown
公钥-合约碰撞攻击的完整成本
Dmitry Khovratovich
问题陈述
以太坊地址作为公钥的函数，被计算为 160 位哈希值：
$$
A{PK} = Keccak{256}(K)[0..160]
$$
其中 $K=[k]P$ 是从秘密密钥 $k$ 派生的公钥，而 $[0..160]$ 表示我们只取输出的 160 位。请注意，$Keccak_{256}$ 与标准化的 SHA-3 略有不同。
以太坊合约地址以两种方式创建。首先，当合约常规部署时，它是 nonce 和创建者地址的哈希值：
$$
A{CT} = Keccak{256}(encode_1(A,N))[0..160]
$$
其中 $N$ 是从 1 开始的 nonce。
其次，通过 CREATE2 指令，合约代码 $C_d$ 也被哈希：
$$
A{CR} = Keccak{256}(encode2(A,S,Keccak{256}(C_d)))
$$
其中 $S$ 是任意的 32 字节 salt。
显然，通过尝试 $2^{80}$ 个 $K_i = K+[i]P$ 变体和 $2^{80}$ 个 salt 值 $S_j$，可以获得地址碰撞：
$$
A{PK}^i = Keccak{256}(Ki)[0..160] = A{CR}^j = Keccak_{256}(encode_2(A,Sj,Keccak{256}(C_d))).
$$
请注意，$encode$ 函数确保了 $A{CR}$ 和 $A{PK}$ 的原像在域上是分离的，因此输入中不可能发生碰撞。
我们研究创建这种碰撞的成本会是多么昂贵。
并行区分点方法
存在一种简单的无内存碰撞搜索方法。它基于用于单个函数 $f$ 碰撞的 rho 方法：
- 从输入 $x$ 开始；
- 使用两个指针：一个迭代 $f(x)$，另一个同时迭代 $f(f(x))$。
- 每当两个指针碰撞时，它们的路径上必然发生过碰撞。
两个函数 $f_1$ 和 $f_2$ 之间的碰撞搜索工作方式相同，我们只是在迭代时以伪随机方式在 $f_1$ 和 $f_2$ 之间切换。函数 $f_1,f2$ 正好是用于推导 $A{PK}$ 和 $A_{CR}$ 的函数，唯一的注意事项是它们必须将输入空间映射到相同的域。这通过固定除 $[i]$ 和 $S_j$ 之外的所有输入并将哈希输出映射到这些输入来实现。例如，
$$
f1(x) = Keccak{256}(K+[x]P)[0..160]
$$
发现的碰撞有 $1/2$ 的概率是 $f_1$ 和 $f_2$ 之间的碰撞。需要恒定内存。请注意，函数 $f_1$ 接受一个 256 位输入并将其映射到值 $i$，这不是低权重。因此，$f_1$ 的单次迭代是曲线点乘法。
该方法的缺点是它需要相当于 $2^{80}$ 次 Keccak+KeyDerivation 调用的时间，这显然是巨大的。van Orrschot 和 Wiener（1996）提出了一种并行版本的碰撞搜索。
我们用 $m$ 表示可用 Keccak 处理器数量。然后每个处理器从自己的点 $x_0$ 开始，迭代 $f$ 直到达到一个区分点（例如，最后 10 位为 0）。然后将其存储在公共内存中，如果与已存储的点没有碰撞，则重新开始搜索。区分点的比例是 $\theta$，因此平均迭代长度是 $1/\theta$。
使用 $m$ 个处理器的攻击运行时间大约是
$$
\frac{2^{81}}{m}+\frac{2.5}{\theta}
$$
次 $f$ 调用（这被认为是椭圆曲线乘法+哈希的成本上限）。
预计将产生的区分点数量是 $\theta 2^{81}$。我们可以假设每个点存储大约 60 位关于 $x_0$ 的信息和 $160 + \log_2 \theta$ 位关于其自身的信息。
具体数字
单次迭代成本
最昂贵的部分是 $f_1$ 的计算。我们需要执行 160 位的固定基点标量乘法和 Keccak-256 哈希。后者被估计需要 40 kGates。然后我们假设芯片足够大，可以存储 $2^6$ 个形式为 $[t]P$ 的 510 位点，其中 $t<2^6$，
这样我们只需要 160 次加倍和 30 次加法，即大约是常规指数运算的一半。后者被报告在 120Mhz 频率的 ASIC 上需要 3 毫秒、300K 周期和 11K 门。因此，我们假设每秒可以进行 $2^{12}$ 次 $f_1$ 调用，或者每年 $2^{37}$ 次调用。
示例
设置 $m=2^{44}$ 和 $\theta=2^{-37}$，我们得到运行时间为 $2^{37}$ 次 $f_1$ 调用（即一年），总存储量约为 160 TB。
成本可以估计如下。假设 SHA-2 的延迟比 $f_1$ 处理器小约 $2^{11}$ 倍，我们得出攻击的总成本应相当于 $2^{92}$ 次 SHA-2 哈希。请注意，比特币挖矿网络每秒计算 $2^{67}$ 次双 SHA-2 哈希，因此攻击成本相当于 $2^{25}$ 秒，即一年，的比特币挖矿成本。这在 2021 年 6 月是 100 亿美元。
