Joan Daemen, Vincent Rijmen The Design of Rijndael AES — The Advanced Encryption Standard November 26, 2001 Springer-Verlag Foreword Rijndael was the surprise winner of the contest for the new Advanced En- cryption Standard (AES) for the United States. This contest was organized and run by the National Institute for Standards and Technology (NIST) be- ginning in January 1997; Rijndael was announced as the winner in October 2000. It was the “surprise winner” because many observers (and even some participants) expressed scepticism that the U.S. government would adopt as anencryptionstandardanyalgorithmthatwasnotdesignedbyU.S.citizens. Yet NIST ran an open, international, selection process that should serve as model for other standards organizations. For example, NIST held their 1999 AES meeting in Rome, Italy. The five finalist algorithms were designed by teams from all over the world. In the end, the elegance, efficiency, security, and principled design of RijndaelwonthedayforitstwoBelgiandesigners,JoanDaemenandVincent Rijmen, over the competing finalist designs from RSA, IBM, Counterpane Systems, and an English/Israeli/Danish team. This book is the story of the design of Rijndael, as told by the designers themselves.ItoutlinesthefoundationsofRijndaelinrelationtotheprevious ciphers the authors have designed. It explains the mathematics needed to understand the operation of Rijndael, and it provides reference C code and test vectors for the cipher. Most importantly, this book provides justification for the belief that Rijndael is secure against all known attacks. The world has changed greatly since the DES was adopted as the national standard in 1976. Then, argu- ments about security focussed primarily on the length of the key (56 bits). Differential and linear cryptanalysis (our most powerful tools for breaking ciphers) were then unknown to the public. Today, there is a large public lit- erature on block ciphers, and a new algorithm is unlikely to be considered seriously unless it is accompanied by a detailed analysis of the strength of the cipher against at least differential and linear cryptanalysis. This book introduces the “wide trail” strategy for cipher design, and explains how Rijndael derives strength by applying this strategy. Excellent resistance to differential and linear cryptanalysis follow as a result. High efficiencyisalsoaresult,asrelativelyfewroundsareneededtoachievestrong security. TheadoptionofRijndaelastheAESisamajormilestoneinthehistoryof cryptography.ItislikelythatRijndaelwillsoonbecomethemostwidely-used cryptosystem in the world. This wonderfully written book by the designers themselves is a “must read” for anyone interested in understanding this de- velopment in depth. Ronald L. Rivest Viterbi Professor of Computer Science MIT Preface This book is about the design of Rijndael, the block cipher that became the Advanced Encryption Standard (AES). According to the ‘Handbook of Applied Cryptography’ [68], a block cipher can be described as follows: A block cipher is a function which maps n-bit plaintext blocks to n- bit ciphertext blocks; n is called the block length. [...] The function is parameterized by a key. Although block ciphers are used in many interesting applications such as e- commerce and e-security, this book is not about applications. Instead, this bookgivesadetaileddescriptionofRijndaelandexplainsthedesignstrategy that was used to develop it. Structure of this book When we wrote this book, we had basically two kinds of readers in mind. Perhaps the largest group of readers will consist of people who want to read a full and unambiguous description of Rijndael. For those readers, the most important chapter of this book is Chap. 3, that gives its comprehensive de- scription. In order to follow our description, it might be helpful to read the preliminaries given in Chap. 2. Advanced implementation aspects are dis- cussed in Chap. 4. A short overview of the AES selection process is given in Chap. 1. A large part of this book is aimed at the readers who want to know why we designed Rijndael in the way we did. For them, we explain the ideas and principles underlying the design of Rijndael, culminating in our wide trail design strategy. In Chap. 5 we explain our approach to block cipher design and the criteria that played an important role in the design of Rijndael. Our design strategy has grown out of our experiences with linear and differential cryptanalysis, two cryptanalytical attacks that have been applied with some success to the previous standard, the Data Encryption Standard (DES). In Chap. 6 we give a short overview of the DES and of the differential and the linear attacks that are applied to it. Our framework to describe linear cryptanalysis is explained in Chap. 7; differential cryptanalysis is described inChap.8.Finally,inChap.9,weexplainhowthewidetraildesignstrategy follows from these considerations Chapter 10 gives an overview of the published attacks on reduced-round variants of Rijndael. Chapter 11 gives an overview of ciphers related to Rijndael. We describe its predecessors and discuss their similarities and dif- ferences. This is followed by a short description of a number of block ciphers that have been strongly influenced by Rijndael and its predecessors. InAppendixAweshowhowlinearanddifferentialanalysiscanbeapplied to ciphers that are defined in terms of finite field operations rather than Boolean functions. In Appendix B we discuss extensions of differential and linear cryptanalysis. To assist programmers, Appendix C lists some tables that are used in various descriptions of Rijndael, Appendix D gives a set of test vectors, and Appendix E consists of an example implementation of Rijndael in the C programming language. See Fig. 1 for a graphical representation of the different ways to read this book. 1 4 (cid:3) (cid:1) (cid:1) 2 3 10 (cid:2) (cid:1) (cid:1) (cid:1) (cid:1) (cid:3) (cid:2) 5 6 7 8 9 11 Fig. 1. Logical dependence of the chapters. Large portions of this book have already been published before: Joan’s PhD thesis [18], Vincent’s PhD thesis [80], our submission to AES [26], and our paper on linear frameworks for block ciphers [22]. Acknowledgements This book would not have been written without the support and help of many people. It is impossible for us to list all people who contributed along the way. Although we probably will make oversights, we would like to name some of our supporters here. First of all, we would like to thank the many cryptographers who con- tributed to developing the theory on the design of symmetric ciphers, and fromwhowelearnedmuchofwhatweknowtoday.Wewouldliketomention explicitly the people who gave us feedback in the early stages of the design process: Johan Borst, Antoon Bosselaers, Paulo Barreto, Craig Clapp, Erik De Win, Lars R. Knudsen, and Bart Preneel. Elaine Barker, James Foti and Miles Smid, and all the other people at NIST, who worked very hard to make the AES process possible and visible. The moral support of our family and friends, without whom we would never have persevered. Brian Gladman, who provided test vectors. Othmar Staffelbach, Elisabeth Oswald, Lee McCulloch and other proof- readers who provided very valuable feedback and corrected numerous errors and oversights. The financial support of K.U.Leuven, the Fund for Scientific Research – Flanders(Belgium),Banksys,ProtonWorldandCryptomathicisalsogreatly appreciated. November 2001 Joan Daemen and Vincent Rijmen Contents 1. The Advanced Encryption Standard Process.............. 1 1.1 In the Beginning ... .................................... 1 1.2 AES: Scope and Significance ............................. 1 1.3 Start of the AES Process ................................ 2 1.4 The First Round ....................................... 3 1.5 Evaluation Criteria ..................................... 4 1.5.1 Security......................................... 4 1.5.2 Costs ........................................... 4 1.5.3 Algorithm and Implementation Characteristics ....... 4 1.6 Selection of Five Finalists ............................... 5 1.6.1 The Second AES Conference....................... 5 1.6.2 The Five Finalists ................................ 6 1.7 The Second Round ..................................... 7 1.8 The Selection .......................................... 7 2. Preliminaries ............................................. 9 2.1 Finite Fields ........................................... 10 2.1.1 Groups, Rings, and Fields ......................... 10 2.1.2 Vector Spaces.................................... 11 2.1.3 Fields with a Finite Number of Elements ............ 13 2.1.4 Polynomials over a Field .......................... 13 2.1.5 Operations on Polynomials ........................ 14 2.1.6 Polynomials and Bytes............................ 15 2.1.7 Polynomials and Columns ......................... 16 2.2 Linear Codes .......................................... 17 2.2.1 Definitions ...................................... 17 2.2.2 MDS codes ...................................... 19 2.3 Boolean Functions...................................... 19 2.3.1 Bundle Partitions ................................ 20 2.3.2 Transpositions ................................... 21 2.3.3 Bricklayer Functions .............................. 22 2.3.4 Iterative Boolean Transformations .................. 22 2.4 Block Ciphers.......................................... 23 2.4.1 Iterative Block Ciphers............................ 24 2.4.2 Key-Alternating Block Ciphers..................... 25 2.5 Block Cipher Modes of Operation ........................ 27 2.5.1 Block Encryption Modes .......................... 27 2.5.2 Key-Stream Generation Modes..................... 27 2.5.3 Message Authentication Modes..................... 28 2.5.4 Cryptographic Hashing............................ 29 2.6 Conclusions............................................ 29 3. Specification of Rijndael .................................. 31 3.1 Differences between Rijndael and the AES................. 31 3.2 Input and Output for Encryption and Decryption .......... 31 3.3 Structure of Rijndael.................................... 33 3.4 The Round Transformation .............................. 33 3.4.1 The SubBytes Step............................... 34 3.4.2 The ShiftRows Step.............................. 37 3.4.3 The MixColumns Step............................. 38 3.4.4 The Key Addition ................................ 40 3.5 The Number of Rounds ................................. 41 3.6 Key Schedule .......................................... 43 3.6.1 Design Criteria................................... 43 3.6.2 Selection ........................................ 43 3.7 Decryption ............................................ 45 3.7.1 Decryption for a Two-Round Rijndael Variant ....... 45 3.7.2 Algebraic Properties .............................. 46 3.7.3 The Equivalent Decryption Algorithm .............. 48 3.8 Conclusions............................................ 50 4. Implementation Aspects .................................. 53 4.1 8-Bit Platforms ........................................ 53 4.1.1 Finite Field Multiplication......................... 53 4.1.2 Encryption ...................................... 54 4.1.3 Decryption ...................................... 55 4.2 32-Bit Platforms ....................................... 56 4.3 Dedicated Hardware .................................... 59 4.3.1 Decomposition of SRD ............................ 60 4.3.2 Efficient Inversion in GF(28)....................... 61 4.4 Multiprocessor Platforms................................ 61 4.5 Performance Figures .................................... 62 4.6 Conclusions............................................ 62 5. Design Philosophy ........................................ 63 5.1 Generic Criteria in Cipher Design ........................ 63 5.1.1 Security......................................... 63 5.1.2 Efficiency ....................................... 64 5.1.3 Key Agility...................................... 64 5.1.4 Versatility ....................................... 64 5.1.5 Discussion....................................... 64 5.2 Simplicity ............................................. 65 5.3 Symmetry ............................................. 65 5.3.1 Symmetry Across the Rounds...................... 66 5.3.2 Symmetry Within the Round Transformation ........ 66 5.3.3 Symmetry in the D-box ........................... 67 5.3.4 Symmetry and Simplicity in the S-box .............. 68 5.3.5 Symmetry between Encryption and Decryption ...... 68 5.3.6 Additional Benefits of Symmetry ................... 68 5.4 Choice of Operations.................................... 69 5.4.1 Arithmetic Operations ............................ 70 5.4.2 Data-Dependent Shifts ............................ 70 5.5 Approach to Security ................................... 71 5.5.1 Security Goals ................................... 71 5.5.2 Unknown Attacks Versus Known Attacks............ 72 5.5.3 Provable Security Versus Provable Bounds........... 73 5.6 Approaches to Design ................................... 73 5.6.1 Non-Linearity and Diffusion Criteria................ 73 5.6.2 ResistanceagainstDifferentialandLinearCryptanalysis 73 5.6.3 Local Versus Global Optimization .................. 74 5.7 Key-Alternating Cipher Structure ........................ 76 5.8 The Key Schedule ...................................... 76 5.8.1 The Function of a Key Schedule.................... 76 5.8.2 Key Expansion and Key Selection .................. 77 5.8.3 The Cost of the Key Expansion .................... 77 5.8.4 A Recursive Key Expansion ....................... 78 5.9 Conclusions............................................ 79 6. The Data Encryption Standard ........................... 81 6.1 The DES .............................................. 81 6.2 Differential Cryptanalysis................................ 83 6.3 Linear Cryptanalysis.................................... 85 6.4 Conclusions............................................ 87 7. Correlation Matrices ..................................... 89 7.1 The Walsh-Hadamard Transform ......................... 89 7.1.1 Parities and Selection Patterns..................... 89 7.1.2 Correlation ...................................... 89 7.1.3 Real-valued Counterpart of a Binary Boolean Function 90 7.1.4 Orthogonality and Correlation ..................... 90 7.1.5 Spectrum of a Binary Boolean Function ............. 91 7.2 Composing Binary Boolean Functions..................... 93 7.2.1 XOR ........................................... 93 7.2.2 AND ........................................... 93 7.2.3 Disjunct Boolean Functions........................ 94 7.3 Correlation Matrices .................................... 94 7.3.1 EquivalenceofaBooleanFunctionanditsCorrelation Matrix .......................................... 95 7.3.2 Iterative Boolean Functions........................ 96 7.3.3 Boolean Permutations ............................ 96 7.4 Special Boolean Functions ............................... 98 7.4.1 XOR with a Constant............................. 98 7.4.2 Linear Functions ................................. 98 7.4.3 Bricklayer Functions .............................. 98 7.5 Derived Properties...................................... 99 7.6 Truncating Functions ................................... 100 7.7 Cross-correlation and Autocorrelation..................... 101 7.8 Linear Trails........................................... 102 7.9 Ciphers ............................................... 103 7.9.1 General Case .................................... 103 7.9.2 Key-Alternating Cipher ........................... 104 7.9.3 Averaging over all Round Keys..................... 105 7.9.4 The Effect of the Key Schedule..................... 106 7.10 Correlation Matrices and Linear Cryptanalysis Literature.... 108 7.10.1 Linear Cryptanalysis of the DES ................... 108 7.10.2 Linear Hulls ..................................... 109 7.11 Conclusions............................................ 111 8. Difference Propagation ................................... 113 8.1 Difference Propagation .................................. 113 8.2 Special Functions....................................... 114 8.2.1 Affine Functions.................................. 114 8.2.2 Bricklayer Functions .............................. 114 8.2.3 Truncating Functions ............................. 115 8.3 Difference Propagation Probabilities and Correlation........ 115 8.4 Differential Trails....................................... 117 8.4.1 General Case .................................... 117 8.4.2 Independence of Restrictions....................... 117 8.5 Key-Alternating Cipher ................................. 118 8.6 The Effect of the Key Schedule........................... 119 8.7 Differential Trails and Differential Cryptanalysis Literature .. 119 8.7.1 Differential Cryptanalysis of the DES Revisited ...... 119 8.7.2 Markov Ciphers .................................. 120 8.8 Conclusions............................................ 122