Fact-checked by Grok 2 weeks ago

Linear cryptanalysis

Linear cryptanalysis is a known-plaintext attack on block ciphers that exploits linear approximations over GF(2) to relate plaintext bits, ciphertext bits, and key bits, where these approximations hold true with a probability significantly deviating from 1/2, enabling the recovery of secret key information through statistical analysis.^[1] Introduced by Japanese cryptographers Mitsuru Matsui and Atsushi Yamagishi in 1992 at EUROCRYPT, with the first application to the FEAL cipher, the method was subsequently detailed in a 1993 theoretical attack on reduced-round versions of the Data Encryption Standard (DES).^[2]^[1] In 1994, Matsui demonstrated its practicality by experimentally breaking the full 16-round DES using Algorithm 2, requiring approximately 2^{43} known plaintext-ciphertext pairs and about 2^{43} DES encryptions, with an 85% success probability.^[3] The core of linear cryptanalysis involves constructing linear approximations for nonlinear components, such as S-boxes, where the input and output bits satisfy an equation like input parity ⊕ output parity = constant with a measurable bias ε = |p - 1/2|, where p is the probability.^[4] These approximations are extended across multiple rounds using the piling-up lemma, which states that the bias of a combined approximation is the product of individual biases assuming independence, allowing coverage of the cipher's structure.^[4] Matsui's Algorithm 1 performs a theoretical key search by evaluating approximations for partial keys, while Algorithm 2, more practical for implementation, uses partial decryptions and parity counts on known pairs to identify the most likely last-round subkey bits, followed by brute-force on the remainder.^[3]^[4] The attack's efficiency depends on the highest bias achievable, often requiring 1/ε^2 pairs, where ε is the total bias. Since its inception, linear cryptanalysis has evolved into a cornerstone of symmetric-key cryptanalysis, with extensions including multiple linear approximations to amplify biases, multidimensional variants treating approximations as subspace correlations, and hybrid techniques like differential-linear attacks combining it with differential cryptanalysis.^[4]^[5] These advancements have been applied to numerous ciphers, such as FEAL, CAST, and components of AES candidates, prompting cipher designers to minimize linear biases through balanced structures and diffusion layers.^[3] Despite refinements, the original method remains influential, with ongoing research exploring its limits in quantum settings, against authenticated encryption schemes, and including machine learning-aided approaches as of 2024.^[6]^[7]^[8]

Introduction

Definition and principles

Linear cryptanalysis is a known-plaintext attack on block ciphers, such as the Data Encryption Standard (DES), that exploits linear relations among plaintext bits, ciphertext bits, and key bits to recover secret key information. Introduced by Mitsuru Matsui in 1993, this method targets the non-linear components of the cipher, like substitution boxes (S-boxes), by finding approximations that hold with probabilities significantly deviating from random expectation. The core principle relies on identifying high-probability linear equations that approximate the cipher's transformations, particularly where the non-linear operations introduce a measurable bias away from perfect randomness. These approximations capture how certain combinations of input and output bits correlate linearly, allowing the attacker to statistically distinguish the cipher's behavior from that of a random permutation. Unlike differential cryptanalysis, which focuses on differences between pairs of inputs, linear cryptanalysis uses parity checks on bit selections to probe the cipher's structure. Mathematically, a linear approximation takes the form \Gamma_p \cdot P \oplus \Gamma_c \cdot C \oplus \Gamma_k \cdot K = 0, where P denotes the plaintext, C the ciphertext, K a subkey, and \Gamma_p, \Gamma_c, \Gamma_k are bit masks (selection vectors) that specify which bits are XORed together in each term; the dot operation represents the parity (XOR sum) of the selected bits. This equation holds with probability p \neq 1/2, and the bias \epsilon = |p - 1/2| quantifies its usefulness, with higher biases enabling more efficient key recovery. In the basic workflow, an attacker first collects a set of plaintext-ciphertext pairs under the target key. They then identify candidate linear approximations for individual cipher components, compute their biases, and combine them across rounds to form a trail with overall high bias, using the piling-up lemma to estimate the combined probability. Finally, the approximations are applied to the collected pairs to set up statistical tests that deduce candidate values for key bits, narrowing down the key space through iterative refinement.

