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

It looks like it is “compiled” from some higher-level language (

`add rsi`

/`sub rsi`

-instructions?)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}`