本博文假设读者已经熟悉滚动哈希（rolling hash）的基本概念。文中包含若干偏重数学的部分，但即使不抓住每一个细节，也能理解核心思想。

本文的主要焦点是：如何选择滚动哈希参数以降低被攻击的风险，以及如何利用不当参数去攻击实现。

设计难以被破解的滚动哈希

回顾滚动哈希与碰撞

滚动哈希有两个参数 \((p,a)\)，其中 \(p\) 是模数，\(0\le a < p\) 是基数。（我们将看到 \(p\) 应该是一个较大的素数，而 \(a\) 应大于字母表大小。）字符串 \(S = s_0 \cdots s_{n-1}\) 的哈希值定义为：

\[ h(S) = \Big(\sum_{i=0}^{n-1} a^{n-i-1} s_i\Big) \bmod p \]

先考虑一个子问题：给定两个等长字符串 \(S,T\)，通过比较各自哈希 \(h(S), h(T)\) 判断是否相等。算法在 \(h(S) = h(T)\) 时认定 \(S\) 与 \(T\) 相等。多数滚动哈希的解决方案要么多次调用这个子问题，要么依赖于其正确性。

我们称满足 \(S \ne T\) 且 \(h(S) = h(T)\) 的两条等长字符串为等长碰撞。等长碰撞会导致算法错误地把不同的字符串判断为相同（注意：此处的误判不会把本应不同长度的字符串混淆为相同）。在固定参数且长度不算大时，可取的字符串远多于哈希值空间，因此必然存在等长碰撞。于是你可能会认为：对任何滚动哈希，都存在让其失败的输入。

幸运的是，随机化可以帮忙。算法不必固定 \((p,a)\)，而是可以按某种方案随机选择。若能证明：对于任意固定的输入 \((S,T)\)，只要 \(S\ne T\)，该方案以高概率选出使得 \(h(S) \ne h(T)\) 的 \((p,a)\)，就称该方案可靠。概率空间仅包含方案内部的随机选择；输入 \((S,T)\) 是固定的、可以视为对抗性选择。（从“被黑”的角度看，就是无论对方怎么挑输入，我们的方案都将以高概率不失败。）

下面给出两种可靠方案。（方案可靠不代表你的实现就一定好；随机数生成器的使用需要谨慎。）

随机化基数

本部分基于 rng_58 的博文，原文讨论了更一般的哈希问题，值得一读。

该方案固定一个素数模 \(p\)（如 \(10^9+7\) 或 \(4\cdot 10^9+7\)），并从区间 \([0,p-1]\) 上对 \(a\) 做均匀随机。令随机变量 \(A\) 表示所选的 \(a\)。

对任意两条等长字符串 \((S,T)\)，有如下计算：

\[ \begin{aligned} h(S) &= h(T)\\ \Big(\sum_{i=0}^{n-1} A^{n-i-1} S_i\Big) \bmod p &= \Big(\sum_{i=0}^{n-1} A^{n-i-1} T_i\Big) \bmod p \end{aligned} \]

于是：

\[ \sum_{i=0}^{n-1} A^{n-i-1} S_i \equiv \sum_{i=0}^{n-1} A^{n-i-1} T_i \pmod p \]

令 \(P(A)\) 为关于 \(A\) 的次数不超过 \(n-1\) 的多项式：

\[ P(A) = \sum_{i=0}^{n-1} A^{n-i-1}(S_i - T_i) \equiv 0 \pmod p \]

当 \(S \ne T\) 时，\(P\) 是非零多项式。由上式可见：当且仅当 \(A\) 是 \(P(A)\) 的根时，\(h(S) = h(T)\)。

因为 \(p\) 是素数，模 \(p\) 的运算在域上进行。域上次数不超过 \(n-1\) 的多项式至多有 \(n-1\) 个根。因此，导致 \(h(S) = h(T)\) 的 \(a\) 的选择至多有 \(n-1\) 个。于是：

\[ \Pr[h(S)=h(T)] = \Pr[P(A)=0] \le \frac{n-1}{p} \]

也就是说，任意两条等长字符串发生等长碰撞的概率最多为 \(\frac{n-1}{p}\)。当 \(n=10^5, p=10^9+7\) 时，大约是 \(10^{-4}\)。若取更大的素数（如 \(2^{31}-1\) 或 \(4\cdot 10^9+7\)）可稍有改善，但需注意溢出问题。

