The Design of RijndaeL: AES - The Advanced Encryption Standard

1. The Advanced Encryption Standard Process. . . . . . . . . . . . . . 19
	1.1 In the Beginning . .. .................................... 19
	1.2 AES: Scope and Significance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
	1.3 Start of the AES Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
	1.4 The First Round .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
	1.5 Evaluation Criteria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
		1.5.1 Security......................................... 22
		1.5.2 Costs........................................... 22
		1.5.3 Algorithm and Implementation Characteristics. . . . . . . 22
	1.6 Selection of Five Finalists ............................... 23
		1.6.1 The Second AES Conference . . . . . . . . . . . . . . . . . . . . . . . 23
		1.6.2 The Five Finalists. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
	1.7 The Second Round ..................................... 25
	1.8 The Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2. Preliminaries............................................. 27
	2.1 Finite Fields. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 28
		2.1.1 Groups, Rings, and Fields. . . . . . . . . . . . . . . . . . . . . . . .. 28
		2.1.2 Vector Spaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 29
		2.1.3 Fields with a Finite Number of Elements. . . . . . . . . . .. 31
		2.1.4 Polynomials over a Field .............. . . . . . . . . . . .. 31
		2.1.5 Operations on Polynomials ..... , . . . . . . . . . . . . . . . . .. 32
		2.1.6 Polynomials and Bytes. . . . . . . . . . . . . . . . . . . . . . . . . . .. 33
		2.1.7 Polynomials and Columns. . . . . . . . . . . . . . . . . . . . . . . .. 34
	2.2 Linear Codes .......................................... 35
		2.2.1 Definitions...................................... 35
		2.2.2 MDS codes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 37
	2.3 Boolean Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 37
		2.3.1 Bundle Partitions ................................ 38
		2.3.2 Transpositions................................... 39
		2.3.3 Bricklayer Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 40
		2.3.4 Iterative Boolean Transformations. . . . . . . . . . . . . . . . .. 40
	2.4 Block Ciphers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 41
		2.4.1 Iterative Block Ciphers. . . . . . . . . . . . . . . . . . . . . . . . . . .. 42
		2.4.2 Key-Alternating Block Ciphers. .. . . . . . . . . . . . . . . . . .. 43
	2.5 Block Cipher Modes of Operation ........................ 45
		2.5.1 Block Encryption Modes. . . . . . . . . . . . . . . . . . . . . . . . .. 45
		2.5.2 Key-Stream Generation Modes. . . . . . . . . . . . . . . . . . . .. 45
		2.5.3 lVIessage Authentication Modes. . . . . . . . . . . . . . . . . . . .. 46
		2.5.4 Cryptographic Hashing. . . . . . . . . . . . . . . . . . . . . . . . . . .. 47
	2.6 Conclusions............................................ 47
3. Specification of Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 49
	3.1 Differences between Rijndael and the AES . . . . . . . . . . . . . . . .. 49
	3.2 Input and Output for Encryption and Decryption .......... 49
	3.3 Structure of Rijndael. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 51
	3.4 The Round Transformation. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 51
		3.4.1 The SubBytes Step. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 52
		3.4.2 The ShiftRows Step. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 55
		3.4.3 The MixColumns Step. . . . . . . . . . . . . . . . . . . . . . . . . . . .. 56
		3.4.4 The Key Addition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 58
	3.5 The Number of Rounds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 59
	3.6 Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 61
		3.6.1 Design Criteria .............. \'. . . . . . . . . . . . . . . . . . . .. 61
		3.6.2 Selection........................................ 61
	3.7 Decryption............................................ 63
		3.7.1 Decryption for a Two-Round Rijndael Variant ....... 63
		3.7.2 Alge braic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 64
		3.7.3 The Equivalent Decryption Algorithm .............. 66
	3.8 Concl usions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 68
