Одноядерный ПК взломал алгоритм постквантового шифрования за один час

Исследователи из группы компьютерной безопасности и промышленной криптографии KU Leuven Воутер Кастрик и Томас Декру смогли взломать алгоритм постквантового шифрования SIKE с помощью обычного компьютера всего за один час.

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

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

Исследователи выпустили документ под названием «Эффективная атака с восстановлением ключа на SIDH (предварительная версия)» с описанием метода, использующего сложную математику и один традиционный ПК для восстановления ключей шифрования, защищающих транзакции SIKE. Они подошли к проблеме с чисто математической точки зрения, атакуя ядро ??конструкции алгоритма, а не потенциальные уязвимости кода.

Основу SIKE составляет протокол под названием SIDH (Supersingular Isogeny Diffie-Hellman). SIDH уязвим для теоремы «склеить и разделить», разработанной математиком Эрнстом Кани в 1997 году, с применением дополнительных математических инструментов. Его удалось взломать благодаря «адаптивной атаке GPST», описанной в статье 2016 года. «Атака использует тот факт, что SIDH имеет вспомогательные точки и что степень секретной изогении известна», — объяснил Стивен Гэлбрейт, профессор математики из Оклендского университета.

Он объяснил, как работает математика:

Пусть E_0 будет базовой кривой и пусть P_0, Q_0 in E_0 имеют порядок 2^a. Пусть E, P, Q заданы так, что существует изогения phi степени 3^b с phi :

Ключевым аспектом SIDH является то, что phi вычисляется не напрямую, а как композиция изогений степени малой степени 3. Другими словами, существует последовательность кривых:

связанных по 3-изогении.

По сути, как и в GPST, атака определяет промежуточные кривые E_i и, следовательно, в конечном итоге определяет закрытый ключ. На шаге i атака выполняет перебор всех возможных

а магическим ингредиентом является гаджет, который показывает, какой из них правильный.

В феврале этого года постдок IBM Уорд Белленс опубликовал исследование, в ходе которого он взломал Rainbow, схему криптографической подписи. 

Исследователи говорят, что атака использует правила математики, которые были опубликованы в 1990-х и 2000-х годах. Одним из неожиданных аспектов атаки является то, что она использует кривые рода 2 для атаки на эллиптические кривые, которые являются кривыми рода 1. Связь между двумя типами кривых оказалась совершенно неожиданной.