界的紧致性

目前该部分仅适用于 \(p-1\) 为“平滑数”的素数，因此并不适用于 \(p=10^9+7\) 等情形。若能给出可计算且适用一般情形的构造会更好。

当 \(n-1\mid p-1\) 时，上述界 \(\frac{n-1}{p}\) 是紧的。取 \(S=ba\dots a\)、\(T=aa\dots b\)，则有 \(P(A)=A^{n-1}-1\)。

由于 \(p\) 为素数，群 \(\mathbb{Z}/p\mathbb{Z}\) 是阶为 \(p-1\) 的循环群，因此存在一个阶为 \(n-1\) 的子群 \(G\subseteq \mathbb{Z}/p\mathbb{Z}\)。对任意 \(g\in G\)，均有 \(g^{n-1}=1\)，故 \(P(A)\) 有 \(n-1\) 个不同的根。

随机化模数

该方案固定一个基数 \(a\le |\Sigma|\) 以及一个界 \(N>a\)，然后从区间 \([N,2N-1]\) 上均匀随机选择一个素数模 \(p\)。

同样对任意两条等长字符串 \((S,T)\)，有：

\[ \begin{aligned} h(S) &= h(T)\\ \Big(\sum_{i=0}^{n-1} a^{n-i-1} S_i\Big) \bmod p &= \Big(\sum_{i=0}^{n-1} a^{n-i-1} T_i\Big) \bmod p \end{aligned} \]

因此：

\[ \sum_{i=0}^{n-1} a^{n-i-1} S_i \equiv \sum_{i=0}^{n-1} a^{n-i-1} T_i \pmod p \]

令：

\[ X = \sum_{i=0}^{n-1} a^{n-i-1}(S_i - T_i) \equiv 0 \pmod p \]

当 \(X \equiv 0 \pmod p\) 即 \(p\mid X\)。我们选择足够大的 \(a\)，保证 \(X\ne 0\)；且有 \(|X| < a^n\)。在区间 \([N,2N-1]\) 中，\(X\) 的不同素因子个数的上界约为 \(\log_N(|X|) = \frac{n\ln a}{\ln N}\)。由素数分布定理，区间 \([N,2N-1]\) 中约有 \(\frac{N}{\ln N}\) 个素数。因此：

\[ \Pr[h(S)=h(T)] = \Pr[p\mid X] \lesssim \frac{n\ln a}{N} \]

该界略逊于“随机化基数”的界。以 \(n=10^5, a=26, N=10^9\) 为例，约为 \(3\cdot 10^{-4}\)。

如何正确随机化

以下是初始化随机数生成器的较好方式：

  • 高精度时间

    1
    2
    chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();
    chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count();

    二者皆可。（理论上 high_resolution_clock 更好，但在 Codeforces 上其精度竟低于 steady_clock？？）

  • 处理器周期计数器

    1
    __builtin_ia32_rdtsc();

  • 将某个堆地址转为整数

    1
    (uintptr_t) make_unique<char>().get();

  • 处理器随机数（需 pragma 或 asm）（感谢 halyavin 的建议）

    1
    2
    3
    4
    5
    6
    7
    // pragma 版本
    #pragma GCC target ("rdrnd")
    uint32_t rdrand32(){
        uint32_t ret;
        assert(__builtin_ia32_rdrand32_step(&ret));
        return ret;
    }
    1
    2
    3
    4
    5
    6
    // asm 版本
    uint32_t rd(){
      uint32_t ret;
      asm volatile("rdrand %0" :"=a"(ret) ::"cc");
      return ret;
    }

若使用 C++11 风格 RNG（推荐），可将上述来源组合：

