Die Rolle der NSA

NBS und IBM beschlossen eine Kooperation mit Unterstützung der National Security Agency (NSA). Welchen Einfluss die NSA auf die Entwicklung des Algorithmus hatte, ist umstritten. Vor allem die Schlüssellänge von 56 Bits und das Design der für Substitution zuständigen „S-Boxen“ gab Anlass zu Spekulation über mögliche Hintertüren, die eventuell durch die NSA eingeführt wurden. Nach eigenen Angaben stärkte die NSA die S-Boxen gegen differentielle Kryptoanalyse, wollte aber gleichzeitig die Schlüssellänge auf 48 Bits beschränken, während IBM 64 Bits wollte. Als Kompromiss einigten sich NSA und IBM auf eine Schlüssellänge von 56 Bits.

Am 17. März 1975 wurde der Algorithmus im „Federal Register“ veröffentlicht. Die NBS bat zudem um öffentliche Stellungnahme. Im folgenden Jahr wurden zwei Workshops zum vorgeschlagenen Standard abgehalten. Durch die unklare Rolle der NSA zogen die Veränderungen des Algorithmus von verschiedenen Seiten Kritik auf sich, unter anderem von den Pionieren asymmetrischer Kryptosysteme Martin Hellman und Whitfield Diffie. Es wurde gemutmaßt, die NSA habe eine Hintertür eingebaut, welche das Verfahren dergestalt schwächt, dass sie damit verschlüsselte Nachrichten lesen konnte. Alan Konheim, einer der DES-Entwickler, gab an, die S-Boxen nach Washington gesendet und stark verändert wiedererhalten zu haben.

Ein nachrichtendienstliches Komitee des US-Senats untersuchte die Einflussnahme des NSA. In der nicht als Verschlusssache gehandhabten Zusammenfassung des Berichts gaben sie 1978 an:

Walter Tuchman, ein weiterer DES-Entwickler, wird mit den Worten zitiert “We developed the DES algorithm entirely within IBM using IBMers. The NSA did not dictate a single wire!” (deutsch: „Wir haben den DES-Algorithmus vollständig innerhalb von IBM unter Nutzung von IBMern entwickelt. Die NSA hat nicht ein einziges Memo diktiert!“).

Durch die Veröffentlichung der differentiellen Kryptoanalyse durch Adi Shamir und Eli Biham im Jahr 1990 wurden einige der Befürchtungen einer Hintertür aus dem Wege geräumt. DES zeigte sich durch die Gestaltung der S-Boxen deutlich widerstandsfähiger gegen diese generische Angriffsmethode, als dies bei einer zufälligen Anordnung der Fall gewesen wäre. 1994 veröffentlichte Don Coppersmith die ursprünglichen Designkriterien für die S-Boxen. Es zeigte sich, dass IBM die differentielle Kryptoanalyse bereits in den 1970er Jahren entdeckt hatte und nach Umgestaltung der S-Boxen von der NSA zur Geheimhaltung instruiert worden war.

Coppersmith erklärte “that was because [differential cryptanalysis] can be a very powerful tool, used against many schemes, and there was concern that such information in the public domain could adversely affect national security.” (deutsch: „dies geschah, da die [differentielle Kryptoanalyse] ein mächtiges Werkzeug gegen viele Verfahren sein kann und es Bedenken gab, die nationale Sicherheit könne durch eine Veröffentlichung gefährdet werden.“).

Shamir selbst kommentierte “I would say that, contrary to what some people believe, there is no evidence of tampering with the DES so that the basic design was weakened.” (deutsch: „Anders als manche glauben, sehe ich selbst keine Hinweise auf Manipulation von DES, welche das grundlegende Design geschwächt hat.“)

Die Kritik an der Länge des Schlüssels blieb jedoch bestehen und wurde durch die Begründung der NSA, 8 der 64 Schlüsselbits könnten als Paritätsbits verwendet werden, noch weiter gestützt. Es wird weithin vermutet, dass die Reduzierung der NSA die Möglichkeit eines Angriffs mit der Brute-Force-Methode schaffen sollte.

Heute gilt der DES aufgrund seiner geringen Schlüssellänge als nicht mehr sicher genug. Durch die Mehrfachanwendung des DES mit unterschiedlichen Schlüsseln wie zum Beispiel beim TDES kann die effektive Schlüssellänge erhöht werden.

