Einleitung Kryptoanalyse

Die Kryptoanalyse ist das zweite, schwierigere Teilgebiet der Kryptologie neben der Kryptografie. Hier geht es nicht um das Verschlüsseln, sondern über das Entschlüsseln, ohne dass man über den Schlüssel verfügt. Dazu wird das Chiffrat und ggf. der zugrundeliegende Algorithmus analysiert, um Rückschlüsse auf Klartext und Schlüssel zu ziehen.

Im Altertum wurden Kryptoanalytiker mit Zauberern gleichgesetzt. Das Knacken von Chiffren war eine schwarze Kunst. Wahrscheinlich stellte man sich vor, wie jemand übermächtige, allsehende Geister beschwor, um sie nach Geheimnissen zu befragen. Später hielten sich Könige und Herrscher im Geheimen Geheimsekretäre in sogenannten "schwarze Kammern", die mit Aufgaben der Spionage, dem abfangen, dechiffrieren und fälschen von Nachrichten und dergleichen betraut waren. Ihr Handwerkzeugszeug war nicht nur die Kryptoanalyse sondern auch der Umgang mit Siegellack, Gußformen oder einem heißen Draht, mit dem unbemerkt Siegel geöffnet und wieder geschlossen wurden.

Heutzutage ist die Kryptoanalyse aus dem Dunkel getreten und im Bereich der Wissenschaft angekommen. Heutige Chiffrier-Algorithmen werden frei nach Kerckhoffs Prinzip öffentlich gemacht, damit Kryptoanalytiker nach Schwachstellen suchen und darüber Feedback geben können, um schließlich sichere Algorithmen für Alle zu finden. Außer der militärischen Anwendung auf hohem, professionellen Niveau beschäftigen sich nunmehr auch Hobby-Kryptologen mit dem Knacken von Chiffren - zur Unterhaltung und um geistig fit zu bleiben.

Wie eine Krytoanalyse durchgeführt wird, hängt von den Informationen ab, die dem Analytiker bekannt sind. Meistens wird dem Kryptoanalytiker nur der Geheimtext vorliegen, ggf. noch zusätzlich Worte oder Fragmente, die im Klartext sicher oder mit großer Wahrscheinlich vorkommen. Dann kommen für die Ciphertext-Only-Attacke folgende Angriffsszenarien in Frage:

Verräterisches Aussehen der Chiffre

Mancher Chiffre sieht man schon am Erscheinungsbild an, welche sie ist. Zum Beispiel wenn eine Geheimschrift seltsame Symbole oder Farben benutzt. Bei der Identifizierung der Geheimschrift hilft dann eine Übersicht von Geheimschriftzeichen. Doch meistens wird der Geheimtext mit normalen Buchstaben und Ziffern dargestellt sein. Und wenn die Geheimschrift nicht bereits nach dem ersten Schritt entziffert ist, etwa weil eine weitere Verschlüsselung des Geheimtextes vorliegt (Überschlüsselung gennant), empfiehlt sich die Überführung in normale Buchstaben und Ziffern. Ganz einfach, weil man in den vertrauten Zeichen sehr viel schneller Muster erkennen kann als in ungewohnten Symbolen. Zudem kann man darauf einfacher Software-Werkzeuge anwenden und sich mit Kollegen austauschen, sei es über e-mail oder auch sprachlich ("das D" statt "dieser komischer Kringel mit dem Auswuchs da oben rechts").

Eventuell verrät sich die Chiffre auch durch die verwendete Zeichen. Kommen nur "." und "-" vor, spricht das für Morse. Kommen nur Nullen und Einsen vor, spricht das für einen binären Code. Oder es kommen ausschließlich Ziffern vor (z. B. Straddling Checkerboard). Oder nur Ziffern im Breich 1 bis 5, das spräche für die Verwendung eines Polybios-Quadrats. Oder nur bestimmte Buchstaben, etwa nur ADFGX oder ADFGVX.

Kontext beachten

Nicht nur der Geheimtext selbst, auch die Umgebung, in der er entstand, kann wichtige Hinweise zur Entzifferung liefern. Welche Sprache spricht der Kryptograf und hat er irgendwelche Vorlieben für Passwörter? Gibt es bestimmte Wörter, die häufig in diesem Kontext benutzt werden oder sogar sicher vorkommen? Wie wird wohl der Schreibstil des Klartextes sein - Telegrammstil oder eher ausschweifend? Gibt es viele Nachrichten, die mit demselben Tagesschlüssel verschlüsselt wurden - kann ich also eine statistische Analyse auf höherliegender Ebene fahren? Welches Verschlüsselungsverfahren benutzt der Kryptograf üblicherweise?

Bei Geocaching Mysteries: wie ist die Difficulty-Wertung oder gibt es versteckte Tipps? Wenn im Klartext Koordinaten stehen - welche Zielgegenden kommen in Frage und welche können ausgeschlossen werden (z. B. mittem im See oder auf einem Acker)?

Brute Force Angriff

"Brute Force" lässt sich mit "rohe Gewalt" übersetzen. Besser beschrieben wäre es vielleicht mit "endlose Geduld", denn hier werden alle in Frage kommenden Möglichkeiten der Reihe nach durch probiert, vergleichbar mit einem 3stelligen Zahlenschloss, bei dem man stur alle Zahlen von 000 bis 999 durchprobieren würde. Irgendwann hat man die richtige Zahl erraten und es geht auf.

Bei langen Schlüsseln und komplexen Algorithmen, wie sie moderne Chiffre anwenden, kann diese Durchprobieren allerdings viele Jahre, wenn nicht Jahrtausende dauern, weil die Anzahl der Lösungsmöglichkeiten entsprechend groß ist. Auf der anderen Seite hat man auf alte, klassische Kryptografie-Verfahren mit der heutigen Rechenkapazität durchaus eine reelle Chance, einen Schlüssel in vertretbarer Zeit zu finden.

