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

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

Nachfolgend werden Beispiele kryptographischer Ansätze gegeben und deren Lawineneffekt eingeschätzt.

SHA-1

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

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

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
  1. Symmetrische Blockchiffren. TU Dresden, abgerufen am 31. März 2024.
  2. Wolfgang Ertel: Angewandte Kryptographie. Hanser Verlag, 2007, ISBN 9783446411951, S. 66.
  3. 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).
  4. James Nechvatal et al.: Report on the Development of the Advanced Encryption Standard (AES). NIST, 2000, S. 27 (PDF).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.