Alexander Benesch

Der vermeintliche NSA-Whistleblower Edward Snowden lässt die nächste Bombe platzen: Der Geheimdienst gibt Milliarden Dollars aus und mischt sich in die Belange von Privatfirmen ein um allerhand Verschlüsselungen im Netz zu brechen oder zu umgehen. Auch spricht sich nach neuen wissenschaftlichen Studien endlich herum, dass der von der US-Regierung finanzierte Anonymisierungsdienst TOR ein schlechter Witz ist.

Computernutzer weltweit klammern sich an ihre letzte Hoffnung: Den Advanced Encryption Standard. Selbst der dubiose, zu den Russen übergelaufene Snowden hofft noch darauf, dass wenigstens die Verschlüsselungsalgorithmen noch taugen. Genauer gesagt geht es um fünf verschiedene Algorithmen, von denen einer durch die US-Regierung im Jahr 2000 zum offiziellen Standard für Material bis hin zu Top Secret erkoren wurde. Ein Wettbewerb war ausgeschrieben worden und fünf Finalisten (Algorithmen) kamen ins Finale, Rijndael machte das Rennen. Nichtsdestotrotz werden auch die anderen Algorithmen heute noch fleißig weltweit benutzt.

Was ist aber die Geschichte dieser fünf Algorithmen? Wer hat sie entwickelt und für sicher befunden?

Keine Zeit, keine Zeit

Das Projekt New European Schemes for Signature, Integrity and Encryption (NESSIE) hatte seinerzeit interessante Untersuchungen angestellt. Finanziert wird man von der Europäischen Union, die Partner sind die Katholieke Universiteit Leuven (Belgien), Ecole Normale Superieure (Frankreich), Fondazione Ugo Bordoni (Italien), Royal Holloway (UK), Siemens AG (Deutschland), Technion (Israel), Universie Catholique de Louvain (Belgien) und Universitetet i Bergen (Norwegen).

http://www.cryptonessie.org
http://csrc.nist.gov/archive/aes/round2/comments/20000524-bpreneel.pdf

“Wir glauben, dass der Aufwand für die Untersuchung der Sicherheit der fünf AES-Finalisten sehr begrenzt war, insbesondere im Vergleich zu den 17 Jahren, die IBM in den späten 1970er Jahren auf DES verwendet hatte. Es ist auffällig, dass die Mehrheit der wissenschaftlichen Papiere bei AES3 sich um die Bewertung der Performance drehten und nicht um die Bewertung der Sicherheit. Dafür gibt es mehrere Gründe:

  • Der Zeitmangel
  • Manche der Finalisten sind recht komplex, was es schwierig und zeitaufwändig macht, sie zu untersuchen”

Anscheinend wollte die Behörde National Institute of Standards and Technology (NIST), dass niemand so genau hinsieht. Das, obwohl die Sicherheit eines Algorithmus wesentlich wichtiger ist, als die Frage ob er mehr Ressourcen frisst als ein anderer. Die Prognose von NESSIE über die Finalisten klingt wenig optimistisch:

“Nichtsdestotrotz glauben wir dass ein praktischer Angriff (z.B. die Verwendung von 2 hoch 32 bekannten Klartexte mit 270 benötigten Verschlüsselungen) nicht innerhalb eines kurzen Zeitraumes (weniger als fünf Jahre) für irgendeinen der fünf Finalisten gefunden werden wird.”

Fünf Jahre waren bereits 2005 vorbei.

“Es ist jedoch wahrscheinlich, dass certicational attacks gegen manche der Finalisten gefunden werden, deren Komplexität unterhalb liegt von der Größe des Key Space. Es ist sicherlich so, dass mehr Kryptoanalyse sehr nützlich gewesen wäre um unser Vertrauen in die langfristige Sicherheit dieser Algorithmen zu erhöhen. Darüberhinaus hätte dies in einer bedeutsamen Vergleichsmöglichkeit resultiert von einer Sicherheitsperspektive.”
“Wir sind uns bewusst dass es nicht einfach ist, den ‘Sicherheitsspielraum’ eines kryptographischen Algorithmus zu definieren. Wir wissen dass NIST um Input dahingehend gebeten hat, aber es scheint dass bisher kein Konsens existiert, über die relativen und absoluten Sicherheitsspielräume.”