1
2
3
4
5
6
7
seed_seq seq{
    (uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
    (uint64_t) __builtin_ia32_rdtsc(),
    (uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
int base = uniform_int_distribution<int>(0, p-1)(rng);

注意：内部会丢弃参数的高 32 位，但影响不大；低位反而更难预测（尤其首项的 chrono）。

参见“滥用不良随机化”部分中的反例。

扩展到多重哈希

可以使用多个哈希（即便采用同一方案与相同固定参数），只要随机样本独立，各哈希相互独立。若单个哈希失败概率不超过 \(a_1,\dots,a_k\)，则全部失败的概率不超过 \(\prod_{i=1}^k a_i\)。

例如使用两重哈希，取 \(p=10^9+7\) 并随机化基数，碰撞概率最多为 \(10^{-8}\)；四重哈希则最多为 \(10^{-16}\)。在此更大的素数常数项更显著；以 \(p=2^{31}-1\) 为例，概率约为 \(2.1\cdot 10^{-9}\) 与 \(4.7\cdot 10^{-18}\)。

更大的模数

采用更大的（如 60 位）素数能降低碰撞概率，并避免误差界中关于 \(n\) 的累积因子。但滚动哈希的计算会更慢、更复杂，因为 Codeforces 上无 __int128。

一个例外是梅森素数 \(p=2^{61}-1\)；此时可用位操作来做模约简。（感谢 dmkz 的建议。）下述代码在无 __int128 的情况下计算 $a\cdot b \bmod p`，仅比 30 位取模哈希慢约 5%。参数需满足 \(0\le a,b<mod\)，返回值也满足该条件。

1
2
3
4
5
6
7
8
9
constexpr uint64_t mod = (1ull<<61) - 1;
uint64_t modmul(uint64_t a, uint64_t b){
    uint64_t l1 = (uint32_t)a, h1 = a>>32, l2 = (uint32_t)b, h2 = b>>32;
    uint64_t l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
    uint64_t ret = (l&mod) + (l>>61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
    ret = (ret & mod) + (ret>>61);
    ret = (ret & mod) + (ret>>61);
    return ret-1;
}

使用无符号类型并取 \(p=4\cdot 10^9+7\) 可略有增益。

注意：\(p=2^{64}\)（unsigned long long 溢出）并非素数，即便做随机化也可被攻击（见下文）。

扩展到多次比较

滚动哈希通常用于不止一次的比较。若我们依赖 \(m\) 次比较且单次失败概率为 \(p\)，则任一失败的概率至多为 \(m\cdot p\)（并用联合界）。当 \(m=10^5\) 时，通常需要两到三个哈希使该概率足够小。

估计所需比较次数时要格外谨慎。若我们对哈希排序或放入集合，需要两两不相同；于是对 \(n\) 条字符串共有 \(\binom{n}{2}\) 次比较需成功。以 \(n=3\cdot 10^5\) 为例，\(m\approx 4.5\cdot 10^9\)，因此需要三到四重哈希（若采用 \(p=2^{61}-1\)，两重即可）。

扩展到不同长度的字符串

若处理不同长度的字符串，可以在哈希中同时存储长度以避免比较。不过在假设无字符哈希为 0 的前提下，这并非必要。此时可以把较短字符串视作在前缀补齐若干空字节，使其与较长者等长，同时不改变哈希值；于是上述理论仍适用。（若存在某字符（如 a）哈希为 0，则补齐过程可能将原本不同的字符串映射为看上去相同的形式，例如 a 与 aa。）

计算反哈希测试

本节介绍若干利用滚动哈希实现中常见错误的技巧，主要用于攻击其他方案。下表给出方法的简要概览。

名称用例运行时间字符串长度备注
Thue–Morse带溢出的哈希\(O(1)\)\(2^{10}\)可同时适用于所有基数（任意 \(a\)）。
生日攻击小模数\(O(\sqrt{p}\log p)\)\(\approx 2\log_{|\Sigma|}p\)可同时找出多个碰撞。
树攻击大模数\(O(2^{\sqrt{p\lg p}})\)\(O(2^{\sqrt{p\lg p}}+1)\)更快；字符串更长
多树攻击大模数\(O((2^{\sqrt{2\lg m\,p}}+\log_{|\Sigma|}m)\,m\log m)\)\(\approx O(2^{\sqrt{2\lg m\,p}}+\log_{|\Sigma|}m)\)更慢；字符串更短
格子约减中大型字母表，多哈希\(O(\text{length}^3)\)\(\approx \sum_{i=0}^{n-1}\log_{|\Sigma|}(p_i)\)\(| \Sigma | =26\) 时效果佳；对二进制较差；对多重哈希有效。
组合多重哈希单个方法运行时间之和单个字符串长度的乘积组合两种攻击。

单重哈希

Thue–Morse 序列：无符号溢出哈希（\(p=2^{64}\)，\(a\) 任意）

一种对任意基数均有效的反哈希测试是 Thue–Morse 序列，生成代码如下：

1
2
3
4
5
6
7
8
const int Q = 10;
const int N = 1 << Q;
std::string S(N, ' '), T(N, ' ');

for (int i = 0; i < N; i++)
    S[i] = 'A' + __builtin_popcount(i) % 2;
for (int i = 0; i < N; i++)
    T[i] = 'B' - __builtin_popcount(i) % 2;

\(S\) 与 \(T\) 构成等长碰撞，无论选择何种基数。

详见这篇博文。其中的界还可略微改进，因为对奇数 \(X\)，\(X^2-1\) 总能被 8 整除（因此可取 \(Q=10\) 而非 \(Q=11\)）。

生日攻击：32 位素数、固定基数（\(p<2^{32}\) 固定，\(a\) 固定）

对仅用一个小素数的哈希可用生日悖论攻击。固定长度 \(l\) 与字母表大小 \(d\)，在长度为 \(l\) 的字符串集合中均匀随机选取 \(k\) 条字符串。若 \(l\) 不过小，其哈希值近似均匀分布。由生日悖论，所选 \(k\) 条字符串的哈希值两两不同的概率为：

\[ \prod_{i=0}^{k-1}\Big(1-\frac{i}{d}\Big) < \prod_{i=0}^{k-1} e^{-\frac{i}{d}} = e^{-\frac{k(k-1)}{2d}} < e^{-\ln 2} = \frac{1}{2} \]

因此，以大于 \(\tfrac12\) 的概率，能找到两条字符串的哈希相同。重复上述过程，在 \(O(\sqrt{p})\) 时间内即可高概率找到等长碰撞。实际中得到的字符串可相当短（例如当 \(p=10^9+7\)、\(d=62\) 时长度约为 6；尚不明确如何严格上界）。

更一般地，利用类似技巧可在 \(O(m\,p^{1-1/m})\) 时间内找到 \(m\) 条哈希相同的字符串，取样次数 \(r=m\,p^{1-1/m}\)。

树攻击：较大素数、固定基数（\(p\) 固定，\(a\) 固定）

感谢 Kaban-5 与 pavel.savchenkov 提供的链接（俄语评论，描述了此思路）。

当素数较大时，生日攻击过慢。回忆两条等长字符串 \((S,T)\)：

\[ h(S) = h(T) \]

\[ \sum_{i=0}^{n-1} a^{n-i-1}(S_i - T_i) \equiv 0 \pmod p \]

令 \(\alpha_i = S_i - T_i\)，则 \(-|\Sigma| \le \alpha_i \le |\Sigma|\)。树攻击尝试寻找 \(\alpha_i\in\{-1,0,1\}\) 使得：

\[ \sum_{i=0}^{n-1} (a^{n-i-1} \bmod p)\cdot \alpha_i = 0 \]

算法维护若干系数簇 \(C_1,\dots,C_k\)。某簇 \(C\) 的和定义为：

\[ S(C) = \sum_{i\in C} (a^{n-i-1} \bmod p)\cdot \alpha_i \]

可将两簇 \(C_1,C_2\) 合并为新簇 \(C_3\)，其和为 \(S(C_1)-S(C_2)\)：做法是将 \(C_2\) 中所有 \(\alpha_i\) 乘以 \(-1\) 并合并两簇的系数集合。实现上可用二叉树存簇，每个结点存其总和；合并即创建新结点，其子为 \(C_1,C_2\)，和为 \(S(C_1)-S(C_2)\)。为保证 \(S(C_3)\ge 0\)，必要时交换 \(C_1,C_2\)。\(\alpha_i\) 的取值不显式存储，最终可通过树回溯得到。

初始化时取 \(n=2k\)，每个 \(\alpha_i=1\) 独自形成一簇。每一轮先按簇和排序，再两两相邻合并。若在某处出现和为 0 的簇，则令不在该簇中的所有 \(\alpha_j=0\) 并结束。若 \(k\) 轮后仍未结束，则取更大的 \(k\) 重试。

取何值的 \(k\) 可期望成功？若假设初始的簇和在 \([0,p-1]\) 上均匀分布，则第 \(i\) 轮后最大簇和应约按因子 \(\sim 2^{k-i}\) 下降。\(k\) 轮后最大和约为 \(\frac{p}{2^{\binom{k}{2}}}\)，故取 \(k\approx \sqrt{2\lg p}+1\) 可行。对应字符串长度为 \(n=2^{\sqrt{2\lg p}+1}\)，时间 \(O(n)\)。（更形式化的分析可见论文《Solving Medium-Density Subset Sum Problems in Expected Polynomial Time》2.2 节。问题与算法略有差异，但思路相近。）

多树攻击

树攻击很快，但得到的字符串可能较长（如 \(p=2^{61}-1\) 时 \(n=2048\)）。若希望更短的碰撞，可增加运行时间：在每个簇中维护能得到的最小 \(m\) 个和（单树攻击相当于 \(m=1\)）。合并两簇可用最小堆与 \(2m\) 指针遍历在 \(O(m\log m)\) 内完成。为尽快得到 \(m\) 条字符串，允许 \(\alpha_i\in[-|\Sigma|,|\Sigma|]\)，并排除所有 \(\alpha_i\) 为 0 的平凡情形。

分析其期望 \(k\) 较难。乐观地假设：在 \(\log_{|\Sigma|} m\) 步后每结点都能得到 \(m\) 个和；和的下降与单树攻击一致；当和小于 \(m^2\) 时由生日悖论可期望出现碰撞；则有

\[ k = \sqrt{\frac{2\lg p}{\lg m}} + \log_{|\Sigma|} m. \]

（更现实的界为 \(k = \frac{\lg p}{\lg m} + \log_{|\Sigma|} m\)，可参考论文《On Random High Density Subset Sums》定理 3.1 中的推导。）

实践中，取 \(m\approx 10^5\)、\(|\Sigma|=2\)、\(p=2^{61}-1\)，能在约 0.4 秒内找到长度 128 的碰撞。

格子约减攻击：不太小的字母表下的单/多重哈希

感谢 hellman_ 的提示，可参考他的写作；另有他人写作见此处。

与树攻击类似，我们寻找满足：

\[ \sum_{i=0}^{n-1} (a^{n-i-1} \bmod p)\cdot \alpha_i = 0 \]

且 \(\alpha_i\in[-|\Sigma|,|\Sigma|]\) 的向量。考虑集合：

\[ \{\alpha_0,\dots,\alpha_{n-1},\beta\}\quad\text{其中}\quad \beta \equiv \sum_{i=0}^{n-1} (a^{n-i-1} \bmod p)\cdot \alpha_i \]

这形成一个格（嵌入到 \(\mathbb{R}^n\) 子空间的自由 \(\mathbb{Z}\) 模）。我们要在格中找一个元素，使得 \(\beta=0\) 且 \(|\alpha_i|\le |\Sigma|\)。可通过惩罚非零 \(\beta\) 来实现：

\[ \beta = 10^5\cdot \Big(\sum_{i=0}^{n-1} (a^{n-i-1} \bmod p)\cdot \alpha_i\Big) \bmod p \]

随后目标转为最小化 \(\max\{| \alpha_0|,\dots,|\alpha_{n-1}|,|\beta|\}\)。这一优化问题很难，于是改为最小化二范数：

\[ \alpha_0^2 + \cdots + \alpha_{n-1}^2 + \beta^2. \]

该问题仍然困难，可能为 NP 完全，但存在较好的近似算法。

与向量空间类似，格中也可定义基。对本问题，一组基为：

\[ \{\,e_\beta + 10^5(a^{n-i-1} \bmod p)\,e_{\alpha_i} \mid 0\le i<n\,\} \cup \{\,p\cdot 10^5\,e_\beta\,\}. \]

格约减算法以该基为输入，利用行列式为 \(\pm 1\) 的可逆整矩阵，将其转化为“近似最短向量”的另一组基。自行实现较难（会受精度或大整数性能影响），因此使用 Sage 的内置实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
"""Anti-rolling-hash test generation by lattice reduction
original code by Hellman_, modified by dacin21
"""

from sage.all import *

def anti_hash(PAs, string_length, sigma, block_size = 0, MULTIPLIER = 100000, sigma_base = ord('a')):
    n = len(PAs)
    N = string_length
    As = [a for p, a in PAs]
    Ps = [p for p, a in PAs]

    def h(s):
        """polynomial hash modulo <n> primes"""
        v = [0] * n
        for c in s:
            v = [(x * q + ord(c))%p for x, q, p in zip(v, As, Ps)]
        return tuple(v % p for v, p in zip(v, Ps))

    mv = matrix(ZZ, N, N)
    for y in xrange(N):
        for x, q, p in zip(range(n), As, Ps):
            mv[y,x] = pow(q, N-y-1, p);

    m = matrix(ZZ, N + n, N + n)
    # submatrix with terms
    m.set_block(0, 0, MULTIPLIER * mv)
    # modulo reductions
    m.set_block(N, 0, MULTIPLIER * diagonal_matrix(Ps))
    # term coefficients
    m.set_block(0, n, identity_matrix(N))
    # 4th submatrix is zero

    m_reduced = m.LLL()
    if block_size > 0:
        m_reduced = m_reduced.BKZ(block_size = block_size)

    for row in m_reduced:
        print row[:n], min(row[n:]), "~", max(row[n:])
        delta = max(abs(v) for v in row[n:])
        if set(row[:n]) == {0} and delta < sigma:
            print "Found collision!"
            s = [None] * N
            t = [None] * N
            for i, v in enumerate(row[n:]):
                a = sigma_base
                b = a + abs(v)
                if v > 0:
                    a, b = b, a
                s[i] = a
                t[i] = b
            s = "".join(map(chr, s))
            t = "".join(map(chr, t))
            print s + " " + t
            # print h(s)
            # print h(t)
            assert h(s) == h(t)
            break
    else:
        print "Failed to find collision, try a larger string_length"
        print "For lengths > 30, setting block_size to 10 or 15 is recommended"

if __name__ == '__main__':
    with open("hash.in", 'r') as infile:
        n, k, sigma = map(int, infile.readline().strip().split())
        PAs = [tuple(map(int, infile.readline().strip().split())) for _ in xrange(n)]
        anti_hash(PAs, k, sigma)

程序从名为 hash.in 的文件读取输入；如需使用 BKZ 算法，设置 block_size 参数。

输入格式：

1
2
3
4
n length sigma
p_1 a_1
...
p_n a_n

Sage 提供两种算法：LLL 与 BKZ。LLL 更快但近似更差，尤其在较长字符串时。分析不易，故做了一些实验：固定 \(|\Sigma|=26\)、\(p=2^{61}-1\)，随机取 \(a_1,\dots,a_n\)，分别用两种算法搜索短的反哈希测试，效果非常好。

LLL 算法：

\(n\)最小长度用时（秒）
1120.02
2230.04
3340.08
4480.18
5600.34
6770.75
73015.14
8>1500>990

当 \(n=8\) 时未能找到长度 \(\le 1500\) 的碰撞。

BKZ 算法（block_size=10）：

\(n\)最小长度用时（秒）
1120.02
2230.04
3330.09
4450.21
5570.58
6721.12
7882.59
81085.33

BKZ 算法（block_size=15）：

\(n\)最小长度用时（秒）
1120.02
2230.04
3330.09
4450.21
5570.52
6701.24
7852.41
81025.20

BKZ 算法（block_size=25）：

\(n\)最小长度用时（秒）
1120.02
2230.04
3330.10
4460.58
5571.14
6703.67
7846.96
89626.70

注意：当 \(n>1\) 且字母表很小（如二进制）时，此攻击效果不佳；另外字符需映射到连续值，因此在组合攻击中应优先使用该方法。

组合攻击：多重哈希

本思路归功于 ifsmirnov，其 jngen 库中使用了该技巧。

使用两个或更多哈希通常可抵御直接的生日攻击。对两个素数而言，可能的哈希数为 \(N=p_1p_2\)。生日攻击的复杂度为 \(O(\sqrt{N})\)，当素数约为 \(10^9\) 时，\(\sqrt{N}\approx 10^{10}\)。此外，若仅存储哈希与 RNG 种子，内存至少为 \(\sqrt{(2\ln 2)N}\cdot 8\) 字节，约 9.5 GB。

破解多重哈希的关键在于逐个突破：

  • 先对第一个哈希 \(h_1\) 做生日攻击，找到等长碰撞，即 \(S\ne T\)、\(h_1(S)=h_1(T)\)。注意：在字母表 \(\{S,T\}\) 上构造的等长字符串（例如将若干个 \(S\) 与若干个 \(T\) 拼接）在 \(h_1\) 下仍会哈希到相同值。
  • 然后以 \(\{S,T\}\) 作为字母表，对第二个哈希 \(h_2\) 做生日攻击，寻找新的等长碰撞。因为使用的是 \(\{S,T\}\)，得到的碰撞自动也是 \(h_1\) 的碰撞。

这样总体复杂度降为 \(O(\sqrt{p_1}+\sqrt{p_2})\)。该策略也适用于“30 位素数哈希 + 模 \(2^{64}\) 哈希”的组合：第二步可用 Thue–Morse 序列替代生日攻击。对更大的模数也可将第二步替换为树攻击。

需要注意的是，字符串长度会随哈希的个数迅速增长（大致为 \(2\log_{|\Sigma|}\!\big(\sqrt{(2\ln 2)p_1}\big)\cdot \log_2\!\big(\sqrt{(2\ln 2)p_2}\big)\cdots \log_2\!\big(\sqrt{(2\ln 2)p_k}\big)\)；第一次生日攻击后字母表缩至 2，实操中首轮常有额外的因子 2）。若在中间步骤搜索多于 2 条哈希相同的字符串，字母表更大、字符串更短，但生日攻击的时间也更长（例如对 3 条字符串，复杂度为 \(O(p^{2/3})\)）。

滥用不良随机化

在 Codeforces 上，许多人会对哈希做随机化。（不幸的是）不少人采用了次优的方式。本节覆盖一些常见的随机化误用以及相应的攻击手段。

其适用范围更广：任何参与者可攻击你方案的环境下，随机化算法都可能遭遇类似问题。

固定种子

若 RNG 种子固定，生成的随机数序列也固定。你只需运行其代码查看生成了哪些“随机数”，再针对这些数构造反哈希测试即可。

从小集合中取基数（如 rand()%100）

rand()%100 至多生成 100 种取值（0 到 99）。可以为每个可能的基数分别构造反哈希测试，再按题目场景组合这些测试（组合方式依题而异，但多数问题可行）。

rand() 的更多问题

在 Codeforces 上，rand() 仅生成 15 位的值，最多 \(2^{15}\) 种取值。虽然运行 \(2^{15}\) 次生日攻击需要时间（以我的笔记本单线程估计，针对 \(p=10^9+7\) 约需 111 分钟），但这会给其他随机化算法带来麻烦。

补充：若使用多树攻击，上述黑箱可能可行。以 \(p=10^9+7, |\Sigma|=26\) 为例，运行 \(2^{15}\) 次、取 \(m=10^4\) 的多树攻击约需 2 分钟，输出约 \(5.2\cdot 10^5\) 个字符。对多数题目仍稍大，但在开放黑客阶段可拆分为多次攻击。

在 C++11 中，建议使用 mt19937 与 uniform_int_distribution 替代 rand()。

低精度时间（Time(NULL)）

Time(NULL) 每秒仅变化一次。可按如下步骤利用之：

  1. 选定时间跨度 \(\Delta T\)。
  2. 估计生成你的测试所需时间的上界 \(T\)。
  3. 通过自定义运行获取当前 Time(NULL) 的值 \(T_0\)。
  4. 对 \(t=0,\dots,\Delta T-1\)，用 \(T_0+T+t\) 替代 Time(NULL) 并针对该固定种子生成反测试。
  5. 在时间 \(T_0+T\) 提交攻击。

若你的攻击在接下来的 \(\Delta T\) 秒内执行，则 Time(NULL) 会取到你已覆盖的值，于是目标方案失败。

MinGW 上的 std::random_device

在 Codeforces 的 MinGW 环境中，std::random_device 是确定性的，会生成相同的数列。使用它的方案可像固定种子的方案一样被攻击。

本文选自 Anti-rolling-hash test generation by lattice reduction