CSAW'19 CTF Quals Writeup - Fault Box

  • Monday, Sep 16, 2019
blog-image

I played the qualification round of CSAW’19 CTF with my team this weekend and wanted to share a writeup for the ‘FAULT BOX’ crypto challenge because I really enjoyed it. OSIRISLAB published all challenges on Github and you can find the code for this particular one here.

Challenge description

The challenge description doesn’t tell too much except who's fault?? and providing the server.py file and a remote server running it. Connecting to the remote server outputs this 

[youben@ym fault_box]$ nc crypto.chal.csaw.io 1001
====================================
            fault box
====================================
1. print encrypted flag
2. print encrypted fake flag
3. print encrypted fake flag (TEST)
4. encrypt
====================================

Solution

The full code of the app can be found here, I’m gonna try to explain the most important part of it so we learn how to exploit it. So the server is using RSA encryption, you can only request two operations from the first three before the key got changed, however, you can encrypt as many data as you want without the change being made, so I set the objective of getting the flag by using no more than two requests for the first three operations and encrypt as many data as we want to. The first interesting snippet of code is this: 

class incoming(socketserver.BaseRequestHandler):
    def handle(self):
        signal.alarm(300)
        random.seed(time.time())

        req = self.request
        while True:
          go(req)

The PRNG used to later generate the RSA key is seeded with a timestamp during the handling of our request, so we can have a short range (actually around a second) to bruteforce it, the time() function returns a float with 7 decimal numbers (e.g 1568465156.8100668) so every second gives 10000000 possible values, not a big deal if we minimize the computation required to check if we got the right timestamp. 

def go(req):
    r = RSA()
    p, x = gen_prime()
    q, y = gen_prime()

    r.generate(p, q)
    fake_flag = 'fake_flag{%s}' % (('%X' % y).rjust(32, '0'))

We can request both the encrypted version of the flag and the fake one and note the timestamp range during our connection then bruteforce over that range generating keys (also the value of y which is used to build the fake flag) and encrypting the fake flag and comparing it with the one we got from the server, this should work theoretically, however, it’s not cost efficient at all and would run slowly, so the trick is to find a way of making the check of our bruteforce cheaper in term of computation compared to the generation of an RSA key and the encryption of the fake flag. Since the value of y shouldn’t be that big, we can start by bruteforcing the value of y by getting the fake encrypted flag from the server then encrypting our own over and over using the unlimited encryption the server provide until it matches, then we can start bruteforcing the timestamp offline. So the first step is to bruteforce y and get the encrypted flag and range of timestamps, all this is done by the python2 code below 

import time
from pwn import *

HOST = ("crypto.chal.csaw.io", 1001)

def recv_heading(r):
    for i in range(8):
        r.recvline()

def bf_y(r, enc_fake_flag):
    print("[+] Bruteforcing y")
    y = 0
    while True:
        fake_flag = 'fake_flag{%s}' % (('%X' % y).rjust(32, '0'))
        r.sendline('4')
        # useless data
        r.recv(1024)
        r.sendline(fake_flag)
        enc_y = r.recvline().strip()
        recv_heading(r)
        if enc_y == enc_fake_flag:
            return y
        else:
            y = y + 1
            print "[+] y:%d" % y


def main():
    time_start = time.time()
    r = remote(*HOST)
    time_end = time.time()
    recv_heading(r)
    # get encrypted fake flag
    r.sendline('2')
    enc_fake_flag = r.recvline().strip()
    recv_heading(r)
    # bruteforce y
    y = bf_y(r, enc_fake_flag)
    # get encrypted flag
    r.sendline('1')
    enc_flag = r.recvline().strip()
    recv_heading(r)
    print "[+] Time interval: [%.7f, %.7f]" % (time_start, time_end)
    print "[+] Encrypted flag:", enc_flag
    print "[+] Encrypted fake flag:", enc_fake_flag
    print "[+] Y:", y
    r.close()

if __name__ == '__main__':
    main()

Part of what this script outputs is this 