Wissenschaftliche Untersuchungen haben mittlerweile erwiesen, dass DES trotz seiner Schlüssellänge von nur 56 Bits sicherer ist als der Lucifer-Algorithmus mit seinen 128 Bits.

Standardisierung

DES wurde als Standard für alle amerikanischen Bundesbehörden zugelassen und am 15. Januar 1977 als FIPS PUB 46 publiziert; verpflichtend für sie wurde er sechs Monate später. Der Standard enthielt die Auflage, alle fünf Jahre neu bestätigt werden zu müssen. Weiterhin befasste sich die Internationale Organisation für Normung (ISO) mit dem Algorithmus unter der Bezeichnung Data Encipherment No. 1 (DEA1).

1981 wurde der DES-Algorithmus vom American National Standards Institute (ANSI) als Standard für den privaten Sektor anerkannt.

Bereits Anfang der 1990er Jahre äußerten Kryptographen erste Zweifel, ob der DES-Algorithmus noch als sicher anzusehen sei. Zum einen hatte sich die Hardware im Vergleich zu 1970 stark weiter entwickelt, zum anderen glaubte man auch Schwächen im Algorithmus zu erkennen. 1994 wurde ein theoretischer Angriff mittels linearer Kryptoanalyse publiziert. Mitte 1998 führte die Electronic Frontier Foundation (EFF) einen erfolgreichen Angriff über die Brute-Force-Methode durch. Die Gesellschaft baute hierzu eine spezielle Hardware mit insgesamt über 1800 Mikroprozessoren und konnte mit dieser einen Schlüssel in weniger als drei Tagen brechen. Die Arbeiten am Nachfolgestandard AES hatten zu diesem Zeitpunkt schon begonnen. Am 26. Mai 2002 wurde DES schließlich durch AES ersetzt.

Die Einführung von DES gilt als Auslöser einer Vielzahl kryptographischer Studien, besonders solcher, die sich mit dem Angriff auf Blockchiffrierungen befassen. Bruce Schneier schreibt in seinem Buch Angewandte Kryptographie:

Chronologie

Betriebsmodi

Der DES-Algorithmus beschreibt zunächst nur, wie ein Datenblock mit 64 Bits verarbeitet wird. Zur Verarbeitung einer Nachricht beliebiger Länge lässt sich der DES wie auch jede andere Blockchiffre in verschiedenen Betriebsmodi verwenden. Für bestimmte Betriebsmodi, wie zum Beispiel ECB oder CBC, ist ein Auffüllen des Klartextes auf ein Vielfaches der vollen Blocklänge notwendig (Padding). Dies geschieht, indem die Bitfolge 1000… angehängt wird.

Die Expansion

Um den Halbblock in der Feistel-Funktion von 32 Bits auf 48 Bits zu erweitern, wird der Halbblock in 4-Bit-Gruppen aufgeteilt. Die Bits am Rand jeder 4-Bit-Gruppe werden vorn, beziehungsweise hinten an die benachbarte 4-Bit-Gruppe angehängt.

Die Substitution

Die Substitutionsboxen (S-Boxen) beim DES sind standardisiert. Um aus den folgenden Tabellen den Ausgabewert zu erhalten, wird der Eingabewert gesplittet. So bildet das erste und letzte Bit zusammen die Zeile, und die Spalte ergibt sich aus den übrigen Bits (siehe Beispiel). Eine Änderung dieser Boxen reduziert die Sicherheit drastisch! Daher sollten die folgenden Tabellen für die Substitutionsboxen verwendet werden:

Deep Crack

Die EFF baute 1998 eine etwa 250.000 Dollar teure Maschine mit dem Namen „Deep Crack“. Dieser Superrechner enthielt 1536 spezielle Krypto-Chips und konnte pro Sekunde etwa 88 Milliarden Schlüssel testen. Im Juli 1998 gelang es mit dieser Maschine, einen DES-Code in 56 Stunden zu knacken und damit die „DES Challenge II-2“ zu gewinnen, die von der Firma RSA Security ausgeschrieben worden war. 1999 gewann die gleiche Maschine die „DES Challenge III“; dazu arbeitete sie mit dem weltweiten Netzwerk von distributed.net, bestehend aus etwa 100.000 Rechnern, zusammen. Der DES-Schlüssel wurde in 22 Stunden und 15 Minuten gefunden, mehr als 245 Milliarden Schlüssel wurden pro Sekunde getestet.

