Home > Kryptographie > Schlüssellänge

Kryptographie

6. Schlüssellänge

Auf die Länge kommt es an? ... Jedenfalls meistens. Es nützt natürlich nichts, einen langen Schlüssel zu verwenden, wenn das Verfahren schwach ist und ohne Kenntnis des Schlüssels leichter geknackt werden kann als mit Brute-Force-Attacken. Trotzdem ist die Schlüssellänge ein entscheidener Faktor bei kryptographischen Algorithmen. Heutzutage sollte jedes Verfahren mindestens 128-Bit-Schlüssel akzeptieren. Aber was bedeuten solche Zahlen überhaupt? 56 Bit, 128 Bit, 256 Bit, 2048 Bit? In diesem Kapitel werde ich Ihnen etwas mehr über solche "großen" Zahlen erzählen.

• 
• Einführung
• Die Methoden
• 56-Bit-Schlüssel
• 128-Bit-Schlüssel
• 256-Bit-Schlüssel
• 512-Bit-Schlüssel
• Fazit

Einführung

Zunächst einmal ein kleiner Einblick, in welcher Größenordnungen diese Zahlen liegen:

Quelle: Bruce Schneier, Angewandte Kryptographie

Wie schnell kann man inzwischen symmetrische Schlüssel mittels Brute Force brechen? (Für Schlüssel asymmetrischer Verfahren gelten andere Zahlen.) Zur Verdeutlichung noch eine Tabelle, ebenfalls aus Schneiers "Angewandte Kryptographie":

Stand: 1995

Ein Beispiel für ein Verfahren, welches mit 40-Bit-Schlüsseln arbeitet, ist eine spezielle Implementation von RC4, die infolge der damaligen Export-Regelung für Krypto-Produkte in den USA auf 40 Bit beschränkt werden musste. Die berühmten 56 Bit gehören natürlich zu DES. Einige wenige betagte Algorithmen verwendeten noch 64 Bit (wie SAFER von James Massey; es existiert allerdings auch eine 128-Bit-Variante, die als sicher angesehen wird). Skipjack, ein geheimes Verfahren, das von der NSA entwickelt wurde, arbeitet mit Blöcken und Schlüsseln der Länge 80 Bit. Eine Variante von Triple-DES verwendet Schlüssel der Länge 112 Bit. Alle modernen Algorithmen arbeiten schließlich mit (mindestens!) 128-Bit-Schlüsseln, wie z. B. Lucifer, der Vorläufer von DES, IDEA oder die AES-Kandidaten.

Die Methoden

Welche Methoden gibt es, einen Schlüssel zu brechen? Die Antwort lautet: Reichlich. Doch bevor wir ans Eingemachte gehen, müssen wir erst noch ein paar Dinge zur Sprache bringen. Zunächst einmal werden wir uns in diesem Kapitel an Brute-Force-Angriffen versuchen. Dieser Angriff ist der simpelste überhaupt: Es werden einfach alle möglichen Schlüssel durchprobiert! Brute Force muss aber nicht notwendigerweise der beste Angriff sein; ist die Chiffrierung schwach, gibt es Angriffere, die schneller durchzuführen sind als Brute Force. Wir setzen also kühn voraus, dass der Krypto-Algorithmus optimal ist, d. h. Brute Force die beste Methode zum Knacken darstellt (was in der Praxis äußerst schwierig zu erreichen ist). Für den Angriff benötigt der Kryptoanalytiker etwas Chiffretext, den er zum Angriff heranzieht, indem er den Text mit allen möglichen Schlüsseln entschlüsselt und die Ergebnisse auf ihre Güte hin überprüft. Je nach Größe des Schlüsselraums und der vorhandenen Mittel zum Knacken kann es 20 Stunden (DES-Cracker mit einer Million Chips, die jeweils eine Million Schlüssel pro Sekunde berechnen können), 214 Tage (DES-Cracker angewandt auf Algorithmen mit 64-Bit-Schlüssel), 2285 Jahre (Computer zum Knacken von DES, welcher eine Million Schlüssel pro Sekunde berechnen kann), 10²⁵ Jahre (Selber Computer angewandt auf Verfahren mit 128-Bit-Schlüssel) oder gar 10⁵⁹⁷ Jahre (Computer angewandt auf Verfahren mit 2048-Bit-Schlüssel) dauern, bis der richtige Schlüssel gefunden ist. Bedenken Sie jedoch, dass das Universum schätzungsweise "erst" 10¹⁰ Jahre alt ist; unter der Voraussetzung, dass das Universum geschlossen ist, hat es eine Lebensdauer von 10¹¹ Jahren. Falls das Universum offen ist, wird, bevor 10⁵⁹⁷ Jahre vergangen sind, sämtliche Materie bei null Kelvin flüssig geworden sein.

