Freitag, 8. Juni 2012


Topthema

Donnerstag, 7. September 2006 | Topthema

About Security #71: Kryptographie — Data Encryption Standard (DES)

(Link zum Artikel: http://www.entwickler.de/jaxenter/kolumnen/031145)
  • Teilen
  • kommentieren
  • empfehlen
  • Bookmark and Share

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, sondern nur aktualisierte Fassungen: FIPS PUB 46-2 und FIPS PUB 46-3 (PDF).

N E U ! Security aktuell
T�glich aktuelle Security-Infos!

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 IP (Initial Permutation), die u.a. den Klartextblock in die beiden 32-Bit-Bl�cke L_0 und R_0 zerlegt,
  • 16 Iterationsrunden, in denen die eigentliche Verschl�sselung erfolgt, und
  • einer zur Eingangspermutation inversen Ausgangspermutation IP^-1, vor deren Ausf�hrung die Ergebnisse der 16. Iterationsrunde, L_16 und R_16, nochmals vertauscht werden.

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

Ablauf des DES-Algorithmus

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 K_i.

Die Verschl�sselungsfunktion

Die Verschl�sselungsfunktion

Der 32-Bit-Block R_(i-1) wird durch die Expansionspermutation E auf 48 Bit erweitert. W�hrend eine Permutation einzelne Eingabewerte vertauscht, ohne ihre Werte oder Gesamtzahl zu ver�ndern, kommen bei einer Expansionspermutation manche Eingabewerte mehrfach in der Ausgabe vor.

About Security: Die komplette Serie

Danach wird der 48 Bit lange Teilschl�ssel K_i 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 S_1 bis S_8 (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 Teilschl�sselerzeugung

Eine permutierende Auswahlfunktion PC-1 (PC = permuted choice) w�hlt aus dem 64-Bit-Schl�ssel 56 Bits aus und teilt sie auf die beiden 28-Bit-Bl�cke C_0und D_0 auf. C_i und D_i (i=1, .., 16) werden erzeugt, indem die Bits in C_(i-1)und D_(i-1)abh�ngig von i um 1 oder 2 Stellen nach links rotiert werden (zyklischer Linksshift LS_i). Die Teilschl�ssel K_i werden dann gebildet, indem C_i und D_i verbunden und daraus durch die permutierende Auswahlfunktion PC-2 48 Bits ausgew�hlt werden.

Die S-Boxen

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

Beispiel: Die S-Box S_1:

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 LS_iTeil 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, 2^56 = 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.

Wenn Sie Fragen oder Themenvorschl�ge haben, k�nnen Sie diese gerne an die angegebene E-Mail-Adresse senden oder im Security-Forum einbringen!

Carsten Eilers

About Security � �bersicht zum aktuellen Thema "Kryptographie � DES"

Kommentare

Folgende Links könnten Sie auch interessieren