entwickler.com

Diesmal geht es um den Algorithmus des DES-Verfahrens. Seine erste Veröffentlichung erfolgte am 15. Januar 1977 in Specification for the Data Encryption Standard; Federal Information Processing Standards Publication 46 (FIPS PUB 46). Die erste Version ist leider nicht online verfügbar, sondern nur aktualisierte Fassungen: FIPS PUB 46-2 und FIPS PUB 46-3 (PDF).

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.

Der DES-Algorithmus besteht aus

• einer kryptographisch bedeutungslosen Eingangspermutation (Initial Permutation), die u.a. den Klartextblock in die beiden 32-Bit-Blöcke und zerlegt,
• 16 Iterationsrunden, in denen die eigentliche Verschlüsselung erfolgt, und
• einer zur Eingangspermutation inversen Ausgangspermutation , vor deren Ausführung die Ergebnisse der 16. Iterationsrunde, und , nochmals vertauscht werden.

Aus dem Schlüssel werden die 16 Teilschlüssel bis erzeugt, einer für jede Iterationsrunde.

Die Iterationsrunden entsprechen den in About Security #70 vorgestellten Runden der Feistel-Netzwerke. Die für die Entschlüsselung notwendige Vertauschung erfolgt nach der 16. Iterationsrunde, der DES-Algorithmus kann also unverändert sowohl zur Ver- als auch Entschlüsselung genutzt werden. Die zum Entschlüsseln notwendige Umkehrung der Reihenfolge der Iterationen erfolgt durch die Umkehrung der Reihenfolge der Teilschlüssel .

Die Verschlüsselungsfunktion

Danach wird der 48 Bit lange Teilschlüssel bitweise modulo 2 hinzuaddiert.

Die Summe wird in acht 6-Bit-Blöcke aufgeteilt, mit denen jeweils ein 4-Bit-Wert aus einer der Substitutionsboxen bis (S-Boxen, substitution box) ausgewählt wird. Diese Substitutionsboxen ordnen Werten von 6-Bit-Blöcken Werte von 4-Bit-Blöcken zu und sorgen so für Nichtlinearität.

Die sich ergebenden acht 4-Bit-Werte werden zu einem 32-Bit-Wert zusammengefasst. Auf das Ergebnis wird die Permutation P angewendet, die dann das Ergebnis liefert. P mischt die Ausgaben der 8 Substitutionsboxen, damit in der nächsten Runde die Ausgabe jeder Substitutionsbox in mehrere Substitutionsboxen eingeht.

Die Teilschlüsselerzeugung

Die S-Boxen
Jede S-Box ist eine Tabelle mit 4 Zeilen und 16 Spalten. Wenn die Eingabe aus den 6 Bits , ..., besteht, bestimmt die aus und gebildete Zahl (2 Bits = 4 Werte) die Tabellenzeile, die aus bis gebildete Zahl die Tabellenspalte. Die Zahl in der entsprechenden Zeile und Spalte wird ausgegeben.

Beispiel: Die S-Box :

Spalte   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
Zeile
0       14   4  13   1   2  15  11   8   3  10   6  12   5   9   0   7
1        0  15   7   4  14   2  13   1  10   6  12  11   9   5   3   8
2        4   1  14   8  13   6   2  11  15  12   9   7   3  10   5   0
3       15  12   8   2   4   9   1   7   5  11   3  14  10   0   6  13

Die S-Boxen sind ebenso wie die Permutationen und Teil des Standards. Da es schwierig ist, die S-Boxen so zu entwerfen, dass der entstehende Algorithmus kryptologisch sicher ist, soll ihre Berechnung einige Monate gedauert haben. Ihre Entwurfskriterien wurden anfangs geheim gehalten und erst nach der Entdeckung der differentiellen Kryptanalyse durch Eli Biham und Adi Shamir 1990 (.ps.gz) veröffentlicht. Sie sind z.B. in Bruce Schneiers Buch Applied Cryptographie nachzulesen.

Die Sicherheit von DES
Es sind drei mögliche Angriffe gegen DES bekannt:

• Bei einem Brute-Force-Angriff werden alle möglichen Schlüssel, = ca. 72 Billiarden, ausprobiert. Dies ist inzwischen machbar. So wurde z.B. 1998 von der EFF ein speziell für das Brechen von DES entwickelter Rechner, der 'DES Cracker', gebaut, der pro Sekunde etwa 88 Milliarden Schlüssel testen konnte.
• Die S-Boxen erschweren eine differentielle Kryptanalyse, bei der die Auswirkung von minimalen Änderungen am Klartext auf den Geheimtext untersucht werden. Daher ist differentielle Kryptanalyse nicht schneller als ein Brute-Force-Angriff.
• Lineare Kryptanalyse, eines der modernsten kryptanalytischen Verfahren, wurde 1993 von Mitsuru Matsui entwickelt und liefert bessere Ergebnisse.

DES muß inzwischen als unsicher angesehen werden. Verbesserungen und die Anwendung des Algorithmus sind das Thema der nächsten Folge.

Carsten Eilers