Table of Contents
Initial Analyisis
The challenge description says:
What's wrong with this binary? Is it working at all?..
So this is what is given to us:
f-hash: ELF 64-bit LSB pie executable x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/l, for GNU/Linux 3.2.0, BuildID[sha1]=c478a507f2ff67bb79eec62b3ec47d7d43393800, stripped
So I try running this in my VM to see what happens and true to the challenge
description, the binary does not seem to be working properly. It is simply
taking too long to execute.
Lets call it along with strace once to make sure its not calling sleep or something.
execve("./f-hash", ["./f-hash"], 0x7ffe8ba77470 /* 25 vars */) = 0
brk(NULL) = 0x559b7ccef000
access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
access("/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=75560, ...}) = 0
mmap(NULL, 75560, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7fa3808f7000
close(3) = 0
access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/usr/lib/x86_64-linux-gnu/libstdc++.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\220\304\10\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0644, st_size=1594864, ...}) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fa3808f5000
mmap(NULL, 3702848, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7fa38035a000
mprotect(0x7fa3804d3000, 2097152, PROT_NONE) = 0
mmap(0x7fa3806d3000, 49152, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x179000) = 0x7fa3806d3000
mmap(0x7fa3806df000, 12352, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7fa3806df000
close(3) = 0
access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libgcc_s.so.1", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\300*\0\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0644, st_size=96616, ...}) = 0
mmap(NULL, 2192432, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7fa380142000
mprotect(0x7fa380159000, 2093056, PROT_NONE) = 0
mmap(0x7fa380358000, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x16000) = 0x7fa380358000
close(3) = 0
access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\260\34\2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=2030544, ...}) = 0
mmap(NULL, 4131552, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7fa37fd51000
mprotect(0x7fa37ff38000, 2097152, PROT_NONE) = 0
mmap(0x7fa380138000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x1e7000) = 0x7fa380138000
mmap(0x7fa38013e000, 15072, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7fa38013e000
close(3) = 0
access("/etc/ld.so.nohwcap", F_OK) = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libm.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\3\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\200\272\0\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0644, st_size=1700792, ...}) = 0
mmap(NULL, 3789144, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7fa37f9b3000
mprotect(0x7fa37fb50000, 2093056, PROT_NONE) = 0
mmap(0x7fa37fd4f000, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x19c000) = 0x7fa37fd4f000
close(3) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fa3808f3000
arch_prctl(ARCH_SET_FS, 0x7fa3808f4080) = 0
mprotect(0x7fa380138000, 16384, PROT_READ) = 0
mprotect(0x7fa37fd4f000, 4096, PROT_READ) = 0
mprotect(0x7fa380358000, 4096, PROT_READ) = 0
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fa3808f1000
mprotect(0x7fa3806d3000, 40960, PROT_READ) = 0
mprotect(0x559b7be17000, 4096, PROT_READ) = 0
mprotect(0x7fa38090a000, 4096, PROT_READ) = 0
munmap(0x7fa3808f7000, 75560) = 0
brk(NULL) = 0x559b7ccef000
brk(0x559b7cd10000) = 0x559b7cd10000
Looks like it is not going to be that easy. Time to break out IDA/Ghidra. After
some debugging it was evident that the function at 0x177c is the blocker. It
seems the function is called multiple times but execution takes too long to
complete if the values of the arguments are greater than certain values.
The function was able to complete execution with lower values. This was of great help later when I was trying to reverse this function.
On further analysing the main of the program it looks like the binary will
print the flag if it completes execution.
So the solution of the problem seems quite simple at this point, we simply have to figure out what the blocker function is doing and optimize it. Easier said than done in most cases.
Scripting
Most of the time spent on this challenge was spent trying to reverse the blocker function. The function and its member functions turned out to be quite simple by the time I wrote it in python. One for example gave us fibonacci numbers and the other was popcount.
The function was a recursive function, this seemed to be the problem. Now whats left is optimising it. I was trying to figure out how I can eliminate the recursion but my team member @sayoojsamuel pointed out that a simple memorisation would suffice and voila! we finally had a blocker function that could handle the values in our challenge binary.
Now at this point we could have wrote whatever the main function was doing in python and get the flag, but I was too lazy to do that. So I wrote a simple gdb-python script that would break whenever our blocker function is called, skip calling the function altogether and instead plug in the values from our optimized python function and continue execution. A little debugging and fiddling around as always and we get the flag!
Here’s the script that does it all:
#!/usr/bin/env python
# gdb -ex "source final_script.py"
from collections import defaultdict
import gdb
fib = [0]
t1 = 0
t2 = 1
block = defaultdict(lambda: defaultdict(dict))
for i in range(0, 0x100):
fib.append(t1 & 0xffffffffffffffff)
nt = t1 + t2
t1 = t2
t2 = nt
val_arr = [0]
ctr = -10
for i in range(256):
if i % 10 == 0:
ctr += 10
val_arr.append(1 + ctr)
def blocker(x,y, n):
try:
return block[x][y][n]
except:
pass
if n == 1:
output = popcount_modified(x,y)
elif n == 2:
output = popcount_modified(x ^ 1,y)
else:
output = blocker(x,y,n-1) + blocker(x,y,n-2) + popcount_modified(x ^ fib[n], y) & 0xffffffffffffffffffffffffffffffff
while (output >> 64) >= 0xf600000000000000:
output -= 0xf6000000000000000000000000000000 + val_arr[n]
block[x][y][n] = output
return output
def popcount_modified(x, y):
return (popcount(x) + popcount(y))
def popcount(x):
return bin(x).count("1")
gdb.execute("file f-hash")
gdb.execute("b *0x55555555577C")
gdb.execute("r")
while True:
addr = int(gdb.execute("p $rdi", to_string=True).split()[2],16)
val1 = gdb.execute("p $rdx", to_string=True).split()[2]
val2 = gdb.execute("p $rcx", to_string=True).split()[2]
ctr = gdb.execute("p $rsi", to_string=True).split()[2]
rel = blocker(int(val1,16),int(val2,16), int(ctr,16))
ret = rel & 0xffffffffffffffffffffffffffffffff
ret_low = ret & 0xffffffffffffffff
ret_high = (ret >> 64) & 0xffffffffffffffff
gdb.execute("set {void *} " + str(hex(addr)) + " = " + str(hex(ret_low)))
gdb.execute("set {void *} " + str(hex(addr+8)) + " = " + str(hex(ret_high)))
gdb.execute("set $rip = $rip + 5")
gdb.execute("c")
'''
VolgaCTF{16011432ba16efc8dcf779477985b3b9}
[Inferior 1 (process 2915) exited normally]
'''