PRetty stroNG - InCTF Internationals 2019


Intended solution of PRetty stroNG challenge from InCTF Internationals 2019

tl;dr

  • Recover sample outputs from PRNG
  • reverse wrapper function
  • find seed from outputs
  • get the flag

Challenge Points: 1000
Challenge Solves: 1
Challenge Author: v3ct0r

Challenge Description

pic

Introduction

You are given this challenge file and a service which hosts this.

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
#!/usr/bin/env python2
from Crypto.Cipher import AES
from Crypto.Util.number import *
from hashlib import *
import sys,random,os
from secret import FLAG,secret,messages

class PRNG(object):
def __init__(self, seed1,seed2):
self.seed1 = seed1
self.seed2 = seed2

@staticmethod
def rotl(x, k):
return ((x << k) & 0xffffffffffffffff) | (x >> 0x40 - k)

def next(self):
s0 = self.seed1
s1 = self.seed2
result = (s0 + s1) & 0xffffffffffffffff

s1 ^= s0
self.seed1 = self.rotl(s0, 0x37) ^ s1 ^ ((s1 << 0xe) & 0xffffffffffffffff)
self.seed2 = self.rotl(s1, 0x24)

return result


def left_right(num):
num = (((num & 2863311530) >> 1) | ((num & 1431655765) << 1))
num = (((num & 3435973836) >> 2) | ((num & 858993459) << 2))
num = (((num & 4042322160) >> 4) | ((num & 252645135) << 4))
num = (((num & 4278255360) >> 8) | ((num & 16711935) << 8))
return((num >> 16) | (num << 16))


def wrapper(x):
a = left_right(x/(2**32))
b = left_right(x%(2**32))
return (a << 64) + b


def Encryption_Box(message):
m = bytes_to_long(message)
h = pow(g, secret, p)
y = wrapper(gen.next())
c1 = pow(g, y, p)
s = pow(h,y,p)
c2 = (m*s) % p
return hex(c1),hex(c2)

def Decryption_Box(c1,c2):
s = pow(c1,secret,p)
m = (c2*inverse(s,p))%p
message = long_to_bytes(m)
if message in messages:
return message
return "Nice Try!"

def Super_Encrypion_Box(key):
key = sha256(long_to_bytes(key)).digest()
aes = AES.new(key,AES.MODE_CBC,md5(key).digest())
ct = aes.encrypt(FLAG)
return ct.encode('hex')


if __name__=="__main__":

g = 2
p = 7199773997391911030609999317773941274322764333428698921736339643928346453700085358802973900485592910475480089726140708102474957429903531369589969318716771
seed1 = bytes_to_long(os.urandom(8))
seed2 = bytes_to_long(os.urandom(8))
gen = PRNG(seed1,seed2)

print "[1] Encryption Box"
print "[2] Super Encryption Box"
print "[3] Decryption Box"
print "[4] Exit"

for _ in range(30):
try:
ch = int(raw_input('Enter option > '))
except:
print "Error!"
sys.exit()
if ch == 1:
random.shuffle(messages)
print "Here is your Encrypted Message:", Encryption_Box(messages[0])
elif ch == 2:
print "Here is your flag:", Super_Encrypion_Box(gen.next())
elif ch == 3:
try:
c1 = raw_input("Enter first ciphertext c1 (in hex): ")
c2 = raw_input("Enter second ciphertext c2 (in hex): ")
c1 = int(c1,16)
c2 = int(c2,16)
print "Here is your message:", Decryption_Box(c1,c2)
except:
print "Wrong Input !!"
sys.exit()
elif ch == 4:
print "Bye!"
sys.exit()
else:
print "Error!"
sys.exit()

As you can see that there are 4 options, lets see what they do.

  1. It justs encrypt random messages with the elgamal Encryption
  2. Encrypts the flag using key and iv derived from the
  3. Decrypts the message encrypted in 1.
  4. Exits from service

Writeup

At first look there doesn’t seem any use for the 1st and 3rd option. But we’ll get to that part. First what we need is a few samples of the output generated by the PRNG, thats where the option 1 comes into play. If you look at the function Encryption_Box you will see that we have used the PRNG to generate the random ephemeral key (y). But how do we get it.

The only way to get that is to solve the DLP. Lets try out various attacks. First lets examine the prime. After factoring the order of the group i.e. p-1 you will see that it has many factors. This gives way for us to use pohlig hellman, and soon enough it works. Now lets move on to the next step.

Seems that the actual value is passed inside the wrapped function, i.e. the value of we got by solving DLP is the output of the wrapper function. So lets reverse the function. And by reverse I mean literally reverse, what the function left_right does is that it reverses the bits of its inputs (it may add some bits at the end but input can be easily recovered by ignoring the other bits). The rest is easy. Now that you have got the values what to do now.

The PRNG we used here is a well known random generator called Xoroshiro128+. But it had a vulnerability that you can predict the seed using few outputs. There are few resources available to know more about them. After we get the seed its only a matter of time to get the key with which the flag was encrypted.

Here is the exploit script.

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
from Crypto.Util.number import *
from pwn import *
from hashlib import *
from Crypto.Cipher import AES
import z3


def sym_xoroshiro128plus(solver, sym_s0, sym_s1, mask, result):
s0 = sym_s0
s1 = sym_s1
sym_r = (sym_s0 + sym_s1)

condition = z3.Bool('c0x%0.16x' % result)
solver.add(z3.Implies(condition, (sym_r & mask) == result & mask))

s1 ^= s0
sym_s0 = z3.RotateLeft(s0, 55) ^ s1 ^ (s1 << 14)
sym_s1 = z3.RotateLeft(s1, 36)

return sym_s0, sym_s1, condition

