Code book attack

In a code book attack on a block cipher, the attacker tries to build up a "code book", a table saying which ciphertexts correspond to which plaintexts.

For example, consider a cipher with only an 8 bit block size. Assume the enemy is able to get or guess some plaintext; he makes a little table, his own "code book" showing which ciphertext blocks correspond to which plaintexts. If he can fill in all 256 entries, then the cipher is broken; he can read everything sent with that key. Such tiny block sizes are therefore never used; real ciphers all have block sizes of at least 64 bits.

Even a partially filled in code book weakens the cipher. When the code book has around 2^blocksize/2 entries, the chance that two entries will be the same, giving the enemy some information, becomes significant: see birthday paradox. For this reason, any block cipher must be re-keyed before 2^blocksize/2 blocks as an absolute upper limit. The general practice is to re-key long before that.

Like a brute force attack (try all possible keys) or an algebraic attack (write the cipher as a system of equations and solve for the key), a code book attack (collect all possible plaintext/ciphertext pairs) will in theory break any block cipher. However, all of those attacks are spectacularly impractical against real ciphers. Brute force and algebraic attacks require the attacker to do far too much work. For a code book attack, he needs very large amounts of storage and a large collection of intercepts, all encrypted with the same key. If the cipher user changes keys at reasonable intervals, a code book attack is impossible.

DES and the generation of ciphers that followed it all used a 64-bit block size. To completely break a single key, an attacker would need a code book with 2⁶⁴ entries. Even to weaken it significantly takes a code book with 2³² entries with the same key, using 32 gigabytes of storage, With any sensible re-keying policy, a code book attack is not a threat.

More recent ciphers such as AES use a 128-bit block size, which makes code book attacks utterly impractical.

The Internet Key Exchange protocol automates re-keying for IPsec. It can be set to re-key after a fixed time or after a fixed amount of data is transferred, or both limits can be set and it will re-key when either is reached. Generally, an administrator sets one or both limits and re-keying is fairly frequent. However, there is a default built in so that, even if the administrator muffs it, the cipher is always re-keyed after 2³² packets.

Code book attacks can be used against any block cipher mode of operation. Take the widely used CBC mode as an example. In that mode, the ciphertext from the previous block is XORed into the plaintext before encryption, so — using p for plaintext, c for the corresponding ciphertexts, e() for encryption, and ^ for XOR — two encryptions might be:

cn = e(pn ^ cn-1)
cm = e(pm ^ cm-1)

If c_n = c_m, then the attacker knows that:

pn ^ cn-1 = pm ^ cm-1

which he can re-arrange to:

pn ^ pm = cn-1 ^ cm-1

but the ciphertexts are known if he has intercepted them, so the right side is known. This gives him:

pn ^ pm = a known constant

This easily breakable. See the stream cipher article for details.