Bei Brute-Force-Angriffen, wie wir sie in unseren Beispielen versuchen werden, benötigen zumeist viel Rechenleistung. Die Geschwindigkeit eines solchen Angriffs hängt erstens von der Anzahl der durchzuprobierenden Schlüssel (bei einem 56-Bit-Schlüssel sind es 72.057.594.037.927.936 mögliche Schlüssel) und zweitens von der Geschwindigkeit eines einzelnen Tests ab. Die Geschwindigkeiten der verfügbaren Algorithmen unterscheiden sich natürlich manchmal erheblich voneinander: So ist Blowfish fast viermal schneller als der alte DES. In unseren Beispielen sollen diese Unterschiede unberücksichtigt bleiben, da wir nach Schlüssellängen suchen, die die Kapazität dessen, was heute möglich ist, weit übersteigen; kleine Unterschiede spielen hierbei keine große Rolle mehr.

Bei unseren Beispielberechnungen müssen wir uns auf grobe Schätzungen einlassen. Wer weiß schon, was in 30, 50 oder 100 Jahren durchführbar ist und in den Rahmen des Möglichen gerückt wird? Man geht davon aus, dass sich die Rechenleistung alle fünf Jahre verzehnfacht. Durchbrüche sind auch hier möglich. Andererseits könnte man auf physikalische Grenzen stoßen, die weitere Fortschritte unmöglich machen. Gleichwohl ist in der Kryptographie Pessimismus angebracht: Sie sollten auf jeden Fall, sofern möglich, eine eher konservative Entscheidung treffen und die sicherere Alternative wählen.

Man kann Brute-Force-Angriffe mit Software durchführen. Obgleich ein Software-Angriff etwa tausendmal langsamer als ein Hardware-Angriff ist, bietet diese Art des Angreifens einen entscheidenden Vorteil: Der Angriff ist praktisch "umsonst"! Es kostet nichts, einen Computer in seiner Leerlaufzeit alle möglichen Schlüssel durchprobieren zu lassen. So sind große Computer-Netzwerke (z. B. in Universitäten) denkbar, die 56-Bit-Schlüssel mit einer bestimmten Wahrscheinlichkeit an einem einzigen Tag oder garantiert in einer bestimmten Zeitspanne knacken können. Derartige Angriffe auf 128-Bit-Schlüssel bleiben jedoch undurchführbar (d. h. die Dauer überschreitet das Alter des Universums), selbst wenn man alle verfügbaren Computer vernetzen würde.

