SIDH i SIKE: projekt i kryptoanaliza

Supersingular Isogeny Diffie-Hellman (SIDH), zaproponowany przez Jao i De Feo w 2011 roku, jest protokołem wymiany kluczy publicznych analogicznym do Diffiego–Hellmana, ale wykorzystującym izogenie na supersingularnych krzywych eliptycznych. Obie strony rozpoczynają od tej samej supersingularnej krzywej E nad Fp2. Alicja oblicza tajną izogenię phi_A: E -> E_A (z losowym jądrem w 2^a-torsion), a następnie publikuje E_A oraz obrazy generatorów grupy torsyjnej Boba względem phi_A. Bob oblicza phi_B: E -> E_B (z losowym jądrem w 3^b-torsion), a następnie publikuje E_B oraz obrazy generatorów grupy torsyjnej Alicji względem phi_B. Alicja używa opublikowanych przez Boba danych, aby obliczyć phi_A': E_B -> E_AB; Bob oblicza phi_B': E_A -> E_AB. Oboje otrzymują j(E_AB) jako wspólny sekret.

Specjalna postać liczby pierwszej w SIDH, p = 2^a * 3^b * f - 1 (f jest małym współczynnikiem dopełniającym używanym przy sprawdzaniu pierwszości), zapewnia, że krzywa E nad Fp2 ma wymaganą strukturę grup torsyjnych. Dla SIKEp434 (poziom 1 NIST, 128-bitowe bezpieczeństwo postkwantowe): p = 2^216 * 3^137 - 1, a = 216, b = 137. Oznacza to, że Alicja wykonuje 216 kroków izogenii stopnia 2, a Bob wykonuje 137 kroków izogenii stopnia 3. Rozmiary kluczy: klucz publiczny Alicji obejmuje E_A oraz dwa punkty Fp2 (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 bajty. SIKEp751 zapewnia 192-bitowe bezpieczeństwo klasyczne / 128-bitowe bezpieczeństwo kwantowe i ma klucze publiczne o rozmiarze 564 bajtów. Są to najmniejsze klucze publiczne spośród wszystkich kandydatów NIST PQC — kosztem szybkości mniejszej 100–1000 razy.

SIKE (Supersingular Isogeny Key Encapsulation) jest bezpiecznym w modelu IND-CCA2 mechanizmem KEM zbudowanym na bazie SIDH przy użyciu transformacji Fujisakiego–Okamoto. SIKE.Encaps: wybiera losową wiadomość m, oblicza (c0 = SIDH public key with seed m, c1 = H2(m) XOR pk) i wysyła (c0, c1). SIKE.Decaps: odzyskuje m z c0 przy użyciu klucza tajnego, weryfikuje c1, ponownie oblicza (c0, c1), aby sprawdzić spójność, i zwraca K = H3(m, c0). Transformacja FO przekształca wymianę SIDH bezpieczną w modelu CPA w bezpieczny w modelu CCA2 mechanizm KEM. SIKE uczestniczył we wszystkich czterech rundach konkursu NIST PQC (2017–2022), przechodząc rozległą analizę kryptograficzną — aż do pojawienia się w lipcu 2022 roku wyniszczającego ataku klasycznego.

W latach 2011–2022 SIDH odpierał znaczne wysiłki kryptoanalityczne. Najlepiej znane ataki na SIDH obejmowały: (1) ogólny algorytm SSIP: O(p^{1/4}) klasycznie, O(p^{1/6}) kwantowo przy użyciu algorytmu Taniego. (2) Atak spotkania pośrodku na ścieżkę izogenii: O(p^{1/4}) klasycznie, tak samo jak SSIP. (3) Algorytmy wielomianowe dla określonych ataków wykorzystujących strukturę (van Oorschot–Wiener): nie mają zastosowania do SIDH. Dziesiątki artykułów analizowały bezpieczeństwo SIDH i przez 11 lat nie znaleziono żadnego wielomianowego ataku klasycznego ani kwantowego. Ta historia sprawiła, że SIKE stał się wiarygodnym finalistą konkursu NIST. Ostateczne złamanie nie nastąpiło w wyniku bezpośredniego ataku na SSIP, lecz przez wykorzystanie informacji o pomocniczych punktach torsyjnych SIDH.

30 lipca 2022 roku Wouter Castryck i Thomas Decru opublikowali preprint pokazujący wielomianowy klasyczny atak na SIDH. Atak wykorzystuje dodatkowe informacje zawarte w pomocniczych punktach torsyjnych SIDH phi_A(P_B), phi_A(Q_B): informacje te zasadniczo ujawniają działanie phi_A na podgrupie 3^b-torsion. W połączeniu z krzywą obrazową E_A umożliwia to odtworzenie jądra phi_A (a tym samym samej phi_A) przy użyciu technik z teorii krzywych eliptycznych z mnożeniem zespolonym oraz izogenii Richelota. Atak został wykonany w 62 minuty na laptopie dla SIKEp434 — zestawu parametrów, który miał zapewniać 128-bitowe bezpieczeństwo postkwantowe. W ciągu kilku dni niezależni badacze potwierdzili atak i rozszerzyli go na wszystkie parametry SIDH.

Projekt SIDH wymagał, aby obie strony publikowały obrazy bazowych punktów torsyjnych drugiej strony względem swojej tajnej izogenii. Było to konieczne do działania protokołu: bez phi_A(P_B) i phi_A(Q_B) Bob nie mógł przenieść swojej izogenii na krzywą Alicji, aby obliczyć wspólny sekret. Jednak ta dodatkowa informacja — ujawniająca działanie phi_A ograniczone do 3^b-torsion — okazała się katastrofalnie obszerniejsza, niż oczekiwano. Atak Castrycka–Decru wykorzystuje krzywe rodzaju 2 (izogenie Richelota), aby przenieść problem na obiekty wyższego rodzaju, gdzie działanie ograniczone całkowicie wyznacza phi_A. Ten wyciek informacji ma charakter strukturalny dla SIDH i nie można go naprawić bez zmiany fundamentalnego projektu protokołu.

5 lipca 2022 roku (przed atakiem Castrycka–Decru) NIST ogłosił wstępne wybory dotyczące standaryzacji PQC: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+) oraz FN-DSA (Falcon) — SIKE nie znalazł się wśród nich (był rozpatrywany w drugiej rundzie). Atak Castrycka–Decru z lipca 2022 roku doprowadził do formalnego całkowitego wyeliminowania SIKE z dalszych rozważań przez NIST. NIST oświadczył: "SIKE is no longer under consideration for standardization." Był to najbardziej spektakularny rozwój kryptoanalityczny w konkursie NIST PQC, pokazujący, że nawet schemat, który przetrwał 11 lat analiz, może zostać złamany dzięki fundamentalnie nowemu odkryciu matematycznemu.

