Vocabulary
What do the following forms and word combinations mean?
Incomprehensible ciphertext, automated aids, removing one bit of drudgery, overlapping superencipherment group, hill climbing algorithm, subkey, recover a DES key, encipher the known plaintext, flipped bit results, (original) trial key, trial encipherment, avalanche property of DES, ciphertext-only solution, mimic the process (of natural selection), chain of discrete elements
Texts
Pre-reading task.
What do you know about cryptanalysis? What cryptographic algorithms can you name?
Text 1. Cryptanalysis.
Cryptanalysis is hard work, requiring a willingness to endure many false starts, and a painstaking attention to detail. It requires intelligence to see subtle patterns in incomprehensible ciphertext.
Automated aids to cryptanalysis come in many forms. Some collected statistical information about ciphertexts, thus removing one bit of drudgery from human shoulders. Others, such as the Bombe used in attacking the German Enigma, or the DES cracker built by the Electronic Frontier Foundation, or the converted unit record equipment (punched card machines) which compared Japanese code messages to one another at various displacements to find messages with overlapping superencipherment groups, work by trying thousands, or millions, of possibilities, one after another.
Neither of these techniques is adequate to deal with many cipher systems, particularly modern ones. A well-designed cipher will not offer a simple opportunity to try different possibilities to find partial information about the key, and will have a key large enough to make trying every possible key hopeless. Nor is ordinary statistical information about the frequencies and contacts of bytes in the ciphertext likely to be much use.
Thus, approaches taken from the field of AI (artificial intelligence) have been tried. In these approaches, it is attempted to combine the speed of the computer with steps that at least slightly move towards the skill and judgement of a human cryptanalyst.
Hill-climbing
Because the individual bits of the subkeys in DES are actual bits taken from the 56-bit DES key, an approach like the following to recover a DES key must have occurred to many people.
Given a block of known plaintext, and its corresponding ciphertext, starting with a random 56-bit possible key, do the following:
Encipher the known plaintext with that key, and with every one of the 56 other keys obtained by inverting one bit of that key.
Compare the resulting ciphertext to the actual ciphertext.
In those of the 56 cases where the flipped bit results in the ciphertext produced differing in fewer bits from the actual ciphertext than that produced by the original trial key, invert that bit of the trial key to obtain the next trial key.
This is a simple example of a hill-climbing algorithm, where the number of bits by which a trial encipherment differs from the actual ciphertext are a measure of one's (lack of) altitude.
It would, however, never work against DES. That is because of the avalanche property of DES; changing a single bit in a DES key results in every bit of the block being enciphered being changed randomly after only a few rounds.
Thus, even attempting to improve the hill climbing algorithm above by, for each trial, enciphering the known plaintext for eight rounds with the trial key, and deciphering the actual ciphertext for eight rounds with the trial key, and then determining the number of bits by which these two results differed would not be enough to help.
Another idea would be to choose two rounds of DES, and by determining the input to those rounds by enciphering the known plaintext by the previous rounds, and the required output from those rounds by deciphering the actual ciphertext by the following rounds, examine the two 48-bit subkeys for the rounds, and, by examining the four possibilities for each group of 6 bits in those subkeys to produce the required change in each half of the block, find those which are consistent with the origin of those two subkeys from the original 56-bit key, and then try the resulting new 56-bit key or keys on the basis that it or they might be improvements over the preceding trial key.
Genetic Programming
A thesis by A. J. Bagnall described the ciphertext-only solution of some simple rotor machines by means of the technique of genetic programming.
Genetic programming is a method by which a computer produces an answer to a question, or even a computer program to perform a task, by mimicing the process of natural selection. As noted in the thesis, and in the book Artificial Life by Stephen Levy, this technique was originated by John Holland in the mid-1960s, and his student David Goldberg was one of the first to refine the technique so that it could be used in practice with real problems of importance.
It can be thought of as a special case of the hill-climbing algorithm, in that a quantitative measure of how "warm" the computer is in approaching the desired solution is required.
Programs or answers must be in the form of a chain of discrete elements, such that there is at least a reasonable likelihood that a chain formed by taking one chain, and replacing a span of elements within it by the corresponding elements from another chain, will "make sense". Random mutations are also usually used, although genetic crossover has been found to be much more important.
Starting with a random selection of solutions, those that work best are retained, and used as the parents of the next generation of solutions to be tried. Often, this retention is also randomized, so that better solutions have a higher probability of being retained.
One type of mutation that happens in real life has not, to my knowledge, been used for genetic programming yet. Occasionally, plants and animals will increase the size of their genetic inheritance by duplicating part of it. Thus, a finite state machine could mutate by becoming a machine with twice as many states. It might be useful to make provision for this where a problem might be more complex to solve than initially realized.
What automated aids to cryptanalysis do you remember? Characterize them in a few words.
What are the approaches to cryptanalysis?
Text 2. Cryptanalytic Methods for Modern Ciphers. Read the text and write its summary. Point out the facts that are new for you. Present them orally.
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.
Extensions of Differential Cryptanalysis
The technique of differential cryptanalysis, in addition to being very powerful by itself, has served as a basis for the development of even more powerful techniques, such as those surveyed here and in the next section.
Truncated differentials
It is of course possible that some of the bits of E(A,k) xor E(B,k) will be more likely to match those of Y than others. If one can, in addition, ignore some of the bits of A and B, one has a truncated differential for the cipher being attacked, and this technique, due to Lars R. Knudsen, has been found to be very powerful. (Being able to ignore some bits of A and B may allow two or more truncated differentials to be used together, and this is why it is important.)
Higher-order Differentials
Another important addition to the available techniques deriving from differential cryptanalysis is the use of higher-order differentials, which first appeared in a paper by Xuejia Lai.
A differential characteristic of the type described above, where for a large number of different values of A, B equals A xor X, and the encrypted versions of A and B for a given key, k, are expected to have the relation E(A,k) = E(B,k) xor Y, if a target statement about the key k is true, can be made analogous to a derivative in calculus, and then it is termed that Y is the first derivative of the cipher E at the point X.
A second-order derivative would then be one involving a second quantity, W, such that E(A,k) xor E(B,k) = E(C,k) xor E(D,k) xor Z is expected to be true more often than would be true due to chance, where not only is B = A xor X, but C = A xor W and D = B xor W. In that case, Z is the second derivative of the cipher E at the point X,W. Since xor performs the function of addition and subtraction, the four items encrypted for any A are just lumped together in this case, but if differential cryptanalysis were being performed over another field where the distinction is significant, then Y=E(A+X,k)-E(A,k) and Z=(E(A+X+W,k)-E(A+W,k))-(E(A+X,k)-E(A,k)) would be the appropriate equations to use. This technique is important because a second order derivative can exist at a point for the first coordinate of which no first order derivative exists, or is probable enough to be useful.
And similarly, a third order derivative is derived from the difference of two second order derivatives, based on another constant difference, and so on.
The Boomerang Attack
Recently, a means of improving the flexibility of differential cryptanalysis was discovered by David A. Wagner. Called the boomerang attack, it allows the use of two unrelated characteristics for attacking two halves of a block cipher.
This diagram shows how the attack might work if everything goes perfectly for a particular initial block. The numbered points in the diagram show the steps involved in the attack.
Start with a random block of plaintext. Based on the characteristic known for the first half of the cipher, if we XOR a certain vector with it, called d1 (equal to 00100000 in the diagram), the result after half-enciphering the two plaintext blocks, before and after the XOR, will differ by c1 (equal to 00110110 in the diagram), if what we wish to learn about the key happens to be true.
Since the characteristic applies only to the first half of the cipher, the results after the whole block cipher won't be related. Take those two results, and XOR each one with d2 (equal to 01001011 in the diagram), which is the vector corresponding to the characteristic for the second half of the cipher. In each case, XORing d2 with a ciphertext block is expected to change the result after deciphering halfway by c2 (equal to 00010000 in the diagram), again, if something is true of the key.
With two intermediate results that differ by c1, if each one has c2 XORed to it, the two results of the XOR will still differ by c1. Since this difference now relates to the first half characteristic, it can be seen in the final output, thus indicating the truth or otherwise of two hypotheses about the key.
This increases the potential effectiveness of differential cryptanalysis, because one can make use of characteristics that do not propagate through the complete cipher. Also, certain kinds of added complexities, such as a bit transpose in the middle of the cipher, do not serve as a barrier to this method, since two values differing by an XOR with some value merely differ by an XOR with some other value after a bit transpose.
However, it has its limitations. It only produces a result if both characteristics are present; it does not allow testing for each characteristic independently. Even so, it seems to double the number of rounds a cipher needs to be considered secure.
Since at one end of a sequence of rounds, the precise difference between blocks that is required for the characteristic must be input, it isn't possible directly to cascade this method to break a block cipher into four or more pieces.
Note that any single Feistel round has a large family of "characteristics" that is 100% probable, but which tells nothing about the key, since any pattern that involves leaving the half that is input to the F-function unchanged, but involves an XOR to the half that is XORed with the output of the F-function applies, so one of the things this method can do is allow the use of attacks against the first or last 15 rounds of DES against 16-round DES. Hence, if by some other trick a block cipher with 16 rounds could be broken into 16 pieces like this, one could test for an informative characteristic which applied to any single round.