Pwn2Win 2021 - Lost Exponent
Challenge Description
Lost Exponent - ppc, misc - 253 ptsWhile Laura was looking for her brother, she found a program that seems to scramble a password and save the result. Could you help her find the original password so that she can find and save her brother before it's too late?
Writeup
First Look
The attachment contain 2 files: a python script
encode.py to encode (or encrypt, if I may) the flag, and the 17MB encrypted flag enc. In this script, it imports 2 variables: e and flag which we didn't have access to.1
from math import sqrt
2
from random import seed, shuffle
3
from lost import e, flag
4
from itertools import product
5
from numpy import sign, diff
6
7
8
assert flag.startswith('CTF-BR{')
9
seed(6174)
10
n = int(sqrt(len(flag))) + 2
11
order = list(product(range(n), repeat=2))
12
shuffle(order)
13
order.sort(key=(lambda x: sign(diff(x))))
14
15
16
class Matrix:
17
def __init__(self):
18
self.n = n
19
self.m = [[0]*n for _ in range(n)]
20
21
def __iter__(self):
22
for i in range(self.n):
23
for j in range(self.n):
24
yield self.m[i][j]
25
26
def I(self):
27
r = Matrix()
28
for i in range(n):
29
r[i, i] = 1
30
return r
31
32
def __setitem__(self, key, value):
33
self.m[key[0]][key[1]] = value
34
35
def __getitem__(self, key):
36
return self.m[key[0]][key[1]]
37
38
def __mul__(self, other):
39
r = Matrix()
40
for i in range(n):
41
for j in range(n):
42
r[i, j] = sum(self[i, k]*other[k, j] for k in range(n))
43
return r
44
45
def __pow__(self, power):
46
r = self.I()
47
for _ in range(power):
48
r = r * self
49
return r
50
51
def __str__(self):
52
return str(self.m)
53
54
55
if __name__ == '__main__':
56
m = Matrix()
57
for i, f in zip(order, flag):
58
m[i] = ord(f)
59
cflag = list(map(str, m ** e))
60
mn = max(map(len, cflag))
61
mn += mn % 2
62
cflag = ''.join(b.zfill(mn) for b in cflag)
63
cflag = bytes([int(cflag[i:i+2]) for i in range(0, len(cflag), 2)])
64
65
with open('enc', 'wb') as out:
66
out.write(cflag)
Copied!
The code is fairly simple. It randomly scramble the flag and represent it into a matrix, then it will do matrix exponentiation of this matrix with
e, flatten the resulting matrix and write it into a file.However, since the seed (6174) is given, the scramble is not purely random and we can determine the order by following the script. Unfortunately, the order is derived from the flag's length (which we didn't know at this point). So we need to find the length before we can continue.
1
seed(6174)
2
n = int(sqrt(len(flag))) + 2
3
order = list(product(range(n), repeat=2))
4
shuffle(order)
5
order.sort(key=(lambda x: sign(diff(x))))
Copied!
Finding the Flag's Length
There are several ways to find the length, one way is to guess from the resulting file. From the script: after the matrix undergoes exponentiations, it will stringify all the numbers inside the matrix and
zfill (prepend zeroes) them so all numbers have same length.1
m = Matrix()
2
for i, f in zip(order, flag):
3
m[i] = ord(f)
4
cflag = list(map(str, m ** e))
5
mn = max(map(len, cflag))
6
mn += mn % 2
7
cflag = ''.join(b.zfill(mn) for b in cflag)
8
cflag = bytes([int(cflag[i:i+2]) for i in range(0, len(cflag), 2)])
Copied!
From this characteristic, we can guess that most of the resulting numbers should have zeroes prefix (only few will have non-zeroes prefix). The resulting line of numbers should be like this:
1
000000...1234
2
000000...1337
3
000023...3456
4
000000...0000 // some line may contain only zeros
5
000000...1321
6
123131...4131 // the max length
7
002512...1231
8
000000...0000
9
... // and so on
Copied!
By analyzing the location of long zeroes inside
enc, we may be able to guess mn (the length of every number in the matrix).First, let's change
enc representation from bytes into string:1
def change_into_string():
2
bytes = []
3
with open('enc', 'rb') as enc:
4
bytes = enc.read()
5
digits = [str(b).zfill(2) for b in bytes]
6
digits = ''.join(digits)
7
with open('enc.string', 'w') as f:
8
f.write(digits)
Copied!
Running the above function will result to a file with double the size of
enc. Which is expected, since we change each byte representation into 2 chars (1 char is 1 byte).1
❯ ls -l
2
-rw-r--r-- 1 adam staff 35091252 May 29 22:14 enc.string
3
[email protected] 1 adam staff 17545626 May 29 22:13 enc
4
[email protected] 1 adam staff 2548 May 29 20:55 encode.py
Copied!
We can also analyze possibilities of
mn by viewing the matrix characteristic:- Remember that all numbers in the matrix have length
mn. That means the size ofenc(size) should be divisible bymn. Therefore,mnshould be a factor ofsize. - The matrix is square, so the number of its element should be a square number. That means
size / mnshould be a square number. - Assume flag's length should be within
6 <= len(flag) <= 100.
From these characteristics, we can have potential candidates of
mn:1
def get_mn(size):
2
factors = sorted(list(get_factors(size)))
3
candidates_mn = []
4
for f in factors:
5
line = size / f
6
if math.sqrt(line).is_integer():
7
candidates_mn.append(f)
8
9
for mn in candidates_mn:
10
print('---')
11
print('mn:', mn)
12
print('lines:', f / mn)
13
print('n:', math.sqrt(f / mn))
14
print('flag:', (math.sqrt(f / mn) - 2) ** 2)
15
16
get_mn(35091252)
17
18
'''
19
output:
20
---
21
mn: 716148
22
lines: 49.0
23
n: 7.0
24
flag: 25.0
25
---
26
mn: 974757
27
lines: 36.0
28
n: 6.0
29
flag: 16.0
30
---
31
'''
Copied!
At this point, there are 2 possibilities, whether the flag length is 25 or 16, both sound equally probable. So next, we can analyze the long-zeroes location inside
enc. In order to do this, we can use this script:1
digits = open('enc.string', 'r').read()
2
3
start_i = None
4
i = 0
5
while i < len(digits):
6
if digits[i:i+16] == '0' * 16:
7
if start_i is None:
8
start_i = i
9
if digits[i] != '0':
10
if start_i is not None:
11
print(start_i, i) # print long-zeroes location
12
start_i = None
13
i += 1
14
15
'''
16
output:
17
0 141963
18
716148 5154999
19
5729183 10168035
20
10742217 15163599
21
15755255 15879749
22
16471404 16595897
23
17187552 17312045
24
17903700 20052146
25
23632884 25065181
26
28645913 28686627
27
29362068 30078217
28
33658956 33699663
29
34375104 34514009
30
'''
Copied!
Basically, by manual analysis, we decide that it is more probable that the flag length is 25, since the long-zeroes location if the flag length is 16 make the challenge unsolvable.
To help us analyze further, let's split the
enc.string to multiple files.1
mn = 716148
2
3
digits = open('enc.string', 'r').read()
4
5
for i in range(49):
6
bytes = digits[mn*mn*(i+1)]
7
open(f'output/{i}.txt','w').write(bytes)
Copied!
Constructing the matrix order
Now that we know the flag length, we can determine the
order. Next, let's visualize the matrix. We know that the first 7 chars of flag is CTF-BR{ and the 25th char is }1
from math import sqrt
2
from random import seed, shuffle
3
from itertools import product
4
from numpy import sign, diff
5
6
flag = 'CTF-BR{??????????????????}'
7
8
seed(6174)
9
n = int(sqrt(len(flag))) + 2
10
order = list(product(range(n), repeat=2))
11
shuffle(order)
12
order.sort(key=(lambda x: sign(diff(x))))
13
14
m = [['.']*n for _ in range(n)]
15
for i, f in zip(order, flag):
16
m[i[0]][i[1]] = f
17
18
for row in m:
19
print(' '.join(row))
20
21
'''
22
output:
23
24
? . . . . . .
25
? . . . . . .
26
- B . . . . .
27
? { ? ? . . .
28
T ? ? ? } . .
29
R ? ? C ? ? .
30
F ? ? ? ? ? ?
31
32
'''
Copied!
Finding the exponent "e"
Looking at the matrix, there is a notable finding there: the location of
} which is (4, 4). If we do exponentiation to the matrix by e. The values of index (4, 4) is ord('}') ** e. With this, we can quickly brute force the value of e. Note that the last 32 digits of values inside cell (5, 5) in enc is 92880428233183920383453369140625.1
e = 1
2
while e := e + 1:
3
if pow(ord('}'), e, 10 ** 32) == 92880428233183920383453369140625:
4
print('FOUND:', e)
5
break
6
7
'''
8
❯ python3 find_e.py
9
FOUND: 341524
10
'''
Copied!
Finding the Flag
Now that we find the
e. We can slowly craft the flag from our matrix. The idea is to find the ? value from matrix diagonal. After that, for each line, slowly move left to get find ? value. There may be an automated way to get this flag, but I do the calculation manually using the program below:1
import string
2
3
e = 341524
4
# flag = 'CTF-BR{abcdefghijklmnopqr}'
5
__flag = 'CTF-BR{s0M3_0F_m47r1X_106}'
6
MOD = 10 ** 32
7
8
A = ord('s')
9
B = ord('0')
10
C = ord('M')
11
D = ord('3')
12
E = ord('_')
13
F = ord('0')
14
G = ord('F')
15
H = ord('_')
16
I = ord('m')
17
18
19
L = ord('r')
20
M = ord('1')
21
N = ord('X')
22
O = ord('_')
23
P = ord('1')
24
Q = ord('0')
25
R = ord('6')
26
27
28
def q():
29
target = int(open('numbers/0.txt', 'r').read()[-32:])
30
for c in string.printable:
31
v = pow(ord(c), e, 10 ** 32)
32
if int(str(v)[:32]) == target:
33
print('FOUND:', c)
34
# q()
35
36
def a():
37
target = int(open('numbers/7.txt', 'r').read()[-32:])
38
for c in string.printable:
39
v = (pow(Q, e-1, 10 ** 32) * ord(c)) % MOD
40
if int(str(v)[:32]) == target:
41
print('FOUND:', c)
42
# a()
43
44
def r():
45
target = int(open('numbers/24.txt', 'r').read()[-32:])
46
for c in string.printable:
47
v = pow(ord(c), e, 10 ** 32)
48
if int(str(v)[:32]) == target:
49
print('FOUND:', c)
50
# r()
51
52
def o():
53
target = int(open('numbers/40.txt', 'r').read()[-32:])
54
print(target)
55
for c in string.printable:
56
v = pow(ord(c), e, 10 ** 32)
57
if int(str(v)[:32]) == target:
58
print('FOUND:', c)
59
60
# o()
61
62
def p():
63
target = int(open('numbers/48.txt', 'r').read()[-32:])
64
print(target)
65
for i in range(255):
66
v = pow(i, e, 10 ** 32)
67
if int(str(v)[:32]) == target:
68
print('FOUND:', chr(i))
69
# p()
70
71
def m():
72
target = int(open('numbers/23.txt', 'r').read()[-32:])
73
print(target)
74
for i in range(255):
75
v = (pow(R, e-1, 10 ** 32) * i) % MOD
76
if int(str(v)[:32]) == target:
77
print('FOUND:', chr(i))
78
# m()
79
80
def d():
81
target = int(open('numbers/31.txt', 'r').read()[-32:])
82
print(target)
83
for c in string.printable:
84
d = ord(c)
85
x = ord('}')
86
for _ in range(1, e):
87
d = ((d * R) + (x * ord(c))) % MOD
88
x = (x * ord('}')) % MOD
89
print('TRY:', c, d)
90
if d == target:
91
print('FOUND:', c)
92
# d()
93
94
def f():
95
target = int(open('numbers/39.txt', 'r').read()[-32:])
96
print(target)
97
for c in string.printable:
98
v = ord(c)
99
x = O
100
for _ in range(1, e):
101
v = ((v * ord('}')) + (x * ord(c))) % MOD
102
x = (x * O) % MOD
103
print('TRY:', c, v)
104
if v == target:
105
print('FOUND:', c)
106
# f()
107
108
def i():
109
target = int(open('numbers/21.txt', 'r').read()[-32:])
110
print(target)
111
for c in string.printable:
112
v1 = ord(c)
113
v2 = ord('{')
114
v3 = M
115
v4 = R
116
for _ in range(1, e):
117
v1 = sum([
118
v1 * Q,
119
v2 * A,
120
v3 * ord('-'),
121
v4 * ord(c)
122
]) % MOD
123
v2 = sum([
124
v3 * ord('B'),
125
v4 * ord('{')
126
]) % MOD
127
v3 = sum([
128
v4 * M,
129
]) % MOD
130
v4 = sum([
131
v4 * R
132
]) % MOD
133
print('TRY:', c, v1)
134
if v1 == target:
135
print('FOUND:', c)
136
# i()
137
138
def g():
139
target = int(open('numbers/30.txt', 'r').read()[-32:])
140
for c in string.printable:
141
v1 = ord(c)
142
v2 = D
143
v3 = ord('}')
144
for _ in range(1, e):
145
v1 = sum([
146
v2 * M,
147
v3 * ord(c),
148
]) % MOD
149
v2 = sum([
150
v2 * R,
151
v3 * D,
152
]) % MOD
153
v3 = (v3 * ord('}')) % MOD
154
155
print('TRY:', c, v1)
156
if v1 == target:
157
print('FOUND:', c)
158
# g()
159
160
def c():
161
target = int(open('numbers/29.txt', 'r').read()[-32:])
162
print(target)
163
for c in string.printable:
164
v1 = ord(c)
165
v2 = G
166
v3 = D
167
v4 = ord('}')
168
for _ in range(1, e):
169
v1 = sum([
170
v2 * ord('B'),
171
v3 * ord('{'),
172
v4 * ord(c)
173
]) % MOD
174
v2 = sum([
175
v3 * M,
176
v4 * G,
177
]) % MOD
178
v3 = sum([
179
v3 * R,
180
v4 * D,
181
]) % MOD
182
v4 = (v4 * ord('}')) % MOD
183
184
print('TRY:', c, v1)
185
if v1 == target:
186
print('FOUND:', c)
187
# c()
188
189
def h():
190
target = int(open('numbers/37.txt', 'r').read()[-32:])
191
print(target)
192
for c in string.printable:
193
v1 = O
194
v2 = F
195
v3 = ord('C')
196
v4 = ord(c)
197
for _ in range(1, e):
198
v4 = sum([
199
v3 * M,
200
v2 * G,
201
v1 * ord(c)
202
]) % MOD
203
v3 = sum([
204
v3 * R,
205
v2 * D,
206
v1 * ord('C')
207
]) % MOD
208
v2 = sum([
209
v2 * ord('}'),
210
v1 * F
211
]) % MOD
212
v1 = (v1 * O) % MOD
213
214
print('TRY:', c, v4)
215
if v4 == target:
216
print('FOUND:', c)
217
# h()
218
219
def find_l():
220
target = int(open('numbers/47.txt', 'r').read()[-32:])
221
print(target)
222
for c in string.printable:
223
v1 = P
224
v2 = ord(c)
225
for _ in range(e-1):
226
v2 = sum([
227
v2 * O,
228
v1 * ord(c)
229
]) % MOD
230
v1 = (v1 * P) % MOD
231
print('TRY:', c, v2)
232
if v2 == target:
233
print('FOUND:', c)
234
# find_l()
235
236
def find_e():
237
target = int(open('numbers/46.txt', 'r').read()[-32:])
238
print(target)
239
for c in string.printable:
240
v1 = P
241
v2 = L
242
v3 = ord(c)
243
for _ in range(e-1):
244
v3 = sum([
245
v3 * ord('}'),
246
v2 * F,
247
v1 * ord(c)
248
]) % MOD
249
v2 = sum([
250
v2 * O,
251
v1 * L
252
]) % MOD
253
v1 = (v1 * P) % MOD
254
print('TRY:', c, v3)
255
if v3 == target:
256
print('FOUND:', c)
257
258
# find_e()
259
260
261
262
def find_b():
263
target = int(open('numbers/45.txt', 'r').read()[-32:])
264
print(target)
265
for c in string.printable:
266
v1 = P
267
v2 = L
268
v3 = E
269
v4 = ord(c)
270
for _ in range(e-1):
271
v4 = sum([
272
v4 * R,
273
v3 * D,
274
v2 * ord('C'),
275
v1 * ord(c)
276
]) % MOD
277
v3 = sum([
278
v3 * ord('}'),
279
v2 * F,
280
v1 * E
281
]) % MOD
282
v2 = sum([
283
v2 * O,
284
v1 * L
285
]) % MOD
286
v1 = (v1 * P) % MOD
287
print('TRY:', c, v4)
288
if v4 == target:
289
print('FOUND:', c)
290
291
# find_b()
292
293
294
# index 44: b*m e*g l*h p*n
295
def find_n():
296
target = int(open('numbers/44.txt', 'r').read()[-32:])
297
print(target)
298
for c in string.printable:
299
v1 = P
300
v2 = L
301
v3 = E
302
v4 = B
303
v5 = ord(c)
304
for _ in range(e-1):
305
v5 = sum([
306
v4 * M,
307
v3 * G,
308
v2 * H,
309
v1 * ord(c)
310
]) % MOD
311
v4 = sum([
312
v4 * R,
313
v3 * D,
314
v2 * ord('C'),
315
v1 * B
316
]) % MOD
317
v3 = sum([
318
v3 * ord('}'),
319
v2 * F,
320
v1 * E
321
]) % MOD
322
v2 = sum([
323
v2 * O,
324
v1 * L
325
]) % MOD
326
v1 = (v1 * P) % MOD
327
print('TRY:', c, v5)
328
if v5 == target:
329
print('FOUND:', c)
330
331
# find_n()
332
333
334
# index 43: n*B b*{ e*c l*k p*j
335
def find_c_k():
336
target = int(open('numbers/43.txt', 'r').read()[-32:])
337
print(target)
338
for k in 'tT7':
339
for c in 'aA4':
340
v1 = P
341
v2 = L
342
v3 = E
343
v4 = B
344
v5 = N
345
v6 = ord(c)
346
for _ in range(e-1):
347
v6 = sum([
348
v5 * ord('B'),
349
v4 * ord('{'),
350
v3 * C,
351
v2 * ord(k),
352
v1 * ord(c)
353
]) % MOD
354
v5 = sum([
355
v4 * M,
356
v3 * G,
357
v2 * H,
358
v1 * N
359
]) % MOD
360
v4 = sum([
361
v4 * R,
362
v3 * D,
363
v2 * ord('C'),
364
v1 * B
365
]) % MOD
366
v3 = sum([
367
v3 * ord('}'),
368
v2 * F,
369
v1 * E
370
]) % MOD
371
v2 = sum([
372
v2 * O,
373
v1 * L
374
]) % MOD
375
v1 = (v1 * P) % MOD
376
print('TRY:', c, v6)
377
if v6 == target:
378
print('FOUND:', c, k)
379
380
# find_c_k()
Copied!
Flag
CTF-BR{s0M3_0F_m47r1X_106}Last modified 11mo ago