80-bitowe zabezpieczenia i czas ataku

Pytanie w dużej mierze sprowadza się do to:

Co oznacza $ n $ -bitowe zabezpieczenie oznacza w praktyce dla danej wartości of $ n $ ?

TL; DR: tak bezpieczny, jak dobry szyfr symetryczny z $ n $ -bitowy klucz.

Nie ma jednej dokładniejszej definicji, nawet jeśli ograniczymy się do atakujących używających klasycznej komputery (a nie komputery kwantowe), tak jak w tej odpowiedzi.

Jednym z ogólnie przyjętych znaczeń jest to, że uważa się, że liczba „kroków” do zerwania systemu to $ 2 ^ n $ ; a dokładniej, prawdopodobieństwo zerwania systemu przez $ s $ „steps” nie jest większe niż $ s \, 2 ^ {- n} $ dowolną metodą dla dowolny $ s $ . Jednak „kroki” i „złamanie” nie są dokładnie zdefiniowane.

W teorii szyfrowania symetrycznego „krok” jest zwykle traktowany jako jedno wykonanie szyfru z nowym kluczem. W ten sposób idealny szyfr z kluczem $ n $ bitów ma $ n $ -bitowy poziom bezpieczeństwa, przeszukiwanie klucza brutalnej siły. Kiedy przechodzimy do praktyki, atakujący nie są zobowiązani do przeszukiwania klucza brutalnej siły, a definicja „kroku” musi stać się liczbą podetapów porównywalnych pod względem liczby i kosztu obliczeniowego do podetapów wymaganych dla jednego wykonanie szyfru z nowym kluczem dla tekstu jawnego o rozmiarze klucza . Przy tej definicji praktyczny szyfr z kluczem $ n $ bitów ma co najwyżej $ n $ – bitowe bezpieczeństwo i dąży do tego ideału.

Kiedy przejdziemy do skrótów, definicja kroku może stać się liczbą podetapów porównywalnych pod względem liczby i kosztu obliczeniowego do wymaganych podetapów do haszowania nowej wiadomości rozmiaru wyjściowego skrótu .

Jednym z wielu problemów z powyższym jest to, że nie ma zgody co do tego, czy powinniśmy liczyć, czy nie, koszt pamięci i dostępów do pamięci w koszcie obliczeniowym. Bezpieczną rzeczą z punktu widzenia użytkownika jest nie liczenie tego, ale może to mieć ogromne znaczenie dla atakującego.

Definicja „kroków” staje się jeszcze bardziej niejasna, jeśli chodzi o kryptografię asymetryczną jak RSA.W teorii „kroki” mogą być jednym z obliczeń w strukturze algebraicznej używanej w kryptosystemie; na przykład dla RSA, jedna ocena mnożenia modularnego $ (a, b) \ mapsto a \, b \ bmod N $ dla dowolnej liczby całkowitej $ a $ i $ b $ w $ [0, N) $ , gdzie $ N $ to moduł publiczny. Ale są problemy z przeniesieniem tego do praktyki, szczególnie w przypadku RSA: najbardziej znanym atakiem jest uwzględnienie modułu publicznego $ N $ za pomocą GNFS , którego koszt obliczeniowy jest zdominowany przez operacje mające niewielkie podobieństwo do mnożenia modularnego, a koszt praktyczny jest zdominowany przez pamięć i dostęp do pamięci. To powoduje powrót do niejasnej definicji w TL; DR.

jak obliczyć czas ataku na ten 80-bitowy schemat kryptografii bezpieczeństwa, taki jak 80-bitowe zabezpieczenie RSA przy użyciu pewnego rodzaju procesora?

„80-bitowe zabezpieczenie RSA” nie jest rozumiane jako RSA z 80-bitowym publicznym moduł $ N $ , który jest ostatecznie niepewny. Gdybyśmy mieli rozmiar N $ N $ , moglibyśmy oszacować trudność na podstawie tego i wcześniejszego doświadczenia (patrz to i jej linki). Ale tego nie robimy i nie ma zgody co do rozmiaru $ N $ dla RSA z 80-bitowymi zabezpieczeniami: często podaje się 1024-bit, ale w zależności od hipotezy i kogo pytasz, to zdecydowanie za dużo lub za mało. Dlatego najlepiej zignorować, że mówimy o RSA i wrócić do: tyle czasu, ile potrzeba, aby złamać dobry szyfr symetryczny za pomocą 80-bitowego key.

Co prowadzi nas do: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Częstotliwość } \ times \ text {Number-of-CPUs}} $$ gdzie $ n $ to poziom bezpieczeństwa w bitach, $ k $ to oszacowanie liczby cykli procesora potrzebnych do oceny dobrego szyfru przy użyciu ultra-zoptymalizowanego algorytmu i $ p $ to szczątkowe prawdopodobieństwo sukcesu przeciwnika. W zależności od perspektywy możemy przyjąć $ k = 1 $ (co oszczędza analizowania szczegółów), $ k = 32 $ (ponieważ to wciąż mniej niż w najlepszych atakach na dobre szyfry przy użyciu komputera ogólnego przeznaczenia) lub znacznie więcej. W zależności od perspektywy możemy wziąć $ p = 1 $ (najbardziej ostrożny z punktu widzenia uprawnionego użytkownika), $ p = 1/2 $ (dając oczekiwany czas w przypadku szyfru blokowego) lub mniejszy $ p $ , jeśli zależy nam na marginesie bezpieczeństwa¹.

Na przykład z $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ approx2 ^ {- 10} $ , $ \ text {Frequency} = 4 \ text {GHz} \ około2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {Number-of-CPUs} = 1000 \ approx2 ^ {10} $ , otrzymujemy $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , czyli około 8 lat. Innymi słowy, nasze 1000 procesorów ma bardzo małe prawdopodobieństwo sukcesu w porównaniu z 80-bitowym symetrycznym krypto, dopóki nie staną się przestarzałe pod względem technicznym.

Z drugiej strony 1000 procesorów to niewielki ułamek procesory na całym świecie, a wydobywanie bitcoinów niezbicie pokazuje, że 80-bitowe kryptowaluty nie są już wystarczające dla przeciwników, którzy mają możliwość projektowania układów ASIC, budowania ich w ogromnych ilościach i utrzymywania kosztów energii potrzebnych do ich działania; zobacz to .

¹ Termin $ p $ w formuła jest najostrożniejsza z punktu widzenia uprawnionego użytkownika, ale powoduje, że $ \ text {Time} $ jest niedoceniany w wielu scenariuszach ataków. Na przykład w wyszukiwanie kolizyjne, poprawny termin byłby bardziej podobny do $ \ sqrt p $ .