4. Implementation Aspects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 71
	4.1 8-Bit Platforms ........................................ 71
		4.1.1 Finite Field Multiplication. . . . . . . . . . . . . . . . . . . . . . . .. 71
		4.1. 2 Encryption...................................... 72
		4.1.3 Decryption...................................... 73
	4.2 32-Bit Platforms ....................................... 74
	4.3 Dedicated Hardware. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 77
		4.3.1 Decomposition of SRD ............................ 78
		4.3.2 Efficient Inversion in GF(2 8 ) . . . . . . . . . . . . . . . . . . . . . .. 79
	4.4 Multiprocessor Platforms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 79
	4.5 Performance Figures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 80
	4.6 Conclusions............................................ 80
5. Design Philosophy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 81
	5.1 Generic Criteria in Cipher Design ........................ 81
		5.1.1 Security......................................... 81
		5.1. 2 Efficiency ....................................... 82
		5.1.3 Key Agility. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 82
		5.1.4 Versatility....................................... 82
		5.1.5 Discussion....................................... 82
	5.2 Simplicity............................................. 83
	5.3 Symmetry............................................. 83
		5.3.1 Symmetry Across the Rounds. . . . . . . . . . . . . . . . . . . . .. 84
		5.3.2 Symmetry Within the Round Transformation. . . . . . .. 84
		5.3.3 Symmetry in the D-box . . . . . . . . . . . . . . . . . . . . . . . . . .. 85
		5.3.4 Symmetry and Simplicity in the S-box . . . . . . . . . . . . .. 86
		5.3.5 Symmetry between Encryption and Decryption ...... 86
		5.3.6 Additional Benefits of Symmetry. . . . . . . . . . . . . . . . . .. 86
	5.4 Choice of Operations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 87
		5.4.1 Arithmetic Operations. . . . . . . . . . . . . . . . . . . . . . . . . . .. 88
		5.4.2 Data-Dependent Shifts. . . . . . . . . . . . . . . . . . . . . . . . . . .. 88
	5.5 Approach to Security ................................... 89
		5.5.1 Security Goals ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 89
		5.5.2 Unknown Attacks Versus Known Attacks. . . . . . . . . . .. 90
		5.5.3 Provable Security Versus Provable Bounds. . . . . . . . . .. 91
	5.6 Approaches to Design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 91
		5.6.1 Non-Linearity and Diffusion Criteria. . . . . . . . . . . . . . .. 91
		5.6.2 Resistance against Differential and Linear Cryptanalysis 91
		5.6.3 Local Versus Global Optimization. . . . . . . . . . . . . . . . .. 92
	5.7 Key-Alternating Cipher Structure ........................ 94
	5.8 The Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 94
		5.8.1 The Function of a Key Schedule. . . . . . . . . . . . . . . . . . .. 94
		5.8.2 Key Expansion and Key Selection. . . . . . . . . . . . . . . . .. 95
		5.8.3 The Cost of the Key Expansion. . . . . . . . . . . . . . . . . . .. 95
		5.8.4 A Recursive Key Expansion ....................... 96
	5.9 Conclusions............................................ 97
6. The Data Encryption Standard. . . . . . . . . . . . . . . . . . . . . . . . . .. 99
	6.1 The DES. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 99
	6.2 Differential Cryptanalysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 101
	6.3 Linear Cryptanalysis. . . . . . . . . . . . . ... 103
	6.4 Conclusions............................................ 105
