Lineare Approximation
Eine Beziehung zwischen Eingabe- und Ausgabebits, die etwas häufiger gilt, als der Zufall erwarten ließe.
Eine lineare Approximation einer S-Box oder einer ganzen Chiffre besagt, dass das XOR bestimmter Eingabebits dem XOR bestimmter Ausgabebits entspricht – und zwar mit einer Wahrscheinlichkeit, die leicht von einem Halb abweicht. Diese Abweichung ist der Bias, und ihn misst ein linearer Angriff. Mit genügend bekannten Klartext-Chiffrat-Paaren zählt der Angreifer, wie oft die Beziehung gilt, und schließt daraus auf Schlüsselbits.
S-Box-Entwickler bestimmen den größten Bias der Tabelle, die sogenannte Linearität, und versuchen, ihn niedrig zu halten. Ist keine Approximation stark genug, um sie billig auszunutzen, hat die S-Box diese Prüfung bestanden.