Writeup for SPlin - VolgaCTF 2023 Quals Task

First we see eight S-boxes SBOX*, which we denote as \(S_0\) though \(S_7\), defined as a list of \(256\) different values ranging from \(0\) to \(255\), that is, a permutation. Therefore, each defines an invertible mapping of an \(8\)-bit input into an \(8\)-bit output.

Below there are two P-boxes PBOX and PBOX2, hereafter \(P\) and \(P_2\), both defined as permutations of length \(64\).

Then there is a code snippet that builds inverted S-boxes SBOX*_inv (denoted as \(S_0^{-1}\) through \(S_7^{-1}\)), and inverted P-box PBOX_inv (\(P^{-1}\)).

These definitions are followed by two functions, sboxes and sboxes_inv, that split an input \(64\)-bit integer \(x\) into eight \(8\)-bit parts \(x_i\), pass these parts through \(S_i\) or \(S_i^{-1}\), respectively, and combine the images \(S_i\mathopen{}\left(x_i\right)\mathclose{}\) or \(S_i^{-1}\mathopen{}\left(x_i\right)\mathclose{}\) into a single output \(64\)-bit integer. Let’s denote these operations as \(S\mathopen{}\left(x\right)\mathclose{}\) and \(S^{-1}\mathopen{}\left(x\right)\mathclose{}\).

The following three functions, pbox, pbox2, and pbox_inv, apply the permutations \(P\), \(P_2\), and \(P^{-1}\), respectively, to the bits of an input \(64\)-bit integer.

Skipping make_keys for now we see functions encrypt_block and decrypt_block. These are the core encryption and decryption functions. encrypt_block takes a \(64\)-bit integer and a set of round keys and sequentially apply the S-boxes, the P-box, and xor with a round key. decrypt_block reverses the process.

Obviously, this cipher is just a regular SP-net [1] (barring some minor differences), which is also hinted at by SP in the cipher’s name SPlin. Its sketch is shown in Figure 1.

The remaining functions encrypt and decrypt define encryption/decryption of input bytes in CBC-mode [2], encrypt_file and decrypt_file wrap these two and handle reading and writing data from and to files.

Most of the test functions check if everything works correctly, e.g. if the S-boxes are actually invertible or whether encrypted data can be decrypted.

Only two functions draw attention: check_key_schedule and check_encryption_file. We describe them in the following sections.

Examining function make_keys we see that the cipher expects a \(256\)-bit input key as a hex string.

Having unhexlified the input key make_keys splits it into four \(64\)-bit parts and applies the second permutation \(P_2\) to each of these parts, combine then into byte array of length \(32\), makes a circular shift by \(4\) bytes, and, finally, splits the array into four \(64\)-bit integers to give the round keys.

As can be easily verified this is just a \(256\)-bit permutation. The test function check_key_schedule defines an inversion function and applies excessive checks.

Effectively, a \(256\)-bit key is used to produce four \(64\)-bit round keys, meaning the key schedule in a trivial one, and we can’t expect any weak keys resulting from it.

Therefore, to break SPlin we need to retrieve all the \(256\) bits of the key, thus brute-forcing seems impractical.

Perhaps, the most valuable information we get examining the test function check_encryption_file.

First of all, we see this function generates some random bytes, encrypts them and saves the ciphertext as file test.bin.enc. It then checks that this ciphertext can be correctly decrypted.

As we are given file named test.bin.enc we can safely assume this function was used to generate it (examining __main__ also shows that it can be spawned by running the cipher script with python3 splin.py test).

As for the missing plaintext file test.bin, it’s generated by python’s random.randbytes function after having seeded the PRNG with value \(42\):

Hence, we can execute this code snippet to get the missing plaintext.

The length of the plaintext is not random, but given by a curiously-looking expression:

The first expression looks pretty much like a bias of an aggregated (chained) linear approximation given by the so-called Piling-up Lemma [3]:

where \(n\) is the number of linear approximations being aggregated.

The theory also gives an estimate of the expected number of known plaintext-ciphertext pairs required for the approximation to hold [3]:

Thus, n_known_pairs equals \(42\) times the expected number of known plaintext-ciphertext pairs:

Along with the ability to regenerate the plaintext, which gives a lot of known plaintext-ciphertext pairs, and yet another hint in the task’s name SPlin, these formulas lead us to conclusion that the cipher is susceptible to linear cryptanalysis.

To find linear approximations with high absolute value of bias we generally apply a brute-force search in the space of all possible linear equations that relate inputs \(x_i\) to outputs \(y_j\).

To calculate bias \(\epsilon_k\) of a given linear equation \(l_k\) with input mask \(\Phi_k\) and output mask \(\phi_k\) we enumerate all input values \(x_i\), evaluate \(S\mathopen{}\left(x_i\right)\mathclose{}\) and count the number of times \(c_k\) the equation (1) holds. The ratio of \(c_k\) to the total number of input values \(x_i\) gives the bias of the linear approximation \(l_k\):

