Einführung in die Kryptoanalyse Marc Ruef Alle Rechte vorbehalten - Kopieren erlaubt! Sinn und Zweck der Kryptographie ist es, Daten von der Einsicht vor unberechtigten Personen zu verbergen. Dabei ist es im Gegensatz zur Steganographie irrelevant, ob der Gegner das Wissen um die geheime Kommunikation haben darf. In den meisten Fällen hat der Angreifer sogar vollständigen Zugriff auf die verschlüsselte Kommunikation. Die Kryptoanalyse versteht sich nun als Teilgebiet der höheren Mathematik, das von der Wiederherstellung des Klartextes einer Nachricht ohne Zugriff auf den geheimen Schlüssel lebt. Eine Kryptoanalyse wird insofern als erfolgreich eingestuft, wenn der vermeindlich codierte Klartext oder genutzte geheime Schlüssel ermittelt werden konnte. Dabei können explizit auch Schwachstellen in einem Algorithmus offengelegt werden, die schlussendlich zum identischen Ziel führen könnten. Eine versuchte Kryptoanalyse wird simpel als "Angriff" bezeichnet und der Verlust eines Schlüssels durch nicht-kryptoanalytische Mittel "Kompromittierung" genannt. Die der neuzeitlichen Kryptographie zugrundelegende Maxime, welche im 19. Jahrhundert erstmalig vom Niederländer A. Kerckhoff aufgestellt wurde, besagt, dass die Sicherheit eines Verschlüsselungsverfahrens nur von der Geheimhaltung des Schlüssels abhängen darf. Der Mathematiker Kerckhoff geht davon aus, dass dem Kryptoanalytiker alle Einzelheiten des kryptographischen Algorithmus und seiner Implementierung bekannt sind. Diese Annahme ist als durchaus sinnvoll zu erachten, obwohl der gemeine Kryptoanalytiker in der grauen Realität nur in den seltensten Fällen über eine solch umfassende Kompetenz verfügen vermag. Wenn man den Algorithmus selbst mit dem Wissen um die Arbeitsweise nicht brechen kann, dann geht es ohne ganz sicher auch nicht. Vielerorts wird trotzdem "security by obscurity" (Sicherheit durch Geheimhaltung) betrieben, was wie das Beispiel um die Verschlüsselungssequenzen (COMP128) im GSM-Netz in den meisten Fällen zum Verhängnis werden kann. Hätten die Netzbetreiber vor der Einführung des proprietären Algorithmus jenen zur öffentlichen Inspektion präsentiert, wären die potentiellen Fehlerquellen nicht durch die zeitabhängige Verwurzlung zur sich exponentiell ausweitenen Gefahr geworden. Wer also behauptet, sein Codierungsverfahren sei sicher und müsse nicht von einer unabhängigen Stelle zertifiziert werden, der ist entweder ein Genie oder ein Dummkopf. Leider werden letztere in unserer Welt mehr gesichtet... Die Angriffsformen Grundsätzlich lassen sich vier Arten von kryptoanalytischen Angriffen unterscheiden. Es wird generell davon ausgegangen, dass der Kryptoanalytiker den Verschlüsselungsalgorithmus genau kennt: 1. Ciphertext-only-Angriff: Der Kryptoanalytiker verfügt über den Chiffretext mehrerer Nachrichten, die mit dem selben Verschlüsselungsverfahren codiert wurden. Seine Aufgabe besteht nun darin, den Klartext möglichst vieler Nachrichten wiederherzustellen. Das ultimative Ziel bei einer solchen Attacke wäre natürlich den genutzten Schlüssel ableiten zu können. Dadurch wäre eine weitere Dechiffrierung sehr vereinfacht. 2. Known-plaintext-Angriff: Der Kryptoanalytiker besitzt bei dieser Attacke neben dem Zugriff auf den Chiffretext auch jenen auf den dazugehörigen Klartext diverser Nachrichten. Seine Aufgabe besteht nun darin, in den Besitz des genutzten Schlüssels oder den Algorithmus zu kommen, mit welchem man codierte Nachrichten entschlüsseln kann. 3. Chosen-plaintext-Angriff: Der Kryptoanalytiker verfügt nicht nur über den Chiffretext und Klartext diverser Nachrichten, sondern findet sich in der erfreulichen Lage wieder, den zu verschlüsselnden Klartext selber definieren zu dürfen. Damit bieten sich ihm natürlich erweiterte Vorteile im Gegensatz zum known-plaintext-Angriff, da er gezielte Klartextblöcke zur gewollten Codierung definieren darf. Dadurch kann er unter Umständen wichtige Informationen über den verwendeten Schlüssel herausfinden. Seine Aufgabe besteht nun darin, den zur Chiffrierung der Nachricht verwendeten Schlüssel herauszubekommen oder einen Algorithmus zu finden, mit dem weitere Nachrichten dechiffriert werden können, die mit dem gleichen Schlüssel generiert wurden. 4. Adaptive-chosen-plaintext-Angriff: Der Kryptoanalytiker schlägt sich hierbei mit einem Spezialfall der chosen-plaintext-Attacke herum. Er kann nicht nur den zu verschlüsselnden Klartext wählen, sondern seine Auswahl auch beliebig variieren, indem er die Ergebnisse der vorangehenden Verschlüsselung berücksichtigt. Bei einem chosen-plaintext-Angriff kann er am Besten einen relativ grossen Block Klartext verwenden; beim adaptive-chosen-plaintext-Angriff hingegen kann er einen kleinen Klartextblock verschlüsseln lassen und auf den Ergebnissen aufbauend einen zweiten Auswählen. Diese lineare Verknüpfung zieht sich alsdann durch seine gesamte Analyse. Es gibt hingegen noch drei weitere Arten kryptoanalytischer Angriffe: 1. Chosen-ciphertext-Angriff: Der Kryptoanalytiker kann diverse Chiffretexte zur Decodierung auswählen und hat Zugriff auf den entschlüsselten Klartext. Seine Aufgabe besteht nun darin, den eingesetzten Schlüssel herauszufinden. Diese Sorte Angriff eignet sich primär für Algorithmen mit publizierten Schlüsseln, also asymmetrische Verfahren wie zum Beispiel RSA. Ein chosen-ciphertext-Angriff darf ab und an auch bei einem symmetrischen Verfahren Erfolge verbuchen. Eine Kombination aus chosen-plaintext- und chosen-ciphertext-Angriff wird auch chosen-text-Angriff genannt. 2. Chosen-key-Angriff: Der Kryptoanalitker darf bei dieser Angriffsform den Schlüssel nicht frei wählen, obwohl dies der Titel eigentlich vermuten lässt. Vielmehr hat er das Wissen um die Zusammenhänge zwischen verschiedenen Schlüsseln. Diese Angriffsart ist relativ ungewöhnlich und spielt in der Praxis keine besondere Rolle. 3. Kryptoanalyse mit Gewalt: Der Kryptoanalytiker bedroht, erpresst oder quält jemanden solange, bis er ihm die gewünschen Informationen über das kryptographische System überlässt. Bestechung wird auch mit "Angriff mit gekauftem Schlüssel" betitelt. All diese ethisch verwerflichen Angriffsmethoden sind äusserst wirkungsvoll und oft der einfachste Weg, einen Algorithmus zu knacken. Know-plaintext- und chosen-plaintext-Angriffe sind relativ beliebt und werden in der Praxis des Öfteren angetroffen. Dabei kann es natürlich vorkommen, dass ein Kryptoanalytiker sich einen Klartext verschafft, der verschlüsselt wurde oder jemanden besticht, der ihm dann eine vordefinierte Nachricht codiert. Manchmal kann man aber die Brechstange zurückstecken und eleganter an das Problem herangehen: Übergibt man zum Beispiel einem Botschafter eines Landes eine Nachricht, so wird jene vermutlich chiffriert zur Begutachtung ins Heimatland übertragen werden. Da formelle Nachrichten sich oft identischer oder nur leicht variierten Floskeln bedienen, ist es dann ein Leichtes, daraus logische Schlüsse ziehen zu können. Gleiches Problem tritt bei verschlüsselten Quellcodes auf, da oft die gleichen Funktionsaufrufe, Variablendefinitionen und Schleifenstukturen genutzt werden. Im zweiten Weltkrieg wurden erfolgreich known-plaintext- und sogar chosen-plaintext-Angriffe gegen die Deutschen und Japaner geführt, wie unter anderem in den Büchern von David Kahn und Bauer in historischen Beispielen dokumentiert wurde. Die Sicherheit eines Algorithmus Die verschiedenen Kryptoalgorithmen bieten ein unterschiedliches Mass an Sicherheit, welches davon abhängt, wie schwer er zu knacken ist. Wenn der für das Aufbrechen des Verfahrens nötige Aufwand den Geldwert der versteckten Informationen übersteigt, so sind sie wahrscheinlich sicher. Zugleich, wenn der Zeitaufwand grösser als die Zeitspanne ist, die die chiffrierten Daten geheim bleiben müssen, so sind sie wahrscheinlich auch sicher. Zu guter Letzt kann behauptet werden, dass wenn das mit einem bestimmten Schlüssel codierte Datenvolumen kleiner als die Datenmenge ist, die zum Brechen des Algorithmus erforderlich wäre, sind sie wahrscheinlich auch sicher. Diese drei Grundsätze könnten jedoch mit einem eventuell nahenden Durchbruch in der Kryptoanalyse erschüttert werden. Lars Knudsen unterteil das Knacken eines Algorithmus in vier verschiedene Kategorien, die mit der sinkenden Schwere wie folgt definiert sind: 1. Vollständiges Brechen: Ein Kryptoanalytiker findet den Schlüssel K, für den DK(C) = P gilt. 2. Globale Deduktion: Ein Kryptoanalytiker findet ohne Kenntnis von K einen alternativen Algorithmus A, der aquivalänt zu DK(C) ist. 3. Punktuelle/lokale Deduktion: Ein Kryptoanalytiker ermittelt den Klartext zu einem abgefangenen Chiffretext. 4. Informationsdeduktion: Ein Kryptoanalytiker gelangt an Informationen über den Schlüssel oder den Klartext. Diese könnten aus einigen Bits des Schlüssels Hinweise zum Format des Klartextes oder ähnliches offenlegen lassen. Ein Algorithmus ist uneingeschränkt sicher, wenn der Klartext auch dann nicht ermittelt werden kann, wenn chiffrierte Daten in beliebigem Umfang vorhanden sind. Tatsache ist, dass nur ein One-time-pad bei unbegrenzten Ressourcen nicht zu knacken ist. Alle anderen Kryptosysteme können mit einem ciphertext-only-Angriff gebrochen werden, indem einfach alle denkbaren Schlüssel anhand des sogenannten primitiven Brute-Force-Angriff ausprobiert werden. Die neu gewonnenen Chiffretexte müssen dann nur noch auf einen Sinn hin analysiert werden, um den Gutfall der Attacke feststellen zu können. Die Komplexität eines Angriffs Die neuzeitliche Kryptographie befasst sich seit der rasant fortschrittlichen Entwicklung in der Halbleitertechnik eher mit Kryptosystemen, die mit angemessenem Berechnungsaufwand nicht geknackt werden können. Ein Verfahren gilt als stark, wenn es mit derzeit und auch den in naher Zukunft vorhandenen Ressourcen nicht gebrochen werden kann. Die Interpretation dieses Satzes ist dem Leser überlassen, der höchstens mit wahrsagerischen Kräften die nahe Zukunft in die Studie einfliessen lassen könnte... Die Komplexität eines Angriffs lässt sich an drei verschiedenen Kriterien messen: 1. Datenkomplexität: Die Menge an Eingabedaten, die zur Durchführung einer erfolgreichen Attacke erforderlich ist. 2. Berehnungskomplexität: Die Zeit, die zur Durchführung eines erfolgreichen Angriffs erforderlich ist. 3. Speicheranforderungen: Der Speicherplatz, der zur Durchführung einer erfolgreichen Attacke erforderlich ist. Als Faustregel sollte man den Aufwand für einen Angriff mit dem Minimum dieser drei Faktoren abschätzen. Bei manchen Angiffen müssen diese jedoch gegeneinander abgewägt werden. So können unter Umständen Einbussen beim Faktor Zeit erreicht werden, insofern genügend Speicherplatz vorhanden ist.