dxdt.ru: занимательный интернет-журнал

Dual EC DRBG (“Сдвоенный детерминированный генератор случайных битов на эллиптической кривой”) – нашумевшая схема генератора псевдослучайных чисел, в которой встроен (потенциальный) математический бэкдор. Несмотря на сразу же возникшие подозрения о бэкдоре, эта схема была без проблем стандартизована NIST в 2006-2007 годах и достаточно широко использовалась. Соответствующий стандарт позже официально отозван NIST.

В криптографии постоянно требуются случайные числа. Получение действительно случайных чисел сопряжено с большими проблемами, которые начинаются с того момента, что всякая попытка строго определить и гарантировать случайность значений неминуемо сталкивается с философскими трудностями, корни которых находятся в области интерпретации реальности. Поэтому на практике гарантировать случайность невозможно, но есть различные модели и допущения, позволяющие приблизиться к “строгой случайности” с точки зрения вычислительных возможностей. (Да, есть “квантовые” предложения – но они сугубо теоретические, и тоже подразумевают некоторую модель – модель “квантовой механики”.) Естественно, только из этого не следует вывод о том, что все практические случайные значения предсказуемы, но зато следует другой вывод – о допустимости использования алгоритмических генераторов псевдослучайных чисел: алгоритмов, выдающих такие последовательностей значений, которые вычислительно неотличимы от истинно случайных. (Оставим понятие “истинно случайный” – за скобками, отметив, что, – по современным представлениям, – генератор “истинно случайных” значений должен быть исключительно аппаратным.)

Важнейшей особенностью криптографических генераторов (псевдо)случайных чисел является то, что выдача генератора детерминирована – то есть, выдаваемые значения определяются внутренним состоянием. Именно этот аспект служит фундаментом для построения бекдора в Dual EC DRBG. Криптографические генераторы псевдослучайных чисел имеют важнейшее значение не только для теоретической, но и для прикладной криптографии – это краеугольный камень всех практических систем криптографической защиты.

Несмотря на то, что с точки зрения теории криптографии схема, о которой идёт речь, предоставляет потенциальный бэкдор, её свойства можно трактовать и как инструмент “депонирования” ключей – то есть, при реализации конкретного экземпляра генератора выбираются такие параметры, что уполномоченная сторона может его “взламывать”. Однако уже сам факт того, что возможно провести в статус стандарта такую схему генератора, которая содержит механизм построения бэкдора на уровне алгоритма и описание этого бэкдора опубликовано на момент стандартизации, имеет большое историческое значение. Ещё более показательна и интересна сугубо математическая часть данного бэкдора. Настоящая статья посвящена именно математике бэкдора и в деталях объясняет то, почему он работает.

По сути, бэкдор в Dual_EC_DRBG – это реализация протокола Диффи-Хеллмана (DH) на эллиптической кривой: секретный ключ находится у стороны, контролирующей бэкдор через параметры протокола, что позволяет этой стороне получать внутреннее состояние генератора псевдослучайных чисел, наблюдая его выдачу. Знание внутреннего состояния приводит к раскрытию всей последующей выдачи генератора. При этом, математически, пользователь Dual EC DRBG неявно выполняет обмен DH с контролирующей параметры генератора стороной. Это важное свойство штатных схем построения “надёжных бэкдоров”: доступ к бэкдору должен быть только у той сторны, которая знает секретный параметр – секретный ключ. Есть и другое важное свойство: если секретный параметр не был раскрыт, то строго доказать, что бэкдор действительно встроен в конкретную реализацию – нельзя. Это не отменяет возможности тсрогого описания для механизма такого бэкдора.

Итак, в Dual EC DRBG, без знания секретного параметра раскрыть внутреннее состояние генератора вычислительно трудно, потому что базовые функции протокола – односторонние. Поэтому, если оставить за скобками секретный параметр, то протокол полностью соответствует общепринятой схеме.

Посмотрим на типовую схему построения программного генератора псевдослучайных чисел. Такие генераторы можно строить на базе двух односторонних функций и цепочки внутренних состояний. Одна из функций переводит текущее внутреннее состояние в следующее, а вторая – извлекает значение из текущего состояния и выводит его в сторону пользователя.

