WeChall - Three Times Sad

Posted on Edited on Views: Disqus:

Challenge

题面给三段 encrypted messages。已知发送者使用 64-bit LFSR 生成 OTP keystream，bit stream 为 MSB first，并提到 teleconferencing 和 master key。

Solution

这是多密文 + LFSR cryptanalysis。

路线：

  1. Base64 解码三段 ciphertext。
  2. 利用同一或相关 LFSR keystream 的结构，做 crib dragging。
  3. 64-bit LFSR 可用 Berlekamp-Massey 从足够 keystream bits 恢复反馈多项式。
  4. 明文主题是 teleconferencing，先猜常见文本/协议片段，如 conference、meeting、call、http 等。
  5. 一旦恢复部分 plaintext，就得到 keystream，再反推 LFSR state/master key。

如果三段使用同一 OTP keystream，则两两 XOR 会消掉 keystream：

1
x = bytes(a ^ b for a, b in zip(c1, c2))  # p1 ^ p2

然后按 natural language crib 逐步扩展。

当前未完成实际 LFSR 恢复，不写 master key spoiler。