<- MISC

Deterministic

4 minutos de lectura

Se nos proporciona un archivo de texto grande llamado deterministic.txt:

$ head -30 deterministic.txt
The states are correct but just for security reasons,
each character of the password is XORed with a very super secret key.
100 H 110
110 T 111
111 B 112
112 { 113
113 l 114
114 0 115
115 l 116
116 _ 117
117 n 118
118 0 119
119 p 120
120 e 121
121 } 122
9 18 69
3 61 5
69 93 22
1 36 10
9 18 69
3 61 5
69 93 22
1 36 10
17 27 20
22 28 18
12 89 1
22 28 18
12 89 1
10 93 13
4 93 1

$ tail deterministic.txt
57 5 6969
101 88 121
91 15 99
55 60 57
9999 20 999
6969 29 39
121 10 55
39 72 46
9 18 69
3 61 5

$ wc -l deterministic.txt
   15589 deterministic.txt

Además, esta es la descripción del reto:

There is a locked door in front of us that can only be opened with the secret passphrase. There are no keys anywhere in the room, only this .txt. There is also a writing on the wall.. “State 0: 69420, State N: 999, flag ends at state N, key length: one”.. Can you figure it out and open the door?

Intuición

Los datos dados son una lista de números distribuidos tres por fila. Hay un breve ejemplo, y los números parecen coincidir (100 -> 110; 110 -> 111; 111 -> 112; 112 -> … -> 121; 121 -> 122).

Por lo tanto, parece que debemos encontrar la fila que comienza con el número 69420 ("State 0"), tomar el número central como carácter y encontrar otra fila que comience con el último número de la fila actual. Este proceso se repite hasta que alcancemos el número 999 ("State N").

La lista es extremadamente larga porque hay filas repetidas. Esto lo podemos resolver con sort -u:

$ cat deterministic.txt | sort -u | wc -l
     410

Aun así, necesitamos programar un poco para encontrar la flag.

Estrategia de programación

En primer lugar, necesitaremos leer el archivo y eliminar todas las filas duplicadas. Además, será útil tener una lista ordenada:

def main():
    with open('deterministic.txt') as f:
        unique_lines = sorted(set(f.read().splitlines()))

Entonces crearemos un diccionario llamado states para tener una relación entre el primer número de cada fila y la tupla formada por el valor (segundo número) y el estado siguiente (tercer número):

    states = {}

    for line in unique_lines:
        if re.match(r'\d+ \d+ \d+', line):
            state, value, next_state = map(int, line.split())
            states[state] = (value, next_state)

Nótese que usamos re para omitir filas que no coinciden con el patrón <number> <number> <number>.

Después de eso, definimos los estados inicial y final, y luego agregamos valores en la lista llamada values usando el diccionario:

    values = []

    initial_state, final_state = 69420, 999
    current_state = initial_state

    while current_state != final_state:
        value, next_state = states[current_state]
        values.append(value)
        current_state = next_state

De esta manera, hacemos un uso eficiente de las estructuras de datos.

En este punto, podemos imprimir los valores como bytes:

    print(bytes(values))

Este es el resultado:

$ python3 solve.py
b"0\x06\x1cI\x04\x08\x07\x08\x0e\x0c\rI\x1d\x06I\x19\x08\x1a\x1aI\x1d\x01\x1b\x06\x1c\x0e\x01I\x08\x05\x05I\x1d\x01\x0cI\n\x06\x1b\x1b\x0c\n\x1dI\x1a\x1d\x08\x1d\x0c\x1aI\x06\x0fI\x1d\x01\x0cI\x08\x1c\x1d\x06\x04\x08\x1d\x08I\x08\x07\rI\x1b\x0c\x08\n\x01I\x1d\x01\x0cI\x0f\x00\x07\x08\x05I\x1a\x1d\x08\x1d\x0cGI$\x08\x07\x10I\x19\x0c\x06\x19\x05\x0cI\x1d\x1b\x00\x0c\rI\x1d\x06I\r\x06I\x1d\x01\x00\x1aI\x0b\x10I\x01\x08\x07\rI\x08\x07\rI\x0f\x08\x00\x05\x0c\rGGI&\x07\x05\x10I\x1d\x01\x0cI\x1b\x0c\x08\x05I\x06\x07\x0c\x1aI\x04\x08\x07\x08\x0e\x0c\rI\x1d\x06I\x1b\x0c\x08\n\x01I\x1d\x01\x0cI\x0f\x00\x07\x08\x05I\x1a\x1d\x08\x1d\x0cGI0\x06\x1cI\x08\x05\x1a\x06I\x0f\x06\x1c\x07\rI\x1d\x01\x0cI\x1a\x0c\n\x1b\x0c\x1dI\x02\x0c\x10I\x1d\x06I\r\x0c\n\x1b\x10\x19\x1dI\x1d\x01\x0cI\x04\x0c\x1a\x1a\x08\x0e\x0cGI0\x06\x1cI\x08\x1b\x0cI\x1d\x1b\x1c\x05\x10I\x1e\x06\x1b\x1d\x01\x10HHI0\x06\x1cI\x1a\x01\x06\x1c\x05\rI\x0b\x0cI\x1b\x0c\x1e\x08\x1b\r\x0c\rI\x1e\x00\x1d\x01I\x1d\x01\x00\x1aI\x0e\x00\x0f\x1dHI=\x01\x0cI\x19\x08\x1a\x1a\x19\x01\x1b\x08\x1a\x0cI\x1d\x06I\x1c\x07\x05\x06\n\x02I\x1d\x01\x0cI\r\x06\x06\x1bI\x00\x1aSI!=+\x12]\x1c\x1dY$]\x1d]6]\x1bZ6/\x1c<\x1c'6]\x07-6'Y\x1d6-X\x0f/X\n<\x05\x1dHH\x14"

Obviamente, esto no es lo que esperábamos. Pero recordemos que la descripción decía que el resultado está cifrado con XOR, y la clave es de un solo byte ("key length: one"). Por lo tanto, podemos aplicar fuerza bruta hasta que encontremos HTB en la cadena descifrada:

    for n in range(256):
        result = xor(bytes(values), bytes([n]))

        if b'HTB' in result:
            print(result.decode())
            break

Y aquí tenemos el mensaje descifrado:

$ python3 solve.py
You managed to pass through all the correct states of the automata and reach the final state. Many people tried to do this by hand and failed.. Only the real ones managed to reach the final state. You also found the secret key to decrypt the message. You are truly worthy!! You should be rewarded with this gift! The passphrase to unlock the door is: HTB{4ut0M4t4_4r3_FuUuN_4nD_N0t_D1fF1cUlt!!}

Flag

Y la flag aparece al final:

$ python3 solve.py | grep -oE 'HTB{.*?}'
HTB{4ut0M4t4_4r3_FuUuN_4nD_N0t_D1fF1cUlt!!}

El script completo se puede encontrar aquí: solve.py.