Yet another cryptanalysis challenge to test your differential-linear skills.

This challenge comes with an implementation of (almost) textbook DES, and a server that allows us to encrypt arbitrary plaintexts with that cipher (in ECB mode, i.e. each 64-bit block independently) using a key that is randomly generated per connection.

There is a time limit set for 20 minutes. To obtain the flag, we need to find the key used by the server for our connection, and submit it to the server.

Unlike some other CTFs [1, 2], this time DES actually means DES without any weird modifications — but there are only 8 rounds instead of the standard 16.

We know that 8-round DES is vulnerable to differential cryptanalysis [3], so that is exactly what we are going to do. If you already have a deeper understanding of differential cryptanalysis or of the attack described in [3], this writeup is not going to be news to you; I found [4] to be a good introduction to the basic attack that is a bit easier to understand than the original paper.

Collecting Data

For historical reasons, DES permutes the incoming plaintext bits with a permutation $\small\mathsf{IP}$, and reverses that permutation on the final ciphertext.

In this section, we use $p$ and $c$ to denote the permuted plaintext and ciphertext as they are used in the algorithm itself; we submit the unpermuted $\hat{p} = \mathsf{\small IP}^{-1}(p)$ to the server and obtain $c = \mathsf{\small IP}(\hat{c})$. The end user of any DES-based encryption will likely only ever deal with $\hat{p}$ and $\hat{c}$, but because the permutations are trivially reversible we find it easier to store $p$ and $c$ directly.

The attack described by [3] requires around 150,000 pairs of related plaintext blocks $(p_1, p_2)$ so that $p_1\oplus p_2 = 40\,5C\,00\,00\,04\,00\,00\,00_{16}$, which we can generate ahead of time.

Because the server uses ECB mode, we can submit these plaintext pairs in bulk (with at most 20000 hex-encoded characters per request, we can submit 625 pairs each time) and obtain ciphertexts $(c_1, c_2)$ for each of them.

The actual cryptanalysis is an offline operation, although we need to keep the connection around to submit the key later.

DES

In a Feistel network such as DES, encryption takes place by repeated application of a round function on the right half of the data, then XOR-ing the result with the left half, and finally swapping the two halves.

We largely follow the notation used in [3]: The inputs into the Feistel round function are called $a,\ldots,h$, its outputs $A,\ldots,H$ ($a$ and $A$ are the in- and output of the first round, $h$ and $H$ those of the eighth and final round).

More interesting are the internals of the round function:

As an example, consider the final round. The input $h$ is expanded to form $S_{Eh} = \mathsf{\small E}(h)$. Together with the round key $K_h$, we obtain the inputs to the S-boxes $S_{Ih}$ (we denote the 6-bit input to a specific S-box $\mathsf{\small S}j$ as $S_{Ih}[j]$). The S-boxes perform a nonlinear substitution yielding $S_{Oh}$, which is then permuted to give the final output $H$ of the round function.

Differential Cryptanalysis

Differential cryptanalysis is based on the idea that encrypting plaintexts with a known relationship (here, $p_1\oplus p_2$ is known) allows us to predict how the internal states of the block cipher applied to each of the plaintexts will be related. This section will also give a brief overview, but the motivated reader is encouraged to read the full paper at [3]. The attack first aims at recovering the 48-bit round key $K_h$ used in the final round.

We denote the XOR between the two blocks in a pair of an internal state $x$ within the cipher as $x’ = x^{(1)} \oplus x^{(2)}$. When we access the ciphertext, we use $c_L$ and $c_R$ to refer to the left and right halves of $c$.

From the cipher, it is possible to derive so-called characteristics, sequences of relationships in the internal states across multiple rounds with a certain probability. The characteristic used in the attack on 8-round DES says that given $\Omega_P = p_1\oplus p_2 = 40\,5C\,00\,00\,04\,00\,00\,00_{16}$, five rounds of DES will lead to the same XOR $\Omega_T = \Omega_P$ in the internal state with probability $\frac{1}{10485.76}$. The internal state examined here is the concatenation of left- and right side after the fifth round is completed, but before the sides are swapped by the Feistel network, i.e. the concatenation of $f$ and $e$. Put differently, we “know” $f’ = 40\,5C\,00\,00_{16}$ and $e’ = 04\,00\,00\,00_{16}$ for at least some of our pairs.

