Inhaltsverzeichnis

1  Geschichtlicher Hintergrund und Grundlagen  3

1.1  Entstehung und Entwicklung des DES.  3

1.2  Klärung grundlegender Begriffe und Ideen der Kryptologie  4

1.2.1  Symmetrische Chiffren  4

1.2.2  Blockchiffren.  5

1.2.3  Exclusive Or (XOR)  5

2  Erklärung der Funktionsweise des DES-Algorithmus.  5

2.1  Überblick über die Funktionsweise.  6

2.2  Eingangs- und Ausgangspermutation.  6

2.3  Der Algorithmus f.  6

2.4  Schlüsselgenerierung durch Shift-Operationen.  7

2.5  Dechiffrierung  8

3  Betriebsmodi von Blockchiffren.  8

3.1  Electronic Codebook Modus (ECB)  9

3.2  Cipher Block Chaining Modus (CB)C  10

3.3  Cipher Feedback Modus (CFB)  10

3.4  Output Feedback Modus (OFB)  11

3.5  TripleDES  11

4  Sicherheit von DES  12

4.1  Eigenschaften des DES  12

4.1.1  S-Boxen.  12

4.1.2  Lawineneffekt.  13

4.1.3  Schwache Schlüssel  13

4.2  Der Brute Force Angriff.  13

4.3  Mittel der differentiellen Kryptoanalyse  14

4.4  Die lineare Kryptoanalyse  14

4.5  Laufzeitabschätzungen  14

5  Anwendung heute  15

5.1  Verschlüsselung im Internet.  16

5.2  Finanzwesen  16

6  Der Nachfolger AES.  17

7  Abkürzungsverzeichnis  18

8  Literaturangaben.  18

8.1  Literaturquellen.  18

8.2  Internetquellen  18

8.3  Bildquellen  19

9  Anhang  20

9.1  Permutationstabellen.  20

9.2  S-Boxen  21

Christian Sperber, 2010 Data Encryption Standard

1 G Ge es sc ch hi ic ch ht tl li ic ch he er r H Hi in nt te er rg gr ru un nd d u un nd d G Gr ru un nd dl la ag ge en n 1

Der Data Encryption Standard (DES) war 20 Jahre lang der weltweite Standard für die Verschlüsselung von Daten in der Informationstechnologie und ist wohl der wichtigste Vertreter der sogenannten symmetrischen Blockchiffren. Er galt lange Zeit als äußert sicher, ist aber heute aufgrund der kleinen Schlüssellänge mit der entsprechenden Rechenkapazität leicht zu brechen.

1.1 Entstehung und Entwicklung des DES

Vor den 1970ern hatte das Thema Kryptologie in der Öffentlichkeit noch kaum Bedeutung, lediglich das Militär bemühte sich, seine Kommunikation zu verschlüsseln. Erst mit dem Aufkommen der Informationstechnologie wuchs auch bei Unternehmen und staatlichen Institutionen der Bedarf an einer sicheren, codierten Datenübertragung.

Das erkannte auch das National Bureau of Standards (NBS) ¹ der

USA und veröffentlichte im Mai 1973 eine Ausschreibung im Federal Register der USA. Gesucht wurde hierbei ein geeigneter Verschlüsselungsalgorithmus. Da auf diese Einschreibung kein einziger Vorschlag einging, der die Sicherheitskriterien erfüllte, folgte ein Jahr später eine zweite Ausschreibung, auf die ein Team von IBM nun einen Vorschlag einreichen konnte. Das Projekt basierte auf dem Algorithmus Lucifer des in Deutschland geborenen

Horst Feistel. Es wurde schließlich der National Security Agency (NSA) zur Beurteilung der Sicherheit übergeben.

Nach der Veröffentlichung im Jahr 1975 wurde der Algorithmus am 23. November 1976 unter dem Namen Data Encryption Standard schließlich zum amerikanischen Standard erklärt. ² In den folgenden Jahren (1980-1986) wurden weitere Standards bezüglich der Betriebsmodi, der Implementierung des DES, oder des Einsatz in der Finanzindustrie definiert (Näheres bei Schneier: Kryptographie, S. 311). Der Standard wurde „(trotz Exportbeschränkungen) weltweit […] zum Marktführer.“ (Bauer: Geheimnisse, S.173)

