Старая математика ломает постквантовые шифры
Мир криптографии постепенно готовится к приходу квантовых вычислений, где вместо двоичной логики используются кубиты. Предполагается, что именно криптография станет одним из первых применений квантовых компьютеров.
Проблема в том, что современные алгоритмы вроде RSA и Диффи-Хеллмана (в том числе на эллиптических кривых) не способны противостоять квантовым атакам. Поэтому в июле 2022 года Национальный институт стандартов и технологий США (NIST) опубликовал набор алгоритмов шифрования, потенциально способных противостоять взлому на квантовых компьютерах — так называемые «постквантовые шифры».
Один из «постквантовых» шифров сразу взломали. Но самое интересное — метод, который применили исследователи.
В июле 2022 года после многоступенчатого отбора NIST определил оптимальный универсальный алгоритм CRYSTALS-Kyber и ещё четыре алгоритма общего назначения BIKE, Classic McEliece, HQC и SIKE, которые требуют доработки.
NIST предложил исследователям проверить опубликованные алгоритмы на наличие уязвимостей с вознаграждением $50 тыс. за удачный взлом.
Алгоритм SIKE базируется на суперсингулярной изогении, то есть кружении в суперсингулярном изогенном графе. Основу SIKE составляет протокол под названием SIDH (Supersingular Isogeny Diffie-Hellman).
Изогенные эллиптические кривые к многообразию E можно получить факторизцией E по конечным подгруппам, которые представлены как подгруппы 4-кручения, источник
Исследователи из Католического университета в Лёвене (Бельгия) довольно быстро взломали алгоритм SIKE, за что получили заслуженную награду (об этом упоминали на Хабре в августе 2022 года).
Для нахождения секретного ключа понадобилось задействовать всего одно ядро старенького процессора Xeon E5-2630v2 на тактовой частоте 2,60 ГГц. Вычисление заняло менее часа.
Но более интересны подробности этого взлома, которые можно почитать в кратком комментарии профессора математики Стивена Гэлбрейта, пресс-релизе Королевского университета Канады и научной статье самих криптографов Воутера Кастрика (Wouter Castryck) и Томаса Декру (Thomas Decru).
Уязвимым местом шифра SIKE оказалась математическая теорема, вероятно, не знакомая авторам шифра и составителям конкурса NIST. Это научная статья д-ра Эрнста Кани от 1997 года. Данная теорема связана с абстрактным манипулированием математическими объектами для исследования их различных свойств.
В теореме Кани обсуждается процесс «склеивания» двух эллиптических кривых — и при каких условиях эта процедура может дать сбой. Собственно, один из описанных в статье вариантов сбоя использовался в реализации SIKE, что дало естественный путь к взлому этого алгоритма с помощью «адаптивной атаки GPST», описанной в статье «О безопасности криптосистем с суперсингулярной изогенией» (2016), которая разработана на основе вышеупомянутой работы 1997 года.
В августе 2022 года соавтор статьи о GPST профессор Гэлбрейт пояснил: ключевая уязвимость SIKE состоит в том, что SIDH вычисляет изогению не напрямую, а через вспомогательные точки, причём степень изогении известна. Таким образом, для атаки можно применять готовый математический аппарат, разработанный в 1997 году.
Как и GPST, атака на SIKE просто определяет промежуточные кривые
между базовой кривой 
и конечным результатом шифрования 
, то есть в конечном итоге определяет закрытый ключ.
«Один из соавторов алгоритма SIKE выразил удивление по поводу того, что кривые второго порядка можно исполь��овать для получения информации об эллиптических кривых. Но именно такой была наша первоначальная стратегия в 1980-х и 1990-х годах (и после)», — сказал доктор Кани в комментарии для пресс-службы университета.
Успешный взлом SIKE доказывает, что он не может быть надёжным средством шифрования, сужая поле возможных кандидатов для технологий постквантового шифрования. Эта история ещё раз демонстрирует силу и мощь глобального научного сообщества, которое действует как единое целое и движет вперёд технический прогресс с неизбежным постоянством.
Математическая теорема Кани 1997 года — чисто теоретическая работа, при написании которой автор вряд ли предвидел возможные практические применения. В этом нет ничего удивительного. И сейчас учёные в области теоретической, фундаментальной физики и математики не могут представить, для каких реальных приборов будут использоваться их формулы через 100, 1000 или 10 000 лет.
Например, французский математик Пьер Ферма в 1637 году во время факторизации больших чисел сформулировал некоторую любопытную теорему. И только в 1978 было найдено её применение в криптографии.
Все методы шифрования данных — это математика. Поэтому и новейшие системы постквантового шифрования тоже основаны на научных достижениях прошлых веков.
Управляемая инфраструктура PKI GlobalSign – это защищенная SaaS-платформа, которая позволит вам полностью контролировать работу с сертификатами на базе единой централизованной учетной записи. API-интерфейсы, интеграция с Active Directory и инструменты учета упростят автоматизацию и отслеживание развертываемых сертификатов.
Более подробную информацию вы можете найти на нашем сайте: www.globalsign.com/ru-ru/managed-pki
Мир криптографии постепенно готовится к приходу квантовых вычислений, где вместо двоичной логики используются кубиты. Предполагается, что именно криптография станет одним из первых применений квантовых компьютеров.
Проблема в том, что современные алгоритмы вроде RSA и Диффи-Хеллмана (в том числе на эллиптических кривых) не способны противостоять квантовым атакам. Поэтому в июле 2022 года Национальный институт стандартов и технологий США (NIST) опубликовал набор алгоритмов шифрования, потенциально способных противостоять взлому на квантовых компьютерах — так называемые «постквантовые шифры».
Один из «постквантовых» шифров сразу взломали. Но самое интересное — метод, который применили исследователи.
Алгоритм SIKE
В июле 2022 года после многоступенчатого отбора NIST определил оптимальный универсальный алгоритм CRYSTALS-Kyber и ещё четыре алгоритма общего назначения BIKE, Classic McEliece, HQC и SIKE, которые требуют доработки.
NIST предложил исследователям проверить опубликованные алгоритмы на наличие уязвимостей с вознаграждением $50 тыс. за удачный взлом.
Алгоритм SIKE базируется на суперсингулярной изогении, то есть кружении в суперсингулярном изогенном графе. Основу SIKE составляет протокол под названием SIDH (Supersingular Isogeny Diffie-Hellman).
Изогенные эллиптические кривые к многообразию E можно получить факторизцией E по конечным подгруппам, которые представлены как подгруппы 4-кручения, источник
Исследователи из Католического университета в Лёвене (Бельгия) довольно быстро взломали алгоритм SIKE, за что получили заслуженную награду (об этом упоминали на Хабре в августе 2022 года).
Для нахождения секретного ключа понадобилось задействовать всего одно ядро старенького процессора Xeon E5-2630v2 на тактовой частоте 2,60 ГГц. Вычисление заняло менее часа.
Но более интересны подробности этого взлома, которые можно почитать в кратком комментарии профессора математики Стивена Гэлбрейта, пресс-релизе Королевского университета Канады и научной статье самих криптографов Воутера Кастрика (Wouter Castryck) и Томаса Декру (Thomas Decru).
Теорема 1997 года
Уязвимым местом шифра SIKE оказалась математическая теорема, вероятно, не знакомая авторам шифра и составителям конкурса NIST. Это научная статья д-ра Эрнста Кани от 1997 года. Данная теорема связана с абстрактным манипулированием математическими объектами для исследования их различных свойств.
В теореме Кани обсуждается процесс «склеивания» двух эллиптических кривых — и при каких условиях эта процедура может дать сбой. Собственно, один из описанных в статье вариантов сбоя использовался в реализации SIKE, что дало естественный путь к взлому этого алгоритма с помощью «адаптивной атаки GPST», описанной в статье «О безопасности криптосистем с суперсингулярной изогенией» (2016), которая разработана на основе вышеупомянутой работы 1997 года.
В августе 2022 года соавтор статьи о GPST профессор Гэлбрейт пояснил: ключевая уязвимость SIKE состоит в том, что SIDH вычисляет изогению не напрямую, а через вспомогательные точки, причём степень изогении известна. Таким образом, для атаки можно применять готовый математический аппарат, разработанный в 1997 году.
Как и GPST, атака на SIKE просто определяет промежуточные кривые
между базовой кривой и конечным результатом шифрования , то есть в конечном итоге определяет закрытый ключ.«Один из соавторов алгоритма SIKE выразил удивление по поводу того, что кривые второго порядка можно исполь��овать для получения информации об эллиптических кривых. Но именно такой была наша первоначальная стратегия в 1980-х и 1990-х годах (и после)», — сказал доктор Кани в комментарии для пресс-службы университета.
Успешный взлом SIKE доказывает, что он не может быть надёжным средством шифрования, сужая поле возможных кандидатов для технологий постквантового шифрования. Эта история ещё раз демонстрирует силу и мощь глобального научного сообщества, которое действует как единое целое и движет вперёд технический прогресс с неизбежным постоянством.
Важность теоретической науки
Математическая теорема Кани 1997 года — чисто теоретическая работа, при написании которой автор вряд ли предвидел возможные практические применения. В этом нет ничего удивительного. И сейчас учёные в области теоретической, фундаментальной физики и математики не могут представить, для каких реальных приборов будут использоваться их формулы через 100, 1000 или 10 000 лет.
Например, французский математик Пьер Ферма в 1637 году во время факторизации больших чисел сформулировал некоторую любопытную теорему. И только в 1978 было найдено её применение в криптографии.
Все методы шифрования данных — это математика. Поэтому и новейшие системы постквантового шифрования тоже основаны на научных достижениях прошлых веков.
Управляемая инфраструктура PKI GlobalSign – это защищенная SaaS-платформа, которая позволит вам полностью контролировать работу с сертификатами на базе единой централизованной учетной записи. API-интерфейсы, интеграция с Active Directory и инструменты учета упростят автоматизацию и отслеживание развертываемых сертификатов.
Более подробную информацию вы можете найти на нашем сайте: www.globalsign.com/ru-ru/managed-pki
