Skip to content
Back to search results

Linear Cryptanalysis

Introduced by
Mitsuru Matsui
Year
1993
Type
linear approximation attack
Family
Cryptanalytic technique
Font size

What does it do?

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.

The intuition behind the method

Linear cryptanalysis finds linear equations relating plaintext bits, ciphertext bits, and key bits. Due to non-perfect mixing in cipher rounds, these linear equations hold with probability slightly better than random. By collecting many plaintext-ciphertext pairs and observing which key values make these equations hold more often, the attacker can narrow down the correct key.

History

Linear cryptanalysis was introduced by Matsui in 1993 as a known-plaintext attack on DES. In 1994, Matsui demonstrated the first experimental cryptanalysis of the DES standard using linear cryptanalysis, recovering a key with 2^43 known plaintexts. This breakthrough demonstrated practical attacks against a deployed standard and influenced the development of AES with proven resistance bounds.

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.

Limitations and considerations

  • 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

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • 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

Applications

  • Cryptanalysis of block ciphers evaluating security properties in research and standardization
  • Cipher design and S-box selection to ensure adequate linear approximation bounds
  • Cryptographic standards validation (NIST, ETSI) requiring linear resistance analysis
  • Legacy cipher assessment for retirement and replacement decisions

How it works

How it works

1

Find linear approximations: linear relationships between plaintext bits, ciphertext bits, and key bits that hold with probability significantly different from 0.5.

2

Estimate the bias (deviation from 0.5) of each linear approximation using statistical analysis of round transformations.

3

For candidate key values, count how often the linear approximation holds in known plaintext-ciphertext pairs. The correct key makes the approximation hold most frequently.

4

Verify recovered key bits by decrypting ciphertext and checking correctness.

Common pitfalls

  • Assuming all linear approximations are exploitable; weak approximations provide minimal advantage
  • Underestimating practical attack difficulty when theoretical data requirements seem reasonable
  • Neglecting interaction between linear and differential properties in cipher analysis

Frequently asked questions

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.

Related methods

Sources

  1. Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.

    Open DOI reference
    Copied.
  2. Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.

    Open DOI reference
    Copied.