PRetty stroNG - InCTF Internationals 2019
I created a challenge for this year's InCTF International. Its based on a PRNG called Xoroshiro128+.
Intended solution of PRetty stroNG challenge from InCTF Internationals 2019
Challenge Points: 1000
Challenge Solves: 1
Challenge Author: v3ct0r
Introduction
You are given this challenge file and a service which hosts this.
#!/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.
- It justs encrypt random messages with the elgamal Encryption
- Encrypts the flag using key and iv derived from the
- Decrypts the message encrypted in 1.
- 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.
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!
Cyber Security Enthusiast, Cryptography and Cryptanalysis with @teambi0s . Love what I do ;)