Linear Cryptanalysis
Also known as: linear attack, linear approximation, piling-up lemma
Linear cryptanalysis is a known-plaintext attack that exploits linear approximations of a cipher's non-linear transformations to recover secret key bits. Introduced by Mitsuru Matsui in 1993, linear cryptanalysis provides practical attacks on ciphers like DES with computational complexity less than brute force. The technique analyzes statistical biases in how linear combinations of plaintext and ciphertext bits relate to key bits, enabling key recovery with reduced data requirements.
Key highlights
- Practical attack on DES requiring 2^43 plaintext-ciphertext pairs and 2^39 operations
- Well-formalized mathematical framework (piling-up lemma) for analyzing approximation biases
- Complements differential cryptanalysis, finding weaknesses differential analysis might miss
- Shapes cipher design requirements for S-box selection and round transformation
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Linear cryptanalysis is used in cryptanalysis research and cipher design evaluation. It guides cipher designers in selecting S-boxes and transformations that resist linear approximations. Modern ciphers are designed with proven bounds on linear approximation strength.
Strengths & limitations
- Practical attack on DES requiring 2^43 plaintext-ciphertext pairs and 2^39 operations
- Well-formalized mathematical framework (piling-up lemma) for analyzing approximation biases
- Complements differential cryptanalysis, finding weaknesses differential analysis might miss
- Shapes cipher design requirements for S-box selection and round transformation
- Modern ciphers (AES) are carefully designed to resist linear cryptanalysis with provable bounds
- Requires known plaintext-ciphertext pairs, which may not be available in all scenarios
- Computational and data requirements can exceed practical feasibility for well-designed ciphers
- Discovering strong linear approximations for modern ciphers is extremely difficult
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
What is the piling-up lemma?
The piling-up lemma provides a method for computing the bias of linear approximations across multiple rounds by combining biases of individual round approximations. It is foundational to linear cryptanalysis.
How does AES resist linear cryptanalysis?
AES uses S-boxes chosen to minimize maximum linear approximation probability and a diffusion layer ensuring fast diffusion of linear biases across rounds. Proven bounds guarantee no practical linear approximations.
What is the difference between linear and differential cryptanalysis?
Differential analysis studies input-output differences, while linear analysis studies linear approximations (XOR of plaintext and ciphertext bits). Both exploit structural weaknesses in ciphers.
Can linear cryptanalysis break modern ciphers?
Not practically. Modern ciphers like AES have provable bounds on linear approximations making attacks computationally infeasible.
How do I evaluate linear resistance in my cipher design?
Analyze S-box linear approximation tables and compute maximum bias through rounds using the piling-up lemma. Ensure maximum bias is negligible across all possible linear approximations.
Sources
- 1.Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.
- 2.Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Linear Cryptanalysis. ScholarGate. https://scholargate.app/cryptography/linear-cryptanalysis