3
$\begingroup$

I am currently working on some research about differential cryptanalysis. There is a lot of literature about that topic in the internet. One of the most known paper is the tutorial on linear and differential cryptanalysis by Howard M. Heys. May be some of you know that paper, if not have a look here:

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

In the meanwhile I got a good idea about the attack and how it can be practically done. In the most tutorials on the net the process works a little bit different as by Heys. My focus here is the extraction of the key bits. This part is described in section 4.4 in the Heys paper. 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 (How can the other keys be obtained? Heys does not tell about). As far as I currently understand the differential cryptoanalysis, it is not possible to encrypt single rounds (until now I read the paper of Heys). Because: All I have are some plaintext / ciphertext pair which I could obtain from the user of the cipher. The user encrypts with the key which I want to recover by doing the attack. So it should not be possible to obtain single outputs of a specific round or decrypt a single round by the user. (Me as an attacker should not be able to interfere the decryption and get input / outputs of a round while the user uses the algorithm) Is my guess here wrong? How could the partial decryption could be done? I am referring to page 26 "A partial decryption..." and so on. Or what is Heys here doing?

Thanks for your attention and help.

Improve this question
$\endgroup$
4
  • $\begingroup$ Statistical characteristic of R-1 rounds is used by decrypting only the last round. So the input for the round R-1 is probabilistic and the output is deterministic. The attack is nice since it can concentrate on partial keys. $\endgroup$
    – kelalaka
    Apr 1, 2019 at 20:41
  • $\begingroup$ so the other rounds can be attacked in the same way, right? Until now I read a lot of tutorials where the attack is started with the first round and goes from there further through the cipher. $\endgroup$
    – chris000r
    Apr 1, 2019 at 20:45
  • $\begingroup$ once you get the key of the last round, the rest will be easier, since the probabilities will be better. If the keys schedule weak, you can get the key directly. $\endgroup$
    – kelalaka
    Apr 1, 2019 at 20:46
  • $\begingroup$ Can you also tell me something about the way of Hays is doing it? In my opinion the attacker is not able to decrypt single rounds of the cipher. $\endgroup$
    – chris000r
    Apr 1, 2019 at 20:49

1 Answer 1

Reset to default
1
$\begingroup$

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

Having done the analysis, the attacker 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 as in the comments.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you for your comment. for me the paper reads as if one would have to decode internal rounds. If that's not the case, that's good. Delta-C means the output difference of the whole cipher and not of a single round, right? I understand the point that we only look at the sbxes of the last round that produce output. So the key space to investigate is very small. $\endgroup$
    – chris000r
    Apr 2, 2019 at 7:26
  • $\begingroup$ Can you describe your last 2 sets in more detail? What do we exactly do? For all cipertexts (which satisfy the output difference Delta-C) (which we have observed) do we undo the last round of the sboxes (s4,x) and count how many times the input difference is satisfied with a given key? The key with the most frequent count value is the key? But I don't know the real key until I can decrypt the whole ciphertext. So there are still some partial keys missing before you can say that you have the real key. $\endgroup$
    – chris000r
    Apr 2, 2019 at 7:26
  • $\begingroup$ Can you also say more precisely how to decrypt the round keys before it? Because round N depends on round N-1? $\endgroup$
    – chris000r
    Apr 2, 2019 at 7:26
  • $\begingroup$ No you start from the beginning and the end and meet in the middle, at the output of round 3. $\endgroup$
    – kodlu
    Apr 2, 2019 at 7:30
  • $\begingroup$ Let's assume you have found the most likely subkey bits targeted above [say you have enough P/C pairs to be confident]. Then, you shall need to find another differential characteristic which has Sboxes S_{4,1}, and S_{4,3} active. This can be done. And now you have all the round 5 keys. Etc, etc. $\endgroup$
    – kodlu
    Apr 2, 2019 at 7:34

Your Answer

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

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