defcon 2020 quals – fountain_ooo_relive

fountain-ooo-reliving

Problem description

We have found the fountain OOO RElive. By discovering its secrets, you will restart the game of life with a chance to do it all over again. This challenge is in memory of John Conway (26 December 1937 – 11 April 2020).

input

We are given a file, which seems to be a game of life state.

The hint at the top of the file # GOOOlly its the Fountain OOO REliving pointed us to the Golly game-of-life simulator. When you feed the file into golly, it shows a diagram (initial state) of what seems like a CPU layout.

initial observation

The diagram can be divided into 4 parts:

  • Top left corner: ROM
  • Top right corner: RAM
  • Bottom right corner: Logic (ALU and CU)
  • Bottom left corner: instruction memory

There are various etching marks written on near each component, labeling them and adding other clues, such as direction of fetching, composition of each instruction, or instruction Op-Code names.

The memory regions (RAM, ROM, instructions), seem to be composed of individual cells (fuses, memory-cells), which have a distinct pattern. When looking closely we can see that there are two patterns to each type of memory, presumably cells representing Zero and cells representing One.

the plan

  1. Use a tool to parse each of the memory regions in the diagram, in order to convert the pictures of cells to a bit stream, where each cell was converted into a bit.
  2. Understand how the instructions should be interpreted and emulate a run of these instructions.
  3. See what comes out and continue from there.

the tools

We used OpenCV as our image processing application, and python as our emulator. We also used The Gimp in order to view a zoomed version of the picture, alongside the individual pixel coordinates.

image processing phase

chopping up the image

At first, using a regular screen-shot cutting tool, we cut out the interesting parts of the diagram, e.g. a rectangle containing the ROM and a rectangle containing the Instructions.

ROM:

Instructions:
alt text

choosing reference cells

Next we opened the picture in the Gimp in order to determine the start location, height and width of each cell. We chose two different looking cells, and labelled one of them Zero and the other One. These two cells are our reference cells, they will be used to compare to all other cells in order to determine which of them are a Zero and which a One.

Example of Rom reference cells:

Example of Instruction reference cells:

This is the code to extract the reference cells.
For ROM:

main_img = cv2.imread('rom.png', cv2.IMREAD_GRAYSCALE)

main_height, main_width = main_img.shape

print(main_width, main_height)
start_offsetx = 9
start_offsety = 17

bit_width = 4
bit_height = 4

skip_height = 7
skip_width = 11

offsetx = start_offsetx
offsety = start_offsety


zero_pattern = main_img[offsety:offsety + bit_height, offsetx:offsetx + bit_width]
one_pattern = main_img[offsety+bit_height+skip_height:offsety + bit_height*2 +
        skip_height, offsetx:offsetx + bit_width]

and Instructions:

main_img = cv2.imread('instructions.png', cv2.IMREAD_GRAYSCALE)

main_height, main_width = main_img.shape

print(main_width, main_height)
start_offsetx = 10
start_offsety = 7

bit_width = 10
bit_height = 3

skip_height = 8
skip_width = 11

offsetx = start_offsetx
offsety = start_offsety


one_pattern = main_img[offsety:offsety + bit_height, offsetx:offsetx + bit_width]
zero_pattern = main_img[offsety+bit_height+skip_height:offsety + bit_height*2 +
        skip_height, offsetx:offsetx + bit_width]

reading and parsing whole memory block

This is the code for ROM which iterates over the whole memory block, converting the pictures into a bit stream:

rom = []
while offsetx < 3204:
    offsety = start_offsety
    column_bits = []
    while offsety < 121:
        if numpy.array_equal(one_pattern, main_img[offsety:offsety + bit_height,
            offsetx:offsetx + bit_width]):
            column_bits.append(1)
        elif numpy.array_equal(zero_pattern, main_img[offsety:offsety + bit_height,
            offsetx:offsetx + bit_width]):
            column_bits.append(0)
        else:
            print("ERROR!!!! doesn't match zero or one: %d, %d" % (offsetx, offsety))
            cv2.imshow("", main_img[offsety:offsety + bit_height, offsetx:offsetx + bit_width])
            cv2.waitKey(0)
            exit()



        offsety += bit_height + skip_height

    column_bits = list(reversed(column_bits))
    rom.append(bits_to_num(column_bits))

    offsetx += skip_width

