# Does the key schedule function need to be a one-way function?

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.

-
Good point. I'm not really interested in implementation though, I'd like to know what happens from a more theoretical perspective. –  rath Dec 25 '13 at 21:02
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] –  fgrieu Dec 25 '13 at 21:14
...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. –  rath Dec 25 '13 at 21:22
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. –  fgrieu Dec 25 '13 at 21:26
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). –  Reid Dec 25 '13 at 22:01

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.