How exactly does key whitening manage to increase security?

Question

Wikipedia states that key whitening increases security:

In cryptography, key whitening is a technique intended to increase the security of an iterated block cipher. It consists of steps that combine the data with portions of the key.

The most common form of key whitening is xor-encrypt-xor -- using a simple XOR before the first round and after the last round of encryption.

But Wikipedia does not explain in what way exactly key whitening manages to increase security.

Reducing it to a minimum, it seems as if the most used form of key whitening is a triple-encryption using a XOR-cipher + Other-Encryption-Algorithm + XOR-cipher combination. A XOR can be reversed rather easy (which is why XOR-ciphers aren’t all too secure), so how does key whitening manage to increase security using two simple XOR steps like that? Does it really make the cipher stronger in some special way, or is key whitening just an obfuscation-step to give attackers a hard time?

Answer 1

While it may be confusing, that Wikipedia article is actually correct! Let me try to explain it a bit better…

Definition of key whitening

Key whitening is an extremely simple technique to make block ciphers like DES much more resistant against brute-force attacks. Like you’ve already discovered yourself, this is the basic scheme:

Or, defining it a bit more mathematically…

Encryption: $y = e_k,k_1 ,k_2 (x) = e_k (x \oplus k_1 ) \oplus k_2$
Decryption: $x = e_k^{-1},k_1 ,k_2 (x) = e_k^{-1} (y \oplus k_2 ) \oplus k_1$

In addition to the regular cipher key $k$, two whitening keys $k_1$ and $k_2$ are used to $\oplus$ (XOR-mask) the plaintext and ciphertext.

Security added by key whitening

Now, it is important to stress that key whitening does not strengthen block ciphers against most analytical attacks such as linear and differential cryptanalysis.

So, your observation/interpretation is somewhat correct.

Key whitening indeed isn’t a “cure” for inherently weak ciphers or something like that. Its use only makes sense when ciphers are relatively strong against analytical attacks, but possess a too short key space.

Trying to use your wording: key whitening can only increase security by strengthening a cipher where its key space is too short. That’s it. When it comes to increasing security, you won’t gain anything else from a key whitening step.

Ciphers using key whitening

A prime example of such a cipher would be DES. A variant of DES which uses key whitening is DES-X. In the case of DES-X, the $k_2$ is derived from $k$ and $k_1$.

If you take a look around, you will notice that most modern block ciphers already apply key whitening internally by adding a sub-key prior to the first round and after the last round… prime example: AES.

_{An aside: In case you want to dig in deeper, it might be interesting for you to check out books like “Understanding Cryptography” by Bart Preneel, Christof Paar, and Jan Pelzl; or “The Block Cipher Companion” by Lars R. Knudsen, and Matthew Robshaw.}

Answer 2

One way key whitening improves security is by increasing resistance to bruteforce attacks (and doing this essentially for free). Consider, for example, DES. Key is 56 bits, so given a single pair $(M, E=DES(K,M))$ attacker will find $K$ in $2^{55}$ operations on average.

By employing key whitening it is possible to increase required effort substantially: we extend key by 128 bits (2 times block size) and use those additional key bits to mask (whiten) plaintext and ciphertext. This scheme is essentially DES-X: $DES\unicode{x2d}X(K, M) = K_3 \oplus DES(K_1, K_2 \oplus M)$ where $K$ is a concatenation of $K_1$, $K_2$, and $K_3$ and $\oplus$ is XOR.

Now, if attacker gets a pair $(M, E=DES\unicode{x2d}X(K, M))$ he will have to brute-force $2^{183}$ operations on average (and the legitimate encryption/decryption only costs two extra XORs).

Note that whitening is part of the encryption algorithm itself and thus it's assumed that attacker cannot observe input after whitening or output before whitening (in this case whitening keys are trivially recovered).

Edit: As @otus pointed out, the security bound for $DES\unicode{x2d}X$ quoted in this paper is $2^{118-lg(m)}$.

Edit: It seems the confusion behind "Key Whitening" is caused, at least partially, by the imprecise title of the Wikipedia article. What it describes is effectively a data whitening, not key whitening. @otus pointed out in comments that this might be due to Rogaway using terms "pre-whitening key" and "post-whitening" key in his work (link above), which sounds plausible to me. Section in Bruce Schneier's "Applied Cryptography" describing this concept is simply called "Whitening".