[+] Time interval: [1568465156.8807663, 1568465156.9883412]
[+] Encrypted flag: 1F6F62EB628EB9DF50F78AB04473DD1ECC7E63F444BD8F29215C3B4F6F27EE652B803D3DCDD5659F22BC9C775EBDA272EB0F4787B7246258C2BB599762AFA833EA68886F96F1B49286DCF11FCCABC1906C90E56A3C83CB3184B9AE04D89AB9508CCBF3869AF43739D1E661C1DC76B48A64399DD76B559209726876FA71A42F895C555AF31E1509338EC566A2C86CA7C891495D53C2335BB10650D25700D147348BE88DEF957A15E4A6FB0C962BA73DA635D17A04FD07E346A404D84048CE101B23209D5BEDEF835732073ACF92F035B36FE33457DB9FC5B99B36A6038B28145F572DC8226D2B4984900E757A673EF35059DABA6FB9170C9E4E4257D7BEAED5D3
[+] Encrypted fake flag: 2C2D6D3192EE857BA442EF224141FFD524AC904FAB1D35719047413F9E5EF797BBCCFB97AB56C1562A3CD8A0EF043394B60136D7CE8540EE7ECFF0536F491AD3277C999046A85B7DE6F12DBE1B6DD70CA7D9EB56BB752913BC4D1F969CDF970FE1C64FA3A100042EB8B6991B4735D8DCCCFBEFD2CCA8A103EA669E763999E87421A73CA0137627663472A31C8ADC53CDF107CEFB07ED37AC170E211A6BACD54F662B5D2E9AD4428E4B3A32D343BA52D592353A34018FAE788261543D98F73B8AD46E202E6A9969E789605ACEE67EBD85B4C4451D31EDE8142F95E306A0CE27DEFCE5B9BADD3F15D9A1C28E6345B7647CC9E477B25483FCE5CBA2CA45FE8626F7
[+] Y: 167

The next step would be to use this values to start bruteforcing the timestamp, we check it by comparing the y value we got from the server and the one we got by randomizing using the timestamp as seed, there were several timestamps that pass this check, so we double checked with generating the RSA key using that timestamp and encrypting fake flag and comparing with the server value. The code to do that is provided below 

import socketserver
import random
import signal
import time
import gmpy2
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes

#FLAG = open('flag', 'r').read().strip()
ENC_FAKE_FLAG = b'2C2D6D3192EE857BA442EF224141FFD524AC904FAB1D35719047413F9E5EF797BBCCFB97AB56C1562A3CD8A0EF043394B60136D7CE8540EE7ECFF0536F491AD3277C999046A85B7DE6F12DBE1B6DD70CA7D9EB56BB752913BC4D1F969CDF970FE1C64FA3A100042EB8B6991B4735D8DCCCFBEFD2CCA8A103EA669E763999E87421A73CA0137627663472A31C8ADC53CDF107CEFB07ED37AC170E211A6BACD54F662B5D2E9AD4428E4B3A32D343BA52D592353A34018FAE788261543D98F73B8AD46E202E6A9969E789605ACEE67EBD85B4C4451D31EDE8142F95E306A0CE27DEFCE5B9BADD3F15D9A1C28E6345B7647CC9E477B25483FCE5CBA2CA45FE8626F7'
Y = 167

def s2n(s):
    return bytes_to_long(bytearray(s, 'latin-1'))

def n2s(n):
    return long_to_bytes(n).decode('latin-1')

def gen_prime(y=0):
    base = random.getrandbits(1024)
    off = y
    while True:
        if gmpy2.is_prime(base + off):
            break
        off += 1
    p = base + off

    return p, off

class RSA(object):
    def __init__(self):
        pass

    def generate(self, p, q, e=0x10001):
        self.p = p
        self.q = q
        self.N = p * q
        self.e = e
        phi = (p-1) * (q-1)
        self.d = inverse(e, phi)

    def encrypt(self, p):
        return pow(p, self.e, self.N)

    def decrypt(self, c):
        return pow(c, self.d, self.N)

    # ===== FUNCTIONS FOR PERSONAL TESTS, DON'T USE THEM =====
    def TEST_CRT_encrypt(self, p, fun=0):
        ep = inverse(self.d, self.p-1)
        eq = inverse(self.d, self.q-1)
        qinv = inverse(self.q, self.p)
        c1 = pow(p, ep, self.p)
        c2 = pow(p, eq, self.q) ^ fun
        h = (qinv * (c1 - c2)) % self.p
        c = c2 + h*self.q
        return c

    def TEST_CRT_decrypt(self, c, fun=0):
        dp = inverse(self.e, self.p-1)
        dq = inverse(self.e, self.q-1)
        qinv = inverse(self.q, self.p)
        m1 = pow(c, dp, self.p)
        m2 = pow(c, dq, self.q) ^ fun
        h = (qinv * (m1 - m2)) % self.p
        m = m2 + h*self.q
        return m

