DES: Der Data Encryption Standard

Inhaltsverzeichnis

Wichtige Begriffe

1 Einleitung

2 Geschichte

3 Der Algorithmus
3.1 Die Funktion DES
3.2 Die Funktion KS
3.3 Die Funktion f
3.4 Die Funktionen S1 bis S8
3.5 Entschlüsselung
3.6 Anwendung und Operationsmodi
3.6.1 Electronic Codebook Modus
3.6.2 Cipher Block Chaining Modus
3.6.3 Cipher Feedback Modus
3.6.4 Output Feedback Modus
3.6.5 Auswirkung von Störungen

4 Varianten
4.1 Triple-DES
4.2 DESX
4.3 NewDES
4.4 Biham-DES
4.5 Generalized-DES

5 Sicherheit
5.1 Schlüssel
5.2 Funktion f
5.3 Anzahl der Runden

6 Risiken
6.1 Schlüsselraum
6.2 Schlüsselverteilung

7 Einsatz
7.1 Beispiel XY-Versicherung
7.2 Bibliotheken

8 Zukunft

9 Zusammenfassung

10 Anhang
10.1 Permutation
10.2 Bijektivität
10.3 XOR
10.4 Paritätsbit

11 Verzeichnisse
11.1 Tabellenverzeichnis
11.2 Abbildungsverzeichnis
11.3 Literaturverzeichnis

Wichtige Begriffe

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Die Geschichte der Kryptologie ist sehr alt. Bereits vor circa 2400 Jahren nutzten die Griechen die so genannte Skytala zur militärischen Datenübermittlung. Das Verfahren nutzte ein dünnes Papyrusband und einen Stab zur Ver- bzw. Entschlüsselung. Dabei wurde das Band so um den Stab gewickelt, dass es entlang dem Stab beschrieben werden konnte. Wickelte man das Band ab, war die Nachricht ohne weiteres nicht mehr zu entschlüsseln (stellt man sich die Buchstaben als Einträge in einer Matrix vor, ist das Ergebnis des Verfahrens nichts anderes als die transponierte Matrix). Der Schlüssel lag bei diesem Verfahren allein im Durchmesser des verwendeten Stabs und war dementsprechend nicht besonders sicher.

Heutige Verschlüsselungsverfahren sind komplexer und aufwendiger zu berechnen, da unsere Möglichkeiten sie anzugreifen, durch die immer schneller und leistungsstärker werdenden Computer, ständig steigen. Beispielsweise ist es durch reines „Durchprobieren“ aller denkbaren Schlüssel möglich, Passwörter von Benutzern auf Windowssystemen in wenigen Minuten zu finden (einen solcher Angriff, bei dem einfach alle möglichen Schlüssel ausprobiert werden, bezeichnet man als Brute Force Angriff oder Brute Force Attacke).

Ein Verschlüsselungsverfahren, welches dieser Entwicklung Rechnung trug, jedoch mittlerweile selbst wieder abgelöst wurde, ist das im Folgenden beschriebene symmetrische, das bedeutet, dass zum ver- und entschlüsseln der gleiche Schlüssel verwendet wird, Blockverschlüsselungsverfahren DES (Data Encryption Standard).

2 Geschichte

In den sechziger Jahren wurden in den USA Computer immer billiger, so dass sich bald jedes Unternehmen einen eigenen Computer leisten konnte. Es wurden viele verschiedene Verschlüsselungssysteme entwickelt, die miteinander nicht kompatibel waren. Für den Datenaustausch zwischen den Nutzern verschiedener Systeme wurde diese Tatsache bald zu einem Problem (Singh, 2004, S. 301).

1972 rief das National Bureau of Standards (NBS) die Fachwelt in Form einer öffentlichen Ausschreibung dazu auf, ein normierbares Verschlüsselungsverfahren zu entwickeln. Der zu entwickelnde Algorithmus sollte folgende Eigenschaften besitzen (NIST, 1981):

- Hohe Sicherheit
- Komplett spezifiziert und leicht zu verstehen
- Sicherheit liegt allein im Schlüssel
- Für jeden verfügbar
- Verwendbar in diversen Anwendungen
- Leichte und wirtschaftliche Implementation in Hardware
- Frei zugänglich/Open source
- Exportierbarkeit

Die auf den ersten Aufruf hin eingereichten Vorschläge waren jedoch allesamt unzureichend, so dass 1974 ein zweiter Aufruf gestartet wurde. Auf diesen zweiten Aufruf hin reichte IBM das so genannte Lucifer-Verfahren ein, welches von dem deutschen Emigranten Horst Feistel entwickelt worden war. IBM verzichtete dabei gleichzeitig auf bereits beantragte Patentrechte an dem Verfahren. Das Lucifer-Verfahren galt als sicher und wurde bereits in verschiedenen Unternehmen eingesetzt. Trotzdem wurde nach einer Analyse durch die National Security Agency (NSA) die Schlüssellänge nachträglich von 128-Bit auf 56-Bit gekürzt.

1975 wurde der Algorithmus in der, durch die NSA modifizierten Version veröffentlicht. Die Fachwelt kritisierte damals haupt-sächlich die geringe Schlüssellänge und die Geheimhaltung der NSA-Designgrundsätze. Die Veröffentlichung des modifizierten Lucifer-Verfahrens war die erste vollständige Veröffentlichung eines Verschlüsselungsalgorithmus.

Am 15.07.1977 schließlich trat der Federal Information Processing Standard (FIPS) 46 mit dem Namen „Data Encryption Standard“ (DES) als offizieller Standard für die Verschlüsselung von nicht geheimen Nachrichten in Kraft. In den Jahren 1983, 1988, 1993 und 1999 wurde der Standard erneut zertifiziert. In keinem anderen Land jedoch wurde das Verfahren zum Standard erhoben (Atterer, 1998).

