Verschicken Sie Briefe mit der Post, so mag es zwar Tage dauern, bis die beim Empfänger ankommen (daher der Spottname Schneckenpost, snail-mail), aber zumindest kann sie kein Fremder unterwegs lesen. E-Mail, das elektronische Pendant, ist zwar blitzschnell, bietet aber kaum Schutz gegen Lauscher. Die Lösung: Sie müssen den Inhalt verschlüsseln, so daß er nur für den rechtmäßigen Empfänger lesbar ist. Schnellere und billigere Computer sowie leistungsstarke Algorithmen haben seit den achtziger Jahren geeignete Systeme allgemein zugänglich gemacht.

Eine Analogie drängt sich auf: Vor vierzig Jahren trieben militärische Einrichtungen wie das Pentagon die Entwicklung spezieller Schaltkreise für Raketen und Flugzeuge voran und förderten so Innovationen in der Elektronik. Heute überwiegt die zivile Nachfrage, und das Militär findet Produkte, die für den breiten Markt entwickelt wurden, mitunter ausreichend für seine Zwecke. In der Kryptographie spielt sich heutzutage Ähnliches ab.

Bis etwa Mitte der siebziger Jahre besaß der geheimste der US-Geheimdienste, die National Security Agency (NSA), praktisch ein Monopol an der amerikanischen Verschlüsselungstechnologie. Das änderte sich 1976, als Whitfield Diffie und Martin E. Hellman von der Universität Stanford (Kalifornien) zum ersten Mal das Verfahren der Public-Key-Kryptographie publizierten (im Deutschen spricht man von Krypto-systemen mit veröffentlichtem Schlüssel beziehungsweise von asymmetrischen Schlüsselsystemen). Seitdem entwickelt sich das Gebiet an Hochschulen wie in Unternehmen energisch, und selbst die NSA deckt mittlerweile ihren Bedarf zumindest teilweise mit kommerziellen Produkten.

Was verlieh der Veröffentlichung von Diffie und Hellman solch durchschlagende Wirkung? Bis dahin diente ein einziger Schlüssel zum Ver- und Entschlüsseln von Nachrichten (also beispielsweise – sehr simpel – eine Konstante, die zur Binärdarstellung einer Nachricht addiert und vom Empfänger wieder subtrahiert wird). Solche symmetrisch genannten Systeme können nur dann funktionieren, wenn der Schlüssel über einen sicheren Kanal übertragen wird, was das Verfahren oftmals unhandlich werden läßt. Wenn man ihn sicher übertragen kann, wieso dann nicht gleich die Nachricht selbst?

Public-Key-Kryptographie arbeitet asymmetrisch, ohne das Transferieren von Schlüsseln zu erfordern. Benötigt werden statt dessen zwei verschiedene, aber komplementäre Schlüssel. Jeder von ihnen entziffert die Nachricht, die der andere codiert, kann aber sein eigenes Werk nicht selbst wieder rückverwandeln. Demnach darf der Besitzer einen davon ohne Bedenken publik machen (public key), während er den anderen (private key) geheimhalten muß. So kann Bob eine Nachricht an Alice mit deren veröffentlichtem Schlüssel chiffrieren, und Alice kann sie dann mit ihrem privaten Schlüssel wieder entziffern (siehe Kasten nächste Seite).

Asymmetrische Kryptographie nutzt die Tatsache, daß sich manche mathematischen Funktionen in einer Richtung recht einfach berechnen lassen, während ihre Umkehrung fast unlösbar ist. Die zwei Hauptvertreter sind der Diffie-Hellman-Algorithmus mit seinen Varianten (zum Beispiel dem Standard für digitale Signaturen des amerikanischen National Institute of Standards and Technology, ElGamal sowie Verfahren, die auf elliptischen Kurven beruhen) und RSA, entwickelt von Ronald L. Rivest, Adi Shamir und Leonard M. Adleman am Massachussetts Institute of Technology in Cambridge (Massachusetts).

