6.2 DES

Mit dem Ziel, begrenzten Schutz bei der Übermittlung nicht geheimer Daten zu erreichen, initiierte das National Bureau of Standards (NBS) im US-amerikanischen Handelsministerium 1973/74 die Entwicklung eines entsprechenden Verschlüsselungsverfahrens. Den damit ausgeschriebenen Wettbewerb gewann das Verfahren Data Encryption Standard (DES) der Firma IBM, das eine Variante des Verfahrens Lucifer derselben Firma darstellte. Das NBS stellte DES im Jahre 1977 als Standard vor. Zu dieser Zeit gab es zwei Gründe für den Erfolg von DES:

Und obwohl DES zwischenzeitlich wohlbekannt war und in der Folgezeit auch kritisch und gründlich analysiert wurde, vor allem von "Konkurrenten" wie Adi Shamir, einer der Autoren von RSA, war vor allem eine Streitfrage entstanden:

Aus welchem Grunde hatten die S-Boxen (die Substitutionstabellen) gerade diese eine Struktur und keine andere?

Shamir machte sich ans Werk und versuchte, die Schwachstellen von DES zu ergründen. Im Jahre 1991 hatte er Erfolg: Er hatte eine Methode entwickelt, die für eine Analyse von DES nur noch 247 Vergleiche benötigte, 512mal weniger als vorher. Ein ungeheurer Sprung! Er soll danach gesagt haben, daß er DES sehr leicht knacken könnte, wenn er auch nur ein einziges Bit in den Tabellen ändern dürfe. Gleichwohl stellte sich für die Praxis heraus, daß DES mit seinen Originaltabellen sich gegenüber dieser neu entwickelten Methode äußerst widerspenstig entgegenstellte, so daß der begründete Verdacht aufkam, daß das Verfahren so entwickelt worden war, daß es gegen ebendiese Angriffe geschützt war. Shamir hatte aber doch das Verfahren erst 1991 entdeckt!

Kurz danach hat dann Donald Coppersmith, einer der Mitentwickler von DES, öffentlich zugegeben, die Methode natürlich schon vorher gekannt zu haben, jedoch an ein Schweigegebot gebunden war. Einer der Gründe war, daß das japanische Verfahren FEAL (Fast encryption algorithm) in all seinen Versionen ebendiesem Angriff nicht standhielt und so jahrelang relativ problemlos geknackt werden konnte. Ein weiterer Beweis dafür, daß selbst das Wissen in der Kryptologie (leicht nachvollziehbar) in zwei Gruppen aufgeteilt ist: in den öffentlichen und in den geheimen Teil.

Natürlich wurde DES auch immer wieder vorgeworfen, daß die Konstruktion von DES auch ein "Hintertürchen" enthalten solle, durch das man ohne Schlüssel leicht an die Daten herankäme. Es gibt dafür keinen Beweis, und die öffentliche Diskussion darüber nimmt immer mehr ab, denn es ist inzwischen nicht mehr relevant, ob das der Fall ist oder nicht, denn DES gilt heutzutage als nicht mehr tragbar selbst für nicht geheime Daten, so daß sich weitere Diskussionen erübrigen. Gleichwohl hat sich die Meinung etabliert, daß es keine "Hintertürchen" in DES gibt.

Adi Shamir sagte am 13. Oktober 1991 gegenüber der New York Times:

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.

Um DES heute wenigstens akzeptabel sicher zu machen, wird die Variante "Triple"-DES benutzt.

Wir wollen das Verfahren im folgenden kurz vorstellen.

Das Blockschaltbild des Verfahrens (s. Abb. 6.1) zeigt vier Hauptkomponenten. Das sind die Anfangsprozedur (IP), der zentrale Block, der sechzehn mal ausgeführt wird, die Schlüsseleinteilung und der abschließende Block (Pl).

Abb. 6.1: DES

DES verschlüsselt stets Blöcke von 64 Bit Länge auf einmal, die Daten müssen als Bitworte vorliegen. Das bedeutet, daß Sprache oder Text zunächst in Bitform umgewandelt werden muß, falls das nicht schon der Fall ist (Computerdaten, ISDN-Telefon, ...). Ein Block von 64 Bit wird dabei in zwei 32 Bit lange Hälften aufgeteilt.

