本文讨论的加密方式是最简单的一种：简单异或。准备一个 key 字符串，然后利用 key 去异或相同长度的明文，即得到密文。如果每个密文都利用新的 key 去加密，那么这种方式称为“一次一密”（One-Time-Pad）。OTP是无条件安全的：即使攻击者拥有无限的计算资源，都不可能破译OTP加密的密文。
然而，一次一密的密钥分发是比较困难的。首先，Alice 想要 给 Bob 发送长度为 n 的信息，则必须在这之前传送长度为 n 的密钥，相当于传输的数据总量翻了倍。其次，尽管密文是无条件安全的，但密钥的传输信道未必是安全的，攻击者一旦窃听了密钥，则可以解密密文。
那么马上就可以想到一个投机取巧的方法—— Alice 造一个比较长的密钥，然后用非常秘密的方式告诉 Bob. 接下来，Alice 每次向 Bob 发送信息，都把明文异或上这个约定好的字符串；Bob 收到信息之后，把密文异或上 key, 于是就可以拿到明文。整个过程只需要传送一次密钥，这是很方便的。这种方式称为 Many-Time-Pad (MTP).
很遗憾，上述的 MTP 办法是不安全的。攻击者如果截获了足够多的密文，就有可能推断出明文、进而拿到密钥。这个缺陷是异或运算的性质带来的。
例子
作为 MTP 攻击的范例，来看下面一道例题：
BUUCTF: [AFCTF2018]你听过一次一密么？
(原题有bug, 笔者有少量改动)
25030206463d3d393131555f7f1d061d4052111a19544e2e5d54
0f020606150f203f307f5c0a7f24070747130e16545000035d54
1203075429152a7020365c167f390f1013170b1006481e13144e
0f4610170e1e2235787f7853372c0f065752111b15454e0e0901
081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a1855
0909075412132e247436425332281a1c561f04071d520f0b1158
4116111b101e2170203011113a69001b47520601155205021901
041006064612297020375453342c17545a01451811411a470e44
021311114a5b0335207f7c167f22001b44520c15544801125d40
06140611460c26243c7f5c167f3d015446010053005907145d44
0f05110d160f263f3a7f4210372c03111313090415481d49530f
上述的每一个字符串 $C_i$，都是某个 key 异或上明文 $M_i$ 得到的。我们的目标是获取这个 key. 已知明文是英文句子。
回顾异或运算的性质：结合律、交换律、逆元为其自身。这是非常好的性质，然而也为攻击者提供了方便。因为：$$C_1 \oplus C_2 = (M_1 \oplus key) \oplus (M_2 \oplus key) = M_1 \oplus M_2$$
这表明，两个密文的异或，就等于对应明文的异或。这是很危险的性质，高明的攻击者可以通过频率分析，来破译这些密文。我们来看字符串 $C_1$ 异或上其他密文会得到什么东西。以下只保留了英文字符，其余字符以 “.” 代替。
....S....N.U.....A..M.N...
...Ro..I...I....SE....P.I.
.E..H...IN..H...........TU
..A.H.R.....E....P......E.
...RT...E...M....M....A.L.
d...V..I..DNEt........K.DU
.......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 \oplus y$ 得到一个英文字母，那么 $x, y$ 中的某一个有很大概率是空格。再来回头看上面 $C_1$ xor 其他密文——也就等于 $M_1$ xor 其他明文的表，如果第 $col$ 列存在大量的英文字母，我们可以猜测 $M_1[col]$ 是一个空格。那一列英文字母越多，把握越大。
知道 $M_1$ 的 $col$ 位是空格有什么用呢？别忘了异或运算下，$x$ 的逆元是其自身。所以$$M_i[col] = M_1[col] \oplus M_i[col] \oplus M_1[col] = M_1[col] \oplus M_i[col] \oplus \text{0x20}$$
于是，只要知道某个字符串的某一位是空格，我们就可以恢复出所有明文在这一列的值。
攻击
攻击过程显而易见：对于每一条密文$C_i$，拿去异或其他所有密文。然后去数每一列有多少个英文字符，作为“$M_i$在这一位是空格”的评分。
上面的事情做完时候，依据评分从大到小排序，依次利用 “某个明文的某一位是空格” 这种信息恢复出所有明文的那一列。如果产生冲突，则舍弃掉评分小的。不难写出代码：
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(' ')
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)
print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))
执行代码，得到的结果是：
Dear Friend, T%is tim< I u
nderstood my m$stake 8nd u
sed One time p,d encr ptio
n scheme, I he,rd tha- it
is the only en.ryptio7 met
hod that is ma9hemati:ally
proven to be #ot cra:ked
ever if the ke4 is ke)t se
cure, Let Me k#ow if ou a
gree with me t" use t1is e
ncryption sche e alwa s...显然这不是最终结果，我们得修正几项。把 "k#now" 修复成 "know"，把 "alwa s" 修复成 "always". 代码如下：
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)
know(10, 21, 'y')
know(8, 14, 'n')
print('\n'.join([''.join([chr(c) for c in x]) for x in msg]))结果得到：
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... 我们成功恢复了明文！那么 key 也很好取得了：把 $C_1$ 异或上 $M_1$ 即可。
key = xo.strxor(c[0], ''.join([chr(c) for c in msg[0]]).encode())
print(key)
# b'afctf{OPT_1s_Int3rest1ng}!'结论
Many-Time-Pad 是不安全的。我们这一次的攻击，条件稍微有点苛刻：明文必须是英文句子、截获到的密文必须足够多。但是只要攻击者有足够的耐心进行词频分析、监听大量密文，还是能够发起极具威胁性的攻击。如果铁了心要用直接xor来加密信息，应当采用一次一密(One-Time-Pad).
完整的解题脚本如下：
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)BUUCTF: [De1CTF2019]xorz
【附件】
给的是 $m[i] \oplus k[i] \oplus s[i]$, 其中 $s$ 已知，故实际上我们拿到了 $m[i] \oplus k[i]$. 在这里 $k$ 是有周期的，且周期不超过38。如果知道了 $k$ 的周期，那么用 Many-Time-Pad 就可以成功攻击。由于 len(key) 并不大，从大到小枚举 len(key)，肉眼判断是否为flag即可。最后发现 len(key)=30 是满足要求的。
from itertools import cycle
import codecs, numpy as np
import Crypto.Util.strxor as xo
salt="WeAreDe1taTeam"
si=cycle(salt)
c = codecs.decode('49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c', 'hex')
a = [r ^ ord(next(si)) for r in c] # a[i] = m[i] ^ k[i]
def div(sz):
ret = [''.join([chr(ch) for ch in a[i*sz : (i+1)*sz]]).encode() for i in range(len(a)//sz)]
# if len(a) % sz != 0:
# ret.append(a[len(a)//sz*sz:])
print('\n'.join(map(lambda x:codecs.encode(x, 'hex').decode(), ret)))
return ret
sz = 30
t = div(sz)➜ workspace python3 work.py > out.txt
➜ workspace python3 mtp.py
In faith I do not love thee wi
th mine eyes,For they in thee
a thousand errors note;But `ti
s my heart that loves what the
y despise,Who in despite of vi
ew is pleased to dote.Nor are
mine ears with thy tongue`s tu
ne delighted;Nor tender feelin
g to base touches prone,Nor ta
ste, nor smell, desire to be i
nvitedTo any sensual feast wit
h thee alone.But my five wits,
nor my five senses canDissuad
e one foolish heart from servi
ng thee,Who leaves unswayed th
e likeness of a man,Thy proud
heart`s slave and vassal wretc
h to be.Only my plague thus fa
r I count my gain,That she tha
t makes me sin awards me pain.
b'W3lc0m3tOjo1nu55un1ojOt3m0cl3W'