Round'n'round

Introduction

For this challenge we are actually given a lot of things. Firstly we have an encrypted file, we also have the program used for encryption and decryption. Finally we have a remote service which will encrypt arbitrary messages under the same key as the encrypted flag.

Affine encryption

Examining the encryption program it turns out that the encryption algorithm is simply a lot of additions (xors) and multiplications over the polynomial $x^{64} + x^4 + x^3 + x + 1$, ie. the CRC-64-ISO polynomial. This means that we can represent the encryption of a single block as an affine function

$$ c = \mathbf{A} p \oplus \mathbf{b} $$

Where $p$ is the plaintext, $c$ is the ciphertext and $\mathbf{A}$ is a matrix representing the linear portion of the encryption and $\mathbf{b}$ a vector representing the affine portion. If we can determine these, decryption is trivial as a slight rearrangement gives:

$$ p = \mathbf{A}^{-1} (c \oplus \mathbf{b}) $$

The affine part

The first thing we tackle the affine portion $\mathbf{b}$. To do this we pick two plaintexts $p_1$ and $p_2$ and ask our encryption service to encrypt $p_1$, $p_2$ and $p_1 \oplus p_2$ giving ciphertexts $c_1$, $c_2$, and $c_{1 \oplus 2}$. With these three we can determine $\mathbf{b}$ as follows:

$$ \begin{aligned} c_1 \oplus c_2 &= \mathbf{A} p_1 \oplus \mathbf{b} \oplus \mathbf{A} p_2 \oplus \mathbf{b} \\ c_1 \oplus c_2 &= \mathbf{A} (p_1 \oplus p_2) \oplus \mathbf{b} \oplus\mathbf{b} \\ c_1 \oplus c_2 &= c_3 \oplus\mathbf{b} \\ \mathbf{b} &= c_1 \oplus c_2 \oplus c_{1 \oplus 2} \\ \end{aligned} $$

So we can simply xor these three ciphertexts together to determine $\mathbf{b}$. With this determined we can reduce the system to being linear.

The linear part

For the linear portion we want to determine the matrix $\mathbf{A}$. This is done by isolating determining each row of $\mathbf{A}$ one at a time by encrypting all the unit vectors.

$$ \begin{aligned} c = \mathbf{A} p \oplus \mathbf{b} \\ c \oplus \mathbf{b} = \mathbf{A} p \\ \end{aligned} $$

If $p$ is the $i$th unit vector, then the $i$th row of $\mathbf{A}$ is $c \oplus \mathbf{b}$. Once $\mathbf{A}$ is determined, we invert it. We are guaranteed that the matrix is invertable as otherwise the encryption would not be reversible. As we had a hard time finding python code to do this inversion in xor, here is our elimination based routine nicely hardcoded for 64 bits:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


def xor_inverse(a):
    total = np.hstack((a, np.eye(64, dtype=int)))
    for i in range(64):
        if total[(i,i)] != 1:
            for j in range(i + 1, 64):
                if total[(j, i)] != 0:
                    total[i] = total[j] ^ total[i]
                    break
            else:
                assert False
        
        row = total[i]
        for j in range(64):
            if i != j:
                if total[(j,i)] != 0:
                    total[j] = total[j] ^ row
    I, ai = np.hsplit(total, 2)
    return ai

Putting it together

Once both $\mathbf{b}$ and $\mathbf{A}^{-1}$ are known we simply apply the decryption formula to each block in the encrypted flag: