8.2.2. Symmetrische Kryptosysteme

Symmetrische Kryptosysteme sind dadurch gekennzeichnet, daß bei ihnen der zur Dechiffrierung notwendige Schlüssel aus dem bei der Chiffrierung verwendeten Schlüssel berechnet werden kann. Bei allen praktisch relevanten Systemen sind beide Schlüssel stets identisch. Deshalb wird in der Literatur meist nur von genau einem Key gesprochen, der typischerweise die Bezeichnung Secret Key trägt und sowohl zur Ver- als auch zur Entschlüsselung dient:

In der englischsprachigen Literatur finden wir verschiedene Bezeichnungen für symmetrische Verfahren, z.B. symmetric algorithms, conventional algorithms und secret key algorithms. Analog spricht man auch von secret key cryptography, conventional cryptography sowie symmetric cryptography.

Anwendungsgebiete

Symmetrische Kryptosysteme lassen sich u.a. für folgende Zwecke einsetzen:

Blockchiffren und Stromchiffren

Bei den symmetrischen Verfahren unterscheidet man zwei große Kategorien: kontinuierliche und blockorientierte Algorithmen, auch Stromchiffren (stream ciphers) bzw. Blockchiffren (block ciphers) genannt. Entsprechend wird von Stromchiffrierung und Blockchiffrierung gesprochen.

Die erste Gruppe verschlüsselt den Klartext bit- oder byteweise (manchmal werden auch 32-Bit-Worte geschlossen verarbeitet). Der Klartext wird über die Funktion XOR mit einer langen Folge binärer Signale verknüpft, deren Periode größer als die zu verschlüsselnde Nachricht sein muß.

Diese Folge bildet man in der Regel über einen geeigneten (d.h. kryptographisch sicheren) Pseudozufallszahlen-Generator, wobei die konkret erzeugten Werte von einem geheimen Schlüssel abhängen und durch diesen auch eindeutig bestimmt sind. Damit läßt sich die Folge beliebig reproduzieren, woraus unter Beachtung der bereits diskutierten Eigenschaften der Funktion XOR die Umkehrbarkeit der Verschlüsselungsfunktion folgt: Ver- und Entschlüsselung sind stets identische Operationen. Der innere Aufbau sowie die Komplexität des Pseudozufallszahlen-Generators sind diesbezüglich irrelevant.

Ein Spezialfall der Stromchiffrierung ist das bereits diskutierte One-time Pad, da hier echte Zufallswerte (z.B. aus einer physikalischen Quelle stammend) eine Rolle spielen, die sich nicht gezielt reproduzieren lassen.

Aus dem Konstruktionsprinzip der Stromchiffren folgt, daß der Geheimtext, der einem bestimmten Bit bzw. Byte-Wert des Klartextes bei der Verschlüsselung zugeordnet wird, vom Prinzip her ständig variiert, und zwar in Abhängigkeit von der Position der betreffenden Klartext-Einheit im Gesamtstrom der Daten. So kann es also sein, daß das erste Zeichen "a" eines Textes als "X" und das zweite "a" als "5" verschlüsselt wird.

Die Stromchiffrierung hat in den für uns interessanten Bereichen eine deutlich geringere Bedeutung als die Blockchiffrierung. So unterstützen viele Protokolle bzw. deren Implementierungen, wenn überhaupt, deutlich weniger kontinuierliche als blockorientierte Verfahren. Eine relativ verbreitete Stromchiffre ist der RC4, dessen Spezifikation allerdings nicht offengelegt wurde, sondern als Geschäftsgeheimnis betrachtet wird.

Bei der zweiten Gruppe, d.h. bei den Blockchiffren, erfolgt die Verschlüsselung des Klartextes generell in Bitblöcken fester Länge. Im Gegensatz zur Stromchiffrierung wird hierbei, solange man denselben Key verwendet, einem bestimmten Klartextblock immer dasselbe Chiffrat zugeordnet. Eine typische Blocklänge beträgt 64 Bit. Sie ist einerseits groß genug, um Kryptoanalysen wirkungsvoll zu verhindern, ist aber andererseits immer noch praktikabel.

Zu den in der Praxis wichtigsten Vertretern von Blockchiffren gehören DES, Triple DES und IDEA. Auf sie werden wir nachfolgend an verschiedenen Stellen etwas genauer eingehen.

Ein symmetrisches Kryptosystem muß bei der Chiffrierung eine eineindeutige Abbildung der Menge aller möglichen Klartexte auf die Menge der möglichen Geheimtexte vornehmen, da anderenfalls keine eindeutige Entschlüsselung möglich wäre. Bei 64-Bit-Blöcken umfassen beide Mengen jeweils 264 Elemente. Damit gibt es insgesamt 264! (! steht für Fakultät) verschiedene Zuordungsvorschriften. Würde man sie alle von Null beginnend mit Binärzahlen durchnumerieren, die jeweilige Nummer als Schlüssel betrachten und eine feste Schlüssellänge unterstellen, so hätten die Keys eine Länge von ca. 1,15×1021 Bit. Zum Vergleich: Die nächstgrößere Zweierpotenz ist 270. Ein Verfahren mit derart extrem langen Schlüsseln wäre für die Praxis komplett unbrauchbar.

Die in guten blockorientierten Verfahren tatsächlich verwendeten Schlüssel haben natürlich eine vernünftige Länge (z.B. 56 Bit bei DES, 112 bzw. 168 Bit bei Triple DES oder 128 Bit bei IDEA) und erzeugen eine eineindeutige Abbildung der Klar- auf die Geheimtexte, die für jemanden, der den Key nicht kennt, so aussieht, als sei sie absolut zufällig. Deshalb lassen sich Blockchiffren auch als Basis für kryptographisch sichere Pseudozufallszahlen-Generatoren nutzen.

Bereits 1949 hat Claude E. Shannon in seinem Paper "Communication Theory of Secrecy Systems" zwei fundamentale Prinzipien zum Verbergen von in Klartexten enthaltenen Redundanzen formuliert: Konfusion (confusion) und Diffusion (diffusion), die noch heute die Basis für die Entwicklung starker Blockalgorithmen darstellen.

Die Konfusion verfolgt das Ziel, sämtliche Beziehungen zwischen Klartext, Geheimtext und Schlüssel zu verbergen. Guten Verfahren gelingt es, die statistischen Zusammenhänge so kompliziert zu gestalten, daß selbst sehr mächtige Methoden der Kryptoanalyse versagen. Am einfachsten ist eine Konfusion durch geeignete Substitutionen (substitutions) erreichbar.

In der klassischen Kryptographie versteht man darunter Ersetzungen von Zeichen oder Zeichenfolgen (Zeichenblöcken) durch andere Zeichen bzw. Zeichenfolgen. Man nennt eine Substitution

Bei den modernen blockorientierten Verfahren werden Substitutionen verwendet, die eine Folge von n Bits gegen eine Folge von m Bits ersetzen. Sehr häufig bezeichnet man eine solche Substitution als m×n-Bit-S-Box. So nutzt z.B. der DES acht verschiedene 6×4-Bit-S-Boxen. Bei IDEA wird eine leicht modifizierte modulare 16-Bit-Multiplikation durchgeführt, die von der Wirkung her einer 16×16-Bit-S-Box entspricht.

S-Boxen stellen in der Regel den einzigen nichtlinearen Schritt eines Algorithmus dar und beeinflussen die Sicherheit des Verfahrens maßgeblich. Eine Eigenschaft, die als sehr wichtig angesehen wird, ist der Lawineneffekt (avalanche effect): Jede minimale Änderung des Inputs sollte eine starke Auswirkung auf den Output der S-Box haben. Ein strenges Kriterium fordert die Beeinflussung von genau der Hälfte aller Output-Bits, wenn sich ein Input-Bit geändert hat.

