Konkurencja kwantowego post-krypto jest odtwarzana przez komputer jednordzeniowy przez godzinę

W trwającej kampanii rządu USA mającej na celu ochronę danych w dobie komputerów kwantowych nowy i potężny atak, w którym wykorzystano pojedynczy klasyczny komputer do całkowitego złamania filtra czwartej rundy, podkreśla ryzyko związane ze standaryzacją algorytmów kryptograficznych nowej generacji.

W zeszłym miesiącu Narodowy Instytut Standardów i Technologii (NIST) Departamentu Handlu Stanów Zjednoczonych został nazwany Cztery algorytmy szyfrowania po obliczeniach kwantowych Zastąpienie algorytmów takich jak RSA, Diffie-Hellman i Diffie-Hellman, które nie są w stanie wytrzymać ataków na komputery kwantowe.

Na tym samym etapie NIST opracował cztery dodatkowe algorytmy jako potencjalne alternatywy oczekujące na dalsze testy w nadziei, że jeden lub więcej z nich będzie również odpowiednią alternatywą kryptograficzną w świecie post-kwantowym. Nowy atak łamie SIKE, jeden z ostatnich czterech dodatkowych algorytmów. Atak nie ma wpływu na cztery algorytmy PQC wybrane przez NIST jako zatwierdzone standardy, z których wszystkie opierają się na zupełnie innych technikach matematycznych niż SIKE.

Całkowicie lubiany

SIKE – skrót od Super symetryczna enkapsulacja klucza— Prawdopodobnie wypadł z wyścigu dzięki badaniom opublikowanym przez badaczy z Ameryki Północnej w ten weekend Bezpieczeństwo komputera i szyfrowanie przemysłowe Kolekcja znajduje się w KU Leuven. Artykuł nosi tytuł Skuteczny atak odzyskiwania klucza na SIDH (wersja początkowa), opisuje technikę wykorzystującą złożoną matematykę i pojedynczy tradycyjny komputer do pobierania kluczy kryptograficznych chroniących transakcje chronione protokołem SIKE. Cały proces trwa około godziny.

„Jest jasne, że ujawniona niedawno luka w zabezpieczeniach jest ogromnym ciosem dla SIKE” – napisał w e-mailu David Gao, profesor na Uniwersytecie Waterloo i współtwórca SIKE. „Atak jest naprawdę nieoczekiwany”.

Pojawienie się kryptografii z kluczem publicznym w latach 70. było dużym przełomem, ponieważ umożliwiło stronom, które nigdy się nie spotkały, bezpieczny handel zaszyfrowanymi materiałami, których przeciwnik nie mógł złamać. Kryptografia klucza publicznego opiera się na kluczach asymetrycznych, z jednym kluczem prywatnym używanym do deszyfrowania wiadomości i osobnym kluczem publicznym do szyfrowania. Użytkownicy szeroko udostępniają swój klucz publiczny. Dopóki ich klucz prywatny pozostaje tajny, system pozostaje bezpieczny.

W praktyce kryptografia klucza publicznego jest często niepraktyczna, dlatego wiele systemów opiera się na mechanizmach enkapsulacji klucza, które umożliwiają stronom, które wcześniej się nie spotkały, wspólne uzgodnienie klucza symetrycznego za pośrednictwem publicznego medium, takiego jak Internet. W przeciwieństwie do algorytmów z kluczem symetrycznym, stosowane obecnie mechanizmy enkapsulacji klucza mogą być łatwo złamane przez komputery kwantowe. Przed nowym atakiem wierzono, że SIKE omija takie luki za pomocą złożonej struktury matematycznej znanej jako hipergenomiczny graf izogeniczny.

Podstawą SIKE jest protokół o nazwie SIDH, który jest skrótem od Supersingular Isogeny Diffie-Hellman. Artykuł badawczy opublikowany w weekend pokazuje, że SIDH ma kontakt z teorią znaną jako „klej i rozszczepienie” opracowaną przez matematyka Ernsta Kanye w 1997 roku, a także z narzędziami opracowanymi przez kolegów matematyków Everetta W. Howe, Frank Leprovost i Björn Bonnen w 2000 roku. Nowa technika opiera się na tak zwanym „adaptacyjnym ataku GPST” opisanym w 2016 papier. Operacje matematyczne stojące za ostatnim atakiem są z pewnością nieprzeniknione dla większości nie-matematyków. Oto jak najbliżej:

„Atak wykorzystuje fakt, że SIDH ma punkty pomocnicze i znany jest stopień utajonej homologii” Stephen Galbraithprofesor matematyki na Uniwersytecie w Auckland i „G” w adaptacyjnym ataku GPST, wyjaśnił w a krótkie pisanie w nowym ataku. „Punkty pomocnicze SIDH zawsze były potencjalnym utrapieniem i podatnością, i były wykorzystywane do ataków zderzeniowych, ataków adaptacyjnych GPST, ataków punktowych itp.

Ukończył:

Odchodzi Mieć krzywą bazową i pozwolić masz prośbę . Odchodzi Musi mieć taką obecność symetrii klasa z A A

Kluczowym aspektem SIDH jest to, że się nie liczy bezpośrednio, ale jako kompozycja jednorodna stopnia 3. Innymi słowy, istnieje szereg krzywych Połączony z 3 izogeniami.

Zasadniczo, tak jak w GPST, atak wyznacza średnie krzywe W ten sposób ostatecznie definiuje klucz prywatny. w takt Atak przeszukuje wszystko, co możliwe, z brutalną siłą Magiczny składnik to narzędzie, które pokazuje, który z nich jest poprawny.

(Powyższe są zbyt uproszczone, homofony Jego atak nie jest klasą 3, ale klasą małej siły 3.)

Ważniejsze od zrozumienia matematyki, Jonathan Katz, członek IEEE i profesor na Wydziale Informatyki Uniwersytetu Maryland, napisał w e-mailu: „Atak jest całkowicie klasyczny i wcale nie wymaga komputerów kwantowych”.