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 | Quelltext 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 | Quelltext bearbeiten]Nachfolgend werden Beispiele kryptographischer Ansätze gegeben und deren Lawineneffekt eingeschätzt.
SHA-1
[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext 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).