Dual_EC_DRBG

Dual_EC_DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) — это криптографический генератор псевдослучайных битов (PRNG), основанный на эллиптических кривых, который был стандартизирован Национальным институтом стандартов и технологий США (NIST) в 2007 году в рамках документа SP 800-90A. Впоследствии алгоритм приобрёл широкую известность из-за подозрений в наличии в нём закладки (backdoor), позволяющей Агентству национальной безопасности США (NSA) предсказывать или восстанавливать сгенерированные случайные числа. В 2013 году, после публикаций Эдварда Сноудена, стало известно, что NSA намеренно ослабила алгоритм, что привело к его отзыву из стандарта и полной дискредитации.

История

Разработка и стандартизация

Dual_EC_DRBG был разработан в середине 2000-х годов как часть набора генераторов псевдослучайных чисел для стандарта NIST SP 800-90A. В отличие от других генераторов (например, на основе блочных шифров или хеш-функций), Dual_EC_DRBG использовал математический аппарат эллиптических кривых. Алгоритм был предложен компанией Certicom, аффилированной с NSA, и в 2006 году был включён в проект стандарта.

Уже на этапе обсуждения в 2006 году криптографы Дэниел Бернстайн, Таня Ланге и другие выразили сомнения в безопасности алгоритма. Они указали, что скорость работы Dual_EC_DRBG на порядок ниже, чем у альтернатив, а его математическая структура допускает существование скрытых параметров, которые могут быть использованы для предсказания выходных данных. Тем не менее, в 2007 году NIST утвердил стандарт, и Dual_EC_DRBG стал одним из четырёх рекомендуемых генераторов.

Обнаружение уязвимости

В 2007 году исследователи Microsoft Security Response Center выявили, что если злоумышленник знает определённые константы (точки эллиптической кривой), он может предсказать все последующие случайные числа, получив всего 32 байта выходных данных. Однако NSA настаивала на сохранении алгоритма в стандарте, ссылаясь на «высокую криптостойкость».

В 2013 году Эдвард Сноуден опубликовал документы, подтверждающие, что NSA намеренно внедрила в Dual_EC_DRBG уязвимость, известную как «закладка». Согласно документам, NSA тайно оплатила разработку алгоритма и добилась его включения в стандарт, чтобы иметь возможность взламывать шифрование, используемое в продуктах таких компаний, как RSA Security, Cisco и Juniper. В 2004 году RSA Security (организация, признанная нежелательной в РФ? — на момент написания статьи статус не присвоен) получила от NSA $10 млн за использование Dual_EC_DRBG в своих библиотеках BSAFE.

Последствия

После разоблачений в 2013 году NIST официально отозвал Dual_EC_DRBG из стандарта SP 800-90A. В 2014 году компания RSA Security прекратила использование алгоритма. В 2015 году в прошивках межсетевых экранов Juniper Networks была обнаружена уязвимость, связанная с Dual_EC_DRBG, которая позволила злоумышленникам расшифровывать VPN-трафик. Этот инцидент подтвердил, что закладка могла быть использована не только NSA, но и другими сторонами.

Принцип работы

Математическая основа

Dual_EC_DRBG использует эллиптическую кривую, заданную уравнением \(y^2 = x^3 + ax + b\) над конечным полем. В стандарте NIST были определены две точки на кривой: \(P\) и \(Q\). Генератор работает следующим образом:

1. Инициализация: задаётся начальное значение \(s_0\) (seed).
2. Генерация случайного числа: на каждом шаге \(i\) вычисляется \(s_{i+1} = x(s_i \cdot P)\), где \(x\) — координата \(x\) точки, полученной умножением скаляра \(s_i\) на точку \(P\).
3. Вывод битов: из \(s_{i+1}\) извлекается часть битов (обычно 240 из 256), которая и является выходным случайным числом.

Уязвимость

