post quantum

by goulov and ice and jofra and mandlebro

Points: 134 (Dynamic, 35 solves)

Description:

Somebody asked for more crypto challenges, so we made one in the middle of the night. Now you better solve it. https://35c3ctf.ccc.ac/uploads/post_quantum-377f0fc6e7eb3afcda72921849d7c2cb.tar.gz

Given: challenge.py generate.py data

Solution:

TLDR

Notice that since we are given plaintexts ($m$), ciphertexts ($c$) pairs: \[c\oplus m = G k \oplus e \Rightarrow \] \[k = G^{-1} (c\oplus m\oplus e)\]
Bruteforce all errors $e$ takes $3^{16}$ possibilities, which is easily done (less than 1 minute in C).
Given the key ($k$), it just remains to recover the flag.

Description

We are presented with a cryptosystem which appears to be based on coding theory, a type of system often used in post-quantum cryptography.

We are also given 1535 pairs of plaintexts and ciphertexts, and the ciphertext for the flag. The plaintexts consist of pairs of bytes, and so does the flag when was encrypted.

Below we explain the relevant parts of the code, and how to exploit it.

For (more) fun, notice one can do everything with just the flag ciphertext, and don’t need any pair of the given plaintext-ciphertext pairs (besides the known 35C3 of the flag).

Repetition code

The code used in this cryptosystem is a simple repetition code. This encoding basically replicates the bits of the message to be transmitted in a noisy channel $n$ times. To decode just choose by majority decision each received $n$ bits. One may read more about these codes on Wikipedia.

We will use functions encode and decode to denote encoding and decoding these codes.

In the given problem, the repetition code repeats each bit 3 times ($n=3$).

Encryption

The encryption function samples a random code columns (we denote this set of random binary matrices by $\mathcal{U}$) which we denote by $G$. It computes the key $k$ in this code. Also, it adds an error to the ciphertext. This error has a very specific structure: It flips a bit randomly in each 3 bits transmitted. This will allow the decoding as we have 3 bits encoding every original bit, and only flip one of these 3. We will denote this error distribution by $\mathcal{E}$.

Then, the encryption function is given by:

\[\begin{align} Encrypt(k,m)&: \\ m_{enc} & \leftarrow \text{encode}(m) \\ G & \leftarrow_\$ \mathcal{U} \\ e & \leftarrow_\$ \mathcal{E} \\ c & \leftarrow G k \oplus m_{enc} \oplus e \\ &\text{return } (G,c) \end{align}\]

Decryption

The decryption is thus:

\[\begin{align} Decrypt(k,G,c)&: \\ m & \leftarrow \text{decode}(c\oplus G k) \\ &\text{return } m \end{align}\]

The attack

The code provided has dimension $48\times48$, and so the key has dimension $48$.

We notice the following: \[c\oplus m = G k\oplus e\Rightarrow\] \[k = G^{-1}(c\oplus m\oplus e)\]

Here $m$ represents the encoded version of the message, but this is just the bit repeated 3 times as already explained.

Given the structure of the error, and since the dimensions are small ($48$), we can bruteforce all error possibilities, i.e. $3^{16}$ cases, so we implement the given cryptosystem in C, as well as our attack. Operations like matrix inversion in $\mathbb{Z}_2$ we do in sage.

To do this we start with the first ciphertext of the flag (no need for the given pairs as we know what it decrypts to), with corresponds to the plaintext 35, and compute the key. We then check this key in the second ciphertext of the flag, which must be C3. If that is the case, we then try to decrypt all ciphertexts corresponding to byte-pairs of the flag.

The last thing to note is that since we are verifying the key only on these 2 bytes C3 it is possible to get false positives that cannot decrypt the rest of the flag. These are not too many, and dumping all decryptions to a file allows on to find one interesting line:

35C3_let's_hope_these_Q_computers_will_wait_until_we're_ready

Resources:

The code we used can be found in solve.c.