Symmetric Cryptography, Volume 1

Christina Boura is an associate professor at the University of Versailles, France, who works on symmetric cryptography. She is a well-recognized member of the cryptographic community, having served on many program committees and as editor-in-chief of the ToSC IACR journal.María Naya-Plasencia is a research director at Inria, France, who also works on symmetric cryptography. She obtained an ERC grant in 2016 and the Young Researcher Prize from Inria-Académie des Sciences in 2019, and has given several invited keynote talks.

• Preface xiChristina BOURA and María NAYA-PLASENCIAPart 1 Design of Symmetric-key Algorithms 1Chapter 1 Introduction to Design in Symmetric Cryptography 3Joan DAEMEN1.1 Introduction 31.2 Cryptographic building blocks 31.2.1 The block cipher and its variants 41.3 Differentially uniform functions 51.4 Arbitrary-length schemes 51.4.1 Modes and constructions 61.4.2 Dedicated schemes 71.4.3 Modes and constructions versus primitives 71.5 Iterated (tweakable) block ciphers and permutations 81.5.1 Cryptanalysis and safety margin 81.5.2 Designing the round function of primitives 91.6 A short history 101.6.1 The data encryption standard 101.6.2 The block cipher FEAL 111.6.3 Differential and linear cryptanalysis 111.6.4 The block cipher IDEA 121.6.5 The advanced encryption standard 121.6.6 Cache attacks 131.6.7 KECCAK 141.6.8 Lightweight cryptography 151.7 Acknowledgments 151.8 References 15Chapter 2 The Design of Stream Ciphers 21Chaoyun LI and Bart PRENEEL2.1 Introduction 212.1.1 What is a synchronous additive stream cipher? 212.1.2 Generic construction 232.1.3 Generic attacks 242.1.4 Open competitions 252.1.5 Standards 262.2 Constructions based on FSRs 272.2.1 LFSR-based constructions 272.2.2 NFSR-based constructions 282.3 Table-based constructions 292.4 Block ciphers and permutations in stream cipher mode 292.4.1 Block cipher modes OFB and CTR 302.4.2 Permutations in stream cipher mode 302.5 Authenticated encryption (AE) 312.5.1 Block ciphers and permutations in stream cipher modes 322.6 Emerging low-complexity stream ciphers 332.7 References 34Chapter 3 Block Ciphers 39Orr DUNKELMAN3.1 General purpose block ciphers 413.1.1 Feistel block ciphers 423.1.2 Substitution permutation networks 433.2 Key schedule algorithms 443.3 Generic attacks 463.4 Tweakable block ciphers 483.5 Some positive results concerning security 493.6 The case of algebraic ciphers 513.7 References 53Chapter 4 Hash Functions 55Gilles VAN ASSCHE4.1 Definitions and requirements 554.1.1 An ideal model: the random oracle 574.1.2 Expressing security claims 584.2 Design of hash functions 604.2.1 The Merkle-Damgård construction 604.2.2 Fixing the Merkle-Damgård construction 614.2.3 Building a compression function 624.2.4 Indifferentiability 644.2.5 The sponge construction 654.2.6 KECCAK, SHA-3 and beyond 674.3 Tree hashing 684.4 References 69Chapter 5 Modes of Operation 73Gaëtan LEURENT5.1 Encryption schemes 735.1.1 Cipher block chaining 745.1.2 Counter mode 755.2 Message authentication codes 755.2.1 CBC-MAC 765.2.2 PMAC 775.2.3 Hash-based MACs 775.2.4 Wegman-Carter MACs and GMAC 785.3 Security of modes: generic attacks 785.3.1 The birthday bound 795.3.2 Generic attack against iterated MACs 795.3.3 Generic attack against Wegman-Carter MACs 805.3.4 Generic attack against CBC 805.3.5 Generic attack against CTR 805.3.6 Small block sizes 815.3.7 Misuse 815.3.8 Limitations of encryption 825.4 References 83Chapter 6 Authenticated Encryption Schemes 87Maria EICHLSEDER6.1 Introduction 876.2 Security notions 886.3 Design strategies for authenticated encryption 896.3.1 Generic composition 916.3.2 Dedicated primitive-based designs 926.3.3 Fully dedicated designs 946.3.4 Standards and competitions 956.4 References 96Chapter 7 MDS Matrices 99Gaëtan LEURENT7.1 Definition 997.1.1 Differential and linear properties 1007.1.2 Near-MDS matrices 1017.2 Constructions 1017.3 Implementation cost 1027.3.1 Optimizing the implementation of a matrix 1037.3.2 Implementation of the inverse matrix 1047.4 Construction of lightweight MDS matrices 1047.4.1 Choice of the field or ring 1057.4.2 MDS matrices with the lowest XOR count 1057.4.3 Iterative MDS matrices 1067.4.4 Involutory MDS matrices 1077.5 References 108Chapter 8 S-boxes 111Christina BOURA8.1 Important design criteria 1138.1.1 Differential properties 1138.1.2 Linear properties 1158.1.3 Algebraic properties 1168.1.4 Other properties 1178.2 Popular S-boxes for different dimensions 1178.2.1 S-boxes with an odd number of variables 1188.2.2 4-bit S-boxes 1188.2.3 8-bit S-boxes 1198.3 Further reading 1198.4 References 119Chapter 9 Rationale, Backdoors and Trust 123Léo PERRIN9.1 Lifecycle of a cryptographic primitive 1249.1.1 Design phase 1249.1.2 Public cryptanalysis 1259.1.3 Deployment? 1259.1.4 The limits of this process 1269.2 When a selection process fails 1269.2.1 Under-engineered algorithms 1279.2.2 Primitives with hidden properties 1289.3 Can we trust modern algorithms? 1319.3.1 Standardization and normalization 1319.3.2 Some rules of thumb 1329.4 References 133Part 2 Security Proofs for Symmetric-key Algorithms 135Chapter 10 Modeling Security 137Bart MENNINK10.1 Different types of adversary models 13710.2 When is an attack considered successful? 13810.3 Random oracle 13810.4 Distinguishing advantage 13910.5 Understanding the distinguishing advantage 14110.5.1 Adversarial complexity 14110.5.2 Claiming security 14210.5.3 Breaking claims 14310.6 Adaptation to block ciphers 14310.6.1 Distinguishing advantage 14410.6.2 Security of AES 14510.7 Acknowledgments 14610.8 References 146Chapter 11 Encryption and Security of Counter Mode 147Bart MENNINK11.1 Block encryption 14711.1.1 Padding 14811.1.2 Cipher block chaining 14911.2 Stream encryption 15011.2.1 Output feedback mode 15111.2.2 Counter mode 15211.3 Provable security of modes: the case of counter mode 15311.4 Acknowledgments 15611.5 References 156Chapter 12 Message Authentication and Authenticated Encryption 159Tetsu IWATA12.1 Message authentication 15912.1.1 WCS construction 16012.1.2 Provable security 16112.2 Authenticated encryption 16412.2.1 GCM, Galois/counter mode 16412.2.2 Provable security 16612.3 References 169Chapter 13 H-coefficients Technique 171Yannick SEURIN13.1 The H-Coefficients technique 17113.2 A worked out example: the three-round Feistel construction 17613.3 The Even-Mansour construction 17813.3.1 H-coefficients security proof 17913.3.2 Extension to multiple rounds 18113.4 References 182Chapter 14 Chi-square Method 183Mridul NANDI14.1 Introduction 18314.2 Preliminaries 18514.2.1 PRF-security definition 18514.2.2 Hypergeometric distribution 18614.3 Truncation of random permutation 18714.3.1 PRF-security of truncation 18814.4 XOR of random permutations 19014.5 Other applications of the chi-squared method 19214.6 Acknowledgments 19314.7 References 193Part 3 Appendices 195Appendix 1 Data Encryption Standard (DES) 197Christina BOURAAppendix 2 Advanced Encryption Standard (AES) 205Christina BOURA and Orr DUNKELMANAppendix 3 PRESENT 217Christina BOURAAppendix 4 KECCAK 223Christina BOURAList of Authors 231Index 233Summary of Volume 2 239