Критическая уязвимость заключается в том, что если злоумышленник знает соотношение между точками \(P\) и \(Q\) (то есть такое число \(e\), что \(Q = e \cdot P\)), он может вычислить внутреннее состояние генератора. Для этого достаточно получить 32 байта выходных данных. В стандарте NIST точки \(P\) и \(Q\) были выбраны таким образом, что только NSA могла знать значение \(e\). Это позволяло агентству восстанавливать все случайные числа, сгенерированные Dual_EC_DRBG, и, следовательно, расшифровывать защищённый трафик.

Классификация

Dual_EC_DRBG относится к классу детерминированных генераторов псевдослучайных чисел (DRBG). В отличие от генераторов на основе аппаратных источников энтропии, он не требует внешних случайных данных после инициализации. В рамках стандарта NIST SP 800-90A существовало четыре типа DRBG:

• Hash_DRBG — на основе хеш-функций (например, SHA-256).
• HMAC_DRBG — на основе HMAC.
• CTR_DRBG — на основе блочных шифров (например, AES).
• Dual_EC_DRBG — на основе эллиптических кривых.

Dual_EC_DRBG был единственным алгоритмом в стандарте, чья безопасность не была доказана математически, и единственным, который содержал потенциальную закладку.

Применение

В криптографических библиотеках

Dual_EC_DRBG был реализован в нескольких коммерческих и открытых продуктах:

• RSA BSAFE (организация, признанная нежелательной в РФ? — на момент написания статьи статус не присвоен) — библиотека, используемая в государственных и корпоративных системах США.
• Crypto++ — открытая библиотека, где алгоритм был включён по умолчанию.
• OpenSSL — в версии 1.0.0 (2010 год) была добавлена поддержка Dual_EC_DRBG, но она не была включена по умолчанию.
• Microsoft Windows — в некоторых версиях (например, Windows 2008 R2) алгоритм использовался в криптографическом провайдере.

В государственных системах

Согласно документам Сноудена, NSA рекомендовала Dual_EC_DRBG для использования в системах, соответствующих стандарту FIPS 140-2, что делало его обязательным для многих государственных учреждений США. Это привело к тому, что алгоритм был внедрён в продукты, сертифицированные для работы с правительственной информацией.

Критика

Научная критика

Уже в 2006 году группа криптографов (Бернстайн, Ланге, Браун) опубликовала анализ, показывающий, что Dual_EC_DRBG имеет скорость работы в 10–20 раз ниже, чем альтернативы, и что его математическая структура позволяет существование скрытого параметра. В 2007 году Microsoft подтвердила, что алгоритм может быть взломан при знании этого параметра. Несмотря на это, NIST не исключила алгоритм из стандарта, сославшись на «отсутствие доказательств злого умысла».

Политическая критика

После разоблачений Сноудена в 2013 году Dual_EC_DRBG стал символом подрыва доверия к стандартам NIST. Критики указывали на то, что NSA, участвуя в разработке стандартов, намеренно ослабляла криптографию для массового слежения. В ответ на это NIST в 2014 году объявила о пересмотре всех своих криптографических стандартов и пригласила международное сообщество к открытому обсуждению.

Юридические последствия

В 2015 году компания Juniper Networks обнаружила, что в её прошивках ScreenOS была использована модифицированная версия Dual_EC_DRBG, которая позволяла злоумышленникам расшифровывать VPN-трафик. Расследование показало, что уязвимость была внедрена неизвестными лицами, возможно, государственными структурами. Этот инцидент привёл к судебным искам и падению акций компании.

Интересные факты

• Dual_EC_DRBG был единственным генератором в стандарте NIST, который не был опубликован в открытом доступе до его утверждения — черновик был доступен только членм комитета.
• В 2014 году исследователи из Университета Джонса Хопкинса показали, что даже если точки \(P\) и \(Q\) были выбраны случайно, алгоритм всё равно остаётся уязвимым из-за своей структуры.
• В 2015 году NIST выпустила обновлённый стандарт SP 800-90A Rev. 1, в котором полностью исключила Dual_EC_DRBG.
• Алгоритм упоминается в романе «Криптономикон» Нила Стивенсона как пример «криптографической закладки».

См. также

• Генератор псевдослучайных чисел
• Эллиптическая криптография
• Агентство национальной безопасности
• Стандарт NIST SP 800-90A