More About Block Ciphers - Understanding Cryptography - page 140

Fig. 5.12 Key whitening of a block cipher

Definition 5.3.1 Key whitening for block ciphers
Encryption :y = e k , k 1 , k 2 ( x )= e k ( x ⊕ k 1 ) ⊕ k 2 .

Decryption :x = e − 1

k , k 1 , k 2 ( x )= e − 1

( y ⊕ k 2 ) ⊕ k 1

k

It is important to stress that key whitening does not strengthen block ciphers
against most analytical attacks such as linear and differential cryptanalysis. This
is in contrast to multiple encryption, which often also increases the resistance to
analytical attacks. Hence, key whitening is not a “cure” for inherently weak ciphers.
Its main application is ciphers that are relatively strong against analytical attacks
but possess too short a key space. The prime example of such a cipher is DES. A
variant of DES which uses key whitening is DESX .InthecaseofDESX,thekey k 2
is derived from k and k 1 . Please note that most modern block ciphers such as AES
already apply key whitening internally by adding a subkey prior to the first round
and after the last round.
Let's now discuss the security of key whitening. A naıve brute-force attack
against the scheme requires 2 κ+2 n

is the bit length of the key
and n the block size. Using the meet-in-the-middle attack introduced in Sect. 5.3,
the computational load can be reduced to approximately 2 κ+ n steps, plus storage
of 2 n data sets. However, if the adversary Oscar can collect 2 m plaintext-ciphertext
pairs, a more advanced attack exists with a computational complexity of

search steps, where κ

2 κ+ n − m

cipher operations. Even though we do not introduce the attack here, we'll briefly
discuss its consequences if we apply key whitening to DES. We assume that the at-
tacker knows 2 m plaintext-ciphertext pairs. Note that the designer of a security sys-
tem can often control how many plaintext-ciphertext are generated before a new key
is established. Thus, the parameter m cannot be arbitrarily increased by the attacker.
Also, since the number of known plaintexts grows exponentially with m , values be-
yond, say, m = 40, seem quite unrealistic. As a practical example, let's assume key
whitening of DES, and that Oscar can collect a maximum of 2 32 plaintexts. He now
has to perform

2 56+64 − 32 = 2 88