Main
The Design Of Rijndael: The Advanced Encryption Standard (AES)
The Design Of Rijndael: The Advanced Encryption Standard (AES)
Joan Daemen, Vincent Rijmen
This is the authoritative guide to Rijndael, the block cipher whose elegance, efficiency, security, and principled design made it the Advanced Encryption Standard (AES), now the most widely applied data encryption technology. The authors developed the Rijndael algorithm and in this book they explain the AES selection process and their motivation in the light of the earlier Data Encryption Standard. They explain their design philosophy and implementation and optimization aspects, and the strength of their approach against cryptanalysis. They support the text with the relevant mathematics, reference code, and test vectors. In this new edition the authors updated content throughout, added new chapters, and adapted their text to the new terminology in use since the first edition. This is a valuable reference for all professionals, researchers, and graduate students engaged with data encryption.
Year:
2020
Edition:
2nd Edition
Publisher:
Springer
Language:
english
Pages:
286
ISBN 10:
3662607689
ISBN 13:
9783662607695
Series:
Information Security And Cryptography
File:
PDF, 2.61 MB
Download (pdf, 2.61 MB)
 Open in Browser
 Checking other formats...
 Convert to EPUB
 Convert to FB2
 Convert to MOBI
 Convert to TXT
 Convert to RTF
 Converted file can differ from the original. If possible, download the file in its original format.
 Please login to your account first

Need help? Please read our short guide how to send a book to Kindle.
The file will be sent to your email address. It may take up to 15 minutes before you receive it.
The file will be sent to your Kindle account. It may takes up to 15 minutes before you received it.
Please note you need to add our email km0@bookmail.org to approved email addresses. Read more.
Please note you need to add our email km0@bookmail.org to approved email addresses. Read more.
Most frequently terms
key^{767}
round^{609}
rijndael^{417}
linear^{407}
cipher^{380}
block^{362}
trail^{304}
trails^{295}
transformation^{264}
correlation^{227}
rounds^{216}
boolean^{210}
bytes^{210}
function^{203}
attacks^{181}
box^{180}
functions^{180}
bit^{177}
active^{174}
length^{172}
bits^{172}
input^{172}
output^{171}
attack^{167}
ciphers^{167}
cryptanalysis^{165}
values^{154}
value^{149}
boxes^{147}
byte^{147}
matrix^{147}
aes^{141}
elements^{140}
block cipher^{131}
security^{130}
structure^{126}
hence^{125}
design^{125}
related^{122}
propagation^{121}
keys^{116}
round transformation^{115}
encryption^{113}
vector^{112}
edp^{110}
theorem^{110}
srd^{109}
columns^{105}
probability^{103}
column^{102}
springer^{99}
sect^{98}
key schedule^{94}
denoted^{94}
branch number^{91}
round key^{90}
block length^{88}
multiplication^{84}
implementation^{83}
algorithm^{82}
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
1

2

