The challenge description gave us a link to an http server containing a qemu command.
qemu-system-i386 -boot n -device e1000,netdev=mynet0 -netdev user,id=mynet0,bootfile=http://18.104.22.168:30172/
By launching it and sniffing the traffic with tcpdump we were able to extract the binary it was downloading from the server.
The binary was a boot file for a x86_64 system. Upon execution it asked for an input, outputted some data and returned an error.
Static analysis through ghidra lead to the discovery of some functions, many of which had weird opcodes not well understood by the decompiler. Since we could not really understand what was happening we ended up attaching gdb to the binary through qemu, getting the base address, setting it up correctly in ghidra, and, by putting up some breakpoints, we managed to get hold of the function reading our input.
The I/O functions of the binary were hard to understand since they used some hardware interrupts. One of my teammates ended up fuzzing the input manually and managed to understand that we were supposed to enter a number of integers in the range 0-127 separated by spaces. Moreover those integers had to be ordered smaller to bigger, without repetitions.
The binary was then reading our input, loading it into an array of integers, and calling a function which returned executable code in the memory area
We tried to disassemble that function but ghidra was unable to understand it and even with the help of gdb it seemed like the instruction pointer was jumping around in memory leading nowhere useful (we even managed to get a crash just by stepping forward in the code).
After a while of trying to understand what that function was doing, we ended up just setting a breakpoint at
0x100000 and hoping that the code generated was not dependent on our input, and indeed it was not.
Here are some examples of codes
0x100000: push ebp
We guessed that the result value in eax was the one deciding which code should be loaded on the next run in the loop. Moreover on the stack we found our input and two arrays of 128 bytes. By reading the codes we realized that they were using our input as indexes for the two arrays, summing the values contained at the locations specified. More codes allowed us to have an upper and lower bounds on those two sums, specifically the first one had to be greather or equal than 1579 and the second one lower or equal than 244.
I dumped the two arrays and passed them to one of my teammates, which implemented a solution for the knapsack problem setting up the weights of the values in a smart way.
def knapsack01_dp(items, limit):
There was probably a more efficient solution but this allowed us to obtain a list of indexes satisfying the constraints.
[8, 22, 28, 32, 34, 37, 43, 48, 50, 53, 69, 70, 76, 84, 104, 108, 112, 117, 127]
By inputting them in the program we got the flag: