8.2. Kryptographische Algorithmen und Techniken

8.2.1. Einführung

An anderer Stelle wurde bereits auf die große Bedeutung der Kryptographie für die Netzwerk-Sicherheit hingewiesen. Deshalb wollen wir uns mit diesem Thema relativ ausführlich auseinandersetzen. Im vorliegenden Abschnitt wird es zunächst um allgemeine kryptographische Algorithmen und Techniken gehen, die die Grundlage von vielen in der Praxis eingesetzten Sicherheits-Werkzeugen und -Systemen bilden.

Ausgangspunkt ist ein Überblick über zentrale Begriffe und Aufgaben der Kryptologie. Im Anschluß daran werden wir in mehreren Abschnitten ausgewählte Aspekte dreier großer Gruppen kryptographischer Algorithmen diskutieren:

Sie wurden in geringerem Umfang bereits im Teil I des Kurses behandelt. Neu hingegen ist der Abschnitt, der sich mit der Problematik der Erzeugung kryptographisch sicherer Zufallszahlen befaßt.

Beginnen wir mit der Terminologie. Die Begriffe Kryptologie und Kryptographie setzen sich aus den griechischen Wörtern kryptos (geheim) und logos (Wort, Kunde) bzw. graphein (schreiben) zusammen. Manche Autoren verwenden beide Termini weitgehend synonym zur Bezeichnung der Kunst und Wissenschaft, die sich mit den Methoden zur Verheimlichung von Nachrichten beschäftigt. Andere nehmen folgende Unterscheidung vor, der wir uns hier anschließen wollen:

Der grundlegende Dienst der Kryptographie besteht in der Geheimhaltung von übertragenen oder gespeicherten Informationen vor Unbefugten. Kryptosysteme erzielen diese Geheimhaltung, indem sie die Zeichen einer Nachricht derart transformieren (verschlüsseln), daß das im Ergebnis der Operation entstehende Chiffrat für Unbefugte keine rekonstruierbare semantische, statistische oder strukturelle Korrelation zum Original mehr aufweist.

Die moderne Kryptologie, wie sie z.B. im Umfeld der Netzwerk-Sicherheit eine stark wachsende Rolle spielt, basiert auf der Darstellung der Informationen in Form von Zahlen und deren Manipulation unter Anwendung mathematischer Methoden. Es handelt sich also dabei um eine mathematische Disziplin. Kryptologen benötigen eine solide Ausbildung auf verschiedenen Gebieten der Mathematik. Relevant sind u.a. die Zweige Zahlentheorie, Gruppentheorie, Kombinatorik, Wahrscheinlichkeitsrechnung und Statistik, Komplexitätstheorie, Ergodentheorie sowie Informationstheorie.

Neben der Geheimhaltung kann die moderne Kryptologie noch andere Dienste anbieten, die wir bereits bei der Diskussion der Anforderungen an Sicherheits-Architekturen kennengelernt hatten:

Die Nachricht, d.h. die Buchstaben- und Zeichenfolge, die wir übermitteln wollen, wird als Klartext (plaintext, seltener als cleartext) bezeichnet. Die verschlüsselte Nachricht, also die tatsächlich gesendete Zeichenfolge, heißt häufig Geheimtext (ciphertext). Daneben existieren noch weitere deutsche Begriffe: Schlüsseltext, Chiffrat oder in der älteren Literatur auch Kryptogramm.

Die endliche, nichtleere und totalgeordnete Menge der Zeichen bzw. Buchstaben, aus denen die Klar- bzw. Geheimtexte bestehen, nennen wir Alphabet. Prinzipiell kann man für die Klartexte und Chiffrate zwei teilweise oder total verschiedene Alphabete benutzen.

Der Prozeß der Transformation des Klartextes in den Geheimtext wird Verschlüsselung oder Chiffrierung (encryption) genannt. Die Umkehroperation heißt Entschlüsselung oder Dechiffrierung (decryption).

Ein abstraktes Kryptosystem (cryptosystem) kann durch folgende fünf Komponenten charakterisiert werden:

Das Verschlüsselungsverfahren, d.h. der aus den Ver- und Entschlüsselungsfunktionen bestehende kryptographische Algorithmus, wird in der englischsprachigen Literatur meist als cipher bezeichnet. In deutschen Darstellungen findet sich die Entsprechung Chiffre, wobei manche Autoren unter diesem Begriff etwas anderes, nämlich das Geheimtext-Alphabet, verstehen. Wir wollen mit Chiffre immer das Verfahren bezeichnen.

Bei der Entwicklung von Kryptosystemen ist ein ständiges Wechselspiel zwischen Kryptographie und Kryptoanalyse zu beobachten. Kryptographen entwickeln Kryptosysteme, und Kryptoanalytiker versuchen, deren Schwachstellen zu finden und die Verfahren nach Möglichkeit zu brechen. Die dabei gewonnenen Erfahrungen fließen nachfolgend in die Konstruktion neuer Kryptosysteme ein, woraus in der Tendenz deren wachsende Resistenz gegen Attacken resultiert.

Kryptographen müssen zwar prinzipiell immer damit rechnen, daß eine Methode gefunden wird, die es gestattet, ihre Verschlüsselungsalgorithmen zu brechen, allerdings gehen sie in der Praxis von folgendem, auch als Fundamental Tenet of Cryptography bezeichneten fundamentalen Grundsatz aus, auf dem ihr Erfolg beruht:

Wenn es vielen fähigen Leuten bisher nicht gelungen ist, ein bestimmtes Problem zu lösen, dann wird dieses Problem aller Voraussicht nach auch nicht (so bald) gelöst werden.

Bei einem Kryptosystem spielt neben dem Algorithmus, d.h. den umkehrbaren Kryptofunktionen (zur Chiffrierung/Dechiffrierung), in der Regel auch noch mindestens ein geheimer Parameter eine Rolle, den man als Schlüssel (key) bezeichnet. Die Menge aller möglichen Schlüssel nennt man Schlüsselraum (keyspace). Je nach Verfahren kommen unterschiedlich viele Schlüssel fester oder variabler Länge zur Anwendung. Hinsichtlich der Anzahl der Schlüssel gilt (für alle praktisch relevanten Fälle):

Die Nutzung von Schlüsseln hat mehrere Gründe. Die Erfahrung lehrt, daß es nicht trivial ist, neue kryptographisch starke Algorithmen zu entwerfen. Außerdem wäre es kompliziert, jedem Kommunikationspartner einen neuen Algorithmus so mitzuteilen bzw. zu erläutern, daß er (und auch nur er) in der Lage ist, diesen zur Ver- und Entschlüsselung von Nachrichten anzuwenden.

Die Kommunikationspartner benötigen also Chiffren, von denen ihnen Beschreibungen oder wenigstens Implementierungen in Form von Hard- bzw. Software zur Verfügung stehen, so daß man sie ohne vorherige spezielle Erläuterung universell einsetzen kann. Dann genügt es z.B., dem Empfänger mitzuteilen, daß zur Dechiffrierung der IDEA zu verwenden ist, ein in vielen frei zugänglichen Publikationen beschriebenes und in einer Reihe von Werkzeugen implementiertes Verfahren.

Im Text sowie in den Abbildungen wird in der Regel folgende Notation verwendet:

Notation Bedeutung
Funktion XOR
 | Verkettung (concatenation)
{nachricht}K Der Klartext nachricht wurde unter Verwendung eines symmetrischen Verfahrens und dem Secret Key K verschlüsselt, wobei dieser ggf. durch einen tiefgestellten Index näher bestimmt wird, z.B. KAB (als gemeinsam von den Partnern A und B zum Zwecke einer gesicherten Kommunikation verwendeter Key) oder K1.
C = EK(P) Das Chiffrat C ist das Resultat der Verschlüsselung des Klartextes P mit Hilfe der Funktion (bzw. des Algorithmus) E unter Verwendung des Schlüssels K, der bei Bedarf durch einen tiefgestellten Index näher bestimmt wird (z.B. K1). Dabei rühren die Symbole von den englischen Bezeichnungen ciphertext, encryption, key und plaintext her.
P = DK(C) Hier handelt es sich um die Umkehrung der eben gezeigten Verschlüsselung. Der Klartext P ergibt sich durch Dechiffrierung des Chiffrats C unter Verwendung der Funktion D sowie des Schlüssels K. Das neue Symbol D steht für decryption.
SK(M) Die Nachricht M wurde mit dem privaten Schlüssel K signiert. Das Berechnen sowie Verfizieren digitaler Signaturen ist nur im Zusammenhang mit asymmetrischen Verfahren relevant.
VK(M) Hiermit wird die Verifikation einer Signatur der Nachricht M unter Verwendung des öffentlichen Schlüssels K ausgedrückt.

