Отобранный NIST постквантовый криптоалгоритм SIKE, оказался не защищён от взлома на обычном компьютере

Исследователи из Лёвенского католического университета разработали метод атаки на механизм инкапсуляции ключей SIKE (Supersingular Isogeny Key Encapsulation), который вошёл в финал конкурса постквантовых криптосистем, проводимого Национальным институтом стандартов и технологий США (SIKE был включён а число дополнительных алгоритмов, прошедших основные этапы отбора, но отправленных на доработку для устранения замечаний перед переводом в разряд рекомендованных). Предложенный метод атаки позволяет на обычном персональном компьютере восстановить значение ключа, используемого для шифрования на базе протокола SIDH (Supersingular Isogeny Diffie-Hellman), применяемого в SIKE.

Готовая реализация метода взлома SIKE опубликована в виде сценария для алгебраической системы Magma. Для восстановления закрытого ключа, применяемого для шифрования защищённых сетевых сеансов, при использовании набора параметров SIKEp434 (level 1) на одноядерной системе потребовались 62 минуты, SIKEp503 (level 2) — 2 часа 19 минут, SIKEp610 (level 3) — 8 часов 15 минут, SIKEp751 (level 5) — 20 часов 37 минут. На решение разработанных компанией Microsoft конкурсных заданий $IKEp182 и $IKEp217 было потрачено 4 и 6 минут соответственно.

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

Опубликованный метод взлома SIKE основан на предложенной в 2016 году адаптивной атаке GPST (Galbraith-Petit-Shani-Ti) на суперсингулярные изогенные механизмы инкапсуляции ключей и использует существование небольшого нескалярного эндоморфизма в начале кривой, подкрепляемого дополнительными сведениями о точке кручения, передаваемыми агентами, взаимодействующими в процессе работы протокола.

Источник: opennet.ru