Many Time Pad Attack

一些基础知识

符号：

⊕ 代表异或

C1 代表密文

M1 代表明文

性质：

交换律
结合律 (a ⊕ b ) ⊕ c = a⊕ ( b ⊕ c)
任何数x x ⊕ x = 0 x ⊕ 0 = X
自反性 x ⊕ b ⊕ b = x ⊕ 0 = x

Description

Many-Time-Pad (多时间垫) 攻击是一种针对多次使用相同密钥的流密码（如一次性密码本，One-Time Pad）的密码分析技术。其核心原理是利用密钥重用导致的明文信息泄露，通过数学和统计方法恢复部分或全部明文。以下是其核心原理和步骤：

1. 一次性密码本（OTP）的安全前提
OTP的安全性是建立在：

密钥完全随机且仅使用一次。
密钥长度 ≥ 明文长度。
若同一密钥被多次加密不同明文（即 C₁ = P₁ ⊕ K, C₂ = P₂ ⊕ K），则攻击者可通过密文的组合推断出明文信息。

2. 攻击原理：密钥重用的漏洞
当同一密钥 K 加密多个明文时，密文之间的异或（⊕）等价于明文之间的异或：

$C₁ ⊕ C₂ = (P₁ ⊕ K) ⊕ (P₂ ⊕ K) = P₁ ⊕ P₂$
形象一点可以表达成这样：

密文 = 明文 ⊕ 密钥
密文1 ⊕ 密文2 = 明文1 ⊕ 明文2 ⊕ 密钥1 ⊕ 密钥2

此时，攻击者获得了 P₁ ⊕ P₂（即明文的异或结果），而无需知道密钥 K。

3. 利用明文冗余恢复信息
通过分析 P₁ ⊕ P₂，攻击者可以利用自然语言的统计特性（如字母频率、空格、常见词）逐步推测明文。例如：

空格字符攻击：在ASCII编码中，空格（0x20）与字母异或的结果具有特定模式（如大写/小写转换）。
词频分析：对 P₁ ⊕ P₂ 的局部进行猜测，若某段异或结果符合常见词的统计特征（如英文中的”the”、”and”），则可反推明文片段。

实践

BUUCTF: [AFCTF2018]

25030206463d3d393131555f7f1d061d4052111a19544e2e5d54
0f020606150f203f307f5c0a7f24070747130e16545000035d54
1203075429152a7020365c167f390f1013170b1006481e13144e
0f4610170e1e2235787f7853372c0f065752111b15454e0e0901
081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a1855
0909075412132e247436425332281a1c561f04071d520f0b1158
4116111b101e2170203011113a69001b47520601155205021901
041006064612297020375453342c17545a01451811411a470e44
021311114a5b0335207f7c167f22001b44520c15544801125d40
06140611460c26243c7f5c167f3d015446010053005907145d44
0f05110d160f263f3a7f4210372c03111313090415481d49530f

设每一个字符串（密文）为$C_i$,都是某个key异或上明文 $M_i$ 得到的.我们的目标是获取到这个key,已知明文是英文句子.

$C_1 ⨁ C_2 =(M_1 ⨁ key) ⨁ (M_2 ⨁ key) = M_1 ⨁ M_2$

因此两个密文异或得到两个明文

我们使用$C_1$异或上其他的密文

import binascii
import string

loca = string.ascii_lowercase + string.ascii_uppercase

def hextostr(hexstr):
    hex = hexstr.encode("utf-8")
    str_bin = binascii.unhexlify(hex)
    return str_bin.decode("utf-8")

c1 = "25030206463d3d393131555f7f1d061d4052111a19544e2e5d"
c2 = '0f020606150f203f307f5c0a7f24070747130e16545000035d'
c3 = '1203075429152a7020365c167f390f1013170b1006481e1314'
c4 = '0f4610170e1e2235787f7853372c0f065752111b15454e0e09'
c5 = '081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a18'
c6 = '0909075412132e247436425332281a1c561f04071d520f0b11'
c7 = '4116111b101e2170203011113a69001b475206011552050219'
c8 = '041006064612297020375453342c17545a01451811411a470e'
c9 = '021311114a5b0335207f7c167f22001b44520c15544801125d'
c10 = '06140611460c26243c7f5c167f3d015446010053005907145d'
c11 = '0f05110d160f263f3a7f4210372c03111313090415481d49'
chiphers =[c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11]