На схеме: S_n – внутренние состояния генератора; φ() – функция, преобразующая состояние S_n в S_n+1; ξ() – функция, преобразующая состояние S_n в выдачу генератора B_n на данном шаге. Биты пошаговой выдачи B_n могут конкатенироваться для получения псевдослучайной последовательности нужной длины (на схеме: RND[…]) – это типовой способ прикладного использования генератора.

Криптографические генераторы псевдослучайных чисел, помимо общих “статистических” требований к неотличимости выдачи от случайной, имеют ряд особенностей. Прежде всего – выдача должна быть необратимой. А именно: состояния S_n являются секретными параметрами, поскольку позволяют раскрыть будущую выдачу генератора. При этом выдача генератора (B_n) на каждом шаге – публична. Из этого нетрудно сделать вывод, что функции φ и ξ должны быть односторонними (однонаправленными – по значению сложно определить аргумент): если это не так, то по публично доступным данным (B_n) легко вычислить состояние генератора. В чём и состоит логический смысл описываемого бэкдора.

Почему односторонней должна быть и функция φ, которая переводит текущее внутреннее состояние в следующее? Это нужно для того, чтобы по утекшей информации о внутреннем состоянии на каком-то шаге было вычислительно сложно восстановить предыдущую выдачу генератора. Одно из базовых требований к криптографически стойким генераторам псевдослучайных чисел состоит в минимизации возможностей по раскрытию данных. Например, если есть бэкдор, позволяющий обратить ξ, то, при условии обратимости φ, взяв любую точку можно раскрыть сколько угодно данных – и предыдущие, и следующие. При этом обратимость ξ может являться следствием не бэкдора, а обычной уязвимости, в том числе, уязвимости реализации алгоритма. Предположим, эта уязвимость ξ срабатывает лишь на каких-от редких данных: соответственно, если подобрать такие данные удалось, но φ осталась необратимой, атакующий сможет вычислить только следующие состояния генератора и все предыдущие секреты останутся защищены.

Математической особенностью описываемого бэкдора является то, что он вовсе и не позволяет обратить функции ξ и φ – они остаются односторонними, но бэкдор открывает возможность простого вычисления следующего внутреннего состояния генератора по известной выдаче ξ. Это возможно потому, что алгоритм содержит дополнительную структуру, связывающую функции ξ и φ.

Псевдослучайная выдача в криптографических протоколах постоянно используется в открытом виде. Например, в открытом виде передаются векторы инициализации для схем зашифрования (GCM и пр.), псевдослучайные векторы в сообщениях TLS (поля ClientRandom и ServerRandom) и др. Поэтому нетрудно извлечь значения из трафика, сопоставить их с выдачей генератора псевдослучайных чисел, раскрыть внутреннее состояние генератора и получить последующие биты выдачи, которые, например, были использованы тем же приложением для получения секретных ключей шифров, защищающих трафик – это позволит восстановить секретные ключи и расшифровать трафик в пассивном режиме.

Dual EC DRBG работает на эллиптической кривой (над конечным полем), а в качестве односторонних функций использует умножение точки эллиптической кривой на скаляр: x∘P. Далее умножение на скаляр обозначается “блобом” (∘). Стойкость к обращению здесь основана на задаче дискретного логарифмирования: то есть, по значению Q = x∘P – вычислительно трудно найти x.

Вспомним, что умножение на скаляр – обычное для эллиптической криптографии последовательное сложение точки кривой с самой собой. Сложение – операция, которая введена на точках кривой. А именно: точкой кривой называется пара (X, Y) значений “координат”, соответствующих уравнению кривой. Здесь X и Y – это элементы подлежащего конечного поля, которое входит в параметры криптосистемы. В данном конкретном случае (например, для кривой P-256) используемое конечное поле – это вычеты, то есть “остатки” по модулю простого числа. Сложение точек P + Q = R позволяет по паре координат точки Q (X_Q, Y_Q) и паре координат точки P (X_P, Y_P) Получить координату точки R (X_R, Y_R). Скаляр – это целое число. Умножение на скаляр 3 означает, что точка складывается сама с сбой в трёх экземплярах: 3∘P = P + P + P (плюс – это сложение точек). По такому сложению точки всякой эллиптической кривой всегда образуют группу (по определению эллиптической кривой).