Was nun folgt, ist ein filigranes Ballett der Bits:

Abb. 6.2: 16-round DES

In diesem Mischungsprozeß wird die rechte Hälfte jeweils unverändert zur linken Hälfte des nächsten Schritts. Desweiteren wird die rechte Hälfte benutzt, um mit dem Rundenschlüssel aus der Schlüsseleinteilung die linke Hälfte zu bearbeiten. Als Operation wird ein ganz simples XOR benutzt, das heißt, wenn zwei zu vergleichende Bits gleich sind, entsteht eine 0, wenn sie unterschiedlich sind, ensteht eine 1.

Für jede Runde wird ein anderer Schlüssel benutzt, der sich aus dem vorherigen berechnet. Das beeinflußt nachgewiesenermaßen nicht die Sicherheit des Verfahrens. Im sogenannten F-Modul werden die eingehenden 32-Bit Worte durch Verdoppeln ausgewählter Bitpositionen auf 48 verlängert und mit dem Schlüssel verknüpft. Das Resultat wird in acht 6-Bit-Worte zerlegt und jedes dieser Teile wird durch eine entsprechende S-Box in eine andere Teilfolge von 4-Bits umgewandelt, was als Gesamtergebnis wieder eine 32-Bit-Folge ergibt.

Die S-Boxen sehen so 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 Umwandlung durch die S-Boxen geschieht nach folgendem Schema:

Angenommen, der 6-Bit-Teil lautet 100110. Dann werden das erste und das letzte Bit zu einer Bitfolge zusammengefaßt und als Dualzahl interpretiert, hier also 10 (= 2 im Zehnersystem). Der übriggebliebene Torso, 0011 ist die Dualdarstellung von 3 im Zehnersystem. Also wendet man die Permutation Nummer 2 auf die Zahl 3 an und erhält laut Tabelle (S-Box Nr. 1) den Wert 8. Als Binärmuster erhält man dann 1000. Aus den eingehenden 48 Bits werden so wieder 32 Bits.

Die Schritte im einzelnen:

64-Bit-Eingabevektor, 56 Bit Schlüssel.

  1. Initial Permutation.
    Durch eine fest vorgegebene Permutation wird der Eingabevektor (der Datenblock) verwürfelt. Danach wird in zwei 32-Bit-Vektoren aufgeteilt, die linke und die rechte Hälfte.
  2. 16 Runden Mischen.
    Die Runden j = 1, 2, ..., 16 bestehen aus den Eingaben der 32-Bit-Vektoren Lj-1 und Rj-1, die aus der Runde j-1 kommen, und aus einem 48-Bit-Vektor kj, der aus dem Schlüssel errechnert wird. Runde j besteht nun aus 6 Abschnitten:
    1. Seiten tauschen: Lj = Rj -1.
    2. Der 32-Bit-Vektor wird auf 48 Bit "verlängert", was durch eine definierte Tabelle vorgeschrieben ist.
    3. Schlüssel kj wird addiert, das Ergebnis in acht Vektoren zu je 6 Bit aufgeteilt.
    4. Die oben beschriebene Anwendung der S-Boxes wird durchgeführt.
    5. Auf das ergebnis wird wieder eine feste Permutation angewendet.
    6. Nun wird Lj - 1 zum Zwischenergebnis addiert.
  3. Tauschen.
    Die beiden 32-Bit-Vektoren tauschen nun nochmal ihre Position.

Listing 6.1: Die Arbeitsweise von DES.

Eine genauere Beschreibung des Verfahrens finden Sie beispielsweise in [12], [13] oder auf [D].

DES ist 1977 von Anfang an als Standard für nicht geheime ("non-classified") Nachrichten entworfen worden. Es wurde und wird noch heute von Banken eingesetzt. Es kann heute aber nicht mehr als sicher angesehen werden. Eine Verstärkung des Verfahrens kann von "Triple"-DES erreicht werden - dies ist aber auch nur eine temporäre Lösung. Im privaten Bereich, z.B. bei der Kommunikation per e-mail, reicht es sicherlich aus; berücksichtigt man aber, daß der Industrie hier in Deutschland DES mit ca. zwanzigjähriger Verspätung als modernes Verfahren angeboten wird, dann kann man nur zur Vorsicht raten.