COPACOBANA

Die einzige andere öffentlich bekannte Maschine zum Brechen von DES ist COPACOBANA. Sie wurde 2006 von zwei Arbeitsgruppen an den Universitäten Bochum und Kiel gebaut. Im Gegensatz zu Deep Crack besteht eine COPACOBANA aus rekonfigurierbaren Hardware-Bausteinen, sogenannten FPGAs. 120 FPGAs vom Typ Xilinx Spartan-3-1000 sind in einer Maschine auf 20 DIMM-Modulen zusammengefasst, wobei jedes DIMM-Modul sechs FPGAs enthält. COPACOBANA kann 65 Milliarden DES-Schlüssel pro Sekunde testen, woraus sich eine durchschnittliche Suchzeit von 6,4 Tagen für eine DES-Attacke ergibt. Durch den Einsatz rekonfigurierbarer Hardware kann COPACOBANA auch zum Brechen anderer Chiffren wie A5 eingesetzt werden. Die Material- und Herstellungskosten von COPACOBANA belaufen sich auf etwa 10.000 Dollar. Der Kostenvorteil gegenüber Deep Crack um einen Faktor 25 ist ein beeindruckendes Beispiel für das Mooresche Gesetz. Hiernach wäre ein Kostenvorteil von etwa 32 = 2⁵ zu erwarten gewesen, da acht Jahre zwischen dem Bau der beiden Maschinen verstrichen sind (das Mooresche Gesetz sagt eine Halbierungen der Kosten digitaler ICs alle 1,5 Jahre voraus, so dass bei acht Jahren etwa 5 Halbierungen stattgefunden haben sollten).

Der derzeitige Rekord wurde 2008 von der Firma SciEngines GmbH (einem SpinOff der COPACOBANA-Arbeitsgruppen) aufgestellt und auf einem Workshop 2009 erneut verbessert. Mit 128 Xilinx-FPGAs lag der Durchsatz bei über 292 Milliarden Schlüsseln pro Sekunde.

Geringfügige Schwächen

DES besitzt eine Komplement-Eigenschaft, das heißt, es gilt

${\displaystyle \operatorname {DES} _{K}(m)={\overline {\operatorname {DES} _{\overline {K}}({\overline {m}})}}}$ für alle Schlüssel ${\displaystyle K}$ und alle Klartexte ${\displaystyle m}$,

wobei ${\displaystyle {\overline {x}}}$ das bitweise Komplement von ${\displaystyle x}$ bezeichnet. Dadurch lässt sich mit einem Chosen-Plaintext-Angriff bei einer vollständigen Schlüsselsuche der Suchraum auf 2⁵⁵ Schlüssel halbieren.

Es existieren vier schwache Schlüssel ${\displaystyle K}$ mit der Eigenschaft, dass

${\displaystyle \operatorname {DES} _{K}(\operatorname {DES} _{K}(m))=m}$ für alle Klartexte ${\displaystyle m}$.

Des Weiteren gibt es sechs semi-schwache Schlüsselpaare ${\displaystyle (K_{1},K_{2})}$ mit der Eigenschaft, dass

${\displaystyle \operatorname {DES} _{K_{1}}(\operatorname {DES} _{K_{2}}(m))=m}$ für alle Klartexte ${\displaystyle m}$.

In der Praxis ist dies jedoch kein Problem, da die Wahrscheinlichkeit für einen (semi-)schwachen Schlüssel bei zufälliger Auswahl eines Schlüssels nur 16:2⁵⁶ beträgt. Außerdem lässt sich die Verwendung dieser Schlüssel leicht vermeiden, indem sie bei der Erzeugung explizit ignoriert werden.

Triple-DES

Der erste Ersatz für DES war Triple-DES (auch 3DES oder DESede genannt). Die Idee der mehrfachen Ausführung von DES mit zwei verschiedenen Schlüsseln ist ein Verfahren, das vom DES-Mitentwickler Walter Tuchman beschrieben und analysiert wurde (siehe FIPS 46-3). Ralph Merkle und Martin Hellman schlugen nach einer weiteren Analyse 1981 die Dreifachverschlüsselung mit drei unabhängigen, voneinander verschiedenen Schlüsseln vor.

