Noch immer ungelöst: Die Weltrekord-Challenge

Der Weltrekord für den längsten kryptografischen Schlüssel, der per vollständiger Suche gelöst wurde, ist fast 20 Jahre alt. Wann wird endlich eine neue Bestmarke aufgestellt?

English version (translated with DeepL)

Zunächst einmal möchte ich mich für alle Zuschriften bedanken, die mich in den letzten drei Wochen bezüglich meines kürzlich erschienenen Comic-Bands “Versutus” erreicht haben. Vor allem über konstruktive Kritik freue ich mich sehr. “Versutus” gibt es auf Amazon zu kaufen. Als PDF kann man das gesamte Comic-Abenteuer sogar kostenlos herunterladen!

Quelle/Source: Schmeh

Ein alter Weltrekord

Kommen wir nun zum eigentlichen Thema des Tages. Da sich die Computer-Technik in den letzten Jahrzehnten erheblich weiterentwickelt hat, mag man kaum glauben, dass einer der bedeutendsten kryptografischen Weltrekorde seit fast 20 Jahren Bestand hat. Es geht um den längsten Schlüssel, der jemals durch Durchprobieren (auch als vollständige Schlüsselsuche oder “Brute Force” bekannt) geknackt wurde.

Im September 2002 berichteten die Medien ausführlich über den heute noch gültigen Rekord. Damals hatte ein Team der Initiative Distributed.net einen 64-Schlüssel des symmetrischen Verfahrens RC5 in fünfjähriger Arbeit mit einer vollständigen Suche geknackt. 331.252 Nutzer in aller Welt hatten Rechenkapazität zur Verfügung gestellt. Am Ende fand ein Teilnehmer in Japan den richtigen Kandidaten.

Quelle/Source: ITProToday

Die RSA-Challenges (1997-2007)

Die 64-Bit-Schlüsselsuche fand im Rahmen der so genannten RSA Secret-Key Challenges statt. Für diese Krypto-Rätsel-Serie veröffentlichte die US-Firma RSA Security im Jahr 1997 13 verschlüsselte Texte, die es mit vollständiger Schlüsselsuche zu lösen galt. 12 davon waren mit dem Verfahren RC5 verschlüsselt, einer mit dem DES. Dem jeweiligen Gewinner winkte ein Geldpreis. Die Texte waren mit Schlüsseln unterschiedlicher Länge verschlüsselt. Damit man Schlüsselkandidaten testen konnte, war jeweils ein Teil des Klartexts bekannt.

Es begann mit einem 32-Bit-RC5-Schlüssel, der schnell geknackt war. Auch der 40-Bit- und der 48-Schlüssel des RC5-Verfahrens waren für einige Teilnehmer der Challenge keine große Hürde. Um 56 Bit zu lösen, waren dagegen immerhin 140 Tage (DES) bzw. 265 Tage (RC5) notwendig. Und schließlich wurde auch, wie erwähnt, der 64-Bit-RC5-Schlüssel gelöst. 10.000 Dollar Preisgeld konnte Distributed.net dafür einstreichen.

Der logische nächste Schritt wäre gewesen, die 72-Bit-Challenge zu knacken. Tatsächlich wurde dazu ein Distributed.net-Projekt ins Leben gerufen, das jedoch zu keinem Erfolg kam. Es ist meines Wissens nicht mehr aktiv.

Im Mai 2007 gab der Veranstalter die Einstellung der acht noch offenen Secret-Key-Challenges bekannt. Die Lösungen wurden zwar nicht verraten, doch Preisgelder gab es keine mehr. Wer also Lust hat, kann sich nach wie vor an den Challenges mit den Schlüssellängen 72, 80, 88, 96, 104, 112, 120 und 128 versuchen.

Seit dem Brechen des 64-Bit-Schlüssels im Jahr 2002 hat niemand behauptet, einen längeren Schlüssel als diesen durch vollständige Suche geknackt zu haben. Das bedeutet, dass 64 Bit den aktuellen Weltrekord bilden.

Meine Weltrekord-Challenge

