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.

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.