Der gefahrlichste Cegner des Kryptographen ist der eigene Kollege. Wer Verfahren ersinnt, geheime Nachrichten zu chiffrieren, muß sich auch mit der Kunst befassen, ohne Kenntnis des Schlüssels aus dem Chiffretext das Original zu rekonstruieren, schon um einem potentiellen Abhörer seine Arbeit möglichst schwer zu machen. Am schönsten – besonders für den Geschäftserfolg – ist es jedoch, wenn es dem Anbieter eines Verschlüsselungssystems gelingt, das Verfahren seines Konkurrenten als unsicher zu entlarven.

Adi Shamir, Mathematikprofessor am Weizmann-lnstitut in Rehovot (Israel) und einer der Schöpfer des bekanntesten Kryptosystems mit veröffentlichtem Schlüssel (die Abkürzung RSA-Chiffre steht für Ronald Rivest, Adi Shamir und Leonard Adleman), hatte somit gute Gründe, einen kryptanalytischen Angriff auf das Verfahren des DES (data encryption standard) zu unternehmen. Dieser Algorithmus war von der Firma IBM entwickelt und l977 vom U. S. National Bureau of Standards zur amerikanischen Norm erhoben worden; er wird vor allem im Datenverkehr der amerikanischen Banken untereinander viel verwendet. Alexander Keewatin Dewdney hat ihn in dieser Zeitschrift in der Rubrik "Computer-Kurzweil" im Januar 1989 vorgestellt.

Als Shamir im Herbst 1991 nach jahrelanger Arbeit einen Erfolg seiner Angriffsversuche über die elektronische Post bekanntgab und viele Zeitungen wenig später diese Meldung aufgriffen, erregte er deshalb zunächst erhebliche Nervosität bei den Sicherheitsbeauftragten der Banken und anderer Institutionen. Immerhin hatte der DES durch einige Umstände bereits Anlaß zum Mißtrauen gegeben.

Die Geheimhaltung der übermittelten Daten hängt an einem Stück Information, das der Absender und der legitime Empfänger kennen und für sich behalten müssen. Dieser Schlüssel ist nur 56 Bits (mit Fehlerkorrektur-Bits 64 Bits) lang. Für den Codebrecher geht es also darum, auf 56 Ja-Nein-Fragen die richtigen Antworten zu finden. Dies durch schlichtes Probieren zu erreichen ist allerdings so mühsam, wie eine Stecknadel in einem Heuhaufen zu finden, der Schleswig-Holstein meterhoch bedeckt: Für 256 (ungefähr 7,2x10¹⁶) Versuche braucht man selbst dann im Durchschnitt länger als 1000 Jahre, wenn man eine Million potentieller Schlüssel pro Sekunde durchprobieren kann.

Der DES-Algorithmus macht aus jeweils 64 Bits des zu verschlüsselnden Klartextes, der als Folge von Bits vorliegen muß, eine ebenso lange BitFolge Chiffretext. Das Verfahren selbst ist in allen Einzelheiten veröffentlicht. Daß es kompliziert ist, verwundert nicht; denn es soll ja – unter Beschränkung auf schnelle Rechenoperationen, die es dem Verschlüsselungscomputer erlauben, mit heutigen Datenübertragungsraten mitzuhalten – die Informationen so unentwirrbar vermischen, daß selbst ein Angreifer, der Zugang zu einem Stück Klartext und dem zugehörigen Chiffretext hat, daraus den Schlüssel nicht ermitteln kann.

Andererseits ist keineswegs einfach zu durchschauen, wie die einzelnen Komponenten zu diesem Zweck zusammenwirken. Es war daher durchaus denkbar, daß in den Chiffretexten, die zunächst von Zufallsfolgen nicht zu unterscheiden sind, doch noch verborgene Korrelationen stecken, die einem Kundigen Rückschlüsse auf den Klartext oder den Schlüssel erlauben.

Diese Zweifel an der Sicherheit des DES wurden noch bestärkt dadurch, daß der USGeheimdienst NSA (National Security Agency ) am Abfassen des Algorithmus beteiligt war und seine Autoren – zur Geheimhaltung verpflichtet – keine Auskunft darüber gaben, warum sie die einzelnen Teilschritte so und nicht anders gewählt hatten. Immerhin wäre es für die NSA nicht uninteressant, den gesamten geheimen Datenverkehr des Landes unbemerkt mitlesen zu können.

Prinzip des DES

Der wesentliche Teil des DES besteht in der sechzehnfachen Wiederholung eines Mischungsprozesses (Bild links). In jedem Schritt wird die eingehende 64-Bit-Folge zunächst in eine linke und eine rechte Hälfte zerlegt. Die rechte Hälfte wird erstens unverändert zur linken Hälfte der Ergebnisfolge, zweitens geht sie in das sogenannte F-Modul ein. Dieser Teil des Programms verwandelt die 32-Bit-Folge mit einem 48 Bits langen Schlüssel in eine andere 32-Bit-Folge, die schließlich mit der linken Hälfte der ursprünglichen Folge zusammengeführt wird: Aus beiden ergibt sich eine neue, gleich lange Folge, in der überall dort eine Null steht, wo die beiden Folgen übereinstimmen, und sonst eine Eins. Das entspricht der logischen Operation des ausschließenden Oder (üblicherweise XOR für exclusive-OR abgekürzt). Diese Folge wird schließlich zur rechten Hälfte der Ergebnisfolge.

