Kryptografia post-kwantowa – nowy algorytm „zniknął w 60 minut”

Pisaliśmy o PQC, skrót od kryptografia post kwantowa, kilka razy wcześniej.

Jeśli przegapiłeś wszystkie medialne emocje z ostatnich kilku lat związane z tak zwanymi obliczeniami kwantowymi…

…jest to (jeśli wybaczysz to, co niektórzy eksperci prawdopodobnie uznają za lekkomyślne uproszczenie) sposób budowania urządzeń komputerowych, które mogą śledzić wiele możliwych wyników obliczenia w tym samym czasie.

Z dużą ostrożnością i być może odrobiną szczęścia oznacza to, że możesz przepisać niektóre rodzaje algorytmów, aby znaleźć właściwą odpowiedź, lub przynajmniej poprawnie odrzucić całą masę błędnych odpowiedzi, bez próbowania i testowania każdego możliwego wyniku jeden po drugim.

Przy użyciu kwantowego urządzenia obliczeniowego możliwe są dwa interesujące przyspieszenia kryptoanalityczne, przy założeniu, że da się zbudować odpowiednio potężne i niezawodne:

• Algorytm przeszukiwania kwantowego Grovera. Zwykle, jeśli chcesz przeszukać losowo uporządkowany zestaw odpowiedzi, aby sprawdzić, czy twoja znajduje się na liście, spodziewasz się, że w najgorszym przypadku przebrniesz przez całą listę, zanim uzyskasz ostateczną odpowiedź. Na przykład, jeśli chcesz znaleźć 128-bitowy klucz deszyfrujący AES do rozszyfrowania dokumentu, musisz przeszukać listę wszystkich możliwych kluczy, zaczynając od 000..001, ..2, ..3i tak dalej, aż do FFF..FFF (16 bajtów o wartości FF), aby mieć pewność, że problem zostanie rozwiązany. Innymi słowy, aby wypróbować wszystkie 2, musisz zaplanować budżet¹²⁸ możliwych kluczy przed znalezieniem właściwego klucza lub ustaleniem, że go nie było. Jednak algorytm Grovera, biorąc pod uwagę wystarczająco duży i potężny komputer kwantowy, twierdzi, że jest w stanie dokonać tego samego wyczynu za pomocą pierwiastek kwadratowy zwykłego wysiłku, tym samym złamanie kodu teoretycznie w zaledwie 2⁶⁴ zamiast tego próbuje.
• Algorytm faktoryzacji kwantowej Shora. Kilka współczesnych algorytmów szyfrowania opiera się na fakcie, że pomnożenie dwóch dużych liczb pierwszych można wykonać szybko, podczas gdy podzielenie ich produktu z powrotem na dwie liczby, od których zacząłeś, jest prawie niemożliwe. Aby to wyczuć, spróbuj pomnożyć 59×87 za pomocą pióra i papieru. Wydobycie go może zająć około minuty (5133 to odpowiedź), ale nie jest to takie trudne. Teraz spróbuj w drugą stronę. Podzielmy, powiedzmy, 4171 z powrotem na dwa czynniki. Dużo trudniej! (Ma 43×97). Teraz wyobraź sobie, że robisz to z liczbą o długości 600 cyfr. Mówiąc krótko, utknąłeś z próbą podzielenia 600-cyfrowej liczby przez każdą możliwą 300-cyfrową liczbę pierwszą, dopóki nie trafisz w dziesiątkę lub nie znajdziesz odpowiedzi. Algorytm Shora obiecuje jednak rozwiązać ten problem za pomocą logarytm zwykłego wysiłku. Tak więc rozłożenie na czynniki liczby 2048 cyfr binarnych powinno zająć tylko dwa razy dłużej niż rozłożenie na czynniki 1024-bitowej liczby, a nie dwa razy dłużej niż rozłożenie na czynniki 2047-bitowej liczby, co stanowi ogromne przyspieszenie.

Przeciwdziałanie zagrożeniu

