3
$\begingroup$

For some key schedule $e_n(e_{n-1}(k))$ (where $e_{n-1}(k)$ is the result of the previous round) , does $e$ need to be a one-way function?

In the case of DES or Rijndael the key schedule doesn't really look like one, as the adversary only has to reverse the operations to get the input.

My question is this:

In the case of the well-studied Rijndael,

  • What are the implications of replacing the iterated schedule $e_n()$ with a one-way function $f$?

My guess is it would increase linearity, leading to a weak cipher. So,

  • What if we added a one-way component to $e$ such that

$$e(x) \leftarrow s( r (f (x))) $$

where $s()$ and $r()$ are the s-box and bit-shift functions respectively.

Note: I ask about Rijndael where I really mean any block cipher that is secure, eg. Rijndael but I'm not exactly sure how to phrase that.

|improve this question
$\endgroup$
  • $\begingroup$ Good point. I'm not really interested in implementation though, I'd like to know what happens from a more theoretical perspective. $\endgroup$ – rath Dec 25 '13 at 21:02
  • 1
    $\begingroup$ One implication of replacing the key schedule of Rijndael by a one-way function is that a minimum-storage hardware implementation that needs to decipher becomes more complex, because it is no longer possible to walk back the key schedule. The options are to store the derived keys, or perform much more key schedules (or some compromise between these). In the basic 128-bit key, 10-round variant we are already talking about a non-trivial 1280 extra latches, or 55 one-way key schedules rather than 10 forward and 10 backward. [reposted with correction so that above comment applies to this] $\endgroup$ – fgrieu Dec 25 '13 at 21:14
  • $\begingroup$ ...which would also provide a much wider side-channel attack surface. Indeed I doubt it would've been the AES finalist if it was too expensive. $\endgroup$ – rath Dec 25 '13 at 21:22
  • 3
    $\begingroup$ In Rijndael the key schedule is bijective, not one-way, so the answer to the question is obviously no when needed is taken as needed to become AES. $\endgroup$ – fgrieu Dec 25 '13 at 21:26
  • 2
    $\begingroup$ I think replacing the key schedule with a one-way function is actually ideal; it's just too expensive in practice. This paper seems to agree (published here). $\endgroup$ – Reid Dec 25 '13 at 22:01
4
$\begingroup$

As fgrieu already pointed out, using a OWF in the way you describe would make the key schedule not efficiently invertible (or even not invertible at all), meaning you would need more memory/chip space to store the user-input key in order to efficiently encrypt more than one block.

In terms of other implications, if the key-state update function $e_n(\cdot)$ is non-surjective then the later round keys will have less entropy than the user-input key, and hence may be guessed with less effort than with the current AES key schedule. This could make the last rounds easier to peel off.

However, if $e_n(\cdot)$ is such that every output bit is a high degree non-linear function of every input bit, then any such loss of entropy would likely be very difficult to exploit, and also would likely make related key and biclique attacks more difficult.

You should also be aware that OWFs can be used in the key schedule in a different way than you describe -- i.e. as round key extractors instead of as key-state update functions. So you might have a permutation (perhaps even a linear one) to update the key-state between each round, but then derive each round key from the key-state using a OWF. As a concrete (but slow) example, your key-state update function might be to add 1 (or some other constant) to the user-input key between each round, and then extract the current round key from that by hashing the key-state with a cryptographically secure hash function like SHA-256. As a much faster example, Serpent uses a linear key-state update function, and non-linear round-key extractors (though in that case they are non-linear permutations using the Serpent s-boxes instead of OWFs).

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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