Historical development

A pivotal early application preceded the formal introduction, with Matsui and Atsuhiro Yamagishi developing a pre-linear known-plaintext attack on the FEAL block cipher in 1992, breaking FEAL-8 using 2^{28} plaintexts and demonstrating deterministic key recovery.^[9] Matsui's seminal work then targeted DES, with his 1993 EUROCRYPT paper outlining the theoretical framework for linear cryptanalysis, including the piling-up lemma for combining approximations across rounds.^[1] In 1994, at CRYPTO, Matsui reported the first experimental break of full 16-round DES using Algorithm 2, requiring only 2^{43} known plaintexts—significantly fewer than the 2^{56} exhaustive search—and 50 days on 12 workstations, marking a practical threat to DES security. The technique rapidly evolved for broader cipher structures, with adaptations for Feistel networks like DES and substitution-permutation networks (SPNs) appearing in subsequent analyses.^[10] Post-2000 developments included multiple linear approximations for enhanced bias estimation, probabilistic key recovery methods to reduce data complexity, and multidimensional linear cryptanalysis, which combines several approximations to improve attack efficiency on reduced-round variants of modern ciphers.^[11] These refinements, such as those incorporating key-dependent biases, extended the method's applicability while addressing limitations in single-trail attacks.^[12] The advent of linear cryptanalysis prompted a reevaluation of DES's security, confirming its vulnerability and accelerating the search for successors.^[4] It directly influenced the AES selection process in the late 1990s, where candidates like Rijndael were rigorously evaluated for resistance to linear and differential attacks, ensuring high nonlinearity in S-boxes and diffusion layers to minimize exploitable biases.^[13]

Core Concepts

Linear approximations in ciphers

In block ciphers, linear approximations provide a way to model the non-linear operations, primarily S-boxes, using linear equations over GF(2) that hold with a probability deviating from random guessing. These approximations express the XOR of certain input and output bits of the S-box as approximately equal to a linear combination of the input bits, enabling the analysis of the cipher's overall linearity.^[14] For an S-box S: \mathbb{F}_2^n \to \mathbb{F}_2^m, a linear approximation is defined by input and output masks \Gamma_{in} \in \mathbb{F}_2^n and \Gamma_{out} \in \mathbb{F}_2^m, such that the equation \Gamma_{in} \cdot X \oplus \Gamma_{out} \cdot S(X) = 0 holds with probability $1/2 + \epsilon, where \cdot denotes the dot product modulo 2 and \epsilon is the bias measuring the deviation from $1/2. The bias is computed as \epsilon = \left| \Pr[\Gamma_{in} \cdot X \oplus \Gamma_{out} \cdot S(X) = 0] - 1/2 \right|, with the probability taken over a uniform random input X. Approximations with |\epsilon| > 0 are non-trivial and useful for cryptanalysis.^[14]^[4] To derive these approximations, all possible mask pairs (\Gamma_{in}, \Gamma_{out}) are enumerated, totaling $2^{n+m} combinations, and for each pair, the equation is evaluated over all $2^n possible inputs X to count how often it holds true; biases are then calculated to identify the strongest approximations. This exhaustive search is feasible for typical S-box sizes, such as n=6 or n=8, due to the modest computational cost.^[4]^[15] Within a block cipher, these local S-box approximations are chained across multiple rounds by leveraging the cipher's diffusion layers, such as permutation boxes (P-boxes) or maximum distance separable (MDS) matrices, which are linear transformations that redistribute the approximations to connect plaintext bits to ciphertext bits without altering their linear form. This chaining allows the construction of high-probability linear relations spanning the entire cipher structure.^[14]^[4] For example, in the Data Encryption Standard (DES), the 6-to-4-bit S-boxes exhibit linear approximations with biases typically ranging from $2^{-3} to $2^{-2}, providing the foundation for analyzing the cipher's rounds.^[14]^[15]

Bias and the piling-up lemma