Von (NIST) wurde der Algoritmus MARS zusammen mit den Kandidaten Serpent und Twofish als hoch-sicher eingestuft, während der Gewinner Rijndael „nur“ als hinreichend-sicher eingestuft wurde. MARS wurde besonders wegen seiner Komplexität, die eine Sicherheitsanalyse erschwert, kritisiert. Je komplexer und verworrener ein Algorithmus, desto besser lassen sich Schwachstellen verbergen, die als Hintertür fungieren können. Statt Trillionen Jahre theoretische Rechenzeit, um den Klartext herauszubekommen, sind es per Hintertür je nachdem vielleicht nur Wochen, Tage, Stunden oder Minuten.

30 Seconds to MARS

Der Algorithmus MARS ist das Werk der Cryptography Research Group beim IBM T.J.Watson Research Center. IBM fertigte lange Supercomputer wie den IBM 7950 Harvest im Jahr 1962 (!) für die Codebrecher der NSA. Wie ironisch, dass IBM gleichzeitig Verschlüsselungsalgorithmen entwickelt, ohne auf den Moral Hazard hinzuweisen, zugunsten der NSA Hintertüren einzubauen.

Foto: Der IBM Harvest

Das MARS-Team bestand 1999 aus Carolynn Burwick, Don Coppersmith, Edward D’Avignon, Rosario Gennaro, Shai Halevi, Charanjit Jutla, Stephen M. Matyas Jr., Luke O’Connor und Mohammad Peyravian. IBMs offizieller Bericht verlautbarte, dass MARS und ein anderer Kandidat namens Serpent  die einzigen Finalisten gewesen wären, die überhaupt resistent waren gegen kommende Fortschritte des mathematischen Codebrechens.

Don Coppersmith aus dem IBM-Team durchlief die Eliteuniversitäten MIT und Harvard, promovierte bei Schlomo Sternberg. Später war er am Center for Communication Research (CCR) des Institute for Defense Analyses in Princeton. Ihr Hauptsitz ist in Alexandria (Virginia). Dort ist auch ihr größtes Forschungszentrum, das IDA Studies and Analyses Center (SAC). Das IDA Center for Communications and Computing arbeitet mit der National Security Agency (NSA) zusammen – es arbeitet also vor allem in Kryptographie. Das IDA hat seine Ursprünge in der 1947 von Verteidigungsminister James Forrestal ins Leben gerufenen Weapons System Evaluation Group (WSEG). Die NESSIE-Wissenschaftler hatten ihre Bedenken gegenüber MARS:

“Das MARS-Design verwendet viele verschiedene Komponenten. Laut den MARs-Designern seien alle verwendeten Komponenten einfach zu Analysieren (C. Burwick et al, MARS – a candidate cipher for AES). Wir sind anderer Meinung.”

“Es gibt auch manche Beziehungen zwischen den unterschiedlichen Outputs der E-Funktion (siehe Robshaw). Darüberhinaus erfüllen die S-boxes von MARS nicht all die Design-Anforderungen die das Team anvisiert hatte (siehe Burnett et al). Während diese Beobachtungen nicht zu einem Angriff gegen MARS fühen, so zeigen sie doch dass es noch keine klare Erkenntnis gibt über die Sicherheit der Struktur von MARS. Es wird erwartet dass weitere ähnliche Fehler in der Anayse von MARS des Design-Teams entdeckt werden.”

“Wir erkennen dass alle Komponenten von Mars nicht zu der erwarteten Stärke der Verschlüsselung führen und es gibt Fragen, ob die Kombination der Einzelteile gegen all die Schwächen der einzelnen Komponenten schützt.”

Eine weitere Studie erklärt neue Angriffsmethoden gegen MARS:

“Auch wenn keine dieser Attacken in der Lage ist, die gesamte Verschlüsselung zu brechen, denken wir dass diese Ergebnisse wertvolle Einblicke liefern in die Sicherheit von MARS.

Wir betrachten diese Ergebnisse als vorläufig und wären nicht überrascht, mittelgradige Verbesserungen bei unseren Angriffen zu sehen. Wenn allerdings große Verbesserungen möglich sind, erwarten wir dass dafür neue Techniken nötig sind.”

http://www.schneier.com/paper-mars-attacks.pdf

TWOFISH

Der Kandidat “Twofish” stammt von der Sicherheitsberaterfirma Counterpane, mitbegründet durch den Kryptografieexperten Bruce Schneier der während dem Studium begonnen hatte, für das US-Verteidigungsministerium zu arbeiten und später bei dem mit der NSA verbandelten Konzern Bell Labs unterkam. Counterpane wurde umbenannt in BT Managed Security Solutions und ausgerechnet an den britischen Telekommunikationsgiganten BT Group verkauft. NESSIE zitiert aus zwei Studien über TWOFISH und findet allerlei Widersprüche und unkonventionelle Auffälligkeiten. Man spart nicht mit harscher Kritik an den Schwächen:

“Eine vorläufige Analyse mit Verwendung dieser Technik lässt auf die Existenz eines 8-Runden-Angriffs auf TwoFish schließen. Darüberhinaus wird behauptet, die wichtigen schlüssel-Abhängigen S-Boxes von Two Fish würden die Sicherheit der Verschlüsselung erhöhen. Die Literatur enthält aber mehrere Beispiele wo das Ersetzen von fixed S-Boxes mit schlüssel-abhängigen S-Boxes die Stärke der Block-Verschlüsselung reduziert.”

Bruce Schneier versichert immer wieder, wie im Magazin “Wired”, dass solche Algorithmen immer noch vor der NSA sicher seien und man ihm völlig vertrauen könne.

Serpent

Serpent wurde gemeinsam von der Cambridge University, der Universität von Haifa in Israel und der Universität von Bergen in Norwegen entwickelt. Cambridge ist fest in der Hand des Britischen Geheimdienstes MI6, der dort u.a. neue Mitglieder rekrutiert. Der ehemalige MI6-Ched Sir Richard Dearlove ging nach seinem Rücktritt nach Cambridge und wurde dort der Boss eines University Colleges.

http://www.cambridge-news.co.uk/Education/Universities/Ex-boss-of-MI6-Sir-Richard-Dearlove-has-his-own-Iraq-dossier-20130721171515.htm

Die Universität von Haifa ist Mossad-Territorium. Die Entwickler von Serpent, Ross Anderson, Eli Biham und Lars Knudsen versprachen, dass ihr Algorithmus mindestens hundert Jahre lang sicher sein werde. Anderson machte seinen Doktor bei dem Royal Society-Mitglied Roger Needham. Wissenschaftler äußerten für NIST ihre Zweifel an Serpent:

“Die Sicherheit ist nur heuristisch. Die Autoren liefern ein heuristisches Argument für eine Version von Serpent die auf 8 Runden reduziert wurde und wählten ungewöhnlich große 32 Runden um Vertrauen in die Sicherheit zu gewinnen. Ein weiterer Anlass zu Besorgnis ist die unklare Herkunft der substitution boxes. Dies könnte die Kontroverse um versteckte Hintertüren aufflammen lassen.”

http://csrc.nist.gov/archive/aes/round1/conf2/papers/baudron1.pdf

Der Gewinner: Rijndael

Der Advanced Encryption Standard (AES), Variante Rijndael, ist nicht nur vorgeschrieben für geheime staatliche Kommunikationen der US-Regierung, sondern wurde auch der weltweite Standard für kommerzielle Verschlüsselungs-Software und -Hardware. Am 2. Oktober 2000 kürte NIST den Gewinner Rijndael, geschaffen von Joan Daemen und Vincent Rijmen von der katholischen Universität Leuven in Belgien (die u.a. EU-Präsident van Rompuy hervorbrachte).

Rijndael ist entworfen um sehr sicher zu sein gegenüber altbackenen approximation attacks, wie linear cryptanalysis, differential cryptanalysis usw. Da Rijndael aber sehr algebraisch ist, tauchten neue algebraische Angriffsmethoden auf. Die Schwäche von Rijndael sind effektive Angriffs-Algorithmen.

Nicolas Courtois und Josef Pieprzyk untersuchten, wie man XL-Techniken verbessern könnte und schufen eine neue Art von Angriff namens XSL, die zumindest eine sehr spannender Ansatz ist. Courtois und Pieprzyk demonstrierten einen Angriff gegen AES 256, konnten aber noch nicht vollständig den Algorithmus brechen. Zuerst war die NSA zurückhaltend in ihrer Bewertung von Rijndael, im Juni 2003 wurde er plötzlich überraschend für sämtliche US-Behörden empfohlen.
Schneier und Ferguson schrieben in ihrem Buch “Practical Cryptography” über AES:

“Wir trauen der Sicherheit nicht so recht. Kein ander block cipher den wir kennen hat eine dermaßen simple algebraische Repräsentation. Wir wissen nicht ob dies zu einem Angriff führt, aber dass man es nicht ausschließen kann, ist Anlass genug um skeptisch zu sein gegenüber der Verwendung von AES.”

AES scheint übermäßig abgesichert worden zu sein im Hinblick auf differentielle oder lineare Kryptoanalyse, jedoch von der Perspektive algebraischer Angriffe aus, handelt es sich um eine extrem schlechte Verschlüsselung.