可并行的内存高效的哈希碰撞算法

概要: 本文讨论三类通用哈希碰撞搜索方法：基于生日悖论的碰撞算法（Birthday Paradox）、结合 Floyd 循环检测的 Pollard’s rho 算法，以及可并行的 Pollard’s Lambda 算法（Distinguished Points），这些通用算法可以类似地泛化到整数分解和离散对数问题的求解。

哈希碰撞问题（第二原像攻击）是一个基础性的密码学问题，其几乎贯彻了整个密码学体系。本文介绍的通用哈希碰撞算法分为下面三类：

生日悖论碰撞算法

经典生日悖论. 一个经典的问题：在一个有 365 天的年份中，需要多少个人才能使得至少两个人有相同生日的概率超过 50%？在完全随机的情况下，理论值是 23 ，这比直觉上要少得多。

考虑一般化的版本：给定 \(k\) 个人，至少有两个人同一生日的概率是多少？在 \(k > 365\) 时，由容斥原理，这个概率为 1。进一步地，给定一个大小为 \(N\) 的集合（比如哈希函数输出空间），随机选择 \(k \le N\) 个集合内的值（有放回抽取），至少有两个相同值的概率记为 \(\Pr\left(\text{coll}\right)\)。令 \(\Pr\left(z=0\right)\) 代表所有选择的值均互异，则 \(\Pr\left(\text{coll}\right) = 1 - \Pr\left(z=0\right)\)，其中：

因此有两个相同值的概率（即碰撞）是：

对于生日悖论问题，只要 \(k \ge 23\)，这个概率就超过了 50%。这比大多数人预期的要少得多。一般地，当 \(k\) 相对于 \(N\) 较小时，使用近似公式有：

对于输出比特长度为 \(n\) 的哈希函数，得到

这意味着，利用生日悖论，我们需要计算 \(\mathcal{O}(2^{n/2})\) 个随机的哈希值，就有很大概率得到碰撞。

Pollard’s rho 算法

Pollard’s rho method 最初是整数分解中的一类算法，其核心原理也是 Birthday Paradox。因其生成序列的性质酷似希腊字母 \(\rho\)，故而得名 rho。

整数分解的 Pollard’s rho 算法

整数分解问题. 给定一个合数 \(n = p \cdot q\)，如何找到它的一个非平凡因子 \(p\)？

对于整数分解的 Pollard’s rho 算法，核心在于定义一个函数 \(g(x)\) 用于生成伪随机数序列，例如我们取一个多项式 \(g(x) = x^2 + 1 \bmod n\)。这会生成下面的有限序列

其中 \(g^k\) 代表映射复合，记 \(x_k = g^k(x_0) \in \mathbb{Z}_n\)。但是，如果我们从模 \(p\) 的视角来看，同样上述序列其实隐藏了一个子群序列：

其是 \(\left\{x_k \bmod p\right\}\) 的子序列。如果我们选取的 \(g(x)\) 足够随机，根据生日悖论，我们大概会在 \(\mathcal{O}(\sqrt p)\) 后找到碰撞。如下图 \(l_0\) 所示：

如果图 1 中序列值代表的是模 \(p\) 的序列，这样的碰撞代表着我们寻找到了 \(g(x_{l_0- 1}) = g(x_{l_0 + n}) \bmod p\)。由于我们只有模 \(n\) 的序列，因此有极大概率在模 \(n\) 的序列下 \(g(x_{l_0- 1}) \ne g(x_{l_0 + n}) \bmod n\)，于是

即可分解 \(n\)。但是，值得注意的是，在计算序列时无法直接判断哪个值发生了碰撞；如果需要和之前的序列进行逐次 \(\gcd\)，其时间和空间开销都非常巨大。因此我们需要一个高效的循环检测算法来辅助 Pollard’s rho 算法。

一个简单的 Pollard’s rho 算法如下：

