Model E1337 v2 - Hardened Rolling Code Lock

This challenge is extremely related to Model E1337 - Rolling Code Lock, specially for the cryptanalysis part. Go and check it if you have not done yet.

As in the previous challenge, we have a simple website that requests a code to unlock:

We can put any number we want and we see it is incorrect:

The difference with the first challenge is the length of the number, this time it is 64-bit long.

We should have the Python source code in order to perform the cryptanalysis process. If we remember, there was a Python script called rng.py (for Random Number Generator) in the previous challenge. We can try to access it from the web server, and here we have it:

$ 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))  

It is pretty similar to the one on the first challenge. The differences are:

• The seed is now 64-bit long
• The computation of the state for each iteration of next is performed three times
• There are 64 iterations inside next, because ret is a 64-bit number

The resolution of the challenge follows the same idea that the previous one. We need to compute every state using matrix $A$ and take the last row (which will be the least significant bit of state, that will be appended to ret):

ret = 0

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

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

This time, we will need $I$, $A^3$, $A^6$ and so on until $A^{141}$ (which is $\left(A^{47}\right)^3$).

For this challenge, we only need one incorrect code (actually, the 48 most significant bits). We will solve a similar system of equations, something like this:

$$ \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} $$

Where $s$ is the state we need and $r$ is the code shown in the error message (ret). The first 16 equations are equal to the ones on the previous challenge: for every quartet, the first and last bits are the same. The following 48 equations contain the last row of matrices $I$, $A^3$, $A^6$ until $A^{141}$ in algebraic form.

To solve the system, we use again Gauss Elimination over Galois Field of 2-dimension $\mathbb{F}_2$ (sums are XOR operations and products are AND operations).

I used again a Python script to solve this challenge. It is pretty similar to the one shown and explained before. Matrix $A$ is the same (the tweaked one), but matrix $M$ is a little different due to the fact that the state is computed three times within an iteration of 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)

And the main function only takes one code, because it is enough information to extract the 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)

Also notice that we are calling next(64) because now ret has 64 bits.

Finally, if we run the script, we get the flag:

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