Lawineneffekt (Kryptographie)

Als Lawineneffekt bezeichnet man in der Kryptographie die Eigenschaft eines Algorithmus, bei einer minimalen Änderung der Eingabe eine völlig andere Ausgabe zu erzeugen.^[1] Diese Eigenschaft ist eine Formalisierung der Forderung, dass bei einer Blockchiffre oder kryptologischen Hashfunktion jedes Bit der Ausgabe von der ganzen Eingabe abhängen soll. Dadurch bewirkt der Lawineneffekt eine gute Diffusion.

Das Strict Avalanche Criterion (SAC, deutsch: strenges Lawinenkriterium) ist eine Formalisierung des Lawineneffekts, die 1985 von Webster and Tavares eingeführt wurde.^[2] Das Kriterium verlangt, dass sich bei einer Änderung eines Eingabebits jedes Bit der Ausgabe mit einer Wahrscheinlichkeit von 50 % ändert. Das strenge Lawinenkriterium ist heutzutage eine Standardforderung für kryptographische Systeme, es wurde bspw. von allen Finalisten des AES-Wettbewerbs erfüllt.^[3]

Erzeugung einer SHA-1-Prüfsumme:

 Eingabe: aaaaaaaaaaaaaaa
 Ausgabe: 7e13c003a8256cd421055563c5da6571d50713c9

 Eingabe: aaaaaaaaaaaaaab
 Ausgabe: da5f09bc23d63778ebf88521ac5df8aa2f7298ce

Beide Ausgaben sind trotz mimimal unterschiedlicher Eingaben völlig verschieden, was auf einen starken Lawineneffekt bei SHA-1 hindeutet.

Verschlüsselung durch AES: In beiden Fällen wird AES-256 im Electronic Code Book Mode mit dem Schlüssel 010101…01 verwendet.

 Eingabe: aaaaaaaaaaaaaaaa
 Ausgabe: 0a561d9e30bb09db47f8e83d443865cf

 Eingabe: aaaaaaaaaaaaaaab
 Ausgabe: c1e768d39177e9efdebee33ab92b4450

Beide Ausgaben sind trotz mimimal unterschiedlicher Eingaben völlig verschieden, was auf dem starken Lawineneffekt bei AES beruht.

Verschlüsselung durch monoalphabetische Substitution: In beiden Fällen wird folgender Auszug einer Substitutionstabelle verwendet: a --> r; b --> z

 Eingabe: aaaaaaaaaaaaaaa
 Ausgabe: rrrrrrrrrrrrrrr

 Eingabe: aaaaaaaaaaaaaab
 Ausgabe: rrrrrrrrrrrrrrz

Beide Ausgaben sind nahezu identisch, was zeigt, dass es bei der monoalphabetischen Substitution keinen Lawineneffekt gibt.

1. ↑ Wolfgang Ertel: Angewandte Kryptographie. Hanser Verlag, 2007, ISBN 9783446411951, S. 66.
2. ↑ A. F. Webster, Stafford E. Tavares: On the design of S-boxes. In: Advances in Cryptology - Crypto '85 (= Lecture Notes in Computer Science). Band 218. Springer, 1985, S. 523–534 (PDF). 
3. ↑ James Nechvatal et al.: Report on the Development of the Advanced Encryption Standard (AES). NIST, 2000, S. 27 (PDF).