Data Encryption Standard

Der Data Encryption Standard (Abkürzung: DES) ist ein weit verbreiteter symmetrischer Verschlüsselungsalgorithmus.

Der DES-Algorithmus wurde als offizieller Standard für die US-Regierung (siehe FIPS 46) im Jahr 1976 bestätigt und wird seither international vielfach eingesetzt. Seine Entstehungsgeschichte hat wegen der Beteiligung der NSA am Design des Algorithmus immer wieder Anlass zu Spekulationen über seine Sicherheit gegeben. Heute wird DES aufgrund der verwendeten Schlüssellänge von nur 56 Bits für viele Anwendungen als nicht ausreichend sicher erachtet.

Die Schlüssellänge kann durch Mehrfachanwendung des DES jedoch leicht vergrößert werden. Als Triple-DES, TDES oder 3DES wird der DES weiterhin am häufigsten, zum Beispiel von Banken in Chipkartenanwendungen, eingesetzt, obwohl der TDES als offizieller Standard für die USA durch den Advanced Encryption Standard (AES) abgelöst wurde.

Geschichte

Zu Beginn der 1970er-Jahre war zwar die militärische Kryptologie auf einem hohen Niveau, für nichtmilitärische Anwendungen waren jedoch kaum brauchbare Produkte verfügbar. Das National Bureau of Standards (NBS) der USA – heute National Institute of Standards and Technology (NIST) – sah Bedarf für einen einheitlichen Standard für die behördenübergreifende Verschlüsselung vertraulicher Daten. Nach Beratungen mit der NSA veröffentlichte es am 15. Mai 1973 im amerikanischen „Federal Register“ eine Ausschreibung. Insbesondere sollte die Sicherheit des Algorithmus gemäß dem Kerckhoffs-Prinzip nur von seinem geheimen Schlüssel, nicht aber von der Geheimhaltung des Algorithmus abhängen. Keiner der eingereichten Kandidaten erfüllt jedoch die gestellten Bedingungen was zu einer neuerlichen Ausschreibung am 27. August 1974 führte.

IBM lieferte einen vielversprechenden Vorschlag, der auf einer Weiterentwicklung des wenige Jahre zuvor unter der Mitarbeit von Horst Feistel entwickelten Algorithmus „Lucifer“ beruhte. Dieser Algorithmus zeichnete sich dadurch aus, dass er einfache logische Operationen auf kleinen Bitgruppen nutzte und dadurch leicht in Hardware implementierbar war. Neben Feistel selbst waren auch Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith und Bryant Tuckerman Teil des IBM-Entwicklungsteams.

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 statt 128 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.

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 ein Hintertür eingebaut, welche das Verfahren dergestalt schwächt, dass sie damit verschlüsselte Nachrichten lesen konnten. 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:

„In the development of DES, NSA convinced IBM that a reduced key size was sufficient; indirectly assisted in the development of the S-box structures; and certified that the final DES algorithm was, to the best of their knowledge, free from any statistical or mathematical weakness. […]

NSA did not tamper with the design of the algorithm in any way. IBM invented and designed the algorithm, made all pertinent decisions regarding it, and concurred that the agreed upon key size was more than adequate for all commercial applications for which the DES was intended.“

(deutsch: „Während der Entwicklung von DES überzeugte die NSA IBM davon, dass eine reduzierte Schlüssellänge ausreichend sei; half indirekt bei der Konstruktion der S-Boxen; und zertifizierte den entstehenden DES-Algorithmus als nach bestem Gewissen frei von statistischen und mathematischen Schwächen.[…]

Die NSA veränderte das Design des Algorithmus in keiner Weise. IBM entwarf und entwickelte diesen, traf alle sachdienlichen Entscheidungen und stimmte darin überein, dass die verkürzte Schlüssellänge mehr als adäquat für die vorgesehenen kommerziellen Verwendungen sei.“)

Walter Tuchman, ein weiterer DES-Entwickler, wird mit den Worten „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 eine einzige Leitung diktiert!“) zitiert.

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 gegen Blockchiffren, 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ärt: „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. Ein „Problem“, das durch die Mehrfachanwendung des DES mit unterschiedlichen Schlüsseln wie zum Beispiel im TDES jedoch leicht behoben werden kann.

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

