Wettrennen der Codeknacker

Schon seit Jahrtausenden entwickeln Menschen Verschlüsselungsverfahren, während andere versuchen, sie zu knacken. Doch erst seit einigen Jahrzehnten gibt es Krypto-Wettbewerbe, in denen derartige Duelle nach festgelegten Regeln ablaufen

Es gibt zwei Arten von Krypto-Wettbewerben. In der einen Variante (Kryptoanalyse-Wettbewerb) geht es darum, Verschlüsselungen zu knacken. Bei der anderen besteht das Ziel darin, das beste kryptografische Verfahren für einen bestimmten Zweck zu finden. Letztere Spielart wird als Algorithmen-Wettbewerb bezeichnet. Beide Wettbewerbsformen haben in der jüngeren Geschichte der Verschlüsselungstechnik eine wichtige Rolle gespielt, wenn auch auf völlig unterschiedliche Weise.

Als treibende Kraft auf dem Gebiet der Kryptoanalyse-Wettbewerbe etablierte sich Anfang der neunziger Jahre die US-Firma RSA Data Security (inzwischen in EMC aufgegangen). Das Unternehmen, das von den drei Erfindern des bekannten RSA-Verschlüsselungsverfahrens gegründet wurde, startete mehrere Wettbewerbe, in denen es für eine erfolgreiche Dechiffrierung Geldpreise zu gewinnen gab. Diese Wettbewerbe werden RSA-Challenges genannt (benannt nach der Firma, nicht nach dem Verfahren). Bis heute sind noch längst nicht alle Dechiffrier-Aufgaben der RSA-Challenges gelöst. Den jeweils aktuellen Stand können Sie im Internet nachlesen.

Die RSA-Challenges

Als erste RSA-Challenge rief RSA Data Security 1991 einen Wettbewerb ins Leben, in dem es um das Zerlegen von Primzahlprodukten in ihre beiden Faktoren ging. Gelingt eine solche Faktorisierung, dann kommt dies dem Knacken eines RSA-Schlüssels gleich. Die erste Zahl, die der Veranstalter im März 1991 vorgab, hatte 100 Stellen (330 Bits) und wurde daher als RSA-100 bezeichnet.

Schon im April 1991 gelang es dem bekannten Kryptografen Arjen Lenstra, RSA-100 zu faktorisieren. Damit war nebenbei auch klar, dass eine RSA-Schlüssellänge von 330 Bit nicht mehr als sicher gelten konnte. In den Folgejahren fielen auch RSA-110, RSA-120 und einige weitere Zahlen des Wettbewerbs. Für den bisherigen Höhepunkt sorgte im Mai 2005 ein deutsches Team unter der Leitung des Bonner Mathematikers Jens Franke, als es die Faktorisierung von RSA-200 bekannt gab. Mit 663 Bit ist RSA-200 bis heute die längste Zahl, die öffentlich faktorisiert wurde.

2001 präsentierte der Veranstalter acht weitere Zahlen, die es zu faktorisieren galt. Dieses Mal wurden die Zahlen nicht nach ihrer Länge im Dezimalsystem, sondern nach ihrer Bitlänge benannt: RSA-576, RSA-640, RSA-704, RSA-768, RSA-896, RSA-1024, RSA-1536 und RSA-2048. Erstmals gab es nun attraktive Geldpreise zu gewinnen. Für das Zerlegen von RSA-2048 (also einer 2.048-Bit-Zahl) lobte der Veranstalter immerhin 200.000 Dollar aus.

Die Forschergruppe um Jens Franke blieb auch bei den neuen Zahlen am Ball und knackte im November 2005 RSA-640, wofür sie 20.000 Dollar als Preisgeld erhielt. Dies war allerdings nur die zweitlängste bis dahin faktorisierte Zahl, da die bereits erwähnte RSA-200 mit 663 Bit noch ein Stück länger ist. Man darf gespannt sein, wie sich der nach wie vor andauernde Wettbewerb in den nächsten Jahren entwickelt.