print(list(reversed(rom)))

Parsing of the instructions was done similarly, only here we also had to dissect each column of bits into the various components of an instruction. We used the etched hints in order to divide each instruction.

result of ROM parsing

The rom parsing turned out to be non-interesting. It consists of 290 words holding the numbers from 0 to 290 respectively.

dissecting the instructions

It was a bit hard to determine from the diagram exactly where each component begins and where it ends (i.e. how many bits to allocate to each component), so we experimented slightly with the sizes until the result seemed to make sense.

Our chosen disection was:

opcode arg1 value arg1 mode arg2 value arg2 mode arg3 value arg3 mode
num bits: 4 16 2 16 2 16 3

The code for disection the function is:

instructions = []
while offsetx < 1275:
    offsety = start_offsety
    column_bits = []
    while offsety < 649:
        if numpy.array_equal(one_pattern, main_img[offsety:offsety + bit_height,
            offsetx:offsetx + bit_width]):
            column_bits.append(1)
        elif numpy.array_equal(zero_pattern, main_img[offsety:offsety + bit_height,
            offsetx:offsetx + bit_width]):
            column_bits.append(0)
        else:
            print("ERROR!!!! doesn't match zero or one: %d, %d" % (offsetx, offsety))


        offsety += bit_height + skip_height

    column_bits = list(reversed(column_bits))
    offset = 0
    opcode_width, value_width, mode_width = 4, 16, 2
    opcode = bits_to_num(column_bits[offset:offset + opcode_width])
    offset += opcode_width
    arg1_val = bits_to_num(column_bits[offset:offset + value_width])
    offset += value_width
    arg1_mode = bits_to_num(column_bits[offset:offset + mode_width])
    offset +=  mode_width
    arg2_val = bits_to_num(column_bits[offset:offset + value_width])
    offset += value_width
    arg2_mode = bits_to_num(column_bits[offset:offset + mode_width])
    offset +=  mode_width
    arg3_val = bits_to_num(column_bits[offset:offset + value_width])
    offset += value_width
    arg3_mode = bits_to_num(column_bits[offset:offset+ mode_width + 1])
    offset +=  mode_width

    instructions.append((opcode, arg1_val, arg1_mode, arg2_val, arg2_mode, arg3_val,
        arg3_mode))

    offsetx += skip_width


instructions = list(reversed(instructions))

Understanding the instructions

Now that we had all instructions parsed, we had a look at them in sequence. We see 115 instructions with opcodes 1, 3 and 6.

For example:

[0]     06      0000:0  0000:0  0002:4
[1]     01      ffff:0  6573:0  0002:4
[2]     01      ffff:0  38da:0  0003:4
[3]     01      ffff:0  57ad:0  0004:4
[4]     01      ffff:0  6343:0  0005:4
[5]     01      ffff:0  0e9f:0  0006:4
[6]     01      ffff:0  344f:0  0007:4
[7]     01      ffff:0  2f1b:0  0008:4
[8]     01      ffff:0  09fa:0  0009:4
[9]     01      ffff:0  3dcf:0  000a:4
...

[50]    03      0027:1  0007:1  0007:4
[51]    06      0001:1  df6d:0  0027:4
[52]    03      0027:1  0008:1  0008:4
[53]    06      0001:1  fa79:0  0027:4
[54]    03      0027:1  0009:1  0009:4
[55]    06      0001:1  ce20:0  0027:4
[56]    03      0027:1  000a:1  000a:4
[57]    06      0001:1  e79d:0  0027:4
[58]    03      0027:1  000b:1  000b:4
[59]    06      0001:1  b6db:0  0027:4
[60]    03      0027:1  000c:1  000c:4
...

