Linear Cryptanalysis
Linear cryptanalysis, introduced by Matsui, exploits the bias of linear approximations of S-boxes to build linear relations among plaintext, ciphertext, and key bits for key recovery.
Purpose
It evaluates a block cipher’s resistance to linear approximation, one of the main design drivers for S-boxes and round counts.
Mechanism
High-probability linear approximation paths are traced through the S-boxes of each round, biases accumulate (piling-up lemma), and a linear equation over plaintext, ciphertext, and key bits is solved with many known plaintext-ciphertext pairs to recover key bits.
Use cases
- Linear attack assessment of DES
- Linearity design of the AES S-box
- Block-cipher security analysis