Cryptanalytic Methods for Modern Ciphers.

Block ciphers like DES are intended to be very hard to break, and they are largely successful in achieving this. Having even copious quantities of corresponding plaintext and ciphertext, it is intended that the fastest way to discover the key, so as to be able to decrypt other messages, would be a brute-force search, that is, trying every possible key until the right one is found.

Many block ciphers appear to meet this condition. Two cryptanalytic methods that can do slightly better with some of the earlier block ciphers, such as DES and LUCIFER, are differential cryptanalysis and linear cryptanalysis.

Other techniques, which are of interest against weaker ciphers, and which partially account for the fact that DES has sixteen rounds, instead of eight, such as hill-climbing techniques and genetic algorithms, are discussed in the next section.

In the book The Hut Six Story, Gordon Welchman first revealed one of the innovations used with the Bombe in connection with the cryptanalysis of the German Enigma. He also noted that it embodied a general principle which made present-day ciphers weaker than they might be expected to be.

Differential Cryptanalysis

However, if one is fortunate enough to have a large quantity of corresponding plaintext and ciphertext blocks for a particular unknown key, a technique called differential cryptanalysis, developed by Eli Biham and Adi Shamir, is available to obtain clues about some bits of the key, thereby shortening an exhaustive search.

After two rounds of DES, knowing both the input and output, it is trivial to determine the two subkeys used, since the outputs of both f-functions are known. For each S-box, there are four possible inputs to produce the known output. Since each subkey is 48 bits long, but the key is only 56 bits long, finding which of the four possibilities is true for each group of six bits in the subkeys is a bit like solving a crossword puzzle.

Once the number of rounds increases to four, the problem becomes much harder. However, it is still true that the output depends on the input and the key. For a limited number of rounds, it is inevitable, without the need for any flaws in the S-boxes, that there will be some cases where a bit or a combination of bits in the output will have some correlation with a simple combination of some input bits and some key bits. Ideally, that correlation should be absolute with respect to the key bits, since there is only one key to solve for, but it can be probabilistic with respect to the input and output bits, since there need to be many pairs to test.

As the number of rounds increases, though, the simple correlations disappear. Differential cryptanalysis represents an approach to finding more subtle correlations.

Instead of saying "if this bit is 1 in the input, then that bit will be 0 (or 1) in the output", we say "changing this bit in the input changes (or does not change) that bit in the output".

In fact, however, a complete pattern of which bits change and do not change in the input and in the output is the subject of differential cryptanalysis. The basic principle of differential cryptanalysis, in its classic form, is this: the cipher being attacked has a characteristic if there exists a constant X such that given many pairs of plaintexts A, B, such that B = A xor X, if a certain statement is true about the key, E(B,k) = E(A,k) xor Y for some constant Y will be true with a probability somewhat above that given by random chance.

Linear Cryptanalysis

Linear cryptanalysis, invented by Mitsuru Matsui, is a different, but related technique. Instead of looking for isolated points at which a block cipher behaves like something simpler, it involves trying to create a simpler approximation to the block cipher as a whole.

For a great many plaintext-ciphertext pairs, the key that would produce that pair from the simplified cipher is found, and key bits which tend to be favored are likely to have the value of the corresponding bit of the key for the real cipher. The principle is a bit like the summation of many one-dimensional scans to produce a two-dimensional slice through an object in computer-assisted tomography.