What are the requirements of a key schedule? 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.
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.