Für jedes der 16 Male, die das F-Modul in Aktion tritt, wird ein anderer 48-Bit-Schlüssel verwendet, der seinerseits auf relativ einfache Weise aus dem ursprünglichen 56-Bit-Schlüssel berechnet wird. Das F-Modul verlängert die eingehende 32-Bit-Folge durch Duplizieren ausgewählter Bits auf 48 Bits und verknüpft sie – wieder durch eine XOR-Operation – mit dem Schlüssel. Das Ergebnis wird in acht Portionen zu je sechs Bits zerlegt. Spezielle Funktionen, sogenannte S-Boxes (S wie Substitution), ersetzen jede Portion nach Maßgabe einer jeweils verschiedenen Tabelle durch eine vier Bits lange Folge, so daß durch Zusammensetzen wieder eine 32 Bits lange Folge zustande kommt (Bild rechts).

Analytische Attacke

Diese Struktur bietet Angriffspunkte für ein Analyseverfahren namens differentielle Kryptanalyse, das auf der Korrelationsanalyse von Thomas Siegenthaler von der Eidgenössischen Technischen Hochschule in Zürich aufbaut. Dabei versucht man nicht direkt zu ermitteln, welches Bit etwa an Stelle 37 des Schlüssels steht, sondern wie sich – bei unbekanntem Schlüssel – der Chiffretext ändert, wenn man ein einzelnes Bit im Klartext von 0 auf 1 setzt oder umgekehrt. Im allgemeinen wird sich ziemlich genau die Hälfte der Bits im Chiffretext ändern; man weiß aber nicht welche. Es hängt also, wie zu fordern ist, jedes Ausgangs-Bit von jedem Eingangs-Bit derart ab, daß einfache Rückschlüsse nicht möglich sind.

Etwas übersichtlicher wird die Situation, wenn man sich zunächst auf eine der 16 Mischungsrunden beschränkt. Ändert man ein Bit in der linken Hälfte des Eingangstextes, so ändert sich im Ausgangstext genau das Bit an der korrespondierenden Stelle der rechten Hälfte und nichts sonst. Der Effekt einer Änderung in der rechten Hälfte ist größer, aber immer noch begrenzt. Wenn das betroffene Bit zu denen gehört, die bei der Verlängerung dupliziert werden, betrifft die Änderung zwei (bekannte) Stellen, sonst nur eine. Die XOR-Operation mit dem unbekannten Schlüssel macht zwar den Text selbst unkenntlich, läßt aber das Muster der Unterschiede unberührt: Der ursprüngliche und der variierte Text unterscheiden sich nach der XOROperation genau dort, wo sie sich vorher unterschieden haben. Das erklärt, warum die differentielle Kryptanalyse trotz Unkenntnis des Schlüssels nützliche Aussagen machen kann.

Unter den acht S-Boxes erhalten nun eine oder zwei einen veränderten Eingangstext, so daß am Ausgang des F-Moduls möglicherweise vier bis acht Bits sich verändert haben. Hier vermag man durch genauere Analyse noch Information herauszuholen: Da eine S-Box 64 möglichen Eingangssignalen nur 16 verschiedene Ausgangssignale zuordnen kann (aus sechs Bits werden vier), muß sie häufig aus verschiedenen Eingängen gleiche Ausgänge machen. Ob sie das im Einzelfall tut, kann man zwar ihrem Eingangstext entnehmen, auf den bereits der Schlüssel gewirkt hat, nicht aber dem unverschlüsselten Originaltext. Es läßt sich jedoch auch ohne Kenntnis des Schlüssels mit einer gewissen Wahrscheinlichkeit (typischerweise 25 Prozent) vorhersagen, daß ein gewisses Ausgangsbit einer S-Box unverändert bleiben wird, weil die S-Boxes nicht alle denkbaren Eingangssignale gleich behandeln. Ein kleiner Rest an Information über den Originaltext sickert also sozusagen durch die S-Boxes durch.

Nun bleibt zwar der Effekt einer Ein-Bit-Änderung nach einer Mischungsrunde auf vier bis acht Bits beschränkt. Aber im Verlauf der nächsten Runden breitet er sich aus wie eine Lawine (die Kryptologen sprechen vom avalanche effect) oder wie die von einem kleinen Stein erzeugte Wasserwelle in einem äußerst kompliziert geformten Becken: Sie wird so häufig reflektiert, daß nach kurzer Zeit das verwirrende Muster kleiner Wellen keinen Rückschluß mehr auf den Einwurfsort erlaubt.

