Many-Time Pad

攻击原理

设明文 P1、P2 用同一个密钥 K 加密，得到密文 C1、C2：

1
2
C1 = P1 XOR K
C2 = P2 XOR K

攻击者截获两条密文后，可以计算它们的异或：

1
2
3
C1 XOR C2 = (P1 XOR K) XOR (P2 XOR K) 
          = P1 XOR P2 XOR (K XOR K) 
          = P1 XOR P2

密钥被完全消除，攻击者得到了 P1 XOR P2

通过交互式的猜测（crib‑dragging），攻击者能将两条明文分离开，进而还原密钥并读取所有用同一密钥加密的消息

Crib‑dragging

假设我们猜测某条明文的某个位置可能出现一个单词（称为 crib），例如 "the " 或 "secret"

将该 crib 异或到 P1 XOR P2 的对应位置：

  • 如果猜测的 crib 恰好是 P1 的子串，则运算结果就会变成 P2 对应位置的原文

  • 如果结果是可读的英文（或符合语言习惯），则猜测很可能正确

  • 随后可以从 P2 的已知片段继续猜测 P1 的其他部分，逐步 “拖拽” 出整段明文

另一个重要技巧是 “空格特性”：

1
2
3
'A' XOR 0x20 = 'a'   （大写变小写）
'a' XOR 0x20 = 'A'   （小写变大写）
空格(0x20) XOR 字母 = 翻转该字母的大小写

在 P1 XOR P2 中，若某个字节呈现出一个字母（0x41‑0x5A 或 0x61‑0x7A），极大概率说明该位置一个明文是空格，另一个是对应的大小写翻转字母

通过判断上下文，可以标出空格位置，极大加速破解

详细案例

假设攻击者截获的密文如下

1
2
C1: 0E 56 77 5F 38 79 FA 5F 52 1C 2F 3C 39 5E 5C 1E 5B 6F
C2: 13 4A 32 16 38 3C F8 0D 5A 11 7C 21 2F 0C 4A 4A 0E 6F

1. 计算 XOR = C1 XOR C2 = P1 XOR P2

1
2
X = C1 XOR C2:
1D 1C 45 49 00 45 02 52 08 0D 53 1D 16 52 16 54 55 00

2. 寻找字母字节

攻击者遍历 X 的每一个字节，识别所有落在字母范围的值：

  • X[2] = 0x45 → ‘E’ (大写字母)

  • X[3] = 0x49 → ‘I’ (大写字母)

  • X[5] = 0x45 → ‘E’

  • X[7] = 0x52 → ‘R’

  • X[10] = 0x53 → ‘S’

  • X[13] = 0x52 → ‘R’

  • X[15] = 0x54 → ‘T’

  • X[16] = 0x55 → ‘U’

得到候选位置：索引 2, 3, 5, 7, 10, 13, 15, 16

3. 利用上下文区分空格归属

现在攻击者需要判断在候选位置上，空格究竟属于 P1 还是 P2

这里利用第二个统计特性：空格在英文中频繁出现，且通常分隔单词。如果某个位置是空格，那么其前后往往是字母

攻击者可以结合候选字母的大小写和局部结构进行推断。例如，索引 2 的 X[2] = 'E'：

  • 假设 P1[2] = 空格 (0x20)，则 P2[2] = 0x20 XOR 0x45 = 0x65 = 'e'（小写 e）。

  • 假设 P2[2] = 空格，则 P1[2] = 0x20 XOR 0x45 = 0x65 = 'e'

单独看无法确定，但我们可以借助其他候选位置的相互关系。英文单词通常不会连续两个空格

所以如果两个候选位置相邻或相近，它们不可能同时是空格

更进一步，攻击者还会采用一种策略：暂时假设某一个位置的空格归属，然后看能否推导出连贯的字母序列

如果错误，推导出的片段会呈现乱码或不符合英文音节；如果正确，则能拼接出可读的单词片段

4. 推演

考虑索引 13 到 16：

1
X[13]=R, X[15]=T, X[16]=U（索引14不是字母）

如果 P1 在这些位置中有空格，推导出的 P2 对应字母会形成某种模式

尝试先从 X[16]=U 开始，英文单词结尾很少出现单独的大写 U，更可能是小写 u

假设 P2[16] = 空格 (0x20)，则 P1[16] = 0x20 XOR 0x55 = 0x75 = 'u'

同时 X[17]=00 意味着 P1[17] = P2[17]

英文中，单词结尾后可能是标点，比如 '.'（0x2E）或 '!'，我们稍后再看

再看 X[15]=T，假设 P2[15] = 空格，则 P1[15] = 0x20 XOR 0x54 = 0x74 = 't'

现在我们得到 P1[15]='t', P1[16]='u'，连续小写字母 "tu"

若转而假设 P1[15]=空格，则 P2[15]=0x20 XOR 0x54=0x74='t'，且 P1[16] 如果是空格（X[16]=U 归因于 P2 是空格），则 P2[16]=0x20 XOR 0x55=0x75='u'，得到 P2 的 "tu",目前无法辨别

…………

经过几次回溯后确认

1
2
P1: "The secret is out."
P2: "It is a mystery!!."