Tim Beyne, Vincent Rijmen · Cambridge University Press eBooks · 2025
Applications of cryptography are plenty in everyday life. This guidebook is about the security analysis or 'cryptanalysis' of the basic building blocks on which these applications rely. Rather than covering a variety of techniques at an introductory level, this book provides a comprehensive and in-depth treatment of linear cryptanalysis. The subject is introduced from a mathematical point of view, providing an overview of the most influential papers on linear cryptanalysis and placing them in a consistent framework based on linear algebra. A large number of examples and exercises are included, drawing upon practice as well as theory. The book is accessible to students with no prior knowledge of cryptography. It covers linear cryptanalysis starting from the basics, including linear approximations and trails, correlation matrices, automatic search, key-recovery techniques, up to advanced topics, such as multiple and multidimensional linear cryptanalysis, zero-correlation approximations, and the geometric approach.
Cited by 0
Kaisa Nyberg, Antonio Flórez-Gutiérrez · SPIRE - Sciences Po Institutional REpository · 2023
Linear cryptanalysis of block ciphers has its origins in stream cipher cryptanalysis. This chapter introduces an approach to linear cryptanalysis of iterative block ciphers, including tools such as the piling-up lemma and a statistical model for estimating the data requirement of a key-recovery attack. Together with differential cryptanalysis, linear cryptanalysis is today one of the main methods to evaluate the security of a block cipher. The Walsh-Hadamard transform has numerous applications in linear cryptanalysis. In order to recover some key bits, the sample correlations are compared to the correlations obtained in the offline analysis of the cipher. There are two basic types of key recovery methods: Matsui's Algorithm 1 and Matsui's Algorithm 2. The idea of using multiple linear approximations started with using several linear approximations involving the same key bits. The chapter describes the wrong-key and right-key probability distributions for some commonly used linear cryptanalysis statistics.
Cited by 0Open access
Yosuke Todo · 2023
This chapter introduces differential-linear attacks, which were proposed by Langford and Hellman. Differential-linear attacks are combined attacks in the sense that two well-known attacks, that is, a differential attack and a linear attack, are successfully combined. Similarly to other attacks like differential attacks or linear attacks, additional rounds are added before and after a differential-linear distinguisher. The fast Fourier transformation is sometimes useful to improve the time complexity of the key recovery. At Eurocrypt 2019, Bar-On et al. presented the paper DLCT: A New Tool for Differential-Linear Cryptanalysis , where the issue related to the dependency between E1 and E2 and a middle layer is formally analyzed. At CRYPTO 2020, Beierle et al.proposed the paper Improved Differential-Linear Attacks with Applications to ARX Ciphers , where three techniques are introduced to improve differential-linear attacks.
Cited by 0
Collard Baudoin, Standaert Fran ccedil ois-Xavier · IOS Press eBooks · 2011
Linear cryptanalysis is one of the most investigated attack against modern block ciphers. It has significantly influenced the design of symmetric encryption algorithms. However, because of the large cardinality of the problems they raise, security evaluations against these attacks frequently rely on a number of simplifying assumptions. In this chapter, we provide an experimental review of the basic hypotheses used in linear cryptanalysis, and take advantage of our experiments to discuss the practical and provable security approaches for designing secure ciphers.
Cited by 2
Baudoin Collard · 2011
Since the publication of linear cryptanalysis in the early 1990s, the precise under-standing of the statistical properties involved in such attacks has proven to be a challenging and computationally intensive problem. As a consequence, a number of strategies have been developed, in order to design block ciphers secure against
Cited by 0
Tim Beyne, Vincent Rijmen · Cambridge University Press eBooks · 2025
Cited by 0
Céline Blondeau, Gregor Leander, Kaisa Nyberg · Journal of Cryptology · 2016
Cited by 69
Jorge Nakahara Jr, Jorge Nakahara, Joos Vandewalle et al. · 2003
Former research reports suggesting the idea of non-linear cryptanalysis of block ciphers date back to the work of Harpes, on generalizations of Matsui's linear cryptanalytic attacks, presented at Eurocrypt '95. Also, the non-linear approach was more explicitly stated in an attack against DES described by Knudsen and Robshaw at Eurocrypt'96 (again as an extension of the concept of linear cryptanalysis, in which binary-valued non-linear approximations are used to approximated the action of the S-boxes of DES). More recently, at Crypto'98, Shimoyama and Kaneko improved Knudsen and Robshaw's attack on DES using quadratic relations to approximate the DES S-boxes. Moreover, the research results of Van Dooren were also concerned with non-linear approximations applied to two AES nalist block ciphers, Two sh and Serpent.
Cited by 0
Wenjun Wu · 2000
In this paper, LOKI97 is analyzed using linear cryptanalysis. The results show that LOKI97 does not meet the needs of AES (advanced encryption standard). Using algorithm 1 of linear cryptanalysis, the authors can get the 92 -bit subkey with 2 50 known plaintexts and the success rate is 0.977; using algorithm 2 of linear cryptanalysis, it is possible to break LOKI97 with 2 45 known plaintexts and the success rate is 0.967.
Cited by 0
He Yeping · 2000
A truncated differential-linear cryptanalysis method is proposed, which extends differential-linear method. DES (data encryption standard) algorithms of 9-ro und and 11-round were analyzed. The method was proved more convenient and widel y applicable. In DES like cipher algorithms, the fact that the order in which S -boxes were placed would affect the security of cipher was shown by the method. In this way, the truncated differential-linear method gives a criterion for or dering S-boxes optimally.
Cited by 1
Orr Dunkelman Nathan, Nathan Keller · 2006
CTC is a toy cipher designed by Courtois in order to prove the strength of algebraic attacks. In this paper we study the di#erential and the linear behavior of the 85 S-boxes version, which is attacked using algebraic techniques faster than exhaustive key search. We show that an n-round variant of the cipher can be attacked by a linear attack using only 2 2n+2 known plaintexts, with a negligible time complexity. We conclude that CTC is insecure, even for quite a large number of rounds. We note that our observations can be probably used to devise other attacks that exploit the relatively slow di#usion of CTC.
Cited by 0
Zhiqiang Liu, Dawu Gu, Jing Zhang et al. · Lecture notes in computer science · 2010
Cited by 15
Jung‐Keun Lee, Woo-Hwan Kim · IACR Transactions on Symmetric Cryptology · 2020
We propose an improved and extended approach of the multiple linear cryptanalysis presented by A. Biryukov et al. at CRYPTO 2004 that exploits dominant and statistically independent linear trails. While they presented only rank based attacks with success probability 1, we present threshold based attacks as well as rank based ones using newly introduced statistic that is a linear combination of the component statistics for the trails and is an approximation of the LLR statistic. The rank based Algorithm 1 style attack yields the same estimate for the gain with Biryukov et al.’s Algorithm 1 style attack. For each of the threshold based Algorithm 1 style and Algorithm 2 style attacks, we provide a formula for its advantage in terms of the correlations of the trails, the data complexity, and the success probability in case the aimed success probability is not 1. Combining the threshold based attacks with the rank based ones, we get attacks each of which has better estimates for the advantage compared to the threshold based one in case the aimed success probability is close to 1. We then extend the methods to get a new framework of multiple linear attacks exploiting close-to-dominant linear trails that may not be statistically independent. We apply the methods to full DES and get linear attacks using 4 linear trails with about the same or better complexity compared to those presented at ASIACRYPT 2017 that use 4 additional trails. With data complexity less than 241, the attack has better complexity than existing attacks on DES.
Cited by 1Open access
Eli Biham, Orr Dunkelman, Nathan Keller · 2001
Cited by 2
Phuong Ha Nguyen, Lei Wei, Huaxiong Wang et al. · Lecture notes in computer science · 2010
Cited by 16
Hermelin Miia, Kaisa Nyberg · IOS Press eBooks · 2011
In this article, the theory of multidimensional linear attacks on block ciphers is developed and the basic attack algorithms and their complexity estimates are presented. As an application, Cho's multidimensional linear distinguisher for the block cipher PRESENT is discussed in detail.
Cited by 30
Tim Beyne, Vincent Rijmen · Cambridge University Press eBooks · 2025
Cited by 0
Professor James, L. Massey, Supervisors Carlo Harpes et al. · 1995
In this work we give some bounds which can be used to determine if a block cipher is secure against generalized linear cryptanalysis and partitioning cryptanalysis. For this purpose, we give a new definition of imbalance which has some nice properties, and we show that an equivalent of Matsui's piling-up lemma holds for this definition. The bounds are illustrated with examples. We prove that it suffices to consider only homomorphic I/O sums when looking for upper bounds on the imbalance. Based on work of Harpes, Kramer, and Massey, we therefore conclude that very likely the cipher IDEA is secure against generalized linear cryptanalysis. Later, we demonstrate how to apply an upper bound for partitioning cryptanalysis to IDEA. We also show that the use of nearly bent functions in the round function most likely thwarts attacks based on the generalization of linear cryptanalysis and on partitioning cryptanalysis. Hopefully this work will bring us towards a setting which can be used to desi...
Cited by 0
Benoît Gérard, Jean–Pierre Tillich · Lecture notes in computer science · 2009
Cited by 15
Jan Říha · Digital Repository (National Repository of Grey Literature) · 2011
In the present work we study advanced methods of linear cryptanalysis. At the beginning, we describe the principle of Matsui's linear cryptanalysis, the two basic algorithms - Algorithm 1 and Algorithm 2, against DES cipher. Further it is described a generalization of linear cryptanalysis and consequently partitioning and statistical cryptanalysis. Then it is followed by a look on the linear approximations over the correlation matrices. Furthermore, we study an improvement of Matsui's Algorithm 2 using Fast Fourier transform, based on circulant matrices theory. Finally we deal multidimensional linear cryptanalysis that uses multiple linear approximations and in the very end we propose an own design of improvement of multidimensional extension of Algorithm 2 by using Fast Fourier transform.
Cited by 0