Noisy CRC

8 minutes to read

We are given the Python source code of the server:

import secrets
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256

from flag import FLAG

def getCRC16(msg, gen_poly):
    assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16
    msglen = msg.bit_length()

    msg <<= 16
    for i in range(msglen - 1, -1, -1):
        if (msg >> (i + 16)) & 1:
            msg ^= (gen_poly << i)

    return msg

def oracle(secret, gen_poly):
    res = [secrets.randbits(16) for _ in range(3)] 
    res[secrets.randbelow(3)] = getCRC16(secret, gen_poly)
    return res


def main():
    key = secrets.randbits(512)
    cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678")  
    enc_flag = cipher.encrypt(FLAG)
    print(f"Encrypted flag: {enc_flag.hex()}")

    used = set({})

    while True:
        gen_poly = int(input("Give me your generator polynomial: "))
        assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16

        if gen_poly in used:
            print("No cheating")
            exit(1)

        used.add(gen_poly)

        print(oracle(key, gen_poly))

main()

Source code analysis

Basically, it creates a random 512-bit key that is used to encrypt the flag with AES. We are given the encrypted flag. The AES key is generated from the SHA256 hash of the key, so we need to find the exact 512-bit key in order to decrypt the AES ciphertext:

def main():
    key = secrets.randbits(512)
    cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b"12345678")  
    enc_flag = cipher.encrypt(FLAG)
    print(f"Encrypted flag: {enc_flag.hex()}")

The server allows us to compute the CRC (Cyclic Redundancy Check) of the 512-bit key with any polynomial of degree 16 (represented by a 16-bit integer). Specifically, we are dealing with CRC-16, since the output will be a 16-bit number:

    used = set({})

    while True:
        gen_poly = int(input("Give me your generator polynomial: "))
        assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16  

        if gen_poly in used:
            print("No cheating")
            exit(1)

        used.add(gen_poly)

        print(oracle(key, gen_poly))

Unfortunately, the server does not return just the CRC code of the key, but two additional random values:

def oracle(secret, gen_poly):
    res = [secrets.randbits(16) for _ in range(3)] 
    res[secrets.randbelow(3)] = getCRC16(secret, gen_poly)  
    return res

The CRC-16 algorithm is correct:

def getCRC16(msg, gen_poly):
    assert (1 << 16) <= gen_poly < (1 << 17)  # check if deg = 16  
    msglen = msg.bit_length()

    msg <<= 16
    for i in range(msglen - 1, -1, -1):
        if (msg >> (i + 16)) & 1:
            msg ^= (gen_poly << i)

    return msg

CRC

When reading about CRC, I found that it is related to Algebra. In fact, the CRC code is just the remainder of the input data and the generator polynomial. If we encode the bits of every number as a polynomial with coefficients in $\mathbb{F}_2$, the CRC is just:

$$ c(x) = x^N \cdot k(x) \mod{p(x)} $$

Where, $c(x)$ is the CRC code (the output), $k(x)$ is the input data (the key), $N = 16$ (CRC-16) and $p(x)$ is the generator polynomial.

Intuition

Assuming that we know which output is the actual CRC code and which outputs are random, we could build a system of congruences like this:

$$ \begin{cases} x^N \cdot k(x) \equiv c_1(x) \pmod{p_1(x)} \\\\ x^N \cdot k(x) \equiv c_2(x) \pmod{p_2(x)} \\\\ \dots \\\\ x^N \cdot k(x) \equiv c_n(x) \pmod{p_n(x)} \end{cases} $$

The above system of congruences should be familiar… It can be solved using the Chinese Remainder Theorem (CRT), but using polynomials in $\mathbb{F}_2[x]$ instead of integers. The solution will be a polynomial

$$ x^N \cdot k(x) \mod{\prod_{i=1}^n p_i(x)} $$