Therefore, to find all the linear equations with high absolute value of bias we essentially enumerate all input masks \(\Phi_k\) and all output masks \(\phi_k\), calculate bias \(\epsilon_k\) and save it in a list. Sorting this list by \(|\epsilon_k|\) gives us the linear approximations we’re looking for.

The complexity of the algorithm is determined by the number of the input bits, \(n\), and the number of the output bits, \(m\), of the S-box, and, clearly, is \(O\mathopen{}\left(2^{2n + m}\right)\mathclose{}\).

Let’s assume that applying this algorithm to our toy example with two S-boxes \(\mathcal{S}_0\) and \(\mathcal{S}_1\) gives us the following equations.

These linear equations for \(\mathcal{S}_0\) and \(\mathcal{S}_1\) can be used to build chained approximations that span through the whole cipher. The approximations are visualized in Figure 3.

Now that we’ve found some linear approximations we can trace outputs of the S-boxes through the P-box into the S-boxes on the next round and build chained approximations.

When linear cryptanalysis is applied to an SP-network, the chained approximations we actually need don’t go down to the ciphertext block \(c\), but span up to an S-box on the last round of encryption. These approximations provide us with a criterion for an exhaustive search for the last round key (see the next section Brute-forcing round key \(\mathcal{K}_2\)).

In the case of our toy example, the chained approximations we’re looking for relate the input bits of a plaintext block \(p\) to the input bits of the third round that we denote \(x^2_{0,3}..x^2_{0,0}\) and \(x^2_{1,3}..x^2_{1,0}\).

Concretely, let’s start with equation \(x_0 \oplus y_0 = 0\) of \(\mathcal{S}_0\) with bias \(\epsilon_0 = \frac{3}{16} \approx 0.187\). Applying this approximation on round \(0\) (the first round) we see that bit \(0\) of an input plaintext block, \(p_0\), is related to the output bit \(0\) of \(\mathcal{S}_0\), \(y^0_{0,0}\):

Tracing output \(0\) of \(\mathcal{S}_0\) on the first round through \(\mathcal{P}\) we see that \(y^0_{0,0}\) is XORed with \(k^0_1\) (bit \(1\) of the round key \(\mathcal{K}_0\)) and becomes \(x^1_{0,1}\) (input bit \(1\) of \(\mathcal{S}_0\) on round \(1\)):

Putting (2) in the equation above gives

Now let’s use the second approximation of \(\mathcal{S}_0\), \(x_1 \oplus y_1 = 0\), with \(\epsilon_1 = \frac{2}{16} = 0.125\), which for the second round can be rewritten as:

Tracing output \(1\) of \(\mathcal{S}_0\) on the second round through \(\mathcal{P}\) we see that \(y^1_{0,1}\) is XORed with \(k^1_7\) and becomes \(x^2_{1,3}\):

Putting (3) and (4) in (5) gives

Equation (6) defines the first chained linear approximation, \(\mathcal{L}_1\), which can be used to brute-force \(4\) bits of the third round key \(\mathcal{K}_2\). \(\mathcal{L}_1\) is shown in Figure 4.

The bias of \(\mathcal{L}_1\) is given by Matsui’s Piling-up Lemma [3]:

which is a relatively significant value. The corresponding expected number of the known plaintext-ciphertext pairs required for the attack:

which is, again, a relatively reasonable amount of known pairs.

In a similar fashion, let’s build another chained approximation to relate inputs of \(\mathcal{S}_1\) on the last round to the bits of an input plaintext block \(p\).

To this end we:

Combining these, we obtain the second chained linear approximation, \(\mathcal{L}_2\):

which can be used to brute-force the other \(4\) bits of the third round key \(\mathcal{K}_2\). \(\mathcal{L}_2\) is shown in Figure 5.

The bias of \(\mathcal{L}_2\) is:

which is still an adequate value. The expected number of the known pairs is:

a tiny amount of known pairs as well.

The linear approximations \(\mathcal{L}_1\) and \(\mathcal{L}_2\) along with enough known plaintext-ciphertext pairs \(N_p\) allow us to find all \(8\) bits of the last round key \(\mathcal{K}_2\). Here we assume \(N_p > max\mathopen{}\left(N\mathopen{}\left(\mathcal{L}_1\right)\mathclose{}, N\mathopen{}\left(\mathcal{L}_2\right)\mathclose{}\right)\mathclose{}\).

Let’s use \(\mathcal{L}_1: x^2_{1,3} = p_0 \oplus k^0_1 \oplus k^1_7\) (equation (6)) to find \(4\) bits of \(\mathcal{K}_2\).

Note that \(x^2_{1,3}\) goes into \(\mathcal{S}_1\) on round \(2\) (see Figure 6). The outputs of \(\mathcal{S}_1\) are passed through \(\mathcal{P}\) and XORed with \(4\) bits of the last round key \(k^2_5, k^2_4, k^2_3, k^2_2\) to become \(4\) bits of the ciphertext block \(c_5, c_4, c_3, c_2\).

We assume that both \(p\) and \(c\) are known, so we can calculate

Obviously, \(4\) high bits of \(o\) are precisely the ciphertext bits in question: \(o_7 = c_2\), \(o_6 = c_4\), \(o_5 = c_5\), and \(o_4 = c_3\).

