Новая атака легко вывела из строя потенциальный алгоритм шифрования

Apr 14, 2023

Дэн Гудин, Ars Technica

В продолжающейся кампании правительства США по защите данных в эпоху квантовых компьютеров новая и мощная атака, в которой использовался один традиционный компьютер, чтобы полностью взломать кандидата четвертого тура, подчеркивает риски, связанные со стандартизацией алгоритмов шифрования следующего поколения.

Эта история первоначально появилась на Ars Technica, надежном источнике технологических новостей, анализа технической политики, обзоров и многого другого. Ars принадлежит материнской компании WIRED, Condé Nast.

В прошлом месяце Национальный институт стандартов и технологий США (NIST) выбрал четыре алгоритма постквантового шифрования для замены таких алгоритмов, как RSA, Диффи-Хеллмана и эллиптической кривой Диффи-Хеллмана, которые не способны противостоять атакам квантового компьютера. компьютер.

Одновременно NIST предложил четыре дополнительных алгоритма в качестве потенциальных заменителей, ожидающих дальнейшего тестирования, в надежде, что один или несколько из них также могут стать подходящими альтернативами шифрования в постквантовом мире. Новая атака взламывает SIKE, один из последних четырех дополнительных алгоритмов. Атака не оказала никакого влияния на четыре алгоритма PQC, выбранные NIST в качестве утвержденных стандартов, каждый из которых основан на совершенно других математических методах, чем SIKE.

SIKE — сокращение от суперсингулярной изогенной инкапсуляции ключей — теперь, вероятно, вышло из строя благодаря исследованию, которое было опубликовано на выходных исследователями из группы компьютерной безопасности и промышленной криптографии в KU Leuven. В документе под названием «Эффективная атака с восстановлением ключей на SIDH (предварительная версия)» описывается метод, который использует сложную математику и один традиционный ПК для восстановления ключей шифрования, защищающих транзакции, защищенные SIKE. Весь процесс занимает всего около часа времени. Этот подвиг дает исследователям Воутеру Кастрику и Томасу Декрю право на вознаграждение в размере 50 000 долларов от NIST.

«Недавно обнаруженная уязвимость, очевидно, является серьезным ударом по SIKE», — написал в электронном письме Дэвид Джао, профессор Университета Ватерлоо и соавтор SIKE. «Атака действительно неожиданная».

Появление шифрования с открытым ключом в 1970-х годах стало крупным прорывом, поскольку оно позволило сторонам, которые никогда не встречались друг с другом, безопасно обмениваться зашифрованными материалами, которые не мог взломать злоумышленник. Шифрование с открытым ключом основано на асимметричных ключах: один закрытый ключ используется для расшифровки сообщений, а другой открытый ключ — для шифрования. Пользователи делают свой открытый ключ широко доступным. Пока их закрытый ключ остается секретным, схема остается безопасной.

На практике криптография с открытым ключом часто может быть громоздкой, поэтому многие системы полагаются на механизмы инкапсуляции ключей, которые позволяют сторонам, которые никогда раньше не встречались, совместно согласовывать симметричный ключ через общедоступную среду, такую ​​​​как Интернет. В отличие от алгоритмов с симметричным ключом, используемые сегодня механизмы инкапсуляции ключей легко взламываются квантовыми компьютерами. До новой атаки считалось, что SIKE позволяет избежать таких уязвимостей, используя сложную математическую конструкцию, известную как суперсингулярный граф изогении.

Краеугольным камнем SIKE является протокол под названием SIDH, сокращение от суперсингулярной изогении Диффи-Хеллмана. В исследовательском документе, опубликованном на выходных, показано, насколько SIDH уязвим для теоремы, известной как «склеивание и разделение», разработанной математиком Эрнстом Кани в 1997 году, а также инструментов, разработанных коллегами-математиками Эвереттом В. Хоу, Франком Лепрево и Бьорном. Пуненом в 2000 году. Новый метод основан на так называемой адаптивной атаке GPST, описанной в статье 2016 года. Математика, лежащая в основе последней атаки, гарантированно будет непонятна большинству нематематиков. Вот примерно так близко, как вы собираетесь получить:

«Атака использует тот факт, что у SIDH есть вспомогательные точки и что степень секретной изогении известна», — объяснил в короткой статье Стивен Гэлбрейт, профессор математики из Университета Окленда и буква «G» в адаптивной атаке GPST. о новой атаке. «Вспомогательные точки в SIDH всегда были раздражающими и потенциально слабыми местами, и их использовали для атак по сбоям, адаптивных атак GPST, атак торсионных точек и т. д.»