Dipl.-Inform. Carsten Eilers

Der Algorithmus des DES-Verfahrens wurde erstmals am 15. Januar 1977 in "Specification for the Data Encryption Standard; Federal Information Processing Standards Publication 46 (FIPS PUB 46)" veröffentlicht. Die erste Version ist leider nicht online verfügbar, ebensowenig die überarbeitete zweite Version. Lediglich die dritte Ausgabe, FIPS PUB 46-3 (PDF) ist noch online. Allerdings nur zur Dokumentation, denn nutzen sollte man DES wirklich nicht mehr. Es sei denn, man möchte, dass jeder die Daten entschlüsseln kann und hat zwar ein Programm zur DES-Verschlüsselung zur Hand, aber keines für Rot13.

DES und die NSA

Über die Beteiligung der NSA rankten sich von Anfang an Gerüchte, so soll der Algorithmus absichtlich unsicherer gemacht oder eine Hintertür eingebaut worden sein. 1978 untersuchte ein Komitee mit Zugriff auf geheime Unterlagen diese Befürchtungen und erklärte sie für unbegründet, hielt die Begründung dafür jedoch geheim. Vermutlich aus gutem Grund, wie wir inzwischen wissen.

Über den Einfluss der NSA auf die Entwicklung von DES gibt es inzwischen unterschiedliche Aussagen. Erst war man bei der NSA gegen eine Mitarbeit, dann wollte man den Schaden zumindest so weit wie möglich begrenzen: Wenn es nur einen allgemein genutzten Algorithmus gibt, der alle Konkurrenzprodukte verdrängt, müsste man sich nur um den kümmern. Laut NSA wurden der Algorithmus gegen alle Angriffe außer Brute-Force-Angriffen gehärtet und auch die S-Boxen verstärkt, gleichzeitig wollte man aber die Schlüssellänge auf 48 Bits beschränken. Da IBM die Schlüssellänge auf 64 Bits festlegen wollte, einigte man sich auf den Kompromiss von 56 Bits, siehe Tom R. Johnson, "American Cryptology during the Cold War, 1945–1989: Book III: Retrenchment and Reform" (entweder als zensierte Veröffentlichung der NSA (DOCID 3417193) als PDF (auf Seite 232 = Seite 114 im PDF) oder als FOIA-Veröffentlichung auf cryptome.org mit weniger Schwärzungen).

Mitarbeiter vom IBM haben einerseits ausgesagt, der DES-Algorithmus sei vollständig bei IBM und nur von IBM-Mitarbeitern entwickelt worden und die NSA hätte rein gar nichts vorgegeben (was im Widerspruch zur NSA-eigenen Aussage steht), andererseits sind die an die NSA gesandten S-Boxen völlig verändert zurückgekommen, siehe Bruce Schneiers Buch "Applied Cryptography". Dafür gibt es mindestens drei mögliche Erklärungen:

1. Die NSA hat über die S-Boxen eine Hintertür eingebaut.
2. Die NSA wollte eine mögliche Hintertür von IBM verhindern und hat darum selbst entwickelte S-Boxen verwendet.
3. Die NSA hat die S-Boxen verbessert, um Angriffen entgegen zu wirken.

Nach der Veröffentlichung der differentiellen Kryptanalyse durch Eli Biham und Adi Shamir ("Differential Cryptanalysis of DES-like Cryptosystems", Download als .PS.GZ) stellt sich heraus, dass DES durch den Aufbau der S-Boxen deutlich widerstandsfähiger gegen differentielle Kryptanalyse ist als es bei einem zufälligen Aufbau der S-Boxen der Fall wäre. 1994 wurden von Don Coppersmith die ursprünglichen Designkriterien der S-Boxen veröffentlicht ("The Data Encryption Standard (DES) and its strength against attacks", PDF). Dabei kam heraus, dass die differentielle Kryptanalyse den DES-Entwicklern von IBM bereits 1974 bekannt war. Man hielt das Verfahren aber geheim, da eine Veröffentlichung die nationale Sicherheit gefährdet hätte. Das wirft natürlich auch wieder Fragen auf: Da IBM die differentielle Kryptanalyse kannte, sollten die S-Boxen bereits dagegen gehärtet gewesen sein, bevor sie an die NSA geschickt wurden. Wieso hat die NSA sie dann geändert?

Das ist alles sehr ausführlich in Bruce Schneiers Buch beschrieben, heutzutage aber nur noch aus historischen Interesse Interessant, und das trotz der Enthüllungen von Edward Snowden (die zumindest bisher nichts zu DES enthalten haben). Den inzwischen kann DES von jedem geknackt werden, der Wert darauf legt.

Früher war es ein Schlüssel, heute ist es ein Witz

Das Problem von DES ist der Schlüssel, genauer: Seine Länge (oder aus heutiger Sicht: Kürze), die nicht geändert werden kann: DES verwendet einen 56 Bit langen Schlüssel und verschlüsselt Blöcke von 64 Bit Länge. Der Schlüssel wird um 8 Paritätsbits auf 64 Bit erweitert, die Paritätsbits werden für den Algorithmus jedoch nicht verwendet.

Auch ohne mögliche NSA-Hintertür kann spezialisierte Hardware die DES-Verschlüsselung durch einen Brute-Force-Angriff in weniger als einem Tag knacken. Dabei werden alle möglichen Schlüssel, 2⁵⁶ = ca. 72 Billiarden, ausprobiert.

Bereits 1998 entwickelte die Electronic Frontier Foundation den 250.000 US-Dollar kostenden "DES Cracker" (auch "Deep Crack" genannt), der einen DES-Schlüssel in 56 Stunden brach (FAQ dazu). 2007 wurden mit den von den Universitäten Bochum und Kiel entwickelten COPACOBANA (Cost-Optimized Parallel Code Breaker) DES-Schlüssel in durchschnittlich 6.4 Tagen (im Worst Case in 12,8 Tagen) geknackt - bei Baukosten von 10.000 US-Dollar. Und der Nachfolger von COPACOBANA, RIVYERA, schaffte es 2008, die Zeit auf unter einen Tag zu drücken. Die NSA sollte also schon seit längerem Rechner haben, die DES deutlich schneller per Brute-Force-Angriff brechen, denn Geld spielt dort ja bekanntlich (fast) keine Rolle.

DES ist ein gutes Beispiel dafür, dass kryptografische Verfahren im Laufe der Zeit immer unsicherer werden. Vereinfacht kann man sagen: Je stärker die Rechenleistung wird, desto länger müssen die Schlüssel werden. An DES an sich ist nach wie vor nichts aus zu setzen, das Problem ist schlicht die Schlüssellänge: Bei seiner Entwicklung hätte ein Brute-Force-Angriff eine Ewigkeit gedauert, mit heute erhältlicher Hardware ist er eine Kleinigkeit. Wenn man DES mit längeren Schlüsseln verwenden könnte, wäre es weiterhin sicher. Vorausgesetzt, die NSA hat keine Hintertür eingebaut, das wäre dann natürlich zu prüfen (bzw. der Algorithmus wegen dieser Bedenken doch nicht zu verwenden).

Der DES-Algorithmus wird in der nächsten Folge beschrieben.

Carsten Eilers