Konfusion (Kryptologie)

Konfusion ist in der Kryptologie eines der beiden zentralen Prinzipien zur Verschleierung von Strukturen eines Klartextes im Zuge einer Verschlüsselung oder beim Hashen. Das andere dieser Prinzipien ist die Diffusion. Sie gehen auf den amerikanischen Mathematiker Claude Shannon zurück. Konfusion soll die Beziehung zwischen Klartext, Schlüssel und Geheimtext verschleiern, indem nichtlineare Operationen zur Berechnung des Geheimtextes genutzt werden.

Zweck

Zwischen dem Klartext sowie dem Schlüssel und dem damit generierten Geheimtext sollte keine Beziehung erkennbar sein, weil dadurch die statistische Kryptoanalyse erschwert wird.[1]

Besteht eine erkennbare Beziehung zwischen Schlüssel und Geheimtext, so kann auf den Schlüssel geschlussfolgert werden.[1] Analog ist es problematisch, wenn eine direkte Beziehung zwischen Klartext und Geheimtext erkennbar ist, sodass aus dem Geheimtext ggf. Informationen über den Klartext abgeleitet werden können, ohne den Schlüssel herausfinden zu müssen, weshalb der Schlüssel die Beziehung möglichst verschleiern sollte.[2]

Eine solche Klartext-Geheimtext-Beziehung ist bei monoalphabetischer Substitution zu beobachten, weil diese die Buchstabenhäufigkeit im Geheimtext vom Klartext übernimmt: Der Schlüssel ändert nichts an der Buchstabenhäufigkeit des generierten Geheimtextes, und das Verfahren ist anfällig gegen die Häufigkeitsanalyse.[1]

Grundlagen

Um Konfusion zu erreichen, muss ein kryptografisches Verfahren nichtlineare Operationen enthalten. Eine Abbildung der Eingabebits (Klartext- und Schlüsselbits) auf ein bestimmtes Ausgabebit (Geheimtextbit) ist linear, wenn das Ergebnis nur durch Additionen im Körper GF(2), das heißt durch XOR von Eingabebits und evtl. negieren des Resultats, berechnet wird. Also dann, wenn das Ergebnis als Polynom vom Grad 1 in den Eingabebits ausgedrückt werden kann.[3] Es wäre somit ein Fehler, die Geheimtextbits nur durch XOR-Verknüpfung von Klartext- und Schlüsselbits zu berechnen. Ein solches Verfahren wäre völlig linear, und durch einen Angriff mit bekanntem Klartext könnte man den Schlüssel leicht ermitteln.

Ein kryptografisches Verfahren ist meist als Abfolge von mehreren gleich oder ähnlich aufgebauten Runden konstruiert. Jede Runde besteht in der Anwendung einer Rundenfunktion auf den Datenblock, die nichtlineare Operationen enthält und außerdem für Diffusion sorgt. Dadurch verstärkt sich die Konfusion mit jeder zusätzlichen Runde, d. h. der Grad des einfachsten Polynoms, mit dem sich die Abbildung der Eingabebits auf ein Ergebnisbit ausdrücken lässt, nimmt mit der Zahl der Runden zu. Insbesondere hängt nach einigen Runden jedes berechnete Bit von allen Eingabebits auf nichtlineare Weise ab. Durch eine ausreichende Rundenzahl kann das Verfahren also genügend komplex gemacht werden, um kryptographisch sicher zu sein.

Realisierung

In der Praxis nutzt man unter anderem die Addition zweier Datenwörter modulo , wobei die Zahl der Bits eines Worts ist, als kryptographisches Primitiv. Diese Operation ist nicht linear, weil bei der Addition zweier Bits das Übertragbit durch UND-Verknüpfung der Eingabebits, also durch Multiplikation in , berechnet wird.