¹ heute: National Institute of Standards and Technology (NIST)

² Der Bundesstandard wurde veröffentlicht unter: National Bureau of Standards (Hg.): Data

Encryption Standard, FIPS PUB 46. National Technical Information Service, 1980.

Christian Sperber, 2010 Data Encryption Standard

In der Öffentlichkeit regte sich währenddessen scharfe Kritik an der unklaren Rolle der NSA bei der Bearbeitung des Algorithmus. So soll auf Druck der Behörde die Schlüssellänge klein gehalten worden sein und auch die sicherheitsrelevanten S-Boxen wurden angeblich von der NSA verändert (Vgl. Wobst: Abenteuer, S. 125). Es wurde der Vorwurf laut, die Agency hätte sich Hintertürchen eingebaut, um selbst mit eigener Rechenkapazität codierte Texte entschlüsseln zu können. Die Veröffentlichung (also nicht nur die Implementierung in Hardware) des Algorithmus beruht wahrscheinlich sogar nur auf einem Missverständnis zwischen NBS und NSA, inoffiziell bezeichnete die NSA den DES als ihren größten Fehler (Vgl. Schneier: Kryptographie, S. 311). Es ist aber auch möglich, dass die NSA die S-Boxen verändert hat, um zu verhindern, dass IBM hier zum eigenem Vorteil eine Schwachstelle einbaut.

Der Algorithmus wurde 1994 dann erstmals innerhalb von 50 Tagen mit einem Rechnerver-bund per Brute Force (Durchprobieren aller möglichen Schlüssel; siehe Kap. 3.2) geknackt. Vier Jahre später benötigte man nur noch drei Tage und 1999 schließlich wurde der „bislang schnellste Angriff gegen DES“ (Ertel: Kryptographie, S. 56 und S. 63, Stand: 2003) in 22 Stunden durchgeführt, allerdings war hierfür auch ein Netzwerk aus etwa 100.000 PCs nötig.

Nach einer Entwicklungszeit von vier Jahren wurde 2001 der Data Encryption Standard vom Advanced Encryption Standard (AES) offiziell abgelöst. Auch der AES ist eine Blockchiffre, die per Ausschreibung gefunden wurde, er ist vor allem wegen der größeren Schlüssellänge sicherer. Doch der Umstieg auf den neuen Standard dauerte Jahre und noch heute wird DES vereinzelt eingesetzt.

1.2 Klärung grundlegender Begriffe und Ideen der Kryptologie

1.2.1 Symmetrische Chiffren

Grundsätzlich gibt es zwei Arten von Verschlüsselungsalgorithmen: Symmetrische und asymmetrische. Während bei der asymmetrischen Methode zwei Schlüssel benötigt werden, wird bei der symmetrischen Verschlüsselung zum Ver- und Entschlüsseln der gleiche

Christian Sperber, 2010 Data Encryption Standard

Schlüssel verwendet oder Chiffrierschlüssel und Dechiffrierschlüssel lassen sich leicht ausei-nander berechnen. Um eine geheime Nachrichtenübertragung zu ermöglichen, muss ein gemeinsamer Schlüssel vereinbart und geheim gehalten werden.

1.2.2 Blockchiffren

Unter den symmetrischen Algorithmen gibt es Block- und Stromchiffren. Eine Stromchiffre verschlüsselt Informationen zeichenweise oder bitweise. Blockchiffren hingegen bearbeiten den Klartext in Bitgruppen, Blöcke genannt. Lässt sich der Klartext nicht genau in solche Blöcke aufteilen, so wird beim sogenannten Padding der letzte Block üblicherweise mit Zufallsbits aufgefüllt.

1.2.3 Exclusive Or (XOR)

Exclusive Or ist eine logische Operation, die zwei Bits miteinander verknüpft. Es gilt die Regel: Sind die Bits gleich, so ist das Ergebnis der Operation eine Null. Bei unterschiedlichen Bits hat XOR eine Eins als Ergebnis. ¹ Mit Hilfe von XOR kann man so eine Daten-Bitfolge mit einer Schlüssel-Bitfolge zu einem Code verknüpfen. Aus diesem Code können dann per Verknüpfung mit dem Schlüssel wieder die Daten gewonnen werden. In Abbildungen findet sich hierfür das Zeichen „ “.

