Ile czasu zajmie złamanie 1024-bitowego szyfrowanego e-maila OpenPGP?


9

W przypadku WPA istnieją kalkulatory określające czas potrzebny na złamanie hasła, ale nie znalazłem nic dla OpenPGP.

Ile czasu zajmie złamanie 1024-bitowego szyfrowanego e-maila OpenPGP (w zależności od mocy procesora)?

Interesują mnie również inne rozmiary klawiszy, takie jak 2048 i 4096.

Odpowiedzi:


7

Podczas gdy odpowiedź @Jensa Erata była dość wyczerpująca, badałem łamanie RSA (algorytm OpenPGP), więc chciałem wybrać:

Złamię normę i najpierw dam TL; DR: Niemożliwe jest złamanie tego klucza. Jeśli spojrzymy na to realistycznie, nie ma sposobu na uwzględnienie 1024-bitowej liczby całkowitej. Najlepszym możliwym zakładem byłoby zerwanie z inną częścią łańcucha bezpieczeństwa (np. Pulpit, na którym odbiorca sprawdza pocztę e-mail).

Po usunięciu realizmu zastanówmy się nad możliwymi strategiami:

  • Ślepe zgadywanie / brutalne zmuszanie. Przy 1024-bitowym semiprime istnieje małe prawdopodobieństwo, że to kiedykolwiek zadziała. Lepiej byłoby wykorzystać swój czas losowo, próbując odgadnąć numery loterii.

  • Generowanie tęczowego stołu. Usuń zgadywanie z faktorowania, biorąc każdą liczbę pierwszą poniżej 2 ^ 1024 i mnożąc ją przez każdą inną liczbę pierwszą, przechowując wynik w tabeli. Następnie wystarczy wyszukać poprawną parę. Jak możesz sobie wyobrazić, to też jest niemożliwe. Wymagałoby to x! pary dla liczby x liczb pierwszych. Dzięki funkcji zliczania liczb pierwszych patrzysz na około 2,95 * 10 ^ 307 liczb pierwszych - dla porównania szacuje się, że liczba atomów w obserwowalnym wszechświecie wynosi 10 ^ 83, więc nawet gdybyśmy mogli sprawienie, by każdy atom zapisał dwie liczby pierwsze i ich produkt w sposób, w jaki nasz komputer mógłby indeksować, byłoby niemożliwe.

  • Użyj sita z polem liczb ogólnych . GNFS jest najlepszym rozwiązaniem do faktorowania dużego semiprime. Został wykorzystany przez Kleinjunga i jego zespół do uwzględnienia RSA-768, 768-bitowego semiprime. Niestety, zajęło to jego zespołowi ponad trzy lata i jest to rząd wielkości mniejszy niż liczby, które chcesz uwzględnić. Nawet gdybyś wydał miliony dolarów (dziennie), wynajmując najlepsze superkomputery na pełnej mocy, obliczenie tej liczby byłoby prawie niemożliwe. Pierwszym krokiem GNFS jest znalezienie wystarczającej liczby „relacji”, które pozwolą na rozwiązanie podproblemów, co może zająć bardzo dużo czasu.

Ostatnią deską ratunku jest użycie komputera kwantowego, który pozwoliłby ci wyliczyć liczby w możliwym czasie. Niestety, należy je jeszcze opracować do pewnego stopnia użyteczności. Na razie nie możemy więc brać pod uwagę 1024-bitowych i większych liczb półpierwszych (a więc algorytmów, które na nich polegają).


20

Po pierwsze, zakładam, że mówisz o 1024-bitowym szyfrowaniu RSA.

Ogólnie rzecz biorąc, temat jest zbyt skomplikowany, aby podać prosty numer.

tl; dr : Złamanie zaszyfrowanej wiadomości OpenPGP na jednym procesorze nie jest możliwe i prawdopodobnie zajmuje lata nawet przy dużych klastrach obliczeniowych. Jednak nieznane (dla opinii publicznej) wady matematyczne mogą to zmienić o rząd wielkości, tak jak w przyszłości komputery kwantowe (z daleka, z punktu widzenia „epoki Internetu”).

Nieco dłuższa wersja:

Złamanie szyfrowania asymetrycznego (klucz RSA 1024-bitowy)

Oprócz 1024 bitowych kluczy RSA dotyczy to także większych rozmiarów kluczy. Większe klucze zapewniają większe bezpieczeństwo (w postaci mocy obliczeniowej do ich złamania), ale pamiętaj, że bezpieczeństwo nie wzrasta liniowo wraz z wielkością klucza.

Na giełdzie stosów zabezpieczeń informacji znajduje się ładny post: „Jak oszacować czas potrzebny na złamanie szyfrowania RSA?” , która nie kończy się oszacowaniem typu „Używając modelu Core i7 xy, będziesz w stanie złamać klucz RSA 1024-bitowy w szacowanych godzinach z”, ale odpowiedzi są zgodne, że „Klucze 1024-bitowe RSA nie mogą zostać złamane przez pojedyncze osoby z zwykle dostępną mocą obliczeniową (tj. garstką wysokiej klasy maszyn) w rozsądnym czasie.