Falls Sie selbst aktiv werden wollen, können Sie sich an RSA-704 versuchen, für deren Faktorisierung 30.000 Dollar ausgesetzt sind. Bei Redaktionsschluss dieses Artikels hatte noch niemand den Preis für sich beansprucht. Hier ist die Zahl (bevor Sie loslegen, bitte die Korrektheit auf der Internetseite des Wettbewerbs überprüfen):

DES und RC5 im Wettbewerbstest

1997 setzten die Organisatoren der RSA-Challenges einen Geldpreis für das Dechiffrieren einer Nachricht aus, die mit dem damals äußerst populären Verschlüsselungsverfahren DES verschlüsselt war. 10.000 US-Dollar sollte erhalten, wer den korrekten Schlüssel fand. Da der Originaltext bekannt war, lief dies auf ein Durchprobieren aller möglichen Schlüssel hinaus, bis per Zufall der richtige gefunden war. Da der DES etwa 72.050.000.000.000.000 verschiedene Schlüssel zulässt, bedeutete dies ein äußerst aufwendiges Unterfangen.

Dennoch dauerte es nur vier Monate, bis ein von dem Programmierer Rocke Verser organisierter Zusammenschluss von 14.000 Rechnern den Schlüssel fand und damit den Wettbewerb gewann. Die Öffentlichkeit nahm mit Erstaunen zur Kenntnis, dass das wichtigste aller Verschlüsselungsverfahren erstmals geknackt worden war – wenn auch nur mit bekanntem Klartext. Kein anderer Kryptoanalyse-Wettbewerb hat bis heute ein so großes Medienecho gefunden.

Der große Erfolg des ersten DES-Wettbewerbs veranlasste den Veranstalter der RSA-Challenges zu mehreren Neuauflagen. In der zweiten Runde gab es zwei DES-Geheimtexte zu knacken (DES II-1 Challenge und DES II-2 Challenge), was in 39 Tagen bzw. 56 Stunden auch gelang. Im ersteren Fall war die distributed.net-Gruppe, die sich auf das verteilte Berechnen rechenzeitintensiver Aufgabenstellungen spezialisiert hat, am schnellsten. Die DES II-2 Challenge wurde von einem Spezialrechner der Internet-Bürgerrechtsbewegung Electronic Frontier Foundation (EFF) gelöst.

Im Januar 1999 startete die dritte DES-Wettbewerbsrunde (DES III Challenge). Dieses Mal arbeiteten die distributed.net-Gruppe und die EFF zusammen, und in weniger als 23 Stunden war der Schlüssel gefunden. Dieser Erfolg markierte den Höhe- und Wendepunkt in der Geschichte der Kryptoanalyse-Wettbewerbe. Das öffentliche Interesse ließ auf Grund der ständig neuen Rekordmeldungen nun deutlich nach. Der Ausrichter verzichtete auf neue Wettbewerbe, und so wurde der Rekord im DES-Knacken bis heute nicht mehr verbessert.

Neben dem DES unterzog RSA Data Security auch das im eigenen Haus entwickelte Verschlüsselungsverfahren RC5 einem Wettbewerb innerhalb der RSA-Challenges. Da RC5 eine variable Schlüssellänge vorsieht, bot es sich an, mehrere unterschiedliche Varianten des Verfahrens knacken zu lassen. Der Aufruf zum Knacken von RC5 diente unter anderem der Demonstration, dass das Verfahren bei ausreichender Schlüssellänge sicher ist.

Im Januar 1997 startete der RC5-Wettbewerb. Die Teilnehmer konnten sich an 12 Geheimtexten versuchen, die mit den Schlüssellängen 40 Bit, 48 Bit, 56 Bit, 64 Bit, 72 Bit, 80 Bit, 88 Bit, 96 Bit, 104 Bit, 112 Bit, 120 Bit und 128 Bit verschlüsselt worden waren. Da ein Teil des jeweils zugehörigen Klartexts bekannt gemacht wurde, war auch hier ein aufwendiges Schlüsseldurchprobieren gefragt. Der 40-Bit-Geheimtext des RC5-Wettbewerbs war bereits nach gut drei Stunden geknackt. Die 48-Bit-Variante fiel nach 13 Tagen. Nach 265 Tagen fand die distributed.net-Gruppe auch den 56-Bit-Schlüssel.

Danach wurde es erst einmal still um den RC5-Wettbewerb. Im Juli 2002 gelang es schließlich erneut distributed.net, nach fünfjähriger Rechenzeit den 64-Bit-Schlüssel zu ermitteln. Dieser Erfolg bildet bis heute den Weltrekord in Sachen Schlüsselsuchdurchprobieren. Es gibt keinen anderen öffentlich bekannten Fall, in dem ein Schlüssel der Länge 64 Bit oder mehr auf diese Weise geknackt wurde. Die acht verbleibenden Schlüssel aus dem nach wie vor laufenden Wettbewerb sind bis heute ungeknackt.

Mystery Twister

Im Januar 2005 startete an der Ruhr-Universität Bochum ein Kryptoanalyse-Wettbewerb namens Mystery Twister. Ziel dieses Projekts war es einerseits, einen Nachfolger für die nur noch auf Sparflamme laufenden RSA-Challenges ins Leben zu rufen. Andererseits wollten die Organisatoren auch Hobby-Kryptologen ansprechen. Diesen Vorgaben entsprechend sah die erste Wettbewerbsrunde kryptografische Aufgaben in drei Schwierigkeitsstufen vor – für Laien, Fortgeschrittene und Experten. Mystery Twister wurde komplett über das Internet abgewickelt, wobei die optisch sehr ansprechende Webseite ihren Teil dazu beitrug, dass in der ersten Runde über 10.000 Teilnehmer ihr Glück versuchten.

Im Februar 2006 begann die zweite Runde von Mystery Twister. Es gab 13 neue Aufgaben, die erneut in drei Schwierigkeitsstufen zu lösen waren. Die höheren Schwierigkeitsgrade hatten alle mit modernen kryptografischen Verfahren wie DES oder RSA zu tun. Am schwierigsten war zweifellos die 13. Aufgabe, in der es um eine RSA-Signatur ging. Die Veranstalter gingen (wie sich zeigte, zu Recht) davon aus, dass dieses Rätsel von niemandem gelöst werden würde.

Leider ist Mystery Twister inzwischen nicht mehr aktiv. Grund dafür sind eine mangelnde Sponsorenunterstützung und der zwischenzeitliche Tod des Kryptologen Hans Dobbertin. Dobbertin, der als bedeutendster deutscher Verschlüsselungsexperte galt, war einer der Väter von Mystery Twister. Es bleibt zu hoffen, dass dieses spannende Projekt bald wieder auflebt.

Einen weiteren vielbeachteten Kryptoanalyse-Wettbewerb rief 1999 der britische Journalist Simon Singh ins Leben. In einem von ihm verfassten Buch präsentierte er zehn kryptografische Rätsel mit steigendem Schwierigkeitsgrad1. Für die Lösung aller zehn Aufgaben gab es einen Preis von 10.000 britischen Pfund zu gewinnen. Jedes der von Singh gestellten Rätsel gab einen Geheimtext vor, den es zu entschlüsseln galt. Dabei kamen unterschiedliche Verfahren zur Anwendung, die zusammen einen Streifzug durch die Geschichte der Verschlüsselungstechnik ergaben. In den Aufgaben 1 bis 8 ging es um klassische Handverfahren, danach war die moderne Computer-Verschlüsselung an der Reihe. Teilweise gab das Ergebnis einer Entschlüsselung Hinweise zur Lösung einer nachfolgenden Aufgabe.

Nach dem Start des Wettbewerbs dauerte es ein gutes Jahr, bis im Oktober 2000 eine Gruppe schwedischer Computerexperten Vollzug melden konnte. Tatsächlich hatten sie alle zehn Aufgaben richtig gelöst und konnten die 10.000 Pfund unter sich aufteilen (was bei einem fünfköpfigen Team allerdings nicht zu großem Reichtum führte).

Der Doppelwürfel Ein noch recht neuer Kryptoanalyse-Wettbewerb wurde vom Autor dieses Artikels gestartet (leider gibt es keinen Geldpreis zu gewinnen). Die gestellte Aufgabe folgt einer Anregung von Otto Leiberich, dem ehemaligen Präsidenten des Bundesamts für Sicherheit in der Informationstechnik (BSI). Leiberich berichtete 1999 in einem Zeitschriftenartikel über den so genannten Doppelwürfel2. Dabei handelt es sich um ein Verschlüsselungsverfahren, das ohne Computerunterstützung von Hand ausgeführt werden kann und trotzdem als recht sicher gilt. Es wird auch als doppelte Spaltentransposition bezeichnet. Der Doppelwürfel wurde (und wird vermutlich noch heute) häufig von Spionen eingesetzt, die sich nicht mit einem Verschlüsselungsgerät oder einem entsprechenden Computer-Programm verdächtig machen wollen.

Der Doppelwürfel sieht die zweifache Ausführung eines Verfahrens vor, das Würfel genannt wird. Um dieses auszuführen, wählt man ein Schlüsselwort (z. B. TELEPOLIS) und schreibt dieses wie folgt unter den zu verschlüsselnden Text (z. B. ERWARTE MORGEN NEUE LIEFERUNG):

Anschließend werden die Spalten so umgeordnet, dass die Buchstaben des Schlüsselworts in alphabetischer Reihenfolge stehen:

Der verschlüsselte Text heißt nun RGEAN EMEGW EFEUN TEURN ROLERI. Für die zweite Runde der Doppelwürfel-Verschlüsselung benötigt man ein zweites Schlüsselwort, mit dem der Vorgang wiederholt wird.

Trotz der weiten Verbreitung sind nur wenige wissenschaftliche Untersuchungen des Doppelwürfels bekannt. Die bedeutendste ist eine 1995 freigegebene Publikation des US-Geheimdiensts NSA, die darauf hindeutet, dass amerikanische Kryptologen das Verfahren schon länger knacken können3. Leider enthält diese Schrift nicht alle Details. Auf Grund der unklaren Lage lässt sich die Sicherheit des Verfahrens schlecht einschätzen. Daher regte Otto Leiberich in seinem Artikel ein kryptografisches Rätsel an, bei dem es um die Entschlüsselung eines Doppelwürfel-Geheimtexts geht. Diesem Wunsch kam der Autor dieses Artikels nach. Er verschlüsselte einen englischen Text mit zwei längeren englischen Schlüsselwörtern unterschiedlicher Länge und veröffentlichte das Resultat in seinem Buch „Codeknacker gegen Codemacher“4. Dieser verschlüsselte Text wird außerdem in der nächsten Version 1.4.20 der kostenlosen Krypto-Lernsoftware CrypTool mit ausgeliefert werden. Er lautet wie folgt:

Algorithmen-Wettbewerbe

Algorithmen-Wettbewerbe verfolgen ein anderes Ziel und laufen anders ab als Kryptoanalyse-Wettbewerbe. Die Veranstalter sind meist Behörden oder Forschungsgruppen, die für einen bestimmten Zweck das am besten passende Verfahren suchen. Während bei einem Kryptoanalyse-Wettbewerb das Knacken der jeweiligen Verschlüsselung das einzige Kriterium für den Erfolg ist, muss der Sieger eines Algorithmen-Wettbewerbs in mehreren Sparten gleichzeitig überzeugen. Neben der Sicherheit sind meist Performanz, Speicherplatzbedarf und Patentfreiheit die wichtigsten Kriterien.

Die Mutter aller Algorithmen-Wettbewerbe begann um das Jahr 1970. Zu diesem Zeitpunkt entwickelte sich der Computer von einem teuren Spezialgerät immer mehr zu einem Werkzeug, das von Industrie und Behörden für alltägliche Zwecke genutzt wurde. Die Notwendigkeit für eine zuverlässige Verschlüsselung war angesichts dieser Entwicklung offensichtlich. Doch obwohl es im Militär- und Geheimdienstbereich bereits damals ein umfangreiches Krypto-Know-how gab, war das öffentlich verfügbare Wissen zu diesem Thema gleich Null. Niemand wusste also so recht, wie eine computergestützte Verschlüsselung aussehen sollte.

Um diesen Mangel zu beheben, hob die US-Standardisierungsbehörde NBS (heute NIST) 1973 den ersten Krypto-Wettbewerb der Computerära aus der Taufe. Die Behörde rief dazu auf, Vorschläge für ein computertaugliches Verschlüsselungsverfahren einzureichen. Das Beste davon sollte zu einem gesetzlich verankerten Standard erklärt werden. Der Aufruf des NBS verfehlte seine Wirkung nicht, und so gingen in der Folgezeit Algorithmen-Vorschläge in großer Zahl ein. Eine Sichtung der Einreichungen verlief jedoch enttäuschend – kein einziges Verfahren erschien den Standardisierern praxistauglich. Die erste Runde des ersten Wettbewerbs endete daher mit einem Abbruch.

1974 versuchte es das NBS mit einem erneuten Aufruf. Dieses Mal gab es einen aussichtsreichen Kandidaten, denn IBM, die damals führende Computerfirma, hatte ein Verfahren namens Lucifer eingereicht. Lucifer war das Ergebnis eines IBM-Forschungsprojekts, in dessen Verlauf mehrere erfahrene Computerexperten ein sicheres und praxistaugliches Verschlüsselungsverfahren entwickelt hatten. Der Rest ist Kryptografie-Geschichte. Als einziger ernst zu nehmender Kandidat gewann Lucifer den ersten Algorithmen-Wettbewerb der Computerära. Die US-Geheimbehörde NSA nahm noch einige Änderungen vor, bevor das Ergebnis schließlich in Form des bereits erwähnten Data Encryption Standard (DES) standardisiert wurde. In den Folgejahren entwickelte sich der DES zum populärsten Verschlüsselungsverfahren überhaupt.

Der AES-Wettbewerb

Angesichts der hohen Qualität des DES konnte sich das NBS (das zwischenzeitlich in NIST umbenannt wurde) mit einem weiteren Wettbewerb fast 25 Jahre Zeit lassen. Erst 1997 gab es ernsthafte Bestrebungen, einen neuen Verschlüsselungsstandard zu finden. Dieser sollte AES (Advanced Encryption Standard) genannt und im Rahmen eines Mitte 1998 gestarteten Algorithmen-Wettbewerbs gefunden werden. Wer teilnehmen wollte, musste eine vollständig dokumentierte Verschlüsselungsmethode mit Referenzimplementierung einreichen, die für Hard- und Software gleichermaßen geeignet und frei von Patentrechten war.

In der Vorrunde des AES-Wettbewerbs überprüfte das NIST lediglich formale Kriterien. Am 20. August 1998 veröffentlichte der Veranstalter eine Liste von 15 Verfahren, die diese erfüllten und damit für den eigentlichen Wettbewerb zugelassen wurden. Diese 15 Verfahren wurden fortan als AES-Kandidaten bezeichnet. Für die Kryptografen dieser Welt tat sich damit ein interessantes Betätigungsfeld auf, denn alle AES-Kandidaten stellten in irgendeiner Form etwas Neues dar.

Bis Mitte 1999 wählte das NIST auf Basis von Expertenmeinungen die fünf besten Algorithmen aus den AES-Kandidaten aus. Diese kamen in die zweite Runde und damit in die Endauswahl. Es handelte sich dabei um die Verfahren Twofish, MARS, Serpent, RC6 und Rijndael. Die restlichen zehn Verfahren mussten sich aus dem Wettbewerb verabschieden. Die fünf AES-Finalisten wurden von der Fachwelt besonders genau unter die Lupe genommen. Leichte Performanzdefizite unter bestimmten Bedingungen und einige theoretische Überlegungen sorgten dafür, dass MARS und RC6 Anfang 2000 ihre Siegchancen einbüßten. Über die drei verbleibenden Verfahren wurde heftig diskutiert, bevor das NIST am 2. Oktober 2000 schließlich den Gewinner bekannt gab: Rijndael hatte das Rennen gemacht.