Wie kann man eine möglichst große Zahl von PC-Besitzern zur Teilnahme an einem solchen Angriff bewegen? Zunächst einmal kann man eine Art "Wettbewerb" veranstalten: Man lädt Leute zur Teilnahme an einem öffentlichen Crack ein, indem man sie beispielsweise mit Sachpreisen anlockt. Die Teilnehmer laden sich eine spezielle Software herunter, die während der Leerlaufzeit der CPU einen Brute-Force-Angriff durchführt. Über Internet werden fortwährend Ergebnisse ausgetauscht. Um die Teilnehmer dazu zu bewegen, das Programm möglichst lange laufen zu lassen, kann man weitere Wettbewerbe um die aktivste Teilnahme veranstalten. Beispiele für solche Projekte sind RC4- oder RC5-Cracking-Projekte, die es sich zum Ziel gesetzt haben, 40- oder 64-Bit-Schlüssel zu brechen. Heimtückischer dagegen sind Computer-Viren, deren Ziel es ist, unentdeckt Brute-Force-Angriffe durchzuführen. Ist der Rechner einen großen Teil seines Betriebs untätig, wird es dem Virus nicht schwerfallen, Zeit für seine Aufgabe zu finden. Wird der richtige Schlüssel gefunden, könnte z. B. eine Meldung ausgegeben werden, die Aussicht auf eine Belohnung stellt und so den "Gewinner" dazu anregt, den gefundenen Schlüssel preiszugeben.

56-Bit-Schlüssel

Kommen wir jetzt zur Schlüssellänge von DES. Diese beträgt ja bekanntlich "nur" 56 Bits. Dafür gibt es immerhin 7,2 · 10¹⁶ Möglichkeiten. Die Wahrscheinlichkeit, diesen Schlüssel beim ersten Mal richtig zu raten, ist in etwa genauso groß wie die Wahrscheinlichkeit, im Lotto den Hauptpreis zu gewinnen und am gleichen Tag vom Blitz erschlagen zu werden – also sehr, sehr gering. Aber wir wollen keine lustige Ratestunde veranstalten. Wir probieren's mit nackter Gewalt, mit Brute Force. Wir gewinnen tatsächlich im Lotto und lassen uns tausend hochmoderne Computer bauen (unser Erspartes legen wir natürlich dazu!). Diese Computer können 1.000.000.000 (1 Milliarde) Schlüssel pro Sekunde berechnen. So, jetzt denken wir uns noch ein ausgeklügeltes System aus, so dass wir jeden Computer effektiv nutzen können. Wir stellen uns diese 1.000 Computer als einen Computer vor, der jetzt 1.000 · 1.000.000.000 Schlüssel pro Sekunde berechnen kann. Wir teilen 7,2 · 10¹⁶ also durch 1 Billion und erhalten die Zeit in Sekunden, die wir brauchen, um DES zu knacken: 72.058 s. In Stunden sind das (geteilt durch 3.600) 20 Stunden. Ziemlich flott, finden Sie nicht? Aber wenn wir viel Geld haben, steht uns weitaus Besseres zur Verfügung. Wir nehmen 1 Million Chips, die 1 Milliarde Schlüssel pro Sekunde berechnen können. Damit ergeben sich 72 s zum Knacken von DES! Wem 10¹³ Dollar zur Verfügung stehen, kann DES gar in 1 Millisekunde knacken!

Schon 1977 ersonnen Whitfield Diffie und Martin Hellman eine spezielle DES-Cracking-Maschine (s. o.), die aus einer Million Chips besteht, welche jeweils eine Million Schlüssel pro Sekunde berechnen können. Diese Maschine ist in der Lage, alle 2⁵⁶ mögliche DES-Schlüssel in 20 Stunden zu testen; ein Angriff gegen 64-Bit-Schlüssel würde 214 Tage dauern.

Stellen Sie sich nun Biochips in Form von Zellen vor, die mögliche Schlüssel testen können. Bruce Schneier führt am Beispiel eines Dinosauriers an, wie effektiv ein Brute-Force-Angriff auf DES wäre:

Ein typischer Dinosaurier bestand aus 10¹⁴ Zellen. Wenn jede davon zu einer Million Verschlüsselungen pro Sekunde in der Lage ist [...], würde das Knacken eines 56-Bit-Schlüssels sieben Zehntausendstel Sekunden dauern.

128-Bit-Schlüssel

Sie sehen schon: DES ist nicht sicher. Privatpersonen werden Sie vielleicht noch aufhalten können, gegen Firmen mit etwas Geld werden Sie sich aber nicht wehren können. Schon mit weniger als 100.000 Dollar kann man DES innerhalb von 35 Stunden knacken! Aber 56 Bits sind ja heute total "out". "In" sind mindestens 128 Bits. Denken Sie jetzt nicht, 128 Bits wären nur ungefähr doppelt so viel wie 56 Bits! 128 Bits sind 2⁷² (ca. 10²¹) mal mehr als 56 Bits! So, jetzt wollen wir solche 128-Bit-Chiffrierungen einmal angreifen. Zuerst wieder als Privatperson mit ein paar Hunderttausendern. 2¹²⁸ sind in Zehnerpotenzen ausgedrückt ca. 10³⁸. Wir probieren's also mit tausend Chips, die 1 Milliarde Schlüssel pro Sekunde berechnen können. Wir rechnen also 10³⁸ / 1.000 / 1.000.000.000 / 3.600 / 24 / 365 und erhalten somit 10¹⁹ Jahre. Bis dahin werden wahrscheinlich keine Menschen mehr auf der Erde existieren, wenn die Sonne erst mal verglüht ist. Gut – jetzt versuchen ma's eben als stinkreiche Regierung, denen eine verschlüsselte Nachricht 10¹³ Dollar wert ist. Bitte, bitte! Denn dieselbe Regierung, die DES in 1 ms knacken kann, braucht für Algorithmen wie IDEA, die einen 128-Bit-Schlüssel benutzen, 100 Milliarden Jahre! Na dann ...

Ralf Senderek rechnet uns vor:

Nach dem heutigen Stand der physikalischen Forschung, der sich natürlich ändern kann, ist die Signalübertragung in jedem denkbaren Computersystem durch die Lichtgeschwindigkeit begrenzt.
Dem widersprechen auch nicht die bisherigen "Überlichtgeschwindigkeitsexperimente".

Angenommen das Hochleistungscomputersystem zum Schlüsseltest hat eine maximale Ausdehnung von 0,3 mm, in der die elektronische oder lichtgeleitete Informationsübertragung erfolgt, dann kann es maximal 1 000 000 000 000 Operationen (10¹²) in jeder Sekunde ausführen, weil es sonst kleiner sein müsste. In 317 Jahren, also 10 003 759 200 Sekunden ist dieses System in der Lage 10 003 759 200 000 000 000 000 Operationen auszuführen. Diese bescheidenen Leistungsfähigkeit von immerhin 10²² Operationen, die in diesen 317 Jahren ausführbar sind, ermöglicht natürlich nicht die Überprüfung von 10²² verschiedenen IDEA-Schlüsseln, weil ein Schlüsseltest sich nicht in einem Taktzyklus erledigen lässt. Aber selbst wenn dies möglich wäre, ist die große Anzahl der möglichen IDEA-Schlüssel von 10³⁸ dann nur zu 0,000 000 000 000 000 029 Prozent durchsucht. Also wird ein einzelner IDEA-Schlüssel auch dann nicht gefunden werden, wenn man "viele" solcher Computersysteme parallel an die Arbeit setzt.

Dieses Argument basiert auf empirischen Annahmen und kann deshalb auch durch die Erfahrung widerlegt werden. Es ist aber sicherlich empirisch falsch, Computersystemen eine "in Zukunft beliebig große Leistungsfähigkeit" zu unterstellen.

Möglich wären auch Algen von der Größe 10 Mikrometer, die jeweils 1 Million Schlüssel pro Sekunde berechnen können. Kippt man soviele davon ins Meer, dass sie eine Fläche von 518 km² bei einem Meter Tiefe bedecken (dazu sind 10²³ Exemplare nötig) und lässt sie einen Angriff auf 128-Bit-Schlüssel starten, so benötigt man immer noch über 100 Jahre, bis der richtige Schlüssel gefunden ist. Dieses Beispiel ist freilich nur ein reines Gedankenexperiment – wie wollen Sie mit den Algen fertig werden? Im Nanometerbereich ist aber sicherlich noch Einiges mehr vorstellbar.

