Score:0

Differential trails in differential cryptanalysis

ir flag

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.

Score:1
sa flag

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.

Simon Balfe avatar
ir flag
In that tutorial he mentioned that the output difference of some round = input difference of next round, so I guess that answers it maybe
kodlu avatar
sa flag
yes of course, otherwise how can you build a trail that is consistent?
Simon Balfe avatar
ir flag
and he also has the ability to look at inputs and outputs for each S-box in an SPN and obtain the reverse ofc
Simon Balfe avatar
ir flag
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?
kodlu avatar
sa flag
Yes, and $2^8$ comes from only 2 sboxes being active at the input to the last round, this saves computation.
Simon Balfe avatar
ir flag
What I would ask now is why is it the case that the 1 and 3 outputs are 0000 is this just for this example and thus influencing what is a right pair for the filtering process
Simon Balfe avatar
ir flag
Also, can they select any S-box and obtain the values for the difference distribution table for it or do they have to feed it starting from the plaintext difference?
kodlu avatar
sa flag
The whole process has to be consistent as you go down the rounds starting with the plaintext difference. Otherwise how could it work? Read the tutorial again, the way differences are linked across rounds is by *canceling* common terms between consecutive rounds which cannot happen unless they match.
Simon Balfe avatar
ir flag
Okay yeah so when they have one S-box they pass in some specific input difference to obtain an output difference which is then passed to the next round and this is done for each S-box of each round to get the distribution table ig
Simon Balfe avatar
ir flag
Also like is this just one example like there could be theoretically no 0000 in the final round and the entire round 5 key will be used right rather than just the ones that interact with 2 S-boxes
Simon Balfe avatar
ir flag
Is the choice of which boxes are active and thus whic key bits are targeted based on the differential characteristic choice and if so then how do we get the full key bits if its only for 2 S-boxes, surely this does not complete round 5's key
kodlu avatar
sa flag
It does not. Read the tutorial.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.