Am 02.12.1980 wurde ein Standard (FIPS-81) für die Operations-modi des DES vom National Institute of Standards and Technology veröffentlicht (NIST, 1980). Ein Standard für die Implementierung und Benutzung des DES (FIPS-74) wurde am 01.04.1981 veröffentlicht (NIST, 1981).

3 Der Algorithmus

Abbildung 10 zeigt schematisch, wie Daten nach dem Data Encryption Standard verschlüsselt werden. Eine genaue Beschreibung des Verfahrens erfolgt im Anschluss.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1: Schematische Darstellung des DES Algorithmus (eigene Darstellung)

Als Input werden die zu verschlüsselnden Daten in 64-Bit Blöcke zerlegt und einzeln verschlüsselt. Zur Verschlüsselung wird ein 64-Bit Schlüssel verwendet. Von diesem Schlüssel sind jedoch nur 56 Bit relevant wie wir weiter unten sehen werden.

Im Folgenden betrachten wir den Data Encryption Standard als Funktion DES, welche für jedes ihr übergebene m zusammen mit einem ihr übergebenen Schlüssel K ein c berechnet. Also:

c = DES(m, K)

Wobei m, c und K jeweils 64-Bit Blöcke darstellen.

3.1 Die Funktion DES

c = DES(m, K)

c - Verschlüsselte Daten (Output), 64 Bit

m - Eingabedaten (Input) , 64 Bit

K - Schlüssel, 64 Bit

Die folgende Abbildung zeigt schematisch den Aufbau der Funktion DES:

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2: Schematische Darstellung der Funktion DES (eigene Darstellung)

Als erstes wird in dieser Funktion m einer so genannten Eingangs-Permutation (siehe 10.1) IP unterzogen. Diese Permutation trägt jedoch nicht zu einer höheren Sicherheit des Algorithmus bei, da sie am Ende wieder rückgängig gemacht wird (siehe unten).

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: IP Permutation

Diese Tabelle ist so zu verstehen, dass nach der Permutation an erster Stelle das Bit Nummer 58 aus m steht. An zweiter Stelle das Bit Nummer 50 und so weiter, an letzter Stelle befindet sich dann das Bit Nummer 7 aus m.

Zu beachten ist hier, dass mit der Nummerierung bei Eins und nicht, wie in der Informatik und Mathematik sonst üblich, bei Null begonnen wird.

Als nächstes wird m in zwei 32-Bit Blöcke geteilt. Es entstehen L0 und R0. Nun folgt der Erste von 16 Durchgängen in denen die beiden Blöcke Li und Ri immer wieder vertauscht und verändert werden.

Bei einem Durchgang i (0<i<17) wird zunächst Ri-1 ohne Veränderung als Li übernommen. Dann wird f(Ri-1, KS(i, K)) berechnet und über XOR (Abbildung in dieser Leseprobe nicht enthalten, siehe 10.3) mit Li-1 verknüpft. Das Ergebnis liefert dann Ri (die Funktionen KS und f werden weiter unten erläutert).

Nach diesem Schema werden in 16 Durchgängen R1, R2, … , R16 und L1, L2, ... , L16 berechnet, die danach wieder zu einem 64-Bit Block zusammengefasst werden. Dieser Block wird dann der Permutation IP-1 unterzogen, welche die Eingangs-Permutation IP wieder rückgängig macht.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: IP-1 Permutation

Das Ergebnis ist dann das zu berechnende c.

3.2 Die Funktion KS

Ki = KS(i, K)

K - Schlüssel, 64 Bit

i - Durchgangsnummer

Ki - Durchgangsschlüssel, 48 Bit

Die folgende Abbildung zeigt schematisch den Aufbau der Funktion KS:

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3: Schematische Darstellung der Funktion KS (eigene Darstellung)

Die Funktion KS unterzieht den ihr übergebenen 64-Bit Schlüssel K zunächst der Permutation PC-1. Die Permutation PC-1 ist in der folgenden Tabelle beschrieben:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: PC-1 Permutation

Zu beachten ist, dass die Permutation PC-1 nur 56 Bit aus K auswählt. Die restlichen Bits sind Paritätsbits (siehe 10.4) und dienen zur Fehlererkennung.

Danach werden die 56 Bit aufgeteilt. Es entstehen so C0 und D0 mit jeweils 28 Bit. Ci und Di werden nach der folgenden Tabelle, abhängig von der Durchgangsnummer, einem oder zwei so genannten Leftshifts unterzogen.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4: Durchgangsnummer und Anzahl der Leftshifts

Ein Leftshift um ein Bit bedeutet, dass das Bit, welches vorher an Position 2 stand auf die Position 1 rückt, das Bit an Position drei auf zwei und so weiter. Das erste Bit wird als letztes angefügt. Man kann einen Leftshift (für einen 28 Bit Block) auch als Permutation nach folgender Tabelle darstellen:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5: Leftshift Permutation (28 Bit)

Das Ergebnis nach dem Leftshift (oder den zwei Leftshifts) bildet die Ausgangsdaten für den nächsten Durchgang.

Das Ergebnis des aktuellen Durchgangs liefert die Funktion KS indem sie Ci und Di, zusammengefasst zu einem 56-Bit Block, der Permutation PC-2 unterzieht. Die Permutation PC-2 ist in der folgenden Tabelle dargestellt:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 6: PC-2 Permutation

Wie in der Tabelle zu ersehen ist, werden die Daten durch die PC-2 Permutation von 56 auf 48 Bit reduziert. Dieses 48-Bit Ergebnis ist Ki, der von der Funktion KS produzierte Schlüssel für den Durchgang i.

[...]