Bereits vor 12 Jahren beschloss ich, eine Challenge zu veröffentlichen, die das Knacken eines 65-Bit-Schlüssels durchvollständige Schlüsselsuche zum Inhalt hat. Das Kalkül dahinter dürfte klar sein: Wer die Challenge löst, stellt einen neuen Weltrekord auf. Genauer gesagt, wird der Weltrekord auf diese Weise um genau ein Bit verbessert.

Meine Weltrekord-Challenge habe ich auf der Krypto-Rätsel-Plattform MysteryTwister veröffentlicht (auf Deutsch und Englisch). 2017 habe ich zum ersten Mal darüber gebloggt.

Quelle/Source: MysteryTwister

Ein Preisgeld gibt es leider nicht. Es könnte aber zu einem gewissen Medienecho führen, wenn dieser Weltrekord nach 20 Jahren endlich verbessert wird.

Der Geheimtext, den ich verwendet habe, wurde mit der Software CrypTool verschlüsselt. Ich habe dazu den AES-Verschlüsselungsalgorithmus im ECB-Modus mit einer Schlüssellänge von 128 Bit gewählt. Die ersten 65 Bit des Schlüssels müssen erraten werden. Die restlichen 63 Bits sind auf 1 gesetzt.

Die ersten acht Bytes des Klartextes sind die Lösung der Aufgabe. Sie bilden ein englisches Wort, das in großen ASCII-Buchstaben geschrieben ist. Die restlichen acht Bytes haben den Wert “CrypTool” (im ASCII-Code) oder 43 72 79 70 54 6F 6F 6C (im Hexadezimal-Code).

Hier ist der Geheimtext der Weltrekord-Challenge (im Hexadezimal-Code):

4B 14 55 BC 8D DF 33 AF 57 91 53 90 BB 2C E1 2A

Da sich die Computertechnologie in den letzten 20 Jahren verbessert hat, sollte es heute möglich sein, die Lösung in deutlich weniger als fünf Jahren zu finden. Wenn wir davon ausgehen, dass sich die Rechenleistung alle 18 Monate verdoppelt (Moore’sches Gesetz), müsste die benötigte Zeit um das Achttausendfache geringer sein. Anstelle von fünf Jahren wären das nicht mehr als ein paar Stunden, sofern die gleiche Menge an Hardware verwendet wird wie damals.

Die Weltrekord-Challenge müsste also lösbar sein. Vielleicht hat ja ein Leser Lust, sich daran zu versuchen.
Follow @KlausSchmeh

Further reading: How to Use a Rubik’s Cube for Encryption

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/

Subscribe to Blog via Email

Kommentare (3)

Ich möchte niemandem den Spaß am Codeknacken verderben, aber mir stellt sich hier doch etwas die Sinnfrage:

– Bei über 330000 PCs die fünf Jahre an einem Problem rechnen, stellt sich die Frage nach dem Energieaufwand, den diese Challenge in Zeiten des rasanten Klimawandels gekostet hat. Hier kann man natürlich argumentieren, dass wir ohnehin eine beträchtliche Menge Energie für sinnloses Zeug wie Spiele, 4k-Videodecoding, Google-Suchanfragen nach “iPhone12” (unter den Top Ten 2020) oder – best of all – Cryptomining verplempern, aber das macht es nicht wirklich besser.

– Das Ergebnis ist in keiner Weise nutzbringend, bis auf die Erkenntnis, dass der Aufwand gewaltig ist. Selbst wenn die Information zum Zeitpunkt der Verschlüsselung relevant gewesen wäre, nach 5 Jahren wäre sie es vermutlich nicht mehr, und einen Fortschritt in der Cryptografie bringt das Knacken eines Schlüssels mittels Brute Force auch nicht.

– Der “Gewinner” dieser Challenge hat keine wirkliche Leistung erbracht – Brute-Force-Attacken sind zwar aufwändig aber mathematisch anspruchslos. Der Gewinner hat nur zufällig im richtigen Intervall von Schlüsseln gesucht. Theoretisch hätte der richtige Key schon nach 20 Sekunden gefunden werden können, und was dann?