Die Wahl guter S-Boxen ist nicht trivial. Hierzu gibt es unterschiedlichste Vorschläge von vielen Kryptologen. Allgemein gilt: Je größer die Boxen sind, desto besser sind sie auch. Einer der Ansätze geht z.B. davon aus, daß man S-Boxen zufällig wählen sollte, wobei sie eine hinreichende Größe haben müssen (mindestens 8 Input-Bits), da sie sonst unsicher sind. Des weiteren wird davon ausgegangen, daß sich die Sicherheit erhöht, wenn man die Boxen schlüsselabhängig gestaltet. Beispielsweise IDEA nutzt relativ große und schlüsselabhängige S-Boxen.

Diffusion verfolgt das Ziel, daß jedes Bit des Klartextes sowie des Schlüssels eine maximal mögliche Anzahl von Bits des Chiffrats beeinflußt. Die Redundanz des Klartextes wird über den Geheimtext verteilt. Dies trägt in Ergänzung zur Konfusion zum Verbergen statistischer Zusammenhänge bei und erschwert so die Kryptoanalyse. Die typische hierfür verwendete Technik ist die Transposition (transposition), auch Permutation (permutation) genannt. Im Gegensatz zur Substitution geht es dabei um keine Ersetzung von Zeichen bzw. Bitfolgen, sondern darum, sie in ihrer Reihenfolge zu vertauschen.

Bereits Shannon hatte erkannt, daß man durch eine geeignete Kombination von an sich relativ schwachen kryptographischen Operationen ein wesentlich stärkeres Verfahren konstruieren kann. Für eine derart erzeugte Chiffre prägte er den Begriff Product Cipher (Produktchiffre). Moderne kryptographisch starke Blockalgorithmen gehören daher zur Klasse der Produktchiffren. Sie verwenden wiederholt und in jeweils verschiedenen Kombinationen unterschiedliche Konfusions- und Diffusionstechniken. Allgemein gilt, daß die Substitution allein bereits ausreicht, um sichere Algorithmen entwickeln zu können. Dagegen ist ein Verfahren, daß nur auf Diffusion beruht, in der Regel relativ leicht zu brechen.

Ein für Blockalgorithmen typisches Prinzip ist deren iterative Arbeitsweise. Bestimmte, meist relativ einfache Operationen werden mehrmals hintereinander ausgeführt. Wie viele kryptoanalytische Attacken gezeigt haben, ist die Anzahl der Runden (rounds) für die Sicherheit eines Verfahrens von entscheidender Bedeutung. So erreicht man z.B. beim DES erst nach 5 Runden die für starke Verfahren geforderte Eigenschaft, daß alle Bits des Geheimtextes von allen Bits des Klartextes sowie des Schlüssels abhängen. Nach 8 Runden erscheint diese Abhängigkeit als im Prinzip zufällig. Das reicht aber noch nicht aus. Hätte der DES weniger als die in seiner Spezifikation definierten 16 Runden, könnte man ihn mit einer Known-plaintext-Attacke effektiver brechen als durch einen Brute-force-Angriff.

DES, AES, Triple DES und IDEA

Nach der Diskussion allgemeiner Aspekte der Blockchiffrierung wollen wir nun kurz die bereits oben erwähnten Verfahren DES, Triple DES und IDEA etwas spezieller vorstellen.

DES ist die Abkürzung für Data Encryption Standard. Er wurde am 23. November 1976 in den USA als Federal Standard angenommen. Die Veröffentlichung seiner offiziellen Beschreibung erfolgte am 15. Januar 1977 im Dokument NBS FIPS PUB 46. NBS steht für National Bureau of Standards. Diese Behörde trägt heute den Namen National Institute of Standards and Technology (NIST). FIPS bedeutet Federal Information Processing Standards. Der DES wurde 1981 auch von der ANSI als Standard X3.92-1981 unter der Bezeichnung Data Encryption Algorithm (DEA) angenommen.

DES ist seit nun mehr als 20 Jahren ein weltweiter Standard, der erstaunlich gut der Vielzahl der gegen ihn gerichteten kryptoanalytischen Attacken standgehalten hat. Zunehmend läßt er allerdings Spuren seines Alters erkennen. Seine primäre Schwäche ist die für heutige Verhältnisse viel zu geringe Schlüssellänge von 56 Bit.

Dies wurde durch verschiedene von der Firma RSADSI initiierte DES-Challenges recht eindrucksvoll demonstriert:

Der Aufwand zum Brechen von DES-Verschlüsselungen sinkt mit zunehmender Leistungsfähigkeit der verfügbaren Rechner sowie fallenden Preisen für Computertechnik zusehends. Auch ohne spezielle DES-Cracker kann man heute schon in relativ kurzer Zeit DES-Chiffrierungen brechen, z.B. durch die Kooperation vieler Rechner im Internet, wie dies bei distributed.net [http://www.distributed.net/] der Fall ist. Darauf hatten wir ja bereits weiter oben hingewiesen.

Ein Vertreter des FBI hat in einer Reaktion [http://www.eff.org/pub/Privacy/Crypto_misc/DESCracker/199808_admin_fax_images/]) auf die mit dem DES-Cracker der EFF erzielten Resultate den Fakt angemerkt, daß in den DES-Challenges von RSADSI immer nur einzelne Nachrichten dechiffriert wurden, wobei erleichternd hinzukam, daß die ersten 24 Byte des Klartextes bekannt sind ("The unknown message is: ").

Für eine Echtzeit-Entschlüsselung realer Kommunikationskanäle, die z.B. das unmittelbare Mitlesen chiffrierter Inhalte (die der Angreifer in der Regel nicht kennt) oder gar eine flächendeckende Überwachung von Kommunikationsnetzen gestatten würde, sind die bisher in der Öffentlichkeit genutzten Techniken noch nicht sinnvoll verwendbar. Dies sollte man bei der Interpretation der o.g. Ergebnisse von Brute-force-Attacken beachten.

In einer ganzen Reihe von Anwendungen bietet DES gegenwärtig noch immer einen verhältnismäßig zuverlässigen Schutz. Dies gilt ganz allgemein dann, wenn der zeitliche bzw. materielle Aufwand, den ein potentieller Angreifer beim Brechen einer Chiffrierung hätte, den Wert der verschlüsselten Information deutlich übersteigt, möglicherweise deshalb, weil die Information nur für kurze Zeit verwertbar ist. Durch einige leicht zu implementierende Maßnahmen, beispielsweise häufige Schlüsselwechsel, zufälliges Padding (Einfügen zufälliger Bytes in die Nachricht) und anschließende Komprimierung des Klartextes zur Reduzierung der Redundanz, läßt sich der Aufwand des Angreifers deutlich erhöhen.

Dessen ungeachtet ist mittlerweile vom Einsatz des DES in Umgebungen bzw. Applikationen, in denen ein hohes Sicherheitsniveau gefordert wird, dringend abzuraten. Der DES sollte so schnell wie möglich gegen ein starkes Verfahren mit deutlich längeren Schlüsseln (128 Bit oder mehr) ersetzt werden. Im Handbuch von PGP 2.6.x äußert sich dessen Autor Philip Zimmermann zur Sicherheit des DES wie folgt:

Obwohl das NBS den DES nach heftiger Debatte 1992 nicht wieder als Standard bestätigen wollte, verabschiedete man ihn in Ermangelung einer echten Alternative dennoch 1993 für weitere 5 Jahre als Standard. Seine aktuelle Beschreibung findet sich in der NIST FIPS PUB 46-2.

Die Historie von DES ist recht interessant. Seit 1972 verfolgte das NBS das Ziel, einen einheitlichen kryptographischen Algorithmus zu entwickeln und zu standardisieren, der eine Reihe von Kriterien erfüllen sollte, u.a. folgende: hohes Sicherheitsniveau, komplett standardisiert, leicht verständlich, frei verfügbar, ökonomisch in Hardware implementierbar, effizient nutzbar sowie exportierbar.

In einer ersten öffentlichen Ausschreibung 1973 kam keiner der eingereichten Vorschläge diesen Kriterien hinreichend nahe. Erst in einer zweiten Ausschreibung 1974 wurde ein passender Kandidat gefunden: ein Algorithmus, der auf dem in den frühen 70er Jahren durch IBM entwickelten Algorithmus namens Lucifer basierte.

Das NBS ließ die Sicherheit des Algorithmus durch die National Security Agency (NSA) überprüfen, die in diesem Zusammenhang einige Veränderungen vornahm. So modifizierte sie die S-Boxen, ohne allerdings die Gründe dafür bzw. die verwendeten Design-Kriterien offenzulegen, und kürzte den ursprünglich bei Lucifer 128 Bit bzw. im von IBM beim NBS eingereichten Originalvorschlag 112 Bit langen Schlüssel auf 56 Bit. Der Einfluß der NSA war vielen suspekt, weswegen lange darüber spekuliert wurde, ob nicht eine Falltür eingebaut worden ist, die der NSA auch ohne Kenntnis des Keys ein relativ leichtes Dechiffrieren von DES-verschlüsselten Nachrichten erlauben könnte.

Erst viel später, nämlich Anfang der 90er Jahre, wurde klar, daß die veränderten S-Boxen den DES sehr resistent gegen eine bis dahin in der akademischen Kryptologen-Gemeinde unbekannte Attacke machen: die von den beiden bekannten israelischen Kryptologen Eli Biham und Adi Shamir 1990 vorgestellte differentielle Kryptoanalyse (differential cryptanalysis). Unter Verwendung dieser Technik gelang den beiden Wissenschaftlern die Konstruktion der oben erwähnten Known-plaintext-Attacke, durch die der DES effektiver als durch einen Brute-force-Angriff gebrochen werden kann, sofern er weniger als 16 Runden hat.

Etwas später gab Don Coppersmith, einer der DES-Entwickler bei IBM, zu, daß seinem Team sowie der NSA bereits damals die von Biham und Shamir publizierte, sehr mächtige kryptoanalytische Methode bekannt war, sie sich aber nach einer Diskussion mit der NSA darauf verständigten, dieses Wissen geheimzuhalten, um den USA einen Vorsprung vor anderen Staaten zu sichern.

DES war insofern ein absolutes Novum, weil niemals zuvor ein von der NSA evaluierter Algorithmus veröffentlicht worden war. Wahrscheinlich hat es sich dabei auch um ein Mißverständnis zwischen NBS und NSA gehandelt. Die NSA ging wohl davon aus, daß DES nur in Hardware realisiert werden sollte. Das NBS gab aber genug Details bekannt, um Software-Implementierungen zu ermöglichen. Inoffiziell hat die NSA den DES deshalb als einen ihrer größten Fehler bezeichnet. Mit ihm stand der Öffentlichkeit erstmals ein kryptographisches Verfahren zum Studium zur Verfügung, das die NSA als sicher eingestuft hatte.

DES übte daher einen wesentlich stärkeren Einfluß auf das Gebiet der Kryptoanalyse aus als jeder andere Algorithmus. Es ist auch nicht verwunderlich, daß der nächste Regierungs-Standard, der in den Clipper- und Capstone-Chips verwendete Skipjack, lange nicht veröffentlicht, sondern nur in einbruchsicherer Hardware implementiert wurde. Im Juni 1998 hat die NSA dann allerdings den Skipjack declassified. Etwas mehr dazu erfahren Sie im Abschnitt über SSL.

Nun einige Bemerkungen zum Verfahren selbst: DES ist eine mit 16 Runden arbeitende Produktchiffre, die auf 64 Bit langen Datenblöcken operiert und Schlüssel der Länge 56 Bit verwendet. Ein Schlüssel wird gewöhnlich als 64-Bit-Zahl angegeben, wobei aber jedes achte Bit (das niedrigstwertige eines Bytes) nur dem Paritätstest dient. Alle 256 möglichen Bitkombinationen dürfen als Key genutzt werden, wobei 64 genau bekannte Schlüssel existieren, die man als mehr oder minder schwach einstuft. Konkret spricht man 4 weak keys, 12 semiweak keys und 48 possibly weak keys. Gemessen an der Gesamtzahl möglicher Schlüssel von ca. 7,2×1016 sind das sehr wenige. Man kann ihre Verwendung mühelos durch einige Vergleichsoperationen verhindern.

Eines der Entwurfsziele von DES bestand darin, daß so schnell wie möglich alle Bits des Geheimtextes von allen Bits des Klartextes sowie des Schlüssels abhängen. Minimale Änderungen des Klartextes bzw. Schlüssels bewirken, daß sich ca. 50% der Bitpositionen ändern. Hierbei handelt es sich um den bereits weiter oben erwähnten Lawineneffekt (avalanche effect).

AES

Am 2. Januar 1997 wurde vom NIST der Beginn eines Prozesses öffentlich bekanntgegeben, dessen Ziel in der Entwicklung einer symmetrischen Chiffre mit der Bezeichnung Advanced Encryption Standard, kurz AES, besteht. Dieser ist als Ersatz für den DES gedacht. Das NIST hat bzgl. des AES folgende Absicht bekundet:

It is intended that the AES will specify an unclassified, publicly disclosed encryption algorithm available royalty-free worldwide that is capable of protecting sensitive government information well into the next century.

Anders als beim DES sollen also beim AES die kryptographischen Aspekte von Anfang an offen diskutiert werden. Die NSA wird übrigens (angeblich auf Bitte des NIST) keinen AES-Kandidaten präsentieren.

Durch die Ankündigung des NIST waren weltweit alle interessierten Experten aufgerufen, Spezifikationen geeigneter Kandidaten für den AES einzureichen, die folgende Minimalkriterien erfüllen müssen:

  1. Es muß sich bei dem Algorithmus um ein symmetrisches Kryptosystem handeln.

  2. Der Algorithmus muß eine Blockchiffre sein.

  3. Er muß eine Blocklänge von 128 Bit sowie die Schlüssellängen 128, 192 und 256 Bit unterstützen. Andere Kombinationen von Block- und Schlüssellängen sind zulässig und werden bei der Bewertung der Kandidaten berücksichtigt.

Am 20. August 1998 wurden vom NIST die 15 offiziellen AES-Kandidaten bekanntgegeben, zu deren Autoren mehrere weltweit anerkannte Kryptologen zählen, die an verschiedenen Stellen dieses Kapitels Erwähnung finden. Als Beispiele seien genannt:

Das NIST bietet auf der WWW-Seite Advanced Enryption Standard (AES) Development Effort [http://csrc.nist.gov/encryption/aes/aes_home.htm] aktuelle und umfangreiche Informationen zum AES.

Triple DES

Hauptsächlich wegen der relativ kurzen Schlüssel, die Brute-force-Attacken begünstigen, bestand ein großes Interesse daran, eine Alternative zu DES zu finden. Ein Weg ist die Entwicklung eines völlig neuen Algorithmus, wie das mit IDEA geschehen ist. Ein anderer Ansatz, der sogar die bisher getätigten Investitionen in DES-basierte Soft- und Hardware schützt, besteht in der aufeinanderfolgenden Anwendung mehrerer DES-Operationen (Ver- und Entschlüsselungen) unter Nutzung verschiedener Keys.

Die heute generell akzeptierte Methode, DES durch Mehrfachverschlüsselung sicherer zu machen, wird oft als EDE (encrypt-decrypt-encrypt) bezeichnet. Wie der Name erkennen läßt, erfolgen bei ihr nacheinander 3 Schritte: Verschlüsselung, Entschlüsselung und Verschlüsselung, woraus die Bezeichnung Triple DES (manchmal auch 3DES genannt) resultiert. Es gibt verschiedene Formen des Triple DES. Einige nutzen 2 und andere 3 verschiedene 56-Bit-Schlüssel, wodurch sich eine effektive Schlüssellänge von 112 bzw. 168 Bit ergibt.

Weit verbreitet ist die Verwendung von 2 Schlüsseln K1 und K2, wobei für Schritt 1 und 3, also die beiden Verschlüsselungen, derselbe Key genutzt wird. Die effektive Schlüssellänge beträgt somit 112 Bit. Die folgenden Gleichungen zeigen die Chiffrierung des Klartextes M sowie die Dechiffrierung des Geheimtextes C:

C = EK1(DK2(EK1(M)))

M = DK1(EK2(DK1(C)))

Wählt man bei diesem Schema die Keys K1 und K2 identisch, so entspricht die Gesamtoperation einer einfachen DES-Operation. Somit ist eine Interoperabilität mit konventionellen DES-Sytemen gegeben.

Es sei noch angemerkt, daß eine Mehrfachverschlüsselung nicht bei allen Blockalgorithmen zu einer Erhöhung der Sicherheit beiträgt. Das hängt von deren algebraischer Struktur ab. Handelt es sich bei einem Verfahren im Sinne der Algebra um eine Gruppe, dann läßt sich für jedes Schlüsselpaar (K1, K2) ein Key K3 finden, so daß

EK2(EK1(M)) = EK3(M)
gilt.

Lange Zeit war nicht sicher geklärt, daß DES keine Gruppe ist. Man nahm es an, aber erst 1992 gelang der explizite Nachweis. Wie wir oben festgestellt hatten, gibt es bei DES mit seinen 64-Bit-Blöcken 264! mögliche Zuordnungen. Mit einem 56-Bit-Schlüssel können wir nur eine relativ kleine, 256 Elemente umfassende Teilmenge nutzen. Durch mehrfache Verschlüsselung gelingt es uns, diese Teilmenge zu vergrößern.

Hinweis:

Für den Triple DES existiert der neue (momentan noch als Draft vorliegende) ANSI-Standard X9.52 mit dem Titel Triple Data Encryption Algorithm Modes of Operation.

IDEA

Bei IDEA (International Data Encryption Algorithm) handelt es sich um einen relativ neuen blockorientierten symmetrischen Verschlüsselungsalgorithmus, der von Xuejia Lai und James L. Massey an der ETH Zürich entwickelt wurde. Eine erste Version stellten die beiden Autoren 1990 unter dem Namen PES (Proposed Encryption Standard) vor. Nachdem Biham und Shamir ihre Methode der differentiellen Kryptoanalyse veröffentlicht hatten, modifizierten Lai und Massey 1991 ihren Algorithmus, um ihn gegen die neue Attacke resistenter zu machen. Sie nannten das Resultat zunächst IPES (Improved Proposed Encryption Standard). 1992 erhielt IPES den heutigen Namen IDEA.

IDEA verfügt über ein recht solides theoretisches Fundament und ist nach Meinung vieler Kryptologen einer der besten und sichersten Blockalgorithmen, der gegenwärtig der Öffentlichkeit zur Verfügung steht, auch wenn er noch keine so umfangreiche Kryptoanalyse erfahren hat wie der DES. Das Verfahren ist in Europa sowie den USA patentiert. Für kommerzielle Anwendungen benötigt man eine Lizenz vom Patentinhaber, der Schweizer Ascom-Tech AG.

Seinen relativ hohen Bekanntheits -und Verbreitungsgrad verdankt IDEA nicht zuletzt der Tatsache, daß er von Phil Zimmermann in den Versionen 2.x des weit verbreiteten Sicherheitswerkzeugs PGP und auch bei SSH sowie bei SSL/TLS genutzt wird. Die Version 1.0 von PGP enthielt noch eine persönliche Kreation Zimmermanns: den Algorithmus Bass-O-Matic. Simson Garfinkel berichtet in seinem Buch über PGP dazu folgende Episode:

1991 weilte Zimmermann auf der jährlich an der University of California at Santa Barbara stattfindenen Crypto Conference, auf der sich die weltbesten Kryptologen treffen. Er wollte jemandem von ihnen seinen Algorithmus zur Begutachtung vorlegen. Adi Shamir, einer der ganz großen Meister seines Faches und Mitautor des RSA-Verfahrens, sagte zu Zimmermann: "send it to Israel and I will spend 10 minutes looking at it".

Etwas später fand Zimmermann Shamirs Kollegen, den schon mehrfach erwähnten Eli Biham, ebenfalls eine Koryphäe auf dem Gebiet der Kryptologie. Er zeigte sich zugänglicher als Shamir und bot an, sich den Algorithmus anzusehen. Zimmermann gab ihm sein wenige Seiten umfassendes Computer-Listing, und innerhalb von wenigen Minuten hatte Biham bereits fundamentale Schwächen gefunden. U.a. entdeckte er einen konzeptionellen Fehler, der verhinderte, daß das letzte Bit jedes Bytes korrekt verschlüsselt wurde. Außerdem war Bass-O-Matic anfällig gegen die differentielle Kryptoanalyse, eines von Bihams Spezialgebieten.

Nach 10 Minuten sah Zimmermann ein, daß sein Verfahren verlorene Liebesmüh war. Er sah auch ein, daß wirklich gute Algorithmen nur von Kryptologen der Weltklasse geschaffen werden können. Phil Zimmermann hatte seine Lektion gelernt.

IDEA ist genau wie DES ein Blockalgorithmus, der 64-Bit-Blöcke mit demselben Key ver- bzw. entschlüsselt und dabei mehrere Runden durchläuft. Das Verfahren arbeitet konkret mit 8 Runden sowie einer sich daran anschließenden Output-Transformation. Die Schlüssel umfassen 128 Bit und sind somit wesentlich länger als bei DES.

Dem Verfahren liegt eine neuartige Design-Philosphie zugrunde, die im Mischen von Operationen unterschiedlicher algebraischer Gruppen besteht. Auch IDEA nutzt eine Kombination von Konfusions- und Diffusionstechniken. Nach Aussage der Autoren wird die notwendige Konfusion durch die aufeinanderfolgende Ausführung dreier "inkompatibler" Gruppen-Operationen auf Paaren von 16-Bit-Subblöcken erreicht. Die erforderliche Diffusion resultiert aus der gewählten Struktur des Verfahrens, die bewußt auch so gestaltet wurde, daß sie sowohl Hard- als auch Software-Implementierungen gestattet.

Zur Manipulation der 16-Bit-Subblöcke kommen die folgenden 3 Gruppenoperationen zur Anwendung:

Bedingt durch die ausschließliche Nutzung von 16-Bit-Subblöcken und den Verzicht auf Bit-Operationen läßt sich IDEA selbst auf 16-Bit-Prozessoren recht effizient implementieren, wenngleich Multiplikationen nicht gerade billige Operationen sind. Aktuelle Software-Implementierungen des IDEA sind nach Aussagen von Schneier ca. doppelt so schnell wie vergleichbare DES-Realisierungen.

Für die Verschlüsselungsalgorithmen DES und IDEA existieren sowohl Hardware- als auch Software-Implementierungen. Bei Rechnernetz-Anwendungen interessiert dabei primär der Durchsatz, der bei Software z.B. mehr als 6 Mbit/s auf einem Pentium-133 und bei Hardware z.T. weit über 100 Mbit/s erreicht.

Es sei noch erwähnt, daß auch bei IDEA eine Klasse schwacher Keys entdeckt wurde, wobei "schwach" hier etwas anders als bei DES aufzufassen ist. Die Details dazu würden allerdings unseren Rahmen deutlich sprengen. Wenn man Keys zufällig wählt, beträgt die Wahrscheinlichkeit dafür, einen schwachen Key gefunden zu haben, 2-96. Man kann diese Gefahr in der Praxis getrost ignorieren. Durch eine leichte Modifikation des Algorithmus läßt sich das Problem der schwachen Schlüssel sogar ganz eliminieren. Man muß dazu nur die intern aus dem Key gebildeten Subkeys mit einer festen Konstante XOR-verknüpfen.

Die Dissertation von Xuejia Lai enthält im Kapitel 3 eine Beschreibung von IDEA. Dieses Kapitel wird zusammen mit einer Implementierung des Algorithmus (z.B. ftp://ftp.cert.dfn.de/pub/tools/crypt/idea/idea.V1.2.tar.Z) in Form einer Postscript-Datei ( ftp://ftp.cert.dfn.de/pub/docs/crypt/IDEA.chap.3.ps.gz) frei verteilt. Aus dieser Datei haben wir die Darstellung des prinzipiellen Ablaufs einer IDEA-Verschlüsselung entnommen, die Sie sich hier ansehen können.


© Holger Trapp, 1.7.1999