密码攻击技术

一、时间空间折中技术

时间空间折中技术（简称TMTO，Time-Memory Trade-Off）是一种密码破解思路，主要用于攻击加密系统，比如找回密钥或破解哈希值。它不是一种“暴力破解”的笨办法，而是聪明地平衡“计算时间”和“存储空间”，让攻击更高效。发明人是Martin Hellman，在1970年代提出，常用于对称加密（如DES）或密码哈希（如Rainbow Table的变种）。

1、预计算

预先生成m条加密“链条”，每条链像一条路径，总长度t+1：

• 选一个起点SP（Starting Point，随机的假密钥）。
• 用加密函数E和一个“归约函数R”（Reduction，把输出变回密钥大小）反复计算：
  • X1 = R(E(P, SP)) // 先加密，再归约
  • X2 = R(E(P, X1))
  • ... 继续t次（链长），直到终点EP = Xt。
• 只存起点SP和终点EP，不存中间所有步骤（节省空间）。

2、攻击

现在有目标密文C和明文P

• 从X0 = C 开始，模拟链条计算：
  • X1 = R(E(P, X0))
  • X2 = R(E(P, X1))
  • ... 计算直到Xi 匹配某个存的EPj。

一旦匹配，说明目标链在第j条预计算链里。

• 然后从SPj 开始，重算整条链（只需t次计算），找到链中等于“C”的那个X的前一个点（就是K）。

3.举例

假设密钥空间N=100（实际是2^56超大），链长t=5，m=4条链。E是简单异或加密（实际用DES），R是取模100（简化）。

预计算表格（虚构）：

• 链1: SP0=3 → 7 → 2 → 9 → 5 (EP0=5)
• 链2: SP1=1 → 4 → 8 → 6 → 0 (EP1=0)
• 链3: SP2=10 → 15 → 20 → 25 → 30 (EP2=30）
• 链4: SP3=40 → 45 → 50 → 55 → 60 (EP3=60)
• 只存SP和EP：(3,5), (1,0), (10,30), (40,60)

现在目标密文C=8（假设真实K=4）

实际攻击：

1. X0 = C =8
2. X1 = R(E(P,8)) = 6
3. 检查6是否EP？不是。
4. X2 = R(E(P,6)) = 0
5. 检查0，是EP1=0！匹配链2。
6. 重建链2：从SP1=1 →4→8→6→0 
7. 逐试：
   • E(P,1)=?8 否
   • E(P,4)=8 是！K=4。

二、中间相遇攻击

中间相遇攻击（简称MITM，不是网络的那个“中间人”）是一种经典的密码破解思路，主要针对“多重加密”系统，比如用两次DES加密（2-DES）或类似的多层加密。它不是从头到尾穷举所有可能，而是聪明地“从两头往中间挤”，大大减少计算量。发明人是Diffie和Hellman，在1977年提出。MITM本质上是一种时间-空间折中，用存储换时间加速。

1.基本思路

假设系统是双重加密：C = E(K2, E(K1, P))，E是加密函数（如DES），K1和K2是两个密钥（每个56位，总112位）。

• 穷举攻击：试所有2^112种组合，太慢（2^112次加密）。
• MITM思路：
  • 从前半段算：固定P，穷举所有可能K1，算中间值M = E(K1, P)，存成表（K1 → M）。
  • 从后半段算：固定C，倒推穷举所有K2，算中间值M' = D(K2, C)，然后查表看M'是否匹配某个M。
  • 如果匹配，说明那个K1和K2就是正确密钥对！

为什么高效？每个半段只需2^56次计算，加上存储2^56个中间值。时间从2^112降到2^57，空间用2^56。

• 核心：中间值M是“相遇点”，前半从P推，后半从C倒推，在M处碰头。

2.攻击过程

阶段1: 预计算前半段（offline）

• 穷举所有可能K1（2^56 for DES）。
• 对每个K1，计算M_i = E(K1, P)。
• 存成排序表或哈希表：{M_i : K1}（按M排序，便于查找）。
• 这步花时间，但只做一次。空间是主要成本。

阶段2: 实际匹配后半段（online）

• 穷举所有可能K2（同样2^56）。
• 对每个K2，计算M'_j = D(K2, C)。
• 查预计算表：如果M'_j 在表中，取出对应K1。
• 验证：用K1和K2全加密P，看是否得C（防假阳性，因为可能碰撞）。
• 找到匹配的(K1, K2)就是密钥。

补充：K1,K2 不独立

这里，我猜是如果K1,K2有交集，那么交集部分加密密钥和解密密钥相同，所以可能是真正的密钥；另外不相交的部分，就是互相独立的情况，计算A1和A2后查表匹配，找出可能的密钥对。