If $\prod_{i=1}^n p_i(x)$ is large enough (in $\mathbb{F}_2[x]$ it would mean that the degree is large enough), then $x^N \cdot k(x)$ will be a polynomial of degree $N + 511$ (the key has 512 bits, so the associated polynomial has degree 511).

Solution

So, let’s start coding the solution with Python and SageMath. We will start by defining some helper functions:

x = PolynomialRing(GF(2), names='x').gens()[0]


def num_to_poly(num):
    i, poly = 0, 0 * x

    while num >> i:
        poly += ((num >> i) & 1) * x ** i
        i += 1

    return poly


def get_crc(poly):
    io.sendlineafter(b'Give me your generator polynomial: ', str(poly).encode())  
    return eval(io.recvline().decode())

No randomness

Now, we will modify the challenge script to output the CRC code at index 1 of the list:

def oracle(secret, gen_poly):
    res = [secrets.randbits(16) for _ in range(3)]   
    res[1] = getCRC16(secret, gen_poly)
    return res

So, we know exactly where is the correct CRC code and we can try to solve the challenge using the CRT:

io = process(['python3', 'chall copy.py'])
io.recvuntil(b'Encrypted flag: ')
enc_flag = bytes.fromhex(io.recvline().decode())

res = num_to_poly(0)
poly = 2 ** 16

crcs, polys = [], []

while (res // (x ** 16)).degree() < 511 and poly < 2 ** 16 + 50:  
    crc = get_crc(poly)[1]
    crcs.append(num_to_poly(crc))
    polys.append(num_to_poly(poly))

    try:
        res = CRT(crcs, polys)
        if res % (x ** 16) != 0:
            io.failure('This should not happen')
    except ValueError as e:
        io.failure('This should not be reached')
        pass

    poly += 1

if poly == 2 ** 16 + 50:
    io.failure('FAIL')
    exit(1)

If the solution is found, then we must divide by $x^N$ and take the coefficients of the polynomial, which should be the 512 bits of the key used to generate the AES key:

res //= x ** 16
io.info(f'Total results needed: {len(polys)}')
coeffs = list(reversed(res.coefficients(sparse=False)))
coeffs += [0] * (512 - len(coeffs))
key = int(''.join(map(str, coeffs)), 2)

cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b'12345678')  
io.success(cipher.decrypt(enc_flag).decode())

With this solution script, we can find the test flag with our modified version of the challenge:

$ while true; do python3 solve_no_random.py && break; done  
[+] Starting local process '/usr/bin/python3': pid 2871946
[-] FAIL
[*] Stopped process '/usr/bin/python3' (pid 2871946)
[+] Starting local process '/usr/bin/python3': pid 2871975
[*] Total results needed: 44
[+] SEKAI{flag}
[*] Stopped process '/usr/bin/python3' (pid 2871975)

The above hard-coded value 2 ** 16 + 50 comes after the total results needed to find a solution (44 queries), just to avoid an unnecessary iterations.

Adaptation

Now that we know that the challenge is solvable when we know where is the CRC code, we must find a way to determine all the correct CRC codes from the lists of three values (two random and one valid).

After solving cryptoGRAPHy challenges series, I was really into graph theory. Since we have that only one out of three outputs is valid, and we need at least 44 correct outputs, I thought of using a search algorithm such as Depth First Search (DFS) or Breadth First Search (BFS). However, they were difficult to implement because the three nodes (the three outputs) of one step are connected with the three nodes of the next step, so there is no clear way of how to determine if a node has been visited or not, and how to determine adjacent nodes and validate if the path holds…

I was trying to avoid doing a naïve brute force approach, because that would be a total of $3^{44}$ possibilities, which is not affordable. However, we can start with brute force and stop a path whenever the CRT result is not valid or does not exist (actually, this is a kind of DFS).

