Linear Cryptanalysis & Approximation Tables

Linear cryptanalysis (Matsui, 1993) is a known-plaintext attack that finds linear approximations (XOR of specific bits) of a cipher that hold with probability p ≠ 1/2. Using many plaintext-ciphertext pairs, statistical bias reveals key bits.

A linear approximation for an S-box: sum of selected input bits XOR sum of selected output bits = 0 (mod 2) with probability p. Expressed as: P[a·x XOR b·y = 0] = 1/2 + ε, where a,b are bit masks and ε is the bias (|ε| >> 0 is desirable).