Исследователи из голландской компании PQShield обнаружили проблему, связанную с потерей защищённости кода после его компиляции. Проблема была выявлена при анализе постквантового криптографического механизма Kyber, но может иметь более широкое распространение и влияние.
- Введение
- Что случилось с механизмом Kyber?
- Атака на Kyber по стороннему каналу
- Как писать код грамотно и не допускать его компрометации
- Но куда ж без компилятора?
- Как такое могло произойти?
- Частный случай или закономерность?
- Расследование по Kyber продолжается
- От слов к делу
- Выводы
Введение
На днях мы сообщали, что в эталонной реализации механизма инкапсуляции ключей (KEM) Kyber была обнаружена уязвимость, позволяющая получить секретные данные через атаку по стороннему каналу. О находке сообщили исследователи из компании PQShield, которая занимается задачами разработки алгоритмов для постквантовой криптографической защиты. Эта фирма была среди участников разработки международных стандартов для квантовых вычислений, проводимых государственным институтом стандартов и технологий США (NIST).
Напомним, что в августе 2023 года NIST сообщил о выборе четырёх базовых алгоритмов для постквантовой криптографии. Они были отобраны среди 69 заявленных кандидатов и призваны играть роль краеугольного камня борьбы с квантовыми угрозами в долгосрочной перспективе.
В список NIST попали следующие алгоритмы постквантовой криптографии:
- CRYSTALS-Kyber (для выполнения общих задач шифрования, в т. ч. для создания защищённых веб-сайтов);
- CRYSTALS-Dilithium (для защиты цифровых подписей при удалённом подписании);
- SPHINCS+ (для защиты цифровых подписей);
- FALCON (тоже для защиты цифровых подписей).
Что случилось с механизмом Kyber?
Напомним, что произошло. Уязвимость может проявиться, когда компилятор — в данном случае Clang — оптимизирует код. Как оказалось, он порождает в функции «poly_frommsg» переход, зависящий от обрабатываемого секрета. Речь идёт о данных, которые передаются через параметр и требуют повышенной защиты.
Суть выявленной проблемы состоит в следующем. Функция «poly_frommsg» используется при декапсуляции многократно (более 100 тыс. раз). По словам экспертов, если собрать статистику по времени, затрачиваемому на выполнение операций декапсуляции (что можно сделать, например, если получить локальный доступ к вычислительной системе), то можно восстановить значение секрета (пароля) за обозримое время.
Исследователи из PQShield подготовили соответствующий демонстрационный (PoC) код для машин с архитектурой x86 и смогли получить значение 512-битного ключа менее чем за 10 минут, реализовав тем самым эксплойт на базе тайминг-уязвимости. Они также сообщили, что им удалось «найти противоядие, объединив усилия с командой Kyber».
Что же именно предложили специалисты? В чём конкретно состояла уязвимость, которую потребовалось устранить? Касается ли это только постквантовых вычислений или имеет значение также и для «обычных»?
Атака на Kyber по стороннему каналу
Как уже было отмечено, выявленная уязвимость позволяет реализовать атаку по стороннему каналу. Иными словами, речь идёт о выявлении стороннего параметра и его оценке, благодаря чему можно найти секретное значение. Такие бреши трудно выявлять. Обычно этим занимаются команды DevSecOps.
В случае с Kyber таким параметром стало время выполнения определённого набора команд. Сбор статистики по этому параметру позволяет сократить диапазон подбираемых значений при использовании метода перебора (Brute Force) и получить в итоге конфиденциальную информацию.
Как писать код грамотно и не допускать его компрометации
В качестве иллюстрации исследователи из PQShield предлагают рассмотреть следующий простой пример.
Допустим, нужно написать функцию, которая получает на вход строковый параметр «msg» длиной 256 бит. Задача — преобразовать получаемый параметр в массив r[256], содержащий целые числа размером 16 бит.
На языке разработчика эта задача будет звучать следующим образом: необходимо присвоить каждому элементу массива r[j] некоторую константу, если соответствующий j-й бит в «msg» равен 1, в противном случае оставить нуль.
Разработчик напишет на языке C примерно так (рис. 1).
Рисунок 1. Пример простого решения задачи
Имеем рабочее решение. Однако оно не отвечает требованиям DevSecOps.
Суть «нарушения» состоит в том, что в зависимости от содержимого входного параметра «msg» обработка будет уходить на разные ветви кода. Эта особенность логики отмечена красным.
Если бы эту задачу предложили решить разработчику, который профессионально занимается криптографией, то вместо ветвления он использовал бы приём маскирования. В итоге, создав битовую маску по исходному сообщению, он сможет использовать её в логическом суммировании с используемой константой, не прибегая к «опасному» ветвлению кода. У него получился бы такой вариант, как на рисунке 2.
Рисунок 2. Пример безопасного решения задачи
Видно, что в результате ветвление кода пропадает, тем самым устраняется риск выявления закономерностей при выполнении кода и их последующего анализа.
Но куда ж без компилятора?
Казалось бы, все проблемы решены. По всей видимости, так считали изначально и разработчики кода Kyber. Но оказалось, что не всё так просто.
В PQShield вспомнили об известном факте: исходный код на высокоуровневом языке, таком как C, C++ или Rust, не доходит до процессора в первозданном виде. Сначала выполняется компиляция, т. е. перевод на низкоуровневый язык — например, в ассемблерный код (для C / C++ обычно используется GCC или Clang). Это делается для того, чтобы код мог работать нативно на целевой машине с определённой архитектурой.
Однако компилятор занимается не только преобразованием, но и оптимизацией кода, причём в несколько проходов. Например, он может удалить часть кода, если это не влияет на результат. Он также может развернуть циклы в более простые последовательности, если в итоге будет достигаться заданная цель оптимизации (например, более высокая производительность). Таких приёмов очень много.
Вернёмся к первому примеру выше. Если код функции «expand_insecure» передать в компилятор Clang (версии 18) для платформы x86 с оптимизацией по размеру кода (-Os), то будет получен следующий результат (рис. 3).
Рисунок 3. Машинный код после компиляции простого решения
«Уязвимость логического ветвления» выделена красным цветом. Частота подстановки константы легко детектируется. Без большого труда выявляется также и место её расположения (по смещению 1665).
Теперь посмотрим, как этот проблемный участок скомпилируется для безопасного кода функции «expand_secure» (второй вариант). Для наглядности была выделена только проблемная часть. Как видно, в итоге получилась та же самая конструкция, что и после компиляции небезопасного варианта № 1.
Рисунок 4. Машинный код после компиляции безопасного решения
Как такое могло произойти?
Компилятор Clang провёл оптимизацию. Он определил, что маска может принимать только два значения: «все нули» и «все единицы». Далее он обнаружил, что получаемый параметр может принимать либо значение «ноль», либо значение «CONSTANT». Проведя оптимизацию для получения наиболее производительной версии под x86, компилятор выдал именно ту ветвь, ради избавления от которой и вводилась маска.
Иначе говоря, компилятор молча переделал код, специально написанный ради повышения безопасности. Он «понял», что введённые ухищрения избыточны с точки зрения производительности, и устранил их.
Частный случай или закономерность?
Инженеры PQShield продолжили свои исследования и обнаружили, что аналогичный результат встречается и при других вариантах оптимизации. Например, для версий компилятора Clang 15–18 для x86 это наблюдается при выборе опций «-Os», «-O1», «-O2 -fno-vectorize» и «-O3 -fno-vectorize».
В итоге исследователи пришли к выводу: многие хитрости, которые разработчики в прошлом придумывали и добавляли в код ради повышения его безопасности, могли на самом деле «уничтожаться» в результате компиляции и не попадать в низкоуровневый / машинный код, превращая его в уязвимый.
Расследование по Kyber продолжается
Вернёмся теперь к Kyber, перспективному механизму инкапсуляции ключей для постквантового шифрования ML-KEM (FIPS-203), с которого начинали. Как выяснили исследователи из PQShield, показанная в качестве примера выше процедура оказалась вполне актуальной. Она реально использовалась для решения задач по инкапсуляции и декапсуляции ключей.
Соответствующая функция носит название «poly_frommsg». Её код доступен здесь и выглядит очень знакомо (рис. 5).
Рисунок 5. Функция «poly_frommsg» в коде Kyber
Что можно сказать после всех приведённых выше рассуждений? Обнаружена мина замедленного действия?
От слов к делу
Питер Швабе (Peter Schwabe), член консультативного совета при компании PQShield, который руководил этим расследованием и впоследствии сообщил о нём публично, задался поначалу вопросом: а не теоретическая ли это проблема?
С одной стороны, условный параметр «msg» является критически важным для безопасности при выполнении процедур инкапсуляции и декапсуляции ключей. С другой стороны, в коде функции «poly_frommsg» обнаружена всего лишь одна уязвимая ветвь, причём только в одном месте. Может, всё не так плохо? В конце концов, компрометация такой погрешности сильно зависит от готовности злоумышленников к проведению глубоких исследований.
Питер Швабе постарался оценить реалистичность подобного события.
Рисунок 6. Питер Швабе
Как показывают исследования, если злоумышленники способны напрямую контролировать выполнение кода и при этом достаточно хорошо подготовлены технически, то они могут провести атаку с контролем содержимого кеша и обеспечить себе высокую частоту снятия значений. Это позволяет им «поймать» предиктор ветвлений и узнать, какие ветви используются. Они также могут замедлять обращения к библиотеке с проблемным кодом и получить нужный результат. Поэтому данную погрешность лучше исправить в машинном коде.
Другой аргумент в пользу устранения изъяна — это результаты реальных операций хакеров. Известно, что при атаках с контролем времени задержек при выполнении декапсуляции злоумышленник может восстановить значение ключа.
В итоге эксплуатация оказалась вполне практичной. В ходе фактического тестирования восстановление значения 512-битного секретного ключа ML-KEM на обычном ноутбуке заняло... 10 минут.
Рисунок 7. Тестовое восстановление секретного ключа длилось 544 секунды
Питер Швабе также назвал библиотеки, где встречается аналогичный код. В их число попали «liboqs», «aws-lc», «pq-code-package» и WolfSSL. Их разработчиков заранее уведомили через закрытый канал раскрытия уязвимостей. По публичному каналу были также проинформированы разработчики PQClean и «rustpq/pqcrypto».
Выводы
Исследователи из компании PQShield привлекли внимание ИБ-сообщества к примечательному феномену: компиляторы могут удалять из кода те элементы и механизмы, которые специально вводятся разработчиками ради повышения защищённости создаваемых программ. Эффект был выявлен на примере постквантового криптографического механизма Kyber, но полученные результаты могут иметь более широкое распространение: инженерам DevSecOps теперь нужно думать ещё и о том, не умножает ли все их ухищрения на ноль обычный компилятор.