s2 = hextostr(c2)
sc1 = hextostr(c1)
for chipher in range(len(chiphers)):
    if chipher == 0:
        continue
    for i in range(len(sc1)):
        asc =chr(ord(sc1[i]) ^ ord(hextostr(chiphers[chipher])[i]))
        for i in asc:
            if i in loca:
                print(i,end="")
            else:
                print(".",end="")
    print()

得到的内容如下：

....S....N.U.....A..M.N..
...Ro..I...I....SE....P.I
.E..H...IN..H...........T
..A.H.R.....E....P......E
...RT...E...M....M....A.L
d...V..I..DNEt........K.D
.......I....K..I.ST...TiS
.....f...N.I........M.O..
.........N.I...I.S.I..I..
....P....N.OH...SA....Sg..

可以观察到，有些列上有大量的英文字符，有些列一个英文字符都没有。这是偶然现象吗？

ascii表

ascii 码表在 Linux 下可以通过 man ascii 指令查看。它的性质有：

0x20 是空格。低于 0x20 的，全部是起特殊用途的字符； 0x20~0x7E 的，是可打印字符。
0x30~0x39 是数字 0,1,2…9。
0x41~~0x5A 是大写字母 A-Z； 0x61~~0x7A 是小写字母 a-z.

我们可以注意到一个至关重要的规律：小写字母 xor 空格，会得到对应的大写字母；大写字母 xor 空格，会得到小写字母！所以，如果 x ⨁ y 得到一个英文字母，那么x和y之中有一个很大概率可能是空格，那么来看 C1 ⊕ 其他密文也就是M1 ⊕ 其他明文的表，如果第col列存在大量英文字母,我们可以猜测 M1[col] 是一个空格知道M1的col位是空格有什么用呢？别忘了异或运算下，x的逆元是其自身。所以

$M_i[col] = M_1[col] ⨁ M_i[col] = M_1[col] ⨁ M_i[col] ⨁ 0x20$

代码如下：

import Crypto.Util.strxor as xo
import libnum, codecs, numpy as np

def isChr(x):
    if ord('a') <= x and x <= ord('z'): return True
    if ord('A') <= x and x <= ord('Z'): return True
    return False


def infer(index, pos):
    if msg[index, pos] != 0:
        return
    msg[index, pos] = ord(' ')
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(' ')

def know(index, pos, ch):
    msg[index, pos] = ord(ch)
    for x in range(len(c)):
        if x != index:
            msg[x][pos] = xo.strxor(c[x], c[index])[pos] ^ ord(ch)


dat = []

def getSpace():
    for index, x in enumerate(c):
        res = [xo.strxor(x, y) for y in c if x!=y]
        f = lambda pos: len(list(filter(isChr, [s[pos] for s in res])))
        cnt = [f(pos) for pos in range(len(x))]
        for pos in range(len(x)):
            dat.append((f(pos), index, pos))

c = [codecs.decode(x.strip().encode(), 'hex') for x in open('Problem.txt', 'r').readlines()]

msg = np.zeros([len(c), len(c[0])], dtype=int)

getSpace()

dat = sorted(dat)[::-1]
for w, index, pos in dat:
    infer(index, pos)

know(10, 21, 'y')
know(8, 14, 'n')

print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))

key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)

输出：

Dear Friend, This time I u
nderstood my mistake and u
sed One time pad encryptio
n scheme, I heard that it 
is the only encryption met
hod that is mathematically
 proven to be not cracked 
ever if the key is kept se
cure, Let Me know if you a
gree with me to use this e
ncryption scheme always...
b'afctf{OPT_1s_Int3rest1ng}!'

总结

Many-Time-Pad攻击利用了密钥重用导致明文信息线性泄漏的特性，结合自然语言的冗余性，通过统计分析恢复明文。这再次验证了OTP的核心安全准则：密钥绝对不可重用。
Many-Time-Pad 是不安全的。我们这一次的攻击，条件稍微有点苛刻：明文必须是英文句子、截获到的密文必须足够多。但是只要攻击者有足够的耐心进行词频分析、监听大量密文，还是能够发起极具威胁性的攻击。如果铁了心要用直接xor来加密信息，应当采用一次一密(One-Time-Pad)

参考：

Crypto

#Crypto

Many Time Pad Attack

https://zer0ptr.github.io/2025/06/22/Many-Time-Pad-Attack/

Author

zer0ptr

Posted on

June 22, 2025

Licensed under

攻防世界Crypto-了不起的盖茨比 Previous

攻防世界Crypto-cat's gift Next