Independent Study Notes Aaron L. Paolini Introduction The following is a summary on selected topics from a 2006 winter session independent study. Over the course of the winter, numerous academic papers and texts were read in order to gain some insight into the practice of cryptanalysis. One common practice when analyzing a particular cipher is the intentional weakening of the cipher to be studied. Not only does this make analysis feasible, it is also useful in that it may reveal weakness pertaining specifically to certain elements within the cipher. Such weaknesses can be used to attack a fuller version of the cipher, as well as improve the cipher’s security by fixing that particular element. The following document attempts to summarize a select number of common attacks that have been used with some degree of success against certain block ciphers. At the end of the document is a list of works that have been read. A Statement about Modern Cryptanalysis Unlike the cryptanalysis of the last few decades, modern cryptanalysis is largely theoretical in nature. Keys that were once 56 bits (for DES) have since grown to as high as 256 bits (or more in some cases), making many attacks infeasible to test experimentally. Of course, such attacks are important, but remain impractical to carry out due to the limits of modern computing equipment. Contents Generalized Attack Methods 1. Classic Cryptanalytic Attacks 2. Differential Cryptanalysis 3. Linear Cryptanalysis 4. Slide Attacks 5. Boomerang Attacks 6. Meet-in-the-Middle Attacks 7. Side-Channel Attacks Other Observations 8. On Khinchin’s Mathematical Foundations of Information Theory 9. On Common Block Cipher Elements Bibliography (See final pages)Classical Cryptanalysis Overview While ciphers of the past have been thoroughly broken, the practice of performing cryptanalysis on early ciphers serves as a gentle introduction to this field of study. Frequency Analysis (substitution, affine) Both monoalphabetic substitution and affine ciphers succumb easily to a method of attack known as frequency analysis. Essentially, by recording the frequency of single characters, digrams, and trigrams in a particular ciphertext and comparing these results against previously obtained frequency characteristics for that particular language, one can attempt to decode the ciphertext. For a large enough ciphertext (so that unique decipherability is obtainable) and for a fine enough expected frequency distribution, this method certainly works. Of course, some additional manual analysis may be necessary to fully recover the plaintext, but for the most part, high frequency characteristics usually hold well enough to make the attempted decoding readable, albeit with minor errors. Correcting such errors is trivial.Differential Cryptanalysis Overview Differential cryptanalysis is one of the earlier methods of block cipher cryptanalysis that proved to be effective against certain block ciphers such as FEAL and reduced-round DES. In general, this attack examines how a given change in the input of a cipher will affect the resultant plaintext. This “difference” is usually defined to be the XOR of two bitstrings (two plaintexts or two ciphertexts). Consider the f-function input of a given Feistel algorithm, such as DES. Given two plaintexts (X1 and X2) with a given XOR (X1 XOR X2), there exists a non-uniform output XOR (Y1 XOR Y2) distribution. That is to say, for the entire range of possible plaintext pairs with a given XOR value, there exists an output XOR value that occurs with a probability Pout that is greater than other possible output XOR values. This characteristic is the basis for a chosen plaintext cryptanalytic attack against a algorithm that exhibits this behavior. On Multiple Rounds and Differential Characteristics For an n-round cipher, there exists an n-round differential characteristic with an associated probability p. This n-round differential characteristic is simply the concatenation of n single round differential characteristics, each with an associated probability pi. The overall probability p is said to be the multiplication of all per-round differential probabilities, although this only holds true if the rounds are considered independent of one another. While this not the case, p, as calculated, is considered to be close enough to its actual value. At this point, it may be beneficial to clarify the concept of the probability p for a given n-round differential characteristic. Essentially, the probability that for a given round input XOR (X1 XOR X2), an expected round output XOR (Y1 XOR Y2) will occur with a probability pi. The probability that the desired per-round characteristics will hold over all rounds in the cipher is given by p. Obviously, the higher this overall probability is, the more favorable the conditions for a cryptanalytic attack. Thus, it is wise to choose carefully the input XOR of the plaintext pair and desired output XOR to yield the highest overall n-round differential characteristic probability p. For example, in a differential attack on the Data Encryption Standard (DES) it is beneficial for the right half of the input XOR to evaluate to zero. Such a technique greatly improves the differential characteristic’s probability, as an f-function input XOR of zero will result in an f-function output of zero with probability 1.On Differential Cryptanalysis and DES In the case of DES, key bits are calculated by considering the final f-function input (essentially the left half of the ciphertext) and an expected f-function output that holds with probability p. The f-round output cannot be known for certain as it is masked by the left half of the previous round input to give the right half of the ciphertext. One of the first effective methods of cryptanalysis on the Data Encryption Standard was differential cryptanalysis, if only reduced round versions (usually 3 to 12). Cryptanalysis of higher round versions of DES requires an exceedingly large amount of plaintext pairs (247 pairs for all rounds), making cryptanalysis somewhat infeasible. With very careful selection of differential characteristics, it is possible to break DES in less time than a brute force attack, although it has been said that this characteristic is no good if the input of the cipher is known to be ASCII encoded text. On Impossible Differentials While most attacks are concerned with finding a high