DES, the Data Encryption Standard, is the best known and most widely used civilian cryptosystem. It was developed by IBM and adopted as a US national standard in the mid 1970`s, and had resisted all attacks in the last 15 years. This book presents the first successful attack which can break the full 16 round DES faster than via exhaustive search. It describes in full detail, the novel technique of Differential Cryptanalysis, and demonstrates its applicability to a wide variety of cryptosystems and hash functions, including FEAL, Khafre, REDOC-II, LOKI, Lucifer, Snefru, N-Hash, and many modified versions of DES. The methodology used offers valuable insights to anyone interested in data security and cryptography, and points out the intricacies of developing, evaluating, testing, and implementing such schemes. This book was written by two of the field`s leading researchers, and describes state-of-the-art research in a clear and completely contained manner.
Author(s): Eli Biham, Adi Shamir
Edition: Softcover reprint of the original 1st ed. 1993
Publisher: Springer
Year: 1993
Language: English
Pages: 188
Preface V
ToC VII
1 Introduction 1
2 Results 7
3 Introduction to Differential Cryptanalysis 11
3.1 Notations and Definitions 11
3.2 Overview ........ . 15
3.3 Characteristics . . . . . . 22
3.4 The Signal to Noise Ratio 29
3.5 Known Plaintext Attacks 31
3.6 Structures . . . . . . . . . 31
4 Differential Cryptanalysis of DES Variants 33
4.1 DES Reduced to Four Rounds. 33
4.2 DES Reduced to Six Rounds . . . . . . . . 37
4.3 DES Reduced to Eight Rounds . . . . . . . 41
4.3.1 Enhanced Characteristic's Probability 46
4.3.2 Extension to Nine Rounds . . . . . . 47
4.4 DES with an Arbitrary Number of Rounds 48
4.4.1 3R-Attacks 49
4.4.2 2R-Attacks 50
4.4.3 1R-Attacks 51
4.4.4 Summary 52
4.4.5 Enhanced Characteristic's Probability 54
4.5 Modified Variants of DES . . . . . . . . . . 55
4.5.1 Modifying the P Permutation . . . . 56
4.5.2 Modifying the Order of the S Boxes 57
4.5.3 Replacing XORs by Additions . . . 58
4.5.3.1 Replacing the XORs Within the F Function 58
4.5.3.2 Replacing All the XORs . . . . . . . . . . . 59
4.5.3.3 Replacing All the XORs in an Equivalent DES Description . . . . . . . . . . . . . . . 59
4.5.4 Random and Modified S Boxes . . . . . . . . . . . . 60
4.5.5 S Boxes with Uniform Difference Distribution Tables 62
4.5.6 Eliminating the E Expansion . . . . . . . . . . . . . 63
4.5.7 Replacing the Order of the E Expansion and the XOR with the Subkeys . 64
4.6 DES with Independent Keys . . . . . . . . . . . . . . . . . . 65
4.6.l Eight Rounds . . . . . . . . . . . . . . . . . . . . . . 65
4.6.2 Sixteen Rounds . . . . . . . . . . . . . . . . . . . . . 68
4.7 The Generalized DES Scheme (GDES) . . . . . . . . . . . . 69
4.7.1 GDES Properties . . . . . . . . . . . . . . . . . . . . 69
4.7.2 Cryptanalysis of GDES . . . . . . . . . . . . . . . . 71
4.7.2.1 A Known Plaintext Attack for n = q . . . . 72
4.7.2.2 A Second Known Plaintext Attack for n = q 72
4.7.2.3 A Chosen Plaintext Attack for n = 2q - 1 . . . . . . . . 73
4.7.2.4 A Chosen Plaintext Attack for n = 3q - 2 . . . . . . . . 73
4.7.2.5 A Chosen Plaintext Attack for n = lq - 1 . . . . . . . . 73
4.7.2.6 The Actual Attack on the Recommended Variant . . . . . . . . . . . . . . . . . . . . 74
4.7.2.7 Summary . . . . . . . . . . . . . . . . . . 76
5 Differential Cryptanalysis o f the Full 16-Round DES 79
5.1 Variants of the Attack . . . . . . . . . . . . . . . . . . . 86
6 Differential Cryptanalysis of FEAL 89
6.1 Cryptanalysis of FEAL-8 . . . . . . . . . . . . . . . . . . . 95
6.1.1 Reducing FEAL-8 to Seven Rounds . . . . . . . . . 96
6.1.2 Reducing the Seven-Round Cryptosystem to Six Rounds 98
6.1.3 Reducing the Cryptosystem to 5 , 4 , 3 , 2 and 1 Rounds 99
6.1.4 Calculating the Key Itself . . . . . . . . . . . . . . . 100
6.1.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . 101
6.2 Cryptanalysis of FEAL-N and FEAL-NX with N <= 31 Rounds 101
6.3 Other Properties of FEAL . . . . . . . . . . . . . . . 105
7 Differential Cryptanalysis of Other Cryptosystems 109
7.1 Cryptanalysis of Khafre . . . . . . . . . . . . . . . . . . . 109
7.2 Cryptanalysis of REDOC-11 . . . . . . . . . . . . . . . . . . 115
7.3 Cryptanalysis of LOKI . . . . . . . . . . . . . . . . . . . . . 121
7.4 Cryptanalysis of Lucifer . . . . . . . . . . . . . . . . . . . . 125
7.4.1 First Attack . . . . . . . . . . . . . . . . . . . . . . . 128
7.4.2 Second Attack . . . . . . . . . . . . . . . . . . . . . 130
8 Differential Cryptanalysis of Hash Functions 133
8.1 Cryptanalysis of Snefru . . . . . . . . . . . . . . 133
8.2 Cryptanalysis of N-Hash . . . . . . . . . . . . . . . . . 145
9 Non-Differential Cryptanalysis of DES with a Small Number of Rounds 149
9.1 Ciphertext Only Attacks ......... . 149
9.1.1 A Three-Round Attack ..... . 149
9.1.2 Another Three-Round Attack . 150
9.1.3 A Four-Round Attack . 150
9.2 Known Plaintext Attacks . . . . . . 151
9.2.1 A Three-Round Attack . . . 151
9.3 Statistical Known Plaintext Attacks 152
9.3.1 A Three-Round Attack 152
9.3.2 A Four-Round Attack 152
9.3.3 A Five-Round Attack 154
9.3.4 A Six-Round Attack 154
Appendix A. Description of DES 155
A.1 The Key Scheduling Algorithm 159
A.2 DES Modes of Operation . . . 162
Appendix B. The Difference Distribution Tables of DES 165
Glossary 175
Bibliography 183
Index 186