Information Security and Cryptography Joan Daemen Vincent Rijmen The Design of Rijndael The Advanced Encryption Standard (AES) Second Edition Information Security and Cryptography Series Editors David Basin Kenny Paterson Advisory Board Michael Backes Gilles Barthe Ronald Cramer Ivan Damgård Andrew D. Gordon Joshua D. Guttman Christopher Kruegel Ueli Maurer Tatsuaki Okamoto Adrian Perrig Bart Preneel More information about this series at http://www.springer.com/series/4752 Joan Daemen • Vincent Rijmen The Design of Rijndael The Advanced Encryption Standard (AES) Second Edition Joan Daemen Digital Security Group Radboud University Nijmegen Nijmegen, The Netherlands Vincent Rijmen COSIC Group KU Leuven Heverlee, Belgium ISSN 2197845X (electronic) ISSN 16197100 Information Security and Cryptography ISBN 9783662607688 ISBN 9783662607695 (eBook) https://doi.org/10.1007/9783662607695 © SpringerVerlag GmbH Germany, part of Springer Nature 2002, 2020 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors, and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein o; r for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. This Springer imprint is published by the registered company SpringerVerlag GmbH, DE part of Springer Nature. The registered company address is: Heidelberger Platz 3, 14197 Berlin, Germany Foreword Rijndael was the surprise winner of the contest for the new Advanced Encryption Standard (AES) for the United States. This contest was organized and run by the National Institute of Standards and Technology (NIST) beginning 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 US government would adopt as an encryption standard any algorithm that was not designed by US citizens. Yet NIST ran an open, international, selection process that should serve as a model for other standards organizations. For example, NIST held their 1999 AES meeting in Rome, Italy. The ﬁve ﬁnalist algorithms were designed by teams from all over the world. In the end, the elegance, eﬃciency, security, and principled design of Rijndael won the day for its two Belgian designers, Joan Daemen and Vincent Rijmen, over the competing ﬁnalist 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. It outlines the foundations of Rijndael in relation to the previous 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 justiﬁcation 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, arguments about security focused primarily on the length of the key (56 bits). Diﬀerential and linear cryptanalysis (our most powerful tools for breaking ciphers) were then unknown to the public. Today, there is a large public literature 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 diﬀerential 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 diﬀerential and linear cryptanalysis follows as a result. High eﬃciency is also a result, as relatively few rounds are needed to achieve strong security. V VI Foreword The adoption of Rijndael as the AES is a major milestone in the history of cryptography. It is likely that Rijndael will soon become the most widely used cryptosystem in the world. This wonderfully written book by the designers themselves is a “must read” for anyone interested in understanding this development 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’ [110], a block cipher can be described as follows: A block cipher is a function which maps nbit plaintext blocks to nbit 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 ecommerce and esecurity, this book is not about applications. Instead, this book gives a detailed description of Rijndael and explains the design strategy 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, which gives its comprehensive description. In order to follow our description, it might be helpful to read the preliminaries given in Chap. 2. Advanced implementation aspects are discussed 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 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 diﬀerential 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 diﬀerential and the linear attacks that are applied to it. Our framework to describe linear cryptanalysis is explained in Chap. 7; diﬀerential cryptanalysis is described VII VIII Preface in Chap. 8. Finally, in Chap. 9, we explain how the wide trail design strategy follows from these considerations. Chap. 10 gives an overview of the published attacks on reducedround variants of Rijndael. Chap. 11 gives an overview of ciphers related to Rijndael. We describe its predecessors and discuss their similarities and diﬀerences. This is followed by a short description of a number of block ciphers that have been strongly inﬂuenced by Rijndael and its predecessors. In Chap. 12 we show how linear and diﬀerential analysis can be applied to ciphers that are deﬁned in terms of ﬁnite ﬁeld operations rather than Boolean functions. In Chap. 13 we discuss extensions of diﬀerential and linear cryptanalysis. In Chap. 14 we study the probability of diﬀerentials and trails over two rounds of Rijndael, and in Chap. 15 we deﬁne plateau trails. To assist programmers, Appendix A lists some tables that are used in various descriptions of Rijndael, Appendix B gives a set of test vectors, and Appendix C consists of an example implementation of Rijndael in the C programming language. Acknowledgments 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 contributed to developing the theory on the design of symmetric ciphers, and from who we learned much of what we know today. We would like to mention 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 Staﬀelbach, Elisabeth Oswald, Lee McCulloch and other proofreaders, who provided very valuable feedback and corrected numerous errors and oversights. The ﬁnancial support of KU Leuven, the Fund for Scientiﬁc Research – Flanders (Belgium), Banksys, Proton World and Cryptomathic is also greatly appreciated. November 2001 Joan Daemen and Vincent Rijmen Preface IX Preface to the second edition This edition contains updates of several chapters as well as four new chapters (Chaps. 12 to 15). We adapted our text to new terminology that has come into use since the ﬁrst edition and removed some material that is now obsolete, including the original Appendix A (Propagation Analysis in Galois Fields) and the original Appendix B (Trail Clustering). We thank Ronan Nugent of Springer for his persistent encouragements to ﬁnalize this second edition. We thank Dave, Eric Bach, Nicolas T. Courtois, Praveen Gauravaram, Jorge Nakahara Jr., Ralph Wernsdorf, Shengbo Xu and Uyama Yasumasa for pointing out errors in the ﬁrst edition of this book. We thank Bart Mennink for proofreading some of the updates. All remaining errors and those newly introduced are of course our own. July 2019 Joan Daemen and Vincent Rijmen Contents 1. The Advanced Encryption Standard Process . . . . . . . . . . . . . . 1.1 In the Beginning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 AES: Scope and Signiﬁcance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Start of the AES Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 The First Round . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Evaluation Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.2 Costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3 Algorithm and Implementation Characteristics . . . . . . . 1.6 Selection of Five Finalists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.1 The Second AES Conference . . . . . . . . . . . . . . . . . . . . . . . 1.6.2 The Five Finalists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 The Second Round . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 The Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 2 3 4 4 4 4 5 5 6 7 7 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Groups, Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 Fields with a Finite Number of Elements . . . . . . . . . . . . 2.1.4 Polynomials over a Field . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.5 Operations on Polynomials . . . . . . . . . . . . . . . . . . . . . . . . 2.1.6 Polynomials and Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.7 Polynomials and Columns . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.8 Functions over Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.9 Representations of GF(pn ) . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 MDS Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Tuple Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Transpositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Bricklayer Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 Iterative Boolean Transformations . . . . . . . . . . . . . . . . . . 9 10 10 11 13 13 14 15 16 17 18 20 20 22 22 23 24 25 26 XI XII Contents 2.4 Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.4.1 Iterative Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4.2 KeyAlternating Block Ciphers . . . . . . . . . . . . . . . . . . . . . 28 3. Speciﬁcation of Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Diﬀerences Between Rijndael and the AES . . . . . . . . . . . . . . . . . 3.2 Input and Output for Encryption and Decryption . . . . . . . . . . 3.3 Structure of Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 The Round Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 The SubBytes Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 The ShiftRows Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.3 The MixColumns Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.4 The Key Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.5 The Rijndael Super Box . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 The Number of Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.1 Design Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6.2 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7.1 Decryption for a TwoRound Rijndael Variant . . . . . . . 3.7.2 Algebraic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7.3 The Equivalent Decryption Algorithm . . . . . . . . . . . . . . 3.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 31 31 33 33 34 37 39 41 41 42 43 44 44 46 46 48 48 50 4. Implementation Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 EightBit Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 FiniteField Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.3 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 ThirtyTwoBit Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 TTable Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Bitsliced Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Dedicated Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Decomposition of SRD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Eﬃcient Inversion in GF(28 ) . . . . . . . . . . . . . . . . . . . . . . . 4.3.3 AESNI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Multiprocessor Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 53 53 54 55 56 56 59 60 61 61 62 62 63 5. Design Philosophy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Generic Criteria in Cipher Design . . . . . . . . . . . . . . . . . . . . . . . . 5.1.1 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.2 Eﬃciency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.3 Key Agility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.4 Versatility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 65 65 65 66 66 Contents XIII 5.1.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Simplicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Symmetry Across the Rounds . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Symmetry Within the Round Transformation . . . . . . . . 5.3.3 Symmetry in the DBox . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.4 Symmetry and Simplicity in the SBox . . . . . . . . . . . . . . 5.3.5 Symmetry Between Encryption and Decryption . . . . . . 5.3.6 Additional Beneﬁts of Symmetry . . . . . . . . . . . . . . . . . . . 5.4 Choice of Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Arithmetic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 DataDependent Shifts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Approach to Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.1 Security Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.2 Translation of Security Goals into Modern Security Notions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5.3 Unknown Attacks Versus Known Attacks . . . . . . . . . . . . 5.5.4 Provable Security Versus Provable Bounds . . . . . . . . . . . 5.6 Approaches to Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6.1 Nonlinearity and Diﬀusion Criteria . . . . . . . . . . . . . . . . . 5.6.2 Resistance Against Diﬀerential and Linear Cryptanalysis 5.6.3 Local Versus Global Optimization . . . . . . . . . . . . . . . . . . 5.7 KeyAlternating Cipher Structure . . . . . . . . . . . . . . . . . . . . . . . . 5.8 The Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.8.1 The Function of a Key Schedule . . . . . . . . . . . . . . . . . . . . 5.8.2 Key Expansion and Key Selection . . . . . . . . . . . . . . . . . . 5.8.3 The Cost of the Key Expansion . . . . . . . . . . . . . . . . . . . . 5.8.4 A Recursive Key Expansion . . . . . . . . . . . . . . . . . . . . . . . 5.9 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 75 76 76 76 76 77 79 80 80 80 81 81 82 6. The Data Encryption Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 The DES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Diﬀerential Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Linear Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 83 85 87 89 7. Correlation Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 The WalshHadamard Transform . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.1 Parities and Masks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.2 Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1.3 RealValued Counterpart of a Binary Boolean Function 7.1.4 Orthogonality and Correlation . . . . . . . . . . . . . . . . . . . . . 7.1.5 Spectrum of a Binary Boolean Function . . . . . . . . . . . . . 7.2 Composing Binary Boolean Functions . . . . . . . . . . . . . . . . . . . . . 7.2.1 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 91 91 91 92 92 93 95 95 66 66 67 67 68 69 69 69 70 71 71 72 73 73 XIV Contents 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10 7.11 8. 7.2.2 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.3 Disjunct Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . Correlation Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1 Equivalence of a Boolean Function and Its Correlation Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.2 Iterative Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . 7.3.3 Boolean Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . Special Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.1 Addition with a Constant . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.2 Linear Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.3 Bricklayer Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4.4 Keyed Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Derived Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Truncating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Crosscorrelation and Autocorrelation . . . . . . . . . . . . . . . . . . . . . Linear Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.9.1 General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.9.2 KeyAlternating Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.9.3 Averaging over All Round Keys . . . . . . . . . . . . . . . . . . . . 7.9.4 The Eﬀect of the Key Schedule . . . . . . . . . . . . . . . . . . . . . Correlation Matrices and the Linear Cryptanalysis Literature 7.10.1 Linear Cryptanalysis of the DES . . . . . . . . . . . . . . . . . . . 7.10.2 Linear Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 96 96 97 98 98 100 100 100 100 101 101 103 104 105 106 106 106 107 109 111 111 112 113 Diﬀerence Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 8.1 Diﬀerence Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 8.2 Special Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 8.2.1 Aﬃne Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 8.2.2 Bricklayer Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 8.2.3 Truncating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 8.2.4 Keyed Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 8.3 Relation Between DP Values and Correlations . . . . . . . . . . . . . . 118 8.4 Diﬀerential Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 8.4.1 General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 8.4.2 Independence of Restrictions . . . . . . . . . . . . . . . . . . . . . . . 120 8.5 KeyAlternating Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.6 The Eﬀect of the Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 8.7 Diﬀerential Trails and the Diﬀerential Cryptanalysis Literature122 8.7.1 Diﬀerential Cryptanalysis of the DES Revisited . . . . . . 122 8.7.2 Markov Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 8.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Contents 9. XV The Wide Trail Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 9.1 Propagation in KeyAlternating Block Ciphers . . . . . . . . . . . . . 125 9.1.1 Linear Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 9.1.2 Diﬀerential Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . 126 9.1.3 Diﬀerences Between Linear Trails and Diﬀerential Trails128 9.2 The Wide Trail Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 9.2.1 The γλ Round Structure in Block Ciphers . . . . . . . . . . . 129 9.2.2 Weight of a Trail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 9.2.3 Diﬀusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 9.3 Branch Numbers and TwoRound Trails . . . . . . . . . . . . . . . . . . . 133 9.3.1 Derived Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 9.3.2 A TwoRound Propagation Theorem . . . . . . . . . . . . . . . . 135 9.4 An Eﬃcient KeyAlternating Structure . . . . . . . . . . . . . . . . . . . . 136 9.4.1 The Diﬀusion Step θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 9.4.2 The Linear Step Θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.4.3 A Lower Bound on the Byte Weight of FourRound Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 9.4.4 An Eﬃcient Construction for Θ . . . . . . . . . . . . . . . . . . . . 139 9.5 The Round Structure of Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . 140 9.5.1 A KeyIterated Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 140 9.5.2 Applying the Wide Trail Strategy to Rijndael . . . . . . . . 142 9.6 Constructions for θ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 9.7 Choices for the Structure of I and π . . . . . . . . . . . . . . . . . . . . . . 145 9.7.1 The Hypercube Structure . . . . . . . . . . . . . . . . . . . . . . . . . 145 9.7.2 The Rectangular Structure . . . . . . . . . . . . . . . . . . . . . . . . 147 9.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 10. Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.1 Truncated Diﬀerentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2 Saturation Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2.2 The Basic Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2.3 Inﬂuence of the Final Round . . . . . . . . . . . . . . . . . . . . . . . 10.2.4 Extension at the End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2.5 Extension at the Beginning . . . . . . . . . . . . . . . . . . . . . . . . 10.2.6 Attacks on Six Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.2.7 The Herds Attack and Other Extensions . . . . . . . . . . . . 10.2.8 Division Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.3 GilbertMinier and DemirciSelçuk Attack . . . . . . . . . . . . . . . . . 10.3.1 The FourRound Distinguisher . . . . . . . . . . . . . . . . . . . . . 10.3.2 The Attack on Seven Rounds . . . . . . . . . . . . . . . . . . . . . . 10.3.3 The DemirciSelçuk Attack . . . . . . . . . . . . . . . . . . . . . . . . 10.4 Interpolation Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.5 RelatedKey Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.5.1 The Key Schedule of Rijndael256 . . . . . . . . . . . . . . . . . . 149 149 149 150 151 152 153 153 154 154 155 155 155 156 157 157 158 159 XVI Contents 10.5.2 The BiryukovKhovratovich Attack . . . . . . . . . . . . . . . . . 10.5.3 The KAS of the BiryukovKhovratovich Attack . . . . . . 10.6 Biclique Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.7 Rebound Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.8 ImpossibleDiﬀerential Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.8.1 Principle of the Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.8.2 Application to Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.9 Implementation Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.9.1 Timing Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.9.2 Power Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 160 162 162 163 163 164 164 164 165 166 11. The Road to Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.2 The Round Transformation . . . . . . . . . . . . . . . . . . . . . . . . 11.2 SHARK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.3 Square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.4 BKSQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 169 169 170 171 173 176 179 12. Correlation Analysis in GF(2n ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 12.1 Description of Correlation in Functions over GF(2n ) . . . . . . . . 182 12.1.1 Functions That Are Linear over GF(2n ) . . . . . . . . . . . . . 184 12.1.2 Functions That Are Linear over GF(2) . . . . . . . . . . . . . . 184 12.2 Description of Correlation in Functions over GF(2n ) . . . . . . . 186 n 12.2.1 Functions That Are Linear over GF(2 ) . . . . . . . . . . . . . 187 12.2.2 Functions That Are Linear over GF(2) . . . . . . . . . . . . . . 187 12.3 Boolean Functions and Functions in GF(2n ) . . . . . . . . . . . . . . . 188 12.3.1 Relationship Between Trace Masks and Selection Masks188 n 12.3.2 Relationship Between Linear Functions in GF(2) and n GF(2 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 12.4 RijndaelGF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 13. On the EDP and the ELP of Two and Four Rijndael Rounds195 13.1 Properties of MDS Mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 13.2 Bounds for Two Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 13.2.1 Diﬀerence Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 13.2.2 Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 13.3 Bounds for Four Rounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 13.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 Contents XVII 205 205 207 207 209 14. TwoRound Diﬀerential Trail Clustering . . . . . . . . . . . . . . . . . . 14.1 The Multiplicative Inverse in GF(2n ) . . . . . . . . . . . . . . . . . . . . . 14.2 Bundles in the Rijndael Super Box . . . . . . . . . . . . . . . . . . . . . . . 14.2.1 Diﬀerentials, Trails and Trail Cores . . . . . . . . . . . . . . . . . 14.2.2 Bundles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.2.3 Number of Bundles with a Given Number of Active Bytes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.3 Conditions for a Trail Core to Extend to a Trail . . . . . . . . . . . . 14.3.1 The Naive Super Box . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.3.2 Sharp Conditions and Blurred Conditions . . . . . . . . . . . 14.4 Number of Trail Cores in a Bundle Extending to a Trail . . . . . 14.4.1 Bundles with One Active SBox in the First Round . . . 14.4.2 Any Bundle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.4.3 Experimental Veriﬁcation . . . . . . . . . . . . . . . . . . . . . . . . . 14.5 EDP of a Bundle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.5.1 Multiple Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.5.2 Occurrence in Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.5.3 How Li Makes a Diﬀerence . . . . . . . . . . . . . . . . . . . . . . . . 14.6 EDP of a Diﬀerential . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14.6.1 Diﬀerentials with Activity Pattern (1110; 1110) . . . . . . . 14.6.2 A Bound on the Multiplicity . . . . . . . . . . . . . . . . . . . . . . . 14.7 Diﬀerentials with the Maximum EDP Value . . . . . . . . . . . . . . . 14.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 211 211 212 213 213 214 215 216 217 217 218 218 218 219 220 221 15. Plateau Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.2 TwoRound Plateau Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.2.1 Planar Diﬀerentials and Maps . . . . . . . . . . . . . . . . . . . . . . 15.2.2 Plateau Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.2.3 Plateau Trails in Super Boxes . . . . . . . . . . . . . . . . . . . . . . 15.3 Plateau Trails over More Than Two Rounds . . . . . . . . . . . . . . . 15.4 Further Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.4.1 Eﬀect of the Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . 15.4.2 Impact on the DP of Diﬀerentials . . . . . . . . . . . . . . . . . . 15.5 TwoRound Trails in Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.5.1 Trails in the Rijndael Super Box . . . . . . . . . . . . . . . . . . . 15.5.2 Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.5.3 Inﬂuence of L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.6 Trails over Four or More Rounds in Rijndael . . . . . . . . . . . . . . . 15.7 DP of Diﬀerentials in Rijndael . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.8 Related Diﬀerentials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.8.1 Deﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.8.2 Related Diﬀerentials and Plateau Trails . . . . . . . . . . . . . 15.9 Determining the Related Diﬀerentials . . . . . . . . . . . . . . . . . . . . . 15.9.1 First Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 223 224 224 226 227 229 230 230 231 231 231 232 234 234 236 236 236 237 239 239 XVIII Contents 15.9.2 For Any Given Diﬀerential . . . . . . . . . . . . . . . . . . . . . . . . 15.9.3 For All Diﬀerentials with the Same Activity Pattern . . 15.9.4 Second Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.9.5 A Combinatorial Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.10 Implications for RijndaelLike Super Boxes . . . . . . . . . . . . . . . . 15.10.1 Related Diﬀerentials over Circulant Matrices . . . . . . . . 15.10.2 Related Diﬀerentials in MixColumns . . . . . . . . . . . . . . . . 15.10.3 Avoiding Related Diﬀerentials . . . . . . . . . . . . . . . . . . . . . 15.11 Conclusions and Further Work . . . . . . . . . . . . . . . . . . . . . . . . . . 240 241 241 243 244 244 244 245 246 A. Substitution Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 SRD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Other Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2.1 xtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2.2 Round Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 249 252 252 252 B. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1 KeyExpansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Rijndael(128,128) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 Other Block Lengths and Key Lengths . . . . . . . . . . . . . . . . . . . . 253 253 253 255 C. Reference Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 1. The Advanced Encryption Standard Process The main subject of this book would probably have remained an esoteric topic of cryptographic research — with a name unpronounceable to most of the world — without the Advanced Encryption Standard (AES) process. Therefore, we thought it proper to include a short overview of the AES process. 1.1 In the Beginning . . . In January 1997, the US National Institute of Standards and Technology (NIST) announced the start of an initiative to develop a new encryption standard: the AES. The new encryption standard was to become a Federal Information Processing Standard (FIPS), replacing the old Data Encryption Standard (DES) and Triple DES. Unlike the selection process for the DES, the Secure Hash Algorithm (SHA1) and the Digital Signature Algorithm (DSA), NIST had announced that the AES selection process would be open. Anyone could submit a candidate cipher. Each submission, provided it met the requirements, would be considered on its merits. NIST would not perform any security or eﬃciency evaluation itself, but instead invited the cryptology community to mount attacks and try to cryptanalyze the diﬀerent candidates, and anyone who was interested to evaluate implementation cost. All results could be sent to NIST as public comments for publication on the NIST AES web site or be submitted for presentation at AES conferences. NIST would merely collect contributions, using them as the basis for their selection. NIST would motivate their choices in evaluation reports. 1.2 AES: Scope and Signiﬁcance The oﬃcial scope of a FIPS standard is quite limited: the FIPS only applies to the US Federal Administration. Furthermore, the new AES would only be used for documents that contain sensitive but not classiﬁed information. © SpringerVerlag GmbH Germany, part of Springer Nature 2020 J. Daemen, V. Rijmen, The Design of Rijndael, Information Security and Cryptography, https://doi.org/10.1007/9783662607695_1 1 2 1. The Advanced Encryption Standard Process However, it was anticipated that the impact of the AES would be much larger than this: for the AES is the successor of the DES, the cipher that ever since its adoption has been used as a worldwide de facto cryptographic standard by banks, administrations and industry. The major factors for the quick acceptance of Rijndael are that it is available royaltyfree, and that it can be implemented easily on a wide range of platforms without reducing bandwidth in a signiﬁcant way. 1.3 Start of the AES Process In September 1997, the ﬁnal request for candidate nominations for the AES was published. The minimum functional requirements asked for symmetric block ciphers capable of supporting block lengths of 128 bits and key lengths of 128, 192 and 256 bits. An early draft of the AES functional requirements had asked for block ciphers also supporting block sizes of 192 and 256 bits, but this requirement was dropped later on. Nevertheless, since the request for proposals mentioned that extra functionality in the submissions would be received favorably, some submitters decided to keep the variable block length in the designs. (Examples include RC6 and Rijndael.) NIST declared that it was looking for a block cipher as secure as Triple DES, but much more eﬃcient. Another mandatory requirement was that the submitters agreed to make their cipher available on a worldwide royaltyfree basis if it were to be selected as the AES. In order to qualify as an oﬃcial AES candidate, the designers had to provide: 1. A complete written speciﬁcation of the block cipher in the form of an algorithm. 2. A reference implementation in ANSI C, and mathematically optimized implementations in ANSI C and Java. 3. Implementations of a series of knownanswer and Monte Carlo tests, as well as the expected outputs of these tests for a correct implementation of their block cipher. 4. Statements concerning the estimated computational eﬃciency in both hardware and software, the expected strength against cryptanalytic attacks, and the advantages and limitations of the cipher in various applications. 5. An analysis of the cipher’s strength against known cryptanalytic attacks. It turned out that the required eﬀort to produce a ‘complete and proper’ submission package would already ﬁlter out several of the proposals. Early in the submission stage, the Cryptix team announced that they would provide Java implementations for all submitted ciphers, as well as Java implementations 1.4 The First Round 3 of the knownanswer and Monte Carlo tests. This generous oﬀer took some weight oﬀ the designers’ shoulders, but still the eﬀort required to compile a submission package was too heavy for some designers. The fact that the AES Application Programming Interface (API), which all submissions were required to follow, was updated twice during the submission stage increased the workload. Table 1.1 lists (in alphabetical order) the 15 submissions that were completed in time and accepted. Table 1.1. The 15 AES candidates accepted for the ﬁrst evaluation round Submissions CAST256 Crypton DEAL DFC E2 FROG HPC LOKI97 Magenta Mars RC6 Rijndael SAFER+ Serpent Twoﬁsh Submitter(s) Entrust (CA) Future Systems (KR) Outerbridge and Knudsen (USA–DK) ENSCNRS (FR) NTT (JP) TecApro (CR) Schroeppel (USA) Brown et al. (AU) Deutsche Telekom (DE) IBM (USA) RSA (USA) Daemen and Rijmen (BE) Cylink (USA) Anderson, Biham and Knudsen (UK–IL–DK) Counterpane (USA) Submitter type Company Company Researchers Researchers Company Company Researcher Researchers Company Company Company Researchers Company Researchers Company 1.4 The First Round The selection process was divided into several stages, with a public workshop to be held near the end of each stage. The process started with a submission stage, which ended on 15 May 1998. All accepted candidates were presented at The First Advanced Encryption Standard Candidate Conference, held in Ventura, California, on 2022 August 1998. This was the oﬃcial start of the ﬁrst evaluation round, during which the international cryptographic community was asked for comments on the candidates. 4 1. The Advanced Encryption Standard Process 1.5 Evaluation Criteria The evaluation criteria for the ﬁrst round were divided into three major categories: security, cost and algorithm and implementation characteristics. NIST invited the cryptology community to mount attacks and try to cryptanalyze the diﬀerent candidates, and anyone interested to evaluate implementation cost. The result could be sent to NIST as public comments or be submitted for presentation at the second AES conference. NIST collected all contributions and would use these to select ﬁve ﬁnalists. In the following sections we discuss the evaluation criteria. 1.5.1 Security Security was the most important category, but perhaps the most diﬃcult to assess. Only a small number of candidates showed some theoretical design ﬂaws. The large majority of the candidates fell into the category ‘no weakness demonstrated’. 1.5.2 Costs The ‘costs’ of the candidates were divided into diﬀerent subcategories. A ﬁrst category was formed by costs associated with intellectual property (IP) issues. First of all, each submitter was required to make his cipher available for free if it were to be selected as the AES. Secondly, each submitter was also asked to make a signed statement that he would not claim ownership or exercise patents on ideas used in another submitter’s proposal that would eventually be selected as the AES. A second category of ‘costs’ was formed by costs associated with the implementation and execution of the candidates. This covers aspects such as computational eﬃciency, program size and working memory requirements in software implementations, and chip area in dedicated hardware implementations. 1.5.3 Algorithm and Implementation Characteristics The category algorithm and implementation characteristics grouped a number of features that are harder to quantify. The ﬁrst one is versatility, meaning the ability to be implemented eﬃciently on diﬀerent platforms. At one end of the spectrum the AES should ﬁt 8bit microcontrollers and smart cards, which have limited storage for the program and a very restricted amount of RAM for working memory. At the other end of the spectrum the AES should be implementable eﬃciently in dedicated hardware, e.g. to provide ontheﬂy encryption/decryption of communication links at gigabitpersecond rates. In 1.6 Selection of Five Finalists 5 between there is the whole range of processors that are used in servers, workstations, PCs, palmtops etc., which are all devices in need of cryptographic support. A prominent place in this range is taken by the Pentium family of processors due to its presence in most personal computers. A second feature is key agility. In most block ciphers, key setup takes some processing. In applications where the same key is used to encrypt large amounts of data, this processing is relatively unimportant. In applications where the key often changes, such as the encryption of Internet Protocol (IP) packets in Internet Protocol Security (IPSEC), the overhead due to key setup may become quite relevant. Obviously, in those applications it is an advantage to have a fast key setup. Finally, there is the criterion of simplicity, which may even be harder to evaluate than cryptographic security. Simplicity is related to the size of the description, the number of diﬀerent operations used in the speciﬁcation, the symmetry or lack of symmetry in the cipher and the ease with which the algorithm can be understood. All other things being equal, NIST considered it to be an advantage for an AES candidate to be more simple for reasons of ease of implementation and conﬁdence in security. 1.6 Selection of Five Finalists In March 1999, the second AES conference was held in Rome, Italy. The remarkable fact that a US Government department organized a conference on a future US Standard in Europe is easily explained. NIST chose to combine the conference with the yearly Fast Software Encryption Workshop, which had for the most part the same target audience and was scheduled to be in Rome. 1.6.1 The Second AES Conference The papers presented at the conference ranged from cryptoattacks, cipher crossanalysis, smartcardrelated papers, and socalled algorithm observations. In the session on cryptographic attacks, it was shown that FROG, Magenta and LOKI97 did not satisfy the security requirements imposed by NIST. For DEAL it was already known in advance that the security requirements were not satisﬁed. For HPC weaknesses had been demonstrated in a paper previously sent to NIST. This eliminated ﬁve candidates. Some cipher crossanalysis papers focused on performance evaluation. The paper of B. Gladman [65], a researcher who had no link with any submission, considered performance on the Pentium processor. From this paper it became clear that RC6, Rijndael, Twoﬁsh, MARS and Crypton were the ﬁve fastest ciphers on this processor. On the other hand, the candidates DEAL, Frog, 6 1. The Advanced Encryption Standard Process Magenta, SAFER+ and Serpent appeared to be problematically slow. Other papers by the Twoﬁsh team (Bruce Schneier et al.) [138] and a French team of 12 cryptographers [10] essentially conﬁrmed this. A paper by E. Biham warned that the security margins of the AES candidates diﬀered greatly and that this should be taken into account in the performance evaluation [21]. The lack of speed of Serpent (with E. Biham in the design team) was seen to be compensated for by a very high margin of security. Discussions on how to measure and take into account security margins lasted until after the third AES conference. In the session on smart cards there were two papers comparing the performance of AES candidates on typical 8bit processors and a 32bit processor: one by G. Keating [78] and one by G. Hachez et al. [69]. From these papers and results from other papers, it became clear that some candidates simply did not ﬁt onto a smart card and that Rijndael was by far the best suited for this platform. In the same session there were some papers that discussed power analysis attacks and the suitability of the diﬀerent candidates for implementations that can resist against these attacks [27, 39, 49]. Finally, in the algorithm observations session, there were a number of papers in which AES submitters reconﬁrmed their conﬁdence in their submission by means of a considerable amount of formulas, graphs and tables and some loyal cryptanalysis (the demonstration of having found no weaknesses after attacks on their own cipher). 1.6.2 The Five Finalists After the workshop there was a relatively calm period that ended with the announcement of the ﬁve candidates by NIST in August 1999. The ﬁnalists were (in alphabetical order): MARS, RC6, Rijndael, Serpent and Twoﬁsh. Along with the announcement of the ﬁnalists, NIST published a status report [118] in which the selection was motivated. The choice coincided with the top ﬁve that resulted from the response to a questionnaire handed out at the end of the second AES workshop. Despite its moderate performance, Serpent made it thanks to its high security margin. The candidates that had not been eliminated because of security problems were not selected mainly for the following reasons: 1. CAST256: comparable to Serpent but with a higher implementation cost. 2. Crypton: comparable to Rijndael and Twoﬁsh but with a lower security margin. 3. DFC: low security margin and bad performance on anything other than 64bit processors. 1.8 The Selection 7 4. E2: comparable to Rijndael and Twoﬁsh in structure, but with a lower security margin and higher implementation cost. 5. SAFER+: high security margin similar to Serpent but even slower. 1.7 The Second Round After the announcement of the ﬁve candidates NIST made another open call for contributions focused on the ﬁnalists. Intellectual property issues and performance and chip area in dedicated hardware implementations entered the picture. A remarkable contribution originated from NSA, presenting the results of hardwareperformance simulations performed for the ﬁnalists. This third AES conference was held in New York City in April 2000. As in the year before, it was combined with the Fast Software Encryption Workshop. In the sessions on cryptographic attacks there were some interesting results but no breakthroughs, since none of the ﬁnalists showed any weaknesses that could jeopardize their security. Most of the results were attacks on reducedround versions of the ciphers. All attacks presented are only of academic relevance in that they are only slightly faster than an exhaustive key search. In the sessions on software implementations, the conclusions of the second workshop were conﬁrmed. In the sessions on dedicated hardware implementations attention was paid to Field Programmable Gate Arrays (FPGAs) and ApplicationSpeciﬁc Integrated Circuits (ASICs). In the papers Serpent came out as a consistently excellent performer. Rijndael and Twoﬁsh also proved to be quite suited for hardware implementation while RC6 turned out to be expensive due to its use of 32bit multiplication. Dedicated hardware implementations of MARS seemed in general to be quite costly. The Rijndaelrelated results presented at this conference are discussed in more detail in Chap. 4 (which is on eﬃcient implementations) and Chap. 10 (which is on cryptanalytic results). At the end of the conference a questionnaire was handed out asking about the preferences of the attendants. Rijndael was resoundingly voted to be the public’s favorite. 1.8 The Selection On 2 October 2000, NIST oﬃcially announced that Rijndael, without modiﬁcations, would become the AES. NIST published an excellent 116page report in which they summarize all contributions and motivate the choice [117]. In the conclusion of this report, NIST motivates the choice of Rijndael with the following words: 8 1. The Advanced Encryption Standard Process Rijndael appears to be consistently a very good performer in both hardware and software across a wide range of computing environments regardless of its use in feedback or nonfeedback modes. Its key setup time is excellent, and its key agility is good. Rijndael’s very low memory requirements make it very well suited for restrictedspace environments, in which it also demonstrates excellent performance. Rijndael’s operations are among the easiest to defend against power and timing attacks. Additionally, it appears that some defense can be provided against such attacks without signiﬁcantly impacting Rijndael’s performance. Finally, Rijndael’s internal round structure appears to have good potential to beneﬁt from instructionlevel parallelism. 2. Preliminaries In this chapter we introduce a number of mathematical concepts and explain the terminology that we need in the speciﬁcation of Rijndael (in Chap. 3), in the treatment of some implementation aspects (in Chap. 4) and when we discuss our design choices (Chaps. 5–9). The ﬁrst part of this chapter starts with a discussion of ﬁnite ﬁelds, the representation of their elements and the impact of this on their operations of addition and multiplication. Subsequently, there is a short introduction to linear codes. Understanding the mathematics is not necessary for a full and correct implementation of the cipher. However, the mathematics are necessary for a good understanding of our design motivations. Knowledge of the underlying mathematical constructions also helps for doing optimized implementations. Not all aspects will be covered in detail; where possible, we refer to books dedicated to the topics we introduce. In the second part of this chapter we introduce the terminology that we use to indicate diﬀerent common types of Boolean functions and block ciphers. When the discussion moves from a general level to an example speciﬁc to Rijndael, the text is put in a grey box. Notation. We use in this book two types of indexing: subscripts: Parts of a larger, named structure are denoted with subscripts. For instance, the bytes of a state a are denoted by ai,j (see Chap. 3). superscripts: In an enumeration of more or less independent objects, where the objects are denoted by their own symbols, we use superscripts. For instance the elements of a nameless set are denoted by {a(1) , a(2) , . . . }, and consecutive rounds of an iterative transformation are denoted by ρ(1) , ρ(2) , . . . (see Sect. 2.3.4). © SpringerVerlag GmbH Germany, part of Springer Nature 2020 J. Daemen, V. Rijmen, The Design of Rijndael, Information Security and Cryptography, https://doi.org/10.1007/9783662607695_2 9 10 2. Preliminaries 2.1 Finite Fields In this section we present a basic introduction to the theory of ﬁnite ﬁelds. For a more formal and elaborate introduction, we refer to the work of Lidl and Niederreiter [95]. 2.1.1 Groups, Rings and Fields We start with the formal deﬁnition of a group. Deﬁnition 2.1.1. An Abelian group (G, +) consists of a set G and an operation deﬁned on its elements, here denoted by ‘+’: + : G × G → G : (a, b) → a + b. (2.1) For the group to qualify as an Abelian group, the operation has to fulﬁll the following conditions: closed: ∀ a, b ∈ G : a + b ∈ G associative: ∀ a, b, c ∈ G : (a + b) + c = a + (b + c) commutative: ∀ a, b ∈ G : a + b = b + a neutral element: ∃ 0 ∈ G, ∀ a ∈ G : a + 0 = a inverse elements: ∀ a ∈ G, ∃ b ∈ G : a + b = 0. (2.2) (2.3) (2.4) (2.5) (2.6) Example 2.1.1. The bestknown example of an Abelian group is (Z, +), the set of integers, with the operation ‘addition’. The structure (Zn , +) is a second example. The set contains the integer numbers 0 to n − 1 and the operation is addition modulo n. Since the addition of integers is the bestknown example of a group, usually the symbol ‘+’ is used to denote an arbitrary group operation. In this book, both an arbitrary group operation and integer addition will be denoted by the symbol ‘+’. Both rings and ﬁelds are formally deﬁned as structures that consist of a set of elements with two operations deﬁned on these elements. Deﬁnition 2.1.2. A ring (R, +, ·) consists of a set R with two operations deﬁned on its elements, here denoted by ‘+’ and ‘·’. For R to qualify as a ring, the operations have to fulﬁll the following conditions: 1. The structure (R, +) is an Abelian group. 2. The operation ‘·’ is closed, and associative over R. There is a neutral element for ‘·’ in R. 2.1 Finite Fields 11 3. The two operations ‘+’ and ‘·’ are related by the law of distributivity: ∀ a, b, c ∈ R : (a + b) · c = (a · c) + (b · c). (2.7) The neutral element for ‘·’ is usually denoted by 1. A ring (R, +, ·) is called a commutative ring if the operation ‘·’ is commutative. Example 2.1.2. The bestknown example of a ring is (Z, +, ·): the set of integers, with the operations ‘addition’ and ‘multiplication’. This ring is a commutative ring. The set of matrices with n rows and n columns, with the operations ‘matrix addition’ and ‘matrix multiplication’ is a ring, but not a commutative ring (if n > 1). Deﬁnition 2.1.3. A structure (F, +, ·) is a ﬁeld if the following two conditions are satisﬁed: 1. (F, +, ·) is a commutative ring. 2. For all elements of F , there is an inverse element in F with respect to the operation ‘·’, except for the element 0, the neutral element of (F, +). A structure (F, +, ·) is a ﬁeld iﬀ both (F, +) and (F \{0}, ·) are Abelian groups and the law of distributivity applies. The neutral element of (F \{0}, ·) is called the unit element of the ﬁeld. Example 2.1.3. The bestknown example of a ﬁeld is the set of real numbers, with the operations ‘addition’ and ‘multiplication.’ Other examples are the set of complex numbers and the set of rational numbers, with the same operations. Note that for these examples the number of elements is inﬁnite. 2.1.2 Vector Spaces Let (F, +, ·) be a ﬁeld, with unit element 1, and let (V, +) be an Abelian group. Let ‘’ be an operation on elements of F and V : : F × V → V. (2.8) Deﬁnition 2.1.4. The structure (F, V, +, +, ·, ) is a vector space over F if the following conditions are satisﬁed: 1. distributivity: ∀ a ∈ F, ∀ v, w ∈ V : a (v + w) = (a v) + (a w) ∀ a, b ∈ F, ∀ v ∈ V : (a + b) v = (a v) + (b v). (2.9) (2.10) 2. associativity: ∀ a, b ∈ F, ∀ v ∈ V : (a · b) v = a (b v). (2.11) 12 2. Preliminaries 3. neutral element: ∀ v ∈ V : 1 v = v. (2.12) The elements of V are called vectors, and the elements of F are the scalars. The operation ‘+’ is called the vector addition, and ‘’ is the scalar multiplication. Example 2.1.4. For any ﬁeld F , the set of ntuples (a0 , a1 , . . . , an−1 ) forms a vector space, where ‘+’ and ‘’ are deﬁned in terms of the ﬁeld operations: (a1 , . . . , an ) + (b1 , . . . , bn ) = (a1 + b1 , . . . , an + bn ) a (b1 , . . . , bn ) = (a · b1 , . . . , a · bn ). (2.13) (2.14) A vector v is a linear combination of the vectors w(1) , w(2) , . . . , w(s) if there exist scalars a(i) such that: v = a(1) w(1) + a(2) w(2) + · · · + a(s) w(s) . (2.15) In a vector space we can always ﬁnd a set of vectors such that all elements of the vector space can be written in exactly one way as a linear combination of the vectors of the set. Such a set is called a basis of the vector space. We will consider only vector spaces where the bases have a ﬁnite number of elements. We denote a basis by a column vector e: T (2.16) e = e(1) , e(2) , . . . e(n) . In this expression the T superscript denotes taking the transpose of the row vector in the righthand side of the equation. The scalars used in this linear combination are called the coordinates of x with respect to the basis e: n (2.17) co(x) = x = (c1 , c2 , . . . , cn ) ⇔ x = i=1 ci e(i) . In order to simplify the notation, from now on we will denote vector addition by the same symbol as the ﬁeld addition (‘+’), and the scalar multiplication by the same symbol as the ﬁeld multiplication (‘·’). It should always be clear from the context what operation the symbols are referring to. A function f is called a linear function of a vector space V over a ﬁeld F , if it has the following properties: ∀ x, y ∈ V : f (x + y) = f (x) + f (y) ∀ a ∈ F, ∀ x ∈ V : f (ax) = af (x). (2.18) (2.19) The linear functions of a vector space can be represented by a matrix multiplication on the coordinates of the vectors. A function f is a linear function n of the vector space GF(p) iﬀ there exists a matrix M such that n co(f (x)) = M · x, ∀ x ∈ GF(p) . (2.20) 2.1 Finite Fields 13 2.1.3 Fields with a Finite Number of Elements A ﬁnite ﬁeld is a ﬁeld with a ﬁnite number of elements. The number of elements in the set is called the order of the ﬁeld. A ﬁeld with order m exists iﬀ m is a prime power, i.e. m = pn for some integer n and with p a prime integer. p is called the characteristic of the ﬁnite ﬁeld. All ﬁnite ﬁelds used in the description of Rijndael have characteristic 2. Fields of the same order are isomorphic: they display exactly the same algebraic structure, diﬀering only in the representation of the elements. In other words, for each prime power there is exactly one ﬁnite ﬁeld, denoted by GF(pn ). From now on, we will only consider ﬁelds with a ﬁnite number of elements. Perhaps the most intuitive examples of ﬁnite ﬁelds are the ﬁelds of prime order p. The elements of a ﬁnite ﬁeld GF(p) can be represented by the integers 0, 1, . . . , p − 1. The two operations of the ﬁeld are then ‘integer addition modulo p’ and ‘integer multiplication modulo p’. For ﬁnite ﬁelds with an order that is not prime, the operations addition and multiplication cannot be represented by addition and multiplication of integers modulo a number. Instead, slightly more complex representations must be introduced. Finite ﬁelds GF(pn ) with n > 1 can be represented in several ways. The representation of GF(pn ) by means of polynomials over GF(p) is quite popular and is the one we have adopted in Rijndael and its predecessors. In the next sections, we explain this representation. 2.1.4 Polynomials over a Field A polynomial over a ﬁeld F is an expression of the form b(x) = bn−1 xn−1 + bn−2 xn−2 + · · · + b2 x2 + b1 x + b0 , (2.21) x being called the indeterminate of the polynomial, and the bi ∈ F the coeﬃcients. The degree of a polynomial equals if bj = 0, ∀j > , and is the smallest number with this property. The set of polynomials over a ﬁeld F is denoted by F [x]. The set of polynomials over a ﬁeld F that have a degree below is denoted by F [x] . In computer memory, the polynomials in F [x] with F a ﬁnite ﬁeld can be stored eﬃciently by storing the coeﬃcients as a string. Example 2.1.5. Let the ﬁeld F be GF(2), and let = 8. The polynomials can conveniently be stored as 8bit values, or bytes: b(x) → b7 b6 b5 b4 b3 b2 b1 b0 . Strings of bits are often abbreviated using the hexadecimal notation. (2.22) 14 2. Preliminaries Example 2.1.6. The polynomial in GF(2)8 x6 + x4 + x2 + x + 1 corresponds to the bit string 01010111, or 57 in hexadecimal notation. 2.1.5 Operations on Polynomials We deﬁne the following operations on polynomials. Addition. Summing of polynomials consists of summing the coeﬃcients with equal powers of x, where the summing of the coeﬃcients occurs in the underlying ﬁeld F : c(x) = a(x) + b(x) ⇔ ci = ai + bi , 0 ≤ i < n. (2.23) The neutral element for the addition 0 is the polynomial with all coeﬃcients equal to 0. The inverse element of a polynomial can be found by replacing each coeﬃcient by its inverse element in F . The degree of c(x) is at most the maximum of the degrees of a(x) and b(x), hence the addition is closed. The structure (F [x] , +) is an Abelian group. Example 2.1.7. Let F be the ﬁeld GF(2). The sum of the polynomials denoted by 57 and 83 is the polynomial denoted by D4, since: (x6 + x4 + x2 + x + 1) + (x7 + x + 1) = x7 + x6 + x4 + x2 + (1 + 1)x + (1 + 1) = x7 + x6 + x4 + x2 . In binary notation we have: 01010111 + 10000011 = 11010100. Clearly, the addition can be implemented with the bitwise XOR instruction. Multiplication. Multiplication of polynomials is associative (2.3), commutative (2.4) and distributive (2.7) with respect to addition of polynomials. There is a neutral element: the polynomial of degree 0 and with coeﬃcient of x0 equal to 1. In order to make the multiplication closed (2.2) over F [x] , we select a polynomial m(x) of degree , called the reduction polynomial. The multiplication of two polynomials a(x) and b(x) is then deﬁned as the algebraic product of the polynomials modulo the polynomial m(x): c(x) = a(x) · b(x) ⇔ c(x) ≡ a(x) × b(x) (mod m(x)). (2.24) Hence, the structure (F [x] , +, ·) is a commutative ring. For special choices of the reduction polynomial m(x), the structure becomes a ﬁeld. Deﬁnition 2.1.5. A polynomial d(x) is irreducible over the ﬁeld GF(p) iﬀ there exist no two polynomials a(x) and b(x) with coeﬃcients in GF(p) such that d(x) = a(x) × b(x), where a(x) and b(x) are of degree > 0. 2.1 Finite Fields 15 The inverse element for the multiplication can be found by means of the extended Euclidean algorithm (see, e.g. [110, p. 81]). Let a(x) be the polynomial we want to ﬁnd the inverse for. The extended Euclidean algorithm can then be used to ﬁnd two polynomials b(x) and c(x) such that: a(x) × b(x) + m(x) × c(x) = gcd(a(x), m(x)). (2.25) Here gcd(a(x), m(x)) denotes the greatest common divisor of the polynomials a(x) and m(x), which is always equal to 1 iﬀ m(x) is irreducible. Applying modular reduction to (2.25), we get: a(x) × b(x) ≡ 1 (mod m(x)), (2.26) which means that b(x) is the inverse element of a(x) for the deﬁnition of the multiplication ‘·’ given in (2.24). A polynomial of degree n is primitive if its roots generate the multiplicative group of GF(pn ), or equivalently, the multiplicative polynomial x has order pn −1. It can be shown that a primitive polynomial is irreducible. Conclusion. Let F be the ﬁeld GF(p). With a suitable choice for the reduction polynomial, the structure (F [x]n , +, ·) is a ﬁeld with pn elements, usually denoted by GF(pn ). Example 2.1.8. Consider the ﬁeld GF(23 ). Let α be a root of x3 + x + 1 = 0. Then the elements of GF(23 ) can be denoted by 0, 1, α, α+1, α2 , α2 +1, α2 +α and α2 + α + 1. 2.1.6 Polynomials and Bytes According to (2.22) a byte can be considered as a polynomial with coeﬃcients in GF(2): b7 b6 b5 b4 b3 b2 b1 b0 → b(x) (2.27) b(x) = b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x + b0 . (2.28) The set of all possible byte values corresponds to the set of all polynomials with degree less than eight. Addition of bytes can be deﬁned as addition of the corresponding polynomials. In order to deﬁne the multiplication, we need to select a reduction polynomial m(x). 16 2. Preliminaries In the speciﬁcation of Rijndael, we consider the bytes as polynomials. Byte addition is deﬁned as addition of the corresponding polynomials. In order to deﬁne byte multiplication, we use the following irreducible polynomial as reduction polynomial: m(x) = x8 + x4 + x3 + x + 1. (2.29) Since this reduction polynomial is irreducible, we have constructed a representation for the ﬁeld GF(28 ). Hence we can state the following: In the Rijndael speciﬁcation, bytes are considered as elements of GF(28 ). Operations on bytes are deﬁned as operations in GF(28 ). Example 2.1.9. In our representation for GF(28 ), the product of the elements denoted by 57 and 83 is the element denoted by C1, since: (x6 + x4 + x2 + x + 1) × (x7 + x + 1) = (x13 + x11 + x9 + x8 + x7 ) + (x7 + x5 + x3 + x2 + x) + (x6 + x4 + x2 + x + 1) = x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1 and (x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1) ≡ x7 + x6 + 1 (mod x8 + x4 + x3 + x + 1). 2.1.7 Polynomials and Columns In the Rijndael speciﬁcation, 4byte columns are considered as polynomials over GF(28 ), having a degree smaller than four. In order to deﬁne the multiplication operation, the following reduction polynomial is used: l(x) = x4 + 1. (2.30) This polynomial is reducible, since in GF(28 ) x4 + 1 = (x + 1)4 . (2.31) In the deﬁnition of Rijndael, one of the inputs of the multiplication is a constant polynomial. Since l(x) is reducible over GF(28 ), not all polynomials have an inverse element for the multiplication modulo l(x). A polynomial b(x) has an inverse if the polynomial x + 1 does not divide it. 2.1 Finite Fields 17 Multiplication with a ﬁxed polynomial. We work out in more detail the multiplication with the ﬁxed polynomial used in Rijndael. Let b(x) be the ﬁxed polynomial with degree three: b(x) = b0 + b1 x + b2 x2 + b3 x3 (2.32) and let c(x) and d(x) be two variable polynomials with coeﬃcients ci and di , respectively (0 ≤ i < 4). We derive the matrix representation of the transformation that takes as input the coeﬃcients of polynomial c, and produces as output the coeﬃcients of the polynomial d = b × c. We have: d=b·c (2.33) (b0 + b1 x + b2 x2 + b3 x3 ) × (c0 + c1 x + c2 x2 + c3 x3 ) ≡ (d0 + d1 x + d2 x2 + d3 x3 ) (mod x4 + 1). (2.34) Working out the product and separating the conditions for diﬀerent powers of x, we get: ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ b0 b3 b 2 b 1 c0 d0 ⎢ d 1 ⎥ ⎢ b1 b0 b 3 b 2 ⎥ ⎢ c 1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ (2.35) ⎣ d 2 ⎦ = ⎣ b2 b1 b 0 b 3 ⎦ × ⎣ c 2 ⎦ . d3 b3 b2 b 1 b 0 c3 2.1.8 Functions over Fields All functions over GF(pn ) can be expressed as a polynomial over GF(pn ) of degree at most pn − 1: pn −1 ci ai , f (a) = (2.36) i=0 with ci ∈ GF(pn ). For simplicity of notation we follow the convention that 00 = 1. Given a table speciﬁcation where the output value f (a) is given for the pn diﬀerent input values a, the pn coeﬃcients of this polynomial can be found by applying Lagrange interpolation [95, p. 28]. On the other hand, given a polynomial expression, the table speciﬁcation can be found by evaluating the polynomial for all values of a. The trace function is a function from GF(pn ) to GF(p) that will turn out to be useful later. Deﬁnition 2.1.6. Let x be an element of GF(pn ). The trace of x over GF(p) is deﬁned by 2 3 Tr(x) = x + xp + xp + xp + · · · + xp n−1 . 18 2. Preliminaries The trace is linear over GF(p): ∀ x, y ∈ GF(pn ) : Tr(x + y) = Tr(x) + Tr(y) ∀ a ∈ GF(p), ∀ x ∈ GF(pn ) : Tr(ax) = aTr(x). and it can be shown that Tr(x) is an element of GF(p). 2.1.9 Representations of GF(pn ) Finite ﬁelds can be represented in diﬀerent ways. Cyclic representation of GF(pn ). It can be proven that the multiplicative group of GF(pn ) is cyclic. The elements of this group (diﬀerent from 0) can be represented as the pn − 1 powers of a generator α ∈ GF(pn ): ∀x ∈ GF(pn )\{0}, ∃ ax ∈ Zpn −1 : x = αax . (2.37) In this representation, multiplication of two nonzero elements corresponds to addition of their powers modulo pn − 1: x · y = αax · αay = αax +ay mod p n −1 . (2.38) Operations such as taking the multiplicative inverse and exponentiation are trivial in this representation. For addition, however, the vector representation (discussed next) is more appropriate. In computations involving both addition and multiplication, one may switch between the two diﬀerent representations by means of conversion tables. The table used for conversion from the vector representation to the cyclic representation is called a log table, and the table for the inverse conversion is called an alog table. We have used this principle in our reference implementation (see Appendix C). Vector space representation of GF(pn ). The additive group of the ﬁnite ﬁeld GF(pn ) and the ndimensional vector space over GF(p) are isomorphic. The addition of vectors in this vector space corresponds to the addition in GF(pn ). We can choose a basis e consisting of n elements e(i) ∈ GF(pn ). We depict the basis e by a column vector that has as elements the elements of the basis: T e = e(1) e(2) · · · e(n) The elements of GF(pn ) can be represented by their coordinates with respect to this basis. We have ai e(i) = aT e. a= (2.39) i where ai ∈ GF(2) are the coordinates of a with respect to the basis e and where a is the column vector consisting of coordinates ai . The map n φe : GF(pn ) → GF(p) : a → φe (a) = a forms an isomorphism. 2.1 Finite Fields 19 Dual bases. Coordinates of a ﬁeld element with respect to a basis can be expressed in terms of the dual basis and the trace map. Deﬁnition 2.1.7. Two bases e and d are called dual bases if for all i and j with 1 ≤ i, j ≤ n, it holds that Tr(d(i) e(j) ) = δ(i − j) (2.40) with δ(x) the Kronecker delta that is 1 if x = 0 and 0 otherwise. Every basis has exactly one dual basis. Let e and d be dual bases. Then we have n n ai e(i) Tr(d(j) a) = Tr d(j) ai Tr(d(j) e(i) ) = aj . = i=1 i=1 Hence the coordinates with respect to basis e can be expressed in an elegant way by means of the trace map and the dual basis d [95]: φe (a) = a = Tr(d(1) a) Tr(d(2) a) . . . Tr(d(n) a) . (2.41) Applying (2.39) gives: n n Tr(e(i) a)d(i) . Tr(d(i) a)e(i) = a= (2.42) i=1 i=1 Example 2.1.10. By choosing a basis, we can represent the elements of GF(23 ) as vectors. We choose the basis e as follows: e = [α2 + α + 1, α + 1, 1]T . The dual basis of e can be determined by solving (2.40). It is given by d = [α, α2 + α, α2 + 1]T . Table 2.1 shows the coordinates of the elements of GF(23 ), with respect to both bases. Boolean functions and functions in GF(pn ). Functions of GF(pn ) can n be mapped to functions of GF(p) by choosing a basis e in GF(pn ). Given f : GF(pn ) → GF(pn ) : a → b = f (a), we can deﬁne a Boolean function f : n n f : GF(p) → GF(p) : a → b = f (a) where 20 2. Preliminaries Table 2.1. Coordinates of the ﬁeld elements, with respect to the bases e and d a 0 1 α+1 α α2 + α + 1 α2 + α α2 2 α +1 a 000 001 010 011 100 101 110 111 ad 000 111 011 100 101 010 110 001 a = [a1 a2 . . . an ] b = [b1 b2 . . . bn ] , and ai = Tr(ad(i) ) bi = Tr(bd(i) ). On the other hand, given a Boolean function g, a function over GF(pn ) can be deﬁned as a = aT e b = bT e. and f = φ−1 So in short, f = φe ◦ f ◦ φ−1 e e ◦ f ◦ φe . This can be extended to functions operating on vectors of elements of GF(pn ). 2.2 Linear Codes In this section we give a short introduction to the theory of linear codes. For a more detailed treatment, we refer the interested reader to the work of MacWilliams and Sloane [100]. In a code, message words are represented by codewords that have some redundancy. In code theory textbooks, it is customary to write codewords as 1 × n matrices, or row vectors. We will follow that custom here. In subsequent chapters, onedimensional arrays will as often be denoted as n × 1 matrices, or column vectors. 2.2.1 Deﬁnitions The Hamming weight of a codeword is deﬁned as follows. 2.2 Linear Codes 21 Deﬁnition 2.2.1. The Hamming weight wh (x) of a vector x is the number of nonzero components of the vector x. Based on the deﬁnition of Hamming weight, we can deﬁne the Hamming distance between two vectors. Deﬁnition 2.2.2. The Hamming distance between two vectors x and y is wh (x − y), which is equal to the Hamming weight of the diﬀerence of the two vectors. Now we are ready to deﬁne linear codes. Deﬁnition 2.2.3. A linear [n, k, d] code over GF(2p ) is a kdimensional subn space of the vector space GF(2p ) , where any two diﬀerent vectors of the subspace have a Hamming distance of at least d (and d is the largest number with this property). The distance d of a linear code equals the minimum weight of a nonzero codeword in the code. A linear code can be described by each of the two following matrices: 1. A generator matrix G for an [n, k, d] code C is a k × n matrix whose rows form a vector space basis for C (only generator matrices of full rank are considered). Since the choice of a basis in a vector space is not unique, a code has many diﬀerent generator matrices, which can be reduced to one another by performing elementary row operations. The echelon form of the generator matrix is the following: (2.43) Ge = Ik×k Ak×(n−k) , where Ik×k is the k × k identity matrix. 2. A paritycheck matrix H for an [n, k, d] code C is an (n − k) × n matrix with the property that a vector x is a codeword of C iﬀ HxT = 0. (2.44) If G is a generator matrix and H a paritycheck matrix of the same code, then GHT = 0. (2.45) Moreover, if G = [I C] is a generator matrix of a code, then H = −CT I is a paritycheck matrix of the same code. The dual code C ⊥ of a code C is deﬁned as the set of vectors that are orthogonal to all the vectors of C: C ⊥ = {x  xyT = 0, ∀ y ∈ C}. (2.46) It follows that a paritycheck matrix of C is a generator matrix of C ⊥ and vice versa. 22 2. Preliminaries 2.2.2 MDS Codes The theory of linear codes addresses the problems of determining the distance of a linear code and the construction of linear codes with a given distance. We review a few wellknown results. The Singleton bound gives an upper bound for the distance of a code with given dimensions. Theorem 2.2.1 (The Singleton bound). If C is an [n, k, d] code, then d ≤ n − k + 1. A code that meets the Singleton bound is called a maximal distance separable (MDS) code. The following theorems relate the distance of a code to properties of the generator matrix G. Theorem 2.2.2. A linear code C has distance d iﬀ every d − 1 columns of the paritycheck matrix H are linearly independent and there exists some set of d columns that are linearly dependent. By deﬁnition, an MDS code has distance n − k + 1. Hence, every set of n − k columns of the paritycheck matrix are linearly independent. This property can be translated into a requirement for the matrix A: Theorem 2.2.3 ([100]). An [n, k, d] code with generator matrix G = Ik×k Ak×(n−k) , is an MDS code iﬀ every square submatrix of A is nonsingular. A wellknown class of MDS codes is formed by the ReedSolomon codes, for which eﬃcient construction algorithms are known. 2.3 Boolean Functions The smallest ﬁnite ﬁeld has an order of 2: GF(2). Its two elements are denoted by 0 and 1. Its addition is the integer addition modulo 2 and its multiplication is the integer multiplication modulo 2. Variables that range over GF(2) are called Boolean variables, or bits for short. The addition of 2 bits corresponds to the Boolean operation exclusive or, denoted by XOR. The multiplication of 2 bits corresponds to the Boolean operation AND. The operation of changing the value of a bit is called complementation. A vector whose coordinates are bits is called a Boolean vector. The operation of changing the value of all bits of a Boolean vector is called complementation. If we have two Boolean vectors a and b of the same dimension, we can apply the following operations: 2.3 Boolean Functions 1. Bitwise XOR: corresponding 2. Bitwise AND: corresponding 23 results in a vector whose bits consist of the XOR of the bits of a and b. results in a vector whose bits consist of the AND of the bits of a and b. A function b = φ(a) that maps a Boolean vector to another Boolean vector is called a Boolean function: φ : GF(2)n → GF(2)m : a → b = φ(a), (2.47) where b is called the output Boolean vector and a the input Boolean vector. This Boolean function has n input bits and m output bits. A binary Boolean function b = f (a) is a Boolean function with a single output bit, in other words m = 1: f : GF(2)n → GF(2) : a → b = f (a), (2.48) where b is called the output bit. Each bit of the output of a Boolean function is itself a binary Boolean function of the input vector. These functions are called the component binary Boolean functions of the Boolean function. A Boolean function can be speciﬁed by providing the output value for the 2n possible values of the input Boolean vector. A Boolean function with the same number of input bits as output bits can be considered as operating on an nbit state. We call such a function a Boolean transformation. A Boolean transformation is called invertible if it maps all input states to diﬀerent output states. An invertible Boolean transformation is called a Boolean permutation. 2.3.1 Tuple Partitions In several instances it is useful to see the bits of a state as being partitioned into a number of subsets. Boolean transformations operating on a state can be expressed in terms of these subsets rather than in terms of the individual bits of the state. In the context of this book we restrict ourselves to partitions that divide the state bits into a number of equally sized subsets. We will use the term tuples to describe these subsets.1 Because in the case of Rijndael, tuples contain eight bits, we will often write bytes instead. However, the reasoning applies as well to tuples of other sizes (larger than two). Consider an nb bit state a consisting of bits ai where i ∈ I. I is called the index space. In its simplest form, the index space is just equal to {1, . . . , nb }. However, for clarity the bits may be indexed in another way to ease speciﬁcations. A partitioning of the state bits may be reﬂected by having an index with two components: one component indicating the byte position within 1 In the ﬁrst edition we used the term bundles, but this term now gets another meaning in Chap. 14. 24 2. Preliminaries the state, and one component indicating the bit position within the byte. In this representation, a(i,j) would mean the state bit in byte i at bit position j within that byte. The value of the byte itself can be indicated by ai . On some occasions, even the byte index can be decomposed. For example, in Rijndael the bytes are arranged in a twodimensional array with the byte index composed of a column index and a row index. Next to the obvious 8bit bytes also the 32bit columns in Rijndael deﬁne a partitioning. The nonlinear steps in the round transformations of the AES ﬁnalist Serpent [4] operate on 4bit bytes. The nonlinear step in the round transformation of 3Way [43] and BaseKing [45] operate on 3bit tuples. The tuples can be considered as representations of elements in some group, ring or ﬁeld. Examples are the integers modulo 2m or elements of GF(2m ). In this way, steps of the round transformation, or even the full round transformation can be expressed in terms of operations in these mathematical structures. 2.3.2 Transpositions A transposition is a Boolean permutation that only moves the positions of bits of the state without aﬀecting their value. For a transposition b = π(a) we have: (2.49) bi = ap(i) , where p(i) is a permutation over the index space. A byte transposition is a transposition that changes the positions of the bytes but leaves the positions of the bits within the bytes intact. This can be expressed as: (2.50) b(i,j) = a(p(i),j) . An example is shown in Fig. 2.1. Figure 2.2 shows the pictogram that we will use to represent a byte transposition in this book. ? U +R U s Fig. 2.1. Example of a byte transposition 2.3 Boolean Functions 25 Fig. 2.2. Pictogram for a byte transposition 2.3.3 Bricklayer Functions A bricklayer function is a function that can be decomposed into a number of Boolean functions operating independently on subsets of bits of the input vector. These subsets form a partition of the bits of the input vector. A bricklayer function can be considered as the parallel application of a number of Boolean functions operating on smaller inputs. If nonlinear, these Boolean functions are called Sboxes. If linear, we use the term Dbox, where D stands for diﬀusion. A bricklayer function operating on a state is called a bricklayer transformation. As a bricklayer transformation operates on a number of subsets of the state independently, it deﬁnes a byte partition. The component transformations of the bricklayer transformation operate independently on a number of bytes. A graphical illustration is given in Fig. 2.3. An invertible bricklayer transformation is called a bricklayer permutation. For a bricklayer transformation to be invertible, all of its Sboxes (or Dboxes) must be permutations. The pictogram that we will use is shown in Fig. 2.4. For a bricklayer transformation b = φ(a) we have: (b(i,1) , b(i,2) , . . . , b(i,m) ) = φi (a(i,1) , a(i,2) , . . . , a(i,m) ), (2.51) for all values of i. If the bytes within a and b are represented by ai and bi , respectively, this becomes: bi = φi (ai ). φ (2.52) ? ? ? ? ? ? ? ? φ0 φ1 φ2 φ3 ? ? ? ? ? ? ? ? Fig. 2.3. Example of a bricklayer transformation Fig. 2.4. Pictogram for a bricklayer transformation 26 2. Preliminaries 2.3.4 Iterative Boolean Transformations A Boolean vector can be transformed iteratively by applying a sequence of Boolean transformations, one after the other. Such a sequence is referred to as an iterative Boolean transformation. If the individual Boolean transformations are denoted by ρ(i) , an iterative Boolean transformation is of the form β = ρ(r) ◦ . . . ◦ ρ(2) ◦ ρ(1) . (2.53) A schematic illustration is given in Fig. 2.5. We have b = β(d), where d = a(0) , b = a(m) and a(i) = ρ(i) (a(i−1) ). The value of a(i) is called an intermediate state. An iterative Boolean transformation that is a sequence of Boolean permutations is an iterative Boolean permutation. ?? ?? ρ ?? ?? ρ ?? ?? ?? ?? ?? ?? ?? ?? ?? (1) (2) ?? ρ(3) ?? ?? Fig. 2.5. Iterative Boolean transformation 2.4 Block Ciphers A block cipher transforms plaintext blocks of a ﬁxed length nb into ciphertext blocks of the same length under the inﬂuence of a cipher key k. More precisely, a block cipher is a set of Boolean permutations operating on nb bit vectors. This set contains a Boolean permutation for each value of the cipher key k. In this book we only consider block ciphers in which the cipher key is a Boolean vector. If the number of bits in the cipher key is denoted by nk , a block cipher consists of 2nk Boolean permutations. The operation of transforming a plaintext block into a ciphertext block is called encryption, and the operation of transforming a ciphertext block into a plaintext block is called decryption. 2.4 Block Ciphers 27 Usually, block ciphers are speciﬁed by an encryption algorithm, being the sequence of transformations to be applied to the plaintext to obtain the ciphertext. These transformations are operations with a relatively simple description. The resulting Boolean permutation depends on the cipher key due to the fact that key material, computed from the cipher key, is used in the transformations. For a block cipher to be up to its task, it has to fulﬁll two requirements: 1. Eﬃciency. Given the value of the cipher key, applying the corresponding Boolean permutation, or its inverse, is eﬃcient, preferably on a wide range of platforms. 2. Security. It must be impossible to exploit knowledge of the internal structure of the cipher in cryptographic attacks. All block ciphers of any signiﬁcance satisfy these requirements by iteratively applying Boolean permutations that are relatively simple to describe. 2.4.1 Iterative Block Ciphers In an iterative block cipher, the Boolean permutations are iterative. The block cipher is deﬁned as the application of a number of keydependent Boolean permutations. The Boolean permutations are called the round transformations of the block cipher. Every application of a round transformation is called a round. Example 2.4.1. The DES has 16 rounds. Since every round uses the same round transformation, we say the DES has only one round transformation. We denote the number of rounds by r. We have: B[k] = ρ(r) [k(r) ] ◦ · · · ◦ ρ(2) [k(2) ] ◦ ρ(1) [k(1) ]. (2.54) In this expression, ρ(i) is called the ith round of the block cipher and k(i) is called the ith round key. The round keys are computed from the cipher key. Usually, this is speciﬁed with an algorithm. The algorithm that describes how to derive the round keys from the cipher key is called the key schedule. The concatenation of all round keys is called the expanded key, denoted by K: K = k(0) k(1) k(2)  . . . k(r) (2.55) The length of the expanded key is denoted by nK . The iterative block cipher model is illustrated in Fig. 2.6. Almost all block ciphers known can be modeled this way. There is however a large variety in round transformations and key schedules. An iterative block cipher in which all rounds (with the exception of the initial or ﬁnal round) use the same round transformation is called an iterated block cipher. 28 2. Preliminaries k(1)  k  k(2)  k(3)  ?? ?? ρ ?? ?? ρ ?? ?? ?? ?? ?? ?? ?? ?? ?? (1) (2) ?? ρ(3) ?? ?? Fig. 2.6. Iterative block cipher with three rounds 2.4.2 KeyAlternating Block Ciphers Rijndael belongs to a class of block ciphers in which the round key is applied in a particularly simple way: the keyalternating block ciphers. A keyalternating block cipher is an iterative block cipher with the following properties: 1. Alternation. The cipher is deﬁned as the alternated application of keyindependent round transformations and key additions. The ﬁrst round key is added before the ﬁrst round and the last round key is added after the last round. 2. Simple key addition. The round keys are added to the state by means of a simple XOR. A key addition is denoted by σ[k]. We have: B[k] = σ[k(r) ] ◦ ρ(r) ◦ σ[k(r−1) ] ◦ · · · ◦ σ[k(1) ] ◦ ρ(1) ◦ σ[k(0) ]. (2.56) A graphical illustration is given in Fig. 2.7. Keyalternating block ciphers are a class of block ciphers that lend themselves to analysis with respect to their resistance against cryptanalysis. This will become clear in Chaps. 7–9 and in Chaps. 13–15. A special class of keyalternating block ciphers are the keyiterated block ciphers. In this class, all rounds (except maybe the ﬁrst or the last) of the cipher use the same round transformation. We have: B[k] = σ[k(r) ] ◦ ρ ◦ σ[k(r−1) ] ◦ · · · ◦ σ[k(1) ] ◦ ρ ◦ σ[k(0) ]. (2.57) In this case, ρ is called the round transformation of the block cipher. The relations between the diﬀerent classes of block ciphers that we deﬁne here are shown in Fig. 2.8. 2.4 Block Ciphers k(0) ? ? ?? ?? ?? ?? ?? ?? ??  29 ρ(1) k  k(1) ? ? ?? ?? ?? ?? ?? ?? ??  ρ(2) k(2) ? ? ?? ?? ?? ?? ?? ?? ??  Fig. 2.7. Keyalternating block cipher with two rounds Keyiterated block ciphers lend themselves to eﬃcient implementations. In dedicated hardware implementations, one can hardwire the round transformation and the key addition. The block cipher can be executed by simply iterating the round transformation alternated with the right round keys. In software implementations, the program needs to code only the one round transformation in a loop and the cipher can be executed by executing this loop the required number of times. In practice, for performance reasons, block ciphers in software will often have code for all rounds: socalled loop unrolling. In these implementations, it is less important to have identical rounds. Nevertheless, the mostused block ciphers all consist of a number of identical rounds. Some other advantages of the keyiterated structure are discussed in Chap. 5. iterated block ciphers keyiterated block ciphers keyalternating block ciphers iterative block ciphers Fig. 2.8. Block cipher taxonomy A block cipher is a cryptographic primitive that can convert a ﬁxedlength plaintext block to a ﬁxedlength ciphertext block and vice versa under a given 30 2. Preliminaries cipher key. In order to use a cipher to protect the conﬁdentiality or integrity of messages of arbitrary length, it must be speciﬁed how the cipher is used. These speciﬁcations are the socalled modes of operation of a block cipher. Modes of operation are out of scope of this book. We refer the reader to [102]. 3. Speciﬁcation of Rijndael In this chapter we specify the cipher structure and the building blocks of Rijndael. After explaining the diﬀerence between the Rijndael speciﬁcations and the AES standard, we specify the external interface to the ciphers. This is followed by the description of the Rijndael structure and the steps of its round transformation. Subsequently, we specify the number of rounds as a function of the block and key length, and describe the key schedule. We conclude this chapter with a treatment of algorithms for implementing decryption with Rijndael. This chapter is not intended as an implementation guideline. For implementation aspects, we refer to Chap. 4. 3.1 Diﬀerences Between Rijndael and the AES The only diﬀerence between Rijndael and the AES is the range of supported values for the block length and cipher key length. Rijndael is a block cipher with both a variable block length and a variable key length. The block length and the key length can be independently speciﬁed to any multiple of 32 bits, with a minimum of 128 bits and a maximum of 256 bits. It would be possible to deﬁne versions of Rijndael with a higher block length or key length, but currently there seems no need for it. The AES ﬁxes the block length to 128 bits, and supports key lengths of 128, 192 or 256 bits only. The extra block and key lengths in Rijndael were not evaluated in the AES selection process, and consequently they are not adopted in the current FIPS standard. 3.2 Input and Output for Encryption and Decryption The input and output of Rijndael are considered to be onedimensional arrays of 8bit bytes. For encryption the input is a plaintext block and a key, and the output is a ciphertext block. For decryption, the input is a ciphertext block and a key, and the output is a plaintext block. The round transformation of Rijndael, and its steps, operate on an intermediate result, called the state. © SpringerVerlag GmbH Germany, part of Springer Nature 2020 J. Daemen, V. Rijmen, The Design of Rijndael, Information Security and Cryptography, https://doi.org/10.1007/9783662607695_3 31 32 3. Speciﬁcation of Rijndael The state can be pictured as a rectangular array of bytes, with four rows. The number of columns in the state is denoted by Nb and is equal to the block length divided by 32. Let the plaintext block be denoted by p0 p1 p2 p3 . . . p4·Nb −1 , where p0 denotes the ﬁrst byte,and p4·Nb −1 denotes the last byte of the plaintext block. Similarly, a ciphertext block can be denoted by c0 c1 c2 c3 . . . c4·Nb −1 . Let the state be denoted by ai,j , 0 ≤ i < 4, 0 ≤ j < Nb , where ai,j denotes the byte in row i and column j. The input bytes are mapped onto the state bytes in the order a0,0 , a1,0 , a2,0 , a3,0 , a0,1 , a1,1 , a2,1 , a3,1 , . . . . For encryption, the input is a plaintext block and the mapping is ai,j = pi+4j , 0 ≤ i < 4, 0 ≤ j < Nb . (3.1) For decryption, the input is a ciphertext block and the mapping is ai,j = ci+4j , 0 ≤ i < 4, 0 ≤ j < Nb . (3.2) At the end of the encryption, the ciphertext is extracted from the state by taking the state bytes in the same order: ci = ai mod 4,i/4 , 0 ≤ i < 4Nb . (3.3) At the end of decryption, the plaintext block is extracted from the state according to pi = ai mod 4,i/4 , 0 ≤ i < 4Nb . (3.4) Similarly, the key is mapped onto a twodimensional cipher key. The cipher key is pictured as a rectangular array with four rows similar to the state. The number of columns of the cipher key is denoted by Nk and is equal to the key length divided by 32. The bytes of the key are mapped onto the bytes of the cipher key in the order: k0,0 , k1,0 , k2,0 , k3,0 , k0,1 , k1,1 , k2,1 , k3,1 , k0,2 . . . . If we denote the key by z0 z1 z2 z3 . . . z4·Nk −1 , then ki,j = zi+4j , 0 ≤ i < 4, 0 ≤ j < Nk . (3.5) The representation of the state and cipher key and the mappings plaintext– state and key–cipher key are illustrated in Fig. 3.1. 3.4 The Round Transformation p0 p4 p8 p12 k0 k4 k8 k12 k16 k20 p1 p5 p9 p13 k1 k5 k9 k13 k17 k21 p2 p6 p10 p14 k2 k6 k10 k14 k18 k22 p3 p7 p11 p15 k3 k7 k11 k15 k19 k23 33 Fig. 3.1. State and cipher key layout for the case Nb = 4 and Nk = 6 3.3 Structure of Rijndael Rijndael is a keyiterated block cipher: it consists of the repeated application of a round transformation on the state. The number of rounds is denoted by Nr and depends on the block length and the key length. Note that in this chapter, contrary to the deﬁnitions (2.54)–(2.57), the key addition is included in the round transformation. This is done in order to make the description in this chapter consistent with the description in the FIPS standard. Following a suggestion of B. Gladman, we changed the names of some steps with respect to the description given in our original AES submission. The new names are more consistent, and are also adopted in the FIPS standard. We made some further changes, all in order to make the description more clear and complete. No changes have been made to the block cipher itself. An encryption with Rijndael consists of an initial key addition, denoted by AddRoundKey, followed by Nr −1 applications of the transformation Round, and ﬁnally one application of FinalRound. The initial key addition and every round take as input the State and a round key. The round key for round i is denoted by ExpandedKey[i], and ExpandedKey[0] denotes the input of the initial key addition. The derivation of ExpandedKey from the CipherKey is denoted by KeyExpansion. A highlevel description of Rijndael in pseudocode notation is shown in List. 3.1. 3.4 The Round Transformation The round transformation is denoted Round, and is a sequence of four transformations, called steps. This is shown in List. 3.2. The ﬁnal round of the cipher is slightly diﬀerent. It is denoted FinalRound and is also shown in List. 3.2. In the listings, the transformations (Round, SubBytes, ShiftRows, 34 3. Speciﬁcation of Rijndael procedure Rijndael(State,Cipherkey) KeyExpansion(CipherKey,ExpandedKey) AddRoundKey(State,ExpandedKey[0]) for i = 1 to Nr − 1 do Round(State,ExpandedKey[i]) end for FinalRound(State,ExpandedKey[Nr ]) end procedure List. 3.1. Highlevel algorithm for encryption with Rijndael . . . ) operate on arrays to which pointers (State, ExpandedKey[i]) are provided. It is easy to verify that the transformation FinalRound is equal to the transformation Round, but with the MixColumns step removed. The steps are speciﬁed in the following subsections, together with the design criteria we used for each step. Besides the stepspeciﬁc criteria, we also applied the following two general design criteria: 1. Invertibility. The structure of the Rijndael round transformation requires that all steps be invertible. 2. Simplicity. As explained in Chap. 5, we prefer simple components over complex ones. procedure Round(State,ExpandedKey[i]) SubBytes(State); ShiftRows(State); MixColumns(State); AddRoundKey(State,ExpandedKey[i]); end procedure procedure FinalRound(State,ExpandedKey[Nr ]) SubBytes(State); ShiftRows(State); AddRoundKey(State,ExpandedKey[Nr ]); end procedure List. 3.2. The Rijndael round transformation 3.4.1 The SubBytes Step The SubBytes step is the only nonlinear transformation of the cipher. SubBytes is a bricklayer permutation consisting of an Sbox applied to the bytes of the state. We denote the particular Sbox being used in Rijndael by SRD . Figure 3.2 illustrates the eﬀect of the SubBytes step on the state. Figure 3.3 shows the pictograms that we will use to represent SubBytes and its inverse. 3.4 The Round Transformation 35  SRD a0,0 a0,1 a0,2 a0,3 b0,0 b0,1 b0,2 b0,3 a1,0 a1,1 a1,2 a1,3 b1,0 b1,1 b1,2 b1,3 a2,0 a2,1 a2,2 a2,3 b2,0 b2,1 b2,2 b2,3 a3,0 a3,1 a3,2 a3,3 b3,0 b3,1 b3,2 b3,3 R Fig. 3.2. SubBytes acts on the individual bytes of the state Fig. 3.3. The pictograms for SubBytes (left) and InvSubBytes (right) Design criteria for SRD . We have applied the following design criteria for SRD , appearing in order of i