MTU攻击

以简单异或实现的流密码，如果不能保证一次一密，则是不安全的。本文展示了多次加密采用同一个密钥的情形，此时从密文可能推断出明文和密钥。

在Alice和Bob之间传送消息—— Alice 造一个比较长的密钥，然后用非常秘密的方式告诉 Bob. 接下来，Alice 每次向 Bob 发送信息，都把明文异或上这个约定好的字符串；Bob 收到信息之后，把密文异或上 key, 于是就可以拿到明文。整个过程只需要传送一次密钥，这种方式称为 **Many-Time-Pad (MTP)**。

但上述的MTP方法是不安全，只要截获了足够多的密文，就能推断出明文，进而拿到密钥。这是由于异或运算的性质带来的。

Demo

BUUCTF: [AFCTF2018]你听过一次一密么？

(原题有bug, 笔者有少量改动)
25030206463d3d393131555f7f1d061d4052111a19544e2e5d54
0f020606150f203f307f5c0a7f24070747130e16545000035d54
1203075429152a7020365c167f390f1013170b1006481e13144e
0f4610170e1e2235787f7853372c0f065752111b15454e0e0901
081543000e1e6f3f3a3348533a270d064a02111a1b5f4e0a1855
0909075412132e247436425332281a1c561f04071d520f0b1158
4116111b101e2170203011113a69001b47520601155205021901
041006064612297020375453342c17545a01451811411a470e44
021311114a5b0335207f7c167f22001b44520c15544801125d40
06140611460c26243c7f5c167f3d015446010053005907145d44
0f05110d160f263f3a7f4210372c03111313090415481d49530f

上面的每个字符串都是明文异或上密钥key得到的密文。
$$
交换律
结合律 (a ⊕ b ) ⊕ c = a⊕ ( b ⊕ c)\
任何数 x ⊕ x = 0 x ⊕ 0 = X\
自反性 x ⊕ b ⊕ b = x ⊕ 0 = x
$$
两个密文的异或就等于两个明文的异或

Ascii表

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

得到规律：小写字母异或上空格为对应的大写字母，大写字母异或空格就会得到对应的小写字母

所以，如果 $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.text', '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...

对结果修正一下

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值

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

得到flag

b'afctf{OPT_1s_Int3rest1ng}!'

打赏