Zagrożeniu ze strony algorytmu Grovera można przeciwdziałać, po prostu zwiększając rozmiar używanych liczb, podnosząc je do kwadratu, co oznacza podwojenie liczby bitów w hashu kryptograficznym lub kluczu szyfrowania symetrycznego. (Innymi słowy, jeśli uważasz, że SHA-256 jest teraz w porządku, użycie zamiast tego SHA-512 zapewniłoby alternatywę odporną na PQC.)

Ale algorytm Shora nie może być tak łatwo skontrowany.

Klucz publiczny o długości 2048 bitów wymagałby wykładniczego zwiększenia jego rozmiaru, nie tylko przez podniesienie do kwadratu, tak że zamiast klucza 2×2048=4096 bitów potrzebny byłby nowy klucz o niemożliwym rozmiarze 2²⁰⁴⁸ bity…

…albo musiałbyś przyjąć zupełnie nowy rodzaj post-kwantowego systemu szyfrowania, do którego algorytm Shora nie miał zastosowania.

Cóż, amerykański organ normalizacyjny NIST prowadzi a „Konkurs” PQC od końca 2017 r.

Proces był otwarty dla wszystkich, wszyscy uczestnicy byli mile widziani, wszystkie algorytmy zostały otwarcie opublikowane, a publiczna kontrola nie tylko możliwa, ale aktywnie zachęcany:

Zaproszenie do składania wniosków. [Zamknięte 2017]. […] Planuje się, że nowe standardy kryptografii z kluczem publicznym będą określać jeden lub więcej dodatkowych niesklasyfikowanych, publicznie ujawnianych podpisów cyfrowych, szyfrowania z kluczem publicznym i algorytmów ustanawiania kluczy, które są dostępne na całym świecie i są w stanie chronić poufne informacje rządowe daleko w dającej się przewidzieć przyszłości, w tym po pojawieniu się komputerów kwantowych.

Po trzech rundach zgłoszeń i dyskusji, Ogłoszono NIST, 2022, że wybrał cztery algorytmy, które uznał za „standardy” ze skutkiem natychmiastowym, wszystkie o rozkosznie brzmiących nazwach: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, SPHINCS+.

Pierwszy (CRYSTALS-KYBER) jest używany jako tak zwany a Kluczowy mechanizm uzgadniania (KEM), gdzie dwa końce publicznego kanału komunikacji bezpiecznie wymyślają jednorazowy prywatny klucz szyfrowania do poufnej wymiany danych sesji. (Po prostu: węszący po prostu dostają posiekaną kapustę, aby nie mogli podsłuchiwać rozmowy.)

Pozostałe trzy algorytmy są wykorzystywane do Podpisy cyfrowe, dzięki czemu możesz upewnić się, że dane, które otrzymałeś, odpowiadają dokładnie tym, które nadawca umieścił po drugiej stronie, zapobiegając w ten sposób manipulacjom i zapewniając integralność. (Po prostu: jeśli ktoś spróbuje zepsuć lub zepsuć dane, będziesz wiedział.)

Potrzeba więcej algorytmów

W tym samym czasie ogłaszając nowe standardy, NIST ogłosił również czwarta runda konkurencji, przedstawiając kolejne cztery algorytmy jako możliwe alternatywne KEM. (Pamiętaj, że w chwili pisania tego tekstu mamy już do wyboru trzy zatwierdzone algorytmy podpisu cyfrowego, ale tylko jeden oficjalny KEM).

One były: BIKE, Classic McEliece, HQC i SIKE.

Co ciekawe, Algorytm McElice został wynaleziony w latach 1970. przez amerykańskiego kryptografa Roberta Mc Eliece, który zmarł w 2019 roku, długo po tym, jak konkurs NIST był już w toku.

Jednak nigdy się nie przyjął, ponieważ wymagał ogromnych ilości kluczowego materiału w porównaniu z popularną alternatywą dnia, algorytmem Diffie-Hellman-Merkle (DHM, a czasem po prostu DH).

