1
$\begingroup$

The context is iterated ciphers.

Regarding Differential and Linear Cryptanalysis, the methods seem to make a cryptanalyst able to do an educated guess on a partial subkey (e.g. bits from the last round key). What I am struggling to grasp is how practically break a cipher with that knowledge. Is perhaps that one could obtain the key "cracking" the key schedule or one should break all internal round one by one (recovering more and more partial subkeys)? Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

This will depend on the key schedule of the design, but they are usually relatively simple expansion algorithms. In particular the initial round keys are often the actual bits of the cryptovariable and so recovering the initial round key recovers the first bits of cryptovariable (additional bits of cryptovariable can then be guessed exhaustively with less work than guessing the full cryptovariable). It is also common for key schedules to be invertible (so that the previous round key can be computed from the current round key - this allows decryption to be implemented efficiently in small memory). This means that if we recover all of the last round key, we can usually invert the key schedule to get the penultimate round key, the ante-penultimate round key and so on, back to the initial round key (which is often the crypto variable itself). Even if the cryptovariable size is larger than the round key recovered, the additional bits can typically be exhaustively recovered with less work than full exhaustion.

All of the above does depend on the choice of key schedule by the designer, but it does apply to major designs such as AES, DES, Serpent, and Twofish.

$\endgroup$
2
  • 1
    $\begingroup$ I think this answer missing an important point. Even if the key schedule is not invertible when an attacker is able to find the last round key with differential and linear attack, then attacking the previous round is key is much easier than the last round and so on. Therefore there is no need for non-reversible key schedule in the view of diff&linear attacks. $\endgroup$
    – kelalaka
    Dec 29, 2021 at 20:26
  • $\begingroup$ Is this a theorem (or a class of theorems)? This "much easier" can be quantified? Thank you so much. $\endgroup$ Feb 20, 2023 at 10:51

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.