# sage
def rho(n):
    # Pollard's rho method
    c = int(10)
    a0 = int(1)
    a1 = a0^2+c
    a2 = a1^2+c
    while gcd(n,a2-a1) == 1:
        a1 = (a1^2+c) % n
        a2 = (a2^2+c) % n
        a2 = (a2^2+c) % n
    g = gcd(n,a2-a1)
    return [g,n//g]

哈希碰撞的 Pollard’s rho 算法

迁移到哈希碰撞的场景，此时伪随机序列的生成函数为哈希函数 \(\mathcal{H}: \{0,1\}^{*} \mapsto \{0,1\}^n\)，或者某个复合哈希映射 \(\mathcal{H}^{+} = \mathcal{H} \circ \mathcal{R}\)。简便起见，初始值为 \(x_0\)，我们使用 \(\mathcal{H}\) 表示伪随机序列的生成函数：\(x_{i+1} = H(x_i)\)。图 1 中环有 \(n+1\) 个点，记 \(N = n + 1\)。

同样地，伪随机序列 \(\{x_k\}\) 会在 \(k = \mathcal{O}(2^{n/2})\) 处发生碰撞，之后进入循环。采用 Floyd 算法进行循环检测（cycle detection），假设在点 \(i\) 为 Floyd 快速序列和慢速序列的相遇点，在这一点相遇时，慢速序列一定处于第一次 cycle 结束之前，因此序列计算次数为 \(i \le l_0 + n\)，有如下关系：

容易得出 \(k = \lceil \frac{l_0}{n} \rceil\)。此时，\(i\) 点相遇，但是不一定发生碰撞，因此我们想要继续行进到点 \(l_0\)。一个有趣的观察是 \(0 \rightarrow l_0\) 和 \(i \rightarrow l_0\) 的距离一定是相等的（模 \(N = n + 1\) 意义下）。证明如下：

故而

以 \(i\) 点为起始点，后续点集序列将会是一个长度为 \(N\) 的循环，因此 \(0 \rightarrow l_0\) 和 \(i \rightarrow l_0\) 将会以相同的步数 \(l_0\) 达到 \(l_0\) 点（均慢速），从而检测得到 \(x_{l_0 - 1}\) 和 \(x_{l_0 + n}\) 两个点发生哈希碰撞，碰撞的哈希值为 \(x_{l_0}\)。

Floyd 算法是一种有效的循环检测算法（Cycle Detection），并且从相遇点（Meeting Point）能够快速定位到碰撞点（Collision Point），在许多密码学算法中都有非常广泛的应用。

Pollard’s lambda 算法

Pollard’s rho 哈希碰撞算法虽然时间复杂度满足生日悖论的界，并且只需要常量内存，但是它不能通过并行计算进行线性的加速；朴素的生日悖论碰撞并行的空间开销巨大，并且也很难满足线性的加速。那么是否存在一种算法，使得其在并行环境中能够线性加速，并且空间复杂度也不高呢？Quisquater 和 Delescaille 在寻找 DES 的碰撞时，就使用了 Distinguished Point 来辅助碰撞。

Distinguished Point 碰撞算法

于是 DP 哈希碰撞算法主要包含下面的步骤，预定义显著点参数为 \(k\)：

1. 随机选取一个初始点 \(S_i\)（start point），计算哈希序列，直至得到一个显著点 \(D_i\)，保存一条 DP 链 \((S_i, D_i, L_i)\)，其中 \(L_i\) 为长度信息。
2. 不断选取不同的初始点，寻找上述 DP 链，直到显著点发生碰撞 \(D_i = D_j\)，此时停止寻找 DP 链。
3. 选取发生碰撞的两条链 \((S_i, D_i, L_i), (S_j, D_j, L_j)\)，先对较长的链进行计算，直至剩余长度与另一条保持一致，之后两条链一起计算，检测是否出现哈希碰撞。如果没有碰撞，丢弃较短的链，继续回到第一步寻找其他的 DP 链。

图 2 是 DP 碰撞搜索中生成的碰撞示意图。图中 \(\mathcal{H}(x_1) = \mathcal{H}(x_2) = x_c\)，它们的显著点 DP 相同，但是位于不同的起点上，从而导致碰撞出现。检测到图 2 中 DP 相同的链出现时，由于 SP1 链比 SP2 链长 1，于是 SP1 首先进行 1 次哈希，此后 SP1 和 SP2 同时进行哈希，之后在 \(x_1, x_2\) 处检测到碰撞。

如果 SP1 链移动后发现与 SP2 链重合，则这是一次伪哈希碰撞，丢弃较短的链。这种情况被称为 Robinhood Case，如图 3 所示：

时间空间复杂度权衡

Distinguished Point 碰撞算法的时间空间复杂度，很大程度上与 Distinguished Point 的难度系数有关（Difficulty）。这里的难度系数定义和比特币挖矿算法的难度系数定义是一致的。记难度系数为 \(k\)：哈希值为前置 \(k\) 个 0。

这是理想分析下的结果，尚不考虑特殊情况如 Robinhood Case 的出现。实际上，如果 \(k\) 值取得太小，空间复杂度高；如果 \(k\) 选取得太大，会频繁出现 Robinhood Case 的伪碰撞，导致时间复杂度增加。因此难度系数 \(k\) 的选取对 Distinguished Point 算法非常关键。

值得指出的是，通过精心选取 \(k\)，Distinguished Point 算法既能保证时间复杂度基本在 \(2^{n/2}\) 附近，不是内存困难的，并且在多核并行下保持线性的加速。比如 \(n = 64\)，选择 \(k = 24\)，时间复杂度 \(\mathcal{O}(2^{32})\)，内存复杂度 \(\mathcal{O}(2^{8})\)，在此情况下可以进行线性加速的并行。下面是笔者对 sha256 的低 64 位进行碰撞的实验数据：

• 4 核（PRNG 的 SEED 为 0x123456789abcdef0）

  Two DP chains collided with dp mask=ffffff
  Number of chains find: 393
  diff = 11897207
  Looking for collision...
  Collision found! with 4 cores
  333412288b678e3b ff7cb8a664c810e3
  962860fc377014f1 962860fc377014f1
    
  real    1m17.441s
  user    5m9.708s
  sys     0m0.020s
  

• 8 核（PRNG 的 SEED 为 0x123456789abcdef0）

  Two DP chains collided with dp mask=ffffff
  Number of chains find: 409
  diff = 11897207
  Looking for collision...
  Collision found! with 8 cores
  333412288b678e3b ff7cb8a664c810e3
  962860fc377014f1 962860fc377014f1
    
  real    0m45.683s
  user    6m5.344s
  sys     0m0.011s
  

上述实验使用了来自 Hitcon 2023 Collision 赛题的一个高效 C++ 实现的 DP 碰撞算法。

上述结果基本符合线性的加速。理论上期望的 DP 链数目为 \(2^8 = 256\)，实际 400 左右略高，是因为生日悖论给出的估计 \(\mathcal{O}(1.117 \cdot 2^{n/2})\) 是碰撞概率刚好大于 50% 时的哈希次数。