Ein gutes Beispiel für einen Brute Force Angriff ist, wenn man versucht, den Klartext zu finden, der zu einem vorliegenden Hash passt. Zwar ist die Hashberechnung eine Art Einbahnstraße und man kann einen Hash nicht zum Klartext zurückrechnen, aber man kann viele, viele Klartexte ausprobieren, bis irgendwann einer den richtigen Hash ergibt. Eine Chance, dass dies nicht ewig dauern wird, wird man allerdings nur haben, wenn man die Menge der auszuprobierenden Klartexte begrenzen kann. Sei es, weil man z. B. weiß, dass es sich um Geo-Koordinaten in einem bestimmten Format in einer bestimmten Gegend handelt; oder weil man darauf baut, dass jemand den Fehler gemacht hat, den Vornamen seine(r/s) Liebsten als Passwort zu verwenden. Dann würde man einfach ein Wörterbuch mit allen möglichen Vornamen durcharbeiten. Mit etwas Glück ist der richtige dabei.

Häufigkeitsanalyse

Handelt sich bei der Chiffre um eine monoalphabetische Substitution - also um eine Verschlüsselung, bei der ein Buchstabe immer durch den selben, anderen Buchstaben (oder Symbol) ersetzt wird, dann kann man sich zunutze machen, dass die Häufigkeiten der einzelnen Buchstaben in einer natürliche Sprache nicht gleich verteilt sind, sondern bestimmte Buchstaben häufiger vorkommen als andere, z. B. das 'E' in deutsch und englisch.

Durch das Zählen der Buchstaben von Texten z. B. der deutschen Sprache erhält man eine statistische Häufigkeitsverteilung, die ein durchschnittlicher Klartext aufweisen sollte. Diese kann mit der Häufigkeitsverteilung des Geheimtextes verglichen werden. So kann man z. B. herausfinden, in welcher Sprache der Klartext abgefasst ist, denn die Verteilungen unterscheiden sich je nach Sprache. Auf der anderen Seite: weiß man, dass der Klartext in einer bestimmten Fachsprache abgefasst ist, z. B. Fachbereich Informatik, dann lohnt es sich evtl. IT-Fachliteratur als Grundlage für die Häufigkeitsverteilung zu benutzen, um noch genauere Prozentzahlen für die einzelnen Buchstaben für dieses Fachgebiet zu erhalten.

Stimmt die Verteilung der Buchstaben im Geheimtext mit der Verteilung der deutschen Sprache überein, ist der häufigste Buchstabe also das E mit ca. 17,5% und folgen danach die häufigen Buchstaben im Deutschen und die seltenen Buchstaben im Deutschen kommen im Geheimtext auch selten vor, dann wurde keine Substitution, sondern eine Transposition zur Verschlüsselung gebraucht, bei der die Buchstaben lediglich miteinander vertauscht, aber nicht ersetzt werden.

Nehmen wir an, wir haben es mit einer monoalphabetische Substitution zu tun und das häufigste Zeichen ist das X mit 17,38%, danach folgend das Y mit 10,02% und das Z mit 7,85%. Ein Blick in eine entsprechende Tabelle mit der Häufigkeitsverteilung ergibt, dass im Deutschen die häufigsten Buchstaben eine ganz ähnliche Häufigkeit aufweisen: E mit 17,41%, N mit 9,78% und S mit 7,89%. Dann kann man davon ausgehen, dass das chiffrierte X für ein Klartext-E steht, das Y für ein N und das Z für ein S. Dann ersetzt man entsprechend alle X durch E etc. und führt das für weitere, von der Verteilung eindeutige Buchstaben fort. Damit hat man den Großteil des Klartextes bereits wiederhergestellt. Danach beginnt man zu kombinieren und kurze oder wahrscheinliche Wörter zu erraten. So erkannte und hinzugewonnene Klartextbuchstabe kann man wieder im Chiffrat ersetzen. Das führt man fort, bis der Klartext komplett wiederhergestellt ist. Ggf. helfen Tabellen über die häufigsten Anfangs- und Endbuchstaben oder Bi- (er, en, ch...) oder Trigramme (ich, ein, und...) oder Doppelbuchstaben (ss, nn, ll...).
Bei langen Texte sollten die Häufigkeitsverteilungen ziemlich genau auf die statistischen Werte kommen. Kürzere Texte reichen evtl. nicht für genaue Prozentzahlen, dann ist die Reihenfolge der Häufigkeit evtl. nicht die aus der statistischen Tabelle - evtl. kommt das S im anvisierten Klartext doch häufiger als das N vor. Dann darf man natürlich nicht stur nach Rezept vorgehen, sondern muss auch mal eine andere Reihenfolge probieren. Mit der entsprechenden Geduld ergibt sich dann auch ein lesabrer Klartext.

Es kann allerdings auch sein, dass der Geheimtext keine Häufigkeitsverteilung aufweist, die einer natürlichen Sprache entspricht. Oder das alle Zeichen in etwa gleichverteilt sind. Das spricht für eine Chiffre mit Homophonen oder für eine polyalphabetische Substitution, also Verschlüsselungen, bei denen nicht nur ein Verschlüsselungsalphabet benutzt wird.

Koinzidenzindex

Einen ersten Hinweis darauf kann der Koinzidenzindex geben. Dieser gibt die Wahrscheinlichkeit an, mit der zwei zufällig aus einem Text herausgegriffene Buchstaben übereinstimmen. Für deutsch ist der Koinzidenzindex z. B. 7.6%, für englisch 6.5% und für eine polyalphabetische Substitution ca. 3.85%.

Seite 2 >