0
$\begingroup$

From section 4.4 of this book https://www.ic.unicamp.br/~rdahab/cursos/mo421-mc889/Welcome_files/Stinson-Paterson_CryptographyTheoryAndPractice-CRC%20Press%20%282019%29.pdf

I'm confused on how the differential trail is formed given they don't know the round key. I would love if someone could give a clear example of how this attack actually works. They mention you can calculate the output xor without knowing the round key but thats for one S-box , what about the other ones etc.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If you can see that for a single Sbox the differential is independent of the input, the same holds for a collection of Sboxes forming the differential trail.

That example is directly from Heys' tutorial on linear and differential cryptanalysis:

https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf

Please read his differential cryptanalysis section. An important focus here is the extraction of the key bits. Heys starts the extraction at the end of the cipher, he wants to recover the last subkey. He is doing it by trying to decrypt the last round and testing some hypotheses about the intermediate subkey bits of the input to that round.

Thus there is no assumption of obtaining any outputs of an internal round at all.

Having done the analysis, he submits enough plaintext pairs with fixed difference $\Delta P$ so that he can be sure with high probability that the most common ciphertext difference is $\Delta C$.

Note that in his example, the 2nd and 4th Sboxes are active, so the target key bits are those at the output of Sboxes $S_{4,2}$ and $S_{4,4}$.

Now he can do a loop where he tries all the $2^8$ possible key bit hypotheses $$(\widehat{K_{5,5}},\widehat{K_{5,6}},\widehat{K_{5,7}},\widehat{K_{5,8}},\widehat{K_{5,13}},\widehat{K_{5,14}},\widehat{K_{5,15}},\widehat{K_{5,16})},$$ and under each hypothesis (since he knows the ciphertexts) he can determine the hypothetical differentials (correct subject to the key guess being correct) at the output of the Sboxes $S_{4,2}$ and $S_{4,4}$ which by inverting the Sboxes can be converted to hypothetical input differences of the form $\Delta U_{4,5},\ldots,\Delta U_{4,16}$.

Whichever key combination gives the most likely differential $$\Delta U_4=[0000~0110~0000~0110]$$ is declared the most likely key guess for the last round. So he would keep a count corresponding to each hypothesized round 5 key as the loop runs and check which value gave the maximum count.

Then the rounds can be peeled off one by one.

Improve this answer
$\endgroup$
12
  • $\begingroup$ In that tutorial he mentioned that the output difference of some round = input difference of next round, so I guess that answers it maybe $\endgroup$
    – Simon Balfe
    Commented Mar 12, 2023 at 13:26
  • $\begingroup$ yes of course, otherwise how can you build a trail that is consistent? $\endgroup$
    – kodlu
    Commented Mar 12, 2023 at 13:35
  • $\begingroup$ and he also has the ability to look at inputs and outputs for each S-box in an SPN and obtain the reverse ofc $\endgroup$
    – Simon Balfe
    Commented Mar 12, 2023 at 15:25
  • $\begingroup$ In the key bit extraction, does he simply then as you said just have 256 different keys to test from which he XOR's with the ciphertext then passes through the inverted S-box then the XOR of the two ciphertexts passing through this S-box inversion is compared to the differential characteristic that is statically defined i presume and if they match then they increment that key? $\endgroup$
    – Simon Balfe
    Commented Mar 12, 2023 at 15:54
  • $\begingroup$ Yes, and $2^8$ comes from only 2 sboxes being active at the input to the last round, this saves computation. $\endgroup$
    – kodlu
    Commented Mar 12, 2023 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.