Konfusion (Kryptologie)

Kernidee und Bedeutung

Konfusion ist in der Kryptologie eines der beiden zentralen Prinzipien zur Verschleierung von Strukturen eines Klartextes bei der Verschlüsselung oder beim Hashen. Das zweite Prinzip ist die Diffusion. Konfusion soll die Beziehung zwischen Klartext, Schlüssel und Geheimtext verbergen. Dazu verwendet ein kryptografisches Verfahren nichtlineare Operationen bei der Berechnung des Geheimtextes.

Das Ziel ist, dass zwischen dem Klartext, dem Schlüssel und dem daraus erzeugten Geheimtext keine erkennbare Beziehung besteht. Dadurch wird die statistische Kryptoanalyse erschwert. Ist etwa eine Beziehung zwischen Schlüssel und Geheimtext sichtbar, kann ein Angreifer möglicherweise auf den Schlüssel schließen. Besteht eine direkte Beziehung zwischen Klartext und Geheimtext, können sich aus dem Geheimtext unter Umständen Informationen über den Klartext ableiten lassen, ohne den Schlüssel zu bestimmen.

Ein Gegenbeispiel ist die monoalphabetische Substitution. Sie übernimmt die Buchstabenhäufigkeiten des Klartextes in den Geheimtext. Der Schlüssel verändert die Häufigkeitsverteilung daher nicht wesentlich, sodass das Verfahren durch Häufigkeitsanalyse angegriffen werden kann.

Nichtlinearität als Grundlage

Für Konfusion muss ein kryptografisches Verfahren nichtlineare Operationen enthalten. Eine Abbildung der Eingabebits, also der Klartext- und Schlüsselbits, auf ein Ausgabebit des Geheimtextes wird als f:{0,1}^n → {0,1} definiert. Sie ist linear, wenn sich das Ergebnis ausschließlich durch Additionen im Körper GF(2), also durch XOR-Verknüpfungen der Eingabebits und gegebenenfalls durch Negieren des Resultats, berechnen lässt. Das Ergebnis kann dann als Polynom vom Grad 1 in den Eingabebits ausgedrückt werden.

Es wäre deshalb unsicher, Geheimtextbits nur durch XOR von Klartext- und Schlüsselbits zu berechnen. Ein solches Verfahren wäre vollständig linear. Bei einem Angriff mit bekanntem Klartext könnte der Schlüssel leicht ermittelt werden.

Kryptografische Verfahren bestehen meist aus mehreren gleich oder ähnlich aufgebauten Runden. Jede Runde wendet eine Rundenfunktion auf einen Datenblock an. Diese Funktion enthält nichtlineare Operationen und sorgt zusätzlich für Diffusion. Mit jeder weiteren Runde verstärkt sich die Konfusion: Der Grad des einfachsten Polynoms, mit dem sich die Eingabebits auf ein Ergebnisbit abbilden lassen, steigt. Nach einigen Runden hängt insbesondere jedes berechnete Bit auf nichtlineare Weise von allen Eingabebits ab. Eine ausreichende Rundenzahl kann das Verfahren dadurch so komplex machen, dass es kryptografisch sicher ist.

Praktische Verfahren

Ein wichtiges kryptografisches Primitiv ist die Addition zweier Datenwörter modulo 2^e. Dabei bezeichnet e die Anzahl der Bits eines Datenworts. Diese Addition ist nichtlinear, weil bei der Addition zweier Bits das Übertragbit durch eine UND-Verknüpfung der Eingabebits berechnet wird. Eine UND-Verknüpfung entspricht einer Multiplikation in GF(2).

In vielen modernen Verfahren ist die Wortaddition die einzige nichtlineare Operation. Sie wird häufig mit bitweisem XOR kombiniert. Die abwechselnde Anwendung von Addition und XOR ist kryptografisch wirksamer als die Addition allein. Blockchiffren, die für die Konfusion nur Addition und XOR verwenden, sind FEAL, TEA, XTEA und Threefish.

Verfahren, die ausschließlich aus Addition, Rotation von Datenwörtern und XOR bestehen, heißen ARX-Chiffren. Die Bezeichnung leitet sich von den Anfangsbuchstaben dieser drei Operationen ab: Addition, Rotation und XOR.

Eine weitere wichtige Komponente sind S-Boxen. Das sind Bauelemente von Rundenfunktionen, bei denen die Ausgabebits gezielt von den Eingabebits abhängig gemacht werden. Bei geeigneter Konstruktion erzeugen S-Boxen eine stark nichtlineare Beziehung und eignen sich deshalb besonders zur Erzeugung von Konfusion.

Beispiel DES und Zusammenspiel mit Diffusion

DES verwendet in seiner Feistel-Rundenfunktion mehrere S-Boxen. Die Nichtlinearität dieser S-Boxen erzeugt die Konfusion. Zur Veranschaulichung betrachtet man zwei Nachrichten M und M', die sich nur in einem Bit unterscheiden und mit demselben Schlüssel verschlüsselt werden. Mit zunehmender Rundenzahl breitet sich dieser Unterschied exponentiell aus, weil sich bei jeder Anwendung der Rundenfunktion bei einem Eingabeunterschied von einem Bit mindestens zwei Bits ändern. Ein Eingabebit beeinflusst dadurch mehrere nicht miteinander korrelierte Ausgabebits.

Zusätzlich werden die Ausgabebits der Rundenfunktion permutiert. Die von einer S-Box ausgegebenen Bits werden in der nächsten Runde auf die Eingaben verschiedener S-Boxen verteilt. So entsteht Diffusion über den gesamten Datenblock. Das erschwert es, Beziehungen zwischen Klartext und Geheimtext herzuleiten. Konfusion und Diffusion wirken dabei zusammen: Die Nichtlinearität verschleiert die Beziehungen, während die Verteilung der Einflüsse über den Datenblock die Strukturen weiter verstreut.

Weitere Verschlüsselungsverfahren mit S-Boxen sind AES, Blowfish, CAST und Serpent.