Одноядерный ПК взломал алгоритм постквантового шифрования за один час
Исследователи из группы компьютерной безопасности и промышленной криптографии 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: E_0 \to E, \phi (P_0) = P и \phi (Q_0) = Q.
Ключевым аспектом SIDH является то, что \phi вычисляется не напрямую, а как композиция изогений степени малой степени 3. Другими словами, существует последовательность кривых E_0 \to E_1 \to E_2 \to \cdots \to E, связанных по 3-изогении.
По сути, как и в GPST, атака определяет промежуточные кривые E_i и, следовательно, в конечном итоге определяет закрытый ключ. На шаге i атака выполняет перебор всех возможных E_i \to E_{i+1}, а магическим ингредиентом является гаджет, который показывает, какой из них правильный.
В феврале этого года постдок IBM Уорд Белленс опубликовал исследование, в ходе которого он взломал Rainbow, схему криптографической подписи.
Исследователи говорят, что атака использует правила математики, которые были опубликованы в 1990-х и 2000-х годах. Одним из неожиданных аспектов атаки является то, что она использует кривые рода 2 для атаки на эллиптические кривые, которые являются кривыми рода 1. Связь между двумя типами кривых оказалась совершенно неожиданной.
