Home > Kryptographie > Moderne Kryptographie > DES
Kryptographie
1973/74 initiierte das National Bureau of Standards (NBS, heute NIST) den Wettbewerb für ein Verschlüsselungs-Verfahren, um begrenzten Schutz bei der Übermittlung nichtgeheimer Daten zu erreichen. 1977 wurde der DES, entwickelt von IBM, zum Standard erklärt. Um dieses Verfahren ranken sich so einige Gerüchte, vor allem weil die NSA ihre Finger mit im Spiel hatte und DES absichtlich geschwächt haben soll. Aber dazu später mehr. DES war ursprünglich für den Einsatz in Hardware gedacht (DES-Chips), kann aber auch in Software implementiert werden, wobei DES in Software vergleichsweise langsam ist.
Der DES-Algorithmus verschlüsselt immer einen Block von 64 Bit Länge. Solche Chiffrierungen nennt man auch Blockalgorithmen oder Blockchiffrierungen. Zunächst wird dieser Block in zwei Hälften L und R der Länge 32 Bit aufgeteilt. Diese Blöcke durchlaufen 16 Runden (dies ist übrigens eine magische Zahl in der Kryptographie – die meisten heutigen Verfahren orientieren sich an dieser Zahl), zum Schluss werden L und R zum 64-Bit-Chiffretext zusammengefasst. Die Schlüssellänge von DES beträgt 56 Bit (die eingehenden 64 Bit werden auf 56 Bit reduziert).
DES besteht aus vier Hauptkomponenten: Der Eingangsprozedur (Inital Permutation, IP), der Schlüsseleinteilung, dem zentralen Block, der 16-mal durchlaufen wird und der Ausgangspermutation (Inverse Permutation, PI). Hier ein kleiner Runden-Überblick:
Quelle: Claus Schönleber, Verschlüsselungsverfahren für PC-Daten
Wie bereits erwähnt verschlüsselt DES immer einen Block der Länge 64 Bit auf einmal. Damit wird vorausgesetzt, dass die Daten bereits in Bitform vorliegen. Dazu müssen sie ggf. umgewandelt werden. Computer-Daten liegen jedoch immer in Bitform vor, so dass sich alles problemlos verschlüsseln lässt – ob Bilder, Sounds, Texte, ausführbare Dateien etc. Die sog. Eingangspermutation erfolgt vor der ersten Runde. Sie ist eigentlich überflüssig, da sie nachgewiesenermaßen nicht die Sicherheit des Verfahrens beeinflusst; sie dient nur dazu, den Klartext und Chiffretext byteweise in den DES-Chip (DES war eigentlich für den Einsatz in Hardware entworfen worden) zu laden. Dabei vertauscht man die Bitpositionen mit Hilfe einer vorgegebenen sog. S-Box (= Substitutions-Box). Dieses "Array" (Feld) enthält Permutationen der Zahlen 1 .. 64. Zum Beispiel rutscht Bit 58 auf Bitposition 1, Bit 50 auf Position 2, Bit 42 auf 3 usw.
Dies ist der Hauptteil, da hier die eigentliche Verschlüsselung stattfindet. Am Anfang wird der 64-Bit-Schlüssel mit Hilfe einer Box reduziert, wobei jedes achte Bit wegfällt. Dann werden die sog. Teilschlüssel aus dem 56-Bit-Schlüssel generiert, d. h. für jede Runde ein Schlüssel (genannt Ki, wobei i der Runde entspricht). Dazu zerlegt man den Schlüssel in zwei Hälften der Länge 28 Bit und verschiebt diese zyklisch um ein oder zwei Bit – je nach aktueller Rundennummer. In der 1. und 2. Runde z. B. um 1 Bit, in der 3. bis 8. Runde um 2 Bit usw. (sieheTabelle) Nach dieser Verschiebung werden 48 der 56 Bits ausgewählt (Kompressionspermutation). Zum Beispiel landet Bit 33 des Schlüssels auf Position 35 der Ausgabe, das Bit auf Position 18 wird ignoriert.
Runde 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Anzahl 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
Anzahl der Bits, um die der Schlüssel in jeder Runde verschoben wird
Zunächst wird hier der Block, der gerade die Eingangspermutation durchlaufen hat, in zwei Hälften Ki und Ri der Länge 32 Bit zerlegt, wobei i die aktuelle Runde ist. Zu Beginn der Runde findet die sog. Expansionspermutation statt, die die 32 Bits von Ri auf 48 Bits expandiert, d. h. erweitert. Der kryptographische Zweck dieser Operation ist der sog. Lawineneffekt. Da ein Bit zwei Substitutionen beeinflusst, wirken sich die Eingabebits schneller auf die Ausgabebits aus. Dadurch wird schon nach fünf Runden ein Zustand erreicht, in dem jedes Bit des Chiffretextes von jedem Bit des Klartextes und jedem Bit des Schlüssel abhängt.
Danach wird der komprimierte Teilschlüssel Ki mit dem expandierten Block per xor verknüpft.
Auf diese Operation folgt die sog. S-Box-Substitution. DES besitzt acht S-Boxen, von denen jede 6 Bit Eingabe erhält und 4 Bit Ausgabe liefert. Die 48 Bits Resultat der xor-Operation werden in acht Teilblöcke der Länge 6 Bit zerlegt. Der erste Teilblock wird von S-Box 1 bearbeitet, der zweite von S-Box 2 usw. Jede S-Box besteht aus einer Tabelle mit vier Zeilen und 16 Spalten. Jeder Tabelleneintrag enthält eine 4 Bit lange Zahl. Die 6 Eingabebits legen fest, welcher Spalte und Zeile die Ausgabe zu entnehmen ist. Als Beispiel betrachten wir eine Eingabe von 110011 auf die sechste S-Box. Das erste und letzte Bit ergeben zusammen 11, also wählen wir Zeile 3 (die dezimale Darstellung von "11") der S-Box. Die mittleren vier Bits ergeben 1001, was Spalte 9 der gleichen S-Box bedeutet. Der Eintrag in Zeile 3 und Spalte 9 der S-Box lautet 14. Übrigens werden die Spalten nicht ab 1, sondern ab 0 gelesen! Also ist für 110011 der Wert 1110 zu substituieren. Die acht 4-Bit-Resultate werden wieder zu einem einzelnen Block der Länge 32 Bit kombiniert, auf den die sog. P-Box-Permutation angewandt wird.
Und so sehen die acht S-Boxen S1 bis S8 von DES aus:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07
1 00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08
S1 2 04 01 14 08 13 06 02 11 15 12 09 07 03 10 05 00
3 15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13
0 15 01 08 14 06 11 03 04 09 07 02 13 12 00 05 10
1 03 13 04 07 15 02 08 14 12 00 01 10 06 09 11 05
S2 2 00 14 07 11 10 04 13 01 05 08 12 06 09 03 02 15
3 13 08 10 01 03 15 04 02 11 06 07 12 00 05 14 09
0 10 00 09 14 06 03 15 05 01 13 12 07 11 04 02 08
1 13 07 00 09 03 04 06 10 02 08 05 14 12 11 15 01
S3 2 13 06 04 09 08 15 03 00 11 01 02 12 05 10 14 07
3 01 10 13 00 06 09 08 07 04 15 14 03 11 05 02 12
0 07 13 14 03 00 06 09 10 01 02 08 05 11 12 04 15
1 13 08 11 05 06 15 00 03 04 07 02 12 01 10 14 09
S4 2 10 06 09 00 12 11 07 13 15 01 03 14 05 02 08 04
3 03 15 00 06 10 01 13 08 09 04 05 11 12 07 02 14
0 02 12 04 01 07 10 11 06 08 05 03 15 13 00 14 09
1 13 11 02 12 04 07 13 01 05 00 15 10 03 09 08 06
S5 2 04 02 01 11 10 13 07 08 15 09 12 05 06 03 00 14
3 11 08 12 07 01 14 02 12 06 15 00 09 10 04 05 03
0 12 01 10 15 09 02 06 08 00 13 03 04 14 07 05 11
1 10 15 04 02 07 12 09 05 06 01 13 14 00 11 03 08
S6 2 09 14 15 05 02 08 12 03 07 00 04 10 01 13 11 06
3 04 03 02 12 09 05 15 10 11 14 01 07 06 00 08 13
0 04 11 02 14 15 00 08 13 03 12 09 07 05 10 06 01
1 13 00 11 07 04 09 01 10 14 03 05 12 02 15 08 06
S7 2 01 04 11 13 12 03 07 14 10 15 06 08 00 05 09 02
3 06 11 13 08 01 04 10 07 09 05 00 15 14 02 03 12
0 13 02 08 04 06 15 11 01 10 09 03 14 05 00 12 07
1 01 15 13 08 10 03 07 04 12 05 06 11 00 14 09 02
S8 2 07 11 04 01 09 12 14 02 00 06 10 13 15 03 05 08
3 02 01 14 07 04 10 08 13 15 12 09 00 03 05 06 11
Die S-Boxen von DES
Diese Operation bildet jedes Eingabebit auf eine Ausgabeposition ab. Kein Bit wird zweimal verwendet und keines ignoriert, d. h. die Bits werden einfach nur umgeordnet. Dies nennt man auch Permutation oder Transformation. Diese Begriffe haben Sie hier kennengelernt. Beispiel: Bit 21 wandert auf Position 4, Bit 4 dagegen auf Position 31.
Schließlich wird das Ergebnis der P-Box-Permutation noch mit der linken Hälfte (Li) des ursprünglichen 64-Bit-Blocks xor-verknüpft. Dann werden die linke und rechte Hälfte vertauscht, und die nächste Runde beginnt. Den zentralen Block kann man auch als f-Funktionen bezeichnen und entspricht daher dem "F" in der Abbildung.
Die Schlusspermutation ist invers zur Eingangspermutation, d. h. die "umgekehrte" Version der Eingangspermutation. Beachten Sie, dass die linke und rechte Hälfte nach der letzten Runde nicht mehr vertauscht werden! Statt dessen dient der zusammengesetzte Block L16R16 als Eingabeblock.
Die Entschlüsselung funktioniert praktisch genauso wie die Verschlüsselung, nur werden die Schlüssel in umgekehrter Reihenfolge angewandt. Die Teilschlüssel K16, K15, K14 ... K1 dienen also als Schlüssel für die Runden 1, 2, 3, ... 16. Außerdem wird der Schlüssel wie bei der Verschlüsselung nach rechts verschoben, und zwar um 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 Positionen.
DES ist ein sog. Feistel-Netzwerk. Die meisten Blockalgorithmen haben diese Form. Man nimmt einen Block der Länge n Bit und teilt ihn in zwei Hälften L und R, die jeweils die Länge n/2 haben. Nun führt man eine bestimmte Anzahl von Runden durch, bei der die Ausgabe der i-ten Runde durch die Ausgabe der vorherigen Runde bestimmt wird (man sagt auch, man iteriert eine Blockchiffrierung):
Li = Ri − 1
Ri = Li − 1 xor f(Ri − 1, Ki)
Ki ist dabei der Teilschlüssel der i-ten Runde und f eine beliebige Rundenfunktion (in DES ist das z. B. der zentrale Block, der als Eingabe die rechte Hälfte R und einen Teilschlüssel erhält). Das Besondere an diesem Konzept ist es, dass die Funktion mit Sicherheit umkehrbar ist. Da die linke Hälfte per xor mit der Ausgabe der Rundenfunktion verknüpft wird, gilt:
Li − 1 xor f(Ri − 1, Ki) xor f(Ri − 1, Ki) = Li − 1
Die Funktion f kann noch so kompliziert sein, Hauptsache jedoch ist, dass nur die Eingabewerte für f in jeder Runde rekonstruiert werden können.
Übrigens existiert auch noch das sog. Extended Feistel-Network, d. h. ein erweitertes Feistel-Netzwerk, das mit beliebig vielen Subblöcken (z. B. A, B, C und D) arbeiten kann.
In DES und in einigen anderen modernen Algorithmen gibt es sog. schwache Schlüssel, die aus der Art und Weise, wie DES Schlüssel generiert, resultieren. Zum Beispiel wird in jeder Runde der gleiche Schlüssel benutzt, wenn der Schlüssel entweder nur aus Nullen oder Einsen besteht, oder wenn die Hälfte des Schlüssels aus Einsen und die andere Hälfte aus Nullen besteht. Insgesamt gibt es 64 schwache, halbschwache und möglicherweise schwache Schlüssel. Die Chance, einen dieser Schlüssel zu erwischen, ist sehr gering, nämlich 1 zu 250. Man kann diese Schlüssel auch bei der Schlüsselgenerierung aussondern.
Die Sicherheit von DES wurde lange Zeit in Frage gestellt. Der NSA, die an der Entwicklung beteiligt war, wurde vorgeworfen, die Schlüssellänge absichtlich auf 56 Bit reduziert zu haben, obwohl von IBM anfangs 112 Bit vorgeschlagen wurden. Auch kam der Verdacht auf, man habe eine sog. "Hintertür" eingebaut, die es der NSA ermöglichte, ohne Kenntnis des Schlüssels und mit geringem Arbeitsaufwand an den Klartext zu gelangen. Des Weiteren stellte sich die Frage, warum die S-Boxen genau diese Struktur haben und keine andere. Über die Jahre stellte sich jedoch heraus, dass die angewandten kryptographischen Techniken gut sind – nur störte immer noch die zu kurze Länge des Schlüssels.
Bis 1990 gab es keine erfolgreiche Methode zum Knacken von DES. Doch dann führten Eli Biham und Adi Shamir, zwei israelische Kryptologen, die sog. differentielle Kryptoanalyse vor, die effizienter als ein Brute-Force-Angriff ist. Gleichwohl stellte sich heraus, dass DES äußerst widerstandsfähig gegenüber dieser Attacke war, so dass der Verdacht aufkam, man habe diesen Angriff schon vorher gekannt. Und tatsächlich: Donald Coppersmith, einer der Mitentwickler von DES gab zu, das Verfahren natürlich schon vorher gekannt zu haben, aber an ein Schweigegebot gebunden war. Da dieser Angriff gegen alle Verfahren mit konstanten S-Boxen angewandt werden kann, hätte eine Offenlegung des Verfahrens "den Vorsprung, den die Vereinigten Staaten auf dem Gebiet der Kryptographie gegenüber anderen Ländern haben, gefährdet". Obwohl die differentielle Kryptoanalyse auf DES angewandt kann, ist der Angriff praktisch sehr schwer – wenn nicht unmöglich – durchzuführen. Der Angriff benötigt sehr viel Geheimtext und viel Speicherplatz, und ein Angriff gegen DES mit 16 Runden ist sowieso ineffizienter als Brute Force.
Heute kann DES nicht mehr als sicher angesehen. Mit genug Geld zur Verfügung wäre DES bereits innerhalb weniger Millisekunden knackbar. Die Frage ist, ob die NSA DES schon bei der Veröffentlichung knacken konnte. Fakt ist, dass die Schlüssellänge ursprünglich auf 112 Bit angesetzt war, dann jedoch, vermutlich auf Anraten der NSA, verkürzt wurde, obwohl sich viele Kryptographen für die längere Variante einsetzten. Heute wird DES (hoffentlich!) nur noch als sog. Triple-DES eingesetzt.
Von Triple-DES gibt es mehrere Varianten, die von dem Kryptologen Tuchman vorgestellt wurden. Die grundlegende Idee ist, einen Klartextblock dreimal mit zwei unterschiedlichen Schlüsseln zu verschlüsseln: Zuerst verschlüsseln mit Schlüssel 1, dann entschlüsseln (!) mit Schlüssel 2 und schließlich noch einmal verschlüsseln mit Schlüssel 1. Dieses System wurde so gewählt, dass es nicht anfällig für einen sog. meet-in-the-middle-Angriff ist. Übrigens bezeichnet man dieses Verfahren auch als EDE (Encryption-Decryption-Encryption)-Modus. Dieses Verfahren verwendet eine Schlüssellänge von 112 (2 · 56) Bit für DES.
Die EDE-Methode mit drei unterschiedlichen Schlüsseln stellt die andere Triple-DES-Variante dar: Im letzten Schritt verschlüsselt man nicht wieder mit Schlüssel 1, sondern mit Schlüssel 3. Für DES beträgt die Schlüssellänge dann 168 (3 · 56) Bit. Beide Triple-DES-Varianten sind vergleichsweise langsam, und Krypto-Programme bevorzugen modernere und vor allem schnellere Algorithmen.
 Zurück |
nach oben |
 |
 Übersicht |
Weiter  |
Letzte Änderung: 04.12.2001
© 2002 by Christian Thöing