What are the requirements of a key schedule?

Question

In the first block cipher I designed I used a CSPRNG to generate the round keys. The purpose was to at least have a chance of creating a (hopefully!) secure cipher on the first try (but please don't use it in production).

One criticism I got was that the key schedule was too expensive. This made me wonder: what are the actual requirements of a key schedule? Clearly a CSPRNG is overkill. I want to know what the actual requirements are. What is required of a key schedule?

I know:

• Every bit of the key should ideally effect each round key.
• As always, speed and simplicity are desirable.

Answer 1

Desirable Properties

There are a few papers and resources related to key schedule design out there.

From this paper from 2012 we can highlight some of the following points:

• Key bits should be uniformly used
• All subkeys should be "equally good"
• It is "hard" to find any remaining key bits from any known key bits.
• Hard to invert
• If possible every key bit should affect nearly every round in different ways
• No equivalent keys
• Collision-freedom (standard hash function properties)
• No dead spots
• Equally powerful effect of every key bit on the subkeys.
• Low implementation cost
• Minimal mutual information between all subkey bits and master key bits

Which the paper then basically summarizes with:

First, key schedules should have no bit leakage in the level of "round", or of the whole key schedule. The former means they only consider leakage between different rounds of subkeys, or between some rounds of subkeys and master keys. When an recursive key schedule is invertible or when subkeys are direct transformation from master key, above leakage cannot be avoided. The latter means that no subkey bits can be derived easily whatever key knowledge is obtained

They then go on to define terms and techniques which are more in depth in relation to cryptanalysis of key schedules.

This paper appears to build on the work of the previous one, but I cannot access it.^[1]

This paper concludes mostly the same things:

• Maximize avalanche in the subkeys and avoid linear key schedules.
  • Though the authors note: "As an open question, we note that the DES key schedule is linear, and wonder why it appears to resist related-key attacks"
• Every key bit should affect nearly every round, if possible, but not in exactly the same way
• The key schedule should be designed to resist differential attacks.

Key Schedule Classification

This last paper had some different material that is also interesting. They classify the key schedules of algorithms into two types, with subclasses of those types. The types are defined by whether or not knowledge of round key bits reveals knowledge of any other round key bits, or the master key.

• A Type 1 key schedule allows recovery of other round key/master key information if some round key information is known
• A type 2 key schedule does not allow recovery of other round key/master key information if some round key information is known

They further go on to define sub types, A, B, and C.

• A Category 1, Type A cipher (1A) is one in which all bits of the master key are used in each round, and hence knowledge of a round subkey yields all bits of the master key and all other round subkeys. The cipher NDS [3] is such an example.
• A 1B cipher is one where knowledge of a round subkey gives some, but not all bits of the master key or other round subkeys. DES is an example.
• A 1C cipher is one in which knowledge of a round subkey yields bits of other round subkeys or the master key after some simple arithmetic operations or function inversions. SAFER K-64 [6 ] is an example.
• A 2A cipher is one in which not all bits of the master key are used to create each round subkey . In these ciphers, certain master keys are guaranteed to produce at least two identical round keys. A cipher such as CAST-128 [7] is an example. In other words, the entropy of the round subkeys is not maximised.
• A 2B cipher is one in which all master key bits are used in the determination of all round subkeys, thus maximising the entropy of the subkeys. An example is Blowfish [8].
• The most secure schedule classification is 2C. However, this may lead to unmanageably large master keys for ciphers whose security cannot hope to match what is naively suggested by the key length. Further, export restrictions on cryptographic materials often limit the size of the key. For these reasons, the best we can hope for is to mimic 2C schedules as closely as possible, with the next strongest classification, 2B.

Efficiency with embedded devices

While one way functions are recommended as part of a key schedule, there is a downside if they are used a certain way. If only noninvertible functions are used in deriving round keys, then decryption will require the algorithm to generate all its key material at the beginning. On a general purpose computer this is not really a concern, however, on embedded devices with limited gate counts/surface areas, the excess storage can become problematic. The storage requirement will increase by the round key size per round. This will lead to a higher unit cost.

The best solution I am aware of is to split the key schedule into two parts, an invertible part, and an uninvertible part. The invertible part is used to generate round key material in a way that is friendly to on the fly processing, while the uninvertible part of applied just before usage of the round key. This maintains the best of both worlds, in that embedded devices can decrypt with an on-the-fly key schedule and the cipher can have the protection a non invertible key schedule offers. This is potentially a small change that will improve the applicability of the cipher towards smartcards and the like.

^{[1] Free version added.}