Ebenso wie in der Theorie der Wellen kann man sich jedoch in der Kryptanalyse Interferenzeffekte zunutze machen. Wenn sich, zumindest mit einer gewissen Wahrscheinlichkeit, vorhersagen läßt, auf welche Bits sich eine Änderung am Eingang des F-Moduls auswirken wird, kann man die entsprechenden Bits in der linken Hälfte des Originaltextes ebenfalls ändern. Bei der XOR-Verknüpfung dieser beiden 32-Bit-Folgen findet Interferenz durch Auslöschung statt, und insgesamt wird bei der ersten Mischungsrunde aus einem Signal, das rechts an einer, links an mehreren Stellen verändert wurde, eines, das sich nur noch an einer Stelle unterscheidet. Damit ist für dieses spezielle Paar aus Eingangstexten der Lawineneffekt abgewendet und ein wenig Information gerettet – zumindest über die erste Runde.

Im Verlauf der 16 Runden verschmiert sich eine durchaus aussagekräftige Wahrscheinlichkeitsverteilung fast bis zur informationsvernichtenden Gleichverteilung, aber eben nicht gänzlich. Es bleibt eine Aussage des Typs, daß eine Eins an Stelle 29 des Schlüssels um eine Winzigkeit wahrscheinlicher ist als eine Null. Aus vielen Differenzanalysen mit geschickt gewählten Paaren geringfügig verschiedener Klartexte ergibt sich ein zunächst hoffnungslos undeutliches Bild vom Schlüssel. Daraus gewinnt man Anregungen für neue Paare zu testender Klartexte, daraus wieder winzige Körnchen an Information, und so weiter. Im Durchschnitt wird man nach 2⁴⁷ Versuchen den Schlüssel gefunden haben.

Ein nutzloser Erfolg

Was hat man davon? Shamir hat mit ungeheurem Scharfsinn den Aufwand, den der Codebrecher treiben müßte, gegenüber dem schlichten Durchprobieren um den stolzen Faktor 2⁹=512 reduziert. Doch ist 2⁴⁷ (ungefähr gleich 1,4 x 10¹⁴) immer noch eine astronomisch hohe Zahl; der Heuhaufen würde immerhin noch das Stadtgebiet von Husum bedecken. Außerdem müßte der Angreifer absurd günstige Bedingungen vorfinden. Nehmen wir an, Bank A chiffriere ihre Überweisungsaufträge an Bank B mit dem DES, und der Angreifer wolle Bank B glauben machen, sie empfange von Bank A eine Million Dollar zur Gutschrift auf sein Konto. Um an den derzeit gültigen Schlüssel zu kommen, müßte er einen Komplizen in einer der Banken veranlassen, 2⁴⁷ Klartexte seiner Wahl in den Chiffriercomputer einzugeben ( chosen plaintext attack), jedesmal den sich ergebenden Chiffretext abfangen und daraus ein neues Paar von Probiertexten bestimmen – und das alles, ohne daß der immense Datenverkehr innerhalb der Bank jemandem auffiele und bevor die Banken routinemäßig die Schlüssel wechseln.

Das Ergebnis ist also für die Kriminellen enttäuschend, für die Kryptologen dagegen um so interessanter. Shamir hat nämlich herausgefunden, daß der DES der differentiellen Kryptanalyse gerade deswegen so gut widersteht, weil er die wenig plausiblen Komponenten enthält. Warum sind die Tabellen, die den S-Boxes zugrunde liegen, so und nicht anders gewählt? Wenn Shamir einen einzigen Tabelleneintrag ändern darf, behauptet er, könne er aus dem DES ein leicht knackbares System machen. Das gleiche gilt, wenn man auf das Verlängern durch Duplizieren verzichtet oder sich mit weniger als 16 Mischungsrunden begnügt.

Warum wählt man sämtliche 48-Bit-Schlüssel für die 16 Runden als Funktionen des großen 56-Bit-Schlüssels, statt 16 unabhängige Schlüssel mit einer Gesamtlänge von 768 Bit zu verwenden? Weil das nichts einbringt. Es tut der Sicherheit des DES keinen Abbruch, daß die verschiedenen Teilschlüssel in hohem Ausmaß voneinander abhängen.

Diese Ergebnisse legen nahezu zwingend den Schluß nahe, daß den Autoren des DES die differentielle Kryptanalyse geläufig war, bevor Shamir sie aufs neue erfand. Somit endet einer, der auszog, die Kryptologen das Fürchten zu lehren, wie in der Geschichte von Hase und Igel. Inzwischen hat Donald Coppersmith, einer der DES-Schöpfer, nachdem die Geheimhaltung sinnlos geworden ist, sein "Ik bün al da" über die elektronische Post verbreitet: Selbstverständlich habe man diese Technik vorher gekannt.

Coppersmith bedauerte mit gutem Grund, so lange an das Schweigegebot gebunden gewesen zu sein. Er hätte gerne seinen japanischen Kollegen die Schmach erspart, daß immer neue Versionen ihres FEAL (fast encryption algorithm) derartigen Attacken zum Opfer fielen.


Aus: Spektrum der Wissenschaft 5 / 1993, Seite 19
© Spektrum der Wissenschaft Verlagsgesellschaft mbH