In linear cryptanalysis, the bias of a linear approximation quantifies the deviation of the probability that a specific linear equation involving plaintext, ciphertext, and key bits holds true from the random expectation of 1/2. This bias ε is defined as ε = |Pr[Γ · P ⊕ Δ · C ⊕ κ · K = 0] - 1/2|, where Γ, Δ, and κ represent masks for the plaintext P, ciphertext C, and key K, respectively, and · denotes bitwise XOR followed by modulo-2 inner product.^[16] The absolute value |ε| serves as a measure of the approximation's reliability, with values closer to 0 indicating near-random behavior and higher |ε| signifying exploitable correlations that deviate significantly from uniformity.^[16] The piling-up lemma, introduced by Matsui, enables the estimation of bias for multi-round linear approximations by combining biases from individual rounds under independence assumptions. For k independent linear approximations with biases ε₁, ε₂, ..., ε_k—typically corresponding to active S-boxes in each round—the overall bias ε is approximated as ε ≈ ∏_{i=1}^k ε_i when the individual biases are small.^[16] The exact expression, derived from the correlation properties of XOR operations, is given by

\varepsilon = 2^{k-1} \prod_{i=1}^k \varepsilon_i.

This formula accounts for the probabilistic chaining across rounds, where the product term amplifies or diminishes the combined deviation based on the signs and magnitudes of the individual ε_i.^[16] The piling-up lemma relies on key assumptions to ensure accuracy: the linear approximations must be independent, implying no overlapping non-linear components (such as shared S-box influences) that could correlate their outputs unexpectedly. It applies particularly to Markov ciphers, where each round's output distribution remains uniform given a uniform input and random round key, preserving the bias propagation without degradation from key dependencies.^[17] Violations of these conditions, such as in non-Markov structures, can lead to underestimated or overestimated biases, necessitating refined models like those for partially Markov ciphers.^[17] In practice, biases for single-round approximations, especially over S-boxes, are computed efficiently using the fast Walsh-Hadamard transform (FWHT), which evaluates the Walsh spectrum of the S-box function in O(m 2^m) time for an m-bit input S-box. The FWHT computes correlations as the sum ∑_x (-1)^{α · x + f(x) · β} over all inputs x, directly yielding the linear approximation table entries proportional to 1 + 2ε for masks α and β. This method, integral to building initial approximations, scales well for typical S-box sizes like 6-8 bits in block ciphers.^[16] For linear cryptanalysis to succeed against an n-bit block cipher, the final approximation's bias must satisfy |ε| > 2^{-n/2} to achieve a favorable signal-to-noise ratio, allowing statistical distinction from random permutations with feasible numbers of known plaintexts (on the order of 1/|ε|^2). Biases below this threshold render the approximation indistinguishable from noise, limiting the attack's viability.

Attack Methodology

Constructing linear trails

A linear trail in linear cryptanalysis is defined as a sequence of input and output masks across multiple rounds of a block cipher, where each mask specifies the bits involved in the linear approximation for that round, and the output mask of one round matches the input mask of the next to ensure propagation.^[18] This sequence identifies the active S-boxes and their associated approximations, allowing the overall correlation of the trail to be estimated as the product of the individual one-round correlations, per the piling-up lemma.^[4] For early block ciphers like DES, linear trails were constructed manually by exhaustively evaluating linear approximations of individual S-boxes and chaining them across rounds to form multi-round paths with high correlation. In Feistel structures, construction typically focuses on approximations within one branch, leveraging the XOR operation to propagate masks while minimizing activity in the other branch. For substitution-permutation network (SPN) ciphers, trails are built by selecting approximations through S-boxes and ensuring diffusion via the linear mixing layer covers all bytes, often starting from plaintext or ciphertext masks with low Hamming weight. Post-2000, automated tools have dominated construction, employing branch-and-bound algorithms—initially proposed by Matsui and later improved with techniques like mixed-integer linear programming (MILP), satisfiability (SAT) solvers, and optimized graph searches—to enumerate and select optimal trails efficiently for larger ciphers.^[19]^[20] More recently, as of 2025, machine learning techniques have been proposed to further automate and enhance the discovery of high-bias linear approximations and key recovery processes, offering potential improvements in efficiency for analyzing modern ciphers.^[8] The primary criterion for selecting trails is to maximize the absolute value of the trail's bias |ε|, as the required data complexity for the attack approximates 1/ε² plaintext-ciphertext pairs, while keeping computational costs for subsequent steps manageable.^[4] Optimization involves using linear approximation tables (LATs), analogous to differential distribution tables, to tabulate one-round biases and bound trail weights; for SPNs, the branch number—defined as the minimum number of active S-boxes in any non-zero input-output mask pair—helps ensure high activity and low maximum correlation across rounds.^[21] These bounds, adapted from differential cryptanalysis, prevent overestimation of trail strength and guide the search toward trails balancing bias and round coverage.^[22]

