Leseprobe
Inhaltsverzeichnis
1 Geschichtlicher Hintergrund und Grundlagen
1.1 Entstehung und Entwicklung des DES
1.2 Klärung grundlegender Begriffe und Ideen der Kryptologie
1.2.1 Symmetrische Chiffren
1.2.2 Blockchiffren
1.2.3 Exclusive Or (XOR)
2 Erklärung der Funktionsweise des DES-Algorithmus
2.1 Überblick über die Funktionsweise
2.2 Eingangs- und Ausgangspermutation
2.3 Der Algorithmus f
2.4 Schlüsselgenerierung durch Shift-Operationen
2.5 Dechiffrierung
3 Betriebsmodi von Blockchiffren
3.1 Electronic Codebook Modus (ECB)
3.2 Cipher Block Chaining Modus (CBC)
3.3 Cipher Feedback Modus (CFB)
3.4 Output Feedback Modus (OFB)
3.5 TripleDES
4 Sicherheit von DES
4.1 Eigenschaften des DES
4.1.1 S-Boxen
4.1.2 Lawineneffekt
4.1.3 Schwache Schlüssel
4.2 Der Brute Force Angriff
4.3 Mittel der differentiellen Kryptoanalyse
4.4 Die lineare Kryptoanalyse
4.5 Laufzeitabschätzungen
5 Anwendung heute
5.1 Verschlüsselung im Internet
5.2 Finanzwesen
6 Der Nachfolger AES
7 Abkürzungsverzeichnis
8 Literaturangaben
8.1 Literaturquellen
8.2 Internetquellen
8.3 Bildquellen
9 Anhang
9.1 Permutationstabellen
9.2 S-Boxen
1 Geschichtlicher Hintergrund und Grundlagen
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.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 1 Horst Feistel
Das erkannte auch das National Bureau of Standards (NBS).[1] 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 er- klärt[2] 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)
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.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2 Logo der NSA
Nach der Entdeckung der differentiellen Kryptoanalyse (siehe Kap. 3.3) im Jahr 1990 durch Elie Biham und Adi Shamir wurde klar, dass die DES-Schöpfer diesen Angriff damals schon kannten, das Wissen um diesen Angriff aber geheim halten wolten und deshalb die Entwurfskriterien der S-Boxen nicht preisgaben (siehe Kap. 4.3). Trotzdem bot der DES immer weniger Sicherheit. Aus Mangel an Alternativen jedoch wurde der Standard weiterhin vom NBS zertifiziert.
Der Algorithmus wurde 1994 dann erstmals innerhalb von 50 Tagen mit einem Rechnerverbund 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
Schlüssel verwendet oder Chiffrierschlüssel und Dechiffrierschlüssel lassen sich leicht auseinander 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.[3] 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 Erklärung der Funktionsweise des DES-Algorithmus
Abbildung in dieser Leseprobe nicht enthalten
Abb. 3 Das DES-Schema
Der Data Encryption Algorithm (DEA) entspricht einer symmetrischen 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 [4] 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 Geheimhaltung des Algorithmus.
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
Abbildung in dieser Leseprobe nicht enthalten
Tab. 1 Eingangsper-mutation
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,[5] 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 SBox 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):
Abbildung in dieser Leseprobe nicht enthalten
Tab. 2 Die erste S-Box
Die sechs Input-Bits seien b1, b2, b3, b4, b5 und be. Die Tabelle ist so zu lesen, dass für die Spalte die Bits b2, b3, b4, b5 in eine Dezimalzahl umgerechnet werden. Die Zeile bestimmen b1 und bé. Angenommen es kämen die sechs Bits 11DD11 in die S-Box, so bilden die Bits zwei bis vier und das entspricht der Dezimalzahl 9. Die äußeren beiden Bits bilden 11, was
einer dezimalen 3 entspricht. Nun findet man in der Spalte 9 und der Zeile 3 den Eintrag 11. Umgerechnet erhält man die vier Output-Bits 1D11.
Die Ergebnisse der acht S-Boxen werden anschließend wieder zusammengesetzt und dann in der Permutation P abschließend vertauscht.
Für weitere Tabellen der Permutationen E und P sowie der S-Boxen sei auf den Anhang verwiesen.
2.4 Schlüsselgenerierung durch Shift-Operationen
Für jede der 16 DES-Runden wird ein eigener Teilschlüssel generiert. Dafür durchläuft der Originalschlüssel einige Operationen. Er erfährt zu Anfang eine Eingangspermutation („Permuted Choice 1"), die den 64-Bit-Schlüssel auf 56 Bit reduziert. Die acht ignorierten, sogenannten Paritätsbits des Originalschlüssels sind lediglich zur Überprüfung der fehlerfreien Übertragung des Schlüssels gedacht und werden somit nicht in den weiteren Prozess mitein- bezogen.
Nun folgen 16 Runden, wobei in jeder ein Teilschlüssel von 48 Bit für die Funktion f der jeweiligen Runde bereitgestellt wird. Der Schlüssel wird - geteilt in zwei Hälften - in den Runden je durch eine Shift-Operation[6] und eine auswählende Permutation bearbeitet (Abb. 4).
[...]
[1] heute: National Institute of Standards and Technology (NIST)
[2] Der Bundesstandard wurde veröffentlicht unter: National Bureau of Standards (Hg.): Data Encryption Standard, FIPS PUB 46. National Technical Information Service, 1980.
[3] Diese Regel entspricht einer Addition modulo 2.
[4] Benannt sind die Feistel-Runden nach ihrem Erfinder Horst Feistel.
[5] Die Tabellen aller Permutationen sowie S-Boxen sind im Anhang zu finden. Sie sind der Übersichtlichkeit halber nicht im Hauptteil aufgeführt.
[6] Die Bits werden um eine festgelegte Zahl nach rechts verschoben, Bits am Ende werden an den Anfang gestellt (zyklische Verschiebung); zur Anzahl der Verschiebungen siehe Anhang.