2 E Er rk kl lä är ru un ng g d de er r F Fu un nk kt ti io on ns sw we ei is se e d de es s D DE ES S- -A Al lg go or ri it th hm mu us s 2

Der Data Encryption Algorithm (DEA) entspricht einer symme-

trischen Blockchiffre, die auf Transpositionen (auch Permutationen genannt) und Substitutionen beruht. D.h. der binäre Klartext wird in Blöcke von 64 Bit zerlegt und jeder Block wird nach dem gleichen Prinzip in 16 Feistel-Runden ² durch Vertauschungen (Permutationen) und Ersetzungen (Substitutionen) zu einem 64 Bit Chiffreblock verschlüsselt. DES verwendet hierbei effektiv einen 56-Bit-Schlüssel. Es gilt das Kerkhoffsche Prinzip: Die ganze Sicherheit liegt in der Geheimhaltung des Schlüssels, nicht etwa auf der Geheimhal-

tung des Algorithmus. ¹ Diese Regel entspricht einer Addition modulo 2.

² Benannt sind die Feistel-Runden nach ihrem Erfinder Horst Feistel.

Christian Sperber, 2010 Data Encryption Standard

2.1 Überblick über die Funktionsweise

Der binäre Klartextblock von 64 Bit wird nach einer Eingangspermutation in zwei 32 Bit Blöcke zerlegt. Mit diesen Hälften werden nun 16 identische Runden durchgeführt, in denen die Daten mit dem Schlüssel verknüpft werden. Dabei wird die sogenannte rechte Hälfte doppelt verwendet. Zum einen bildet sie die linke Hälfte der nächsten Runde, zum anderen wird sie in der Funktion f mit dem Rundenschlüssel Ki verknüpft. Das Ergebnis der Funktion wird mit der linken Hälfte XOR (siehe Kap. 1.2.3) verrechnet und formt so die rechte Hälfte der nächsten Runde. Nach 16 Runden folgt eine der Eingangspermutation inverse Ausgangspermutation (Abb. 3).

2.2 Eingangs- und Ausgangspermutation

Vor der ersten Runde erfolgt die Eingangspermutation. Sie vertauscht die

64 Eingangsbits gemäß Tabelle 1. So wird beispielsweise das Bit an der Stelle 58 an die erste Outputstelle geschoben, das 50. Bit besetzt die zweite Outputstelle usw. Nach der letzten Runde folgt die Ausgangspermutation, die invers zur Eingangspermutation ist, ¹ d.h. erfährt ein Bitblock lediglich diese beiden Operationen, so ist das Ergebnis genau wieder

dieser Bitblock. Deshalb haben diese Permutationen keinen sicherheitsrelevanten Einfluss auf den Algorithmus. Man brauchte diese Permutationen, da früher DES in Hardware implementiert wurde, und so wurden sie im Standard verankert.

2.3 Der Algorithmus f

Zunächst werden die 32 Eingangsbits in einer sogenannten Expansion Permutation vertauscht und teilweise doppelt verwendet (Abb. 4). Der so entstehende 48 Bit Output wird dann mit dem Runden-Teilschlüssel, ebenfalls von einer Länge von 48 Bit, XOR verknüpft.

Nun kommen die S-Boxen („Substitution-Boxes“) zum Einsatz, die wesentlich zur Sicherheit des DEA beitragen: Die Bits werden gleichmäßig auf die acht S-Boxen aufgeteilt und jede S-Box verarbeitet ihren 6 Bit Input zu einem 4 Bit Output. Für jede S-Box gibt es hierfür verschiedene Vorschriften im Standard, als Beispiel soll hier die S-Box 1 dienen (Vgl. Tab. 2):

¹ Die Tabellen aller Permutationen sowie S-Boxen sind im Anhang zu finden. Sie sind der

Übersichtlichkeit halber nicht im Hauptteil aufgeführt.