– Mit modernen CPUs/GPUs oder Spezialhardware könnten Dauer und Energieaufwand vielleicht um den Faktor 100 oder 1000 oder 100000 verkleinert werden, aber mit einer um 7 oder 10 oder 17 Bit vergrößerten Schlüssellänge wäre dieser Vorteil schon wieder verloren. Man sprengt immer dickere Wände mit immer mehr Sprengstoff.

@schlappohr: Das sehe ich alles auch so. Und dennoch:
Erstens gelten diese Argumente für alle “Challenges”, sofern bei der Lösung nicht neue Verfahren entwickelt werden.
Zweitens ist es schon von einem gewissen Interesse, Aussagen über sichere Schlüssellängen nicht nur aus theoretischen Extrapolationen herzuleiten, sondern auch auf konkrete praktische Ergebnisse zurückgreifen zu können.

@schlappohr:
>aber mir stellt sich hier doch etwas die Sinnfrage
Das kann man sicherlich so sehen. Es gibt zweifellos wichtigere Dinge in der Kryptografie. Trotzdem fände ich es interessant zu wissen, welche Schlüssellänge man heutzutage mit realistisschem Aufwand knacken kann.

#1 schlappohr
12. Januar 2022

Ich möchte niemandem den Spaß am Codeknacken verderben, aber mir stellt sich hier doch etwas die Sinnfrage:

– Bei über 330000 PCs die fünf Jahre an einem Problem rechnen, stellt sich die Frage nach dem Energieaufwand, den diese Challenge in Zeiten des rasanten Klimawandels gekostet hat. Hier kann man natürlich argumentieren, dass wir ohnehin eine beträchtliche Menge Energie für sinnloses Zeug wie Spiele, 4k-Videodecoding, Google-Suchanfragen nach “iPhone12” (unter den Top Ten 2020) oder – best of all – Cryptomining verplempern, aber das macht es nicht wirklich besser.

– Das Ergebnis ist in keiner Weise nutzbringend, bis auf die Erkenntnis, dass der Aufwand gewaltig ist. Selbst wenn die Information zum Zeitpunkt der Verschlüsselung relevant gewesen wäre, nach 5 Jahren wäre sie es vermutlich nicht mehr, und einen Fortschritt in der Cryptografie bringt das Knacken eines Schlüssels mittels Brute Force auch nicht.

– Der “Gewinner” dieser Challenge hat keine wirkliche Leistung erbracht – Brute-Force-Attacken sind zwar aufwändig aber mathematisch anspruchslos. Der Gewinner hat nur zufällig im richtigen Intervall von Schlüsseln gesucht. Theoretisch hätte der richtige Key schon nach 20 Sekunden gefunden werden können, und was dann?

– Mit modernen CPUs/GPUs oder Spezialhardware könnten Dauer und Energieaufwand vielleicht um den Faktor 100 oder 1000 oder 100000 verkleinert werden, aber mit einer um 7 oder 10 oder 17 Bit vergrößerten Schlüssellänge wäre dieser Vorteil schon wieder verloren. Man sprengt immer dickere Wände mit immer mehr Sprengstoff.
#2 Klaus Pommerening
Mainz und Öhningen
15. Januar 2022

@schlappohr: Das sehe ich alles auch so. Und dennoch:
Erstens gelten diese Argumente für alle “Challenges”, sofern bei der Lösung nicht neue Verfahren entwickelt werden.
Zweitens ist es schon von einem gewissen Interesse, Aussagen über sichere Schlüssellängen nicht nur aus theoretischen Extrapolationen herzuleiten, sondern auch auf konkrete praktische Ergebnisse zurückgreifen zu können.
#3 Klaus Schmeh
15. Januar 2022

@schlappohr:
>aber mir stellt sich hier doch etwas die Sinnfrage
Das kann man sicherlich so sehen. Es gibt zweifellos wichtigere Dinge in der Kryptografie. Trotzdem fände ich es interessant zu wissen, welche Schlüssellänge man heutzutage mit realistisschem Aufwand knacken kann.