Step 1: Obtaining the first 18 key bits

We observe:

1. For any round $r$, while $S_{Ir} = S_{Er}\oplus K_r$ the XOR remains the same (and are independent from the key): $S’_{Ir} = S’_{Er}$.
2. If the inputs into an S-box are the same (i.e. $S’_{If}[j] = 0$), the outputs will also be the same: $S’_{Of}[j] = 0$
3. If $f’$ follows the assumption described above, the S-boxes S2, S5, S6, S7, and S8 show this behavior ($S’_{If}[j] = 0$), and we can determine the corresponding bits of $F’$ (also zeroes).

The Feistel network immediately gives $H = c_L\oplus g = c_L\oplus e\oplus F$, and the same relation holds for the XOR difference $H’$. Again under the assumption that the pair in question follows the characteristic, we have

• the value of $c’_L$ from the ciphertext pair
• the value of $e’=04\,00\,00\,00_{16}$
• the location of 20 zero-bits in $F’$

and can therefore compute the value of 20 bits of $H’$. If we invert the permutation $\mathsf{\small P}$ at the end of the round function, these bits line up exactly with the outputs of the S-boxes that led to the zeroes in $F’$: S2, S5, S6, S7, and S8. For $j\in\lbrace 2, 5, 6, 7, 8\rbrace$, we now know $S’_{Oh}[j]$.

On the other side of the S-boxes of the final round, we obtain $S’_{Ih} = S’_{Eh} = \mathsf{\small E}(h’) = \mathsf{\small E}(c’_R)$ from the ciphertext pair.

For each of the S-boxes, we determine possible values of $S^{(1)}_{Ih}[j]$ and $S^{(2)}_{Ih}[j]$ so that

• $S’_{Ih}[j] = S^{(1)}_{Ih}[j] \oplus S^{(2)}_{Ih}[j]$, and
• $S’_{Oh}[j] = \mathsf{\small S}j(S^{(1)}_{Ih}[j])\oplus\mathsf{\small S}j(S^{(2)}_{Ih}[j])$.

This means that the differences both before and after the non-linear substitution need to be correct. This check is best performed using a pre-computed lookup table over $S’_{Ih}[j]$ and $S’_{Oh}[j]$; testing all combinations on the fly has some significant performance drawbacks.

If the table does not contain a valid combination for even a single one of the S-boxes, we know that the pair cannot follow the characteristic, and discard it.

For both potential input bit sequences $S_{Ih}$, we compute the corresponding $S_{Eh} = \mathsf{\small E}(c_R)$ and cast a vote for the bits of $K_h = S_{Ih}\oplus S_{Eh}$ that were XORd on top of the inputs for S-boxes S6, S7, and S8 (just as in the original paper, we use S2 and S5 only for filtering, and recover their key bits separately). Over the 150,000 pairs, a simple majority voting reveals the 18 bits of the round key $K_h$ corresponding to these inputs (150,000 is carefully chosen to make this peak distinctive enough, [3] discusses why this many pairs are needed).

Step 2: Discard invalid pairs

With those 18 key bits, we can filter out most of our pairs: Through $S_{Ih}[j] = K_h[j]\oplus S_{Eh}[j]$ we determine the actual $S_{Oh}[j]$ ($j\in\lbrace 6, 7, 8\rbrace$) and compute $S’_{Oh}[j]$. If this value does not match our assumption ($S’_{Oh} = \mathsf{\small P}^{-1}(c’_L\oplus e’\oplus F’)$, see above), we discard the pair. After this step, only around 50 pairs will remain.

Step 3: Obtaining the next 12 key bits