Trotz der andauernden Kritik wurde DES 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 Standardisierungsorganisation International Organization for Standardization (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 Kryptografen 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 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 von 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“:

„Inoffiziell bezeichnete die NSA den DES als einen ihrer größten Fehler. Hätte die Behörde gewußt, daß die Einzelheiten herausgegeben und Softwareimplementierungen möglich wurden, hätte sie niemals zugestimmt. Mehr als alles andere revolutionierte DES die gesamte Kryptoanalyse. Jetzt gab es einen Algorithmus, den man untersuchen konnte – sogar einen, den die NSA als sicher bezeichnete.“^[1]

Chronologie

Datum		Ereignis
15. Mai	1973	Das NBS veröffentlicht eine erste Ausschreibung für ein standardisiertes Verschlüsselungsverfahren
27. August	1974	Das NBS veröffentlicht eine zweite Ausschreibung für ein standardisiertes Verschlüsselungsverfahren
17. März	1975	DES wird im „Federal Register“ veröffentlicht
August	1976	Erster Workshop zu DES
September	1976	Zweiter Workshop, welcher die mathematischen Grundlagen von DES behandelt
November	1976	DES wird als Standard zugelassen
15. Januar	1977	DES wird als FIPS-Standard „FIPS PUB 46“ veröffentlicht
	1983	DES wird das erste mal neu bestätigt
	1986	Videocipher II, ein aus DES basierendes Verschlüsselungssystem für Fernsehsatelliten wird von der HBO verwendet
22. Januar	1988	DES wird als „FIPS 46-1“ revalidiert, welches FIPS PUB 46 ersetzt
	1992	Biham und Shamir publizieren den ersten theoretischen Angriff mit gegenüber der Brute-Force-Methode verminderter Komplexität: die differentielle Kryptanalyse. Dieser Angriff erfordert jedoch unrealistische 2⁴⁷ frei gewählte Klartexte.
30. Dezember	1993	DES wird ein drittes Mal bestätigt, diesmal als „FIPS 46-2“
	1994	Die erste experimentelle Kryptanalyse von DES wird mittels linearer Kryptanalyse durchgeführt (Matsui, 1994)
Juni	1997	Das DESCHALL-Projekt bricht erstmals öffentlich eine mit DES verschlüsselte Nachricht
Juli	1998	Der DES-Knacker „Deep Crack“ der EFF bricht einen DES-Schlüssel binnen 56 Stunden
Januar	1999	Deep Crack und distributed.net brechen in einer Kooperation einen DES-Schlüssel in 22 Stunden und 15 Minuten
25. Oktober	1999	DES wid ein viertes Mal in Gestalt des „FIPS 46-3“ bestätigt. Dieser gibt als bevorzugte Anwendung 3DES an und erlaubt DES selbst nur für den Einsatz in veralteten Systemen
26. November	2001	Der Advanced Encryption Standard wird als „FIPS 197“ publiziert
26. Mai	2002	Der AES tritt in Kraft
26. July	2004	Im „Federal Register“ wird die Absetzung des FIPS 46-3 und verwandter Standards empfohlen
19. Mai	2005	NIST setzt den FIPS 46-3 außer Kraft

Funktionsweise

Bei DES handelt es sich um einen symmetrischen Algorithmus, das heißt zur Ver- und Entschlüsselung wird derselbe Schlüssel verwendet. DES funktioniert als Blockchiffre, das heißt jeder Block wird unter Verwendung des Schlüssels einzeln chiffriert, wobei die Daten in 16 Iterationen beziehungsweise Runden von Substitutionen und Transpositionen (Permutation) nach dem Schema von Feistel „verwürfelt“ werden. Die Blockgröße beträgt 64 Bits, das heißt ein 64-Bit-Block Klartext wird in einen 64-Bit-Block Chiffretext transformiert. Auch der Schlüssel, der diese Transformation kontrolliert, besitzt 64 Bits. Jedoch stehen dem Benutzer von diesen 64 Bits nur 56 Bits zur Verfügung; die übrigen 8 Bits (jeweils ein Bit aus jedem Byte) werden zum Paritäts-Check benötigt. Die wirkliche Schlüssellänge beträgt daher nur 56 Bits. Die Entschlüsselung wird mit dem gleichen Algorithmus durchgeführt wobei die einzelnen Rundenschlüssel in umgekehrter Reihenfolge verwendet werden.

Betriebsmodi

Der DES-Algorithmus beschreibt zunächst nur, wie ein Datenblock mit 64 Bits verarbeitet wird. Zur Verarbeitung einer Nachricht beliebiger Länge gibt es verschiedene so genannte Betriebsmodi: ECB, CBC, CFB, OFB. Diese Verfahren lassen sich auf jede Blockchiffre anwenden.

Die Nachricht wird in 64-Bit-Blöcke zerlegt. Beim ECB und CBC wird der letzte Block auf volle 64 Bits ergänzt bzw. ein weiterer Block angefügt. Zum Auffüllen wird die Bitfolge 1000… verwendet. Diese Paddingvorschrift ist eindeutig umkehrbar, das heißt, die Füllbits können nach dem Entschlüsseln wieder entfernt werden.

ECB – Electronic Code Book. Die Blöcke werden jeweils mit dem gleichen Schlüssel unabhängig von einander verschlüsselt.

CBC – Cipher Block Chaining Mode. Vor der Verschlüsselung wird der Klartextblock mit dem zuvor verschlüsselten Block verknüpft (XOR-Verknüpfung). Der erste Klartextblock wird dem Initialisierungsvektor IV verknüpft. Der IV wird zur Entschlüsslung benötigt, muss jedoch nicht geheim gehalten werden. Dadurch entsteht eine Verkettung (englisch chain) der Blöcke. Trotz dieser Verkettung wird bei einem Übertragungsfehler in einem Chiffrenblock nur der betroffene Block und der nachfolgende falsch entschlüsselt. Fehler/Manipulationen in einem Block wirken sich also bei der Entschlüsselung nur auf den fehlerhaften/manipulierten und den nächsten Block aus. Trotzdem gilt, dass durch eine einzige Änderung im Klartext sich alle nachfolgenden Blöcke in der Folge stark verändern. Ein Angreifer kann daher die Chiffre kaum unbemerkt verändern, ohne dass danach zwei Blöcke erkennbar manipuliert sind. In keinem Fall sind gezielte Veränderungen ohne Kenntnis des Schlüssels möglich. Durch Verwendung eines verschlüsselten Prüfwerts (zum Beispiel CRC) wird dies mit höchster Sicherheit ausgeschlossen.

OFB – Output Feedback Mode. In diesem Modus wird eine Zufallsfolge erzeugt. Dazu wird ein Initialisierungsvektor verschlüsselt, das Ergebnis erneut verschlüsselt etc. Die Verschüsselung erfolgt durch XOR-Verknüpfung der Zufallsfolge mit dem Klartext. Der IV darf nur einmalig verwendet werden. Diese Verfahren entspricht einer Stromchiffre vergleichbar zu RC4.

CFB – Cipher Feedback Mode. Hier wird wie beim OFB eine Zufallsfolge erzeugt und zur Verschlüsselung per XOR-Verknüpfung genutzt. Jedoch wird die Chiffre zur Berechnung der Zufallsfolge verwendet (daher die Bezeichnung Cipher Feedback).

Schwächen

Weil die Schlüssellänge nur 56 Bits beträgt, konnte DES bereits durch Brute Force-Angriffe gebrochen werden, indem systematisch alle möglichen Schlüssel (2⁵⁶ = ca. 72 Billiarden) getestet wurden. Es gibt die Vermutung, dass diese kleine Schlüssellänge absichtlich gewählt wurde, weil die NSA bereits in den 1970er Jahren genug Rechnerkapazität besaß, um diese Verschlüsselung zu brechen.

Die EFF baute 1998 eine etwa 250.000 Dollar teure Maschine mit dem Namen „Deep Crack“. Dieser Superrechner enthielt 1.536 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.

Geringfügige Schwächen

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

\operatorname {DES} _{K}(m)={\overline {\operatorname {DES} _{\overline {K}}({\overline {m}})}}

für alle Schlüssel

K

und alle Klartexte

m

,

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

Es existieren vier schwache Schlüssel $K$ mit der Eigenschaft, dass

\operatorname {DES} _{K}(\operatorname {DES} _{K}(m))=m

für alle Klartexte

m

.

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

\operatorname {DES} _{K_{1}}(\operatorname {DES} _{K_{2}}(m))=m

für alle Klartexte

m

.

In der Praxis lässt sich die Verwendung dieser Schlüssel jedoch leicht vermeiden, indem sie bei der Schlüsselerzeugung explizit ignoriert werden.

Anwendungen

Breite Anwendung findet der DES-Algorithmus bei Geldautomaten: Mithilfe des DES-Algorithmus und eines geheimen Schlüssels wird bereits in der Tastatur eine sogenannte PAC berechnet. Diese wird zusammen mit den Daten des Magnetstreifens (Kontonummer, Bankleitzahl, Gültigkeitszeitraum, …) zum Host des kontoführenden Instituts geschickt, dort wird die PIN entschlüsselt und verifiziert.

In der Anfangszeit der Geldautomaten wurde aus den Daten des Magnetstreifens (Kontonummer, Bankleitzahl, Gültigkeitszeitraum, …) und dem geheimen Schlüssel die PIN berechnet und das Ergebnis mit der Eingabe des Benutzers verglichen. Diese sogenannte offline PIN-Prüfung wird seit mehreren Jahren nicht mehr verwendet.

Die bis vor kurzem gültige US-Exportbeschränkung für den DES mit voller 56-Bit-Schlüssellänge wurde inzwischen aufgehoben.

Ersatz-Algorithmen

Triple-DES

Viele frühere DES-Nutzer benutzen jetzt Triple-DES (auch 3DES genannt), ein Verfahren, das vom DES-Mitentwickler Walter Tuchman beschrieben und analysiert wurde (siehe FIPS 46-3).

Dabei wird jeder Datenblock mit einem DES-Schlüssel $K_{1}$ chiffriert, dann mit $K_{2}$ dechiffriert und mit $K_{3}$ chiffriert:

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

Die Schlüssel $K_{1}$ , $K_{2}$ und $K_{3}$ können jeweils ein einfach langer DES-Schlüssel sein, oder $K_{1}$ und $K_{3}$ die linke Hälfte eines doppelt langen DES-Schlüssels und $K_{2}$ die rechte Hälfte. Bei einem dreifach langen Schlüssel sind $K_{1}$ , $K_{2}$ und $K_{3}$ der jeweilige Anteil des Schlüssels. Dieses Verfahren wird auch als EDE (Encrypt-Decrypt-Encrypt) bezeichnet. Eine einfache DES-Verschlüsselung ist somit ein Spezialfall von 3DES:

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

Da DES nicht abgeschlossen ist (das heißt, es gibt Schlüssel $K_{1}$ und $K_{2}$ , sodass $\operatorname {DES} _{K_{2}}\circ \operatorname {DES} _{K_{1}}\neq \operatorname {DES} _{K}$ für alle Schlüssel $K$ ), lässt sich damit die effektive Schlüssellänge tatsächlich steigern.

Die Schlüssellänge von 3DES ist mit 168 Bits dreimal so groß wie bei DES (56 Bits), wodurch die Schlüsselkomplexität um den Faktor $2^{112}$ gesteigert wird. Die effektive Schlüssellänge liegt aber nur bei 112 Bits, bedingt durch die Möglichkeit der sog. meet in the middle attack. Ist diese einem Angreifer nicht möglich, so liegt die Schlüssellänge bei 168 Bit. 3DES wird momentan als ähnlich sicher wie moderne Verschlüsselungsverfahren bei 128 Bits Schlüssellänge angesehen. Es ist dabei aber relativ langsam, da der Rechenaufwand durch die dreimalige Verschlüsselung hoch ist. Man beachte im Übrigen, dass es mehrere Methoden gibt, DES dreimal anzuwenden; Tuchmans 3DES ist nur eine davon.

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.

3DESE – Triple DES im Bereich PPP

Die im RFC 2420 definierte Protokollerweiterung 3DESE (Triple-DES Encryption Protocol Extension) ermöglicht über PPP (Point-to-Point Protocol) die gewohnte Triple-DES-Verschlüsselung.

Zitierte Quellen

↑ Bruce Schneier: Applied Cryptography, Protocols, Algorithms, and Source Code in C, 2. Auflage, John Wiley and Sons, New York (1996) p. 267

Literatur

Spektrum der Wissenschaft, Dossier Kryptographie (4/2001), S. 42–47
Klaus Schmeh, Die Welt der geheimen Zeichen, S. 197–211, W3L Verlag Bochum, 2004, ISBN 3-937-13790-4

Weblinks

DES- und TripleDES-Spezifikation des NIST (PDF) (englisch)
DES als JavaScript (inkl. Zwischenwerte des Algorithmus') (englisch)
DES Beschreibung im linux-magazin
Einfache Beschreibung von DES und Triple-DES mit Grafik
Algorithmus-DES, Verschlüsselung und Dekodierung – programmiert in C++
Detaillierte Darstellung von DES

Vorlage:Navigationsleiste Symmetrische Verschlüsselungsverfahren

Vorlage:Link FA

[1] Bruce Schneier: Applied Cryptography, Protocols, Algorithms, and Source Code in C, 2. Auflage, John Wiley and Sons, New York (1996) p. 267

[1]