rand

点击此处获得更好的阅读体验


WriteUp来源

本WP由Vanish提供

题目考点

  • MT19937预测key

解题思路

啊,一道憨憨题,mt19937都快给玩烂了。而且这还是最最简单的预测,直接套上现成的工具就能解key。至于后面的一个只给了加密函数没给解密函数用的feistel的密码,可能是DES吧,没细看。直接把密钥流反过来,用他给的加密函数来解密就好了。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import random

class MT19937Recover:
"""Reverses the Mersenne Twister based on 624 observed outputs.

The internal state of a Mersenne Twister can be recovered by observing
624 generated outputs of it. However, if those are not directly
observed following a twist, another output is required to restore the
internal index.

See also https://en.wikipedia.org/wiki/Mersenne_Twister#Pseudocode .

"""
def unshiftRight(self, x, shift):
res = x
for i in range(32):
res = x ^ res >> shift
return res

def unshiftLeft(self, x, shift, mask):
res = x
for i in range(32):
res = x ^ (res << shift & mask)
return res

def untemper(self, v):
""" Reverses the tempering which is applied to outputs of MT19937 """

v = self.unshiftRight(v, 18)
v = self.unshiftLeft(v, 15, 0xefc60000)
v = self.unshiftLeft(v, 7, 0x9d2c5680)
v = self.unshiftRight(v, 11)
return v

def go(self, outputs, forward=True):
"""Reverses the Mersenne Twister based on 624 observed values.

Args:
outputs (List[int]): list of >= 624 observed outputs from the PRNG.
However, >= 625 outputs are required to correctly recover
the internal index.
forward (bool): Forward internal state until all observed outputs
are generated.

Returns:
Returns a random.Random() object.
"""

result_state = None

assert len(outputs) >= 624 # need at least 624 values

ivals = []
for i in range(624):
ivals.append(self.untemper(outputs[i]))

if len(outputs) >= 625:
# We have additional outputs and can correctly
# recover the internal index by bruteforce
challenge = outputs[624]
for i in range(1, 626):
state = (3, tuple(ivals+[i]), None)
r = random.Random()
r.setstate(state)

if challenge == r.getrandbits(32):
result_state = state
break
else:
# With only 624 outputs we assume they were the first observed 624
# outputs after a twist --> we set the internal index to 624.
result_state = (3, tuple(ivals+[624]), None)
rand = random.Random()
rand.setstate(result_state)

if forward:
for i in range(624, len(outputs)):
assert rand.getrandbits(32) == outputs[i]

return rand

def test_PythonMT19937Recover():
"""Just a testcase to ensure correctness"""
mtb = MT19937Recover()

#r1 = random.Random(0x31337)

# just some discarded random numbers to move internal state forward
#[r1.getrandbits(32) for _ in range(1234)]

# the actual leak of 1000 values
#n = [r1.getrandbits(32) for _ in range(1000)]
with open ("random") as f:
nn= f.read().split("\n")
print(nn)
n = [int(_) for _ in nn[:-1]]
r2 = mtb.go(n)
print (r2.getrandbits(32))

#assert r1.getrandbits(32) == r2.getrandbits(32)

test_PythonMT19937Recover()

拿到key,改加密函数,解密得到flag

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
# -*- coding: utf-8 -*-
import base64
import random

flag = "flag{************************************}"

hexadecimalcontrast = {
'0': '0000',
'1': '0001',
'2': '0010',
'3': '0011',
'4': '0100',
'5': '0101',
'6': '0110',
'7': '0111',
'8': '1000',
'9': '1001',
'a': '1010',
'b': '1011',
'c': '1100',
'd': '1101',
'e': '1110',
'f': '1111',
}
IP = [58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7]
IP_1 = [40, 8, 48, 16, 56, 24, 64, 32,
39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30,
37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28,
35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26,
33, 1, 41, 9, 49, 17, 57, 25]
E = [32, 1, 2, 3, 4, 5,
4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13,
12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21,
20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29,
28, 29, 30, 31, 32, 1]
S = [[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9, ],
[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12, ],
[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13, ],
[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14, ],
[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3, ],
[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13, ],
[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12, ],
[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11, ]]
PC_1 = [57, 49, 41, 33, 25, 17, 9, 1,
58, 50, 42, 34, 26, 18, 10, 2,
59, 51, 43, 35, 27, 19, 11, 3,
60, 52, 44, 36, 63, 55, 47, 39,
31, 23, 15, 7, 62, 54, 46, 38,
30, 22, 14, 6, 61, 53, 45, 37,
29, 21, 13, 5, 28, 20, 12, 4, ]
PC_2 = [14, 17, 11, 24, 1, 5, 3, 28,
15, 6, 21, 10, 23, 19, 12, 4,
26, 8, 16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55, 30, 40,
51, 45, 33, 48, 44, 49, 39, 56,
34, 53, 46, 42, 50, 36, 29, 32, ]
P = [16, 7, 20, 21,
29, 12, 28, 17,
1, 15, 23, 26,
5, 18, 31, 10,
2, 8, 24, 14,
32, 27, 3, 9,
19, 13, 30, 6,
22, 11, 4, 25, ]
movnum = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]