Niestety, jeden z trzech algorytmów rundy czwartej, a mianowicie SIKE, wydaje się, że został złamany.

W oszałamiającym artykule zatytułowanym EFEKTYWNY ATAK Z ODZYSKIWANIEM KLUCZA NA SIDH (WERSJA WSTĘPNA), belgijscy kryptografowie Wouter Castryk i Thomas Decru wydają się zadać śmiertelny cios algorytmowi SIKE

Jeśli się zastanawiasz, SIKE to skrót od Enkapsulacja klucza izogenicznego w liczbie nadosobniczej, a SIDH oznacza Izogenia nadliczbowa Diffie-Hellman, szczególne zastosowanie Algorytm SIKE przy czym dwa końce kanału komunikacyjnego wykonują podobną do DHM „kryptodance” w celu wymiany zbioru danych publicznych, która pozwala każdemu z końców uzyskać prywatną wartość do wykorzystania jako jednorazowy tajny klucz szyfrujący.

Nie będziemy tutaj próbować wyjaśniać ataku; powtórzymy tylko to, co twierdzi gazeta, a mianowicie, że:

Mówiąc bardzo luźno, dane wejściowe tutaj obejmują dane publiczne dostarczone przez jednego z uczestników kryptotanie ustanawiania klucza, wraz z wcześniej określonymi (a zatem publicznie znanymi) parametrami używanymi w procesie.

Ale wyodrębnione dane wyjściowe (informacje określane jako izogenia φ powyżej) ma być nigdy nieujawnianą częścią procesu – tzw. kluczem prywatnym.

Innymi słowy, z samych informacji publicznych, takich jak dane wymieniane otwarcie podczas konfiguracji klucza, kryptografowie twierdzą, że są w stanie odzyskać klucz prywatny jednego z uczestników.

A kiedy znasz mój klucz prywatny, możesz łatwo i niewykrywalnie udawać mnie, więc proces szyfrowania jest zepsuty.

Najwyraźniej algorytm łamania klawiszy potrzebuje około godziny, aby wykonać swoją pracę, używając tylko jednego rdzenia procesora o mocy obliczeniowej, jaką można znaleźć w zwykłym laptopie.

Jest to sprzeczne z algorytmem SIKE, gdy jest skonfigurowany tak, aby spełniał poziom 1, podstawowy poziom bezpieczeństwa szyfrowania NIST.

Co robić?

Nic!

(To dobra wiadomość.)

Jak sugerują autorzy artykułu, po stwierdzeniu, że ich wynik jest jeszcze wstępny, „przy obecnym stanie rzeczy wydaje się, że SIDH jest całkowicie złamany dla każdej publicznie generowanej krzywej bazowej”.

(To zła wiadomość.)

Jednak biorąc pod uwagę, że algorytm SIKE nie został jeszcze oficjalnie zatwierdzony, można go teraz albo dostosować, aby udaremnić ten konkretny atak (coś, co autorzy przyznają, że jest możliwe), albo po prostu całkowicie zrezygnować.

Cokolwiek w końcu stanie się z SIKE, jest to doskonałe przypomnienie, dlaczego próba wymyślenia własnych algorytmów szyfrowania jest obarczona niebezpieczeństwem.

To także doskonały przykład tego, dlaczego zastrzeżone systemy szyfrowania które polegają na tajności samego algorytmu utrzymanie ich bezpieczeństwa jest po prostu niedopuszczalne w 2022 roku.

Gdyby algorytm PQC, taki jak SIKE, przetrwał percepcję i sondowanie przez ekspertów z całego świata przez ponad pięć lat, mimo że został ujawniony specjalnie po to, aby mógł zostać poddany publicznej kontroli…

…wtedy nie ma potrzeby zadawać sobie pytania, jak dobrze poradzą sobie Twoje domowe, ukryte algorytmy szyfrowania, gdy zostaną wypuszczone na wolność!

---