HITCON CTF 2020 Writeup
Posted on Wed, 2020-12-02 in CTF
Wassup wassup wassup wassuuuuuuuup! C-T-eeeeeF!
So, after a somewhat long time out of the CTF scene, I played with my team mhackeroni.
These is my (short) writeup for challenge Run Run Run and L'Obscurité (I know you only care about the latter, so I put it at the end :P). Only 1 solve in the world, baby.
We also have an asciinema today, so don't miss the conclusion!
Run Run Run
This was a Garmin-made custom VM for embedded devices. If you are thinking "Wait, what the fuck?" you are correct.
The VM is pretty simple and I just used the .jar file fom the SDK to get the disassembly, resources and strings.
After a bit of processing, this is the control flow graph you get:
I'm a huge fan of creating CFGs from CTF VMs and then using Inkscape as IDA Pro.
Anyway, the Garmin thingie is a stack-based VM, and after some reversing I wrote this equivalent python script:
#!/usr/bin/env python3
import sys
magic = [
98, 32, 84, 253, 217, 18, 92, 22, 112, 138, 147, 46, 168, 229, 31, 149, 72, 94, 191, 124, 21, 176, 10, 104, 154, 213, 235, 25, 237, 61, 18, 15
]
def solve(i):
target = 3**i
x_m1 = 1
x_m2 = 1
x_m3 = 1
for i in range(target):
# x[i] = x[i-1] * 2 + x[i-2] + 7 * x[i-3]
x_new = (7 * x_m3 + x_m1 * 2 + x_m2) % 31337
x_m3 = x_m2
x_m2 = x_m1
x_m1 = x_new
return x_m1
for i in range(40):
x = magic[i] ^ solve(i)
x &= 0xFF
x = chr(x)
sys.stdout.write(x)
sys.stdout.flush()
So the challenge writes the flag as its output, but it gets exponentially slower (see target above).
The equation being used is a linear recurrence equation and you can represent it as a simple matrix multiplication.
Sprinkle some fast modular exponentiation on top of the python code above and you can speed up the algorithm and get the flag.
In this case, my boy chqmatteo did the math part because I couldn't be bothered doing it and he is a crypto guy.
L'Obscurité
Aaaaaand this is the one you care about.
The challenge was a binary with a go() function taking a bunch of bytes as input:
int __cdecl main(int argc, const char **argv, const char **envp)
{
char s[32]; // [rsp+0h] [rbp-30h]
int v5; // [rsp+20h] [rbp-10h]
int i; // [rsp+24h] [rbp-Ch]
v5 = 0;
read(0, &input, 64uLL);
if ( go(&input, &input) <= 0 )
{
memset(s, 0, 0x14uLL);
SHA1(&input, 64LL, s);
printf("Flag: hitcon{", 64LL);
for ( i = 0; i < 20; ++i )
printf("%02x", (unsigned __int8)s[i]);
printf("}\n");
}
else
{
puts("Too large");
}
return 0;
}
So, the point is to find an input that makes go() return 0.
Unfortunately, go() is made of 3 basic blocks in total and the middle one is very big, aka it's obfuscated.
I will make it super short and tell you this: like everyone, I wrote an LLVM lifter that didn't work.
After that, almost like a joke, I wrote a very dumb genetic algorithm and it worked.
So, first thing was patching the binary to get the return value from the function.
This is what main() looked like after that:
int __cdecl main(int argc, const char **argv, const char **envp)
{
__int64 v3; // rax
read(0, &input, 0x40uLL);
v3 = go(&input, &input);
printf("%llX", v3);
return 0;
}
Then I wrote a stupid python bitflipper:
#!/usr/bin/env python3
import random
import time
import subprocess
random.seed(random.random())
score = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
best = [0x0] * 0x40
exec = 0
start = time.time()
while score != 0:
guess = best[:]
for _ in range(random.randint(1, 30)):
i = random.randint(0, 0x3F)
b = random.randint(0, 7)
guess[i] ^= 0b1 << b
p = subprocess.check_output('./superpatched', input=bytes(guess))
p = int(p.decode('ascii'), 16)
# exec += 1
if p <= score:
print(p)
best = guess
print(bytes(best).hex())
# print(exec / (time.time() - start))
if p < score:
open('/tmp/best/{}.bin'.format(p), 'wb').write(bytes(best))
score = p
I actually changed this script a lot along the way, so this is just one of the many iterations. Anyway, after some 30-60 minutes I had many solutions to the challenge.
However, they were not valid. In other words, they solved the challenge but the flags I got were not accepted by the scoreboard.
I'm 100% sure some other team reached this point, because the organizers said that the input bytes should only take the value 0x00 or 0x01.
But they got stuck here I guess...
So, after this new constraint I rewrote the bitflipper to just use 1s and 0s, but it wasn't working that well.
I was about to go to sleep when I though: Why not take one of the earlier solutions and try to make it valid?. And this is what I did.
Here's the script that takes an invalid solution and changes its bytes to make them 0 or 1:
#!/usr/bin/env python3
import random
import time
import subprocess
random.seed(random.random())
best = list(open('/tmp/best/0.bin', 'rb').read())
p = subprocess.check_output('./superpatched', input=bytes(best))
score = int(p.decode('ascii'), 16)
best_weight = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
# score = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
# best = [0x0] * 0x40
# exec = 0
# start = time.time()
# while score != 0:
while True:
guess = best[:]
for _ in range(random.randint(1, 30)):
i = random.randint(0, 0x3F)
if guess[i] > 1:
b = random.randint(0, 7)
guess[i] ^= 1 << b
p = subprocess.check_output('./superpatched', input=bytes(guess))
p = int(p.decode('ascii'), 16)
# exec += 1
if p & 0x8000000000000000:
break
if p <= score:
print(p)
print(bytes(guess).hex())
weight = sum(sum(map(int, bin(x)[2:])) for x in guess)
if weight <= best_weight:
best_weight = weight
best = guess
# print(exec / (time.time() - start))
if p < score:
open('/tmp/best/{}.bin'.format(p), 'wb').write(bytes(best))
score = p
Here's an asciinema for the lulz:
Conclusion
This writeup is a shitty one but to be honest I'm only writing it because many people asked and also because the organizers want it since we reached 2nd place.
Some Italian researchers I know from twitter were able to solve the challenge using a SMT solver. They are not CTF players though, and did it after the event was finished.
I honestly don't know what the intended solution was, but it seems like the organizers are not going to release it so... This is my crappy solution and it worked.
Never underestimate the power of stupid approaches, especially in CTFs.
I guess I won the CTF bingo this time!
Cheers,