В алгоритме Dual EC DRBG используется две точки кривой: P и Q. Точка P – задаёт последовательность внутренних состояний. Внутреннее состояние S_n в Dual EC DRBG – целое число, которое соответствует координате X точки кривой, полученной умножением P на значение предыдущего состояния, как на скаляр. Вторая точка, Q – задаёт “ответвления”, то есть, выдачу генератора по каждому из состояний, и используется в качестве основания на каждом шаге. Ниже представлена упрощённая схема Dual EC DRBG.

На этой схеме: S_n – внутреннее состояние; для получения следующего состояния из текущего – точка P умножается на значение состояния (скаляр: S_n∘P), а координата X получившейся точки – выводится в качестве нового состояния генератора; для вывода случайных значений – вторая точка, то есть – точка Q, умножается на состояние (S_n∘Q) и выводится координата X получившейся точки. То есть, используется две одинаковых функции с разным основанием: P и Q. Раз стойкость этих функций основана на дискретном логарифмировании, то они односторонние, как и требуется.

Математический смысл бэкдора не нарушает стойкость конкретных операций с точками P и Q, он несколько хитрее и строится на в соотношении между точками P и Q. Допустим, атакующей стороне известно такое значение δ, что P = δ∘Q. Выдача генератора – это X-координата точки S_n∘Q. Атакующий находит подходящую Y-координату, подставив значение в уравнение кривой (точек с подходящими координатами будет две, алгоритм знак координаты Y не различает, но выбор точки, очевидно, не представляет труда). Таким образом атакующий легко восстанавливает точку кривой, подходящую для выдачи генератора. Далее – умножаем на δ.

δ∘(S_n∘Q) = S_n∘(δ∘Q) = S_n∘P   (1)

Рассмотрим формулу (1) подробнее. Почему она работает? Потому что скаляры – это целые числа. Из-за коммутативности группы точек кривой к скалярам применимы арифметические свойства целых чисел. В алгебре такая конструкция называется ℤ-модулем. Всякая коммутативная группа является ℤ-модулем. (Некоторые алгебраисты из-за этого даже не считают коммутативные группы “настоящими” группами.) Применительно к эллиптической кривой: 3∘P = P + P + P, а 5∘P = P + P + P + P + P. Но тогда (3+2)∘P = 5∘P = P + P + P + P + P, что следует из свойств групповой операции – просто поставим скобки: (P + P) + (P + P + P), получив, таким образом, две точки (P + P) = 2∘P и (P + P + P) = 3∘P. 3∘P + 2∘P = 5∘P. Обратите внимание, что здесь знак “плюс” используется в двух значениях: и для обозначения сложения точек кривой, и для обозначения привычного сложения в целых числах (3+2). А раз схема работает для сложения целых чисел, то она обязательно работает и для умножения целых чисел, потому что умножение в целых числах можно построить через сложение (собственно, при корректном преобразовании 0 и 1, сложение и умножение в целых числах просто могут быть переведены одно в другое, как операции). Но тогда и (3*2)∘P = (P + P) + (P + P) + (P + P) = 3∘(2∘P) = 6∘P. Что и используется в формуле (1), вместе с коммутативностью умножения в целых числах: 2 * 3 = 3 * 2.

Таким образом, атакующая сторона, которая знает секретный скаляр δ, получила значение следующего состояния генератора, вычислив Χ-координату точки S_n∘P (см. схему). Формула (1) вообще очень похожа на реализацию протокола Диффи-Хеллмана (DH) на эллиптической кривой. То есть, пользователь генератора псведослучайных чисел, можно сказать, обменялся с атакующей стороной открытыми параметрами Диффи-Хеллмана. А именно: открытый параметр атакующей стороны, статический ключ, зашит в константы протокола – P = δ∘Q, где секретный ключ – δ; открытый параметр DH пользователя – это динамическая выдача основного алгоритма – S_n∘Q, где секретный ключ S_n. “Открытые параметры DH” пользователя атакующая сторона наблюдает в трафике. Важное отличие от практического DH состоит в том, что “общий секрет” тут не должен становиться “общим” с атакующей стороной.

Итак, для внедрения бэкдора нужно выбрать такие P и Q, что P = δ∘Q. Полученные точки – это параметры конкретной реализации алгоритма, но они могут быть закреплены в стандарте (что и было сделано). Но в спецификации Dual EC DRBG для кривой P-256 в качестве точки P строго указана базовая точка группы кривой, которая используется в спецификации P-256. То есть, произвольно выбрать P нельзя. Оказывается, в том случае, если одна из точек P или Q заранее строго задана, то определить нужное значение δ можно при помощи вычисления мультипликативного обратного по модулю порядка группы точек. Важно, чтобы порядок был простым числом. Но это стандартная практика для прикладной криптографии. Например, для кривой P-256 – соответствующий порядок простой.