W ciągu tygodnia od ataku Castrycka–Decru Thomas Decru i Luciano Maino (niezależnie od siebie), a później Damien Robert, opublikowali dalsze usprawnienia. Wariant ataku Roberta wykorzystuje tę samą obserwację, ale oblicza pierścień endomorfizmów E_A zamiast bezpośrednio obliczać jądro izogenii, i można go uznać za prostszy w opisie matematycznym. Te szybkie, niezależne ponowne odkrycia potwierdziły, że atak Castrycka–Decru ujawnił fundamentalną słabość strukturalną, a nie nieoczywistą sztuczkę. Tempo publikacji kolejnych artykułów odzwierciedlało również fakt, że wielu badaczy analizowało wyciek informacji z punktów torsyjnych SIDH jako potencjalny wektor ataku. Zdawali sobie sprawę, że było to nietypowe ujawnienie informacji, lecz nie potrafili go wykorzystać, dopóki Castryck i Decru nie znaleźli przejścia przez krzywe rodzaju 2.

FESTA (Fast Encryption from Supersingular Torsion Attacks, 2023) to projekt mechanizmu KEM inspirowany przez SIDH, który unika pomocniczych danych o punktach torsyjnych. FESTA wykorzystuje inną strukturę protokołu: klucz publiczny nie zawiera obrazów bazowych punktów torsyjnych drugiej strony — zamiast tego tajna izogenia jest uwierzytelniana wyłącznie za pomocą krzywej obrazowej (bez punktów pomocniczych). FESTA szyfruje przy użyciu izogenii w sposób ujawniający mniej informacji strukturalnych. Wstępna analiza bezpieczeństwa sugeruje, że FESTA unika struktury ataku Castrycka–Decru. FESTA jest jednak nowszy i został poddany mniejszej liczbie analiz niż SIKE w ciągu jego 11-letniej historii, dlatego społeczność zajmująca się izogeniami ostrożnie podchodzi do wdrażania nowych schematów przed przeprowadzeniem ich rozległej analizy.

