DES-Design und die Lucifer-Chiffre

1971 entwickelte Horst Feistel bei IBM Research im Rahmen eines Projekts zur Banksicherheit für Lloyd's of London eine Chiffre namens Lucifer. Lucifer war eine der ersten modernen Blockchiffren und verwendete einen 128-Bit-Schlüssel sowie 128-Bit-Blöcke.

Lucifer zeigte, dass sich mithilfe der Feistel-Struktur eine starke Blockchiffre entwickeln lässt: Abwechselnde Runden aus Substitution und Permutation werden auf Blockhälften angewendet. Lucifer war der direkte Vorläufer von DES.

DES wendet die Feistel-Struktur in 16 Runden auf 64-Bit-Blöcke an. In jeder Runde wird der 64-Bit-Block in zwei 32-Bit-Hälften geteilt. Die rechte Hälfte wird auf 48 Bit erweitert, mit einem 48-Bit-Teilschlüssel per XOR verknüpft, durch S-Boxen geleitet, permutiert und per XOR mit der linken Hälfte verknüpft.

Anschließend werden die Hälften vertauscht und der Vorgang wiederholt sich. Nach 16 Runden erzeugt eine abschließende Permutation den 64-Bit-Ciphertext. Die Entschlüsselung verwendet dieselbe Struktur, jedoch die Teilschlüssel in umgekehrter Reihenfolge.

DES verschlüsselt Daten in 64-Bit-Blöcken (8 Byte). Diese feste Blockgröße war für die Hardware des Jahres 1977 angemessen, ist jedoch zu einem Sicherheitsrisiko geworden. Bei ausreichender Datenmenge werden Kollisionen aufgrund des Geburtstagsparadoxons wahrscheinlich.

Bei 64-Bit-Blöcken treten nach ungefähr 2^32 Blöcken (~32 GB unter demselben Schlüssel verschlüsselter Daten) statistische Muster auf. Dieser Sweet32-Angriff machte 3DES für Datenverkehr mit hohem Volumen wie HTTPS unsicher.

DES verwendet einen 64-Bit-Schlüssel, aber 8 der Bits sind Paritätsbits zur Fehlererkennung und werden nicht für die Verschlüsselung verwendet. Die effektive Schlüssellänge beträgt daher nur 56 Bit.

Das bedeutet, dass es nur 2^56 (etwa 72 Billiarden) mögliche DES-Schlüssel gibt. Nach den Maßstäben von 1977 galt das als ausreichend. 1997 war es nachweislich möglich, einen solchen Schlüssel mit einem entschlossenen Angreifer zu brechen.

DES beginnt mit einer initialen Permutation (IP), die die 64 Bit des Klartextblocks neu anordnet, und endet mit einer abschließenden Permutation (IP^-1), die exakt deren Umkehrung ist. Diese Permutationen erhöhen die kryptografische Stärke nicht.

Sie wurden für die Hardwareeffizienz auf bestimmten Chiparchitekturen der 1970er-Jahre entwickelt, um das Laden von Bits in Register zu beschleunigen. Moderne Analysen bestätigen, dass sie nichts zur Sicherheit beitragen.

Die acht S-Boxen (Substitutionsboxen) bilden das Herzstück der Nichtlinearität von DES. Jede S-Box nimmt 6 Eingabebits auf und erzeugt 4 Ausgabebits mithilfe einer festen Nachschlagetabelle. Die äußeren 2 Bits wählen die Zeile aus, die inneren 4 Bits die Spalte.

Ohne die durch die S-Boxen bereitgestellte Nichtlinearität wäre DES eine rein lineare Chiffre, die sich mit linearer Algebra trivial brechen ließe. Das spezielle Design der S-Boxen von DES ist resistent gegen differentielle Kryptoanalyse.

Nach den S-Boxen wendet DES eine P-Box-Permutation an, die die 32 Ausgabebits der S-Boxen neu anordnet. Dies sorgt für Diffusion, indem die Ausgabe jeder S-Box so verteilt wird, dass sie mehrere S-Boxen in der nächsten Runde beeinflusst.

