The Design of Rijndael. AES - The Advanced Encryption Standard

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