def go(req):
    r = RSA()
    p, x = gen_prime()
    q, y = gen_prime()

    r.generate(p, q)
    fake_flag = 'fake_flag{%s}' % (('%X' % y).rjust(32, '0'))

    def enc_flag():
        req.sendall(b'%X\n' % r.encrypt(s2n(FLAG)))

    def enc_fake_flag():
        req.sendall(b'%X\n' % r.encrypt(s2n(fake_flag)))

    def enc_fake_flag_TEST():
        req.sendall(b'%X\n' % r.TEST_CRT_encrypt(s2n(fake_flag), x))

    def enc_msg():
        req.sendall(b'input the data:')
        p = str(req.recv(4096).strip(), 'utf-8')
        req.sendall(b'%X\n' % r.encrypt(s2n(p)))

    menu = {
        '1': enc_flag,
        '2': enc_fake_flag,
        '3': enc_fake_flag_TEST,
        '4': enc_msg,
    }

    cnt = 2
    while cnt > 0:
        req.sendall(bytes(
            '====================================\n'
            '            fault box\n'
            '====================================\n'
            '1. print encrypted flag\n'
            '2. print encrypted fake flag\n'
            '3. print encrypted fake flag (TEST)\n'
            '4. encrypt\n'
            '====================================\n', 'utf-8'))

        choice = str(req.recv(2).strip(), 'utf-8')
        if choice not in menu:
            exit(1)

        menu[choice]()

        if choice == '4':
            continue

        cnt -= 1

class incoming(socketserver.BaseRequestHandler):
    def handle(self):
        signal.alarm(300)
        t = time.time()
        print('time %.7f' % t)
        random.seed(t)

        req = self.request
        while True:
            go(req)

class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass

def run():
    socketserver.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer(("0.0.0.0", 23333), incoming)
    server.serve_forever()

def decrypt_flag(r):
    FLAG = "1F6F62EB628EB9DF50F78AB04473DD1ECC7E63F444BD8F29215C3B4F6F27EE652B803D3DCDD5659F22BC9C775EBDA272EB0F4787B7246258C2BB599762AFA833EA68886F96F1B49286DCF11FCCABC1906C90E56A3C83CB3184B9AE04D89AB9508CCBF3869AF43739D1E661C1DC76B48A64399DD76B559209726876FA71A42F895C555AF31E1509338EC566A2C86CA7C891495D53C2335BB10650D25700D147348BE88DEF957A15E4A6FB0C962BA73DA635D17A04FD07E346A404D84048CE101B23209D5BEDEF835732073ACF92F035B36FE33457DB9FC5B99B36A6038B28145F572DC8226D2B4984900E757A673EF35059DABA6FB9170C9E4E4257D7BEAED5D3"
    flag = n2s(r.decrypt(int(FLAG,16)))
    if 'flag' in flag:
        print("[+] Found:", flag)

def crack(enc_fake_flag):
    sec = 1568465156
    ms_start = 8807663
    ms_end = 9883412
    r = RSA()
    for i in range(ms_start, ms_end):
        # construct the timestamp from the second and milliseconds
        t = round(float(sec) + i * 1e-7, 7)
        print("\r[+] %.7f" % t, end='')
        random.seed(t)
        p = random.getrandbits(1024)
        q = random.getrandbits(1024)
        q += Y
        # if q+y is prime then y could have been generated with t as seed
        if gmpy2.is_prime(q):
            random.seed(t)
            p, x = gen_prime()
            q, y = gen_prime(y=Y)
            r.generate(p, q)
            fake_flag = 'fake_flag{%s}' % (('%X' % y).rjust(32, '0'))
            enc_y = b'%X\n' % r.encrypt(s2n(fake_flag))
            # make sure that the key generated by the seed is the correct one
            if enc_y.strip() == enc_fake_flag:
                print("[*] Found at %.7f!" % t)
                decrypt_flag(r)

print("[+] Started cracking")
crack(ENC_FAKE_FLAG)

It was able to find the flag in less than 5 minutes 

[youben@ym fault_box]$ python bf.py
[+] Started cracking
[+] 1568465156.9699578[*] Found at 1568465156.9699578!
[+] Found: flag{ooo000_f4ul7y_4nd_pr3d1c74bl3_000ooo}

I hope you enjoyed the writeup cause I really enjoyed this challenge, thanks to NYU for organizing such CTF and making awesome challenges.


comments powered by Disqus