Verwirrung und Verbreitung - Confusion and diffusion

In der Kryptographie sind Verwirrung und Diffusion zwei Eigenschaften des Betriebs einer sicheren Verschlüsselung, die von Claude Shannon in seinem 1945 klassifizierten Bericht A Mathematical Theory of Cryptography identifiziert wurde . Diese Eigenschaften, falls vorhanden, verhindern die Anwendung von Statistiken und anderen Methoden der Kryptoanalyse .

Diese Konzepte sind auch beim Entwurf robuster Hashfunktionen und Pseudozufallszahlengeneratoren wichtig, bei denen die Dekorrelation der erzeugten Werte von größter Bedeutung ist.

Definition

Verwechslung

Verwirrung bedeutet, dass jede binäre Ziffer (Bit) des Geheimtextes von mehreren Teilen des Schlüssels abhängen sollte, wodurch die Verbindungen zwischen den beiden verschleiert werden.

Die Eigenschaft der Verwirrung verbirgt die Beziehung zwischen dem Geheimtext und dem Schlüssel.

Diese Eigenschaft macht es schwierig, den Schlüssel aus dem Geheimtext zu finden, und wenn ein einzelnes Bit in einem Schlüssel geändert wird, wird die Berechnung der meisten oder aller Bits im Geheimtext beeinflusst.

Verwirrung erhöht die Mehrdeutigkeit von Geheimtext und wird sowohl von Block- als auch von Stromchiffren verwendet.

In Substitutions-Permutationsnetzwerken sorgen Substitutionsboxen für Verwirrung .

Diffusion

Diffusion bedeutet, dass, wenn wir ein einzelnes Bit des Klartextes ändern, sich etwa die Hälfte der Bits im Geheimtext ändern sollte, und ähnlich sollte sich etwa die Hälfte der Klartext-Bits ändern, wenn wir ein Bit des Geheimtexts ändern. Dies entspricht der Erwartung, dass Verschlüsselungsverfahren einen Lawineneffekt aufweisen .

Der Zweck der Verbreitung besteht darin, die statistische Beziehung zwischen dem Geheimtext und dem Klartext zu verbergen. Zum Beispiel stellt die Diffusion sicher, dass irgendwelche Muster im Klartext, wie etwa redundante Bits, im Geheimtext nicht sichtbar sind. Blockchiffren erreichen dies, indem sie die Informationen über die Struktur des Klartextes über die Zeilen und Spalten der Chiffre "verbreiten".

In Substitutions-Permutationsnetzwerken wird die Diffusion durch Permutationsboxen bereitgestellt .

Theorie

In Shannons ursprünglichen Definitionen bezieht sich Verwirrung darauf, die Beziehung zwischen dem Chiffretext und dem symmetrischen Schlüssel so komplex und kompliziert wie möglich zu gestalten; Diffusion bezieht sich auf die Verteilung der statistischen Struktur des Klartextes über den Großteil des Geheimtextes . Diese Komplexität wird im Allgemeinen durch eine wohldefinierte und wiederholbare Reihe von Substitutionen und Permutationen implementiert . Substitution bezieht sich auf das Ersetzen bestimmter Komponenten (normalerweise Bits) durch andere Komponenten nach bestimmten Regeln. Permutation bezieht sich auf die Manipulation der Reihenfolge von Bits gemäß einem Algorithmus. Um effektiv zu sein, muss jede Ungleichmäßigkeit von Klartextbits über viel größere Strukturen im Chiffretext neu verteilt werden, wodurch diese Ungleichmäßigkeit viel schwieriger zu erkennen ist.

Insbesondere sollte für einen zufällig gewählten Eingang, wenn man das i- te Bit umdreht, die Wahrscheinlichkeit, dass sich das j- te Ausgangsbit ändert, für jedes i und j die Hälfte betragen – dies wird als das strenge Lawinenkriterium bezeichnet . Allgemeiner kann man verlangen, dass das Flippen eines festen Satzes von Bits jedes Ausgangsbit mit einer Wahrscheinlichkeit von der Hälfte ändern sollte.

Ein Ziel der Verwirrung besteht darin, es sehr schwer zu machen, den Schlüssel zu finden, selbst wenn eine große Anzahl von Klartext-Geheimtext-Paaren mit demselben Schlüssel erzeugt wurde. Daher sollte jedes Bit des Chiffretexts vom gesamten Schlüssel und auf unterschiedliche Weise von verschiedenen Bits des Schlüssels abhängen. Insbesondere die Änderung eines Bits des Schlüssels sollte den Geheimtext vollständig ändern. Der einfachste Weg, sowohl Diffusion als auch Verwirrung zu erreichen, besteht darin, ein Substitutions-Permutations-Netzwerk zu verwenden . In diesen Systemen spielen der Klartext und der Schlüssel oft eine sehr ähnliche Rolle bei der Produktion der Ausgabe, daher sorgt der gleiche Mechanismus sowohl für die Verbreitung als auch für die Verwirrung.

Angewendet auf Verschlüsselung

Beim Entwerfen einer Verschlüsselungsmethode werden sowohl die Prinzipien der Verwirrung als auch der Diffusion verwendet. Verwirrung bedeutet, dass der Prozess Daten von der Eingabe in die Ausgabe drastisch ändert, beispielsweise indem die Daten durch eine nichtlineare Tabelle übersetzt werden, die aus dem Schlüssel erstellt wurde. Es gibt viele Möglichkeiten, lineare Berechnungen umzukehren. Je nichtlinearer sie also sind, desto mehr Analysewerkzeuge werden zerstört.

Diffusion bedeutet, dass die Änderung eines einzelnen Zeichens der Eingabe viele Zeichen der Ausgabe ändert. Gut gemacht, wirkt sich jeder Teil der Eingabe auf jeden Teil der Ausgabe aus, was die Analyse viel schwieriger macht. Kein Diffusionsprozess ist perfekt: er lässt immer einige Muster durch. Eine gute Diffusion streut diese Muster weit über die Ausgabe, und wenn mehrere Muster durchkommen, verwürfeln sie sich gegenseitig. Dadurch sind Muster erheblich schwerer zu erkennen und die Datenmenge, die analysiert werden muss, um die Chiffre zu knacken, wird erheblich erhöht.

Analyse von AES

Der Advanced Encryption Standard (AES) hat sowohl eine ausgezeichnete Verwirrung als auch eine ausgezeichnete Verbreitung. Seine Verwirrungs-Nachschlagetabellen sind sehr nichtlinear und gut darin, Muster zu zerstören. Seine Diffusionsstufe verteilt jeden Teil der Eingabe auf jeden Teil der Ausgabe: Die Änderung eines Eingabebits ändert im Durchschnitt die Hälfte der Ausgabebits. Sowohl Verwirrung als auch Diffusion werden für jede Eingabe mehrmals wiederholt, um die Menge an Verwürfelung zu erhöhen. Der geheime Schlüssel wird in jeder Phase eingemischt, sodass ein Angreifer nicht vorausberechnen kann, was die Chiffre tut.

Nichts davon passiert, wenn ein einfaches einstufiges Scramble auf einem Schlüssel basiert. Eingabemuster würden direkt zur Ausgabe durchfließen. Es mag für das Auge zufällig erscheinen, aber die Analyse würde offensichtliche Muster finden und die Chiffre könnte gebrochen werden.

Siehe auch

Verweise

zitierte Werke