256-Bit-Schlüssel

Jetzt wird's etwas phantastisch. Denn jetzt "bauen" wir uns einen Planeten, der so groß ist wie unsere Sonne und gänzlich aus Chips besteht (fragen Sie mich nicht, wie das funktionieren soll). Diese Chips können eine Milliarde Schlüssel pro Sekunde berechnen. Also, die Sonne besteht aus 10⁵⁷ Atomen. Für einen 256-Bit-Schlüssel gibt es 10⁷⁷ Möglichkeiten. Wir führen also die Rechnung 10⁷⁷ / 10⁵⁷ / 1.000.000.000 / 3.600 / 24 / 365 durch und erhalten 3.672 Jahre. Immer noch ziemlich lange, finden Sie nicht? Mit "normalen" Mitteln können wir 256-Bit-Schlüssel sowieso nicht knacken. Um solch einen Schlüssel in annehmbaren 100 Jahren zu knacken, bräuchten wir schon 10⁶⁵ Chips, die jeweils 1 Billion Schlüssel pro Sekunde berechnen können (oder umgekehrt, wie Sie wollen). Und das halte ich für unmöglich. Es ist sehr unwahrscheinlich, dass 256-Bit-Schlüssel je geknackt werden können, da dazu einfach zu viel Energie und zu viele Chips nötig sind. Aber sagen Sie nicht, ich hätte Sie nicht gewarnt! ... :-)

In seinem Buch "Angewandte Kryptographie" zeigt Bruce Schneier die Einschränkung durch die Thermodynmaik auf: Zur Repräsentation eines Bits ist eine bestimmte Energie erforderlich. Der im Buch beschriebene Ansatz besteht darin, die Energie einer Supernovae zu sammeln und mit dieser Energie den Schlüsselraum (d. h. die Anzahl der Möglichkeiten eines Schlüssels) zu durchsuchen. Schneier erläutert:

Eine typische Supernova gibt etwa 10⁵¹ erg ab. [...] Könnte all diese Energie in eine einzige Berechnungsorgie kanalisiert werden, könnten wir damit einen 219-Bit-Zähler all seine Zustände durchlaufen lassen.

Das reicht nicht einmal für einen 256-Bit-Schlüssel, und so resümiert er schließlich:

Diese Zahlen haben nichts mit der Gerätetechnik zu tun, es handelt sich um die nach den Gesetzen der Thermodynamik maximal erreichbaren Werte. Und sie lassen sehr deutlich darauf schließen, dass Brute-Force-Angriffe gegen 256-Bit-Schlüssel undurchführbar sind, bis Computer nicht mehr aus Materie bestehen und keine räumliche Ausdehnung besitzen.

512-Bit-Schlüssel

Es wird noch phantastischer. Denn jetzt besitzen wir ein ganzes Universum, das so groß wie unseres ist. Dieses Universum besteht aus 10⁸⁰ Chip-Atomen. Für einen 512-Bit-Schlüssel gibt es um den Dreh 10¹⁵⁴ Möglichkeiten. Jeder dieser "Chips" müsste über 10⁶⁴ Schlüssel pro Sekunde berechnen können, um einen derartigen Schlüssel in annehmbaren 100 Jahren knacken zu können! Und die unglaublich große Zahl 10⁶⁴ sprengt den Rahmen des Möglichen bei weitem. Eine Berechnung, wie viel Zeit wir wohl mit so und so viel Rechenleistung benötigen würden, lohnt sich also gar nicht, denn dazu bräuchten wir schon unvorstellbar viel Energie, die wir niemals aufbringen können. Angriffe gegen solche Schlüssel sind praktisch undurchführbar. Ich behaupte, 512-Bit-Schlüssel sind unknackbar. Wenn wir ein solches Unterfangen wirklich in Angriff nehmen wollten, benötigten wir entweder enorm viele Chips, für die es im ganzen Universum aber nicht genug Platz gibt, oder enorm viel Energie, die wir sehr, sehr lange sammeln müssten – dafür haben wir allerdings nicht annähernd genug Zeit, denn bis dahin existiert die Erde gar nicht mehr ...

