Gdyby dzisiejsze protokoły kryptograficzne zawiodły, niemożliwe byłoby zabezpieczenie połączeń online — wysyłanie poufnych wiadomości, dokonywanie bezpiecznych transakcji finansowych czy uwierzytelnianie danych. Każdy mógł uzyskać dostęp do wszystkiego; każdy mógł udawać, że jest kimkolwiek. Gospodarka cyfrowa upadnie.
Kiedy (lub if) staje się dostępny w pełni funkcjonalny komputer kwantowy, a to właśnie może się zdarzyć. W rezultacie w 2017 r. Narodowy Instytut Standardów i Technologii (NIST) rządu USA ogłosił międzynarodowy konkurs na znalezienie najlepszych sposobów na osiągnięcie kryptografii „post-kwantowej”.
W zeszłym miesiącu agencja wybrała pierwszą grupę zwycięzców: cztery protokoły, które z pewnymi zmianami zostaną wdrożone jako tarcza kwantowa. Zapowiedział również czterech dodatkowych kandydatów, którzy są nadal rozważani.
Następnie 30 lipca para badaczy ujawniła, że: złamał jednego z tych kandydatów w godzinę na laptopie. (Od tego czasu inni jeszcze bardziej przyspieszyli atak, łamiąc protokół w ciągu kilku minut.) „Atak, który jest tak dramatyczny i potężny… był nie lada szokiem” – powiedział. Stevena Galbraitha, matematyk i informatyk na Uniwersytecie Auckland w Nowej Zelandii. Nie tylko matematyka leżąca u podstaw ataku była zaskakująca, ale zmniejszyła (bardzo potrzebną) różnorodność kryptografii post-kwantowej – eliminując protokół szyfrowania, który działał zupełnie inaczej niż ogromna większość schematów w konkursie NIST.
„To trochę wpadka”, powiedział Krzysztof Peikert, kryptograf z Uniwersytetu Michigan.
Wyniki wprawiły społeczność kryptografii post-kwantowej zarówno w szok, jak i zachętę. Wstrząśnięty, ponieważ ten atak (i kolejny z poprzedniej rundy konkursu) nagle zmienił coś, co wyglądało jak cyfrowe stalowe drzwi w mokrą gazetę. „To wyszło znikąd”, powiedział Dustina Moody'ego, jeden z matematyków prowadzących prace normalizacyjne NIST. Ale jeśli schemat kryptograficzny ma się zepsuć, najlepiej, jeśli stanie się to na długo przed użyciem go na wolności. „Jest wiele emocji, które przez ciebie przechodzą”, powiedział Dawid Jao, matematyk z University of Waterloo w Kanadzie, który wraz z badaczem IBM Luca De Feo, zaproponował protokół w 2011 roku. Z pewnością wśród nich są zaskoczenie i rozczarowanie. - Ale także - dodał Jao - przynajmniej teraz się zepsuł.
Sekretne spacery wśród zakrętów
Jao i De Feo dostrzegli okazję do stworzenia systemu kryptograficznego, który byłby zarówno podobny, jak i odpowiednio odmienny od znanych protokołów. Ich schemat, nazwany protokołem nadsingularnej izogenii Diffie-Hellmana (SIDH), dotyczył krzywych eliptycznych — tych samych obiektów matematycznych używanych w jednym z najbardziej rozpowszechnionych obecnie rodzajów kryptografii. Ale wykorzystał je w zupełnie inny sposób. Był to również najbardziej zwarty program, jaki rozważał NIST (z kompromisem, że był wolniejszy niż wielu innych kandydatów).
I „matematycznie to jest naprawdę eleganckie”, powiedział Jao. „W tamtym czasie wydawało się to pięknym pomysłem”.
Powiedzmy, że dwie strony, Alice i Bob, chcą potajemnie wymienić wiadomość, nawet pod czujnym okiem potencjalnego napastnika. Rozpoczynają się od zbioru punktów połączonych krawędziami, zwanego grafem. Każdy punkt reprezentuje inną krzywą eliptyczną. Jeśli możesz przekształcić jedną krzywą w drugą w określony sposób (za pomocą mapy zwanej izogenią), narysuj krawędź między parą punktów. Powstały wykres jest ogromny i łatwo się w nim zgubić: jeśli przejdziesz stosunkowo krótki spacer wzdłuż jego krawędzi, znajdziesz się w miejscu, które wygląda zupełnie losowo.
Wykresy Alicji i Boba mają wszystkie te same punkty, ale krawędzie są różne — są definiowane przez różne izogenie. Alicja i Bob zaczynają w tym samym punkcie i każdy z nich przeskakuje wzdłuż losowych krawędzi na własnym wykresie, śledząc swoją ścieżkę z jednego punktu do drugiego. Każdy następnie publikuje swoją końcową lokalizację, ale zachowuje swoją ścieżkę w tajemnicy.
Teraz zamieniają się miejscami: Alice idzie do ostatniego punktu Boba, a Bob do Alice. Każdy powtarza swój sekretny spacer. Robią to w taki sposób, że oboje skończą w tym samym punkcie.
Ta lokalizacja została znaleziona w tajemnicy, więc Alicja i Bob mogą używać jej jako swojego tajnego klucza — informacji, która pozwala im bezpiecznie szyfrować i odszyfrowywać swoje wiadomości. Nawet jeśli atakujący widzi punkty pośrednie, które Alicja i Bob wysyłają sobie nawzajem, nie zna sekretnego spaceru Alicji lub Boba, więc nie może ustalić tego końcowego punktu końcowego.
Ale aby SIDH zadziałało, Alice i Bob muszą również wymienić kilka dodatkowych informacji o swoich spacerach. Te dodatkowe informacje doprowadziły do upadku SIDH.
Nowy zwrot w starej matematyce
Tomasz Decru nie zamierzał złamać SIDH. Próbował na tym bazować — uogólnić metodę w celu ulepszenia innego rodzaju kryptografii. To nie wyszło, ale podsunęło pomysł: jego podejście może być przydatne do atakowania SIDH. I tak się zbliżył Wouter Castryck, jego kolega z Katolickiego Uniwersytetu w Leuven w Belgii i jeden z jego byłych doktorantów, i obaj zagłębili się w odpowiednią literaturę.
Natknęli się na artykuł opublikowany przez matematyka Ernsta Kani w 1997 roku. Było to twierdzenie, które „niemal natychmiast miało zastosowanie do SIDH”, powiedział Castryck. „Myślę, że kiedy zdaliśmy sobie sprawę, że… atak nastąpił dość szybko, w ciągu jednego lub dwóch dni”.
Ostatecznie, aby odzyskać sekretny spacer Alicji (a tym samym wspólny klucz), Castryck i Decru zbadali iloczyn dwóch krzywych eliptycznych — krzywej początkowej Alicji i krzywej, którą wysłała publicznie do Boba. Ta kombinacja tworzy rodzaj powierzchni zwanej powierzchnią abelową. Następnie wykorzystali te powierzchnie abelowe, twierdzenie Kaniego (które łączy powierzchnie abelowe z krzywymi eliptycznymi) oraz dodatkowe informacje, które Alicja dała Bobowi, aby odkryć każdy krok, który zrobiła Alicja.
„To prawie jak sygnał naprowadzający, który pozwala namierzyć [niektóre powierzchnie abelowe]” – powiedział Jao. „I ten sygnał mówi ci, że to jest droga, którą powinieneś iść, aby zrobić kolejny krok, aby znaleźć właściwy [sekretny spacer]”. Co doprowadziło ich prosto do wspólnego klucza Alice i Boba.
„To bardzo nieoczekiwane podejście, przechodzenie do bardziej skomplikowanych obiektów w celu uzyskania wyników dotyczących prostszego obiektu” – powiedział Jao.
„Byłem bardzo podekscytowany, widząc, jak ta technika jest używana”, powiedział Krystyna Lauter, matematyk i kryptograf w Meta AI Research, który nie tylko pomógł opracować kryptografię opartą na izogenii, ale także pracował na powierzchniach abelowych. „Wstydź się więc, że nie myślałem o tym jako o sposobie na złamanie tego”.
Atak Castrycka i Decru złamał wersję protokołu SIDH o najniższym poziomie bezpieczeństwa w ciągu 62 minut, a najwyższy poziom bezpieczeństwa w niecały dzień. Niedługo potem inny ekspert zmodyfikował atak tak, że złamanie wersji o niskim poziomie bezpieczeństwa zajęło zaledwie 10 minut, a złamanie wersji o wysokim poziomie bezpieczeństwa zajęło kilka godzin. Bardziej ogólne ataki opublikowane w ciągu ostatnich kilku tygodni sprawiają, że jest mało prawdopodobne, że SIDH może zostać uratowany.
„To było wyjątkowe uczucie”, powiedział Castryck, choć słodko-gorzkie. „Zabiliśmy jeden z naszych ulubionych systemów”.
Chwila rozlewiska
Nie można zagwarantować, że system jest bezwarunkowo bezpieczny. Zamiast tego kryptografowie polegają na upływającym wystarczająco dużo czasu i wystarczającej liczbie osób próbujących rozwiązać problem, aby poczuć się pewnie. „To nie znaczy, że nie obudzisz się jutro i odkryjesz, że ktoś znalazł do tego nowy algorytm” – powiedział. Jeffreya Hoffsteina, matematyk na Brown University.
Dlatego właśnie konkursy takie jak NIST są tak ważne. W poprzedniej rundzie konkursu NIST Ward Beullens, kryptograf w IBM, wymyślił atak, który złamał schemat o nazwie Rainbow w weekend. Podobnie jak Castryck i Decru, był w stanie przeprowadzić atak dopiero po tym, jak spojrzał na leżący u jego podstaw problem matematyczny pod innym kątem. I podobnie jak atak na SIDH, ten złamał system, który opierał się na innej matematyce niż większość proponowanych protokołów post-kwantowych.
„Ostatnie ataki były przełomowym momentem” – powiedział Thomas Perst, kryptograf w startupie PQShield. Podkreślają, jak trudna jest kryptografia post-kwantowa i jak wiele analiz może być potrzebnych do zbadania bezpieczeństwa różnych systemów. „Obiekt matematyczny może nie mieć oczywistej struktury z jednej perspektywy, a mieć strukturę możliwą do wykorzystania w innej” – powiedział. „Trudne jest określenie właściwej nowej perspektywy”.
