The Design Of Rijndael: The Advanced Encryption Standard (AES)

Foreword......Page 5
Structure of this book......Page 7
Acknowledgments......Page 8
Preface to the second edition......Page 9
Contents......Page 10
1.2 AES: Scope and Significance......Page 18
1.3 Start of the AES Process......Page 19
1.4 The First Round......Page 20
1.5.3 Algorithm and Implementation Characteristics......Page 21
1.6.1 The Second AES Conference......Page 22
1.6.2 The Five Finalists......Page 23
1.8 The Selection......Page 24
2. Preliminaries......Page 26
2.1.1 Groups, Rings and Fields......Page 27
2.1.2 Vector Spaces......Page 28
2.1.4 Polynomials over a Field......Page 30
2.1.5 Operations on Polynomials......Page 31
2.1.6 Polynomials and Bytes......Page 32
2.1.7 Polynomials and Columns......Page 33
2.1.8 Functions over Fields......Page 34
2.2.1 Definitions......Page 37
2.3 Boolean Functions......Page 39
2.3.1 Tuple Partitions......Page 40
2.3.2 Transpositions......Page 41
2.3.3 Bricklayer Functions......Page 42
2.4 Block Ciphers......Page 43
2.4.1 Iterative Block Ciphers......Page 44
2.4.2 Key-Alternating Block Ciphers......Page 45
3.2 Input and Output for Encryption and Decryption......Page 48
3.4 The Round Transformation......Page 50
3.4.1 The SubBytes Step......Page 51
3.4.2 The ShiftRows Step......Page 54
3.4.3 The MixColumns Step......Page 56
3.4.5 The Rijndael Super Box......Page 58
3.5 The Number of Rounds......Page 59
3.6 Key Schedule......Page 60
3.6.2 Selection......Page 61
3.7.1 Decryption for a Two-Round Rijndael Variant......Page 63
3.7.3 The Equivalent Decryption Algorithm......Page 65
3.8 Conclusions......Page 67
4.1.1 Finite-Field Multiplication......Page 69
4.1.2 Encryption......Page 70
4.1.3 Decryption......Page 71
4.2.1 T-Table Implementation......Page 72
4.2.2 Bitsliced Software......Page 75
4.3 Dedicated Hardware......Page 76
4.3.2 Efficient Inversion in GF(28)......Page 77
4.4 Multiprocessor Platforms......Page 78
4.5 Conclusions......Page 79
5.1.2 Efficiency......Page 80
5.2 Simplicity......Page 81
5.3.1 Symmetry Across the Rounds......Page 82
5.3.2 Symmetry Within the Round Transformation......Page 83
5.3.5 Symmetry Between Encryption and Decryption......Page 84
5.3.6 Additional Benefits of Symmetry......Page 85
5.4.1 Arithmetic Operations......Page 86
5.4.2 Data-Dependent Shifts......Page 87
5.5.1 Security Goals......Page 88
5.5.2 Translation of Security Goals into Modern Security Notions......Page 89
5.5.3 Unknown Attacks Versus Known Attacks......Page 90
5.6.2 Resistance Against Differential and Linear Cryptanalysis......Page 91
5.6.3 Local Versus Global Optimization......Page 92
5.7 Key-Alternating Cipher Structure......Page 94
5.8.2 Key Expansion and Key Selection......Page 95
5.8.4 A Recursive Key Expansion......Page 96
5.9 Conclusions......Page 97
6.1 The DES......Page 98
6.2 Differential Cryptanalysis......Page 100
6.3 Linear Cryptanalysis......Page 102
6.4 Conclusions......Page 104
7.1.2 Correlation......Page 105
7.1.4 Orthogonality and Correlation......Page 106
7.1.5 Spectrum of a Binary Boolean Function......Page 107
7.2.2 Multiplication......Page 109
7.3 Correlation Matrices......Page 110
7.3.1 Equivalence of a Boolean Function and Its Correlation Matrix......Page 111
7.3.3 Boolean Permutations......Page 112
7.4.3 Bricklayer Functions......Page 114
7.5 Derived Properties......Page 115
7.6 Truncating Functions......Page 117
7.7 Cross-correlation and Autocorrelation......Page 118
7.8 Linear Trails......Page 119
7.9.2 Key-Alternating Cipher......Page 120
7.9.3 Averaging over All Round Keys......Page 121
7.9.4 The Effect of the Key Schedule......Page 123
7.10.1 Linear Cryptanalysis of the DES......Page 125
7.10.2 Linear Hulls......Page 126
7.11 Conclusions......Page 127
8.1 Difference Propagation......Page 128
8.2.1 Affine Functions......Page 129
8.2.4 Keyed Functions......Page 130
8.3 Relation Between DP Values and Correlations......Page 131
8.4.1 General Case......Page 132
8.4.2 Independence of Restrictions......Page 133
8.5 Key-Alternating Cipher......Page 134
8.7.1 Differential Cryptanalysis of the DES Revisited......Page 135
8.8 Conclusions......Page 136
9.1.1 Linear Cryptanalysis......Page 137
9.1.2 Differential Cryptanalysis......Page 138
9.2 The Wide Trail Strategy......Page 140
9.2.1 The γλ Round Structure in Block Ciphers......Page 141
9.2.2 Weight of a Trail......Page 143
9.2.3 Diffusion......Page 144
9.3 Branch Numbers and Two-Round Trails......Page 145
9.3.2 A Two-Round Propagation Theorem......Page 147
9.4.1 The Diffusion Step θ......Page 148
9.4.3 A Lower Bound on the Byte Weight of Four-Round Trails......Page 150
9.4.4 An Efficient Construction for θ......Page 151
9.5.1 A Key-Iterated Structure......Page 152
9.5.2 Applying the Wide Trail Strategy to Rijndael......Page 154
9.6 Constructions for θ......Page 155
9.7.1 The Hypercube Structure......Page 157
9.8 Conclusions......Page 159
10.2 Saturation Attacks......Page 160
10.2.1 Preliminaries......Page 161
10.2.2 The Basic Attack......Page 162
10.2.3 Influence of the Final Round......Page 163
10.2.5 Extension at the Beginning......Page 164
10.2.7 The Herds Attack and Other Extensions......Page 165
10.3.1 The Four-Round Distinguisher......Page 166
10.3.2 The Attack on Seven Rounds......Page 167
10.4 Interpolation Attacks......Page 168
10.5 Related-Key Attacks......Page 169
10.5.2 The Biryukov-Khovratovich Attack......Page 170
10.5.3 The KAS of the Biryukov-Khovratovich Attack......Page 171
10.7 Rebound Attacks......Page 173
10.8.1 Principle of the Attack......Page 174
10.9.1 Timing Attacks......Page 175
10.9.2 Power Analysis......Page 176
10.10 Conclusions......Page 177
11.1.1 Evolution......Page 179
11.1.2 The Round Transformation......Page 180
11.2 SHARK......Page 181
11.3 Square......Page 183
11.4 BKSQ......Page 186
11.5 Conclusion......Page 189
12. Correlation Analysis in GF(2n)......Page 190
12.1 Description of Correlation in Functions over GF(2n)......Page 191
12.1.2 Functions That Are Linear over GF(2)......Page 193
12.2 Description of Correlation in Functions over GF(2n)......Page 195
12.2.2 Functions That Are Linear over GF(2)......Page 196
12.3.1 Relationship Between Trace Masks and Selection Masks......Page 197
12.3.2 Relationship Between Linear Functions in GF(2)......Page 198
12.4 Rijndael-GF......Page 201
13.1 Properties of MDS Mappings......Page 204
13.2 Bounds for Two Rounds......Page 207
13.2.1 Difference Propagation......Page 209
13.2.2 Correlation......Page 211
13.3 Bounds for Four Rounds......Page 212
13.4 Conclusions......Page 213
14.1 The Multiplicative Inverse in GF(2n)......Page 214
14.2.1 Differentials, Trails and Trail Cores......Page 216
14.2.2 Bundles......Page 218
14.2.3 Number of Bundles with a Given Number of Active Bytes......Page 219
14.3.1 The Naive Super Box......Page 220
14.3.2 Sharp Conditions and Blurred Conditions......Page 221
14.4.1 Bundles with One Active S-Box in the First Round......Page 222
14.4.2 Any Bundle......Page 223
14.4.3 Experimental Verification......Page 224
14.5 EDP of a Bundle......Page 225
14.5.2 Occurrence in Trails......Page 226
14.6.1 Differentials with Activity Pattern (1110; 1110)......Page 227
14.6.2 A Bound on the Multiplicity......Page 228
14.7 Differentials with the Maximum EDP Value......Page 229
14.8 Conclusions......Page 230
15.1 Motivation......Page 231
15.2.1 Planar Differentials and Maps......Page 232
15.2.2 Plateau Trails......Page 234
15.2.3 Plateau Trails in Super Boxes......Page 235
15.3 Plateau Trails over More Than Two Rounds......Page 237
15.4.1 Effect of the Key Schedule......Page 238
15.5.1 Trails in the Rijndael Super Box......Page 239
15.5.2 Observations......Page 240
15.6 Trails over Four or More Rounds in Rijndael......Page 242
15.8.1 Definitions Definition 15.8.1.......Page 244
15.8.2 Related Differentials and Plateau Trails Theorem 15.8.1.......Page 245
15.9.1 First Example......Page 247
15.9.2 For Any Given Differential......Page 248
15.9.4 Second Example......Page 249
15.9.5 A Combinatorial Bound......Page 251
15.10.2 Related Differentials in......Page 252
15.10.3 Avoiding Related Differentials......Page 253
15.11 Conclusions and Further Work......Page 254
A.1 SRD......Page 256
A.2.2 Round Constants......Page 259
B.2 Rijndael(128,128)......Page 260
B.3 Other Block Lengths and Key Lengths......Page 262
C. Reference Code......Page 265
Bibliography......Page 272
Index......Page 283