Bei der am häufigsten verwendeten Methode wird jeder Datenblock mit einem DES-Schlüssel ${\displaystyle K_{1}}$ chiffriert, dann mit ${\displaystyle K_{2}}$ dechiffriert und mit ${\displaystyle K_{3}}$ chiffriert:

${\displaystyle \operatorname {3DES} _{(K_{1},K_{2},K_{3})}:=\operatorname {DES} _{K_{3}}\circ \operatorname {DES} _{K_{2}}^{-1}\circ \operatorname {DES} _{K_{1}}}$

Dieses Verfahren wird auch als EDE (Encrypt-Decrypt-Encrypt) bezeichnet. Eine einfache DES-Verschlüsselung ist somit ein Spezialfall von 3DES:

${\displaystyle \operatorname {3DES} _{(K,K,K)}=\operatorname {DES} _{K}}$

Ein für die Verschlüsselungsstärke von 3DES wichtiges mathematisches Problem war die Frage, ob die Hintereinanderausführung von DES-Operationen die Sicherheit erhöht; dies wäre nicht der Fall, wenn DES eine Gruppe ist. Campell und Wiener fanden heraus, dass die Menge der DES-Verschlüsselungen ${\displaystyle \operatorname {DES} _{K}}$ unter Hintereinanderausführung nicht abgeschlossen ist. Das bedeutet, dass es Schlüssel ${\displaystyle K_{1}}$ und ${\displaystyle K_{2}}$ gibt, sodass ${\displaystyle \operatorname {DES} _{K_{2}}\circ \operatorname {DES} _{K_{1}}\neq \operatorname {DES} _{K}}$ für alle Schlüssel ${\displaystyle K}$. Anders ausgedrückt ist die Anzahl der Permutationen von der Form ${\displaystyle \operatorname {DES} _{K_{2}}\circ \operatorname {DES} _{K_{1}}}$ bedeutend größer als die Zahl der ${\displaystyle \operatorname {DES} _{K}}$-Permutationen. Damit lässt sich die effektive Schlüssellänge tatsächlich steigern. Dies konnte allerdings erst 1992 gezeigt werden.

Die Schlüssellänge von 3DES ist mit 168 Bits dreimal so groß wie bei DES (56 Bits), die effektive Schlüssellänge liegt aber nur bei 112 Bits. Dies ist bedingt durch die Möglichkeit eines sogenannten Meet-in-the-middle-Angriff: Ist der Angreifer im Besitz eines Paares aus Klartext und Chiffre, so kann er die Verschlüsselung von beiden Seiten angreifen. Der Klartext wird mit sämtlichen möglichen Schlüsseln für Stufe 1 verschlüsselt (2⁵⁶ Möglichkeiten). Die so entstandenen Texte werden ebenfalls jeweils mit allen möglichen Schlüsseln für Stufe 2 entschlüsselt (2¹¹² Möglichkeiten). Deren Ergebnisse vergleicht man mit den Ergebnissen der Entschlüsselung des Chiffretextes mit sämtlichen Schlüsseln (2⁵⁶Möglichkeiten). So müssen insgesamt nur 2¹¹²+2⁵⁶≈2¹¹² Ver- bzw. Entschlüsselungen durchgeführt werden, anstatt 2¹⁶⁸ bei Verwendung der Brute-Force-Methode.

Aufgrund dieses Missverhältnisses zwischen Schlüssellänge und effektivem Sicherheitsniveau wird oft ${\displaystyle K_{1}=K_{3}}$ gewählt. Dies liefert für eine Schlüssellänge von 112 Bits ein theoretisches Sicherheitsniveau von 112 Bits, da kein Meet-in-the-middle-Angriff möglich ist. Es gibt jedoch weitere Angriffe, so dass 3DES mit zwei Schlüsseln vom National Institute of Standards and Technology mit einem Sicherheitsniveau von 80 Bits bewertet wird.

AES

Durch einen Wettbewerb des NIST wurde im Oktober 2000 der Advanced Encryption Standard (AES) gewählt, um DES offiziell zu ersetzen. Das jetzt als AES bezeichnete Verschlüsselungsverfahren, das den Wettbewerb gewann, war von seinen belgischen Entwicklern Vincent Rijmen und Joan Daemen unter dem Namen Rijndael zu diesem Wettbewerb eingereicht worden.