Die erste Methode nutzt, daß die Berechnung diskreter Logarithmen schwer ist. Es ist relativ einfach, gx mod p zu berechnen. Man muß nur die Potenz von g berechnen und durch die große Primzahl p teilen, und was übrigbleibt, ist das Ergebnis. Es ist aber fast unmöglich, daraus wieder x zu ermitteln (siehe "Die Mathematik neuer Verschlüsselungssysteme" von Martin E. Hellman, Spektrum der Wissenschaft, Oktober 1979, Seite 92, "Computer-Kurzweil: Über moderne Computer-Verschlüsselungsmethoden ..." von A. K. Dewdney, Spektrum der Wissenschaft, Januar 1989, Seite 6, und "Piraten im Datennetz" von Paul Wallich, Spektrum der Wissenschaft, Mai 1994, Seite 64).

Das RSA-Chiffriersystem beruht auf den Schwierigkeiten der Primzahlzerlegung. Es ist einfach, zwei große Primzahlen miteinander zu multiplizieren, aber sehr schwierig, das Produkt wieder in seine Faktoren zu zerlegen (siehe "Faktorisierung großer Zahlen" von Johannes Buchmann, Spektrum der Wissenschaft, September 1996, Seite 80).

Eine weitere nette Anwendung asymmetrischer Kryptographie ist der Nachweis der Echtheit von Nachrichten. Wenn Bob Alice eine Nachricht sendet, verschlüsselt er sie zuerst mit seinem persönlichen und danach noch einmal mit Alices offenem Schlüssel. Alice verfährt umgekehrt: Sie entschlüsselt die Nachricht zuerst mit ihrem persönlichen Schlüssel und danach noch einmal mit Bobs offenem Schlüssel. Wenn der dechiffrierte Text lesbar ist, muß er von Bob stammen.

Natürlich erfordern diese Prozesse eine Unzahl von mathematischen Berechnungen, aber Computer können bei diesem Unterfangen helfen und den Prozeß automatisieren. Alice und Bob haben nichts weiter zu tun, als "Verschlüsseln" oder "Entschlüsseln" anzuklicken, während alle Rechenoperationen hinter den Kulissen ausgeführt werden.

Doch leider hat die Kryptographie mit öffentlichem Schlüssel zwei Nachteile: Sie ist zu zeitaufwendig für längere Botschaften, und – wichtiger noch – der Chiffrierprozeß läßt manchmal Regelmäßigkeiten im Text unverändert, was den Code leichter zu knacken macht.

Daher nutzt man meist die schnelleren und sichereren symmetrischen Schlüssel, die dann aber ihrerseits mit Public-Key-Kryptographie übertragen werden. So würde Bob seine Nachricht mit einem symmetrischen Schlüssel chiffrieren, den er danach mit Alices veröffentlichtem Schlüssel codiert und der Nachricht für Alice anfügt. Sie dechiffriert zuerst den Schlüssel und kann danach Bobs Nachricht selbst decodieren.

Zum Zwecke der Authentifizierung verläßt sich Bob nicht darauf, einfach seinen verschlüsselten Namen unter die Nachricht zu setzen. Statt dessen berechnet er eine Prüfsumme, ein Kondensat der Nachricht, das typischerweise 160 Bit lang ist. Diese Kennzahl läßt sich durchaus mit einem Fingerabdruck vergleichen. Denn entsprechende mathematische Werkzeuge wie SHA-1, RIPEMD-160 und MD5 machen es fast unmöglich, eine gefälschte Nachricht mit gleicher Kennzahl zu erstellen.

Bob verschlüsselt diese Prüfsumme mit seinem persönlichen Schlüssel und sendet diese "Signatur" mit der chiffrierten Nachricht. Alice decodiert zunächst die Prüfsumme mit Bobs offenem Schlüssel und dann die Nachricht. Anschließend berechnet sie selbst noch einmal die Kennzahl der Botschaft und vergleicht die Ergebnisse. Stimmen beide überein, hat sie die Garantie, daß die Nachricht echt und Bob der Absender ist.

Zur Übertragung wird die Nachricht in Blöcke von konstanter Länge, meist 64 oder 128 Bit, zerlegt und diese dann nacheinander verschlüsselt. Sogenannte Blockchiffren wenden die mathematischen Operationen des Verschlüsselungsalgorithmus gewöhnlich ein paar Mal auf jeden der Blöcke an, wobei jeder Schritt auch Permutationen – etwa den Übergang von "xtv" zu "tvx" – und Substitutionen – etwa "cb2" statt "tvx" – enthalten kann. Das Ergebnis einer Iteration bildet den Input der nächsten; die Zahl der Schritte bestimmt der jeweilige Algorithmus (siehe Kasten).