Recovering key bits

In linear cryptanalysis, recovering key bits begins with a high-bias linear approximation, derived from linear trails spanning multiple rounds, that relates plaintext bits P, ciphertext bits C, and a small number of unknown key bits K' through an equation of the form P \oplus C \oplus K' = 0 with bias \epsilon = |p - 1/2|, where p is the probability of the equation holding.^[14] For partial key recovery involving k key bits, all $2^k possible candidates for K' are enumerated. For a set of N known plaintext-ciphertext pairs, the left-hand side excluding K' (i.e., P \oplus C) is computed for each pair. Then, for each candidate guess \hat{K}', the number of pairs T where P \oplus C \oplus \hat{K}' = 0 is counted; the correct guess yields T closest to N(1/2 + \epsilon) or N(1/2 - \epsilon), depending on the sign of the bias, while incorrect guesses average N/2.^[14] This process, known as Matsui's Algorithm 2, requires N \approx c / \epsilon^2 pairs for high success probability (e.g., over 95%), where c is a small constant depending on the desired confidence, ensuring the correct candidate's deviation |T - N/2| exceeds that of others by several standard deviations (approximately \sqrt{N}/2).^[14] To rank key hypotheses statistically, the deviation |2T/N - 1| serves as an estimate of $2\epsilon, with the candidate maximizing this metric selected as correct; more advanced tests, such as the log-likelihood ratio comparing observed T to binomial expectations under biased versus unbiased hypotheses, can refine ranking but are not essential for the basic method.^[14] The time complexity is O(2^k \cdot N), or O(2^k / \epsilon^2) given the data requirement, as each pair must be evaluated against all guesses.^[14] The recovery proceeds iteratively, starting with the last-round subkey (where approximations are most accurate due to fewer rounds) and peeling backward: once a partial subkey is recovered, it is used to adjust the linear approximation for the prior round, enabling recovery of earlier subkeys sequentially until the full key schedule is covered.^[14] This backward extension leverages the cipher's iterative structure, with each step reusing the same N pairs but updating the approximation. For full key recovery, multiple independent partial approximations are constructed to cover all key bits without overlap, recovering disjoint subkeys in parallel before combining them via the key schedule; if overlaps occur, resolved bits reduce the search space for remaining ones.^[14] The overall data complexity remains O(1/\epsilon^2) dominated by the weakest approximation, while time scales with the largest $2^k partial search. An advanced optimization employs the Fast Fourier Transform (FFT) to accelerate sieving of $2^k candidates: by representing the counting as a convolution over the parity of differences in a circulant matrix derived from the linear expression, the biases for all guesses are computed via three k-dimensional FFTs of size $2^k, reducing time from O(2^k / \epsilon^2) to O(k \cdot 2^k / \epsilon^2).^[23] This is particularly effective when k is moderate (e.g., up to 20–30 bits), as FFT leverages the structure of key addition in Feistel or substitution-permutation networks.^[23]

Applications and Examples

Attack on DES