Чтобы получить бэкдор, нужно определить δ из P = δ∘Q. Может показаться, что если точка P зафиксирована, – соответственно, выбрать эту точку умножением какой-то точки Q на произвольный скаляр нельзя, – то требуется решить сложную задачу отыскания дискретного логарифма. Но это не так, поскольку мы всё равно можем выбрать произвольную точку Q. Чтобы согласовать точки, возьмём произвольное значение ε в интервале от 2 до порядка группы, генерируемой P, а потом возьмём δ = ε^(-1) по модулю порядка. Пусть порядок P – то есть, количество точек в используемой группе, – это простое число n. Тогда нужно найти ε * δ = 1 (mod n). (Например, 2 – обратный по умножению элемент к 4 по модулю 7, так как 2 * 4 = 1 (mod 7).) Задача нахождения мультипликативного обратного по модулю простого числа здесь вычислительно несложная. Определив δ = ε^(-1), в качестве точки Q выберем ε∘P. Тогда: δ∘Q = δ∘(ε∘P) = (ε^(-1)*ε)∘P = P. Следовательно, мы нашли такое δ, что P = δ∘Q.

То есть, если можно выбрать оба параметра – точки P и Q, – то выбираем так, что P = δ∘Q, а если одна из точек зафиксирована – выбираем δ = ε^(-1) по модулю (простого) порядка группы точек, это всегда можно сделать из-за особенностей спецификации: подлежащие группы имеют простой порядок. (Не забывайте, что в формулах выше используется два умножения – умножение точки на скаляр и умножение целых чисел (δ = ε^(-1); 1 = ε^(-1)*ε). Это работает потому, что скаляры – целые числа, но по модулю порядка группы.)

В Dual EC DRBG битовый вывод генератора, – то есть, X-координата S_n∘Q, – урезается: из него удаляются 16 старших битов. Это означает, что прямо использовать результат для вычисления координат исходной точки нельзя. Но 16 бит можно быстро перебрать, проверяя, для всех значений подряд, лежит ли на кривой точка с соответствующей X-координатой. Вычисление значений по уравнению кривой тоже не составляет проблемы – уравнение известно, а используемые там операции обязательно быстрые.

Естественно, полученная перебором точка может оказаться неверной. То есть, точка не будет являться S_n∘Q. На этом шаге “через бэкдор” у атакующего нет никакого способа проверить, что точки совпали. Но это не сильно затрудняет атаку. Значения секретного состояния нужно вычислить для всех возможных точек, которые соответствуют сокращённому битовому значению, а результат по каждой точке – сопоставить с дальнейшим анализом трафика. Например, если выдача генератора используется для получения секретного ключа, то выбрать его верное значение можно при помощи пробного расшифрования. В любом случае, анализ 2^16 числовых значений при помощи перебора не представляет здесь вычислительной проблемы.

В ранней версии стандарта NIST на Dual EC DRBG реализация использовала подмешивание дополнительной маски на каждом шаге вычисления псевдослучайных чисел. Это делало описанный бэкдор нерабочим. Однако стандарт был быстро обновлён, точка подмешивания дополнительной маски перенесена, и использование бэкдора стало снова возможным. Поэтому данная особенность здесь не рассматривается.

Проблема алгоритма Dual EC DRBG, как криптографического генератора псевдослучайных чисел, помимо низкой производительности, в том, что внутри его конструкции есть жесткая структура, зависящая от внешних параметров. Из-за алгебраических свойств эллиптических кривых, в практической реализации – точки P и Q всегда связаны. Да, иногда, если специально постараться, они могут быть получены способом, дающим некоторую гарантию того, что связующий скаляр никому не известен. Либо, P и Q может генерировать конкретный пользователь, в качестве параметра для своей локальной версии генератора. Стандарт NIST разрешал такой вариант, но не рекомендовал его, а для соответствия строгим требованиям FIPS допускались только параметры из спецификации.

(Это расширенная версия статьи, которую я недавно опубликовал на “Хабре”.)

Адрес записки: https://dxdt.ru/2025/06/30/15791/