Linear cryptanalysis

Linear cryptanalysis is a statistical attack technique against block ciphers that approximates nonlinear components — particularly the substitution boxes (S-boxes) of a Substitution-permutation network — with linear functions, then exploits the resulting statistical bias to deduce information about the secret key. Developed by Mitsuru Matsui in 1993, it was the first published attack capable of breaking the Data Encryption Standard (DES) faster than brute force, requiring roughly 2^43 known plaintexts. The attack reveals a fundamental vulnerability in ciphers whose nonlinear operations are only weakly nonlinear: if an S-box can be approximated by a linear function with probability significantly different from 0.5, the cipher leaks key information through statistical correlations. Modern cipher design, including AES, explicitly optimizes S-boxes to maximize resistance to linear cryptanalysis by minimizing the largest linear bias of any approximation. The technique demonstrates that security in cryptography is not merely about avoiding obvious structural flaws but about controlling the statistical properties of every primitive component.