So funktionieren Brute-Force-Angriffe

Ein Brute-Force-Angriff auf eine Chiffre probiert jeden möglichen Schlüssel aus, bis der richtige gefunden wird. Für einen Schlüssel mit n Bit gibt es 2^n mögliche Schlüssel. Bei einem 3-Bit-Schlüssel gibt es nur 8 Möglichkeiten, bei einem 56-Bit-Schlüssel mehr als 72 Billiarden. Der grundlegende Schutz vor Brute-Force besteht darin, Schlüssel zu wählen, die groß genug sind, sodass eine vollständige Suche innerhalb eines sinnvollen Zeitraums rechnerisch nicht durchführbar ist.

DES (Data Encryption Standard) verwendet einen 56-Bit-Schlüssel und bietet damit einen Schlüsselraum von ungefähr 7,2 * 10^16. Im Jahr 1977 erschien das gewaltig. 1998 brach die Deep-Crack-Maschine der EFF DES in 56 Stunden für 250.000 US-Dollar. 2006 konnte ein speziell entwickelter Cluster DES in weniger als 9 Tagen für unter 10.000 US-Dollar brechen. Die Lehre war eindeutig: 56 Bit boten gegen einen motivierten Angreifer keine ausreichende Sicherheit mehr.

AES-128 verwendet 128-Bit-Schlüssel, wodurch es 2^128 mögliche Schlüssel gibt, also ungefähr 3,4 * 10^38. Selbst wenn jedes Atom im beobachtbaren Universum ein Computer wäre, der seit dem Urknall eine Milliarde Schlüsseltests pro Sekunde durchführen würde, wäre die Suche noch nicht annähernd abgeschlossen. Selbst bei exponentiell schnellerer Hardware in der Zukunft werden 128-Bit-Schlüssel voraussichtlich auf absehbare Zeit gegen klassische Brute-Force-Angriffe sicher bleiben.

Online-Brute-Force-Angriffe zielen auf aktive Systeme ab, indem sie wiederholt Authentifizierungsanfragen senden. Sie werden durch Netzwerklatenz, die Antwortzeit des Servers und Ratenbegrenzungen eingeschränkt, wodurch sie langsam sind. Offline-Brute-Force-Angriffe arbeiten mit gestohlenen Daten, etwa einer Datenbank mit Passwort-Hashes. Mit den Hashes kann ein Angreifer mithilfe lokaler Hardware und ohne Einschränkungen durch das Netzwerk Milliarden von Kandidaten pro Sekunde testen.

Moderne GPUs enthalten Tausende parallel arbeitende Rechenkerne, die für Gleitkommaarithmetik optimiert sind. Hashcat, das führende GPU-Tool zum Knacken von Hashes, kann auf einer einzelnen leistungsstarken GPU über 100 Milliarden MD5-Hashes pro Sekunde testen. Ein Verbund aus acht GPUs kann über 800 Milliarden Kandidaten pro Sekunde testen. Dadurch sind schlecht gewählte Passwörter und schwache Hashfunktionen für schnelles Offline-Cracking anfällig.

Anwendungsspezifische integrierte Schaltungen sind Chips, die ausschließlich für eine einzige Berechnung entwickelt wurden. Bitcoin-Miner verwenden ASICs, die SHA-256-Hashes mit mehreren zehn Terahashes pro Sekunde berechnen – deutlich schneller als jede GPU. Bitcoin-ASICs berechnen zwar eine andere Operation als beim Passwort-Cracking, aber das Prinzip ist dasselbe: Speziell entwickelte Hardware ermöglicht bei bestimmten kryptografischen Berechnungen eine um Größenordnungen höhere Geschwindigkeit als universell einsetzbare Hardware.

