经典密码攻击原理
一句话定义
经典密码攻击的共同机理不是堆算力暴力搜索,而是利用算法或实现泄露的信息冗余——统计规律、碰撞结构、错误反馈、物理时序——把看似 2^n 的搜索空间压缩数个数量级。
为什么重要
把攻击按”利用哪一层泄露”分类,是防御设计的坐标系:知道了生日界才知道哈希要选多长;知道了 padding oracle 才明白认证加密为何重要;知道了侧信道才理解常数时间实现的必要性。这类攻击直接对应 CWE-208(可观察时序不一致)、CWE-916(口令哈希计算不足)等缺陷分类。
前置知识
- kp-007:分组模式、IV/nonce、AEAD、熵与密钥空间。
- 概率初步:生日问题的直觉。
- 哈希函数的输出空间与抗碰撞目标。
核心概念
- 频率分析(frequency analysis):利用自然语言字符分布破解确定性替换。
- 已知明文(known-plaintext):以可预测内容为锚点压缩搜索空间。
- 生日攻击(birthday attack):利用碰撞概率的平方根级增长。
- 预言机(oracle):把秘密判定变成可观察响应的实现缺陷。
- 侧信道(side channel):时序、功耗、缓存等物理泄露。
- KDF(密钥派生函数,key derivation function):以可调成本对抗口令猜测。
原理与机制
统计与结构层。单表替换密码保留语言的字符频率分布:英文中 e、t、a 高频,二字母组合与重合指数提供第二层约束,26! 的名义空间在几十次”假设-验证”内坍缩。多表密码(如 Vigenère)先用重合指数估计密钥长度,再退化为多个单表逐个击破。现代映射:ECB 类确定性加密与协议头、文件魔数等可预测结构,让统计攻击在现代复现。由此建立的安全基线:必须抵御选择明文攻击(CPA,Chosen-Plaintext Attack)。
碰撞层。生日攻击的数学基础:在大小为 2^n 的输出空间中随机取 q 个值,碰撞概率约 1 − e^(−q^2/2^(n+1));当 q ≈ 2^(n/2) 时概率约为 63%。含义是找碰撞只需平方根级代价,远低于找原像的 2^n。这是 n 位哈希抗碰撞强度只有 n/2 位的原因,也是 MD5(实际碰撞成本已低于 2^64)与 SHA-1(2017 年公开实际碰撞)被弃用的量化依据。
反馈层。padding oracle 类攻击的前提是解密器成为”可区分的预言机”:填充合法与 MAC 匹配两个失败模式返回不同错误、或耗时不同(CWE-209),等于提供逐字节判定信号。攻击者据此以每次查询换取对明文字节的判定信息,把复杂度从 2^n 降为与明文长度线性相关的查询次数。机理要点:数学上不可区分的失败被实现拆分成了可观察类别。对应的现代解法是 AEAD——解密端只允许”通过/失败”两个出口。
物理层。侧信道打破”攻击者只见输入输出”的假设:分支与查表行为使时间随秘密位波动(缓存命中与否改变内存访问延迟)、功耗随数据汉明权重波动、共享硬件的缓存行碰撞可反推查表索引。2003 年公开的远程时序攻击研究证明,跨网络时间测量足以恢复 RSA 私钥——数学强度与实现强度可相差多个数量级。防御是常数时间实现:无秘密分支、无秘密索引查表、无数据相关内存访问。
低熵层。口令是低熵秘密:真实分布高度集中,字典攻击按”先验概率排序的猜测列表”即可命中大比例用户;无盐哈希可被彩虹表预计算,一次计算全库复用。盐迫使每库单独重算,KDF(bcrypt/scrypt/argon2)再用可调成本与内存硬度对抗 GPU/ASIC 并行。对抗模型是乘积关系:猜测成本 = 单次验证成本 × 猜测次数。
防御映射:常数时间实现消除物理与反馈泄露;认证加密消除 padding oracle 面;按 2^(n/2) 目标强度选择哈希长度;口令一律经 KDF(参数标准见 kp-009)。
实例或案例
- 1586 年苏格兰玛丽女王信件被频率分析破译(公开史料),确立统计破解对替换密码的决定性。
- 二战 Enigma 破译依赖已知明文锚点(公开史实),印证可预测结构对搜索空间的压缩。
- POODLE(CVE-2014-3566,2014 年公开披露):TLS 填充校验的失败模式可区分,构成 oracle 类缺陷;修复路径即迁移到认证加密。
- 2003 年公开的远程时序攻击论文证明网络级时间测量可恢复 RSA 密钥,推动了常数时间实现的普及。
- 2017 年公开的 SHA-1 实际碰撞研究(SHAttered)验证了生日界的工程可达性。
常见误区
- “算法强等于系统强”:泄露发生在实现层与协议层,数学强度只是下限。
- “暴力破解需要 2^256 所以不可能”:oracle 与侧信道可以把代价降到可执行规模。
- “加盐就够”:盐只防预计算复用,不防字典猜测;慢 KDF 才是核心。
- “碰撞攻击离工程很远”:生日界意味着强度减半,n 位哈希需按 n/2 位评估。
自测题
- 频率分析为什么对单表替换有效? 答案要点:确定性替换保留字符统计分布,语言先验把 26! 空间压缩到可人工验证的规模。
- 生日界为什么是 2^(n/2)? 答案要点:q 个输入产生约 q^2/2 个两两配对机会,命中 2^n 空间只需 q ≈ 2^(n/2)。
- padding oracle 的根本缺陷在数学层还是实现层? 答案要点:实现层——把不可区分的失败拆成可观察类别(错误类型/时序),打破安全定义中的不可区分性假设。
公式或模型
生日碰撞模型:输出空间 N = 2^n,随机样本 q 个,碰撞概率 P ≈ 1 − e^(−q^2/2N);令 P ≈ 0.63 得 q ≈ 2^(n/2)。口令对抗模型:攻击成本 ≈ 单次验证成本 × 猜测次数,KDF 提高前者,盐与黑名单提高后者。
图示
攻击面:从"2^n 暴力"到"信息泄露压缩"
┌────────────────┬──────────────────────────┐
│ 攻击类别 │ 利用的泄露层 │
├────────────────┼──────────────────────────┤
│ 频率分析 │ 语言统计(确定性替换) │
│ 已知明文 │ 协议结构(可预测内容) │
│ 生日攻击 │ 数学结构(碰撞界 2^(n/2)) │
│ padding oracle │ 实现反馈(错误可区分) │
│ 侧信道 │ 物理泄露(时序/功耗/缓存) │
│ 字典/彩虹表 │ 低熵分布(口令集中) │
└────────────────┴──────────────────────────┘
防御映射:认证加密 │ 常数时间 │ KDF
直观类比
生日问题:一个 366 人的教室里几乎必然有人同月同日生——配对机会是人数的平方级。预言机像猜数字游戏里每次都热心报”热/冷”的主持人,答案本身就成了泄露。彩虹表是提前印好的”哈希-口令对照字典”,盐则让每本字典作废,逼攻击者逐库重印。
与其他知识点的关系
- kp-007:误用模式是攻击面的来源——无 AEAD 才有 padding oracle,无盐才有彩虹表。
- kp-009:KDF 参数标准、泄露黑名单与协议层防御在此落地。
- kp-039:非对称实现同样暴露于侧信道与 oracle 类缺陷。
延伸阅读
- Jean-Philippe Aumasson《Serious Cryptography》
- Menezes、van Oorschot、Vanstone《Handbook of Applied Cryptography》
- Vaudenay《Security Flaws Induced by CBC Padding—Applications to SSL, IPsec, WTLS》(Eurocrypt 2002 论文)
- CWE-208、CWE-916