Mohammad Razzaghi - Linear Cryptanalysis

Theory Overview (Stinson)

Goal: Find a linear approximation for the S-box where the XOR sum of specific input bits (selected by mask α) equals the XOR sum of specific output bits (selected by mask β) with high probability.

Equation: (α ⋅ x) ⊕ (β ⋅ S[x]) = 0

x: The input integer to the S-box.
S[x]: The output integer from the S-box.
α (Alpha): Input Mask. Selects which bits of input x to check.
β (Beta): Output Mask. Selects which bits of output S[x] to check.
⊕ (XOR): Addition modulo 2.

Bias Calculation: For each pair (α, β), we check all possible inputs x. If the equation holds, it's a "Match".
Bias = (Number of Matches) - (Total Inputs / 2).
Values covering the "Linear Approximation Table" below are these Biases. High magnitude values (e.g. +/- 6 or 8) indicate a weakness.

S-Box Configuration (Comma separated integers)

Example 4x4 S-box from Stinson's Cryptography (Heys tutorial). Good for demonstrating high bias (-6).

Linear S-box ($S[x]=x$). Results in perfect bias (+8) on diagonal.

Sample row from AES S-box (highly non-linear, low bias).

Linear Approximation Table (LAT)

Click on any cell to see the step-by-step verification logic.

Theory Overview (Stinson)

Linear Approximation Table (LAT)

Step-by-Step Detail