Home > Krypto-FAQ > Teil 3
Krypto-FAQ
Hinweis Die [xxx]-Angaben sind noch nicht vervollständigte Verweise auf Bücher in Teil 10, der noch nicht übersetzt ist – aber bald :-)
Die Geschichte beginnt so: Als Julius Caesar Nachrichten an seine Vertrauten schickte, traute er den Boten nicht. Also ersetzte er jedes A durch ein D, jedes B durch ein E und so weiter durch das Alphabet. Nur derjenige, der die "Verschiebung um 3 Positionen"-Regel kannte, vermochte seine Nachrichten zu dechiffrieren.
Ein Kryptosystem oder Chiffresystem ist ein Verfahren, Nachrichten zu verschleiern, so dass nur bestimmte Leute durch diese Verschleierung blicken können. Kryptographie ist die Kunst, Kryptosysteme zu erstellen und zu benutzen. Kryptoanalyse ist die Kunst, Kryptosysteme zu knacken – das heißt, durch die Verschleierung zu schauen, selbst wenn darauf spekuliert wird, dass Sie zu eben dem nicht in der Lage sind. Kryptologie ist das Studium sowohl der Kryptographie als auch der Kryptoanalyse.
Die Originalnachricht nennt man Klartext. Die verschleierte Botschaft Chiffretext. Mit Verschlüsselung ist jede Art von Prozedur gemeint, einen Klartext in einen Chiffretext zu verwandeln. Mit Entschlüsselung meint man dementsprechend Prozeduren, mit denen sich ein Chiffretext in den Klartext umwandeln lässt.
Ein Kryptosystem ist normalerweise eine ganze Ansammlung von Algorithmen. Die Algorithmen werden mit einem "Aufkleber" versehen; die Aufkleber werden als Schlüssel bezeichnet. Caesar z. B. benutzte wahrscheinlich die "Verschiebung um n Positionen"-Verschlüsselung für einige unterschiedliche Werte von n. Es leuchtet ein, dass n in diesem Fall der Schlüssel ist.
Diejenigen, die dazu befähigt sein sollen, durch die Verschleierung zu blicken, nennt man Empfänger. Andere Leute sind Feinde, Gegner, Eindringlinge, Lauscher oder Dritte.
Was eine Einführung in den technischen Bereich anbelangt, so werden Ihnen die Artikel in Teil 10 einen guten Überblick und einen leichten Einstieg verschaffen, da sie im Allgemeinen prägnant und gut geschrieben sind, zudem von kompetenten Leuten verfasst wurden. Allerdings beschäftigen sich diese Artikel zumeist mit der Kryptographie, wie sie sich in den letzten 50 Jahren entwickelt hat und sind eher abstrakt und mathematisch als historisch. The Codebreakers von Kahn [xxx] ist umfassend in der Geschichte und dem technischen Detail der Kryptologie bis in die Mitte der 60er Jahre.
Einführende Kryptoanalyse können Sie von Gaines [xxx] oder Sinkov [xxx] lernen. Dies ist insbesondere für jene Leute empfehlenswert, die einen eigenen Verschlüsselungs-Algorithmus entwerfen wollen, denn es ist ein weit verbreiteter Fehler zu versuchen, ein System zu erstellen, ohne zu wissen, wie man eines bricht.
Die Auswahl eines Algorithmus für den DES lenkte die Aufmerksamkeit von vielen öffentlichen Forschern auf Probleme in der Kryptologie. Konsequenterweise sind einige Lehrbücher zum Thema erschienen. Das Buch von Denning [xxx] vermittelt eine gute Einführung in ein breites Feld der Sicherheit, Verschlüsselungs-Algorithmen, Datenbank-Sicherheit, Zugangskontrolle und formale Sicherheitsmodelle eingeschlossen. Ähnliche Kommentare gelten für die Bücher von Price & Davies [xxx] und Pfleeger [xxx].
Die Bücher von Konheim [xxx] und Meyer & Matyas [xxx] sind eher technisch orientierte Bücher. Sowohl Konheim als auch Meyer waren direkt an der Entwicklung von DES beteiligt, und beide Bücher bieten eine gründliche Analyse von DES. Konheims Buch ist ziemlich mathematisch, mit detaillierten Analysen vieler klassischer Kryptosysteme. Meyer und Matyas konzentrieren sich auf moderne kryptographische Verfahren, insbesondere was Schlüsselverwaltung und die Integration von Sicherheitsangelegenheiten in Computersysteme und Netzwerke anbetrifft. Für eine zeitgemäßere Dokumentation auf verwandten Gebieten, probieren Sie G. Simmons in [xxx].
Die Bücher von Rueppel [xxx] und Koblitz [xxx] konzentrieren sich auf die Anwendung von Zahlentheorie und Algebra auf die Kryptographie.
Klassische Kryptoanalyse umfasst eine interessante Kombination von analytischer Argumentation, Anwendung mathematischer Werkzeuge, das Auffinden von Mustern, Geduld, Entschlossenheit und Glück. Die besten erhältlichen Lehrbücher zum Thema sind die Military Cryptanalytics-Serien [xxx]. Natürlich kann eine gewisse Fertigkeit in der Kryptoanalyse zum größten Teil nur durch das Versuchen von Lösungen für gegebene Systeme erworben werden. Derartige Erfahrungen werden als so wertvoll betrachtet, dass einige der Kryptoanalysen, die während des Zweiten Weltkriegs durchgeführt wurden, immer noch als geheim eingestuft sind.
Moderne Public-Key-Kryptoanalyse kann sich daraus zusammensetzen, eine Ganzzahl zu faktorisieren, oder einen diskreten Logarithmus zu verwenden. Dies sind nicht die traditionellen Mittel des Kryptoanalytikers. Zahlentheoretiker, die mit Computern arbeiten, sind einige der erfolgreichsten Kryptoanalytiker gegen Systeme mit öffentlichem Schlüssel.
In Kürze: Wenn f(x) = y ist, und Sie kennen y und können f berechnen, dann können Sie x finden, indem Sie jedes mögliche x probieren. Das ist Brute-Force-Suche.
Beispiel: Sagen wir, ein Kryptoanalytiker hat einen Klartext und den entsprechenden Chiffretext gefunden, kennt aber den Schlüssel nicht. Er kann einfach versuchen, den Klartext zu verschlüsseln, indem er jeden möglichen Schlüssel probiert, bis das Resultat mit dem Chiffretext übereinstimmt; er kann auch den Chiffretext entschlüsseln, um eine Übereinstimmung mit dem Klartext zu erhalten – was auch immer schneller ist. Jedes gut designte Kryptosystem hat einen so großen Schlüsselraum, dass diese Brute-Force-Suche praktisch undurchführbar ist.
Technologische Fortschritte ändern gelegentlich die Vorstellung von dem, was man als "praktisch" betrachtet. DES z. B., der nun seit über 10 Jahren in Benutzung ist, hat 256 oder ca. 1017 mögliche Schlüssel. Eine Berechnung mit dieser Vielzahl an Operationen war sicherlich sehr ungeeignet für die meisten Benutzer in der Mitte der 70er Jahre. Heute ist die Situation ganz anders, dank der dramatischen Verringerung der Kosten pro Prozessoroperation. Maschinen, die massiv parallel geschaltet sind, bedrohen die Sicherheit von DES gegenüber Brute-Force-Suche. Einige Szenarien werden von Garron und Outerbridge beschrieben [xxx].
Eine Phase einer erfahrenerer Kryptoanalyse kann eine Brute-Force-Suche einiger kontrollierbarer Räume von Möglichkeiten umfassen.
Die Sicherheit eines starken Systems hängt viel mehr mit der Geheimhaltung des Schlüssels als mit der angenommenen Geheimhaltung des Algorithmus zusammen.
Ein starkes Kryptosystem hat einen großen Schlüsselraum, wie oben erwähnt. Es besitzt eine ausreichend große Unizitäts-Distanz; siehe Frage 8.8.
Ein starkes Kryptosystem wird mit Sicherheit Chiffretext produzieren, der allen statistischen Tests (siehe z. B. [xxx]) zufällig erscheint.
Ein starkes Kryptosystem wird allen zuvor angewandten Angriffen widerstehen. Ein System, das noch nie einer genaueren Untersuchung unterworfen wurde, ist verdächtig.
Wenn ein Kryptosystem all die oben genannten Tests besteht, ist es dann notwendigerweise stark? Mit Sicherheit nicht. Viele schwache Kryptosysteme sahen am Anfang gut aus. Manchmal jedoch ist es möglich, durch einen mathematischen Beweis zu zeigen, dass ein Kryptosystem stark ist. "Wenn Joe dieses System brechen kann, dann kann er auch das bekannte schwierige Problem, Ganzzahlen zu faktorisieren, lösen." Siehe Teil 6. [Failing that, it's a crap shoot.]
Kryptoanalytische Verfahren beinhalten etwas, das unter dem Namen "praktische Kryptoanalyse" bekannt ist: der Feind braucht nicht einfach so lange den Chiffretext analytisch auseinander zu nehmen, bis er den Klartext herausfindet. Er kann z. B. die Existenz von cribs annehmen – gestreckte Teile des möglichen Klartextes. Wenn der crib korrekt ist, kann er womöglich den Schlüssel ableiten und dann den Rest der Botschaft dechiffrieren. Oder er könnte isologs ausnutzen – der gleiche Klartext chiffriert in mehreren Kryptosystemen oder mehreren Schlüsseln. Somit kann er möglicherweise Lösungen erhalten, selbst wenn er nach der kryptoanalytischen Theorie keine Chance hätte.
Einige kennen kein besseres. Oft denken Amateure, sie könnten ein sicheres System entwickeln, sind sich aber nicht bewusst, was ein versierter Kryptoanalytiker tun könnte. Und manchmal ist keine ausreichende Motivation für Interessierte vorhanden, die für das Knacken des Systems benötigte Arbeit zu investieren.
Eine Standard-Attacke auf kryptoanalytische Systeme setzt voraus, etwas Klartext, der mit einem gegebenen Stück Chiffretext übereinstimmt, zu kennen und dann zu versuchen, den Schlüssel zu bestimmen, welcher den Klartext auf diesen Chiffretext abbildet. Dieser Klartext kann bekannt sein, weil er Standard ist (ein Standard-Gruß, ein bekannter Header oder Trailer etc.) oder weil er geraten wird. Wird vermutet, dass ein bestimmter Text in einer Botschaft enthalten ist, ist seine Position wahrscheinlich nicht bekannt; jedoch ist eine Nachricht gewöhnlich kurz genug, so dass der Kryptoanalytiker den Text für jede mögliche Position annehmen und Angriffe für jeden Fall parallel starten kann.
Ein starker Verschlüsselungs-Algorithmus ist nicht nur unter bekanntem Klartext (unter der Annahme, dass der Feind den gesamten Klartext für einen gegebenen Chiffretext kennt) unknackbar, sondern auch unter "Adaptive Chosen Plaintext" – eine Attacke, die das Leben für den Kryptoanalytiker erheblich erleichert. Bei dieser Attacke gelingt es dem Feind auszuwählen, welchen Klartext er benutzt; dies gelingt ihm immer wieder, indem er den Klartext für Runde N+1 auswählt, nachdem er das Ergebnis von Runde N analysiert hat.
Zusammengefasst lauten die grundlegenden Typen kryptoanalytischer Angriffe (nach Schwierigkeit für den Angreifer geordnet, die schwerste zuerst):
Ciphertext Only: der Angreifer hat nur die kodierte Nachricht, aus der er den Klartext bestimmen kann, ohne Kenntnis des Letzteren. Ein Ciphertext-Only-Angriff wird normalerweise als möglich vorausgesetzt, und die Widerstandsfähigkeit eines Codes gegen diesen Angriff wird als die Basis seiner kryptographischen Sicherheit betrachtet.
Known Plaintext: der Angreifer ist im Besitz von Klartext und entsprechendem Chiffretext einer beliebigen Nachricht, die er nicht ausgewählt hat. Diese bestimmte Nachricht des Senders gilt nun als kompromittiert. In einigen Systeme kann ein einziges Known Ciphertext-Plaintext-Paar das gesamte System kompromittieren, sowohl frühere als auch nachträgliche Übertragungen, und die Widerstandsfähigkeit dem gegenüber ist ein Charakteristikum einer sicheren Chiffrierung.
Bei den folgenden Angriffen hat der Angreifer die weit weniger wahrscheinliche oder plausible Fähigkeit, den Sender dadurch "auszutricksen", dass dieser beliebige Klartexte oder Chiffretexte ver- oder entschlüsselt. Chiffrierungen, die diesen Angriffen standhalten, werden als äußerst sicher eingestuft.
Chosen Plaintext: der Angreifer hat die Fähigkeit, den Chiffretext zu finden, der einer beliebigen Klartext-Botschaft, der seiner Auswahl entstammt, entspricht.
Chosen Ciphertext: der Angreifer kann beliebigen Chiffretext auswählen und den entsprechenden entschlüsselten Klartext finden. Dieser Angriff kann in Public-Key-Systemen zeigen, wo der private Schlüssel enthüllt werden könnte.
Adaptive Chosen Plaintext: der Angreifer kann den Chiffretext gewählter Klartexte in einem interaktiven oder iterativen Prozess, der auf vorherigen Resultaten beruht, bestimmen. Das ist der allgemeine Ausdruck für ein Verfahren namens "differentielle Kryptoanalyse", Produktchiffren anzugreifen.
Der nächste Teil der FAQ erläutert die mathematischen Details hinter verschiedenen Typen kryptoanalytischer Angriffe.
 Zurück |
nach oben |
 |
 Übersicht |
Weiter  |
Letzte Änderung: 02.04.2002
© 2002 by Christian Thöing