Dass sich Rijndael gegenüber Twofish durchsetzte, lag daran, dass Letzterer etwas langsamer und komplexer ist. Serpent hatte in Software-Implementierungen die etwas geringere Performanz gezeigt. So gesehen ist Rijndael sicherlich ein würdiger Sieger, auch wenn sich einige Kryptografen auf Grund einer höheren Anzahl von Verschlüsselungsrunden für Twofish oder Serpent ausgesprochen hatten.

Die gesamte Fachwelt war sich darüber einig, dass das NIST während des gesamten AES-Auswahlprozesses erstklassige Arbeit geleistet hatte. In der Tat waren die Entscheidungen des NIST allesamt nachvollziehbar, und das gesamte Projekt lief in einer wohltuenden Offenheit ab. Auch die Idee, den AES in Form eines Wettbewerbs festlegen zu lassen (und nicht etwa durch ein Gremium), wurde immer wieder gelobt. Da zudem die vom DES bekannte Geheimniskrämerei bei der AES-Festlegung ausblieb, gab es am Ende geradezu euphorische Reaktionen der Beteiligten.

NESSIE und ihre Artgenossen

Die positiven Erfahrungen mit dem AES-Wettbewerb führten dazu, dass in den Folgejahren zwei weitere Veranstaltungen mit ähnlichem Ablauf stattfanden: NESSIE und CRYPTREC. Dabei handelte es sich um einen europäischen und um einen japanischen Wettbewerb.

NESSIE ist ein inzwischen abgeschlossenes europäisches Forschungsprojekt, dessen Inhalt ein Wettbewerb zur Findung starker kryptografischer Verfahren war. Die Abkürzung NESSIE steht für New European Schemes for Signatures, Integrity and Encryption. Im Gegensatz zum AES-Wettbewerb ging es bei NESSIE nicht nur um Verschlüsselungsverfahren. Vielmehr wurden in sieben kryptografischen Kategorien Sieger gekürt, darunter teilweise sogar mehrere pro Kategorie, um beispielsweise unterschiedliche Schlüssellängen zu unterstützen.

NESSIE startete 1999. Es gab insgesamt 42 Einreichungen, was bei sieben Kategorien nicht unbedingt viel ist. Der NESSIE-Wettbewerb sollte zwar ein europäisches Gegengewicht zum amerikanischen AES-Wettbewerb bilden, doch im Gegensatz zum Vorbild war ein Sieg nicht mit einer Deklarierung als Standard verbunden. Dies war wohl der Hauptgrund, warum NESSIE ein geringeres Interesse erfuhr als der AES-Wettbewerb. 2003 wurden die Sieger verkündet. Die erfolgreichen Verfahren sind auf der Wettbewerbs-Webseite nachzulesen.

CRYPTREC (Cryptography Research and Evaluation Committee) ist der Name eines japanischen Projekts, das etwa zeitgleich zu NESSIE lief und ebenfalls einen Krypto-Wettbewerb zum Inhalt hatte. Es wurden kryptografische Verfahren in vier Kategorien bewertet. Die Sieger wurden zwischen 2001 und 2003 veröffentlicht.

Inzwischen blicken Kryptografen, die sich für Algorithmen-Wettbewerbe interessieren, wieder in die USA. Die dortige Behörde NIST, die bereits den DES- und AES-Wettbewerb ausgerichtet hat, bereitet derzeit einen neuen Wettbewerb vor, in dem die beste kryptografische Hashfunktion (dies ist ein Einweg-Verschlüsselungsverfahren, das für spezielle Anwendungen benötigt wird) gefunden und standardisiert werden soll. Falls Sie sich beteiligen wollen, haben Sie noch ein paar Monate Zeit. Teilnehmer können bis zum 31. Oktober 2008 ihre Vorschläge einreichen.