Model E1337 v2 - Hardened Rolling Code Lock

Este reto está muy relacionado a Model E1337 - Rolling Code Lock, especialmente en la parte de criptoanálisis. Se recomienda leerlo si no se ha hecho antes.

Como en el reto anterior, tenemos una simple página web que solicita un código para desbloquear:

Podemos poner cualquier número y veremos que es incorrecto:

La diferencia con el primer reto es la longitud del número, esta vez es de 64 bits.

Deberíamos de tener el código fuente en Python para realizar el proceso de criptoanálisis. Si recordamos, había un script llamado rng.py (de Random Number Generator) en el reto anterior. Podemos intentar acceder a él desde el servidor web, y aquí lo tenemos:

$ curl http://35.190.155.168/5eaafdba5d/rng  

import random


def setup(seed):
    global state

    state = 0

    for i in range(16):
        cur = seed & 3
        seed >>= 2
        state = (state << 4) | ((state & 3) ^ cur)
        state |= cur << 2


def next(bits):
    global state

    ret = 0

    for _ in range(bits):
        ret <<= 1
        ret |= state & 1

        for _ in range(3):
            state = (state << 1) ^ (state >> 61)
            state &= 0xFFFFFFFFFFFFFFFF
            state ^= 0xFFFFFFFFFFFFFFFF

            for j in range(0, 64, 4):
                cur = (state >> j) & 0xF
                cur = (cur >> 3) | ((cur >> 2) & 2) | ((cur << 3) & 8) | ((cur << 2) & 4)
                state ^= cur << j

    return ret


setup((random.randrange(0x10000) << 48) | (random.randrange(0x10000) << 32) | (random.randrange(0x10000) << 16) | random.randrange(0x10000))  

Es extremadamente similar al del primer reto. Las diferencias son:

• La semilla seed es de 64 bits
• El cálculo del state para cada iteración de next se realiza tres veces
• Hay 64 iteraciones en next, ya que ret es un número de 64 bits

La resolución del reto sigue el mismo procedimiento que el reto anterior. Necesitamos obtener todos los state utilizando la matriz $A$ y tomar la última fila (que será el bit menos significativo de state, que será añadido a ret):

ret = 0

for _ in range(64):
    ret <<= 1
    ret |= state & 1

    for _ in range(3):
        # Changes in state  

Esta vez, necesitamos $I$, $A^3$, $A^6$ hasta $A^{141}$ (que es $\left(A^{47}\right)^3$).

Para este reto, solamente necesitamos un código incorrecto (de hecho, solamente los 48 bits más significativos). Necesitamos resolver un sistema de ecuaciones similar, como este:

$$ \begin{cases} s_{63} + s_{60} & = & 0 \newline s_{59} + s_{56} & = & 0 \newline \dots & = & 0 \newline s_3 + s_0 & = & 0 \newline s_0 & = & r_{63} \newline \dots & = & r_{62} \newline \dots & = & \dots \newline \dots & = & r_{16} \newline \end{cases} $$

Donde $s$ es el state que necesitamos y $r$ es el código mostrado en el mensaje de error (ret). Las primeras 16 ecuaciones son iguales a las del reto anterior: para cada cuarteto, el primer y el último bit son el mismo. Las siguientes 48 ecuaciones contienen la última fila de las matrices $I$, $A^3$, $A^6$ hasta $A^{141}$ en forma algebraica.

Para resolver el sistema, empleamos de nuevo Eliminación Gaussiana sobre el Cuerpo Finito de Galois de dimensión 2 (las sumas son operaciones XOR y los productos son operaciones AND), o $\mathbb{F}_2$.

Utilicé un script de Python para resolver este reto. Es realmente similar al mostrado y explicado anteriormente. La matriz $A$ es la misma (la mejorada), pero la matriz $M$ es ligeramente diferente debido a que state se calcula tres veces en cada iteración de next:

state_mat_initial = [...]
ret_mat = []

for i in range(16):
    ret_mat.append(list(map(int, list(f'{9 << (4 * i):064b}'))))

state_mat = [[int(i == j) for j in range(64)] for i in range(64)]  

for _ in range(48):
    ret_mat.append(state_mat[-1])
    state_mat = multiply_matrix(state_mat, state_mat_initial)
    state_mat = multiply_matrix(state_mat, state_mat_initial)
    state_mat = multiply_matrix(state_mat, state_mat_initial)

Y en la función main solamente se toma un código, ya que es suficiente información para extraer el state:

def main():
    global state

    code1 = get_code()

    codes = ('0' * 16 + f'{code1:064b}')[:64]
    codes_vector = list(map(int, list(codes)))

    comp_state = gauss_elim(ret_mat, codes_vector)
    state = int(''.join(map(str, comp_state)), 2)

    next(64)
    code2 = next(64)

    r = requests.post(f'{url}/unlock', {'code': code2})  
    print(r.text)

Cabe mencionar las llamadas a next(64), porque ahora ret es de 64 bits.

Finalmente, si ejecutamos el script, obtenemos la flag:

$ python3 solve.py http://35.190.155.168/5eaafdba5d
Unlocked successfully.  Flag: ^FLAG^xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx$FLAG$