def HexToBin(string):
"Convert sixteen to binary"

Binstring = ""
string = string.lower()
for i in string:
try:
Binstring += hexadecimalcontrast[i]
except:
return -1
return Binstring

def BinToStr(strbin):
"Turn the binary string to a ASCII string"

strten = ""
for i in range(len(strbin) // 8):
num = 0
test = strbin[i * 8:i * 8 + 8]
for j in range(8):
num += int(test[j]) * (2**(7 - j))
strten += chr(num)
return strten

def StrToHex(string):
"Converts a string to HEX"

hexStr = ''
for i in string:
tmp = str(hex(ord(i)))
if len(tmp) == 3:
hexStr += tmp.replace('0x', '0')
else:
hexStr += tmp.replace('0x', '')
return hexStr

def Binxor(string1, string2):
"If the length is different, only the short one is returned."

strlen = 0
xorstr = ""
if len(string1) > len(string2):
strlen = len(string2)
else:
strlen = len(string1)
for i in range(strlen):
if string1[i] == string2[i]:
xorstr += '0'
else:
xorstr += '1'
return xorstr

def SubstitutionBox(keyfield, sub):

newkeyfield = ''
for i in range(len(sub)):
newkeyfield += keyfield[sub[i] - 1]
return newkeyfield

def SubkeyGeneration(freq, C, D):

for i in range(movnum[freq]):
C = C[1:] + C[:1]
D = D[1:] + D[:1]
return C, D, SubstitutionBox(C + D, PC_2)

def enkey(secretkey):

netss = SubstitutionBox(HexToBin(StrToHex(secretkey)), PC_1)
C, D = netss[:28], netss[28:]
key = []
for i in range(16):
C, D, keyone = SubkeyGeneration(i, C, D)
key.append(keyone)
return key

def Sbox(plaintext, sub):

return HexToBin("%x" % S[sub][int(plaintext[:1] + plaintext[-1:], 2) * 16 + int(plaintext[1:-1], 2)])

def Function(plaintext, secretkey):

plaintext = Binxor(SubstitutionBox(plaintext, E),
secretkey)
sout = ''
for i in range(8):
sout += Sbox(plaintext[i * 6:(i + 1) * 6], i)
sout = SubstitutionBox(sout, P)
return sout

def endecrypt(plaintext, secretkey):

netss = SubstitutionBox(HexToBin(StrToHex(plaintext)), IP)
L, R = netss[:32], netss[32:]
for i in range(16):
L, R = R, Binxor(L, Function(R, secretkey[i]))
return SubstitutionBox(R + L, IP_1)

def encryption(plaintext, secretkey):

plaintext = plaintext + (8 - len(plaintext) % 8) * '\0'
keys = enkey(secretkey[:8])
print(keys)
ciphertext = ''
for i in range(len(plaintext) / 8):
ciphertext += endecrypt(plaintext[i * 8:(i + 1) * 8], keys)
return base64.b64encode(BinToStr(ciphertext))

def decryption(plaintext, secretkey):
plaintext = "t2GzuEfVDaJsNLBqC8N7C3/2UgIeCoQLC2qLkT1ukFULskzMc1u9QeFizVUfFYfA"
plaintext = base64.b64decode(plaintext)
print plaintext
keys = enkey(secretkey[:8])[::-1]
#print(keys)
ciphertext = ''
for i in range(len(plaintext) / 8):
ciphertext += endecrypt(plaintext[i * 8:(i + 1) * 8], keys)
return (BinToStr(ciphertext))

def generate():
fw = open("random", "w")
for i in range(700):
fw.write(str(random.getrandbits(32))+"\n")
fw.close()

generate()
f = open("flag.txt", "r")

key = str(random.getrandbits(32))
key = '2990136190'
ciphertext = decryption(flag, key)
print ciphertext

Flag