swiss hacking challenge 2024 - train-dilemma-to-work
Difficulty: hard
Category: re
Author: muffinx
So do you know the train dilemma or trolley problem?
Yeah, that one.
It’s already the hundredth meeting where Terence talked about some edgy scenarios in his meetings.
You know I am just sipping my morning coffee and the guy already asks if, if I had the choice I would save my cousin or 4 random strangers from a incoming train…
I was like man, listen I don’t get paid enough for this.
Anyway we then switched topics, and it was really nice talking with Terence about his jungle vacations and how he spent time with the natives there.
I mean besides those edgy scenarios Terence is a very nice guy, don’t get me wrong.
I believe its from his shamanic practices that he somehow lost a bit touch of society and its common manners and morals.
So anyway he made this puzzle for me to test my analytical skills.
I think a train dilemma to work while traveling to work with a train might be not such a bad idea.
Files
We get a single executable called train:
$ file train
train: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, stripped
Running it:
./train
<< Train >>
> Flip the switches!
[+] Flag: test
[...] Checking Flag 0.00%
[...] Checking Flag 0.29%
[-] Flag not correct.
Exploitation
I used binary ninja for this challenge. My steps would probably also work in other tools with some slight differences.
Getting musl function signatures
When looking at the binary in binary ninja, there are no known functions at all. Usually, a disassembler tries to match known function signatures even when the binary is stripped and statically linked.
Based on strings and the No error information string, I figured that musl libc was statically linked into the binary.
After installing musl on my system, I did the following to get one file that I could open in binary ninja:
cd /usr/lib/x86_64-linux-musl/
ar vx ../libc.a
ld -relocatable *.lo -o libc.o
With that, I used the Signature Library plugin to generate a signature file that I placed in $binaryninja-folder/signatures/linux-x86_64/. The generated signature file is available here :)
Function encryption
After that, I could see some libc functions but still no functions relevant to the actual binary functionality.
There is also debugger protection, so using strace or gdb directly causes the binary to just exit.
I wrote these neat little scripts that with a bit of luck attach GDB or create a coredump after the anti-debugger checks have run:
gdbstart.sh
#!/bin/bash
./train < inputfile &
gdb -p $! train
dumpmem.sh
#!/bin/bash
./train < train &
gcore $!
When opening the coredump in binary ninja, we see the actual functions (only the relevant two are shown). I’ve already annotated them:
int64_t check_switches(int64_t* starting_pointer, int64_t good, int64_t bad)
{
int64_t* history;
__builtin_memset(&history, 0, 8000);
history = starting_pointer;
void directions;
__builtin_memset(&directions, 0, 1000);
char current_value = 'L';
int64_t* current_pointer = starting_pointer;
int32_t index = 0;
int32_t searching = 1;
int64_t return_code;
while (true)
{
if (searching == 0)
{
return_code = 0;
break;
}
if (current_value != 'L')
{
current_pointer = current_pointer[1];
*(uint8_t*)(&directions + ((int64_t)index)) = 'R';
}
else
{
current_pointer = *(uint64_t*)current_pointer;
*(uint8_t*)(&directions + ((int64_t)index)) = 'L';
}
index = (index + 1);
&history[((int64_t)index)] = current_pointer;
if (current_pointer == good)
{
return_code = 1;
break;
}
if (current_pointer != bad)
{
if (current_value == 'R')
{
current_value = 'L';
}
}
else if (current_value == 'L')
{
index = (index - 1);
current_pointer = &history[((int64_t)index)];
current_value = 'R';
}
else
{
index = (index - 1);
while (*(uint8_t*)(&directions + ((int64_t)index)) == 'R')
{
index = (index - 1);
if (index < 0)
{
break;
}
}
if (*(uint8_t*)(&directions + ((int64_t)index)) == 'R')
{
return_code = 0;
break;
}
current_pointer = &history[((int64_t)index)];
current_value = 'R';
}
}
return return_code;
}
uint64_t check_flag(void* input)
{
int64_t var_98;
__builtin_memcpy(&var_98, "\xd6\x18\x50\xe4\x40\xc8\xe0\xe4\x17\x39\xa4\x35\xf1\x35\x68\xc2\x1a\x4c\x4d\xef\x05\xf8\x0c\xf7\x41\x38\x52\x48\x8e\x8c\xfc\x44", 0x20);
char var_78 = 0;
for (int32_t i = 0; i <= 0x29c; i = (i + 1))
{
uint32_t rax_7 = ((i >> 0x1f) >> 0x1b);
*(uint8_t*)(((int64_t)i) + sub_40cccf) = (*(uint8_t*)(((int64_t)i) + sub_40cccf) ^ *(uint8_t*)(&var_98 + ((int64_t)(((i + rax_7) & 0x1f) - rax_7))));
}
sub_40cccf();
for (int32_t i_1 = 0; i_1 <= 0x29c; i_1 = (i_1 + 1))
{
uint32_t rax_21 = ((i_1 >> 0x1f) >> 0x1b);
*(uint8_t*)(((int64_t)i_1) + sub_40cccf) = (*(uint8_t*)(((int64_t)i_1) + sub_40cccf) ^ *(uint8_t*)(&var_98 + ((int64_t)(((i_1 + rax_21) & 0x1f) - rax_21))));
}
void correct_switcheroo;
void* var_c8 = &correct_switcheroo;
void pointer_magic_end;
void* var_c0 = &pointer_magic_end;
void* var_d8 = &correct_switcheroo;
void* var_d0 = &correct_switcheroo;
void** var_e8 = &var_d8;
void** var_e0 = &var_d8;
void*** var_f8 = &var_e8;
void** var_f0 = &var_d8;
// a lot more pointers
var_3f08 = &var_3458;
void************ var_3f00 = &var_17e8;
var_3f18 = &var_3228;
void******** var_3f10 = &var_a48;
var_3f28 = &var_2628;
void************ var_3f20 = &var_3608;
var_3f38 = &var_3d8;
void***************** var_3f30 = &var_2d68;
int32_t flag_is_correct = 1;
void switch_state;
for (int32_t i_2 = 0; i_2 <= 0x157; i_2 = (i_2 + 1))
{
*(uint32_t*)(&switch_state + (((int64_t)i_2) << 2)) = i_2;
}
randomize_shit(get_time(nullptr));
for (int32_t i_3 = 0; i_3 <= 0x1869e; i_3 = (i_3 + 1))
{
rand();
int32_t var_5c_1 = 0x466d23;
int32_t var_5c_2 = 0xf0;
rand();
int32_t var_60_1 = 0x466d23;
int32_t var_60_2 = 0xf0;
int32_t rax_33 = *(uint32_t*)(&switch_state + (((int64_t)var_5c_2) << 2));
*(uint32_t*)(&switch_state + (((int64_t)var_5c_2) << 2)) = *(uint32_t*)(&switch_state + 0x3c0);
*(uint32_t*)(&switch_state + (((int64_t)var_60_2) << 2)) = rax_33;
}
int64_t switch_xor;
__builtin_memcpy(&switch_xor, "\x32\x44\x04\x21\xa4\x59\x5e\xf3\x71\x50\xc6\xc7\xf5\x9c\x60\xaf\x09\x60\x5f\x49\xdf\x09\xe1\x55\x2f\x66\xe8\x9e\xe0\x5f\xfe\xe8", 0x20);
char var_44a8 = 0;
int64_t xor_key;
for (int32_t switch_loop = 0; switch_loop <= 343; switch_loop = (switch_loop + 1))
{
int32_t cur_switch_state = *(uint32_t*)(&switch_state + (((int64_t)switch_loop) << 2));
int64_t status;
__builtin_memcpy(&status, "\x67\x7e\x88\x93\xbd\x71\xad\x24\xa1\xc8\x66\x1e\xd1\x61\x50\x23\xce\x52\xf7\x25\xf0\x64\x36\x4d\x0a\x42\x60\xfe\x00", 0x1d);
__builtin_memcpy(&xor_key, "\x3c\x50\xa6\xbd\xe0\x51\xee\x4c\xc4\xab\x0d\x77\xbf\x06\x70\x65\xa2\x33\x90\x05\xd5\x4a\x04\x2b\x2f\x67\x6a\xfe\xc5\xbc\x78\x3f", 0x20);
char var_4538_1 = 0;
for (int32_t j = 0; j <= 0x1b; j = (j + 1))
{
uint32_t key_diff = ((j >> 0x1f) >> 0x1b);
*(uint8_t*)(&status + ((int64_t)j)) = (*(uint8_t*)(&status + ((int64_t)j)) ^ *(uint8_t*)(&xor_key + ((int64_t)(((j + key_diff) & 0x1f) - key_diff))));
}
__sanitizer::Printf(&status, 1);
for (int32_t j_1 = 0; j_1 <= 0x1b; j_1 = (j_1 + 1))
{
uint32_t rax_54 = ((j_1 >> 0x1f) >> 0x1b);
*(uint8_t*)(&status + ((int64_t)j_1)) = (*(uint8_t*)(&status + ((int64_t)j_1)) ^ *(uint8_t*)(&xor_key + ((int64_t)(((j_1 + rax_54) & 0x1f) - rax_54))));
}
sub_40da00(&data_417180);
int32_t manip_switch_state = cur_switch_state;
if (manip_switch_state < 0)
{
manip_switch_state = (manip_switch_state + 7);
}
uint8_t rax_67 = ((int8_t)((cur_switch_state >> 0x1f) >> 0x1d));
int64_t __saved_rbp;
if (((1 << (((cur_switch_state + rax_67) & 7) - rax_67)) & ((int32_t)*(uint8_t*)((char*)input + ((int64_t)(manip_switch_state >> 3))))) <= 0)
{
for (int32_t j_2 = 0; j_2 <= 0x177; j_2 = (j_2 + 1))
{
uint32_t rax_110 = ((j_2 >> 0x1f) >> 0x1b);
*(uint8_t*)(((int64_t)j_2) + check_switches) = (*(uint8_t*)(((int64_t)j_2) + check_switches) ^ *(uint8_t*)(&switch_xor + ((int64_t)(((j_2 + rax_110) & 0x1f) - rax_110))));
}
if (check_switches(*(uint64_t*)(&&__saved_rbp[(((int64_t)cur_switch_state) * 2)] - 0x3f30), &pointer_magic_end, &correct_switcheroo) == 0)
{
flag_is_correct = 0;
break;
}
for (int32_t j_3 = 0; j_3 <= 0x177; j_3 = (j_3 + 1))
{
uint32_t rax_130 = ((j_3 >> 0x1f) >> 0x1b);
*(uint8_t*)(((int64_t)j_3) + check_switches) = (*(uint8_t*)(((int64_t)j_3) + check_switches) ^ *(uint8_t*)(&switch_xor + ((int64_t)(((j_3 + rax_130) & 0x1f) - rax_130))));
}
}
else
{
for (int32_t j_4 = 0; j_4 <= 0x177; j_4 = (j_4 + 1))
{
uint32_t rax_77 = ((j_4 >> 0x1f) >> 0x1b);
*(uint8_t*)(((int64_t)j_4) + check_switches) = (*(uint8_t*)(((int64_t)j_4) + check_switches) ^ *(uint8_t*)(&switch_xor + ((int64_t)(((j_4 + rax_77) & 0x1f) - rax_77))));
}
if (check_switches(*(uint64_t*)(&&__saved_rbp[(((int64_t)cur_switch_state) * 2)] - 0x3f28), &pointer_magic_end, &correct_switcheroo) == 0)
{
flag_is_correct = 0;
break;
}
for (int32_t j_5 = 0; j_5 <= 0x177; j_5 = (j_5 + 1))
{
uint32_t rax_97 = ((j_5 >> 0x1f) >> 0x1b);
*(uint8_t*)(((int64_t)j_5) + check_switches) = (*(uint8_t*)(((int64_t)j_5) + check_switches) ^ *(uint8_t*)(&switch_xor + ((int64_t)(((j_5 + rax_97) & 0x1f) - rax_97))));
}
}
}
uint64_t i_8;
if (flag_is_correct == 0)
{
int64_t flag_wrong;
__builtin_memcpy(&flag_wrong, "\x1b\x4c\x15\xdb\x65\xa0\xc7\x5a\xc3\xc5\x16\x5f\x8f\x36\x80\xf6\xe2\x8e\x54\xd5\x5b\xb0\xd5\x00", 0x18);
__builtin_memcpy(&xor_key, "\x40\x61\x48\xfb\x23\xcc\xa6\x3d\xe3\xab\x79\x2b\xaf\x55\xef\x84\x90\xeb\x37\xa1\x75\xba\xd5\x84\xd9\x5c\xef\x58\x53\x98\x19\xdc", 0x20);
char var_4538_3 = 0;
for (int32_t i_4 = 0; i_4 <= 0x16; i_4 = (i_4 + 1))
{
uint32_t rax_160 = ((i_4 >> 0x1f) >> 0x1b);
*(uint8_t*)(&flag_wrong + ((int64_t)i_4)) = (*(uint8_t*)(&flag_wrong + ((int64_t)i_4)) ^ *(uint8_t*)(&xor_key + ((int64_t)(((i_4 + rax_160) & 0x1f) - rax_160))));
}
i_8 = __sanitizer::Printf(&flag_wrong, 0);
for (int32_t i_5 = 0; i_5 <= 0x16; i_5 = (i_5 + 1))
{
uint32_t rax_170 = ((i_5 >> 0x1f) >> 0x1b);
i_8 = ((int64_t)i_5);
*(uint8_t*)(&flag_wrong + i_8) = (*(uint8_t*)(&flag_wrong + ((int64_t)i_5)) ^ *(uint8_t*)(&xor_key + ((int64_t)(((i_5 + rax_170) & 0x1f) - rax_170))));
}
}
else
{
int64_t flag_correct;
__builtin_memcpy(&flag_correct, "\xa1\xac\x28\x71\x8c\xa8\x4e\xcf\x55\x93\x0f\xb4\x9f\x66\x98\x12\x2d\xfb\xc3\x00", 0x14);
__builtin_memcpy(&xor_key, "\xfa\x87\x75\x51\xca\xc4\x2f\xa8\x75\xf0\x60\xc6\xed\x03\xfb\x66\x0c\xf1\xc3\x1a\xf4\xbb\xba\x18\x7d\xd1\x14\x09\x8f\x57\xa0\xf5", 0x20);
char var_4538_2 = 0;
for (int32_t i_6 = 0; i_6 <= 0x12; i_6 = (i_6 + 1))
{
uint32_t rax_141 = ((i_6 >> 0x1f) >> 0x1b);
*(uint8_t*)(&flag_correct + ((int64_t)i_6)) = (*(uint8_t*)(&flag_correct + ((int64_t)i_6)) ^ *(uint8_t*)(&xor_key + ((int64_t)(((i_6 + rax_141) & 0x1f) - rax_141))));
}
i_8 = __sanitizer::Printf(&flag_correct, 0);
for (int32_t i_7 = 0; i_7 <= 0x12; i_7 = (i_7 + 1))
{
uint32_t rax_151 = ((i_7 >> 0x1f) >> 0x1b);
i_8 = ((int64_t)i_7);
*(uint8_t*)(&flag_correct + i_8) = (*(uint8_t*)(&flag_correct + ((int64_t)i_7)) ^ *(uint8_t*)(&xor_key + ((int64_t)(((i_7 + rax_151) & 0x1f) - rax_151))));
}
}
return i_8;
}
Gimme flag plz
When looking at the source code I saw that the input of the check_flag function is only used in one if condition:
if (((1 << (((cur_switch_state + rax_67) & 7) - rax_67)) & ((int32_t)*(uint8_t*)((char*)input + ((int64_t)(manip_switch_state >> 3))))) <= 0)
Looking further into this, I noticed that based on each bit of the input, the check_switches function gets called with a different input. So I went on to re-implement everything in a python script:
from pwn import *
cache = {}
def get_value_at_address(address):
#print(address)
if hex(address) in cache:
addr_int = cache[hex(address)]
else:
addr = os.popen(f"gdb -c core.522201 -ex 'x/1gx {hex(address)}' -ex 'quit' --batch | tail -n 1").read().strip()
addr = addr.split(":")[1]
addr_int = int(addr, 16)
cache[hex(address)] = addr_int
return addr_int
def check_switches(start, end, wrong):
elements = [0] * 8000
switches = ['0'] * 1000
current_pointer = start
current_value = "L"
index = 0
i = 0
ret = "?"
switches[0] = "R"
while True:
i += 1
if i % 20000 == 0:
info("".join(switches))
if current_value != "L":
current_pointer = get_value_at_address(current_pointer+8)
switches[index] = "R"
else:
current_pointer = get_value_at_address(current_pointer)
switches[index] = "L"
if index == 0:
elements[index] = current_pointer
index += 1
elements[index] = current_pointer
if current_pointer == end:
# if we reached the end, return 1
warn("=========1")
ret = "1"
break
if current_pointer != wrong:
# if we went right too far, go back
if current_value == "R":
current_value = "L"
elif current_value == "L":
# if we were left and got stuck, go back+right
index -= 1
current_pointer = elements[index]
current_value = "R"
else:
# if we went right and got stuck, go right one turn earlier
index -= 1
while switches[index] == "R":
index -= 1
if index <= 0:
break
if switches[index] == "R":
warn("=========0")
ret = "0"
break
current_pointer = elements[index]
current_value = "R"
return ret
rbp = 0x7ffe2667a4a0
wrong = 0x7ffe2667a400
end = 0x7ffe2667a3f0
success(f"wrong: {hex(wrong)}")
success(f"End: {hex(end)}")
offset = 0x3f28 #-0x648 #0x3f30
out = []
for i in range(0,343):
cur = i
cur = cur << 0x4
cur = cur + rbp
cur = cur - offset
try:
out.append(check_switches(cur, end, wrong))
except:
pass
success("=================")
success("".join(out))
with open("output.txt", "w") as f:
f.write("".join(out))
I was too lazy to reimplement pointers on the stack, so I just used a very ugly solution of calling gdb on the coredump to get the values. Running the script looks very cool:
Swapping the endianness of every 8 bits of the output and decoding them to ascii gitves us the file gives us the flag!
Flag
Conclusion
This was probably the hardest rev challenge I have ever solved to far. Annotating everything definitely helped with tracking parameters and functions, I can recommend noting down as much as possible about every function that you know.
Hype counter?
While checking the flag, the binary also did the following (thanks muffinx lol):
curl -X POST https://mnt.gk.wtf/hypecounter.php 2> /dev/null > /dev/null
(State 2024-04-14) sadly my logs only go back until March 17 but binaries from all the participants have made 43009 requests as of right now.
(State 2024-04-30) it’s now 122865 requests starting Apr 16!