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 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 , , and so on until (which is ).

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:

Where is the state we need and 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 , , until in algebraic form.

To solve the system, we use again Gauss Elimination over Galois Field of 2-dimension (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 is the same (the tweaked one), but matrix 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$