4 июня 2026 года Дэниел Бернстайн выложил работу "Exploiting ML-DSA bugs" (cr.yp.to/papers/mldsa-20260601.pdf) - 59 страниц, две рабочие демонстрации key recovery из ML-DSA (FIPS 204). Обе атаки завершаются менее чем за секунду на одном ядре ноутбука: на входе - публичный ключ и две подписи, на выходе - полный секретный ключ и возможность штамповать поддельные подписи, проходящие стандартную верификацию. Параллельно появились исследования, которые систематизируют side-channel утечки рандомности в ML-DSA как семейство задач Integer Learning with Errors (ILWE) и показывают, что Belief Propagation-солверы роняют порог атаки на один-два порядка по числу необходимых подписей. В русскоязычном пространстве эти результаты разобраны поверхностно - разбираемся от математики подписи до конкретных солверов.
Процедура подписи ML-DSA: анатомия уязвимого компонента
ML-DSA (Module-Lattice-Based Digital Signature Algorithm, FIPS 204) - постквантовый стандарт цифровой подписи, раньше известный как CRYSTALS-Dilithium. Безопасность схемы стоит на двух ногах: стойкость решёточной задачи Module-LWE / Module-SIS и секретность эфемерной рандомности, используемой при каждом акте подписи. Первая нога цела. Вторая ломается при утечке даже нескольких бит.
Шаги Sign по Algorithm 7 FIPS 204
Подпись сообщения M проходит через rejection loop, и каждый элемент этого цикла критичен для понимания вектора атаки:Вычисление mu. Хеш Mu = H(tr || M', 64) - 64-байтный дайджест, включающий tr (хеш публичного ключа, привязывающий подпись к конкретному ключу) и форматированное сообщение M' (Algorithm 7, FIPS 204). Значение tr предотвращает подстановку ключей: подпись жёстко привязана к конкретному публичному ключу.
Генерация seed рандомности p'. В hedged-режиме (по умолчанию) p' = H(K || rnd || mu, 64), где K - секретный компонент ключа, rnd - 32 байта свежей рандомности от RNG. В детерминированном режиме rnd = 0x00...00. Значение p' - единственный источник энтропии для генерации вектора y.
Развёртывание маски y через ExpandMask(p', k). Вектор y ∈ R_q^l содержит коэффициенты в диапазоне [-(Y₁-1), Y₁]. Для ML-DSA-44 Y₁ = 2^17 (коэффициенты представимы 18 битами со знаком), для ML-DSA-65 и ML-DSA-87 Y₁ = 2^19 (20 бит со знаком). Счётчик κ инкрементируется при каждом rejection-проходе - свежие значения y на каждой итерации без повторного обращения к RNG.
Вычисление w = A*y и разложение w на старшие (w₁) и младшие биты. Матрица A - публичная, генерируется из p (компонент публичного ключа).
Challenge c = H(mu, w₁) - разреженный полином в R_q с ровно t ненулевыми коэффициентами (+-1). Для ML-DSA-44 t = 39, для ML-DSA-65 t = 49, для ML-DSA-87 t = 60.
Отклик z = y + c*s₁. Здесь s₁ - секретный вектор из закрытого ключа. Это центральное уравнение всей схемы: если атакующий знает y, он вычисляет c*s₁ = z − y и восстанавливает s₁. Всё. Игра окончена.
Rejection sampling. Если ||z||∞ >= Y₁ − beta или если младшие биты w − c*s₂ выходят за допустимые границы, подпись отвергается, κ увеличивается, алгоритм возвращается к генерации нового y.
Зачем нужен rejection sampling
Без rejection sampling каждая опубликованная подпись z = y + c*s₁ несла бы статистическую информацию о секрете s₁ через распределение y. Rejection sampling - механизм из парадигмы Fiat-Shamir with Aborts (Lyubashevsky, 2009) - гарантирует, что распределение принятых z неотличимо от равномерного на допустимом множестве и не зависит от s₁.Инвариант держится ровно до тех пор, пока y полностью скрыт от наблюдателя. Утечка частичной информации о y - через side-channel (энергопотребление, тайминги кэша, электромагнитное излучение) или через программный баг - превращает публичные подписи в систему уравнений с секретом. И тут начинается самое интересное.
Утечка рандомности ML-DSA как задача Integer LWE
Работа "From Regression to Prior-Aware Inference: Solving the ILWE Family in Randomness Leakage Attacks against ML-DSA" (arxiv.org/html/2607.05921v1) формализует атаку через утечку рандомности как двухэтапную процедуру:Этап 1 - конструирование ILWE-инстанса из утечки и публичных подписей. Этап 2 - решение инстанса солвером для восстановления s₁.
Предшествующие работы копали первый этап: как построить систему уравнений при разных моделях утечки. Систематический анализ влияния солвера на второй этап - отсутствовал.
Как утечка бит превращается в уравнения
Берём одну подпись с откликом z = y + c*s₁. Допустим, атакующий знает k старших бит каждого коэффициента y. Тогда y = ŷ + ε, где ŷ - известная аппроксимация, |ε| < 2^(b-k) для b-битных коэффициентов. Подстановка даёт:z − ŷ = ε + c*s₁
Левая часть известна, c публикуется как часть подписи, s₁ - неизвестный секрет, ε - ограниченный шум. Это задача Integer LWE. Из N подписей с утечкой строится система из N таких соотношений. Красиво, правда?
Три варианта ILWE
По классификации из arxiv.org/html/2607.05921v1, в зависимости от модели утечки возникают три варианта:OILWE (Ordinary ILWE) - базовая модель с известной матрицей, вектором и неизвестными секретом и шумом. Эталон для калибровки солверов.
FS-ILWE (Fiat-Shamir ILWE) - возникает при побитовой утечке рандомности y. Утечка одного бита на позиции j коэффициента y через уравнение z = y + c*s₁ даёт одно целочисленное соотношение с секретом. Отличие от OILWE - неоднородность шума: каждое уравнение привязано к конкретной позиции бита и конкретному challenge c, дисперсия пляшет от строки к строке.
CILWE (Concealed ILWE) - возникает при утечке информации о нулевых коэффициентах y. Если side-channel позволяет идентифицировать коэффициенты y, равные нулю (через профилирование энергопотребления), то для таких позиций z_i = c_i * s₁ - точное уравнение без шума. Но профилирование неидеально: часть идентифицированных "нулей" на самом деле ненулевые (concealment). При concealment rate выше 0.9 задача резко усложняется - ложные нули превращаются в грубые выбросы в системе уравнений. И вот тут выбор солвера решает всё.
Солверы key recovery: три класса подходов
Центральный результат работы на arxiv.org/html/2607.05921v1 - выбор солвера для ILWE-инстанса определяет практическую осуществимость атаки не менее, чем качество самой утечки. Предшествующие исследования использовали ad-hoc солверы под конкретные модели утечки без систематического сравнения. Авторы это исправили.Регрессия наименьших квадратов (OLS и L₁-эстиматоры). Решение в вещественных числах z* = argmin ||Az − b|| с последующим округлением до ближайших целых из допустимого множества. Подход прост и дёшев вычислительно, но требует значительного запаса уравнений для корректного округления, особенно при высоком шуме. Для реализации хватит
numpy.linalg.lstsq и координатного округления - ничего экзотического.Робастная регрессия (Huber, Cauchy). Устойчива к выбросам. В контексте CILWE выбросы - те самые ложные "нулевые" коэффициенты, создающие грубые ошибки в отдельных уравнениях. Cauchy-регрессия с её тяжелохвостым профилем функции потерь держится при concealment rate выше 0.9, где OLS и Huber разваливаются.
Prior-aware дискретная инференция (Belief Propagation, жадный поиск, hill-climbing). Принципиально другой зверь. BP работает непосредственно в конечном дискретном пространстве секретов - никакого округления вещественных чисел. Для ML-DSA коэффициенты s₁ лежат в малом множестве: при n = 2 это {−2, −1, 0, 1, 2}, при n = 4 - {−4, ..., 4}. BP строит графовую модель (factor graph), где каждый узел-переменная соответствует коэффициенту s₁, а каждый фактор-узел - одному уравнению из ILWE-инстанса. Априорное знание о дискретности и ограниченности коэффициентов зашито прямо в сообщения, которые гоняются по графу.
Результаты: BP снижает порог атаки на порядки
Экспериментальные данные из arxiv.org/html/2607.05921v1 по трём уровням безопасности ML-DSA (44, 65, 87):| Модель | BP vs baseline | Эффект |
|---|---|---|
| FS-ILWE, noise-free | BP vs OLS | На 1-2 порядка меньше информативных соотношений |
| FS-ILWE, noisy | BP vs OLS | Кратное снижение; расширение диапазона атакуемых позиций бит |
| CILWE, concealment < 0.9 | BP vs Cauchy | BP эффективнее |
| CILWE, concealment > 0.9 | BP vs Cauchy | Cauchy стабильнее |
Снижение на один-два порядка (10-100*) по числу необходимых информативных соотношений - это граница между "теоретически интересно" и "можно сделать руками". Если побитовая утечка через side-channel даёт один информативный бит на подпись, OLS потребует тысячи наблюдений, а BP - десятки. BP расширяет и диапазон атакуемых позиций: OLS работает только с утечкой старших бит (высокое отношение сигнал/шум), BP вытягивает секрет при утечке более младших позиций - там, где OLS уже сдаётся.
Программные баги как канал полной утечки рандомности
Side-channel атаки требуют физического или микроархитектурного доступа к подписывающей системе. Работа Бернстайна (cr.yp.to/papers/mldsa-20260601.pdf) бьёт с другой стороны: программные ошибки в реализациях ML-DSA, приводящие к полной (не частичной) утечке или структурному повреждению рандомности.
AABBCC-баг: парные коэффициенты в маске y
Ошибка в коде распаковки коэффициентов полинома y, при которой коэффициенты дублируются парами: y = (a, a, b, b, c, c, ...) вместо (a, b, c, d, e, f, ...). Дефект возникает при неправильной индексации в цепочке битовых операций - типичная ситуация, когда copy-paste-modify одного индексного выражения приводит к удвоению. По данным из анализа на postquantum.com, Бернстайн показал, что в OpenSSL-реализации ML-DSA цепочка bitwise-операций содержит место, где замена одного вычитания на побитовое AND обнуляла бы каждый второй коэффициент (паттерн A0B0C0) - столь же эксплуатируемый вариант.Атака Бернстайна: из публичного ключа и двух подписей строится система линейных уравнений над кольцом полиномов R_q, решение которой даёт четыре секретных полинома s₀, s₁, s₂, s₃. Демонстрация отработала на 50 последовательно сгенерированных случайных ключах - без осечек.
И вот что по-настоящему неприятно: подписи с AABBCC-багом валидны. Они проходят стандартную верификацию, known-answer тесты (если тесты сгенерированы кодом с тем же багом) и кросс-библиотечные interop-проверки. Обе официальные реализации Dilithium 1.0 в 2017 году содержали баг этого класса, обнаруженный только при кросс-имплементационном сравнении с дерандомизированным RNG. Две из двух - 100%.
Nonce reuse: ML-DSA-аналог PS3 ECDSA
Вторая атака эксплуатирует повторное использование вектора y в двух подписях - прямой аналог nonce reuse в ECDSA (Sony PlayStation 3, 2010), адаптированный к кольцу полиномов.Если (z₁, c₁) и (z₂, c₂) подписаны с одним и тем же y, вычитание даёт:
z₁ - z₂ = (c₁ - c₂) * s₁
Секрет s₁ восстанавливается полиномиальным делением в R_q при условии обратимости (c₁ - c₂). Для случайных challenge-полиномов ML-DSA с τ ненулевыми коэффициентами +-1 разность имеет коэффициенты в {−2, −1, 0, 1, 2} и обратима в R_q = Z_q[x]/(x^256 + 1) с высокой вероятностью.
Python:
# Концептуальная демонстрация nonce reuse key recovery
# Среда: SageMath, q = 8380417 (ML-DSA-44)
Rq = PolynomialRing(GF(8380417), 'x').quotient('x^256 + 1')
delta_z = Rq(z1 - z2) # разность откликов (публична)
delta_c = Rq(c1 - c2) # разность challenge-полиномов
s1_recovered = delta_z * delta_c.inverse_of_unit()
# Результат: полный секрет s1, <1 сек на laptopПрогноз масштаба: 25% библиотек с критическим багом
Бернстайн строит статистическую модель на основе эмпирических данных Blessing, Specter и Weitzner (2021): 312 CVE в восьми крупных криптографических библиотеках за 2010-2020 годы, показатель 0.45-1.19 CVE на 1000 строк добавленного кода, средний эксплуатируемый lifetime 5.13 года. Экстраполяция из cr.yp.to/papers/mldsa-20260601.pdf: 50 библиотек ML-DSA * 2000-4000 строк специфичного кода = 100 000-200 000 строк. При наблюдаемых исторических показателях - порядка 100 уязвимостей. При доле критических ~1/8, около 25% библиотек выпустят первый релиз с хотя бы одной уязвимостью класса "подделка подписей".Для сравнения: за 10+ лет существования порядка 100 библиотек Ed25519 зафиксировано 1-2 критические уязвимости. Разница - на порядки.
Дополнительное свидетельство: анализ на postquantum.com ссылается на работу Kobeissi ("Verification Theatre"), которая нашла 13 уязвимостей в Cryspen's libcrux - библиотеке с декларированной формальной верификацией, используемой Firefox и OpenSSH. Четыре бага сидели внутри периметра формальной верификации, включая неправильную спецификацию умножения в ML-DSA, делавшую аксиоматизированные AVX2-доказательства несостоятельными. Формально верифицировано, а баг - вот он.
Операционный контекст: маппинг на MITRE ATT&CK
Атаки на рандомность ML-DSA формируют цепочку через несколько техник.Основная цепочка: Exploitation for Credential Access (T1212) -> Private Keys (T1552.004). Атакующий эксплуатирует криптографическую слабость реализации ML-DSA для восстановления закрытого ключа подписи. Результат - подпись произвольных сообщений от имени жертвы: сертификаты, firmware, аутентификационные токены.
Supply chain сценарий: Reduce Key Space (T1600.001). Целенаправленное внедрение уязвимой реализации (подмена криптографической библиотеки, внесение AABBCC-бага при контрибуции в open-source) маппится на T1600.001 (Defense Impairment). Все ключи, сгенерированные скомпрометированной библиотекой, восстановимы a priori.
Resource Development. Разработка PoC для конкретной реализации - Exploits (T1587.004). Идентификация уязвимой библиотеки в инфраструктуре цели - Vulnerabilities (T1588.006).
Контекст применимости: атака через программные баги работает удалённо - достаточно получить две подписи от целевой системы через любой публичный канал (TLS handshake, подписанное обновление, подписанный JWT). Атака через side-channel утечки требует микроархитектурного или физического канала к подписывающей системе: embedded-устройства, HSM с совместным размещением, облачные инстансы с shared tenant-моделью.
Что проверять в реализациях ML-DSA
Hedged vs детерминированная подпись
Согласно IETF draft (draft-connolly-cfrg-ml-dsa-security-considerations-02), hedged (рандомизированная) подпись - единственный безопасный режим в средах с риском fault injection или side-channel. В hedged-режиме свежая рандомность rnd подмешивается к K и μ для генерации p', что предотвращает полное повторение nonce при fault injection и маскирует зависимость p' от секретного K. При отказе RNG (rnd = все нули) hedged-режим корректно деградирует до детерминированного - совместимость сохраняется без катастрофической потери безопасности.Формат ключа
FIPS 204 определяет компактный формат секретного ключа - 32-байтный seed ξ, из которого детерминированно восстанавливаются все расширенные компоненты (ρ, K, tr, s₁, s₂, t₀). Как указывает IETF draft, seed-формат исключает создание malformed key: изменение одного бита seed полностью меняет весь расширенный ключ, не давая независимо подбирать отдельные секретные компоненты. Расширенные компоненты можно кэшировать на время операций подписи, но защищать их нужно так же, как seed.Стратегия тестирования
Стандартные functional и known-answer тесты не ловят баги класса AABBCC и nonce reuse. По анализу из postquantum.com, надёжно работают только:- Кросс-имплементационное сравнение - подписание идентичных (seed, message) дерандомизированным RNG в двух независимых реализациях с побитовым сравнением результата
- Статистическое профилирование коэффициентов y - проверка на пары-дубликаты, нулевые паттерны, аномалии в распределении
- Фаззинг индексов распаковки - целенаправленная мутация индексных переменных в bitwise-операциях, наиболее подверженных copy-paste ошибкам
Оценка порога утечки
Формула n*(b−l)/l даёт верхнюю оценку информационной ёмкости побитовой утечки, где n - размерность секрета, b - битность коэффициентов y, l - число утекших бит на коэффициент. Это оценка сверху: реальное необходимое число подписей N зависит от блочного размера BKZ при lattice reduction и конкретного солвера. С учётом результатов BP (снижение на один-два порядка относительно OLS) практический порог для ML-DSA-44 при утечке одного старшего бита - десятки подписей вместо тысяч.Дополнительные направления: implicit hints и rejection leakage
Ситуация с ML-DSA напоминает 2009-2012 годы, когда nonce reuse в ECDSA ломал одну реализацию за другой - от Sony PS3 до Bitcoin-кошельков. Разница - в масштабе attack surface: в ECDSA один скаляр k, одно уравнение, одна точка отказа. В ML-DSA - вектор y на 256*l коэффициентов, rejection loop с утечкой через тайминги, bitwise-распаковка с десятками мест для индексной ошибки. Модель Бернстайна (25% библиотек с критическим багом на старте) - не алармизм, а экстраполяция: две из двух первых реализаций Dilithium 1.0 в 2017 году содержали эксплуатируемый дефект. Результаты по BP-солверам (arxiv.org/html/2607.05921v1) меняют оценку side-channel угрозы кардинально: то, что требовало тысяч наблюдений подписей, теперь укладывается в десятки - вполне реалистичный объём для embedded-устройств или shared cloud. Гибридная схема Ed25519+ML-DSA, при всём увеличении размера подписей, остаётся единственным инженерным ответом, не требующим слепого доверия к качеству каждой из 50 выходящих реализаций. Кто хочет собрать lattice-атаку от алгебраической слабости до полного key recovery руками - crypto-задачи на HackerLab.pro (https://hackerlab.pro) дают возможность прочувствовать разницу между формулой на бумаге и работающим эксплойтом.
Последнее редактирование модератором:
