时间存储折中攻击

一、基本背景与动机

1. 密码分析的目标

   • 给定密文 $C=E(P,K)$，在已知明文 $P$的情况下恢复密钥$K$。
   • 不依赖算法内部结构（黑盒模型），适用于任意分组密码。

2. 三种通用密钥恢复方法对比

   方法	时间复杂度 $T$	存储复杂度 $M$	特点
   穷举攻击	$2^k$	可忽略	每次攻击都需重新计算
   查表攻击	1	$2^k$	预存所有 $(K,C)$ 对，内存巨大
   TMTO 攻击	介于两者之间	介于两者之间	平衡时间与存储

3. 核心思想：时间-存储折中（Time-Memory Tradeoff）

   • 预计算阶段：一次性构建查找表（存储起点 SP 和终点 EP）。
   • 在线攻击阶段：利用表快速定位密钥，减少实时计算量。
   • 目标：在可接受的存储下显著降低单次攻击时间。

---

二、Hellman TMTO 攻击详解

1. 基本设定

• 分组密码：$C=E(P,K)$，其中 $|P|=|C|=n$，$|K|=k$。
• 为简化，常假设 $n=k$（如 DES：$k=56$）。

2. 链的构造（Chain）

• 固定明文 $P$。
• 从起点 $SP=K_0$ 开始迭代：$$K_1=E(P,K_0),K_2=E(P,K_1),\dots ,K_t=E(P,K_{t-1})=EP$$
• 每条链长度为 $t+1$，仅存储 $(SP,EP)$。

3. 预计算阶段

• 构造 $m$ 条独立链，每条长 $t$。
• 总预计算工作量：$mt$。
• 存储需求：$m$ 个 $(SP,EP)$ 对（需按 EP 排序以便快速查找）。

4. 在线攻击阶段

• 已知 $C=E(P,K)$。
• 从 $X_0=C$ 开始，迭代计算：$$X_1=E(P,X_0),X_2=E(P,X_1),\dots$$
• 若某步 $X_i=E{P}_j$（查表命中），则从 $S{P}_j$ 重建整条链：$$Y_0=S{P}_j,Y_1=E(P,Y_0),\dots$$
• 若存在 $Y_{t-i-1}$ 使得 $E(P,Y_{t-i-1})=C$，则 $K=Y_{t-i-1}$。

5. 成功概率分析（理想 vs 现实）

• 理想情况：链无重叠、无环 → 覆盖全部密钥空间。
• 现实问题：
  • 链合并（Merge）：不同起点生成相同中间值，导致信息丢失。
  • 循环（Cycle）：链进入自循环，无法到达 EP。
  • 假警报（False Alarm）：命中 EP 但重建链不包含真实密钥。

6. 改进：多表法（Multiple Tables / Rainbow Tables）

• 使用 $r$ 个不同的归约函数 $F_0,F_1,\dots ,F_{r-1}$。
• 每张表使用不同 $F_i$ 构造链，避免链合并。
• 参数选择：令 $m=t=r=2^{k/3}$，则：
  • 存储 $M=mr=2^{2k/3}$
  • 时间 $T=tr=2^{2k/3}$
  • 成功概率 ≥ 55%

7. 成功概率公式（基于“占位问题”）

• 将密钥空间视为 $N=2^k$ 个“桶”，预计算的 $mtr$ 个点视为“球”。
• 覆盖密钥比例 ≈ $1-e^{-mtr/N}$
• 故成功概率：$$P_{\text{success}}\approx 1-e^{-mtr/2^k}$$

8. 复杂度权衡曲线

• 基本关系：$T{M}^2=N^2=2^{2k}$
• 最优平衡点：$T=M=2^{2k/3}$

---

三、扩展：TMDTO（时间-存储-数据折中）

1. 动机

• 当攻击者能获取多个密文（对应不同密钥或 IV）时，可进一步降低复杂度。

2. 模型

• 函数 $f:K\times V\to C$，其中 $V$ 为公共参数（如 IV）。
• 在线阶段获得 $D$ 个输出：$y_1=f(x_1),\dots ,y_D=f(x_D)$
• 目标：恢复任意一个 $x_i$

3. 复杂度关系

• $T{M}^2{D}^2=N^2$，其中 $N=|K\times V|=2^{k+v}$
• 示例：若 $D=N^{1/4}$，则 $T=M=N^{1/2}$

---

四、应用场景

应用	说明
分组密码（如 DES）	$f(K)=E(P,K)$，$ N = 2^k $
流密码	目标是恢复内部状态 $S$（大小 $s$）• Babbage-Golic 攻击：$TM=2^s$• 安全要求：$s\ge 2k$
哈希函数（口令破解）	$f(\text{password})=H(\text{pw})$• 使用彩虹表预计算• 加盐（salt）可使 $N$ 增大，抵抗 TMTO
公钥加密（特定场景）	如 NTRU 中恢复明文，需识别合适的单向函数

---

五、防御建议

1. 增大密钥/状态空间：使 $2^{2k/3}$ 不可行。
2. 加盐（Salt）：对哈希函数，使每个用户有独立函数 $f_{\text{salt}}$，破坏预计算通用性。
3. 流密码设计：
   • 内部状态 $s\ge 2k$
   • IV 长度 $v\ge k$
4. 限制数据量：防 TMDTO（如 DRACO 限制每密钥输出 $2^{32}$ 比特）。

---

✍️ 练习题（含答案）

---

题 1：基本概念

问：Hellman TMTO 攻击中，为什么只存储链的起点（SP）和终点（EP），而不是整条链？

答：
为了节省存储空间。整条链长度为 $t+1$，若存储所有点，存储量为 $O(mt)$，与穷举相当。而只存 $(SP,EP)$ 可将存储降至 $O(m)$。在线攻击时若命中 EP，再通过 SP 实时重建链（最多 $t$ 步），实现时间与存储的折中。

---

题 2：复杂度计算

问：对一个 56 位密钥的密码（如 DES），若采用 Hellman TMTO 攻击并设 $m=t=r=2^{19}$，求：

1. 预计算工作量；
2. 存储需求 $M$；
3. 单次攻击时间 $T$；
4. 成功概率近似值。

答：

1. 预计算 = $mtr=2^{19}\times 2^{19}\times 2^{19}=2^{57}$
2. $M=mr=2^{19}\times 2^{19}=2^{38}$
3. $T=tr=2^{19}\times 2^{19}=2^{38}$
4. $P\approx 1-e^{-2^{57}/2^{56}}=1-e^{-2}\approx 1-0.135=0.865$（86.5%）

注：实际因链合并，成功率低于此值。

---

题 3：流密码安全

问：某流密码密钥长 $k=80$ 位，IV 长 $v=64$ 位，内部状态 $s=128$ 位。是否易受 TMTO 攻击？为什么？

答：
是，易受攻击。
因为 TMTO 攻击复杂度取决于输入空间大小 $N=2^{k+v}=2^{144}$。
即使状态 $s=128<2k=160$，但更关键的是 $v=64<k=80$。
根据 TMDTO 理论，当 $v<k$ 时，攻击者可通过多数据（不同 IV）发起高效攻击，与状态大小 $s$ 无关。
安全设计应满足 $v\ge k$。

---

题 4：哈希与加盐

问：为什么在口令哈希中加入随机盐（salt）能有效防御彩虹表攻击？

答：
彩虹表是针对固定哈希函数 $H$ 预计算的。
加盐后，每个用户的哈希为 $H(\text{pw}\parallel \text{salt})$，相当于每个用户有不同的单向函数 $H_{\text{salt}}$。
攻击者无法用一张表攻击所有用户，必须为每个 salt 单独预计算，使预计算成本从 $O(1)$ 增至 $O(\text{用户数})$，失去可行性。

---

题 5：权衡曲线推导

问：从 Hellman TMTO 的参数关系出发，推导出 $T{M}^2=N^2$ 的过程。

答：
设：

• $m$：链数
• $t$：链长
• $r$：表数（不同归约函数）
• $N=2^k$：密钥空间大小

为保证高成功率，需覆盖大部分密钥空间：

$$m\cdot t\cdot r\approx N\text{(1)}$$

存储复杂度（每表存 $m$ 对，共 $r$ 表）：

$$M=m\cdot r\text{(2)}$$

时间复杂度（每表最多走 $t$ 步，共 $r$ 表）：

$$T=t\cdot r\text{(3)}$$

由 (2)(3) 得：

$$M^{2}T=(mr{)}^2(tr)=m^{2}t{r}^3$$

但更直接：由 (1) 得 $m=N/(tr)$，代入 (2)：

$$M=\frac{N}{tr}\cdot r=\frac{N}{t}\Rightarrow t=\frac{N}{M}$$

代入 (3)：

$$T=\frac{N}{M}\cdot r$$

若取 $r\approx t=N/M$（平衡设计），则：

$$T\approx \frac{N}{M}\cdot \frac{N}{M}=\frac{N^2}{M^2}\Rightarrow T{M}^2=N^2$$

即得 $T{M}^2=N^2$。

---