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

На "Хабре" недавно опубликован перевод статьи про практическую реализацию бэкдора в Dual EC DRBG, с примерами кода на Python. Но в той публикации, к сожалению, отсутствует объяснение математической части. А математическая часть данного бэкдора очень показательная и интересная. В том числе, с точки зрения истории криптографии. Настоящая статья посвящена именно математике бэкдора и в деталях объясняет то, почему он работает. Для понимания потребуется хотя бы минимальное знакомство с основными понятиями алгебры и криптографии.

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

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

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

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

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

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

Вспомним, что умножение на скаляр - обычное для эллиптической криптографии последовательное сложение точки кривой с самой собой. А именно: точкой кривой называется пара (X, Y) значений "координат", соответствующих уравнению кривой. Здесь X и Y - это элементы подлежащего конечного поля, которое входит в параметры криптосистемы. В данном конкретном случае (например, для кривой P-256) используемое конечное поле - это вычеты, то есть "остатки", по модулю простого числа. Скаляр - это целое число. Умножение на скаляр 3 означает, что точка складывается сама с сбой в трёх экземплярах: (плюс - это сложение точек). По такому сложению точки всякой эллиптической кривой образуют группу (это по определению эллиптической кривой).

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

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

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

Формула (*) из предыдущего абзаца вообще очень похожа на реализацию протокола Диффи-Хеллмана (DH) на эллиптической кривой. То есть, пользователь генератора псведослучайных чисел, можно сказать, обменялся с атакующей стороной открытыми параметрами Диффи-Хеллмана. А имено: открытый параметр атакующей стороны, статический ключ, зашит в константы протокола - , секретный ключ - δ; открытый параметр пользователя - динамическая выдача основного алгоритма, - , где секретный ключ . Выдачу "открытых ключей DH" пользователя атакующая сторона наблюдает в трафике. Важное отличие от практического DH состоит в том, что "общий секрет" тут не должен становиться "общим" с атакующей стороной.

Если одна из точек P, Q заранее задана, то определить нужное значение δ можно при помощи вычисления мультипликативного обратного по модулю порядка группы точек. Порядок, на практике, простое число, поэтому вычислить такой обратный элемент нетрудно. В Dual EC DRBG для кривой P-256 в качестве точки P указан генератор группы кривой - точка, указанная в спецификации P-256. Чтобы получить бэкдор, нужно определить δ из .

Может показаться, что если P зафиксирована, а выбрать эту точку умножением Q на произвольный скаляр нельзя, то требуется решить сложную задачу отыскания дискретного логарифма. Но это не так, поскольку мы всё равно можем выбрать произвольную точку Q. Чтобы согласовать точки, выберем произвольное значение ε в интервале от 2 до порядка группы, генерируемой P, а потом возьмём по модулю порядка (простая задача). В качестве точки Q выберем . Тогда: .

То есть, если можно выбрать оба параметра - точки P и Q, - то выбираем так, что , а если одна из точек зафиксирована - выбираем по модулю (простого) порядка группы точек, это всегда можно сделать из-за особенностей спецификации: подлежащие группы имеют простой порядок. (Обратите внимание, что в формулах выше используется два умножения - умножение точки на скаляр и умножение целых чисел . Это работает потому, что скаляры - целые числа, но по модулю порядка группы.)

В Dual EC DRBG битовый вывод генератора, - то есть, X-координата , - урезается: из него удаляются 16 старших битов. Это означает, что прямо использовать результат для вычисления координат исходной точки нельзя. Но 16 бит можно быстро перебрать, проверяя, для всех значений подряд, лежит ли на кривой точка с соответствующей X-координатой. Вычисление урванения кривой тоже не составляет проблемы. Естественно, полученная перебором точка может оказаться неверной. То есть, точка не будет являться . На этом шаге "через бэкдор" у атакующего нет никакого способа проверить, что точки совпали. Но это не сильно затрудняет атаку. Значения секретного состояния нужно вычислить для всех возможных точек, которые соответствуют сокращённому битовому значению, а результат по каждой точке - сопоставить с дальнейшим анализом трафика. Например, если выдача генератора используется для получения секретного ключа, то выбрать его верное значение можно при помощи пробного расшифрования. В любом случае, анализ 2^16 числовых значений при помощи перебора не представляет здесь вычислительной проблемы.

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

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

Литература

• Bernstein, Lange, Niederhagen. Dual EC: A Standardized Back Door

• NIST SP 800 90A, 2012.