Generell sollte bei der Entwicklung von Chiffren das für die Kryptoanalyse fundamentale Prinzip von Kerckhoffs (benannt nach dem niederländischen Philologen Auguste Kerckhoffs von Nieuwenhof) beherzigt werden:

Die Sicherheit eines Kryptosystems darf nicht von der Geheimhaltung des Algorithmus abhängen. Die Sicherheit gründet sich ausschließlich auf die Geheimhaltung des Schlüssels.

Keinesfalls ist es ratsam, blauäuig darauf zu vertrauen, daß schon niemand den verwendeten Algorithmus erfahren wird. In der Geschichte der Kryptographie hat sich dies vielfach als ein folgenschwerer Irrtum herausgestellt. Ein gutes Kryptosystem zeichnet sich daher dadurch aus, daß man den Algorithmus bedenkenlos offenlegen kann. Solange jemand nur das Verfahren, nicht aber den bzw. die Schlüssel kennt, kann er eine Nachricht auch nicht dechiffrieren.

Es ist heute gängige Praxis, daß die meisten frei oder kommerziell verfügbaren Kryptosysteme veröffentlicht werden. Dies ermöglicht deren umfassende Untersuchung durch viele erfahrene Kryptoanalytiker, was im Sinne der Sicherheit von nicht zu unterschätzender Bedeutung ist, da Fehler bzw. Schwachstellen schneller gefunden werden. Das einem kryptographischen Algorithmus entgegengebrachte Vertrauen hängt zu Recht in entscheidendem Maße von Art und Umfang der kryptoanalytischen Attacken ab, denen das betreffende Verfahren erfolgreich standgehalten hat.

Militär und Geheimdienste setzen in der Regel geheime Chiffren ein, vermutlich primär deswegen, um dem Gegner den Zugang zu starken Algorithmen und deren Design-Prinzipien zu erschweren. Mitunter verzichten auch kommerzielle Hersteller auf die Veröffentlichung ihrer Kryptosysteme, z.B. um Geschäftsgeheimnisse zu wahren oder leichter eine Exportgenehmigung von den zuständigen Behörden zu bekommen. Natürlich bleibt hierbei immer das Risiko, daß die Geheimhaltung auch der Sicherheit dienen soll (was unter Beachtung des Prinzips von Kerckhoffs völlig inakzeptabel ist) oder daß ernste Schwächen nicht gefunden wurden, die bei öffentlicher Diskussion bereits entdeckt worden wären.

Wer einen zuverlässigen kryptographischen Schutz seiner Daten wünscht, ist daher gut beraten, auf diejenigen (relativ wenigen) Verfahren zurückzugreifen, die veröffentlicht und von den weltbesten Kryptologen (zumindest von jenen, die ihre Resultate publizieren) über mehrere Jahre hinweg massiv und unabhängig voneinander attackiert wurden, ohne dabei gebrochen worden zu sein.

Um Kryptosysteme in der Praxis nutzen zu können, müssen sie denjenigen, die im Besitz eines gültigen Schlüssels sind, eine relativ effiziente Ver- und Entschlüsselung erlauben. Andererseits soll natürlich eine Dechiffrierung des Geheimtextes ohne Kenntnis des Schlüssels so schwer wie möglich sein.

Das sog. One-time Pad stellt das einzige Verfahren dar, das sich unabhängig von der zur Verfügung stehenden Rechenleistung nachweislich nicht brechen läßt, da selbst beliebig viel Geheimtext nicht genug Informationen liefert, um daraus den Klartext oder den Schlüssel rekonstruieren zu können. Deshalb bezeichnet man diese Chiffre auch als absolut bzw. theoretisch sicher. Der Klartext wird mit dem Schlüssel XOR-verknüpft:

Da uns die Funktion XOR noch häufiger begegnen wird, wollen wir an dieser Stelle eine Diskussion ihrer für uns interessanten Eigenschaften einschieben. Die Wertetabelle sieht so aus:

a b a  XOR  b
0 0 0
0 1 1
1 0 1
1 1 0

Eine 1 ergibt sich also genau dann, wenn die beiden verknüpften Werte unterschiedlich sind. Außerdem gelten die folgenden 3 Gleichungen:

(1)   a  XOR  a = 0
(2)   a  XOR  0 = a
(3)   a  XOR  b  XOR  b = a
Betrachtet man in (3) die Variable a als Klartext, b als Schlüssel und den Ausdruck a XOR b als Geheimtext, dann gilt, daß der durch eine XOR-Verknüpfung mit dem Schlüssel generierte Geheimtext durch dieselbe Operation (d.h. durch die XOR-Verknüpfung mit dem Schlüssel) in den Klartext überführt, also dechiffriert wird.

Wir stellen fest, daß die Funktion

(4)   f(a) = a  XOR  b
ihre eigene inverse Funktion darstellt. Dies gilt unabhängig von der Komplexität des sich hinter dem Operanden b verbergenden Konstrukts. Daher spielt XOR in der Kryptologie an vielen Stellen eine Rolle. Jede gemäß (4) aufgebaute Funktion kann auf Grund ihrer garantierten Invertierbarkeit prinzipiell als Verschlüsselungsfunktion in einem Kryptosystem dienen, wobei sie sich durch eine geeignete Wahl von b beliebig sicher gestalten läßt. Außerdem ist von Vorteil, daß ein und dieselbe Funktion sowohl zur Chiffrierung als auch zur Dechiffrierung verwendet wird, so daß die Notwendigkeit entfällt, zwei unterschiedliche Algorithmen implementieren zu müssen.

Beim One-time Pad wird als Schlüssel eine echt zufällige Bitfolge verwendet. Auf dem Rechner generierte Pseudo-Zufallsfolgen taugen hierfür nicht! Jeder Key hat dieselbe Länge wie die zu chiffrierende Nachricht (da pro Bit des Klartextes ein Bit des Schlüssels verbraucht wird) und kommt nur genau einmal, also für genau eine Nachricht zur Anwendung.

Lediglich der Besitzer einer Kopie des Schlüssels (in der Regel der Empfänger) kann die ursprüngliche Information zurückgewinnen. Mit Methoden der Kryptoanalyse ist der Klartext dagegen nicht ermittelbar, da es sich bei dem verschlüsselten Text genau wie beim Schlüssel um eine echt zufällige Bitfolge handelt.

Für die meisten Anwendungen ist dieses Verfahren nicht praktikabel, da die Erzeugung und die sichere Verteilung der Schlüssel (d.h. langer Zufallsfolgen) an die einzelnen Kommunikationspartner einen unvertretbar hohen Aufwand erfordern.

Für unsere Anwendungszwecke sind primär die als stark bzw. praktisch sicher bezeichneten Chiffren interessant, also jene, für die kein Algorithmus bekannt ist, welcher das Kryptosystem mit den heute und in absehbarer Zukunft verfügbaren Ressourcen und vertretbarem Kosten- bzw. Zeitaufwand brechen kann.

Natürlich besteht bei den praktisch sicheren Verfahren immer die theoretische Möglichkeit, den Schlüsselraum vollständig zu durchsuchen, bis man auf den richtigen Schlüssel stößt und so in der Lage ist, den Geheimtext zu dechiffrieren. Dieses Vorgehen wird auch als Brute-force Attack bezeichnet. Sie scheitert jedoch bei guten Chiffren am dafür notwendigen riesigen Aufwand. Allgemein sollte man stets dafür sorgen, daß die Kosten für das Brechen eines Kryptosystems deutlich höher sind als der Wert der dabei gewonnenen Daten.

