So after starting the first level,  we are greeted with this matplotlibdiagram:
```python game.py level1```
![level1](https://hack.more.systems/images/posts/2021-07-06-googlectf-parking-level1.png)
This is actually a game that can be played by clicking inside the diagram.
The green, grey and red boxes represent cars. They can be moved onlyforward and backward (apparently driving wheels were not invented yet). Thegoal of the game is to arrange the car in a way that allows the red car tomove. This is actually very similar to the principle of this[Android game "Unblock Me"](https://play.google.com/store/apps/details?id=com.kiragames.unblockmefree&hl=en_US&gl=US)
The position of the green car(s) is then used to calculate the flag. Level 1was only for demonstration of the rules. Level 2 is the real challenge,so let's fire that up
```python game.py level2```
![level2](https://hack.more.systems/images/posts/2021-07-06-googlectf-parking-level2.png)
Well ok, this is slightly more complicated. If you zoom in more you can stillsee the individual cars though, so it should not be that complicated.
We did know that this challenge can be solved with a tool like `z3`, but werealized that there are a lot of similar patterns throughout the entire"parking lot". Also we were amazed by the idea of building logic gates out ofcars, so we started examining:
Something we noticed is that the red car is in the lower right corner of theplane, while all the green cars are at the very left. Also the entire structurehas their components replicated 64 times vertically. There are also exactly 64green cars, which have only two positions to be in. This means our inputis a 64 bit number which we apply some logic on to derive wether their positionallows the red car to move or not.
## Basic Components and Gates
Let's dig into the basic components. At the smalest scale we have:
| component | explanation || --------- | ----------- || ![x](https://hack.more.systems//images/posts/2021-07-06-googlectf-parking-or_gate.png) | or gate: either car can move out of the way to allow the ouput car to move ||  ![x](https://hack.more.systems//images/posts/2021-07-06-googlectf-parking-and_gate.png) | and gate: both cars need to move to allow the ouput car to move ||  ![x](https://hack.more.systems//images/posts/2021-07-06-googlectf-parking-splitter.png) | splitter: if an and gate is used in the other direction, we get a signal splitter || ![x](https://hack.more.systems//images/posts/2021-07-06-googlectf-parking-crossing.png)| crossing: both chains (top to bottom and left to right) can independently carry their signal ||  ![x](https://hack.more.systems//images/posts/2021-07-06-googlectf-parking-constant.png) | constant: a constant is represented via a dead end wich either allows the car to move or not |
## Higher Level Gates
The reason a constant always consists of two opposing strands is very simple:In order to force the green cars into a certain position, the challenge authors had to consider both cases (car up or car down) and apply logic to it. If only one position was checked, we could just move all cars in the opposite position and get a valid solution to the puzzle, but not the intended flag. So actually the entire higher level logic always has two opposing strands for every signal.
From the basic components we recognized before, some more advanced logic blocks were created:
| component | explanation || --------- | ----------- ||  ![x](https://hack.more.systems//images/posts/2021-07-06-googlectf-parking-xor_gate.png) | xor gate: this gate first calculates all combinations of the four inputs (remember that the inputs a and a  always come as two opposing "wires". from top to bottom we have a, ¬a, b and ¬b.The output XOR is then computed as (a AND ¬b) OR (¬a AND b). Because this is a higher level component, all calculations have to be done twice, so the negative strand is calculated as (a AND b) OR (¬a AND ¬b) ||  ![x](https://hack.more.systems//images/posts/2021-07-06-googlectf-parking-half_adder.png) | half adder: similarly to the xor gate, but it additionally performs the calculaiton of the carry bit as (a AND b) with the respective negative strand |
## The Big Picture (literally)
We can now reconstruct what the entire circuit does. If we take three of the 64 rows, the circuit looks like this:
![Truncated parking lot without annotations](https://hack.more.systems/images/posts/2021-07-06-googlectf-parking-3fold.png)
![Truncated parking lot with annotations](https://hack.more.systems/images/posts/2021-07-06-googlectf-parking-annotated.png)
(Note: all the inputs that are not connected just lead to zero constants)
We can see that the half adders always form a full adder.So the entire circuit performs the following operations:
1. XOR with a 64-bit constant1. Multiply with 3 by adding the value to itself shifted by one (`x + (x<<1) == x * 3`)1. XOR with the current value shifted by 1 (`x ^ (x>>1)`)1. Rotate right by one (`ROR x`)1. Add a 64-bit constant1. XOR with a 64-bit constant1. And all bits of the current value
The result of those operations needs to be 0. So we only had to write a little scirpt that extracted all the constants and calculated backwards to get the position of the cars. This took some time, but at the end it did work and we could recover the flag using the code from the `game.py` file. Turns out the 64-bit input value it is just ASCII encoded text
# Flag
```CTF{2TheBr1m}```
# Files
## `sovle.py`
```pythonimport sysimport timeimport stringfrom PIL import Image, ImageDrawfrom matplotlib import pyplot as pltif sys.platform == 'darwin':    import matplotlib    matplotlib.use('TkAgg')import osimport numpy as np
def bitstoint(bits):    return int(''.join(str(x) for x in bits[::-1]), 2)
def bitstostr(bits):    return ''.join(str(x) for x in bits[::-1])
def inttobits(i):    return [int(x) for x in "{0:064b}".format(i)[::-1]]
def inttostr(i):    return "{0:064b}".format(i)
assert bitstoint(inttobits(123456)) == 123456
pic = Image.open("big.png")data = np.array(pic)starts = [[2301,805], [1509,1285], [21,805]]rowsize = 1237 - 805rows = 64
consts = [[] for _ in range(len(starts))]for i, var64 in enumerate(starts):    for row in range(rows):        x = var64[0]        y = var64[1]+row*rowsize        assert data[y][x][2] in [0, 255]        bit = data[y][x][2] == 0        consts[i].append(int(bit))
carry = 0sub1 = []for i in range(64):    in1 = consts[0][i] ^ consts[1][i] ^ carry    sub1.append(in1)    carry = int(consts[1][i] + carry + in1 >= 2)
sub1i = bitstoint(sub1)sub1i_fast = bitstoint(consts[0]) - bitstoint(consts[1])assert sub1i == sub1i_fast
rol1 = sub1[-1:] + sub1[:-1]
carry = 0xor2 = []for i in range(64)[::-1]:    in1 = rol1[i] ^ carry    xor2.append(in1)    carry = in1
xor2 = xor2[::-1]
carry = 0in1 = 0sub2 = []for i in range(64):    in2 = in1 ^ xor2[i] ^ carry    sub2.append(in2)    carry = int(carry + in1 + in2 >= 2)    in1 = in2
sub2i = bitstoint(sub2)sub2i_fast = (bitstoint(xor2) + 2**64) / 3assert inttobits((sub2i * 3) % (2**64))  == xor2
res = [x ^ y for x,y in zip(sub2, consts[2])]
def printflag(res):    bits = ''.join(str(x) for x in res)    flag = b"CTF{"    while bits:        byte, bits = bits[:8], bits[8:]        flag += bytes([ int(byte[::-1], 2) ])    flag += b"}"    print(flag)
printflag(res)```