Dyskusja na temat łamania 1024-bitowych kluczy przy znacznie większej mocy obliczeniowej była rozważana tylko z akademickiego punktu widzenia:

Niedawno dowiedziałem się, że rozpoczął się wybór parametrów dla faktoryzacji liczb 1024-bitowych (to jest część „rozgarnięta”); przesiewanie jest technicznie wykonalne (będzie kosztowne i wymagać lat obliczeniowych na wielu klastrach uniwersyteckich), ale na razie nikt nie wie, jak wykonać liniową część redukcji dla 1024-bitowej liczby całkowitej. Nie spodziewaj się więc w najbliższym czasie 1024-bitowej przerwy.

Prawdopodobnie dotyczy to również dużych, dobrze finansowanych instytucji o dużej mocy obliczeniowej, takich jak NSA.

Wszystko może się szybko zmienić, jeśli

  • ktoś odkrył matematyczną wadę, która zmniejsza złożoność RSA o rzędy wielkości (niektóre instytucje, takie jak NSA, zatrudniają ogromną liczbę wielkich matematyków), lub
  • komputery kwantowe wreszcie działają i stają się wystarczająco potężne i potrafią uruchamiać określone algorytmy. Nie przewiduje się wystąpienia w ciągu najbliższych kilku lat.

W przypadku DSA / ElGamal sprawy wyglądają nieco inaczej. Klucz DSA o tym samym rozmiarze co klucz RSA zapewnia większe bezpieczeństwo, ale jednocześnie DSA jest bardziej podatny na złe liczby losowe (porównaj z wadą generatora liczb losowych Debiana ). Kryptografia krzywej eliptycznej, która ma się teraz pojawić w OpenPGP, nie ma jeszcze znanych ataków na algorytmy obsługiwane i ogólnie uważanych za bezpieczne, ale są pewne wątpliwości, szczególnie w przypadku krzywych zalecanych przez NIST (NIST straciła dość reputację za zrobienie zepsutego losowego generator liczb w standardzie), a niektóre nitpicks implementacji.

Złamanie szyfrowania symetrycznego

Ze względu na wydajność OpenPGP wykorzystuje szyfrowanie hybrydowe, dlatego wiadomość jest szyfrowana za pomocą szyfrowania symetrycznego i losowego klucza symetrycznego (w OpenPGP, często nazywanego „kluczem sesji”). Ten klucz sesji jest ponownie szyfrowany przy użyciu algorytmu szyfrowania asymetrycznego, np. RSA.

Jeśli jesteś w stanie złamać symetryczny klucz szyfrujący wiadomości, możesz również przeczytać wiadomość (w przeciwieństwie do złamania klucza asymetrycznego, w którym możesz odczytać wszystkie wiadomości zaszyfrowane tym kluczem).

W przeciwieństwie do bardzo wczesnych wersji PGP (które używały algorytmu szyfrowania symetrycznego zaprojektowanego przez samego Zimmermanna, zwanego BassOmatic , który jest uważany za uszkodzony), wszystkie algorytmy symetryczne zdefiniowane dla OpenPGP nie mają odpowiednich znanych ataków.

Chyba że ktoś zdecyduje się nie używać szyfrowania symetrycznego (co jest faktycznie możliwe!), Złamanie wiadomości przy użyciu algorytmu szyfrowania symetrycznego nie powinno być w tej chwili uważane za wykonalne.


Muszę zapytać ... czy błąd w pisowni słowa „asymetryczny” jest zamierzony?
David Z

Nie, oczywiście że nie; nie było też „copmuting”. Dziękuję za powiadomienie mnie.
Jens Erat

Nie ma czegoś takiego jak „klucz DES tego samego rozmiaru co klucz RSA”. DES używa 56-bitowych kluczy, kropka . Jest zdefiniowany tylko za pomocą 56-bitowych kluczy; nie można uruchomić DES z żadnym innym kluczem. Nie jest również podatny na złe liczby losowe, ponieważ DES nie używa liczb losowych w żadnym punkcie algorytmu (podobnie jak inne prymitywy szyfrów blokowych); jego szczególne zastosowania mogą obejmować aspekt losowy (np. IV dla trybu CBC musi być losowy), ale sam DES jest w pełni deterministyczny. DES również nie jest już używany (czasami potrójny DES, ale sam DES nigdy). Czy na pewno chcesz porozmawiać o DES?
cpast

Oczywiście, że nie chciałem. Pomylenie DES z DSA nie powinno się zdarzyć. DES, PGP, RSA, NSA, DSA: Potrzebujemy mniej trzyliterowych skrótów!
Jens Erat

Podobno większość 1024-bitowych kluczy openpgp (w przeciwieństwie do kluczy ssl / tls) to DSA, a nie RSA. Znajduję mnóstwo dyskusji online na temat łamania 1024-bitowego RSA, ale niewiele na temat łamania 1024-bitowego DSA.
plugwash
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.