## 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:

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

Viola!