In vielen modernen Verfahren dient die Addition von Wörtern als einzige nichtlineare Operation. Sie wird meist mit dem bitweisen XOR kombiniert, denn es zeigt sich, dass die abwechselnde Anwendung von Addition und XOR kryptografisch wirksamer ist als die Addition allein. Beispiele für Blockchiffren, die nur Addition und XOR zur Konfusionserzeugung nutzen, sind FEAL, TEA, XTEA und Threefish. Verfahren, die nur aus Addition, Rotation von Datenwörtern und XOR aufgebaut sind, wie etwa Threefish, nennt man auch ARX-Chiffren, nach den Anfangsbuchstaben dieser drei Operationen.

Viele kryptografische Verfahren enthalten S-Boxen als Bauelemente ihrer Rundenfunktion. Bei geschickter Wahl, wie die Ausgabebits einer S-Box von deren Eingabebits abhängen, kann mit einer S-Box eine stark nichtlineare Beziehung hergestellt werden, sodass S-Boxen als Konfusionserzeuger gut geeignet sind.

Zur Verdeutlichung soll DES dienen, welches die Kombination mehrerer S-Boxen in seiner Feistel-Rundenfunktion verwendet. Konfusion wird durch die Nichtlinearität der S-Boxen erreicht. Werden zwei Nachrichten und , die sich in nur einem Bit unterscheiden, mit dem gleichen Schlüssel verschlüsselt, so breitet sich dieser Unterschied exponentiell mit steigender Rundenanzahl aus, da sich pro Anwendung der Rundenfunktion mindestens zwei Bits bei einem Unterschied von einem Bit in der Eingabe ändern.[4] Ein Eingabebit hat also auf mehrere unkorrelierte Ausgabenbits Einfluss. Außerdem werden die Ausgabebits der Rundenfunktion so permutiert, dass die von einer S-Box ausgegebenen Bits sich in der nächsten Runde auf die Eingaben unterschiedlicher S-Boxen aufteilen, was zu Diffusion über den ganzen Datenblock führt. All das macht es schwieriger, Beziehungen zwischen Klartext und Geheimtext herzuleiten.[5]

Andere Verschlüsselungsverfahren, die S-Boxen verwenden, sind AES, Blowfish, CAST und Serpent.

Einzelnachweise

  1. ↑ a b c C. E. Shannon: Communication theory of secrecy systems. In: The Bell System Technical Journal. Band 28, Nr. 4, Oktober 1949, ISSN 0005-8580, S. 656–715, hier: Kapitel 23. Statistical Methods (S. 707ff), doi:10.1002/j.1538-7305.1949.tb00928.x (ieee.org [abgerufen am 27. Januar 2023]).
  2. ↑ C. E. Shannon: Communication theory of secrecy systems. In: The Bell System Technical Journal. Band 28, Nr. 4, Oktober 1949, ISSN 0005-8580, S. 656–715, hier: Kapitel 24. The Probable Word Method (S. 710f), doi:10.1002/j.1538-7305.1949.tb00928.x (ieee.org [abgerufen am 27. Januar 2023]).
  3. ↑ Klaus Pommerening: Linearitätsmaße für boolesche Abbildungen. 4. Juli 2008, abgerufen am 9. August 2020.
  4. ↑ Don Coppersmith: The Data Encryption Standard (DES) and its strength against attacks. In: International Business Machines Corporation (Hrsg.): IBM Journal of Research and Development. Band 38, Nr. 3, 3. Mai 1994, S. 247, Absch. Design Criteria Nr. S-4 (simson.net [PDF]): „If two inputs to an S-box differ in exactly one bit, the outputs must differ in at least two bits.“
  5. ↑ C. E. Shannon: Communication theory of secrecy systems. In: The Bell System Technical Journal. Band 28, Nr. 4, Oktober 1949, ISSN 0005-8580, S. 656–715, hier: Kapitel 24. The Probable Word Method (S. 710f), doi:10.1002/j.1538-7305.1949.tb00928.x (ieee.org [abgerufen am 27. Januar 2023]): „From the point of view of increasing confusion, it is desirable to have the f_i involve several m_i, especially if these are not adjacent and hence less correlated.“