def find_seed(results_with_masks):
start_s0, start_s1 = z3.BitVecs('start_s0 start_s1', 64)
sym_s0 = start_s0
sym_s1 = start_s1
solver = z3.Solver()
conditions = []

for result, mask in results_with_masks:
sym_s0, sym_s1, condition = sym_xoroshiro128plus(solver, sym_s0, sym_s1, mask, result)
conditions.append(condition)

if solver.check(conditions) == z3.sat:
model = solver.model()

return (model[start_s0].as_long(), model[start_s1].as_long())

else:
return None

class PRNG(object):
def __init__(self, seed1,seed2):
self.seed1 = seed1
self.seed2 = seed2

@staticmethod
def rotl(x, k):
return ((x << k) & 0xffffffffffffffff) | (x >> 64 - k)

def next(self):
s0 = self.seed1
s1 = self.seed2
result = (s0 + s1) & 0xffffffffffffffff

s1 ^= s0
self.seed1 = self.rotl(s0, 55) ^ s1 ^ ((s1 << 14) & 0xffffffffffffffff)
self.seed2 = self.rotl(s1, 36)

return result

def crt(list_a, list_m):
try:
assert len(list_a) == len(list_m)
except:
print "[+] Length of list_a should be equal to length of list_m"
return -1
for i in range(len(list_m)):
for j in range(len(list_m)):
if GCD(list_m[i], list_m[j])!= 1 and i!=j:
print "[+] Moduli should be pairwise co-prime"
return -1
M = 1
for i in list_m:
M *= i
list_b = [M/i for i in list_m]
assert len(list_b) == len(list_m)
try:
assert [GCD(list_b[i], list_m[i]) == 1 for i in range(len(list_m))]
list_b_inv = [int(inverse(list_b[i], list_m[i])) for i in range(len(list_m))]
except:
print "[+] Encountered an unusual error while calculating inverse using gmpy2.invert()"
return -1
x = 0
for i in range(len(list_m)):
x += list_a[i]*list_b[i]*list_b_inv[i]
return x % M



def brute_dlp(g,a,p):
x=1
while(True):
if pow(g,x,p)==a:
return x
else:
x+=1

def pohlig_hellman_pp(g, y, p, q, e):
try:
# Assume q is a factor of p-1
assert (p-1) % q == 0
except:
print "[-] Error! q**e not a factor of p-1"
return -1

# a = a_0*(q**0) + a_1*(q**1) + a_2*(q**2) + ... + a_(e-1)*(q**(e-1)) + s*(q**e)
# where a_0, a_1, a_2, ..., a_(e-1) belong to {0,1,...,q-1} and s is some integer
a = 0

b_j = y
alpha = pow(g, (p-1)/q, p)
for j in range(e):
y_i = pow(b_j, (p-1)/(q**(j+1)), p)
a_j = brute_dlp(alpha, y_i, p)
#assert a_j >= 0 and a_j <= q-1
a += a_j*(q**j)

multiplier = pow(g, a_j*(q**j), p)
assert GCD(multiplier, p) == 1
b_j = (b_j * inverse(multiplier, p)) % p
return a

def pohlig_hellman(g, y, p, list_q, list_e):
x_list = [pohlig_hellman_pp(g, y, p, list_q[i], list_e[i]) for i in range(len(list_q))]
mod_list = [list_q[i]**list_e[i] for i in range(len(list_q))]
return crt(x_list, mod_list)


def left_right(num):
num = (((num & 2863311530) >> 1) | ((num & 1431655765) << 1))
num = (((num & 3435973836) >> 2) | ((num & 858993459) << 2))
num = (((num & 4042322160) >> 4) | ((num & 252645135) << 4))
num = (((num & 4278255360) >> 8) | ((num & 16711935) << 8))
return((num >> 16) | (num << 16))

def fix1(x):
b = bin(x)[2:][::-1]
flag = True
i =32
while(flag):
ans = int(b[:i],2)
if left_right(ans)==x:
return ans
i+=1


def exploit(a):
ph = pohlig_hellman(g,a,p,x,y)
assert pow(g,ph,p)==a
a = ph/(2**64)
b = ph%(2**64)
a = fix1(a)
b = fix1(b)
ran = (a << 32) + b
return ran


def decrypt(ct,key):
key = sha256(long_to_bytes(key)).digest()
aes = AES.new(key,AES.MODE_CBC,md5(key).digest())
ct = aes.decrypt(ct.decode('hex'))
return ct


def decrypt_from_seed(seed):
genr = PRNG(seed[0],seed[1])
for i in range(7):
key = genr.next()
flag = decrypt(fl,key)
if 'inctf' in flag:
return flag

def create_list(l):
lis = []
for i in l:
lis.append((i,0xffffffffffffffff))
return lis

if __name__ == "__main__":

g = 2
p = 7199773997391911030609999317773941274322764333428698921736339643928346453700085358802973900485592910475480089726140708102474957429903531369589969318716771L
x = [2, 5, 109, 7963, 8539, 20641, 38833, 39341, 46337, 51977, 54319, 57529]
y = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]



io = remote('18.218.190.20',3197)
lis = []
print io.recv()
if io.can_recv():
io.recv()
io.recvuntil("> ")
for i in range(6):
io.sendline('1')
s = io.recvuntil('> ').split()
so=s[5].split("'")
c1 = eval(so[1])
exp = exploit(c1)
print exp
lis.append(exp)
io.sendline('2')
io.recvuntil('flag:')
fg = io.recv().split()
fl = fg[0]
sed = find_seed(create_list(lis[:5]))
print decrypt_from_seed(sed)

Running this script will give us: inctf{PRNG_n0t_t00_57r0ng_4_y0u}

In case of any query, feedback or suggestion, feel free to comment or reach me out on Twitter!