Nach Moores Gesetz verdoppelte sich die Transistordichte ungefähr alle zwei Jahre, was historisch eine entsprechende Steigerung der Rechenleistung bewirkte. Eine Schlüssellänge, die heute als sicher gilt, muss auch angesichts künftiger Verbesserungen der Hardware über Jahrzehnte hinweg sicher bleiben. Sicherheitsempfehlungen enthalten daher erhebliche Sicherheitsmargen. AES-128 würde eine Beschleunigung der Berechnungen um den Faktor 2^64 benötigen, um durch klassische Brute-Force-Angriffe verwundbar zu werden. Das liegt weit jenseits jeder plausiblen Extrapolation des Mooreschen Gesetzes.

NIST SP 800-57 legt Sicherheitsstärken für kryptografische Algorithmen fest. 112-Bit-Sicherheit ist derzeit das Minimum für neue Systeme. Für langfristigen Schutz wird 128-Bit-Sicherheit empfohlen. Symmetrische Schlüssel mit 256 Bit bieten eine Sicherheitsmarge über die derzeit absehbaren Bedrohungen durch klassische Computer hinaus. NIST rät von Sicherheitsstufen mit 80 Bit oder weniger ab, da diese für jede neue Anwendung als unzureichend gelten.

Grov ers Quanten-Suchalgorithmus ermöglicht eine quadratische Beschleunigung bei der unstrukturierten Suche. Das bedeutet, dass ein Schlüsselraum mit N Elementen in ungefähr sqrt(N) Schritten statt in N Schritten durchsucht werden kann. Für AES-128 reduziert sich die Sicherheit gegenüber einem Quantenangreifer dadurch effektiv auf 64 Bit. Für AES-256 beträgt die effektive Sicherheit gegenüber Grov ers Algorithmus 128 Bit. Deshalb werden symmetrische Schlüssel mit 256 Bit für Postquanten-Sicherheit empfohlen.

Um gegenüber einem Quantencomputer, auf dem Grov ers Algorithmus ausgeführt wird, eine Sicherheit von 128 Bit zu gewährleisten, müssen symmetrische Schlüssel mindestens 256 Bit lang sein. AES-256 hat bereits diese Größe und gilt für symmetrische Verschlüsselung als quantensicher. Zur Einordnung: Eine Verdopplung der Schlüssellänge von 128 auf 256 Bit verdoppelt nicht den Rechenaufwand für den regulären Benutzer – sie fügt nur einige weitere AES-Runden hinzu –, erfordert aber, dass der Angreifer seine Quantenressourcen quadriert.

Sicherheitsteams setzen Brute-Force-Tools bei autorisierten Passwortprüfungen ein, um schwache Zugangsdaten zu identifizieren, bevor Angreifer dies tun. Hashcat und John the Ripper werden auf exportierte Datenbanken mit Passwort-Hashes angewendet, um zu ermitteln, welcher Anteil der Passwörter geknackt werden könnte. Die Ergebnisse der Prüfung führen zu Verbesserungen der Passwortrichtlinien: Anforderungen an die Mindestlänge, Komplexitätsregeln und die Einführung moderner Passwort-Hashing-Algorithmen wie bcrypt oder Argon2.

Wie wirkt sich Grov ers Quantenalgorithmus auf die effektive Sicherheit von AES-128 aus?

Brute-Force testet jeden möglichen Schlüssel; Sicherheit erfordert Schlüsselräume, die sich in der Praxis nicht vollständig durchsuchen lassen. DES mit 56 Bit wurde 1998 gebrochen. AES-128 mit 2^128 möglichen Schlüsseln ist für klassische Computer nicht praktikabel anzugreifen. GPU-Cluster knacken Hashes offline mit Hunderten Milliarden Versuchen pro Sekunde. Grov ers Quantenalgorithmus halbiert die Bitsicherheit, weshalb für eine Postquanten-Sicherheit von 128 Bit Schlüssel mit 256 Bit erforderlich sind. NIST empfiehlt für neue Systeme eine Mindestsicherheit von 128 Bit.