Die P-Box wurde sorgfältig entwickelt, um die Diffusion zu maximieren: Jedes Ausgabebit einer S-Box beeinflusst in der nächsten Runde mindestens zwei verschiedene S-Boxen und sorgt so für einen schnellen Avalanche-Effekt.

DES leitet aus dem 56-Bit-Hauptschlüssel 16 verschiedene 48-Bit-Unterschlüssel ab, einen für jede Runde. Der Schlüsselplan beginnt mit der Anwendung einer Permutation Choice (PC-1), die Paritätsbits entfernt und die Schlüsselbits neu anordnet.

Die 56 Bits werden in zwei 28-Bit-Hälften aufgeteilt, die in jeder Runde um 1 oder 2 Positionen nach links rotiert werden. Anschließend wählt eine Permutation Choice (PC-2) 48 der 56 Bits aus, um den Unterschlüssel der jeweiligen Runde zu bilden.

Die NSA arbeitete während der Entwicklung von DES mit IBM zusammen, verkürzte die Schlüssellänge von Lucifers 128 Bit auf 56 Bit und veränderte das Design der S-Boxen. Dies löste eine jahrzehntelange Kontroverse darüber aus, ob Hintertüren eingeführt worden waren.

In den 1990er-Jahren bestätigten NSA-Beamte, dass sie die S-Boxen gegen differentielle Kryptoanalyse verstärkt hatten – eine Technik, die IBM 1974 entdeckt hatte. Die NSA kannte die differentielle Kryptoanalyse bereits Jahre vor der akademischen Forschung. Das deutet darauf hin, dass sie DES widerstandsfähiger und nicht schwächer gemacht hatte.

DES wurde im Januar 1977 nach einem Vergleich mehrerer Verfahren als Federal Information Processing Standard 46 verabschiedet. Es wurde zum Standardverfahren für nicht klassifizierte Regierungsdaten und fand breite Anwendung im Bankenwesen und in der Industrie.

Die Standardisierung von DES war historisch bedeutsam: DES war der erste öffentlich verfügbare, von einer Regierung unterstützte kryptografische Algorithmus. Sie trieb die Entwicklung von Hardware-Implementierungen voran und etablierte das Muster für künftige Standardisierungsverfahren von Verschlüsselungsverfahren.

DES selbst ist eine Blockchiffre, die jeweils genau 64 Bit verschlüsselt. Da echte Nachrichten länger sind, legen Betriebsmodi fest, wie die Chiffre auf mehrere Blöcke angewendet wird. Zu den verbreiteten Modi gehören ECB (jeden Block unabhängig verschlüsseln), CBC (jeden Block vor der Verschlüsselung mit dem vorherigen Geheimtext per XOR verknüpfen), CFB, OFB und CTR.

ECB ist der schwächste Modus: Identische Klartextblöcke erzeugen identische Geheimtextblöcke, wodurch sichtbare Muster entstehen. CBC und CTR beseitigen diese Schwäche und werden für die praktische Verwendung von DES und 3DES bevorzugt.

Testen Sie Ihr Wissen über die Designparameter von DES.

DES entwickelte sich aus IBMs Lucifer-Chiffre zu einer 16-rundigen Feistel-Chiffre mit 64-Bit-Blöcken und effektiven 56-Bit-Schlüsseln. Seine Sicherheit beruht auf 8 nichtlinearen S-Boxen für Konfusion, der P-Box für Diffusion und 16 Runden, die den Lawineneffekt verstärken.

Die Beteiligung der NSA am Design der S-Boxen war umstritten, verbesserte letztlich aber die Widerstandsfähigkeit gegen differentielle Kryptoanalyse. DES’ 56-Bit-Schlüssel, der für Hardware des Jahres 1977 ausgelegt war, erwies sich Ende der 1990er-Jahre als unzureichend.