Простой компьютер взломал алгоритм постквантового шифрования: справился за час
Ученые применили математический подход, атаковав ядро алгоритма напрямую.
Ученые из Левенского католического университета (Нидерланды) взломали алгоритм постквантового шифрования с помощью простого компьютера. На взлом они потратили 1 ч, сообщает arstechnica.com
Национальный институт стандартов и технологий Министерства торговли США (NIST) выбрал четыре алгоритма шифрования постквантовых вычислений для замены алгоритмов, которые не могут выдержать атак квантовых компьютеров, — RSA, алгоритм Диффи-Хеллмана и алгоритм Диффи-Хеллмана на основе эллиптических кривых. Также в NIST выбрали 4 дополнительных алгоритма в качестве потенциальной замены традиционным алгоритмам. Оказалось, что один из алгоритмов “на замену”, SIKE, можно взломать. Однако стоит отметить, что взломать четыре алгоритма PQC (PQC — пост-квантовая криптография), выбранных NIST в качестве утвержденных стандартов, не удалось, так как они основаны на совершенно иных математических методах.
Нидерландские исследователи Воутер Кастрик и Томас Декру применили свои математические знания и обычный одноядерный компьютер, что и помогло им одолеть SIKE. Ученые нацелили атаку на ядро алгоритма, а не пошли по пути поиска и атак уязвимостей.
Ядром алгоритма является протокол Supersingular Isogeny Diffie-Hellman (SIDH), который, как выяснилось, и является одной сплошной уязвимостью. Применив теорему “склеить и разделить” (glue-and-split) авторства математика Эрнста Кани и несколько инструментов, разработанных математиками Эвереттом Хоу, Франком Лепрево и Бьорном Пуненом, нидерландские ученые совершили адаптивную атаку GPST (GPST — Galbraith-Petit-Shani-Ti, фамилии исследователей).
Адаптивная атака GPST нацелена на так называемые “вспомогательные точки” протокола SIDH, которые заранее известны. Поэтому взломать SIKE не составило труда, используя даже “слабенький” компьютер.
