allways r0ops

This challenge was quite hard for the points given. Anyway, the “reversing” is easy enough.

First off the program accepts a network connection and reads up to 0x1000 bytes to a global buffer. Then it copies 0x1000 random looking bytes from one global buffer to another. I have no idea what this step is for; an attempt at obfuscation maybe?

Lastly rdi is loaded with the address of the received data, rsi with the address of an uninitialized global buffer, and rsp with an address in the middle of the random looking bytes. Upon return from the program will then of course jump to the first address stored here.

As it turns out that address contains a jump to a short code sequence which ends in a ret, which of course means that the program jumps to the next address in the “stack”:

Looking at a few more gadgets on the “stack” I see the pattern that they all start with a short jump and end with a return.

So I write an IDA script to extract the “real” program:

And run it:

There are four conditional jumps in there. They all jump past the next instruction and directly to the retn. In all four cases the following instruction adds to rsp which is effectively a jump in the stack-program.

Looking at the stack-program I notice that

1. It looks like it is “compiled” from some higher-level language (add rsi/sub rsi -instructions?)

2. The last two gadgets are huge; they are probably “real” functions. The second one (the pointer at 0x0e0bc90) is just back in the accept-loop, so the first one (pointer at 0x0ebc88) is probably a win-function.

First I group the program by which instructions I guess belong to the same higher-level language operation:

Points of interest:

• rsi is only used for moving a value from one register to another.
• rdi (pointer to the data received from the network, remember?) is only modified in one place: 8 is being added shortly after reading one qword from [rdi] into rax.
• Before each conditional jump a constant is loaded into rdx and depending on whether rax and rbx is equal or not rdx is added to rsp.
• Right before the win-function is a loop instruction that jumps to add rsp​, rdx ; retn. These instructions were of course not found by my IDA script.
• rcx is set to 8 in the beginning and then only modified by the loop instruction.

Rewriting register assignment, jumps and inserting labels gives:

Aha, rax and rbx are only used as temporary variables (notice that the compiler completely breaks character in the right-shift operation where 1 is used directly rather than being loaded into rbx).

Getting rid of rax and rbx:

One final rewrite (even though I’m sure you have it figured out):

This code computes a series as:

$x_0 = \tt{0x1337deadbeef0095} \\ x_n = x_{n-1} \cdot \tt{0xcafe} + \tt{0xbeef}$

Split the input into qwords, $$y_1, ..., y_8$$. For each $$y_i$$ exponentiation by squaring is used to compute $$y_{i}^{13337}$$.

If $$y_{i}^{13337} = x_i$$ for $$i = 1, ..., 8$$ the win-function is called. Easy-peasy.

#### Team member kriztw solved this part:

Because register values wrap around, computation effectively happens modulo $$2^{64}$$.

By Euler’s theorem we have that $$a^{\phi(n)} \equiv 1 \mod n$$, so if we can find $$d \equiv 13337^{-1} \mod \phi(n)$$ we will have $$x_{i}^{d} = (y_{i}^{13337})^d = y_{i}^{13337 \cdot d} = y_{i}^1 = y_i$$.

Every odd number is relatively prime to $$2^{64}$$ so $$\phi(2^{64})$$ is $$2^{63}$$. And here’s the program:

Flag: 0ctf{c97155a5e288fa45f926b1058e4e0385d6ccde8513002885dc67948524bcbc85}

(To top)