Rating:

# Basics (hardware, 50p, 280 solved)

## Description

In the task we get 2 source files:
- [main](https://raw.githubusercontent.com/TFNS/writeups/master/2020-08-24-GoogleCTF/basics/main.cpp)
- [system verilog checker](https://raw.githubusercontent.com/TFNS/writeups/master/2020-08-24-GoogleCTF/basics/check.sv)

We can also connect to remote server, where this code is running.

## Static code analysis

### Main

Main is pretty simple:
1. Read input character
2. Strip most significant bit
3. Feed to the circuit
4. Simulate clock tick, so the input goes through the circuit
5. Loop at most 100 times, or when user provides newline
6. Check the state of check->open_safe circuit outpupt, and give the flag

Note: since the flag is sent when we match input to the circuit, it's safe to assume that our input is NOT the flag, but rather some random string.

### Password checker

The important part here is the system verilog circuit which verifies the password.
Since we don't know it, we just tried to guess-timate /check the syntaxt and re-write this logic into python.

Input is marked as:

input [6:0] data

so there are 7 bits of input, which matches what main is feeding.

Then we have:

verilog
reg [6:0] memory [7:0];


So memory is 8 element array of 7 bit registers.
Enough to hold 8 bytes of input.

There is also:

verilog
reg [2:0] idx = 0;

So 3 bit register for holding index, therefore it's enough to count 0..7, as much as our input array can have.

This all suggests password length of 8.

Next entry is:

verilog
wire [55:0] magic = {
{memory, memory},
{memory, memory},
{memory, memory},
{memory, memory}
};


This is 56 bit array, created by concatenation of values in memory, so our inputs.
It concatenates pairs of input bytes, and then combines this in a single bitstream.
Keep in mind bit order during this concatenation!
It is:


memory, ..., memory, memory, ...,memory


Where memory is MSB and memory is LSB of memory entry.

This is important, because if you hold a binary value in, for example, python, bit order is inverted compared to this!
Eg. D is 68 or 0b1000100, but in such case val would return MSB and not LSB.

Then we have:

verilog
wire [55:0] kittens = { magic[9:0], magic[41:22], magic[21:10], magic[55:42] };


Again a 56 bit array, created by concatenating bits from magic array.

Then state of the password checker is done via:

verilog
assign open_safe = kittens == 56'd3008192072309708;


So basically kittens have to be equal to this 56 bit decimal number 3008192072309708

Lastly we have:

verilog
always_ff @(posedge clk) begin
memory[idx] <= data;
idx <= idx + 5;
end


So data are not filling memory in consecutive order.
Notice that idx is bumped by 5, and we know idx is counting mod 8, so we're filling memory in order 0, 5, 2, 7, 4, 1, 6, 3

### Pythonized checker

Now that we know what the checker does, we can implement this in python:

python
def encrypt(input_data):
memory = [None for _ in range(8)]
idx = 0
for data in input_data:
memory[idx] = bin(ord(data)).replace("0b", "").rjust(7, '0')
idx = (idx + 5) % 8
magic = memory + memory + memory + memory + memory + memory + memory + memory
magic = magic[::-1] # if we access via index magic is LSB not MSB as in our string magic, so invert here
kittens = magic[0:10][::-1] + magic[22:42][::-1] + magic[10:22][::-1] + magic[42:56][::-1] # each bit chunk has inverted bit order
res = int(kittens, 2)
return res


## Solver

Now we need to implement inverse function.

First we can just turn output value into bitstream, and then we want to get back from kittens to magic:

python
def recover_magic(kittens):
idx = 0
magic = [None for _ in range(56)]
for i in range(9, -1, -1):
magic[i] = kittens[idx]
idx += 1
for i in range(41, 21, -1):
magic[i] = kittens[idx]
idx += 1
for i in range(21, 9, -1):
magic[i] = kittens[idx]
idx += 1
for i in range(55, 41, -1):
magic[i] = kittens[idx]
idx += 1
magic = magic[::-1]
magic = ''.join(magic)
return magic


We know which bit ranges where going to next kittens bits, so we can read them back.

Rest of the decryption is quite simple.
Once we have magic, we can split it in 7-bit blocks, and put them back in original order.
Finally we want to invert the permutation introduced by idx+5 %8:

python
def decrypt(target):
kittens = bin(target).replace("0b", "").rjust(56, '0')
magic = recover_magic(kittens)
chunks = chunk(magic, 7)
memory = [chunks, chunks, chunks, chunks, chunks, chunks, chunks, chunks]
shuffled_input = [chr(int(x, 2)) for x in memory]
input_perm = [0, 5, 2, 7, 4, 1, 6, 3]
res = [None for _ in range(8)]
for i, s in enumerate(input_perm):
res[s] = shuffled_input[i]
return ''.join(res)


We can check this with a simple sanity check:

python
def sanity():
input_data = "ABCDEFGH"
enc = encrypt(input_data)
dec = decrypt(enc)
assert input_data == dec

sanity()


So if we reversed the checker logic correctly, our decrypt should be valid as well.
There is only one way to find out -> decrypt 3008192072309708 and send to the server.
Decryption gives 7LoX%*_x and if we submit this to the server we get CTF{W4sTh4tASan1tyCh3ck?}

Original writeup (https://github.com/TFNS/writeups/blob/master/2020-08-24-GoogleCTF/basics/README.md).