We repeat the process from step 1 for the outputs of the S-boxes S2 and S5 on the filtered list of pairs. Because the filtered list has a far higher ratio of pairs that match our characteristic, the peak in votes is again strong enough to make obtaining these 12 key bits fairly straightforward.

Step 4: Bruteforcing the remaining bits

Of the round key $K_h$, we are still missing the bits corresponding to the S-boxes S1, S3, and S4. However, we do not really want to bruteforce the full $(2^{6})^3=2^{18}$ combinations. While it is possible that our time budget would actually allow this approach, there is a faster way to solve this issue.

First, we (again probabilistically) derive $K_h[1]$ and $K_h[4]$ by bruteforcing the entire keyspace ($2^{12}$ possible combinations):

To evaluate a key, we keep $K_h[3] := 0$ and compute the value of $S_{Og}$ for each ciphertext:

1. Use the key to compute $H=F(h, K_h)=F(c_R, K_h)$ where $F$ is the round function
2. Then, compute $g = H\oplus c_L$.
3. Reverse the key scheduling algorithm to obtain a guess for the round key $\tilde{K}_g$ (some bits will remain 0 because they are independent of $K_h$)
4. Compute $S_{Ig} = \mathsf{\small E}(g) \oplus \tilde{K}_g$
5. Apply the S-boxes to obtain $S_{Og}$

Within each ciphertext pair, we can then compare the resulting XOR to our expected $G’ = f’\oplus h’$ (with $f’$ known from the characteristic, and $h’ = c’_R$). The candidate key bits that yields the correct $G’$ for the largest number of pairs are chosen as $K_h[1]$ and $K_h[4]$.

We repeat this step with $K_h[1]$ and $K_h[4]$ fixed to their new values in order to obtain the final 6 bits of the round key ($K_h[3]$).

Step 5: Bruteforce the DES key

Once we have recovered $K_h$, we can reverse the key scheduling algorithm of DES to restore the DES key. However, DES only uses 48 bits of the 56 bit key for each round key. Using a single plaintext-ciphertext pair, we find the last 8 bits of the DES key by bruteforcing over the 256 possible options, choosing those bits that yield the correct encryption. And so:

[*] Generating plaintexts
[*] Setting up counters
[*] Precomputing S-box XORs
[*] Solved proof-of-work: fn,d
[*] Examining plaintext pairs: 150000 of 150000 after 327.750s (455.759 pairs/s)     
[*] Analyzed 150000 ciphertext pairs
[*] Obtaining probable key bits for S6, S7, and S8
    K8[S6] = 44
    K8[S7] = 58
    K8[S8] = 35
[*] Filtering pairs with expected S-box outputs
[*] 61 valid pairs remaining
[*] Examining remaining pairs
[*] Obtaining probable key bits for S2 and S5
    K8[S2] = 62
    K8[S5] = 35
[*] Bruteforcing key bits for S1 and S4
    K8[S1] = 20
    K8[S4] = 18
[*] Bruteforcing key bits for S3
    K8[S3] = 16
[*] Bruteforcing DES key
[*] Submitting DES key: 849640b62ed24aa4
[*] Got flag: flag{but_th3_litt1e_sticky_leave5_and_tHe_pRec1ous_t0mbs_and_the_b1Ue_sky_ANd_The_woman_you_loVe_How_will_you_lIVe_h0w_wi1l_yoU_love_them_wiTh_5uch_a_h3ll_in_YouR_h34rt_and_y0ur_he4d__How__Can__You__}

python zero.py  357.90s user 0.36s system 95% cpu 6:16.86 total

---

[1] X-MAS CTF 2018: A white rabbit in a snowstorm (DES with linear S-boxes) (writeup)

[2] X-MAS CTF 2018: A black rabbit in the dark (DES without output permutations) (writeup)

[3] E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” Journal of Cryptology, vol. 4, no. 1, pp. 3–72, January 1991. DOI: 10.1007/BF00630563

[4] E. Biham, “Differential Cryptanalysis,” University of Haifa, 2013 (PDF)