AES unter Beschuss
Kürzlich veröffentlichten Wissenschaftler ein Verfahren für einen Angriff gegen das bisher als sehr sicher geltende Verschlüsselungs-verfahren AES. Es wirft die Frage auf, ob AES damit für seine Rolle als Nachfolger für DES noch geeignet ist.
- Dr. Reinhard Wobst
Am 2. Oktober 2000 wurde der Algorithmus Rijndael zum neuen Verschlüsselungsstandard AES erkoren. Unter den fünf Endkandidaten des Wettbewerbs um die DES-Nachfolge erschien er als geeignetster: außerordentlich schnell, einfach, Ressourcen sparend und hoffentlich jahrzehntelang sicher genug für alle denkbaren Anforderungen [1|#literatur].
Das Problem jeder praktikablen Chiffriermethode ist jedoch, dass ihre Sicherheit (bis jetzt) nicht beweisbar ist. Man kann nur testen, ob die bisher bekannten Angriffsmethoden der Kryptanalyse versagen. Es gab zwar Warnungen wegen der besonders einfachen Struktur von AES, doch rational begründete Bedenken konnte niemand vorbringen: AES schien resistent gegenüber allen bekannten Angriffen.
Im Mai 2001 gelang es Ferguson, Schroeppel und Whiting, den Algorithmus als geschlossene Formel darzustellen - allerdings mit 250 Termen, also etwa eine Billiarde Summanden [2|#literatur]. Niemand weiß, ob daraus jemals ein sinnvoller Angriff auf AES konstruiert werden kann, doch bisher ließ sich kein anderes sicheres Verfahren in solch einer ‘einfachen’ Form darstellen. Die Meinungen in der Fachwelt waren geteilt. Im Folgejahr stellte der bekannte Kryptanalytiker Biham weitere besondere algebraische Eigenschaften von Rijndael vor und bestärkte die Zweifler.
Ein Qualitätssprung war jedoch eine Arbeit von Courtois und Pieprzyk [3|#literatur]. Die Mathematiker beschrieben ganze Klassen von Chiffrierungen mittels sehr großer Systeme quadratischer Gleichungen, zum Beispiel 128-Bit-AES als System von 8000 Gleichungen mit 1600 Variablen. Derartige Systeme lassen sich im Allgemeinen nicht mit vertretbarem Rechenaufwand lösen, doch in diesem Fall sind starke Vereinfachungen mittels der so genannten XSL-Methode möglich. Sie nutzt aus, dass die Gleichungssysteme mehr Gleichungen als Unbekannte enthalten (sie sind überbestimmt), die meisten Koeffizienten Null sind (schwach besetzt) und dass sie eine besonders reguläre Struktur haben.
Die betroffenen Algorithmen verarbeiten den Klartext blockweise (man spricht daher von Blockchiffrierungen), die Chiffrierung jedes Blockes geschieht in weitgehend identischen, nacheinander ausgeführten Runden, die aus jeweils drei mathematischen Operationen bestehen.
Dieses einfache Design findet man bei zahlreichen modernen Verschlüsselungsverfahren, unter anderem bei AES selbst und beim AES-Endkandidaten Serpent. Es garantierte bei geeigneter Wahl der Operationen sogar beweisbare Immunität gegenüber bekannten kryptanalytischen Verfahren bei gleichzeitig hoher Performance. Der XSL-Angriff stellt diese Welt auf den Kopf. Gerade der als besonders sicher eingeschätzte Algorithmus Serpent wird mit der neuen Methode leichter angreifbar als AES, und dank der Weiterentwicklung der XSL-Methode erscheint mittlerweile ein Angriff auf AES mit ‘lediglich’ 2100 Rechenoperationen denkbar.
Was heißt ‘unsicher’?
Manche Experten sprechen deshalb bereits von einem Durchbruch. Tatsächlich stellen diese Ergebnisse einen Qualitätssprung in der Kryptanalyse dar. Die bisherigen Methoden wie differenzielle und lineare Kryptanalyse beruhten darauf, dass sich aus Geheim- und/oder Klartext konstruierte Ausdrücke nicht ganz zufällig verhielten. Aus winzigen Abweichungen vom ‘reinen Zufall’ ließen sich Schlüssel rekonstruieren, allerdings nur mittels enormer Mengen von Geheim- und meist auch Klartext. Diese ‘klassischen’ Angriffe werden obendrein mit wachsender Rundenzahl sehr schnell uneffektiv.
Der XSL-Angriff hingegen könnte - wenn er denn durchführbar ist - die Rekonstruktion des Schlüssels aus kleinen Mengen Geheimtext ermöglichen, denn anders als die bisher üblichen statistischen Methoden ‘berechnet’ er den Schlüssel direkt. Das ist der Wunschtraum aller Kryptanalytiker! Es überrascht auch, dass die Sicherheit eines Blockalgorithmus gegen diesen Angriff offenbar nicht mehr exponentiell mit der Rundenzahl steigt. Noch überraschender ist, dass Serpent plötzlich unsicherer erscheint als Rijndael. Man war bis vor kurzem vom Gegenteil überzeugt.
Und dennoch ist AES deswegen (noch) nicht unsicher. Zum einen beruhen viele Abschätzungen des Arbeitsaufwands noch auf Vermutungen. Zum anderen sind 2100 Rechenschritte eine utopisch große Zahl. Ein aus GHz-Pentium-Prozessoren aufgebauter Rechen-Cluster, der diese Arbeit binnen eines Jahres schaffen sollte, hätte einen Stromverbrauch von vielen Millionen Gigawatt, was viele Größenordnungen über der Weltenergieproduktion liegt. Die genannten Angriffe sind also rein akademischer Natur. Doch für Kryptologen ist eben alles, was schneller geht als das Durchprobieren aller möglichen Schlüssel, bereits ein Erfolg - selbst wenn es auf absehbare Zeit in der Praxis nicht realisiert werden kann.
Ob auf der Basis von XSL eines Tages ein praktikabler Angriff konstruiert werden kann (vielleicht auch mit Hilfe der noch hypothetischen Quantencomputer), vermag derzeit niemand zu sagen. Es zeigt sich aber, dass es immer noch keinen auf lange Zeit garantiert sicheren Chiffrieralgorithmus gibt. Die weitere Entwicklung bleibt spannend - und AES darf man vorerst mit gutem Gewissen weiter benutzen. (ju)
Literatur
[1] Reinhard Wobst, Von DES zu AES, Neuer Verschlüsselungsstandard vor der Verabschiedung, iX 10/01, S. 92
[2] Ferguson, Schroeppel und Whiting: www.xs4all.nl/~vorpal/pubs/rdalgeq.html
[3] Courtois und Pieprzyk: eprint.iacr.org/2002/044/ (ju)
