做密码安全这块迟早会遇到一个问题我手里已经有了一张彩虹表磁盘占用看起来也很可观可真拿去查一批哈希的时候实际成功率却总比想象中低一大截。后来我发现问题不是表不够大而是大多数人包括当时的我根本没把彩虹表的“成功率计算”这件事弄明白。这篇内容我就把这件事彻底讲透成功率是怎么来的、公式怎么推、参数怎么搭以及一张看似“完美”的表为什么会翻车。1. 先把存储机制说清楚成功率为什么不等于“表大小/明文空间”很多人对彩虹表有个直觉表越大、存的条目越多能覆盖的明文就越多那成功率自然就等于“覆盖的明文数 / 明文空间大小”。这个直觉害死人。彩虹表几乎从来不会把中间状态全部存下来它存的是“链首链尾”中间所有位置都是通过计算现算的。所以一张表的“有效覆盖”和磁盘条数之间隔着一整条概率链路。1.1 链条的构造哈希函数和归约函数交替折叠彩虹表的核心单位不是一条记录而是一条“链”。构造方式是这样的随便取一个明文作为起点做一次哈希再用一个归约函数把哈希值映射回明文空间再哈希、再归约如此循环固定次数。定义清楚一点哈希函数写成 H归约函数写成 R。链条就是p0 → H → c1 → R1 → p1 → H → c2 → R2 → p2 → … → p_{t-1} → H → c_t其中 p 表示明文c 表示哈希值t 是链长。构造完这条链之后我们只保存 (p0, c_t)也就是起点明文和终点哈希。中间那几百上千个状态查询的时候现算。这里有一个看起来不起眼、但影响成功率的关键设计每一列使用的归约函数 R 是不同的所以严谨写法是 R1、R2、R3……而不是所有列共用一个 R。原因后面会细讲这直接关系到链条合并的概率而链条合并是成功率缩水的第一大元凶。1.2 查询过程不是扫描全表而是从目标哈希反向折叠如果我们要查的目标哈希值是 c查询过程是从 c 出发尝试“折 0 次、折 1 次、折 2 次……直到折 t-1 次”。每次折叠都是先做归约、再做哈希这样得到的每种结果如果正好等于某条链的链尾就说明这条链的某一段覆盖了目标哈希。这时候再拿到链首从头把链条重新走一遍走到某个位置时如果算出的哈希等于目标值那个位置前面的明文就是结果。所以一张彩虹表能覆盖的密度取决于“所有链条的所有折叠点”在明文空间里的分布密度。注意是“覆盖密度”不是“条目数量”。链条越长每个起点产生的可能命中位置越多链条越多起点数量越多。而这两者之间存在一个肉眼看不出的此消彼长关系。1.3 覆盖率不可能到 100% 的物理限制很多新手默认“我把表做到明文空间的好几倍大小成功率应该接近 100%”。实际上彩虹表的覆盖率永远达不到 100%原因有三层。第一链条会合并。两条链从不同起点出发如果某个折叠点撞到了同一个哈希值那接下来的路径就完全一样了后边等于白走。链条越长合并概率越高。第二链尾碰撞。就算中间没合并两张表的链尾也可能相同而存储时为了去重通常会只保留一条这会悄悄损失掉一部分有效链。第三端点分布不均匀。归约函数再均匀在有限空间里也必然存在热点和冷区冷区里的明文就是那些“理论上在覆盖范围内、实际上永远等不到”的倒霉蛋。所以成功率的本质是在“链条长度、链条数量、合并概率、端点碰撞、分布均匀性”这几股力共同作用下的一个统计结果。下面这个数学模型就是把这些因素尽量量化。2. 成功率公式的来龙去脉从漏报概率到可抄走的代码关于彩虹表成功率的理论最早来自经典论文里的概率模型。我不重复论文推导过程直接讲它的核心思路和最终结果因为实际动手时你需要的是“能用”的公式。2.1 从“漏报概率”说起每一列都有盲区先给一个非常重要的定义漏报概率意思是某个明文的哈希值在某一列折叠过程中没有被覆盖到的概率。我们假设明文空间大小是 N一张表有 m 条链链长固定为 t。任何一张表在构造过程中第 i 列上会实际出现一些不同的明文点用 m_i 表示第 i 列上不同点的期望数量。m_i 不是一个固定值。第一列近似等于 m因为 m 个随机起点之间的碰撞还比较少。但从第二列开始每列的新增点会和已有覆盖点重合造成浪费。学术上常用一个递推式来近似m_{1} mm_{i1} N × (1 - e^{-m_i / N})这个式子看着抽象其实逻辑很朴素第 i1 列能贡献的新点数量取决于“第 i 列已经覆盖到哪里”。如果第 i 列覆盖了 30% 的空间那第 i1 列折叠出来的点大约有 30% 的概率落在已覆盖区域实际新增只有 70%。指数形式来自泊松近似因为路径上的落点在理想模型下服从随机均匀分布。有了 m_i第 i 列的漏报概率就是 1 - m_i / N。这是整张表某一列“没接住”的概率。如果目标哈希在某张表的任何一个折叠列都没被命中那这张表对这个目标就失效了。2.2 一张表的成功率所有列都漏掉才算失败一张表里任何一列命中一次就能还原出目标明文。所以“整张表漏掉”等价于“每一列都漏掉”。把所有列的漏报概率乘起来再被 1 减就是这张表的理论成功率S ≈ 1 - ∏_{i1}^{t} (1 - m_i / N)这个公式说明三件事。第一链长 t 会增加公式里的乘数项数每加一列就多一层覆盖机会所以链长对成功率是正向贡献。第二每列覆盖点 m_i 受前一轮覆盖影响链条越长后面的列增长会越来越慢这是反向压制。第三表总数 m 只影响起点数量不会线性放大成功率它被塞在 m_i 的递推里所以“把 m 加倍成功率远不会加倍”是正常的。用 Python 实现这个递推大约就是这么几行import math def table_success_prob(N, m, t): ms [] mi m for _ in range(t): ms.append(mi) mi N * (1 - math.exp(-mi / N)) miss 1.0 for mi in ms: miss * (1 - mi / N) return 1 - miss这里有个非常重要的使用边界这个公式在“链条不太长、表占空间比例不太大”的时候比较接近真实值。一旦 m×t 已经接近甚至超过 N理论值就会被严重高估因为模型里没有充分惩罚链条合并带来的全局损失。后面实测对比你会看到这个偏差到底有多大。2.3 多张表的组合成功率表之间的“独立”是近似单张表到不了 100%人们自然的反应是多做几张表。如果一共有 l 张表每张表的理论成功率分别是 S1、S2……Sl在“表与表之间互相独立”的假设下整体失败率等于每张表失败率的乘积S_total ≈ 1 - (1 - S1) × (1 - S2) × … × (1 - Sl)代码就是几行乘乘除除的事def multi_table_success_prob(tables, N): total_miss 1.0 for m, t in tables: s table_success_prob(N, m, t) total_miss * (1 - s) return 1 - total_miss但这里我必须泼一盆冷水多张表之间远非独立。只要它们覆盖的是同一个明文空间、用的是同一类归约函数族就必然存在大量重叠区域。用“独立假设”算出来的组合成功率通常是乐观值。尤其是当每张表本身的覆盖率已经很高时新增一张表带来的边际收益会迅速缩水。想准确评估多表成功率最可靠的办法还是用小规模模拟器实测然后把偏差系数外推到大空间。3. 一百万明文空间的实测对比理论和现实之间有一条深沟说一万遍理论不如跑一次实验。我在本地搭了一个小规模验证环境明文空间故意压得很小6 位数字也就是 N 1,000,000。这样在一台普通笔记本上可以真正把表建出来、把查询跑完适合用来观察理论公式和实测结果之间的差距。3.1 构造一个可控实验环境哈希函数直接用常见哈希算法的十六进制摘要归约函数则从摘要中取不同位置的 8 位十六进制片段、再对 1000000 取模。这样在不同折叠列上使用不同的摘要片段模拟“不同列使用不同归约函数”的效果。代码可以简化成下面这样核心是链构造和链查询import hashlib def H(p): return hashlib.md5(str(p).encode()).hexdigest() def R(col, h): # 从摘要的固定偏移位取 8 个十六进制字符转成整数后取模 off (col * 8) % (len(h) - 8) return int(h[off:off8], 16) % 1000000 def fold(col, h): return R(col, H(h))这里要特别注意直接把十六进制片段取模是一种“教学用法”真实工程里归约函数要设计得更复杂否则容易出现偏置和循环。后面第 5 部分会专门说这个问题。实验环境只是为了对照理论公式不需要工程级的完美。有了折叠函数再写建表和查询。建表时把链尾哈希作为键、链首明文作为值放进字典重复链尾用第一条覆盖。3.2 理论值和实际查询成功率的对照我随机抽了 3000 个明文用同样的哈希函数算出它们的哈希值作为测试集。测试集里的明文是从整个明文空间随机抽样而不是只从链覆盖区域抽样这一点特别重要。然后分别统计理论成功率和实测成功率得到下面一组数据参数组合理论成功率实测成功率偏差m20000, t100约 86.5%约 43.8%很大m20000, t300约 99.7%约 51.2%很大m50000, t100约 99.3%约 63.5%较大m10000, t500约 99.0%约 32.6%很大m5000, t50约 22.1%约 17.4%较小第一眼看过去理论公式在低覆盖场景下勉强可用而在高覆盖场景下高估得离谱。这验证了我在 2.2 里说的边界问题m×t 越大链条合并越严重理论公式越失效。另一个明显趋势是同样是总折叠次数接近的参数组合链条短而表多的组合实测效果远好于链条长而表少的组合。m20000, t300 的总折叠次数是 600 万m50000, t100 是 500 万前者折叠次数还更多实测成功率却更低。原因是链长增加以后链内合并概率呈非线性增长很多折叠都浪费在重复路径上了。3.3 偏差到底出在哪几个环节理论公式假设“每个折叠点在明文空间中随机落位、互不影响”这个假设在三个方面破了功。第一链尾去重。建表时如果两条链的终点哈希相同只保留一条。链长越长终点汇聚越容易发生去重丢掉的链就越多。实验中 m10000, t500 这组实际存进表里的有效链数远低于 10000这才是成功率崩盘的直接原因。第二折叠落点不是标准均匀分布。取模操作总会有轻微偏置有些区间被反复覆盖有些区间始终是黑洞。第三重放链条时还可能遇到循环。如果某个折叠点进去了一个环链条会在局部打转导致后续列全是重复覆盖。所以结论是理论公式适合用来确定参数搜索的方向不适合用来作为最终验收指标。真正确认一张表能不能用必须用独立测试集实测。4. 反推参数链长、表数、存储空间怎么权衡既然理论公式和实测有偏差那参数到底怎么定我通常的做法是先用简化公式做“方向性搜索”再用小空间模拟器做“精度校正”最后把校正系数放大到目标空间。这一节讲清楚这三个环节里的关键权衡。4.1 总存储固定时链长不是越长越好假设明文空间是 N你计划总共建造 M 条链每条链长 t那么存储量大约正比于 M因为每条链只存链首和链尾。单张表的折叠总次数是 M×t但有效覆盖率不是 M×t/N而是要打一个折扣。我把这个关系拆成两条力单独看。增加链长 t 会带来更多列理论上每列都是一次覆盖机会这是正向收益。但同时链长增加后每一条链内部发生合并的概率更高链的“末端”更容易和别的链汇合实际存活链快速下降。实验里 m10000, t500 被 m50000, t100 全面碾压已经说明问题五百步长链还没走到一半就大量身死不如一百步短链多造几条。所以固定总折叠次数的情况下一般应该优先增加链条数量而不是一味加长链条。到底选多长取决于明文空间的规模和归约函数的均匀程度。小空间实验里t 取 50 到 150 之间通常比较稳空间变大后t 可以适当加长但要控制在“平均链长带来的链内合并率可接受”的范围内。4.2 从目标成功率反推需要的表和链数如果你手上有一个硬指标比如要求成功率不低于 90%可以倒着做参数搜索。步骤大概是这样的第一步用小空间模拟器固定 N10^6生成几组 M 和 t 的实测成功率数据第二步拟合出“在当前归约函数设计下指定折叠总量能拿到多少实测覆盖率”的经验曲线第三步把目标 N 成比例放大同时保持“每单位明文空间对应的折叠量”不变得到目标空间需要的折叠总次数第四步根据存储预算交叉约束确定具体 M 和 t。这里的放大系数不能拍脑袋应该来自同一套归约函数、同一类明文空间形态的小规模实验。我吃过的亏是直接拿理论公式放大参数结果建了张巨大的表最后实测成功率比预期低了二三十个百分点白花时间。4.3 不同场景下的推荐参数范围以下是我在自建实验环境里测试过后觉得比较合理的经验值给新手做个起点参考。注意它们不是公式算出来的标准答案而是“从某个方向上搜索出来的可行区间”。明文空间规模链长 t 建议起点初始链数建议备注10^660~120总折叠量约 3~5 倍空间适合快速验证10^8150~300总折叠量约 8~15 倍空间增加链数收益更高10^10 以上300~600偏向多表组合必须用分表和不同归约族这个表的含义是当空间变大时链长得更粗才能覆盖足够多的“列机会”但表数也要跟上而不是单表无限做长。多表之间用不同的归约函数族才能把“独立近似”的误差尽量压小。5. 实验里踩过的坑一张看起来能用的表为什么经常爆冷最后这部分纯粹是实操中攒出来的经验。很多问题不是理论公式能告诉你的必须在建表、查表、评估这一整套流程里踩过才知道。5.1 归约函数设计不当会制造热点和循环我最初偷懒归约函数直接取“哈希字符串的前 8 位再取模”结果表建完以后查了一批哈希成功率低得离谱。排查下来发现某些摘要前缀的分布极不均匀大量折叠点挤在一小段区间里别的区间根本没人覆盖。后来改成从哈希的不同偏移位取片段、并混合一个常数偏移覆盖率立刻正常了。归约函数的核心要求是“每一列都尽量像一次新的均匀随机映射”任何规律性都会变成效率漏洞。5.2 多张表的“虚假独立性”为了凑成功率我同时建过多张表用的归约函数只是把常数偏移换了几个数字。看着是 l 张不同的表实际折叠路径高度相似表与表之间的覆盖率重叠非常严重组合成功率远低于“1-(1-S)^l”的预期。后来把归约函数族彻底打乱比如不同表采用不同取模策略、不同摘要片段起始位置甚至不同哈希算法组合才算真正发挥了多表优势。5.3 评估成功率时最容易犯的三个统计错误一个是用“链覆盖区域内的样本”做测试。建表时已经有了一张终点表如果测试哈希都从这些链会覆盖的位置附近取成功率当然虚高。正确做法是从整个明文空间随机取明文再算哈希完全不看链表结构。第二个是测试集太小几百条样本的方差巨大一次查询多失败几个点成功率能差出十个百分点。我一般至少跑两千到三千个样本。第三个是只看“总成功率”不看失败样本的分布。如果失败样本集中在某几个区间说明归约函数存在系统偏置这比整体低几个百分点更值得警惕。说回我自己现在的习惯每次设计彩虹表参数之前先在一个 10^6 空间的小环境里跑整套模拟拿到当前归约函数族的“理论→实测偏差系数”再用这个系数去推算大空间参数。这比迷信任何一个公式都靠谱得多。毕竟成功率这个东西终究是统计出来的不是算出来的。