Downloading the binary for challenge 11, we are presented with a windows x86 binary named covfefe. Opening it up in IDA Pro, we see that it is very small, with only a couple functions that perform the application’s logic. The decompilation of the functions can be seen below.

Looking over the challenge code, it appears a series of subtractions is performed over a large array in the binary’s data section. The result of each subtraction is then compared against zero to determine the next instruction. There also appears to be flags that are checked prior to performing IO operations.

After further investigation, I surmise that this must be some kind of virtual machine whose instructions are likely combinations of the single subtraction based primitive. Stepping through the code in a debugger, I can see that the array in the data has distinct sections that serve different purposes. The first 5 dwords act as variables with the following characteristics: one temporary variable for calculations, two that act as flags for when a char is to be read or written, and the other two hold the char that is read or written. This section is followed by a large section that holds strings that are output during the execution of the program. Finally the last section is made up of an array of instruction structures that are executed by the program. The instruction structure has the following format.

                 [ Source Offset ][ Destination Offset ][Next Instruction Offset]

From here I determined that I needed to come up with a way of tracing the execution of the program code that I identified in the data section array. Given the simplicity of the instruction set, I decided to just dump the array to a file and simulate the execution of the program in python. The initial execution trace dumped each subleq instruction and the values of each memory location affected. It also cleared defined the execution path by dumping the current instruction offset. The following is an example of an instruction trace.

   0xf13: mem[0x0]{0x0} – mem[0xefa]{0x65} = mem[0x0]{0xffffff9b}     # Branch Taken: 0xf19

To turn the execution traces into something more readable, I wrote code to simplify the traces into higher level operations. These operations included add, mov, jmp, left shift, and clear. The following is an example of an add operation composed of subtraction operations.

   0x4fc: mem[0x0]{0x0} – mem[0x4fb]{0x1} = mem[0x0]{0xffffffff} #
   0x4ff: mem[0xa1]{0x9e} – mem[0x0]{0xffffffff} = mem[0xa1]{0x9f} #

Once I had a few high level execution traces with different password inputs, I began to manually compare them in Notepad++ to see if I could identify any patterns. Using the visual compare feature, I was able to identify the same round of instructions being executed for each 2 characters of a password that were input. Navigating to the end of these rounds, I found an instruction that appeared to be comparing a static value to one being computed and branching if the value did not equal zero. These static values are listed below.

Line 5185: 0xdef: mem[0xe99]{0x35e8a} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x176cc} #
Line 8515: 0xdef: mem[0xe99]{0x2df13} – mem[0xe98]{0x1e7be} = mem[0xe99]{0xf755} #
Line 11845: 0xdef: mem[0xe99]{0x2f58e} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x10dd0} #
Line 15174: 0xdef: mem[0xe99]{0x2c89e} – mem[0xe98]{0x1e7be} = mem[0xe99]{0xe0e0} #
Line 18500: 0xdef: mem[0xe99]{0x3391b} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x1515d} #
Line 21829: 0xdef: mem[0xe99]{0x2c88d} – mem[0xe98]{0x1e7be} = mem[0xe99]{0xe0cf} #
Line 25155: 0xdef: mem[0xe99]{0x2f59b} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x10ddd} #
Line 28483: 0xdef: mem[0xe99]{0x36d9c} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x185de} #
Line 31809: 0xdef: mem[0xe99]{0x36616} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x17e58} #
Line 35135: 0xdef: mem[0xe99]{0x340a0} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x158e2} #
Line 38461: 0xdef: mem[0xe99]{0x2d79b} – mem[0xe98]{0x1e7be} = mem[0xe99]{0xefdd} #
Line 41787: 0xdef: mem[0xe99]{0x2c89e} – mem[0xe98]{0x1e7be} = mem[0xe99]{0xe0e0} #
Line 45113: 0xdef: mem[0xe99]{0x2df0c} – mem[0xe98]{0x1e7be} = mem[0xe99]{0xf74e} #
Line 48439: 0xdef: mem[0xe99]{0x36d8d} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x185cf} #
Line 51765: 0xdef: mem[0xe99]{0x2ee0a} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x1064c} #
Line 55093: 0xdef: mem[0xe99]{0x331ff} – mem[0xe98]{0x1e7be} = mem[0xe99]{0x14a41} #

As these constants represent two character sets, I realized I could brute force each tuple fairly quickly and retrieve the password. After 16 rounds of brute forcing, I recovered the password, subleq_and_reductio_ad_absurdum@flare-on.com. The python script I used to solve the challenge can be found on my Github here.