[108]   03      0027:1  0024:1  0024:4
[109]   06      0001:1  c763:0  0027:4
[110]   03      0027:1  0025:1  0025:4
[111]   06      0001:1  aac7:0  0027:4
[112]   03      0027:1  0026:1  0026:4
[113]   01      ffff:0  fffe:0  0000:4
[114]   01      0000:0  0000:0  0000:4

By looking at the etching near the Control Unit , and a bit of educated guessing, it seems that the opcodes mean:

opcode mnemonic operation
1 MLZ Move if less than zero
3 SUB Subtract
6 XOR Exclusive Or

Judging by the size of the values, and guessing that lower number may refer to registers/ram addresses while larger numbers are more likely immediate values. The mode bits, for the first two operands seem to be:

mode meaning
0 immediate value
1 register number

emulating the instructions

We wrote the following code to emulate the instructions:

def emulate_instructions():
    registers = [0] * 72
    for j, i in enumerate(instructions):
        print("[%d]" % j +  "\t%02x\t%04x:%x\t%04x:%x\t%04x:%x" % i)
        opcode, a1, a1m, a2, a2m, a3, a3m = i
        op1 = a1 if a1m == 0 else registers[a1]
        op2 = a2 if a2m == 0 else registers[a2]
        if opcode == 6:
            registers[a3] = op1 ^ op2
        elif opcode == 1:
            if unsigned_to_signed(op1) < 0:
                registers[a3] = op2
            else:
                pass
        elif opcode == 3:
            registers[a3] =  (op1- op2) & 0xffff

After running this we looked at the resulting memory (the values in the registers), to see if it is leading us somewhere.
The data was taking shape, so we felt that we are getting somewhere, but the result made no sense so we understood that we were still missing something.

the missing register

Looking at the instruction list can be broken down to:

  1. The first 38 instructions initialize the registers from 2 to 39 with immediate values.
  2. The next instructions perform some kind of hashing function, consisting of Xors and Subtraction on the registers.

Something we found is that register 1 is used in the hashing phase, but as opposed to all other registers it is never initialized in the initialization phase.

Since thre registers are only 16 bits wide, we decided to brute force all possible values for an initialized register 1, and see what we get. The updated code is as follows:

def emulate_instructions(secret):
    registers = [0] * 72
    registers[1] = secret
    for j, i in enumerate(instructions):
        # print("[%d]" % j +  "\t%02x\t%04x:%x\t%04x:%x\t%04x:%x" % i)
        opcode, a1, a1m, a2, a2m, a3, a3m = i
        op1 = a1 if a1m == 0 else registers[a1]
        op2 = a2 if a2m == 0 else registers[a2]
        if opcode == 6:
            registers[a3] = op1 ^ op2
        elif opcode == 1:
            if unsigned_to_signed(op1) < 0:
                registers[a3] = op2
            else:
                pass
        elif opcode == 3:
            registers[a3] =  (op1- op2) & 0xffff
    return registers

for secret in range(0xffff):
    registers = emulate_instructions(secret)
    out = b""
    for r in registers:
        out += struct.pack("<H", r)

    with open("results/%x.out" % secret, "wb") as fout:
        fout.write(out)

searching for the flag

Seeing that we know the flag starts with “OOO”, we searched all of our 65535 result files for that string:

$ grep -a OOO results/*
results/107.out:_/_?Ok/yOy_qo|QUoOOOqiOeObu1^1qOgO^mQ
results/12f.out://7OC/'\_qQmW7OwqO}OJ]1WFOW1]q_WOOOFQ
results/1fd.out:.N/Cu?p_VR?     POOO_1P2
                                        qH_O!P:
results/2117.out:!OOOO/{Oi_isQ_lif1e_/_Qyo/u/re_Qon_/oQuQr_o/w/n}1_
results/4117.out:AOoOOO{oinQ_othQis_Qlifeo_Q__yourOe_qoQn_yoqur_OownO}

The flag

The result of file 4117.out seems suspiciously close to the expected flag format.
We obviously still have errors in our code, seeing that there are a few extra characters sprinkled throughout the flag string, but this was enough for us to guess the correct flag:
OOO{in_this_life__youre_on_your_own}

The full python script usef for the solution can be found here.