Würde man identische Textabschnitte mit diesem Verfahren behandeln, ergäben sich identische Datenblöcke. Um das Entstehen solcher Muster im verschlüsselten Text zu vermeiden (weil sie das Knacken des Codes erleichtern würden), verwenden Blockalgorithmen eine Art von Verkettung: Blöcke, die schon verschlüsselt wurden, werden bei der Codierung der darauffolgenden mitverwendet. Im Endeffekt hängt die Codierung eines Blockes von allen vorhergehenden ab (siehe Kasten nächste Seite).

Blockchiffren verwenden symmetrische Schlüssel mit Längen von 56, 128 oder 256 Bit. Bekannte Beispiele sind der Data Encryption Standard (DES), der dreifache DES, CAST, IDEA und Skipjack. Als die Arbeitstiere der Kryptographie sind Blockchiffren Gegenstand intensiver Forschung.



Der Schlüssel liegt im Schlüssel



Die sensibelste Aufgabe in der Kryptographie ist das Berechnen der Schlüssel. Um das System so sicher wie möglich zu machen, müssen sie zufällig und damit unvorhersagbar sein. Zahlen, die solche Schlüssel repräsentieren, müssen von anderer Natur sein als die Pseudozufallszahlen, die Computer für Spiele und Simulationen erzeugen. Vielmehr kann man sie nur von wahrhaft zufälligen Prozessen in der Natur, wie zum Beispiel dem radioaktiven Zerfall, ableiten.

Es ist schwer, solch hochgradig stochastische Prozesse auf einem Computer zu simulieren. Eine Methode ist, die Zeitspanne zwischen aufeinanderfolgenden Tastendrucken eines Nutzers zu messen – auch diese sind nicht vorhersagbar. Die so gewonnenen Daten sind allerdings noch nicht zufällig genug, aber man kann sie noch durch eine Prüfsummenfunktion schicken, die sozusagen die Ordnung herausfiltert und nur noch die schiere Unordnung übrigläßt.

Es ist erwähnenswert, daß der einzige nachweislich vollkommen sichere Code einen Schlüssel verwendet, der von gleicher Länge wie die Nachricht ist und nur einmal verwendet wird (daher die englische Bezeichnung one-time pad, OTP). Das Chiffrieren ist denkbar einfach: Man addiert Nachricht und Schlüssel Bit für Bit ohne Übertrag, also beispielsweise das 34. Bit der Botschaft zum 34. Bit der Zufallsfolge, die als Schlüssel dient. Wegen ihrer Unhandlichkeit werden OTPs aber kaum benutzt: Der lange Schlüssel muß über einen sicheren Kanal zum Empfänger gelangen, und mehrmaliges Verwenden gäbe Lauschern die Möglichkeit zur Dechiffrierung.

Obwohl viele glauben, die Länge eines Schlüssels und damit die Anzahl möglicher Varianten davon bestimme die Qualität des Verfahrens, muß man doch ebensoviel Sorgfalt auf sein Design verwenden. Nehmen wir als Beispiel einen einfachen Substitutionsschlüssel, der alle "A" in "W", alle "B" in "K", alle "C" in "Q" und so weiter umwandelt. Er sollte kaum zu knacken sein, ist doch die Anzahl der möglichen Anordnungen der Buchstaben des Alphabets gleich 26!=26x25x...x3x2x1 oder angenähert 288. Doch schon Kinder brechen diesen Code mit Papier und Bleistift, indem sie den häufigsten Buchstaben in der verschlüsselten Botschaft suchen und dem in der jeweiligen Sprache häufigsten gleichsetzen, dann den zweithäufigsten und so weiter.

In gut entworfenen kryptographischen Systemen hat die Länge des Schlüssels allerdings wirklich direkten Einfluß auf den Aufwand, der zu seiner Brechung erforderlich ist. Für Blockchiffren wächst er gewöhnlich exponentiell, so daß ein einziges zusätzliches Bit im Schlüssel die Arbeit eines Spions verdoppelt. Nimmt man sogar einen Schlüssel von doppelter Länge, so steigt der Aufwand ins Quadrat. Das Knacken eines 128-Bit-Schlüssels erfordert durchschnittlich 2127 Operationen.

