Motivation / Introduction
In cryptography, secret key algorithms (like block ciphers and stream ciphers) often need a reasonably large amount of secret data. For example, in block ciphers it is pretty much necessary that a different sub-key be used in each round of the cipher. Other ciphers, like Blowfish and Twofish, need large, key-dependent S-Boxes.
However, it is highly inconvenient to have to use a 4000 bit key for a symmetric cipher. For one thing, it is highly unlikely that the cipher is actually strong enough to warrant a key that large - we (and by we I mean the public community of cryptographers, of which I am not) only know how to make ciphers which have about 2256 strength against attack (and even that is a bit of a stretch). In addition, transmitting a very large key is quite a challenge, as most public key encryption schemes (like RSA and ElGamal) can only encrypt a message which is smaller than the bit size of the group the operation is performed in. Using a 4096 bit RSA modulus is much, much slower than using a 1024 or 2048 bit RSA modulus.
Lastly, there are actually security concerns as well. If the RNG creating this very large key has a bias of some sort, the algorithm's strength could be in serious jeopardy. Indeed, some ciphers (like MARS) require that some of the sub-keys have a particular structure.
Thus, all modern ciphers have a so-called key schedule, which transforms a smaller input key (usually in the range of 40 to 256 bits) into as much keying information as the particular algorithm desires.
Examples
For example purposes, I'll show how the key schedules of IDEA and Blowfish work.
IDEA
IDEA's key schedule takes as an input a 128 bit key, and produces a number of 128 bit sub-keys. Each sub-key is produced by simply rotating the previous sub-key to the left by 25 bit positions. This choice has caused endless problems for IDEA, including related key attacks and several classes of weak keys.
Blowfish
Blowfish, on the other hand, uses a key schedule that is (while conceptually quite simple) extremely complicated to attack. Blowfish requires 5 tables of 32 bit integers be filled in: S1, S2, S3, S4, and P. The S tables each have 256 elements, while the P table has 18 elements. The key schedule can take a key of any size smaller than 448 bits.
First, initialize P and the S tables with the hexadecimal values of pi. Concatenate the key with itself enough times to produce 576 bits, and XOR it with the elements of the P table.
Then, using the P and S tables described above, encrypt the all-zero string, and replace P[0] and P[1] with the ciphertext. Then encrypt the previous ciphertext using the newly modified sub-keys, replacing P[2] and P[3] this time. Continue this process with all the elements of the P array, followed by all of the S-boxes (in order).
This key schedule is slow, inelegant, and quite secure.
Bad Key Schedules Break Ciphers
Many good ciphers have fallen to attacks based on poorly chosen key schedules. For example, each of DES's sub-keys is 48 bits of the 56 bit input key, shuffled around. By recovering a single round sub-key (eg, with linear cryptanalysis), the entire 56 bit key can be easily recovered (by simply search the remaining 8 bit keyspace by brute force, an attack that would take seconds at most). AES also suffers from this problem, and some attacks have been developed which (while totally impractical) show that AES can be attacked faster than brute force. These attacks rely heavily on the fact that AES's key schedule is not very good.
Properties of Good Key Schedules
A good key schedule should be fast, simple to understand and code, and above all secure. Specifically, the following conditions should hold:
- Given all but one of the sub-keys, it is impossible to determine the remaining sub-key.
- Given all of the sub-keys, it is impossible to determine the master key.
- Each sub-key bit is a random function of all of the bits of the master key.
- A single bit change in the master key will, on average, flip half of the bits of each sub-key, in an unpredictable manner.