Поделиться
Хваленый алгоритм защиты от атак квантовых компьютеров бесполезен. Его может обойти древний одноядерный ПК
Алгоритмы шифрования, защищающие от атак квантовых компьютеров, оказались бесполезны перед древним компьютером с обычным одноядерным процессором. Алгоритм SIKE удалось взломать всего за час, притом хакеры задействовали математические инструменты, разработанные несколько десятков лет назад. Авторы SIKE были крайне удивлены, узнав, что их детище оказалось беззащитным перед этими инструментами.
Миф о надежности постквантового шифрования развеян
Исследователи Воутер Кастрик (Wouter Castryck) и Томас Декру (Thomas Decru) доказали, что постквантовое шифрование в том виде, в котором оно существует сейчас, не всегда способно обеспечить должный уровень безопасности. Как пишет ArsTechnica, им удалось обойти его при помощи самого обычного компьютера с кремниевым процессором, притом далеко не самого современного.
Декру и Кастрик взломали алгоритм постквантового шифрования SIKE, используя компьютер, процессор которого имеет всего-навсего одно ядро. По меркам 2022 г. это ультраустаревшее «железо». Вопреки ожиданиям, весь процесс занял у них не годы и даже не месяцы или дни – исследователи справились приблизительно за 60 минут.
Алгоритмы постквантовой криптотграфии в общей своей массе призваны сохранять устойчивость при атаке со стороны квантовых компьютеров. Хотя разработка таких компьютеров по-прежнему находится на относительно ранней стадии, предполагается, что их вычислительные мощности позволят взламывать многие современные алгоритмы шифрования за короткое время.
Подробнее о SIKE
SIKE или Supersingular Isogeny Key Encapsulation – это один из нескольких современных алгоритмов постквантового шифрования, который предложен экспертами Национального института стандартов и технологий Министерства торговли США (NIST) на замену традиционным алгоритмам Диффи-Хеллмана (обычный и на основе эллиптических кривых) и RSA. Все трое по умолчанию не в состоянии противостоять атакам квантовых вычислений, что делает их бесполезными в грядущей эпохе квантовых ПК.
Четыре варианта их замены NIST уже утвердил, и еще четыре, включая SIKE, ожидали дальнейшего тестирования на устойчивость к взлому. Декру и Крастик исключили его из списка претендентов.
Что не так с алгоритмом
Крастик и Декру использовали для взлома бреши в системе безопасности протокола SIDH (Supersingular Isogeny Diffie-Hellman), составляющем основу SIKE. Подойдя к вопросу с точки зрения высшей математики, они обнаружили, что этот протокол уязвим для так называемой теоремы «склеить и разделить» (glue-and-split), разработанной математиком Эрнстом Кани (Ernst Kani) еще 25 лет назад, в 1997 г. Также они использовали ряд инструментов за авторством математиков Эвереттом Хоу (Everett Howe), Франком Лепрево (Franck Leprevost) и Бьорном Пуненом (Bjorn Poonen) в 2000 г.
Для взлома алгоритма исследователи провели описанную в 2016 г. так называемую «адаптивную атаку GPST». Аббревиатура в названии расшифровывается как Galbraith-Petit-Shani-Ti. Это фамилии ученых, описавших ее.
«Атака использует тот факт, что протокол SIDH располагает вспомогательными точками, и что степень секретной изогении известна», – сказал профессор математики из Оклендского университета (США) Стивен Гэлбрейт (Steven Galbraith), один из тех, кто первым объяснил принцип атаки GPST. Ученый подчеркнул, что упомянутые им вспомогательные точки всегда были слабым местом SIDH и регулярно использовались для взлома этого протокола.
Крастик и Декру доказали, что для взлома постквантового алгоритма шифрования SIKE не нужен квантовый компьютер – хватит и обычного древнего ПК. За проделанную работу они получили $50 тыс. (около 3 млн руб. по курсу ЦБ на 3 августа 2022 г.).
Комментируя исследование Крастика и Декру, член Института инженеров электротехники и электроники (Institute of Electrical and Electronics Engineers, IEEE) Джонатан Кац (Jonathan Katz) подтвердил, что такого рода атака на SIKE действительно может проводиться с использованием классического ПК.
Неожиданный сюрприз
Для разработчиков SIKE уязвимость алгоритма к атаке GPST оказалась сюрпризом. Это ArsTechnica подтвердил его соавтор Дэвид Джао (David Jao), профессор Университета Ватерлоо. «Атака была неожиданностью», – сказал он.
На вопрос ArsTechnica, почему SIKE уязвим перед математическими теоремами, которым десятки лет, Дэвид Джао ответил: «Это правда, что атака использует математику, которая была опубликована в 1990-х и 2000-х годах. В некотором смысле атака не требует новой математики; это могло быть замечено в любое время. Одним из неожиданных аспектов атаки является то, что она использует кривые второго рода для атаки на эллиптические кривые (которые являются кривыми первого рода)».
«Связь между двумя типами кривых совершенно неожиданна, – добавил профессор. – Чтобы привести пример, иллюстрирующий то, что я имею в виду, в течение десятилетий люди пытались атаковать криптографию с использованием обычных эллиптических кривых, включая тех, кто пытался использовать подходы, основанные на кривых второго рода. Ни одна из этих попыток не увенчалась успехом. Таким образом, эта попытка добиться успеха в области изогений является неожиданным развитием событий».
Алгоритмы сдаются один за другим
NIST ищет алгоритмы постквантового шифрования на замену RSA-алгоритму на протяжении пяти лет. в 2017 г. список кандидатов насчитывал 69 позиций, к 2019 г. их осталось 26, а еще через год в перечень состоял лишь из семи финалистов и восьми запасных вариантов.
В 2021 г. осталось четыре финалиста и четыре запасных алгоритма, включая SIKE. Последний теперь выбыл, но он в этом плане не единственный. Ранее аналогичная участь постигла схему криптографической подписи Rainbow. За ее взломом стоит эксперт компании IBM Уорд Белленс (Ward Beullens).
Поделиться
Короткая ссылка