Linear cryptanalysis was first applied to the Data Encryption Standard (DES) by Mitsuru Matsui in 1993, with theoretical analysis showing its potential as an attack on a widely used block cipher. Matsui described two variants: Type 1, a known-plaintext attack relying on linear sieving, and Type 2, a ciphertext-only attack exploiting non-random plaintext distributions (e.g., English text). Both build on a basic 3-round linear approximation involving specific bits in the DES structure, particularly approximations in S-boxes like S5 with high bias (e.g., 28/64 probability).^[14] The theoretical Type 1 attack on 16-round DES requires approximately $2^{47} known plaintext-ciphertext pairs to recover the full 56-bit key, with time complexity around $2^{47} operations. Type 2, applicable under specific plaintext assumptions, requires fewer data for reduced rounds (e.g., $2^{23} ciphertexts for 8-round DES with random ASCII), but is impractical for the full cipher without plaintext access.^[14] In 1994, Matsui demonstrated the attack's practicality using Algorithm 2 on full 16-round DES, employing a 14-round linear trail with 43 active S-boxes and overall bias of $2^{-22}. This trail targets the last rounds for subkey recovery, with approximations involving plaintext bits, intermediate outputs, and ciphertext bits XORed with subkeys. The piling-up lemma combines individual S-box biases (typically around $2^{-2}) across the trail. The attack iteratively guesses subkeys starting from round 14, verifying candidates with about 20 linear approximations for high success probability.^[24]^[25] The practical attack requires $2^{43} known plaintext-ciphertext pairs, with time complexity of about $2^{43} DES encryptions (including partial decryptions and parity counts), achieving 85% success probability. Key bits are recovered by ranking subkey candidates by bias deviation before brute-forcing remaining bits. This references general key recovery via linear equation deviations, tailored to DES's Feistel structure.^[24]^[26] The attack was experimentally verified in 1994 using standard workstations, processing data over approximately 100 hours with multiple processors, confirming feasibility and breaking full DES faster than brute force. These results highlighted DES vulnerabilities, contributing to NIST's retirement of DES in 2005 due to its insufficient 56-bit key length against statistical attacks.^[25]

Attacks on other block ciphers

Linear cryptanalysis was first applied to block ciphers other than DES shortly after its introduction, targeting early designs such as the Japanese FEAL family. In 1992, Matsui and Yamagishi demonstrated an attack on the 4-round version FEAL-4 using just 5 known plaintext-ciphertext pairs, recovering the full 64-bit key in seconds on contemporary hardware. This result highlighted the vulnerability of FEAL's structure to linear approximations, with similar techniques extended to FEAL-6 requiring about 100 known plaintexts and FEAL-8 needing around $2^{24} plaintexts. During the 1990s, the method was adapted to other Japanese proposals, including variants of CIPHERUN and early iterative ciphers, where linear trails exploited weak S-box biases to achieve key recovery on reduced rounds with data complexities under $2^{30}. Following the success against DES, linear cryptanalysis was evaluated against the Advanced Encryption Standard (AES) during its selection process in the late 1990s and early 2000s. Attacks on reduced-round AES-128 have targeted up to 7 rounds, with one approach requiring approximately $2^{40} known plaintexts to recover key bits via high-probability linear approximations spanning the MixColumns and ShiftRows layers. These attacks leverage the piling-up lemma to combine single-round biases of about $2^{-6} from the S-boxes, but full-round AES resists due to the low overall correlation after 10 rounds. More recent refinements, such as multiple linear approximations, have slightly improved efficiencies for 7-round variants but remain impractical for the full cipher.^[27] In the realm of lightweight block ciphers, linear cryptanalysis has been applied to families like SIMON and SPECK, designed for resource-constrained environments. For SIMON32/64, linear approximations with biases around $2^{-10} enable distinguishers over 11 rounds, allowing key recovery attacks on up to 18 reduced rounds with data complexities of $2^{20} to $2^{30} using Matsui's Algorithm 2.^[28] Similarly, SPECK32/64 exhibits linear trails with comparable biases, supporting attacks on 15 reduced rounds where multiple approximations amplify the signal for subkey guessing.^[29] These results underscore adaptations for ARX-based structures, focusing on modular addition biases rather than traditional S-boxes. A key adaptation in linear cryptanalysis is the multidimensional variant, which employs multiple linearly independent approximations simultaneously to reduce data requirements and improve key-ranking efficiency. In 2011, Cho applied this technique to the lightweight cipher PRESENT, constructing a 26-round distinguisher using $2^{15} approximations with a total correlation capacity equivalent to a single bias of $2^{-63}, enabling a full key recovery attack on 27 reduced rounds with $2^{64} data—far below classical linear needs. This method treats the distribution of linear parities as a multidimensional Gaussian, allowing fast Fourier transforms for optimal linear combinations and has since influenced attacks on other SPN ciphers. Notable applications include attacks on the AES-like cipher Khazad, where linear hulls with non-zero correlations over 6 rounds were combined with differential paths to break 9 out of its 10 rounds in 2004, recovering 80 key bits with $2^{50} data. For Camellia-128, zero-correlation linear cryptanalysis variants target reduced rounds without FL/FL^{-1} layers, achieving key recovery on 10 rounds with about $2^{48} chosen plaintexts by exploiting unbiased hulls over the P-function.^[30] As of November 2025, linear cryptanalysis has not achieved a full break on AES-128, with the best attacks limited to 8 rounds due to the cipher's low S-box biases (maximum $2^{-5}) and wide-trail strategy that dilutes correlations. However, theoretical analyses indicate potential vulnerability if future implementations use S-boxes with higher linear biases exceeding $2^{-4}, as the piling-up lemma would amplify multi-round correlations beyond secure thresholds.^[13]^[31]

