Lawineneffekt (Kryptographie)
Als Lawineneffekt (auch Avalanche-Effekt[1], von englisch avalanche, Lawine) bezeichnet man in der Kryptographie die Eigenschaft eines Algorithmus, bei einer minimalen Änderung der Eingabe eine völlig andere Ausgabe zu erzeugen.[2] 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.
Strict Avalanche Criterion Bearbeiten
Das Strict Avalanche Criterion (SAC, engl. „strenges Lawinenkriterium“) ist eine Formalisierung des Lawineneffekts, die 1985 von Webster and Tavares eingeführt wurde.[3] Dieses Kriterium verlangt, dass sich bei einer Änderung eines Eingabebits jedes Bit der Ausgabe mit einer Wahrscheinlichkeit von 50 % ändert. Die Erfüllung des SAC ist heutzutage eine Standardforderung für kryptographische Systeme, es wurde beispielsweise von allen Finalisten des AES-Wettbewerbs erfüllt.[4]
Beispiele Bearbeiten
Nachfolgend werden Beispiele kryptographischer Ansätze gegeben und deren Lawineneffekt eingeschätzt.
SHA-1 Bearbeiten
Der SHA-1-Prüfsummenalgorithmus zeigt einen starken Lawineneffekt.
Demonstration durch beispielhafte Erzeugung zweier SHA-1-Prüfsummen (160 Bit) und deren Vergleich:
Eingabe: aaaaaaaaaaaaaaa Ausgabe: 7e13c003 a8256cd4 21055563 c5da6571 d50713c9 Eingabe: aaaaaaaaaaaaaab Ausgabe: da5f09bc 23d63778 ebf88521 ac5df8aa 2f7298ce
Anzahl der unterschiedlichen Bits (Hamming-Distanz): 89
Quote in diesem Beispiel: 55,6 % Bitdifferenz.
Beide Ausgaben sind trotz minimal unterschiedlicher Eingaben erheblich verschieden.
AES Bearbeiten
Der AES-Verschlüsselungsalgorithmus zeigt einen starken Lawineneffekt.
Verschlüsselung von 128-Bit-Wörtern durch AES: In beiden Fällen wird AES-256 im Electronic Code Book Mode mit dem alternierenden Schlüssel 010101…01 verwendet.
Eingabe: aaaaaaaaaaaaaaaa Ausgabe: 0a561d9e 30bb09db 47f8e83d 443865cf Eingabe: aaaaaaaaaaaaaaab Ausgabe: c1e768d3 9177e9ef debee33a b92b4450
Anzahl der unterschiedlichen Bits (Hamming-Distanz): 62
Quote in diesem Beispiel: 48,4 % Bitdifferenz.
Beide Ausgaben sind trotz minimal unterschiedlicher Eingaben erheblich verschieden.
Monoalphabetische Substitution Bearbeiten
Eine Verschlüsselung durch monoalphabetische Substitution zeigt keinen Lawineneffekt.
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.
Einzelnachweise Bearbeiten
- ↑ Symmetrische Blockchiffren. TU Dresden, abgerufen am 31. März 2024.
- ↑ Wolfgang Ertel: Angewandte Kryptographie. Hanser Verlag, 2007, ISBN 9783446411951, S. 66.
- ↑ 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).
- ↑ James Nechvatal et al.: Report on the Development of the Advanced Encryption Standard (AES). NIST, 2000, S. 27 (PDF).