FCSC2025 - Le retour de Jafar

Le retour de Jafar

Jafar est de retour avec de la crypto maléfique !

Jafar is back with some evil crypto!

nc chall.fcsc.fr 2153

Technical description of the challenge

This challenge introduces a symmetric block cipher named Jafar. This block cipher roughly follows the Substitution-Permutation network model, with an added Galois field multiplication by the key in the middle.

Fold
class Jafar:
    # [...]
    def Encrypt(self, x):
        state = x
        for _ in range(self.N):
            state = self.AddKey(state)
            state = self.Sbox(state)
            state = self.Permute(state)
        state = self.Middle(state)
        for _ in range(self.N):
            state = self.Sbox(state)
            state = self.Permute(state)
            state = self.AddKey(state)
        return state

The goal of the challenge is to craft a valid cleartext/ciphertext pair, after having performed three encryption / decryption queries (of the user's choice) with an oracle.

TLDR

This challenge is solved with differential cryptanalysis. The S-Box of the block cipher has a serious weakness, as the following properties hold for any $x \in [0, 255]$:

Moreover, these constants play well with the permutation layer, as there are arrangements of these "post S-Box" diffs that fallback to "pre S-Box" diffs after the permutation layer. For instance, $Perm([0, 134, 0, 129, 0, 0, 0, 134, 0, 0, 0, 0, 0, 0, 0, 0]) = [0, 0, 74, 0, 0, 0, 0, 0, 82, 0, 0, 24, 0, 0, 0, 0]$.

It is even possible to construct a cycle $(d_1, d_1', d_2, d_2', d_3, d_3')$, where $S(d_1) = d_1'$, $Perm(d_1') = d_2$, $S(d_2) = d_2'$, $Perm(d_2') = d_3$, $S(d_3) = d_3'$ and $Perm(d_3') = d_1$. The diffing bits can be followed through the first 20 rounds of enc/dec.

We can thus ask for the encryption of a pair $(a_0, a_1 = p_0 \oplus d_1)$ differing by $d_1$, and get $c_i = Encrypt(a_i)$ for $i \in {0, 1}$, as well as ask for the decryption of $c_2 = c_1 \oplus d_1$ to get $a_2 = Decrypt(c_2)$. The pair $(m = a_2 \oplus d_1, c = c_0 \oplus d_1)$ is a valid input/output pair that has not been requested.

Detailed write-up

When facing a challenge based on a custom symmetric cipher, the first step should be to inspect the S-Box (following this great tutorial for example). Here, the Differential Distribution Table will be helpful. The Differential Distribution Table (DDT) shows the repartition of the difference in the output, given a difference in the input. For instance, the value at row 3 and column 7 of the table gives the number of values $x$ for which $S(x) \oplus S(x \oplus 3) = 7$ is true. In our case, the DDT looks really fishy:

S-Box DDT

Keep in mind that the DDT of a good S-Box is supposed to look like random noise!

Apart from the obvious structures, do you see the little black dots? They correspond to rows where an input difference produces a single output difference. Indeed, we can check that for any $x \in [0, 255]$:

We can follow an input difference through the first AddKey, Sbox, Permute, AddKey procedure. But surely the diffs are all scrambled by the Permute step, and we cannot follow them through a second round of Sbox !

Note that the AddKey step does not affect the diffs, because if $s_1 = s_0 \oplus d$, then $s_1 \oplus K = (s_0 \oplus d) \oplus K = (s_0 \oplus K) \oplus d$

At this point, I noted that the number of 1 bits stays constant on each side of the pair: 24 has two 1 bits and so does 129, 74 and 82 both have three 1 bits and so does 7 and 134. This nudged me towards inspecting the permutation layer, with a thought in mind: What if there exist permutations of these "post S-Box" constants giving back only "pre S-box" constants?. Indeed, if such a permutation existed, we could feed the second Sbox round with "pre S-box" diffs, giving us once more these known output diffs.

There are $4^{16} = 2^{32}$ possible arrangement of "post S-box" diffs states, let's feed them all through the Permute routine and see what comes out.

Fold
diffs_preS = [0, 24, 74, 82]
diffs_postS = [0, 129, 7, 134]
for i in range(4**16):
    input = bytes([diffs_postS[(i>>(2*j))&3] for j in range(16)])
    output = [int(o) for o in Permute(input)]
    if all(o in diffs_preS for o in output):
        input = [int(o) for o in input]
        print("Found diff!", input, output)

Found diff! [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Found diff! [134, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 74, 0, 0, 0]
Found diff! [0, 134, 0, 129, 0, 0, 0, 134, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 74, 0, 0, 0, 0, 0, 82, 0, 0, 24, 0, 0, 0, 0]
Found diff! [134, 134, 0, 129, 0, 0, 0, 134, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 74, 0, 0, 0, 0, 0, 82, 0, 0, 24, 74, 0, 0, 0]
[...]

This takes a while to run, we can stop it here. So we have such arrangements, letting us follow the input diffs through one more round. For instance, to exploit the third diff arrangement found, we can do the following:

diff_preS = [0, 82, 0, 24, 0, 0, 0, 82, 0, 0, 0, 0, 0, 0, 0, 0] # later called d_1
diff_postS = [0, 134, 0, 129, 0, 0, 0, 134, 0, 0, 0, 0, 0, 0, 0, 0] # later called d_1'
diff_postSP = [0, 0, 74, 0, 0, 0, 0, 0, 82, 0, 0, 24, 0, 0, 0, 0] # later called d_2
diff_postSPS = [0, 0, 7, 0, 0, 0, 0, 0, 134, 0, 0, 129, 0, 0, 0, 0] # later called d_2'

To follow this diff further, we would need the diff_postSPS to be yet another arrangement where all "post S-box" constants map to "pre S-box" constants. By any chance, does our diff match this property ?

out = Permute(bytes([0, 0, 7, 0, 0, 0, 0, 0, 134, 0, 0, 129, 0, 0, 0, 0])) # Permute(d_2')
print([int(o) for o in out])
# [0, 0, 0, 0, 0, 74, 0, 0, 0, 0, 24, 0, 0, 74, 0, 0] (later called d_3)

It does, wonderful! Let's push this one more round further:

out = Permute(bytes([0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 129, 0, 0, 7, 0, 0])) # Permute(d_3')
print([int(o) for o in out])
# [0, 82, 0, 24, 0, 0, 0, 82, 0, 0, 0, 0, 0, 0, 0, 0] (recognize d_1)

Looks like we are back to our first arrangement. So we found a cycle $(d_1, d_1', d_2, d_2', d_3, d_3')$, such that $S(d_1) = d_1'$, $Perm(d_1') = d_2$, $S(d_2) = d_2'$, $Perm(d_2') = d_3$, $S(d_3) = d_3'$ and $Perm(d_3') = d_1$.

This means that if we input two values $a_0$ and $a_1$ (differing by $d_1$) into the Jafar encryption routine, we can follow the diff through the first 20 rounds, until just before the Middle routine.

Following the diff through the first 20 rounds of Encrypt

The Middle routine, being a Galois-field multiplication, is linear: as $GF(a)GF(b \oplus c) = (GF(a)GF(b)) \oplus (GF(a)*GF(c))$, we have $\text{Middle}(a \oplus b) = \text{Middle}(a) \oplus \text{Middle}(b)$. However, we lose track of the diffs after the first round of Sbox after Middle, as we have no way of knowing $\text{Middle}(d_3)$

Following the diff through Middle and losing it afterwards

We can follow the diffs using the same techniques in the Decrypt routine.

Following the diff through the first half of Decrypt

I introduced a new variable to conclude this challenge; it is just an ease of notation, to clarify the final steps. Let $b_i'$ be the state just before the invMiddle routine, and $b_i$ the state just after the invMiddle routine. Conveniently, we will use the same notations for the Encrypt procedure, where $b_i$ is the state just before the Middle routine, and $b_i'$ the state just after the Middle routine. To sum up, let's say $b_i' = \text{Middle}(b_i)$, which is equivalent to $b_i = \text{invMiddle}(b_i')$

Now, when we use our first two wishes to encrypt $a_0 = [0, \dots, 0]$ and $a_1 = a_0 \oplus d_1 = d_1$, we have the following properties:

With a high-level intuition, we need to use our third wish to "learn" relations in the ciphertext-side. To do so, we can ask to decrypt $c_2 = c_1 \oplus d_1$. This will give us the following relations:

Let us rewrite $b_1$ in terms of what we learned from the encryption of $a_0$ and $a_1$:

Now, imagine following the diffs in a pair of encryptions $(a_2, a_3 = a_2 \oplus d_1)$. We would have the following:

$b_3'$ and $b_0'$ only differ by $d_2$, and we know that it corresponds to a difference of $d_1$ in the ciphertexts (go back to the schematics about following diffs in Decrypt if this sounds made-up :D). So the pair $(a_2, a_3 = a_2 \oplus d_1)$ produces ciphertexts $(c_2, c_3 = c_0 \oplus d_1)$, and with that we have crafted a valid ciphertext $c_3$ :-)

Fold
$ python3 solve.py 
I am an oracle. I can encrypt or decrypt any data through my carefully designed block cipher.
You have three wishes, then you should provide a matching input/output pair (that you have not already requested, of course)!
You have 3 wishes remaining:
 - For encryption, type "enc".
 - For decryption, type "dec".
What is your wish?
>>> enc
Understood. Please send your data (hex format).
>>> 00000000000000000000000000000000
Here is your requested data:
231851bba3447301e45c8cb195930549
You have 2 wishes remaining:
 - For encryption, type "enc".
 - For decryption, type "dec".
What is your wish?
>>> enc
Understood. Please send your data (hex format).
>>> 00520018000000520000000000000000
Here is your requested data:
2940a0950c27835274f036ea979b9519
[exploit-logs] Calculating c_2 = xor(c_1, d_1)
You have 1 wishes remaining:
 - For encryption, type "enc".
 - For decryption, type "dec".
What is your wish?
>>> dec
Understood. Please send your data (hex format).
>>> 2912a08d0c27830074f036ea979b9519
Here is your requested data:
24cd838bb212aed2c5050d6a6bae6be5
[exploit-logs] Calculating a_3 = xor(a_2, d_1)
[exploit-logs] Calculating c_3 = xor(c_0, d_1)
Now, show me a correct input/output pair that you have not requested:
>>> 249f8393b212ae80c5050d6a6bae6be5
>>> 234a51a3a3447353e45c8cb195930549
Congrats! Here is the flag:
FCSC{4185***[...]***58cf}

Thought process while solving the challenge