Limitations and Defenses

Inherent weaknesses of the attack

Linear cryptanalysis fundamentally depends on the availability of high-bias linear approximations within the substitution boxes (S-boxes) of a block cipher. If all such approximations exhibit a bias |ε| ≤ 2^{-n/2}, where n is the block size, the attack fails because the required number of plaintext-ciphertext pairs would exceed the total possible inputs of 2^n. For randomly generated S-boxes of size 2^r, the expected maximum bias is approximately 2^{-r/2}, rendering the approximations too weak for practical exploitation.^[32]^[32] The data complexity of the attack scales as O(1/ε²), where ε denotes the overall bias of the linear trail, making it highly demanding for approximations with small biases. For instance, the AES S-box has a maximum linear bias of 2^{-4}, and constructing a viable multi-round approximation would necessitate over 2^{40} plaintext-ciphertext pairs, far beyond feasible limits for full-round attacks. Computationally, the time required to recover key bits increases exponentially with the number of subkey bits guessed in partial key recovery steps, limiting the attack's viability against ciphers with key lengths greater than 100 bits.^[14] Structurally, linear cryptanalysis struggles against wide-trail designs, which minimize the bias of low-weight linear trails by enforcing a high minimum number of active S-boxes across multiple rounds. The attack also presumes the Markov property, under which the bias of approximations remains independent of the subkeys; this assumption is invalidated by key-dependent operations, such as rotations, which introduce key-varying mixing. Overall, these inherent limitations confine linear cryptanalysis to effectiveness primarily against 1990s-era block ciphers like DES, while modern designs necessitate hybrid approaches combining it with other cryptanalytic techniques for any meaningful progress.^[4]

Countermeasures in cipher design

To resist linear cryptanalysis, block cipher designers prioritize the selection of substitution boxes (S-boxes) that exhibit low maximum bias in their linear approximations. The bias of an S-box linear approximation is quantified as the absolute deviation from 1/2 in the probability that a linear equation involving input and output bits holds, and low values minimize the correlation exploitable by attackers. For instance, the AES S-box achieves a maximum bias of 1/16, verified through exhaustive computation of its linear approximation table, which lists correlations for all input-output mask pairs.^[33] Diffusion layers are engineered to ensure rapid and thorough mixing of differences or linear relations across the state, thereby reducing the overall bias of multi-round approximations via the piling-up lemma. A key metric is the branch number, which counts the minimum number of active bytes (those involved in non-trivial transformations) in any non-zero input-output pair; high branch numbers force multiple active S-boxes per trail, exponentially attenuating the combined bias. In AES, the MixColumns operation employs a maximum distance separable (MDS) matrix with branch number 5 for its 4-byte columns, ensuring at least 25 active S-boxes over any four-round linear trail and limiting the maximum trail correlation to 2^{-75}.^[33] The key schedule must generate round subkeys that avoid linear dependencies or predictability, as weak schedules can enable key-related linear trails that amplify biases. Designers incorporate non-linear operations, such as S-boxes or modular additions, and round constants to decorrelate subkeys from the master key and across rounds, preventing invariant subspaces or related-key attacks that exploit linear structure. For example, linear key schedules augmented with random round constants achieve variance in key-dependent biases comparable to independent random subkeys, as analyzed in Fourier domain models.^[34] Sufficient round count provides a security margin against linear attacks by extending trails beyond the point where biases become negligible. A common guideline is to use at least 2r + 2 rounds, where r denotes the maximum number of rounds for which a high-bias linear approximation can be constructed; this accounts for one round of key mixing at the start and end, plus an extra for diffusion. In AES-128, 10 rounds were selected based on the wide trail strategy, ensuring no full-round attack is feasible given the four-round trail bounds.^[33] During the AES selection process, the Rijndael design (adopted as AES) highlighted its provable resistance to linear cryptanalysis through the wide trail strategy, balancing low S-box biases with strong diffusion to bound multi-round correlations. Similarly, lightweight ciphers like SIMON employ bit-sliced Feistel structures with arithmetic-rotation-XOR (ARX) operations in the round function, which inherently yield low biases in linear approximations due to the non-linear AND gate and rotations disrupting linear relations.^[33]^[35]