(Alle Berechnungen erfolgten ohne Berücksichtigung möglicher Zeitreisen, Parallel-Universen, Wurmlöchern, Aliens etc. ;-)

Fazit

Die Zahlen, mit denen Kryptologen arbeiten, sind groß. Aber größtenteils ist dies alles nur Theorie. In der Praxis sieht das ganz anders aus – wie Sie sich sicherlich denken können. Oftmals ist es gar nicht nötig, Brute Force anzuwenden. Man greift ein System an seinem schwächsten Punkt an. So wurden bereits viele Verschlüsselungs-Programme geknackt. Zum Beispiel nicht gelöschte Passwörter, hinterlassene temporäre Dateien, die nicht überschrieben wurden etc. Selbst wenn das Programm sicher ist, kann ein Kryptoanalytiker die Schwäche von Menschen ausnutzen, schlechte Passwörter zu wählen. Aber das ist noch ein ganz anderes Thema ...

Sie sollten allerdings auch bedenken, dass es nicht immer erforderlich ist, lange Schlüssel zu wählen. Denn: Wie viel sind meine Daten eigentlich wert? Wie lange besitzen sie Gültigkeit? Würden Sie 128-Bit-Passwörter für Ihre Registrierung bei einem Chat-Room wählen? Oder für das Abonnement eines Newsletters? Wenn Sie jeden Tag, jede Woche oder jeden Monat ein neues Passwort wählen, müssen Sie dann 128-Bit-Passwörter wählen? Sind Ihre Daten nur für einen bestimmten Zeitraum von Bedeutung? Sie sehen: Nicht immer ist es vonnöten, lange Schlüssel zu verwenden. Vor allem dann, wenn Sie die Schlüssel in Form von Passwörtern mühsam memorieren müssen. Ein "gutes" (im Sinne von "zufällig") 128-Bit-Passwort merken Sie sich nicht "einfach mal so" – Sie müssen es wirklich auswendig kennen und dürfen es niemals vergessen! Es stellt sich nun die Frage: Wie viel Sicherheit brauche ich wirklich? Wenn es um Ihre Zugangsdaten bei Ihrem Provider geht, sollten Sie ein sicheres Passwort wählen. Bei weniger wichtigen Dingen sollten Sie dies nicht tun. Bedenken Sie, dass Passwörter oft per E-Mail übertragen werden und damit für alle neugierigen Lauscher sichtbar sind! Überlegen Sie, vor allem als Privatperson, also gut, welches Sicherheitsniveau im Einzelfall für Sie in Frage kommt und wie viel Ihnen Ihre Daten wert sind.

Anmerkung: Wenn es in bestimmten Fällen kein großes Hindernis darstellt, den Schlüssel aufzubewahren, ist es natürlich unsinnig, Passwörter niedriger Sicherheit zu wählen. Wenn Sie es pflegen, Ihre Schlüssel auf Diskette zu speichern und in einem Safe aufzubewahren, warum sollten Sie dann nur 64-Bit-Schlüssel einsetzen? Ihre Schlüssel sind dann natürlich nur so sicher wie der Safe, den sie zum Schutz verwenden! Wenn Sie ein Gedächtnis-Künstler sind und ein Faible für lange Passwörter haben, warum sollten Sie dann auf kürzere Passwörter umsteigen?

Mehr zur leidigen Passwort-Thematik finden Sie auf meiner speziellen Seite.

Zurück

nach oben

Übersicht

Weiter

Letzte Änderung: 24.03.2002
© 2002 by Christian Thöing