Differential cryptanalysis of the Data Encryption Standard

From MaRDI portal





Differential cryptanalysis is a powerful new type of cryptanalysis attack invented by the authors, which has been successfully applied to iterated cryptosystems and hash functions. It is one of few examples of methods of cryptanalysis that have become known in the open literature, which can not only be applied to a single cipher but to a whole variety of encryption and hash functions. The best known and most widely used iterated cryptosystem is the block cipher DES (Data Encryption Standard). The key size of DES is 56 bits and the block size 64 bits. This block is divided into two halves of 32 bits each. A crucial part of the round- function is the \(F\) function, which works on the right half of the data using a subkey of 48 bits and eight (six-bit to four-bit) \(S\) boxes. The 32 output bits of the \(F\) function are XORed with the left half of the data and the two halves are exchanged. (A complete description of the DES algorithm is given in Appendix A of the present book.) Differential cryptanalysis is a method which analyzes the effect of particular differences in plaintext pairs on the difference of the resulting ciphertext pairs. These differences can be used to assign probabilities to the possible keys and to estimate the most probable key. This procedure in most cases needs many pairs of plaintexts with the same particular difference using the resulting ciphertext pairs. For DES and many other DES-like cryptosystems the difference is chosen as a fixed XORed value of the two plaintexts. Differential cryptanalysis is a chosen plaintext attack which can often be converted into a known plaintext attack. In order to describe the method of differential cryptanalysis, DES is taken as the canonical example of an iterated cryptosystem, but similar ideas can be carried over to other iterated cryptosystems by taking an appropriate notion of difference. The detailed differential cryptanalysis of DES is based on the difference distributions of each \(S\) box, in order to analyze the round by round evolution of differences when two related plaintexts are encrypted under the same key. The results of the attacks on variants of DES with reduced numbers of round as given in the book are as follows. DES reduced to six rounds can be broken by a chosen plaintext attack in less than 0.3 second on a personal computer using 240 ciphertexts. Its known plaintext variant needs about \(2^{36}\) ciphertexts. DES reduced to eight rounds can be broken by a chosen plaintext attack in less than two minutes on a computer by analyzing \(2^{14}\) ciphertexts. Its conversion to a known plaintext attack needs about \(2^{39}\) ciphertexts. Any reduced variant of DES is breakable by a chosen plaintext attack faster than exhaustive search. The known plaintext variants of the attacks are faster than exhaustive search for up to 14 rounds. An advanced form of differential cryptanalysis can also attack the full 16-round DES. Although this attack is faster than exhaustive key search, it does not endanger present practical applications of DES. The analysis shows however that almost any structural modification of DES leads to a much weaker cryptosystem, thus demonstrating the crucial role of the elements of the design. Beyond DES, differential cryptanalysis is applied to bounded-round versions of the cryptosystems FEAL, Khafre, REDOC-II, LOKI and Lucifer, and to the hash functions Snefru and \(N\)-hash.




Cited in
(only showing first 100 items - show all)








This page was built for publication: Differential cryptanalysis of the Data Encryption Standard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3136298)