Bedingt durch technologische Fortschritte in der Computertechnik werden die Rechner deutlich schneller und gestatten es, pro Zeiteinheit immer mehr Schlüssel zu testen. Auf die daraus resultierende Bedrohung der Sicherheit eines Verfahrens kann man in der Regel recht effektiv und schnell durch die Nutzung längerer Schlüssel reagieren. Dadurch läßt sich der dem Angreifer entstehende Aufwand schlagartig um Größenordnungen erhöhen. Speziell bei Algorithmen mit variablen Schlüssellängen ist das sehr einfach möglich. Die Erweiterung des Schlüssels um n Bits hat zur Folge, daß bei einer Brute-force-Attacke die 2n-fache Anzahl von Keys durchsucht werden muß.

Auch für den legalen Nutzer eines Kryptosystems resultiert aus den längeren Schlüsseln ein Mehraufwand, der allerdings deutlich geringer als beim Angreifer ausfällt. So verursacht z.B. die Verdopplung der Schlüssellänge von 56 auf 112 Bit beim Triple DES eine Verdreifachung der Anzahl der vom Schlüsselinhaber auszuführenden Operationen. Der Aufwand für den Angreifer wächst dagegen nicht so moderat linear, sondern exponentiell mit dem Faktor 256.

Von der steigenden Rechenleistung der Maschinen profitieren also tendenziell ganz klar die legalen Nutzer von Kryptosystemen, da die Schlüssel so verlängert werden können, daß deren Besitzer keine zeitlichen Einbußen bei der Ver- und Entschlüsselung hinnehmen müssen, wogegen der Aufwand für den Angreifer trotz der schnelleren Technik nicht sinkt, sondern in der Regel deutlich steigt.

Trotzdem werden in letzter Zeit verstärkt Experimente mit Brute-force-Attacken initiiert. Man macht sich dabei zunutze, daß sich die Arbeit bei einem solchen Angriff sehr gut aufteilen läßt, auch auf Rechner sehr unterschiedlicher Leistung und mit verschiedenen Betriebssystemen. Auf einem zentralen Rechner wird ein Server installiert, der den Schlüsselraum verwaltet und den an der Attacke beteiligten Klienten einen jeweils ihrer Leistung angemessenen Schlüsselraum zuweist. Damit lassen sich sehr große Mengen von Rechnern zusammenziehen und ansonsten "verlorengehende" Rechenkapazitäten nutzen.

Auf diese Weise ist es z.B. schon mehrfach gelungen, Lösungen für verschiedene sog. DES- und RC5-Challenges zu finden. Im Rahmen der ersten von der Firma RSA Data Security Inc. (RSADSI) initiierten DES-Challenge wurde am 17. Juni 1997 erstmals ein in ca. 119 Tagen gebrochener DES-Schlüssel öffentlich präsentiert. Die DES-Challenge III von RSADSI wurde sogar in nur 22 Stunden und 15 Minuten gelöst. Dabei ist allerdings zu beachten, daß die ersten 24 Zeichen des Klartextes bei allen DES-Challenges von RSADSI öffentlich bekannt sind und immer "The unknown message is: " lauten. Nähere Informationen zu dieser Thematik finden Sie z.B. auf folgenden WWW-Seiten:

Mag der wissenschaftliche Wert dieser Aktivitäten auch relativ gering sein (daß Brute-force-Attacken prinzipiell in einer vorher berechenbaren Maximalzeit zum Ziel führen, ist bekannt), so wird doch bewiesen, daß durch die Nutzung des Netzes mit überschaubarem Aufwand Schlüssel zu brechen sind, die als nicht brechbar galten. Mit der Etablierung von "MilliCash"-Systemen, also Bezahlung von Kleinbeträgen im Netz, kann man vielleicht in wenigen Jahren sehr preiswert Rechenleistung einkaufen. Wer wäre nicht gern bereit, seinen Privat-PC für ein paar Dollar pro Nacht arbeiten zu lassen?

Damit wird auch eine andere Sichtweise auf die Sicherheit von Kryptosystemen deutlich: Wie teuer ist es, einzelne Schlüssel zu brechen? Wenn ein Schlüssel in einer bestimmten Zeit gebrochen werden soll, kann anhand der Größe des Schlüsselraumes berechnet werden, welche Menge an Rechentechnik dafür benötigt wird. Folglich kann man auch einen Preis für das Brechen dieses Schlüssels nennen. Die Sicherheit eines Schlüssels läßt sich also ohne großen Aufwand in Dollar oder Mark (bzw. Euro) umrechnen. Die Frage des Anwenders sollte weniger darauf abzielen, ob sein System sicher ist oder nicht, sondern bis zu welchem Preis es sicher ist.