7. Correlation Matrices ..................................... 107
	7.1 The Walsh-Hadamard Transform. . . . . . . . . . . . . . . . . . . . . . . .. 107
		7.1.1 Parities and Selection Patterns. . . . . . . . . . . . . . . . . . . .. 107
		7.1.2 Correlation...................................... 107
		7.1.3 Real-valued Counterpart of a Binary Boolean Function 108
		7.1.4 Orthogonality and Correlation. . . . . . . . . . . . . . . . . . . .. 108
		7.1.5 Spectrum of a Binary Boolean Function. . . . . . . . . . . .. 109
	7.2 Composing Binary Boolean Functions. . . . . . . . . . . . . . . . . . . .. 111
		7.2.1 XOR........................................... 111
		7.2.2 AND........................................... 111
		7.2.3 Disjunct Boolean Functions. . . . . . . . . . . . . . . . . . . . . . .. 112
	7.3 Correlation Matrices .............................. . . . . .. 112
		7.3.1 Equivalence of a Boolean Function and its Correlation Matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 113
		7.3.2 Iterative Boolean Functions. . . . . . . . . . . . . . . . . . . . . . .. 114
		7.3.3 Boolean Permutations ............................ 114
	7.4 Special Boolean Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 116
		7.4.1 XOR with a Constant. . . . . . . . . . . . . . . . . . . . . . . . . . . .. 116
		7.4.2 Linear Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 116
		7.4.3 Bricklayer Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 116
	7.5 Derived Properties. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 117
	7.6 Truncating Functions ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
	7.7 Cross-correlation and Autocorrelation ..................... 119
	7.8 Linear Trails ........................................... 120
	7.9 Ciphers ............................................... 121
		7.9.1 General Case .................................... 121
		7.9.2 Key-Alternating Cipher ........................... 122
		7.9.3 Averaging over all Round Keys ..................... 123
		7.9.4 The Effect of the Key Schedule ..................... 124
	7.10 Correlation Matrices and Linear Cryptanalysis Literature .... 126
		7.10.1 Linear Cryptanalysis of the DES ................... 126
		7.10.2 Linear Hulls ..................................... 127
	7.11 Conclusions ............................................ 129
8. Difference Propagation . .................................. 131
	8.1 Difference Propagation .................................. 131
	8.2 Special Functions ....................................... 132
		8.2.1 Affine Functions .................................. 132
		8.2.2 Bricklayer Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 132
		8.2.3 Truncating Functions ............................. 133
	8.3 Difference Propagation Probabilities and Correlation ........ 133
	8.4 Differential Trails ....................................... 135
		8.4.1 General Case .................................... 135
		8.4.2 Independence of Restrictions ....................... 135
	8.5 Key-Alternating Cipher ................................. 136
	8.6 The Effect of the Key Schedule ........................... 137
	8.7 Differential Trails and Differential Cryptanalysis Literature .. 137
		8.7.1 Differential Cryptanalysis of the DES Revisited ...... 137
		8.7.2 Markov Ciphers .................................. 138
	8.8 Conclusions ............................................ 140
9. The Wide Trail Strategy . ................................. 141
	9.1 Propagation in Key-alternating Block Ciphers .............. 141
		9.1.1 Linear Cryptanalysis .............................. 141
		9.1.2 Differential Cryptanalysis ......................... 143
		9.1.3 Differences between Linear Trails and Differential Trails 144
	9.2 The Wide Trail Strategy ................................ 144
		9.2.1 The ,A Round Structure in Block Ciphers ........... 145
		9.2.2 Weight of a Trail ................................. 147
		9.2.3 Diffusion ........................................ 148
	9.3 Branch Numbers and Two-Round Trails ................... 149
		9.3.1 Derived Properties ............................... 151
		9.3.2 A Two-Round Propagation Theorem ................ 151
	9.4 An Efficient Key-Alternating Structure .................... 152
		9.4.1 The Diffusion Step e .............................. 152
		9.4.2 The Linear Step e .. : ............................ 154
		9.4.3 A Lower Bound on the Bundle Weight of Four-Round Trails ........................................... 154
		9.4.4 An Efficient Construction for e .................... 155
	9.5 The Round Structure of Rijndael ......................... 156
		9.5.1 A Key-Iterated Structure .......................... 156
		9.5.2 Applying the Wide Trail Strategy to Rijndael ........ 160
	9.6 Constructions for e ..................................... 161
	9.7 Choices for the Structure of I and 7r ...................... 163
		9.7.1 The Hypercube Structure ......................... 163
		9.7.2 The Rectangular Structure ........................ 165
	9.8 Conclusions ............................................ 165
