Many time pad attack

前言

看到了 2020HGAME week1 里的一道题,随手复现一下

题目

懒得搭docker部署服务器了,就自己写个函数调用着假装交互

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import os
import random
import string
import binascii
import base64
from flag import flag
flag = flag.encode()
assert flag.startswith(b'flag{') and flag.endswith(b'}')

flag_len = len(flag)

def xor(s1, s2):
#assert len(s1)==len(s2)
return bytes(map((lambda x: x[0] ^ x[1]), zip(s1, s2)))

def get_data():
random.seed(os.urandom(8))
keystream = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(flag_len)])
keystream = keystream.encode()
return base64.b64encode(xor(flag, keystream)).decode()

分析

题目使用与flag等长的key与其异或并且交给我们,而想要知道key显然是不可能的,(除非你脸够欧),所以我们就要从异或这一算法下手,我们知道flag是以flag{开头,而异或所能够得到的结果终究是个很小的有限集,所以我们可以通过足够多的结果来不断缩小这一集,进而达到找到原文的效果。

举个例子:flag的第一位f,某次我们得到密文的第一位为7,通过枚举我们可以知道7 = a ^ V = b ^ U = c ^ T = d ^ S = f ^ Q ......,显然这个集是比较大的,而对于每一个密文,我们都可以得到一个可能的集,通过不断地获取密文并取交集,就能很快的得到原来的明文,但是必须保证flag中的所有字符在脚本中的table里包含,不然会跑不出交集的,(你都没有我从哪里给你搞出来啊)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import os
import random
import string
import binascii
import base64
from flag import flag
flag = flag.encode()
assert flag.startswith(b'flag{') and flag.endswith(b'}')

flag_len = len(flag)

def xor(s1, s2):
#assert len(s1)==len(s2)
return bytes(map((lambda x: x[0] ^ x[1]), zip(s1, s2)))

def get_data():
random.seed(os.urandom(8))
keystream = ''.join([random.choice(string.ascii_letters+string.digits) for _ in range(flag_len)])
keystream = keystream.encode()
return base64.b64encode(xor(flag, keystream)).decode()

clist = []
for i in range(1000):
c = get_data()
c = base64.b64decode(c)
clist.append(c)
print('Data ready!')

table = b'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}-_!@#$%^&*()=+|'
# {}-_!@#$%^&*()=+|

def getdir(x):
dic = ''
length = len(table)
for i in range(0,length):
for j in range(i,length):
if(x == (table[i] ^ table[j])):
dic += chr(table[i]) + chr(table[j])
return dic

def sol(a,b):
ans = ''
for i in range(0,len(a)):
for j in range(0,len(b)):
if(a[i] == b[j] and ans.find(a[i]) == -1):
ans += a[i]
return ans


for i in range(0,len(clist[0])):
res = sol(getdir(clist[0][i]),getdir(clist[1][i]))
for j in range(2,len(clist)):
res = sol(getdir(clist[j][i]),res)
if(len(res)==0):
print('Table is too small!')
elif(len(res)>1):
print('Data is too little!')
else:
print(res,end = '')