Code book attack

A code book attack is a technique for cryptanalysis. The name comes from the attack on a block cipher; the attacker tries to build up a "code book", a table saying which ciphertexts correspond to which plaintexts. There is also a variant usable against a stream cipher; the attacker attempts to build a listing of the entire output stream, until it repeats.

For example, consider a block 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 ever sent with that key. Such tiny block sizes are therefore never used; real block 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 attack. 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, 32 gigabytes of data. 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.

Block cipher modes

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:

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

and, if the same key was used for both blocks, this gives him

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.

In some modes, more frequent re-keying may be required. For example, for counter mode, using the block cipher as a random number generator, there is an attack (given in the Yarrow paper) that is effective after 2^blocksize/3blocks of output.

Stream ciphers

A variant of a codebook attack can also be used against a stream cipher. In this, the attacker collects information on the pseudorandom output sequence. The equivalent of getting a complete code book for a block cipher is getting a complete listing of the pseudorandom sequence; this would break a stream cipher completely. As for block ciphers, even partial success gives the attacker some information. As for block ciphers, the attack is wildly impractical against real ciphers and can be made impossible by reasonable re-keying policies. Stream ciphers are designed to have a long period, to run for 2¹⁰⁰ or more output bits before repeating; this blocks code book attacks on them, much as adequate block sizes prevent these attacks for block ciphers.

Defense in Internet Key Exchange

The Internet Key Exchange protocol automates key management 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. It will re-key when either limit is reached on either of the two gateways used for the connection. In normal usage, a gateway administrator sets one or both limits and the system is re-keyed fairly often. The re-keying mechanism is efficient enough that moderately frequent re-keying generally does not have much performance impact.

However, there is also a default built in so that, even if both administrators muff it and no limit is set on either gateway, the cipher will still be re-keyed. A packet count is kept and the cipher is re-keyed if it overflows, after 2³² packets. For a 64-bit block cipher, 2³² packets is larger than 2³² blocks, so there is a theoretical weakness in this. However, it is completely safe for a 128-bit cipher such as AES. Even for a 64-bit cipher, it is close enough for a safety mechanism that should never actually be used and was only added to protect against blunders by implementers or administrators.