Let \(k_h = (k^2_2, k^2_4, k^2_5, k^2_3)\) and \(o_h = \mathopen{}\left(o_7,o_6,o_5,o_4\right)\mathclose{}\). Then, since \(\mathcal{S}_2\) is invertible (the toy cipher is an SP-network), we can find

Note that if \(k_h\) are the true key bits, then \(v_{h,3} = x^2_{1,3}\).

Here comes the key point: for the true key bits \(k_h\) we expect \(\mathcal{L}_1\) to hold with probability approximately \(Pr(\mathcal{L}_1) = 1/2 + \epsilon(\mathcal{L}_1)\), while for a random wrong key this probability should be closer to \(Pr(\mathcal{L}_1) = 1/2\).

This gives us a criterion for brute-force search: for a putative \(k_h\), estimate \(Pr(\mathcal{L}_1)\) using \(N_p\) known plaintext-ciphertext pairs, equations (8)-(9), and the linear approximation \(\mathcal{L}_1\). If \(Pr(\mathcal{L}_1)\) matches \(1/2 + \epsilon(\mathcal{L}_1)\) then \(k_h\) is likely to be the true key bits.

However, there’s a slight complication: generally, a linear approximation involves some key bits of the previous rounds, as is the case for \(\mathcal{L}_1\). To alleviate this problem, note that these key bits don’t depend on the bits \(k_h\) being enumerated, therefore their XOR is a constant value:

with \(a = const\), albeit unknown.

Hence, while evaluating the probability we actually check if

holds, completely ignoring the constant key bits \(a\). Then, depending on the value of \(a\):

Still, for a wrong \(k_h\) \(\mathcal{L}^{\prime}_1\) should hold with probability close to \(Pr(\mathcal{L}^{\prime}_1) = 1/2\).

Therefore, the quantity

can be used to distinguish the true key regardless of \(a\).

Which leads to the following algorithm for brute-force search for \(k_h\) key bits:

Sorting by \(f_h\) values in descending order we get a list of probable key values. Provided \(N_p\) is sufficient, we can take the first (the most probable) value as \(k_h\).

The complexity of the algorithm is largely determined by the number of bits being enumerated and is \(O\mathopen{}\left(2^{log\left(k_h\right)}\right)\mathclose{}\) for every chained linear expression considered.

To get the other \(4\) bits of the key \(\mathcal{K}_2\) we make use of the other linear approximation \(\mathcal{L}_2: x^2_{0,2} = p_1 \oplus k^0_7 \oplus k^1_2\) (equation (7)) and repeat the procedure described above.

Note that \(x^2_{0,2}\) goes into \(\mathcal{S}_0\) on round \(2\) (see Figure 7). The outputs of \(\mathcal{S}_0\) are passed through \(\mathcal{P}\) and XORed with the other \(4\) bits of the last round key \(k^2_7, k^2_6, k^2_1, k^2_0\) to become \(4\) bits of the ciphertext block \(c_7, c_6, c_1, c_0\).

Using (8), we calculate \(o\). Let \(k_l = (k^2_0, k^2_6, k^2_7, k^2_1)\) and \(o_l = (o_0,o_6,o_7,o_1)\). Then (9) becomes

and, again, if \(k_l\) are the true key bits, then \(v_{l,2} = x^2_{0,2}\).

Then, similarly to (10), we define

and use the algorithm (with equations (11)-(12)) to brute-force the key bits and find the most probable value \(k_l\).

Finally, having found the two most probable halves, we simply concatenate \(k_h\) and \(k_l\) and pass the concatenation through \(\mathcal{P}\) to get the last round key:

Now that \(\mathcal{K}_2\) is known, we can decrypt the last round of encryption for all the known ciphertext blocks. Since the S-boxes and the P-box don’t change from round to round, our task now is to analyse two-round version of the toy cipher in the same KPA setting.

Conveniently, we can trim the beginnings of \(\mathcal{L}_1\) and \(\mathcal{L}_2\) and apply these trimmed approximations to perform brute-force search for the bits of the round key \(\mathcal{K}_1\). One way to think about it is that these chained approximations are moved one round up with the exceeded equations removed, see Figure 8.

Essentially, the only relevant change is the plaintext bits that we use in the trimmed linear approximations: \(\mathcal{L}_1\) becomes

and \(\mathcal{L}_2\) is now

Therefore, to get \(\mathcal{K}_1\) we repeat the algorithm for brute-force search, replacing \(p_0\) with \(p_1\) for \(\mathcal{L}_1\) and \(p_1\) with \(p_7\) for \(\mathcal{L}_2\).

Having found the most probable \(\mathcal{K}_1\) we decrypt one more round of encryption and the task becomes breaking one-round SP-network, which actually doesn’t require applying linear cryptanalysis as the key \(\mathcal{K}_0\) can be calculated directly:

where \(r = D_{\mathcal{K}_1}(D_{\mathcal{K}_2}(c))\) is partially decrypted ciphertext block \(c\).

Finally, with all the round keys known we can decrypt any ciphertext, so the toy cipher is broken!