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
- 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.
- Understand how the instructions should be interpreted and emulate a run of these instructions.
- 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:
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:
- The first 38 instructions initialize the registers from 2 to 39 with immediate values.
- 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.