So wurde DES geknackt

DES besitzt 2^56 mögliche Schlüssel, was ungefähr 72 Billiarden (72.057.594.037.927.936) Schlüsseln entspricht. Auch wenn diese Zahl enorm klingt, handelt es sich um einen endlichen Schlüsselraum, der mit ausreichender Rechenleistung systematisch durchsucht werden kann.

Das Ausschöpfen des Schlüsselraums (Brute-Force-Angriff) erfordert im Durchschnitt, die Hälfte des Schlüsselraums zu testen, bevor der richtige Schlüssel gefunden wird. Für DES bedeutet das etwa 2^55 Entschlüsselungsversuche, von denen jeder auf moderner Hardware nur wenige Operationen benötigt.

1997 setzte RSA Data Security ein Preisgeld von 10.000 US-Dollar für das Brechen einer mit DES verschlüsselten Nachricht aus. Rocke Verser koordinierte eine verteilte Rechenleistung über Zehntausende mit dem Internet verbundene Computer.

Nach 96 Tagen Suche wurde der Schlüssel gefunden. Der Klartext lautete „Starke Kryptografie macht die Welt sicherer.“ Die Aktion zeigte, dass DES gebrochen werden konnte, auch wenn dafür Monate und eine umfangreiche Koordination erforderlich waren.

Die Electronic Frontier Foundation baute Deep Crack 1998 für 250.000 US-Dollar. Das System enthielt 1.856 speziell entwickelte ASICs, von denen jedes 2,5 Millionen DES-Schlüssel pro Sekunde testen konnte. Dadurch erreichte Deep Crack insgesamt mehr als 90 Milliarden Schlüssel pro Sekunde.

Deep Crack konnte den gesamten DES-Schlüsselraum durchschnittlich in etwa 9 Tagen ausschöpfen. Damit war bewiesen, dass ein entschlossener Angreifer mit einer Investition von 250.000 US-Dollar DES in weniger als zwei Wochen brechen konnte.

Bei DES Challenges II-1 (Februar 1998) knackte Deep Crack gemeinsam mit dem freiwilligen Rechnernetzwerk von distributed.net DES in nur 39 Tagen. Challenge II-2 (Juli 1998) fiel nach 56 Stunden.

Die schnelle Verbesserung von 96 Tagen auf 56 Stunden innerhalb eines einzigen Jahres zeigte, wie stark Hardwarefortschritte und bessere Koordination Brute-Force-Angriffe beschleunigen konnten.

Im Januar 1999 brachen Deep Crack der EFF und distributed.net DES Challenge III gemeinsam in nur 22 Stunden und 15 Minuten und gewannen damit ein Preisgeld von 10.000 US-Dollar von RSA Security.

Diese eindeutige Demonstration, dass DES in weniger als 24 Stunden gebrochen werden konnte, beendete praktisch jede Argumentation für die Sicherheit von DES. NIST begann kurz darauf mit der Auswahl eines DES-Ersatzes, aus der AES hervorging.

Distributed.net organisierte Aktionen mit freiwilliger Rechenleistung, bei denen gewöhnliche Internetnutzer ihre CPU-Zeit für die DES Challenges zur Verfügung stellten. Auf dem Höhepunkt beteiligten sich Hunderttausende Computer.

Jeder Computer testete einen anderen Teil des Schlüsselraums, koordiniert von einem zentralen Server. Damit wurde das Modell des verteilten Rechnens für die Kryptoanalyse etabliert, das bis heute bei Herausforderungen wie dem Brechen älterer Chiffren verwendet wird.

Das Ausschöpfen des Schlüsselraums funktioniert, weil jede DES-Entschlüsselung schnell ist (auf Hardware im Mikrosekundenbereich) und unabhängig von den anderen durchgeführt werden kann. Zwischen dem Testen des Schlüssels N und des Schlüssels N+1 besteht keine Abhängigkeit. Daher lässt sich die Suche perfekt auf beliebig viele Rechner verteilen.

Diese inhärent parallele Struktur bedeutet, dass eine Verdopplung der Hardware die benötigte Zeit exakt halbiert. Weitere Rechner sorgen für eine lineare Beschleunigung, wodurch sich der Aufwand für Angreifer wirtschaftlich lohnt.

Eli Biham und Adi Shamir veröffentlichten 1990 die differentielle Kryptoanalyse, eine Technik, die ausnutzt, wie sich Unterschiede in Eingabepaaren durch die Runden einer Chiffre fortpflanzen. Für DES erfordert sie theoretisch 2^47 ausgewählte Klartexte.

Später wurde bekannt, dass die S-Boxen von DES mit Blick auf die Widerstandsfähigkeit gegen differentielle Kryptoanalyse entwickelt worden waren. Das deutet darauf hin, dass die NSA diese Technik bereits in den 1970er-Jahren kannte. Der Angriff ist theoretisch beeindruckend, wird in der Praxis jedoch von Brute-Force-Angriffen mit Hardware übertroffen.

Mitsuru Matsui veröffentlichte 1993 die lineare Kryptoanalyse, die für einen Angriff auf DES 2^43 bekannte Klartexte erfordert. Er implementierte den Angriff und brach DES 1994 experimentell, womit er die theoretische Analyse bestätigte.

Die lineare Kryptoanalyse findet lineare Näherungen für das Verhalten der S-Boxen und verwendet sie, um Schlüsselbits anhand einer statistischen Verzerrung zu ermitteln. Theoretisch benötigt sie deutlich weniger Daten als Brute Force, war jedoch vor den Hardwareangriffen praktisch nicht umsetzbar.

Die differentielle Kryptoanalyse wurde 1990 veröffentlicht, erfordert jedoch ausgewählte Klartexte, die in den meisten realen Szenarien unpraktisch sind. Die lineare Kryptoanalyse wurde 1993 veröffentlicht und funktioniert mit bekannten Klartexten, benötigt davon aber 2^43.

Brute Force mit Hardware (Deep Crack) brach DES 1999 in 22 Stunden. In der Praxis war der Hardwareangriff verheerender als die theoretischen Fortschritte der Kryptoanalyse, da er keinerlei spezielle Klartext-Geheimtext-Paare erforderte.

Das öffentlich dokumentierte Brechen von DES hatte unmittelbare Auswirkungen auf die Sicherheitspolitik. NIST begann 1997 mit dem Auswahlverfahren für AES, im selben Jahr, in dem DES Challenge I erfolgreich abgeschlossen wurde. Das Verfahren war ausdrücklich darauf ausgelegt, die Schwächen des Standardisierungsprozesses von DES zu vermeiden.

Banken und Regierungsbehörden begannen, während der Entwicklung von AES als Zwischenlösung auf 3DES umzustellen. Der Zeitplan für das Brechen von DES bestimmte unmittelbar die Dringlichkeit und den Zeitrahmen der Einführung von AES.

Testen Sie Ihr Verständnis der Geschichte des Brechens von DES.

DES wurde zunehmend schneller gebrochen: 1997 in 96 Tagen, 1998 in 56 Stunden und 1999 in 22 Stunden. Deep Crack der EFF nutzte speziell entwickelte ASICs, um 90 Milliarden Schlüssel pro Sekunde zu testen.

Sowohl differentielle Kryptoanalyse (2^47 ausgewählte Klartexte) als auch lineare Kryptoanalyse (2^43 bekannte Klartexte) können DES theoretisch brechen, doch Brute Force mit Hardware war der praktische entscheidende Angriff. Der 22-stündige Angriff beendete die Einsatzfähigkeit von DES als praktikable Chiffre.