10. Cryptanalysis ............................................. 167
	10.1 Truncated Differentials .................................. 167
	10.2 Saturation Attacks ..................................... 167
		10.2.1 Preliminaries .................................... 168
		10.2.2 The Basic Attack ................................. 168
		10.2.3 Influence of the Final Round ....................... 170
		10.2.4 Extension at the End . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 171
		10.2.5 Extension at the Beginning ........................ 171
		10.2.6 Attacks on Six Rounds ............................ 171
		10.2.7 The Herds Attack ................................ 172
	10.3 Gilbert-Minier Attack .................................. 172
		10.3.1 The Four-Round Distinguisher ..................... 172
		10.3.2 The Attack on Seven Rounds ...................... 173
	10.4 Interpolation Attacks ................................... 174
	10.5 Symmetry Properties and Weak Keys as in the DES ........ 174
	10.6 Weak keys as in IDEA .................................. 175
	10.7 Related-Key Attacks .................................... 175
	10.8 Implementation Attacks ................................. 175
		10.8.1 Timing Attacks .................................. 175
		10.8.2 Power Analysis ................................... 176
	10.9 Conclusion ............... : ............................ 178
11. Related Block Ciphers . ................................... 179
	11.1 Overview .............................................. 179
		11.1.1 Evolution ....................................... 179
		11.1.2 The Round Transformation ........................ 180
	11.2 SHARK ............................................... 181
	11.3 Square ................................................. 183
	11.4 BKSQ ................................................ 186
	11.5 Children of Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 189
		11.5.1 Crypton ......................................... 189
		11.5.2 Twofish ....................................... \" 190
		11.5.3 ANUBIS ......................................... 190
		11.5.4 GRAND CRU ..................................... 191
		11.5.5 Hierocrypt ...................................... 191
	11.6 Conclusion ............................................ 191
Appendices 193
A. Propagation Analysis in Galois Fields . .................... 193
	A.1 Functions over GF(2^n) .... , ............................. 194
		A.1.1 Difference Propagation. . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
		A.1.2 Correlation ...................................... 195
		A.1.3 Functions that are Linear over GF(2^n) .............. 197
		A.1.4 Functions that are Linear over GF(2) ............... 198
	A.2 Functions over (GF(2^n))^\\ell ................................ 199
		A.2.1 Difference Propagation ............................ 200
		A.2.2 Correlation ...................................... 200
		A.2.3 Functions that are Linear over GF(2^n) ............ \" 200
		A.2.4 Functions that are Linear over GF(2) ............... 201
	A.3 Representations of GF(p^n) ............................... 202
		A.3.1 Cyclic Representation of GF(p^n) ................... 202
		A.3.2 Vector Space Representation of GF(p^n) ............. 202
		A.3.3 Dual Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 203
	A.4 Boolean Functions and Functions in GF(2^n) ............... 204
		A.4.1 Differences in GF(2)^n and GF(2^n) .................. 204
		A.4.2 Relationship Between Trace Patterns and Selection Patterns ........................................ 205
		A.4.3 Relationship Between Linear Functions in GF(p)^n and GF(p^n) ......................................... 205
		A.4.4 Illustration ...................................... 208
	A.5 Rijndael-GF ........................................... 210
B. Trail Clustering . .......................................... 213
	B.1 Transformations with Maximum Branch Number ........... 214
	B.2 Bounds for Two Rounds ................................. 217
		B.2.1 Difference Propagation ............................ 218
		B.2.2 Correlation ...................................... 220
	B.3 Bounds for Four Rounds ................................ 222
	B.4 Two Case Studies ...................................... 223
		B.4.1 Differential Trails ................................. 223
		B.4.2 Linear Trails ..................................... 225
C. Substitution Tables . ...................................... 229
	C.1 SRD .................................................. 229
	C.2 Other Tables ........................................... 230
		C.2.1 xtime ........................................... 230
		C.2.2 Round Constants ................................. 230
D. Test Vectors . ............................................. 233
	D.1 KeyExpansion ......................................... 233
	D.2 Rijndael(128,128) ....................................... 233
	D.3 Other Block Lengths and Key Lengths .................... 235
E. Reference Code . .......................................... 239
Bibliography . ................................................. 247
Index . ........................................................ 253