Ungeachtet der erfolgreichen Lösung der in verschiedenen Challenges gestellten Aufgaben bleiben Brute-force-Attacken im allgemeinen ein ineffizientes Mittel für Angriffe, sie helfen aber, das Augenmerk auf die Notwendigkeit guter Kryptosysteme zu lenken und den gesetzlichen Spielraum für ihre Anwendung zu schaffen.

Kryptoanalytische Attacken

Kryptoanalyse verfolgt das Ziel, den zu einem Geheimtext gehörenden Klartext bzw. den zur Chiffrierung verwendeten Schlüssel zu ermitteln, d.h., ein Kryptosystem zu brechen. Gemäß dem Prinzip von Kerckhoffs nehmen wir an, daß der Kryptoanalytiker die verwendeten Algorithmen, nicht aber den jeweils genutzten Schlüssel kennt. In Abhängigkeit davon, welche Informationen für die Analyse zur Verfügung stehen, unterscheidet man zwischen unterschiedlichen Arten von Attacken. Drei elementare Formen sind die folgenden:
  1. Ciphertext-only Attack: Der Kryptoanalytiker verfügt über den Geheimtext mehrerer Nachrichten, die alle mit demselben Algorithmus chiffriert wurden. Es ist in der Regel sehr leicht, sich solche Chiffrate zu beschaffen. Das Ziel besteht im Auffinden der zugehörigen Klartexte und nach Möglichkeit auch der Keys, um so andere Nachrichten leicht dechiffrieren zu können.

    Der Kryptoanalytiker muß eine grobe Vorstellung von der Struktur des Klartextes (englischer Text, C-Programm, Postscript-Datei, ...) haben, da er sonst nicht entscheiden kann, ob eine vorgenommene Dechiffrierung erfolgreich war oder nicht.

    Da es meist kein großes Problem darstellt, Chiffrate zu beschaffen, muß jedes Kryptosystem zumindest gegen Ciphertext-only-Attacken sicher sein. In vielen Fällen reicht das allerdings nicht aus, da der Kryptologe zusätzliche Informationen ermitteln kann, so daß ein Algorithmus auch den nächsten beiden Attacken standhalten muß.

  2. Known-plaintext Attack: Der Kryptoanalytiker kennt zumindest für einige Nachrichten sowohl den Klartext als auch das Chiffrat. Seine Aufgabe besteht nun darin, den zur Verschlüsselung verwendeten Key zu finden oder einen Algorithmus zu entwickeln, der es gestattet, den Klartext aller mit demselben Key chiffrierten Nachrichten zu berechnen.

    Diese Attacke ist gar nicht so selten, wie sie auf den ersten Blick erscheinen mag. Oft weiß ein Angreifer grob, worum es bei einer Kommunikation geht, und kann so charakteristische Wörter oder Wortgruppen etc. erraten. Auch feste Eröffnungs- und Schlußfloskeln erleichtern ihm die Arbeit deutlich.

  3. Chosen-plaintext Attack: In relativ seltenen Fällen ist der Kryptoanalytiker in der glücklichen Lage, sich jeden beliebigen Klartext mit einem bestimmten Key verschlüsseln lassen zu können. Er kennt dann Paare von Klar- und Geheimtext, deren Klartext er aber selbst gewählt hat, was u.U. für ihn sehr vorteilhaft sein kann, da speziell strukturierte Klartexte ggf. mehr Informationen über den Schlüssel liefern als andere. Sein Ziel besteht wie bei der Known-plaintext-Attacke darin, den zur Verschlüsselung verwendeten Key zu ermitteln oder einen Algorithmus zu entwickeln, der es gestattet, den Klartext aller mit demselben Key chiffrierten Nachrichten zu berechnen.
Bei der Analyse von Kryptosystemen kommen im wesentlichen folgende Strategien zum Einsatz, die meist kombiniert werden:


© Holger Trapp, 30.6.1999
Ralph Sontag, 3.7.1997