Symmetric Cryptography, Volume 2 E-Book
142,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Symmetric cryptology is one of the two main branches of cryptology. Its applications are essential and vital in the Information Age, due to the efficiency of its constructions. The scope of this book in two volumes is two-fold. First, it presents the most important ideas that have been used in the design of symmetric primitives, their inner components and their most relevant constructions. Second, it describes and provides insights on the most popular cryptanalysis and proof techniques for analyzing the security of the above algorithms. A selected number of future directions, such as post-quantum security or design of ciphers for modern needs and particular applications, are also discussed. We believe that the two volumes of this work will be of interest to researchers, to master's and PhD students studying or working in the field of cryptography, as well as to all professionals working in the field of cybersecurity.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 485
Veröffentlichungsjahr: 2023
Ähnliche
Table of Contents
Cover
Table of Contents
Title Page
Copyright Page
Preface
PART 1: Cryptanalysis of Symmetric-key Algorithms
1 Differential Cryptanalysis
1.1. Statistical attacks on block ciphers: preliminaries
1.2. Principle of differential cryptanalysis and application to DES
1.3. Some refinements and generalizations
1.4. Design strategies and evaluation
1.5. Further notes and references
1.6. References
Notes
2 Linear Cryptanalysis
2.1. History
2.2. Correlation and linear hull
2.3. Multidimensional linear approximation
2.4. Walsh-Hadamard transform
2.5. Linear approximation of an iterative block cipher
2.6. Matsui’s Algorithm 1 type of key recovery
2.7. Matsui’s Algorithm 2 type of key recovery
2.8. Searching for linear approximations and estimating correlations
2.9. Speeding up key recovery
2.10. Key-recovery distinguisher
2.11. Classical model of Algorithm 2
2.12. Algorithm 2 with distinct known plaintext and randomized key
2.13. Multiple linear approximations
2.14. Multidimensional linear cryptanalysis
2.15. References
3 Impossible Differential Cryptanalysis
3.1. Finding impossible differentials
3.2. Key recovery
3.3. Some improvements
3.4. Applications
3.5. References
4 Zero-Correlation Cryptanalysis
4.1. Correlation and linear cryptanalysis
4.2. Attacks using a linear hull with correlation zero
4.3. Linear hulls with correlation zero
4.4. References
5 Differential-Linear Cryptanalysis
5.1. Brief introduction of differential-linear attacks
5.2. How to estimate correlations of a differential-linear distinguisher
5.3. On the key recovery
5.4. State of the art for differential-linear attacks
5.5. References
Notes
6 Boomerang Cryptanalysis
6.1. Basic boomerang attack
6.2. Variants and refinements
6.3. Tricks and failures
6.4. Formalize the dependency
6.5. References
7 Meet-in-the-Middle Cryptanalysis
7.1. Introduction
7.2. Basic meet-in-the-middle framework
7.3. Meet-in-the-middle techniques
7.4. Automatic tools
7.5. References
Notes
8 Meet-in-the-Middle Demirci-Selçuk Cryptanalysis
8.1. Original Demirci-Selçuk attack
8.2. Improvements
8.3. Finding the best attacks
8.4. References
9 Invariant Cryptanalysis
9.1. Introduction
9.2. Invariants for permutations and block ciphers
9.3. On design criteria to prevent attacks based on invariants
9.4. A link to linear approximations
9.5. References
Notes
10 Higher Order Differentials, Integral Attacks and Variants
10.1. Integrals and higher order derivatives
10.2. Algebraic degree of an iterated function
10.3. Division property
10.4. Attacks based on integrals
10.5. References
Notes
11 Cube Attacks and Distinguishers
11.1. Cube attacks and cube testers
11.2. Conditional differential attacks and dynamic cube attacks
11.3. References
Notes
12 Correlation Attacks on Stream Ciphers
12.1. Correlation attacks on the nonlinear combination generator
12.2. Correlation attacks and decoding linear codes
12.3. Fast correlation attacks
12.4. Generalizing fast correlation attacks
12.5. References
13 Addition, Rotation, XOR
13.1. What is ARX?
13.2. Understanding modular addition
13.3. Analyzing ARX-based primitives
13.4. References
Notes
14 SHA-3 Contest Related Cryptanalysis
14.1. Chapter overview
14.2. Differences between attacks against keyed and keyless primitives
14.3. Rebound attack
14.4. Improving rebound attacks with Super-Sbox
14.5. References for further reading about rebound attacks
14.6. Brief introduction of other cryptanalysis
14.7. References
15 Cryptanalysis of SHA-1
15.1. Design of SHA-1
15.2. SHA-1 compression function
15.3. Differential analysis
15.4. Near-collision attacks
15.5. Near-collision search
15.6. Message expansion differences
15.7. Differential trail
15.8. Local collisions
15.9. Disturbance vector
15.10. Disturbance vector selection
15.11. Differential trail construction
15.12. Message modification techniques
15.13. Overview of published collision attacks
15.14. References
Notes
PART 2: Future Directions
16 Lightweight Cryptography
16.1. Lightweight cryptography standardization efforts
16.2. Desired features
16.3. Design approaches in lightweight cryptography
16.4. References
Notes
17 Post-Quantum Symmetric Cryptography
17.1. Different considered models
17.2. On Simon’s and Q2 attacks
17.3. Quantizing classical attacks in Q1
17.4. On the design of quantum-safe primitives
17.5. Perspectives and conclusion
17.6. References
Notes
18 New Fields in Symmetric Cryptography
18.1. Arithmetization-oriented symmetric primitives (ZK proof systems)
18.2. Symmetric ciphers for hybrid homomorphic encryption
18.3. Parting thoughts
18.4. References
Notes
19 Deck-function-based Cryptography
19.1. Block-cipher centric cryptography
19.2. Permutation-based cryptography
19.3. The problem of the random permutation security model
19.4. Deck functions
19.5. Modes of deck functions and instances
19.6. References
List of Authors
Index
Summary of Volume 1
End User License Agreement
List of Tables
Chapter 1
Table 1.1. DDT of the 3-bit permutation from example 1.1
Chapter 3
Table 3.1. Summary of the best impossible differential attacks against AES-128...
Chapter 4
Table 4.1. Overview of zero-correlation attacks
Chapter 6
Table 6.1. SKINNY’s 4-bit S-box
Chapter 16
Table 16.1. Underlying primitives of the second-round candidates
List of Illustrations
Chapter 1
Figure 1.1. Overall structure of a statistical attack on an iterative block ci...
Figure 1.2. DES Feistel F-function Φ
Figure 1.3. One-round DES characteristic of probability 1/4
Figure 1.4. Three-round DES characteristic of probability approximately 1/16....
Figure 1.5. Two-round iterative characteristic for DES.
Figure 1.6. Truncated differential characteristic on DES reduced to four round...
Figure 1.7. Example of a truncated differential characteristic for four rounds...
Chapter 3
Figure 3.1. Impossible differential for four rounds of AES
Figure 3.2. Basic impossible differential attack.
Chapter 5
Figure 5.1. Differential-linear distinguisher
Figure 5.2. Log2 of differential probability and squared correlation
Figure 5.3. Differential-linear distinguisher with middle layer
Figure 5.4. Attack framework proposed by Beierle et al.(2020)
Chapter 6
Figure 6.1. Boomerang and sandwich attacks.
Figure 6.2. Decompose the cipher into rounds (left), and decompose the cipher ...
Figure 6.3. S-box and Feistel switches.
Figure 6.4. BCT and FBCT of SKINNY’s 4-bit S-box
Chapter 7
Figure 7.1. Meet-in-the-middle attack with splice-and-cut
Figure 7.2. Meet-in-the-middle attack with a biclique
Chapter 8
Figure 8.1. 4 AES-rounds. The 25 black bytes are the parameters of describing ...
Figure 8.2. Online phase of Demirci and Selçuk attack. ℬ
on
is composed by...
Figure 8.3. Attack on 8 AES rounds. Bytes of ℬ
off
are in black. Bytes of ℬ
on
a...
Figure 8.4. Differential characteristic on 8 AES rounds. The differences are n...
Chapter 9
Figure 9.1. The partition of into Sg and its complement for an invariant g. ...
Figure 9.2. Propagation of invariant subspaces in key-alternating block cipher...
Chapter 10
Figure 10.1. Three-round integral for the AES as depicted in Knudsen and Wagne...
Chapter 12
Figure 12.1. Scenario for correlation attacks
Figure 12.2. Overview of the E0 stream cipher
Chapter 14
Figure 14.1. Basic differences of attacks against keyed (left) and keyless (ri...
Figure 14.2. Toy function with a simple SPN structure. Both the block size and...
Figure 14.3. Differential propagation of the rebound attack against a four-rou...
Figure 14.4. Rebound attack with Super-Sboxes. Numbers between #X
3
and #Y
3
den...
Chapter 15
Figure 15.1. Internal round of the compression function of SHA-1.
Figure 15.2. Two-block attack.
Guide
Cover Page
Table of Contents
Title Page
Copyright Page
Preface
Begin Reading
List of Authors
Index
Summary of Volume 1
WILEY END USER LICENSE AGREEMENT
Pages
iii
iv
xiii
xiv
xv
xvi
xvii
xviii
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
SCIENCES
Computer Science, Field Directors – Valérie Berthé and Jean-Charles Pomerol
Cryptography, Data Security, Subject Head – Damien Vergnaud
Symmetric Cryptography 2
Cryptanalysis and Future Directions
Coordinated by
Christina Boura
María Naya-Plasencia
First published 2023 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the under mentioned address:
ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK
www.iste.co.uk
John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA
www.wiley.com
© ISTE Ltd 2023The rights of Christina Boura and María Naya-Plasencia to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s), contributor(s) or editor(s) and do not necessarily reflect the views of ISTE Group.
Library of Congress Control Number: 2023930938
British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-78945-147-4
ERC code:PE6 Computer Science and Informatics PE6_5 Cryptology, security, privacy, quantum cryptography
Preface
Christina BOURA1 and María NAYA-PLASENCIA2
1University of Paris-Saclay, UVSQ, CNRS, Versailles, France
2Inria, Paris, France
Symmetric-key cryptology is one of the two main branches of modern cryptology. It comprises all primitives, modes and constructions used to ensure the confidentiality, authenticity and integrity of communications by means of a single key shared between the two communicating parties. Hash functions and some other keyless constructions are equally considered as symmetric constructions because of the similarity in the design and analysis with classical keyed symmetric ciphers. Symmetric algorithms are essential for establishing secure communications, as they can have very compact implementations and achieve high speed in both software and hardware. Furthermore, compared to public-key algorithms, keys used in symmetric cryptography are short, typically of 128 or 256 bits only.
The goal of this two-volume project is to provide a thorough overview of the most important design, cryptanalysis and proof techniques for symmetric designs. The first volume is dedicated to the most popular design trends for symmetric primitives, modes and constructions, and to the presentation of the most important proof techniques. On the other hand, the current volume describes and analyzes some of the most well-established and powerful cryptanalysis techniques against symmetric constructions.
Cryptanalysis is an essential process for establishing trust toward the symmetric ciphers to be used and deployed. Indeed, in symmetric cryptography, it is common to provide security proofs for the modes of operation and high-level constructions. These security proofs, analyzed in Volume 1, are fundamental for having confidence in the high-level constructions themselves, but they often rely on unrealistic assumptions, for example, by considering the internal functions to be perfect random ones. Therefore, in order to trust the primitives, cryptanalysis is a necessary process to be taken into account together with the security proofs.
The first modern symmetric cryptanalysis techniques started developing almost together with the appearance of the first symmetric designs. These first cryptanalysis techniques have not stopped evolving since. Moreover, the appearance of new designs had as a consequence the development of new analysis techniques adapted to these new schemes.
The goal of this second volume is to present the most powerful and the most promising attacks among those that have emerged since the 1980s. The book is divided into two parts. The first part contains 15 chapters and gives an overview of the most important cryptanalysis techniques. The second part is composed of four chapters and investigates some future directions for the field of symmetric cryptology.
Chapter 1 is dedicated to differential cryptanalysis, the oldest and probably the most well-studied attack against block ciphers and related primitives. First, a general background for statistical attacks is provided and the notion of distinguisher is introduced. Then, the most important notions encountered in differential cryptanalysis are given. Some possible refinements and extensions of the basic attack are provided, notably the differential effect and truncated differential characteristics. Finally, the most prominent design approaches to achieve resistance against this class of attacks are given.
Together with differential cryptanalysis, linear cryptanalysis is without doubt the second most well-known analysis technique against block ciphers. This technique is described in Chapter 2. After a brief historical note, the main notions for this attack, notably those of correlation, linear hull and multidimensional linear approximations are presented. Then, two well-known algorithms for key recovery, namely Matsui’s algorithms 1 and 2, are given. The problem of finding good linear approximations for a given cipher is analyzed next and some techniques to speed up key recovery are given. Finally, two extensions of classical linear cryptanalysis are provided: the use of multiple linear approximations and the technique of multidimensional linear cryptanalysis.
Impossible differential cryptanalysis is another powerful attack against block ciphers. The idea, explained in Chapter 3, is to exploit differentials of probability zero. The distinguishing part, consisting of finding good impossible differentials, is first analyzed. Techniques for the key recovery part are given next. In this part, closed formulas for estimating the complexity of an attack are given. Some improvements to the classical version of this cryptanalysis technique are provided at the end of this chapter.
Zero-correlation attacks are an extension of linear cryptanalysis. These attacks, presented in Chapter 4, are based on linear approximations with correlation exactly zero. First, this chapter presents the central notion of correlation matrices. The notions of linear trails and hulls are defined once again and some results on computing the correlations over a permutation are provided next. Then, this chapter analyzes how linear hulls with correlation zero can be used to mount an attack and techniques for reducing the data complexity are given. Finally, some important applications for Feistel ciphers and for the advanced encryption standard (AES) are discussed.
Chapter 5 is dedicated to differential-linear attacks. This cryptanalysis technique consists of successfully combining a differential attack together with a linear one. First, the attack framework is presented and ways to estimate correlations of a differential-linear distinguisher are given next. Then, the key recovery part is discussed and the notion of differential-linear connecting table (DLCT) is presented. At the end, three techniques to improve differential-linear attacks are discussed.
Boomerang attacks are statistical attacks against block ciphers based on differential cryptanalysis. Chapter 6 introduces this type of cryptanalysis and some of its refinements, namely, the amplified boomerang and rectangle attacks. A discussion on the probability computation of boomerangs is next given, and several ways to improve or formalize this computation are discussed. Finally, a recent tool to calculate the boomerang probability for a single S-box, called Boomerang connectivity table (BCT) is presented together with its Feistel variant, FBCT.
Chapter 7 gives an overview of another famous cryptanalysis technique called meet-in-the-middle cryptanalysis. Meet-in-the-middle attacks are among the oldest symmetric cryptanalysis techniques and still continue to evolve. This chapter starts by presenting the basic meet-in-the-middle framework together with a first complexity analysis. The most important techniques used in modern meet-in-the-middle cryptanalysis are given next, such as the partial or indirect matching, the sieve-in-the-middle or the slice-and-cut technique. Finally, a method called biclique, which permits extension of the number of rounds of a meet-in-the-middle attack, is presented.
Chapter 8 presents meet-in-the-middle Demirci-Selçuk attacks, an advanced form of meet-in-the-middle cryptanalysis, particularly successful on reduced versions of the AES. The chapter starts by presenting the basic form of this attack and discusses its application to the AES. Then, several refinements and techniques are given. A discussion of how to choose the best parameters for mounting such an attack is provided, and finally a series of tools for applying a meet-in-the-middle attack in an automated way are briefly presented.
Invariant attacks are a form of structural cryptanalysis against block ciphers and cryptographic permutations that showed to be particularly efficient against some lightweight cryptographic designs. Chapter 9 presents the most important concepts and ideas behind two important invariant attacks classes, the invariant subspace attacks and the nonlinear invariant attacks. Methods to detect potential vulnerabilities in cryptographic designs that could lead to the presence of invariants are discussed. Finally, design criteria to prevent attacks based on invariants are provided, and a link between invariant attacks and linear approximations is discussed.
Chapter 10 gives an overview of higher order differential and integral attacks as well as some of their most important variants. All these attacks exploit either some algebraic or some structural property of the underlying design, or sometimes both type of properties at the same time. The chapter starts by describing the notions of integrals and higher order derivatives. The notion of algebraic degree, essential for these attacks, and its properties for iterated permutations are presented next. A powerful tool, called the division property, that can be seen as a combination of integral and higher order differential cryptanalysis is given. Finally, attacks based on integrals are discussed.
Cube attacks and cube testers are additional methods of algebraic cryptanalysis that target designs with a relatively low number of nonlinear operations. Chapter 11 is dedicated to this class of attacks and summarizes the main ideas of these techniques. The classical cube attack that aims at recovering the secret key by analyzing the algebraic form of the cipher is described first. Then, a related distinguishing technique, called cube testers, is presented. Finally, conditional differential attacks and dynamic cube attacks, key recovery techniques related to cube attacks, are briefly given.
Chapter 12 describes correlation attacks against stream ciphers, one of the most well-studied and efficient cryptanalysis technique against this class of algorithms. The main idea of attacks against nonlinear combination generators is first presented. The link between correlation attacks and the linear codes decoding problem is next presented. Notably, the so-called fast correlation attacks that are attacks exploiting the above link to speed up the decoding problem are extensively analyzed. Finally, the chapter is concluded with two generalizations of correlation attacks on the stream ciphers E0 and A5/1.
ARX ciphers are constructions that only use the operations of modular addition, rotation and XOR to compute their output. These ciphers, described in Chapter 13, permit constant-time and extremely fast implementations in software and have been used in several popular designs and standards. The basic structure of such schemes is first described. Then, the development of ARX ciphers since the 1980s until today is provided. The properties of modular addition, the only nonlinear operation in these constructions, are discussed next as these properties are crucial for understanding the security of these schemes. Finally, methods and tools for analyzing the security of ARX ciphers are presented.
The NIST SHA-3 competition was a public competition held by the US National Institute of Standards and Technology (NIST) between 2008 and 2012. Its goal was to develop and standardize a new hash function called SHA-3. During the 4 years of the competition, many new hash function cryptanalysis techniques emerged. Chapter 14 is dedicated to the presentation of some of these techniques. First, a discussion of the difference between attacks against keyed and keyless primitives is provided. Then, the biggest part of this chapter is dedicated to the description of the rebound attack, probably the most powerful technique that emerged in this context against substitution-permutation network (SPN)-based hash functions. At the end of this chapter, other new cryptanalysis methods developed against some SHA-3 candidates, notably the internal differential and the rotation cryptanalysis, are presented.
SHA-1 is a standardized cryptographic hash function, deprecated since 2011, but that was implemented inside a multitude of industrial products for decades and is still in use in many applications. The cryptanalysis efforts against this standard form a fascinating series of results until the practical break of the function in 2017. Chapter 15 is dedicated to the cryptanalysis of SHA-1 and describes the most important cryptanalysis techniques that were developed while trying to break SHA-1.
The second part of this book is consecrated to the discussion of some promising future directions for the field of symmetric cryptology.
During the last decade, many resource-constrained computing environments were developed and largely deployed. Most of them treat sensitive data and need to implement cryptographic algorithms to ensure their security. However, most of the general-purpose cryptographic algorithms cannot be implemented on such constrained devices while keeping decent performances, thus new cryptographic constructions are needed. Lightweight cryptography encompasses all cryptographic primitives, schemes and protocols that are optimized for resource-constrained devices. Chapter 16 is dedicated to lightweight cryptography and provides an overview of the standardization efforts, desired features and design trends for these applications. The NIST standardization process for lightweight cryptography, a public competition launched in 2018, is notably discussed.
The future arrival of quantum computers will have enormous consequences for the field of cryptography. The cryptographic community has been devoting significant time and effort over several years in anticipation of these potential effects. We know today that the most deployed public key schemes will be broken, because notably of Shor’s algorithm, and for this reason the public key community is actively searching for solutions and replacements. However, for symmetric algorithms, the situation is different. The main quantum algorithm relevant to symmetric cryptography is Grover’s algorithm that permits to accelerate the generic exhaustive search attack by a square root. Thus, doubling the size of the key would potentially be sufficient to overcome this problem. However, it is naïve to believe that this will be the only consequence for symmetric schemes. For this reason, for some years, a new domain dedicated to the quantum cryptanalysis of symmetric primitives, modes and constructions emerged. The most important of these efforts and the latest results are described in Chapter 17 of this book.
Not all symmetric algorithms are intended to be run on classical computing environments such as CPUs or smartcards. Chapter 18 describes the last efforts made in designing the newly introduced arithmetization-oriented (AO) symmetric ciphers, intended to be used within some particular zero-knowledge protocols, homomorphic encryption (HE) or multi-party computation (MPC) schemes. This chapter describes the most important design strategies for this family of ciphers and briefly discusses the most promising cryptanalysis techniques against them.
Chapter 19 describes finally some promising future directions for the design of symmetric primitives. In particular, doubly extendable cryptographic keyed (deck) functions are discussed.
The field of cryptography has never stopped evolving since the appearance of the first commercial cryptographic applications in the 1970s. Due to this constant evolution, providing a complete survey of all the design trends, cryptanalysis techniques or proof methods is an extremely difficult task. We believe, however, that this book offers a good starting point to all readers interested in learning about the most important and promising results of the field, in particularly to all those wishing to learn how to design and analyze a secure symmetric cipher. We believe that the two volumes of this work will be helpful to researchers, master’s and PhD students studying or working in the field of cryptography as well as to all professionals working in the field of cybersecurity.
July 2023
