80-Bit-Sicherheit und Angriffszeit

Die Frage läuft weitgehend zusammen an:

Was bedeutet $ n $ -Bit-Sicherheit in der Praxis für einen bestimmten Wert von $ n $ ?

TL; DR: so sicher wie eine gute symmetrische Verschlüsselung mit ein $ n $ -Bit-Schlüssel.

Es gibt keine präzisere Definition, selbst wenn wir uns auf Angreifer beschränken, die Klassik verwenden Computer (anstelle von Quantencomputern), wie dies bei dieser Antwort der Fall ist.

Eine allgemein akzeptierte Bedeutung ist, dass die Anzahl der „Schritte“ zum Brechen des Systems als angenommen wird $ 2 ^ n $ ; oder genauer gesagt, dass die Wahrscheinlichkeit, das System mit $ s $ „Schritten“ zu brechen, nicht größer als $ s \, 2 ^ {- n} $ nach einer beliebigen Methode für beliebig $ s $ . „Schritte“ und „Unterbrechung“ sind jedoch nicht genau definiert.

In der Theorie der symmetrischen Verschlüsselung wird „Schritt“ typischerweise als eine Ausführung der Verschlüsselung mit einem neuen Schlüssel angesehen. Auf diese Weise hat eine ideale Verschlüsselung mit einem Schlüssel aus $ n $ -Bits eine $ n $ -Bit-Sicherheit. unter Brute-Force-Schlüsselsuche. Wenn wir zum Üben übergehen, sind Angreifer nicht an die Brute-Force-Schlüsselsuche gebunden, und die Definition eines „Schritts“ muss zu einer Anzahl von Unterschritten werden, die in Anzahl und Rechenaufwand mit den für einen erforderlichen Unterschritten vergleichbar sind Ausführung der Chiffre mit einem neuen Schlüssel für einen Klartext von der Größe des Schlüssels . Mit dieser Definition hat eine praktische Chiffre mit einem Schlüssel von $ n $ Bits höchstens $ n $ – Bit-Sicherheit und zielt auf dieses Ideal ab.

Wenn wir zu Hashes übergehen, kann die Definition eines Schritts zu einer Anzahl von Teilschritten werden, die in Anzahl und Rechenaufwand mit den erforderlichen Teilschritten vergleichbar sind Zum Hashing einer neuen Nachricht die Größe der Hash-Ausgabe .

Eines der vielen Probleme mit dem oben genannten ist, dass es keine Einigung darüber gibt, ob wir die Kosten für Speicher und Speicherzugriffe zählen sollen oder nicht in den Rechenkosten. Aus Sicht eines Benutzers ist es sicher, es nicht zu zählen, aber das kann für einen Angreifer von größter Bedeutung sein.

Die Definition von „Schritten“ wird bei der asymmetrischen Kryptographie noch trüber wie RSA.Theoretisch könnten „Schritte“ eine Berechnung in der für das Kryptosystem verwendeten algebraischen Struktur sein; wie für RSA eine Bewertung der modularen Multiplikation $ (a, b) \ mapsto a \, b \ bmod N $ für eine beliebige ganze Zahl $ a $ und $ b $ in $ [0, N) $ , wobei $ N $ der öffentliche Modul ist. Es gibt jedoch Probleme, dies in die Praxis umzusetzen, insbesondere für RSA: Der bekannteste Angriff besteht darin, den öffentlichen Modul $ N $ mit der GNFS -Algorithmus, dessen Rechenaufwand von Operationen dominiert wird, die wenig Ähnlichkeit mit der modularen Multiplikation aufweisen, und deren praktische Kosten vom Speicher und den Zugriffen auf den Speicher dominiert werden. Damit wird die vage Definition in der TL; DR.

verwendet, um die Zeit für den Angriff auf dieses 80-Bit-Sicherheitskryptografieschema zu berechnen, z 80-Bit-Sicherheits-RSA mit einer Art CPU?

„80-Bit-Sicherheits-RSA“ ist nicht als RSA mit einer 80-Bit-Öffentlichkeit zu verstehen Modul $ N $ , der unheilbar unsicher ist. Wenn wir die Größe von $ N $ hätten, könnten wir die Schwierigkeit basierend auf dieser und früheren Erfahrungen abschätzen (siehe dies und seine Links). Dies ist jedoch nicht der Fall, und es besteht kein Konsens über die Größe von $ N $ für RSA mit 80-Bit-Sicherheit: 1024-Bit wird häufig zitiert, hängt jedoch von der Hypothese ab und wen Sie fragen, das ist viel zu viel oder zu wenig. Daher ist es am besten, zu ignorieren, dass es sich um RSA handelt, und zurück zu: so viel Zeit wie nötig, um eine gute symmetrische Chiffre mit einem 80-Bit zu brechen Schlüssel.

Das bringt uns zu: $$ \ text {Zeit} = \ frac {2 ^ n \ mal k \ mal p} {\ text {Frequenz } \ times \ text {Anzahl der CPUs}} $$ wobei $ n $ die Sicherheitsstufe in Bits ist, $ k $ ist eine Schätzung der Anzahl von CPU-Zyklen zur Bewertung einer guten Verschlüsselung unter Verwendung eines ultraoptimierten Algorithmus und $ p $ ist die verbleibende Erfolgswahrscheinlichkeit eines Gegners. Abhängig von der Perspektive können wir $ k = 1 $ (was das Untersuchen der Einzelheiten erspart), $ k = 32 $ (weil das immer noch weniger ist als bei den besten Angriffen gegen gute Chiffren mit einem Universalcomputer) oder viel mehr. Abhängig von der Perspektive können wir $ p = 1 $ (aus Sicht eines legitimen Benutzers am umsichtigsten), $ p nehmen = 1/2 $ (ergibt die erwartete Zeit im Fall einer Blockverschlüsselung) oder ein kleineres $ p $ , wenn wir eine Sicherheitsmarge wollen¹.

Zum Beispiel mit $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ ca.2 ^ {- 10} $ , $ \ text {Frequenz} = 4 \ text {GHz} \ ca.2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {Anzahl der CPUs} = 1000 \ ca.2 ^ {10} $ , wir erhalten $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , das sind ungefähr 8 Jahre. Mit anderen Worten, unsere 1000 CPUs haben nur eine sehr geringe Erfolgswahrscheinlichkeit gegenüber symmetrischer 80-Bit-Krypto, bis sie technisch veraltet sind.

Andererseits sind 1000 CPUs ein winziger Bruchteil von Weltweite CPUs und Bitcoin-Mining zeigen schlüssig, dass 80-Bit-Krypto nicht mehr gegen Gegner ausreicht, die ASICs entwerfen, in großen Mengen bauen und die Energiekosten für ihren Betrieb aufrechterhalten können. Siehe this .

¹ Der Begriff $ p $ in Die Formel ist aus Sicht eines legitimen Benutzers am umsichtigsten, führt jedoch dazu, dass $ \ text {Time} $ in vielen Angriffsszenarien unterschätzt wird Bei der Kollisionssuche wäre der richtige Begriff eher $ \ sqrt p $ .