Public-Key-Algorithmen sind etwas weniger eindrucksvoll. Die Zahl ihrer Schlüssel wächst gewöhnlich langsamer als eine Exponentialfunktion ihrer Länge, doch schneller als jede Potenz. Verdoppelt man also die Länge eines solchen Schlüssels, ist die Zahl der nun erforderlichen Operationen geringer als das Quadrat der ursprünglichen Anzahl. Ein RSA- oder Diffie-Hellman-Schlüssel, der mit dem gleichen Aufwand aufzulösen sein soll wie ein 128-Bit Blockschlüssel, müßte immerhin 3000 Bit lang sein.

Doch auch Blockchiffren sind nicht unfehlbar. So dechiffrierte ein speziell konstruierter Parallelrechner der Electronic Frontier Foundation in San Francisco eine DES-Botschaft, indem er innerhalb einer Woche alle denkbaren 56-Bit-Schlüssel durchprobierte. Der Computer kostete weniger als 250000 US-Dollar.

Derartige "rohe Gewalt" ist nur eine der Methoden, um Codes zu brechen. Kryptoanalyse stellt leistungsstarke mathematische und statistische Werkzeuge zur Verfügung, um beispielsweise Muster im codierten Text aufzuspüren. Man kann diese Versuche in drei Gruppen einteilen, je nachdem, wieviel man über das Original oder den Codetext weiß.

In manchen Fällen ist der Codetext alles, womit der Spion arbeiten kann – er hat also wenig Anhaltspunkte zum Raten des Schlüssels. Selbst schlecht entworfene Chiffren können einem solchen Angriff widerstehen.

Ist aber wenigstens ein Teil der Nachricht bekannt, zum Beispiel eine Anrede, stehen die Chancen schon wesentlich besser. Zumindest lassen sich nun verschiedene Schlüssel probieren, bis einer etwa den Text "Lieber Bob" in den Anfang der Geheimnachricht verwandelt. Selbst die bloße Kenntnis der Landes- oder Programmiersprache kann schon hilfreich sein – beispielsweise kann man davon ausgehen, daß die häufigsten Worte in einem deutschsprachigen Text die Artikel sind. Um solche Angriffe schon im Keim zu ersticken, komprimieren Verschlüsselungssysteme oftmals das Original, bevor sie es codieren, um alle Muster auszulöschen.

Häufig weiß der Hacker aber sogar sehr viel mehr. Dem Chip einer gestohlenen Scheckkarte kann er Millionen sorgfältig ausgewählter Daten eingeben und die Antworten studieren. Solche Methoden würden einen schlecht entworfenen Code bald brechen. Auch das Public-Key-System läßt sich austesten, etwa durch Chiffrieren spezieller Texte mit dem offenen Schlüssel und Analyse der Ergebnisse (chosen plaintext attack).

Differential- und Linearmethoden sind zwei relativ neue und effektive kryptoanalytische Verfahren, mit denen bereits viele bekannte Blockchiffren geknackt wurden; auch DES läßt sich damit viel leichter entschlüsseln als durch Probieren.

Bei der Differentialanalyse, entwickelt von Shamir und Eli Biham am Technion in Haifa (Israel), werden verschiedene Texte verschlüsselt, die sich in sorgfältig gewählten Punkten unterscheiden. Aus korrespondierenden Differenzen in den Codetexten lassen sich dann Eigenschaften des Schlüssels ableiten (Spektrum der Wissenschaft, Mai 1993, Seite 19).

Linearanalyse, eingeführt von Mitsuru Matsui von der Mitsubishi Electric Corporation, spürt geringfügig stärkere Korrelationen zwischen Original, Codetext und Schlüssel auf und vergleicht die Ergebnisse mit der Statistik einer großen Anzahl von bekannten Original-Codetext-Paaren. Aus bestimmten Abweichungen kann man dann Hinweise auf den Schlüssel erhalten.



Das Problem der Zertifizierung



Trotz ihrer Stärken verlangen kryptoanalytische Methoden oftmals einen ungeheuren Rechenaufwand. Häufig ist es einfacher, statt des Schlüssels selbst seine Implementierung zu attackieren.

Die wichtigste Schwachstelle von Public-Key-Systemen sind Angriffe durch Dritte, die sich in den Übertragungskanal hineinmogeln. Wenn Cindy Bob glauben machen kann, daß sie Alice ist, so daß Bob Cindys offenen Schlüssel statt Alices zur Verschlüsselung benutzt, dann kann sie Bobs Nachrichten lesen (siehe Kasten).