References

[1]
Linear Cryptanalysis Method for DES Cipher - SpringerLink
Jul 13, 2001 · We introduce a new method for cryptanalysis of DES cipher, which is essentially a known-plaintext attack. As a result, it is possible to break 8-round DES ...Missing: original | Show results with:original
[2]
The First Experimental Cryptanalysis of the Data Encryption Standard
The scenario is a known-plaintext attack based on two new linear approximate equations, each of which provides candidates for 13 secret key bits with negligible ...
[3]
[PDF] A Tutorial on Linear and Differential Cryptanalysis - IOActive
Linear cryptanalysis was introduced by Matsui at EUROCRYPT '93 as a theoretical ... Matsui, "The First Experimental Cryptanalysis of the Data Encryption ...
[4]
Multidimensional Linear Cryptanalysis | Journal of Cryptology
Nov 12, 2018 · The multidimensional extension of linear cryptanalysis to be introduced in this paper considers using multiple linear approximations that form a ...
[5]
[PDF] Multivariate Profiling of Hulls for Linear Cryptanalysis
Proposed by Matsui [Mat93, Mat94b] in the early 1990s, linear cryptanalysis has proven to be a seminal cryptanalytic technique for symmetric-key cryptography.
[6]
[PDF] Differential Cryptanalysis in Stream Ciphers
Abstract. In this paper we present a general framework for the appli- cation of the ideas of differential cryptanalysis to stream ciphers. We.
[7]
[PDF] Introduction to Cryptanalysis: Attacking Stream Ciphers
Abstract. This article contains an elementary introduction to the cryptanalysis of stream ciphers. Initially, a few historical examples are given to explain ...
[8]
A New Method for Known Plaintext Attack of FEAL Cipher
May 18, 2001 · About this paper. Cite this paper. Matsui, M., Yamagishi, A. (1993). A New Method for Known Plaintext Attack of FEAL Cipher. In: Rueppel, R.A. ...
[9]
[PDF] 25 Years of Linear Cryptanalysis
Dec 3, 2018 · Induction on the number of rounds: – Computes Bbestr (and the corresponding. a0. ,a1. ,…,ar) assuming Bbest(i) (i=1,…,r-1) is known.
[10]
[PDF] Linear Cryptanalysis Using Multiple Linear Approximations
A natural idea for enhancing linear cryptanalysis is using multiple approxima- tions instead of one. Matsui was the first to suggest this enhancement. In 1994.
[11]
[PDF] Improving Key-Recovery in Linear Attacks: Application to 28-Round ...
Feb 12, 2021 · For multiple and multidimensional linear cryptanalysis, Blondeau et al. have provided estimations of the distributions of the test statistics in ...
[12]
[PDF] Differential and Linear Cryptanalysis in Evaluating AES Candidate
Abstract. Since the introduction of DES in 1977, cryptanalysis methods have been developed and constantly improved to assess the security of encryption ...
[13]
Linear Cryptanalysis Method for DES Cipher
In this paper we introduce an essentially known-plaintext attack of DES cipher. The purpose of this method is to obtain a linear approximate expression of a ...
[14]
[PDF] Linear and Differential Cryptanalysis
Dec 15, 2006 · A linear cryptanalysis is a known plain text attack, against a block cipher. The attack was first described by Matsui in 1994 as an attack ...<|control11|><|separator|>
[15]
[PDF] Linear cryptanalysis method for DES cipher - of Luca Giuzzi
The first aim of this paper is to solve these problems for DES cipher. For this purpose, we begin by studying linear approximations of S-boxes in Chapter 4, and ...Missing: original | Show results with:original
[16]
Probability distributions of Correlation and Differentials in Block ...
Jul 5, 2005 · For Markov ciphers there exists a solid theory that expresses bounds on the complexity of differential and linear cryptanalysis in terms of ...
[17]
[PDF] On Linear Hulls and Trails - Cryptology ePrint Archive
Linear hulls are the counterpart of a differential in linear cryptanalysis, and can form in a single round. Overlooking them may lead to wrong estimations.
[18]
[PDF] Improving Matsui's Search Algorithm for the Best Differential/Linear ...
The algorithm represents the problem of searching multiple differential or linear trails as the problem of finding many long paths through a multistage graph.
[19]
[PDF] Experimenting Linear Cryptanalysis - Université catholique de Louvain
Matsui's original description of the linear cryptanalysis comes with two algo- rithms that allow exploiting linear approximations in iterated block ciphers [36] ...
[20]
[PDF] Chapter 5: Propagation and Correlation
Difference propagation is specifically exploited in differential cryptanalysis (DC), invented by Eli Biham and Adi Shamir [BiSh91]. Input-output correlation is ...
[21]
[PDF] The Wide Trail Design Strategy
The Wide trail strategy is an approach to design the round transformations of block ciphers that combine efficiency and resistance against differential and ...
[22]
[PDF] Improving the Time Complexity of Matsui's Linear Cryptanalysis
Abstract. This paper reports on an improvement of Matsui's linear cryptanalysis that reduces the complexity of an attack with algorithm.<|control11|><|separator|>
[23]
[PDF] Linear Cryptanalysis of DES - Pascal Junod
The main goal of this diploma work is the implementation of Matsui's linear cryptanalysis of DES and a statistical and theoretical analysis of its com-.
[24]
[PDF] On the Complexity of Matsui's Attack - Cryptology ePrint Archive
Linear cryptanalysis remains the most powerful attack against. DES at this time. Given 243 known plaintext-ciphertext pairs, Matsui ex- pected a complexity of ...Missing: details | Show results with:details
[25]
Improved Key Recovery Attacks on Reduced-Round AES with ...
Sep 26, 2019 · In particular, our attack on 7-round AES with 192-bit keys requires 2^{26} data, 2^{32} memory and 2^{153} time, which outperforms the Square ...
[26]
Linear Cryptanalysis of Round Reduced SIMON
Oct 24, 2013 · In this paper we analyze the security of SIMON against linear cryptanalysis. We present several linear characteristics for all variants of SIMON ...Missing: Khazad | Show results with:Khazad
[27]
[PDF] Linear Cryptanalysis of Reduced-Round Speck - COSIC - KU Leuven
We illustrate that linear approximations with high bias exist in variants of Speck. 1 Introduction. A recent surge of new block cipher designs has urged the ...
[28]
[PDF] Improved Zero-Correlation Linear Cryptanalysis of Reduced-round ...
Although our attacks require certain conditions for. 15 subkey bits, they improve the existing cryptanalytic results on Camellia-192/256 with. F L/F L−1 and ...<|control11|><|separator|>
[29]
[PDF] Linear Cryptanalysis Using Low-bias Linear Approximations
This paper deals with linear approximations having absolute bias smaller than 2− n. 2 which were previously believed to be unusable for a linear attack. We ...
[30]
[PDF] Security of the AES with a Secret S-box - Cryptology ePrint Archive
Replacing AES's S-box with a secret one increases security, but integral cryptanalysis can recover the key and S-box in 4-6 rounds.
[31]
[PDF] The Rijndael Block Cipher - NIST Computer Security Resource Center
• Choose an S-box where the maximum prop ratio and the maximum input-output correlation are as small as possible. For the Rijndael S-box this is respectively 2.
[32]
[PDF] Linear Cryptanalysis: Key Schedules and Tweakable Block Ciphers
Abstract. This paper serves as a systematization of knowledge of linear cryptanalysis and provides novel insights in the areas of key schedule design and ...
[33]
None
### Summary on Simon Cipher: Resistance to Linear Cryptanalysis and Design Choices for Low Bias