Symmetric Cryptography, Volume 2

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 xiiiChristina Boura and María Naya-PlasenciaPart 1 Cryptanalysis of Symmetric-key Algorithms 1Chapter 1 Differential Cryptanalysis 3Henri Gilbert and Jérémy Jean1.1. Statistical attacks on block ciphers: preliminaries 41.2. Principle of differential cryptanalysis and application to DES 71.2.1. Differential transitions and differential characteristics 71.2.2. Derivation of non-trivial differential characteristics 101.2.3. Leveraging characteristics to mount a key-recovery attack 141.3. Some refinements and generalizations 181.3.1. Differential effect 181.3.2. Truncated differentials 191.4. Design strategies and evaluation 201.4.1 Case of the AES 211.4.2. Automated analysis 231.5. Further notes and references 231.6. References 26Chapter 2 Linear Cryptanalysis 29Kaisa Nyberg and Antonio Flórez-Gutiérrez2.1. History 292.2. Correlation and linear hull 302.3. Multidimensional linear approximation 312.4. Walsh-Hadamard transform 322.5. Linear approximation of an iterative block cipher 322.6. Matsui’s Algorithm 1 type of key recovery 332.7. Matsui’s Algorithm 2 type of key recovery 342.8. Searching for linear approximations and estimating correlations 352.9. Speeding up key recovery 362.10. Key-recovery distinguisher 382.11. Classical model of Algorithm 2 392.12. Algorithm 2 with distinct known plaintext and randomized key 402.13. Multiple linear approximations 402.14. Multidimensional linear cryptanalysis 422.15. References 43Chapter 3 Impossible Differential Cryptanalysis 47Christina Boura and María Naya-Plasencia3.1. Finding impossible differentials 483.2. Key recovery 493.2.1. Data, time and memory complexities 503.3. Some improvements 523.3.1. Early abort technique 523.3.2. Multiple impossible differentials or multiple extension paths 533.4. Applications 543.5. References 54Chapter 4 Zero-Correlation Cryptanalysis 57Vincent Rijmen4.1. Correlation and linear cryptanalysis 574.1.1. Correlation matrix 574.1.2. Linear trails and linear hulls 584.1.3. Approximations of linear functions 594.1.4. Computing the correlations over a permutation 604.2. Attacks using a linear hull with correlation zero 604.2.1. Correlation zero in random permutations 614.2.2. Distinguisher 614.2.3. Reducing the data complexity 624.3. Linear hulls with correlation zero 624.3.1. Feistel ciphers 634.3.2. AES 644.3.3 Extended result on AES 644.4. References 64Chapter 5 Differential-Linear Cryptanalysis 67Yosuke Todo5.1. Brief introduction of differential-linear attacks 675.2. How to estimate correlations of a differential-linear distinguisher 695.3. On the key recovery 715.4. State of the art for differential-linear attacks 725.4.1. Differential-linear connecting table 725.4.2. Three techniques to improve differential-linear attacks 735.5. References 76Chapter 6 Boomerang Cryptanalysis 77Ling Song6.1. Basic boomerang attack 776.2. Variants and refinements 796.3. Tricks and failures 806.4. Formalize the dependency 836.5. References 86Chapter 7 Meet-in-the-Middle Cryptanalysis 89Brice Minaud7.1. Introduction 897.2. Basic meet-in-the-middle framework 907.2.1. The 2DES attack 907.2.2. Algorithmic framework 917.2.3. Complexity analysis and memory usage 927.3. Meet-in-the-middle techniques 947.3.1. Filtering 947.3.2. Splice-and-cut 967.3.3. Bicliques 977.4. Automatic tools 987.5. References 98Chapter 8 Meet-in-the-Middle Demirci-Selçuk Cryptanalysis 101Patrick Derbez8.1. Original Demirci-Selçuk attack 1018.2. Improvements 1038.2.1. Data/time/memory trade-off 1048.2.2. Difference instead of value 1048.2.3. Multiset 1058.2.4. Linear combinations 1058.2.5. Differential enumeration technique 1068.3. Finding the best attacks 1088.3.1. Tools 1088.3.2. Results 1098.4. References 109Chapter 9 Invariant Cryptanalysis 111Christof Beierle9.1. Introduction 1119.2. Invariants for permutations and block ciphers 1129.2.1. Invariant subspaces 1139.2.2. Quadratic invariants 1179.3. On design criteria to prevent attacks based on invariants 1179.4. A link to linear approximations 1199.5. References 121Chapter 10 Higher Order Differentials, Integral Attacks and Variants 123Anne Canteaut10.1. Integrals and higher order derivatives 12310.2. Algebraic degree of an iterated function 12610.3. Division property 12810.4. Attacks based on integrals 13010.4.1. Distinguishers 13010.4.2. Attacks 13010.5. References 131Chapter 11 Cube Attacks and Distinguishers 133Itai Dinur11.1. Cube attacks and cube testers 13311.1.1. Terminology 13411.1.2. Main observation 13511.1.3. The basic cube attack 13611.1.4. The preprocessing phase on cube attacks 13711.1.5. Cube testers 13811.1.6. Applications 13911.2. Conditional differential attacks and dynamic cube attacks 14011.2.1. Conditional differential attacks 14011.2.2. Dynamic cube attacks 14011.2.3. A toy example 14011.3. References 141Chapter 12 Correlation Attacks on Stream Ciphers 143Thomas Johansson12.1. Correlation attacks on the nonlinear combination generator 14412.2. Correlation attacks and decoding linear codes 14512.3. Fast correlation attacks 14612.3.1. Fast correlation attacks and low weight feedback polynomials 14712.3.2. Finding low weight multiples of the feedback polynomial 14812.3.3. Fast correlation attacks by reducing the code dimension 15012.4. Generalizing fast correlation attacks 15112.4.1. The E0 stream cipher 15112.4.2. The A5/1 stream cipher 15212.5. References 153Chapter 13 Addition, Rotation, XOR 155Léo Perrin13.1. What is ARX? 15513.1.1. Structure of an ARX-based primitive 15613.1.2. Development of ARX 15613.2. Understanding modular addition 15713.2.1. Expressing modular addition in Fn2 15813.2.2. Cryptographic properties of modular addition 15813.3. Analyzing ARX-based primitives 16013.3.1. Searching for differential and linear trails 16013.3.2. Proving security against differential and linear attacks 16113.3.3. Other cryptanalysis techniques 16213.4. References 163Chapter 14 SHA-3 Contest Related Cryptanalysis 167Yu S Asaki14.1. Chapter overview 16714.2. Differences between attacks against keyed and keyless primitives 16814.3. Rebound attack 16914.3.1. Basic strategy of the rebound attack 16914.3.2. Rebound attack against AES-like structures 17114.4. Improving rebound attacks with Super-Sbox 17314.5. References for further reading about rebound attacks 17514.6. Brief introduction of other cryptanalysis 17614.6.1. Internal differential cryptanalysis 17614.6.2. Rotational cryptanalysis 17714.7. References 177Chapter 15 Cryptanalysis of SHA-1 181Marc Stevens15.1. Design of SHA-1 18115.2. SHA-1 compression function 18215.3. Differential analysis 18415.4. Near-collision attacks 18415.5. Near-collision search 18515.6. Message expansion differences 18615.7. Differential trail 18715.8. Local collisions 18715.9. Disturbance vector 18815.10. Disturbance vector selection 18915.11. Differential trail construction 19015.12. Message modification techniques 19015.13. Overview of published collision attacks 19115.14. References 192Part 2 Future Directions 195Chapter 16 Lightweight Cryptography 197Meltem Sönmez Turan16.1. Lightweight cryptography standardization efforts 19716.2. Desired features 19816.3. Design approaches in lightweight cryptography 20016.4. References 202Chapter 17 Post-Quantum Symmetric Cryptography 203María Naya-Plasencia17.1. Different considered models 20417.1.1. With respect to the queries 20417.1.2. With respect to memory 20517.2. On Simon’s and Q2 attacks 20617.2.1. Off-line Simon’s attack 20717.3. Quantizing classical attacks in Q 1 20717.3.1. About collisions 20717.4. On the design of quantum-safe primitives 20817.5. Perspectives and conclusion 20917.5.1. About losing the quantum and classical surname 20917.5.2. No panic 20917.6. References 209Chapter 18 New Fields in Symmetric Cryptography 215Léo Perrin18.1. Arithmetization-oriented symmetric primitives (ZK proof systems) 21618.1.1. The current understanding of this new language 21718.1.2. The first attempts 21818.1.3. Cryptanalysis 21918.2. Symmetric ciphers for hybrid homomorphic encryption 22018.2.1. The current understanding of this new language 22118.2.2. First design strategies 22118.3. Parting thoughts 22318.4. References 223Chapter 19 Deck-function-based Cryptography 227Joan Daemen19.1. Block-cipher centric cryptography 22719.2. Permutation-based cryptography 22719.3. The problem of the random permutation security model 22819.4. Deck functions 22819.5. Modes of deck functions and instances 22919.6. References 230List of Authors 231Index 233Summary of Volume 1 239