Lawineneffekt (Kryptographie)

Autor: Leandro Alegsa

03-11-2020

Der Lawineneffekt ("Erdrutscheffekt") ist eine Eigenschaft von Blockchiffrierungen und kryptographischen Hash-Funktions-Algorithmen. Er ist in der Kryptographie oft erwünscht. Der Effekt besagt, dass sich ein großer Teil der Ausgabe ändern muss, auch wenn sich die Eingabe nur wenig ändert. Bei guten Blockchiffrierungen bedeutet das: Eine kleine Änderung des Schlüssels oder des Klartextes sollte eine starke Veränderung des Chiffriertextes bewirken.

Das bedeutet, dass sich kleine Änderungen schnell ausbreiten können, wenn der Algorithmus Iterationen verwendet. Daher hängt jedes Bit der Ausgabe von jedem Bit der Eingabe ab.

Der Begriff Lawineneffekt wurde erstmals von Horst Feistel verwendet (Feistel 1973). Später wurde der Begriff durch Shannons Eigenschaft der Verwirrung identifiziert.

Wenn eine Blockchiffrierung oder kryptographische Hashfunktion den Lawineneffekt nicht in signifikantem Maße befriedigt, hat sie eine schlechte Randomisierung. So kann ein Kryptoanalytiker Vorhersagen über die Eingabe machen, wenn er nur die Ausgabe erhält. Dies kann ausreichend sein, um den Algorithmus teilweise oder vollständig zu brechen (zu knacken).

Es ist eines der primären Designziele, wenn Menschen eine starke Chiffre oder kryptographische Hash-Funktion erstellen. Sie versuchen, darin einen guten Lawineneffekt aufzubauen. Mathematisch gesehen wird dabei der Schmetterlingseffekt genutzt. Aus diesem Grund sind die meisten Blockchiffrierungen Produktchiffrierungen. Das ist auch der Grund, warum Hash-Funktionen große Datenblöcke haben.

Die SHA1-Hashfunktion hat eine gute Lawinenwirkung. Wenn ein einzelnes Bit geändert wird, wird die Hash-Summe völlig anders.

Name

Der Ursprung des Namens sind Erdrutsche. Ein kleiner Stein kann herunterfallen, mit etwas Schnee mitgehen und einen zerstörerischen Erdrutsch verursachen. Der Fels war klein, konnte aber viele Zerstörungen verursachen. Das ist das Gleiche wie das, was diese Auswirkungen haben. Eine kleine Änderung im Input (dem Felsen) sollte den Output (die Landschaft) verändern.

Strenge Lawinen-Kriterien

Das Strenge Lawinenkriterium (SAC; ein "starkes Erdrutschkriterium") ist eine Eigenschaft boolescher Funktionen. Es ist für die Kryptographie von Bedeutung. Es ist erfüllt, wenn sich alle Ausgangsbits mit einer Wahrscheinlichkeit von 50 Prozent ändern, wenn ein einzelnes Eingangsbit geändert wird.

Der SAC wurde auf den Konzepten der Vollständigkeit der Evolution und der Lawine aufgebaut. Er wurde 1985 von Webster und Tavares eingeführt. Heutzutage ist es eine Voraussetzung für jedes moderne kryptographische System. Er wurde z.B. von allen Finalisten des AES-Wettbewerbs erfüllt.

Bit-Unabhängigkeitskriterium

Das Bit-Unabhängigkeitskriterium (BIC; ein vom Bit unabhängiges Kriterium) ist ein Kriterium. Es geht: Wenn ein einzelnes Eingangsbit geändert (invertiert) wird, sollten sich zwei Ausgangsbits unabhängig voneinander ändern. Dies gilt für alle Bits.

Es wäre z.B. nicht zufriedenstellend, wenn sich nur das eine Ausgabebit ändert, wenn sich auch das andere Ausgabebit ändert. Sie könnten sich nur ändern, weil sich das Eingangsbit ändert. Andernfalls würden die Ausgangsbits voneinander abhängen.

Fragen und Antworten

F: Was ist der Lawineneffekt?

A: Der Lawineneffekt (auch "Erdrutscheffekt" genannt) ist eine Eigenschaft von Blockchiffren und kryptographischen Hash-Funktionsalgorithmen, die besagt, dass eine kleine Änderung des Schlüssels oder des Klartextes eine starke Änderung des Chiffretextes bewirken sollte.

F: Wer hat den Begriff "Avalanche-Effekt" zuerst verwendet?

A: Der Begriff Avalanche-Effekt wurde erstmals von Horst Feistel im Jahr 1973 verwendet.

F: Wie hängt er mit der Shannonschen Eigenschaft der Verwirrung zusammen?

A: Das Konzept des Avalanche-Effekts wurde durch die Shannon'sche Konfusionseigenschaft identifiziert, die besagt, dass eine Blockchiffre oder kryptografische Hash-Funktion, die diesen Grad nicht in signifikantem Maße erfüllt, eine schlechte Randomisierung aufweist und teilweise oder vollständig gebrochen (geknackt) werden kann.

F: Welche Ziele werden bei der Entwicklung von starken Chiffrierungen verfolgt?

A: Wenn Menschen starke Chiffren entwickeln, versuchen sie, einen guten Lawineneffekt in sie einzubauen, indem sie mathematische Prinzipien wie den Schmetterlingseffekt anwenden. Das ist der Grund, warum die meisten Blockchiffren Produktchiffren sind und warum Hash-Funktionen große Datenblöcke haben.

F: Was passiert, wenn ein Algorithmus den Avalanche-Effekt nicht erfüllt?

A: Wenn ein Algorithmus den Avalanche-Effekt nicht in signifikantem Maße erfüllt, weist er eine schlechte Randomisierung auf und kann von Kryptoanalytikern, die Vorhersagen über die Eingabe auf der Grundlage nur der gegebenen Ausgabe machen können, teilweise oder vollständig geknackt werden.

F: Warum verwenden die meisten Blockchiffren Produktchiffren?

A: Die meisten Blockchiffren verwenden Produktchiffren, weil sie mit Hilfe mathematischer Prinzipien wie dem Schmetterlingseffekt gute Avalance-Effekte in sie einbauen.

F: Warum haben Hash-Funktionen große Datenblöcke?

A: Hash-Funktionen haben große Datenblöcke, weil sie mit Hilfe mathematischer Prinzipien wie dem Schmetterlingseffekt gute Avalance-Effekte erzeugen.