Let’s put an example where the correct path is [0, 2, 1]: We start testing with [0, 0]. If the CRT is valid, then we continue testing [0, 0, 0], [0, 0, 1] and [0, 0, 2]; otherwise, we would jump to [0, 1] and then to [0, 1, 0], [0, 1, 1] and [0, 1, 2]. Let’s say that [0, 1, 1] gives a correct CRT, so we will save this result in a list. Eventually, we will try all possible combinations (cutting off those that are no longer possible) and obtain a list of valid results (that includes the combination that contains the indices of the real CRC codes).

This is the relevant code for this approach:

def brute_force(valid, index):
    new_valid = []

    for crc_list, poly_list in valid:
        for crc in queries[index]:
            new_crc_list = crc_list + [num_to_poly(crc)]
            new_poly_list = poly_list + [num_to_poly(2 ** 16 + index)]
            try:
                CRT(new_crc_list, new_poly_list)
                new_valid.append((new_crc_list, new_poly_list))
            except ValueError:
                continue

    return new_valid


valid_queries = [
    ([num_to_poly(queries[0][0])], [num_to_poly(2 ** 16)]),
    ([num_to_poly(queries[0][1])], [num_to_poly(2 ** 16)]),
    ([num_to_poly(queries[0][2])], [num_to_poly(2 ** 16)])
]

round_prog = io.progress('Round')

for r in range(1, 44):
    valid_queries = brute_force(valid_queries, r)
    round_prog.status(f'{r + 1} / 44. Current amount: {len(valid_queries)}')  
    if len(valid_queries) > 10000:
        round_prog.failure()
        exit(1)

Then, we just need to take the valid lists (one of them should be the one with all the correct CRC codes) and try to get the AES key from the 512 coefficients of the CRT polynomial to decrypt the ciphertext:

for crc_list, poly_list in valid_queries:
    res = CRT(crc_list, poly_list)

    if res % (x ** 16):
        continue

    res //= x ** 16

    coeffs = list(reversed(res.coefficients(sparse=False)))
    coeffs += [0] * (512 - len(coeffs))
    key = int(''.join(map(str, coeffs)), 2)

    cipher = AES.new(sha256(long_to_bytes(key)).digest()[:16], AES.MODE_CTR, nonce=b'12345678')  
    pt = cipher.decrypt(enc_flag)

    if b'SEKAI' in pt:
        io.success(f'Flag: {pt.decode()}')
        break
else:
    io.failure('FAIL')
    exit(1)

I was surprised that the brute force / DFS approach took around 2 minutes when the answer was found. Nevertheless, I am pretty sure there is a way to determine which outputs are valid CRC codes and which ones are not.

Flag

Anyways, we can run the script and get the flag after some time:

$ while true; do time python3 solve.py chals.sekai.team 3005 && break; done
[+] Opening connection to chals.sekai.team on port 3005: Done
[*] Closed connection to chals.sekai.team port 3005
[+] Round: 44 / 44. Current amount: 4608
[-] FAIL
python3 solve.py chals.sekai.team 3005  116,84s user 0,63s system 96% cpu 2:01,11 total  
[+] Opening connection to chals.sekai.team on port 3005: Done
[*] Closed connection to chals.sekai.team port 3005
[+] Round: 44 / 44. Current amount: 864
[-] FAIL
python3 solve.py chals.sekai.team 3005  52,71s user 0,58s system 93% cpu 57,000 total
[+] Opening connection to chals.sekai.team on port 3005: Done
[*] Closed connection to chals.sekai.team port 3005
[-] Round: Failed
python3 solve.py chals.sekai.team 3005  261,03s user 0,72s system 98% cpu 4:25,42 total
[+] Opening connection to chals.sekai.team on port 3005: Done
[*] Closed connection to chals.sekai.team port 3005
[+] Round: 44 / 44. Current amount: 2916
[+] Flag: SEKAI{CrCrCRcRCRcrcrcRCrCrC}
python3 solve.py chals.sekai.team 3005  72,01s user 0,62s system 95% cpu 1:16,35 total

The full script can be found in here: solve.py.