Złamanie SIKE dostarcza ważnych wniosków. (1) Ujawnianie informacji pomocniczych jest niebezpieczne: dodatkowe dane o punktach torsyjnych w SIDH były konieczne do działania protokołu, ale doprowadziły do wycieku informacji umożliwiającego jego złamanie. Projektanci protokołów muszą analizować każdy fragment publikowanych danych, a nie tylko główne wartości. (2) Historia analiz nie jest dowodem bezpieczeństwa: 11 lat bez znanego ataku daje pewność, ale nie stanowi gwarancji. Dowody kryptograficzne (redukcja do dobrze zdefiniowanego trudnego problemu) są bardziej wiarygodne niż argument oparty na autorytecie lub samym przetrwaniu kontroli. (3) Nowe narzędzia matematyczne wiążą się z ryzykiem: atak Castrycka–Decru wykorzystał izogenie Richelota krzywych rodzaju 2 — narzędzie matematyczne, którego wcześniej nie stosowano w kryptoanalizie izogenii. Kryptoanalitycy badający nowe prymitywy muszą uwzględniać nowe dziedziny matematyki.

Pomimo złamania SIKE kryptografia oparta na izogeniach nadal jest aktywną dziedziną badań. Podpisy SQISign (177 bajtów na poziomie 1) pozostają najbardziej kompaktowymi znanymi podpisami PQC i wykorzystują inne założenie dotyczące trudności problemu (problem pierścienia endomorfizmów), na które nie ma wpływu atak na SIDH. Protokoły oparte na CSIDH wykorzystują strukturę działania grupy klas (przemienne izogenie) i nie ujawniają informacji z punktów torsyjnych, choć CSIDH mierzy się z własnymi wyzwaniami (jest wolniejszy niż SIDH przed atakiem, a analiza bezpieczeństwa kwantowego nadal trwa). Społeczność zajmująca się izogeniami postrzega złamanie SIKE jako doświadczenie, które pogłębiło wiedzę o tym, jakie informacje należy ukrywać w protokołach wykorzystujących izogenie — jest to cenna wiedza przy projektowaniu przyszłych schematów.

SIDH wykorzystuje naprzemienne łańcuchy izogenii 2^a i 3^b między dwiema stronami, udostępniając obrazy pomocniczych punktów torsyjnych w celu umożliwienia wymiany kluczy. SIKE opakowuje SIDH transformacją Fujisakiego–Okamoto, zapewniając bezpieczeństwo CCA2. SIKE miał najmniejsze klucze spośród wszystkich kandydatów NIST PQC (374 bajty), ale był 100–1000 razy wolniejszy. Po 11 latach analiz bezpieczeństwa Castryck i Decru złamali SIKE w lipcu 2022 roku, wykorzystując izogenie Richelota krzywych rodzaju 2 do wykorzystania wycieku informacji z punktów torsyjnych. NIST wyeliminował SIKE. FESTA unika ujawniania informacji o punktach torsyjnych. SQISign nadal wykorzystuje trudność problemu pierścienia endomorfizmów. Złamanie SIKE pokazuje, że pomocniczne dane publiczne należy analizować równie starannie jak podstawowe wartości protokołu.