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

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.

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.

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!