Das läßt sich nur vermeiden, wenn Bob sicherstellen kann, daß er wirklich Alices Schlüssel hat. Die Komplexität von sorgfältig implementierten Public-Key-Systemen besteht im Stopfen eben dieser Lücke. So kann eine vertrauenswürdige dritte Partei für die Echtheit von Alices Schlüssels bürgen, was aber sofort das nächste Problem aufwirft: Soll diese Rolle zentral von der Regierung übernommen oder dezentral Unternehmen und Individuen übertragen werden? Wem darf man trauen (Spektrum der Wissenschaft, Mai 1995, Seite 46)? Dieses brisante Politikum hätte gut und gerne den gesamten Artikel gefüllt.

Codebrechende Verfahren sind stärker und stärker geworden, und kryptographische Methoden wurden gezwungen, mit ihnen Schritt zu halten. Kürzlich hat das National Institute of Standards and Technology AES (Advanced Encryption Code) als den Nachfolger von DES angekündigt, der mit seinem kurzen 56-Bit-Schlüssel und 64 Bit Blocklänge mittlerweile ausgedient hat. AES wird 128-Bit-Datenblöcke mit Schlüsseln von 128, 192 oder 256 Bit Länge chiffrieren.

Gute AES-Designs werden mehrere Kriterien erfüllen. Sie bieten variable Schlüssel- und Blocklängen, sollen effektiv bei der Erstellung von Schlüsseln sowie beim Codieren und Decodieren von Nachrichten sein, und das unabhängig davon, ob sie auf 32-Bit- oder 8-Bit-Technologie implementiert sind. Sie werden sich außerdem durch große Anwendungsbreite, von der Satellitenkommunikation bis zum hochauflösendem Fernsehen, auszeichnen.

Die besseren Vorschläge bauen auf den Erfahrungen von Kryptologen auf, die Blockchiffren durchweg während der letzten 20 Jahre studierten, mit besonderem Schwerpunkt auf der Abwehr von Differential- und Linearanalyseverfahren. Ich glaube, daß von den 15 Vorschlägen mehrere das Zeug dazu haben, zum neuen Standard erklärt zu werden. MARS, das auf den Erfahrungen des originalen DES-Teams bei IBM aufbaut, benutzt zwei total verschiedene Strukturen für den Verschlüsselungsprozeß. Diese Doppelcodierung gewährleistet nach Meinung der IBM-Kryptographen deutlich mehr Sicherheit als der bisherige einfache Prozeß.

Ein anderes Verfahren, CAST-256, erweitert die gegenwärtige CAST-Architektur auf eine Schlüssellänge von 256 Bit und eine Blocklänge von 128 Bit. Der Standard Twofish erfüllt vor allem strengere mathematische Bedingungen als sein Vorläufer, Blowfish. Serpent mit seinem ungewöhnlichen Paralleldesign ist schließlich genauso schnell wie DES, bietet zudem eine rasche Schlüsselerstellung und könnte somit effizient zur Prüfsummenberechnung eingesetzt werden.

Welcher Kandidat auch immer den Zuschlag erhält, AES dürfte die Kryptographie erst einmal effektiver machen. Derzeit sind die besten Verschlüsselungsmethoden außerhalb der Reichweite der besten Codebrecher. Doch ist es vorstellbar, daß neue, leistungsstarke Methoden zum Knacken von Codes schon in den nächsten Jahren entwickelt werden. Aber selbst dann sind Kryptologen zuversichtlich, daß die Kluft zwischen Chiffrierern und Codeknackern nur noch weiter werden wird.

Ich stimme dem zu, und nicht zuletzt deshalb, weil es die Szene der Kryptographen an Universitäten und im Privatsektor mittlerweile mit den besten Experten im Militär aufnehmen kann. Als die NSA den bislang geheimgehaltenen Skipjack-Code für ihren Clipper-Chip freigab, fand der Technion-Kryptologe Biham, daß der Code den besten akademischen Entwürfen deutlich unterlegen war. Wie das Internet ist Kryptographie aus dem Schatten des Militärs herausgetreten und steht nun im grellen Licht des freien Marktes.


Aus: Spektrum der Wissenschaft 3 / 1999, Seite 94
© Spektrum der Wissenschaft Verlagsgesellschaft mbH