Инцидент с бэкдором Dual EC DRBG

Детерминированный генератор случайных битов на основе двух эллиптических кривых (Dual EC DRBG) был одним из четырёх механизмов DRBG, стандартизированных NIST в SP 800-90A (2006). Он генерирует псевдослучайные биты с помощью двух точек эллиптической кривой P и Q: на каждом шаге вычисляется r_i = x(s_i * P) (координата x результата умножения точки), затем s_{i+1} = x(r_i * P) обновляет состояние, а output = x(r_i * Q) генерирует биты. Генератор выглядел правдоподобно в академических обозначениях. Он был включён в NIST SP 800-90A, а позднее рекомендован RSA Security как вариант по умолчанию в своей криптографической библиотеке BSAFE, что способствовало его распространению в корпоративном и государственном программном обеспечении.

Закладка в Dual EC DRBG использует соотношение между P и Q. Если противник знает секретный скаляр e такой, что Q = e * P, то, имея любой блок вывода, он может вычислить следующее: из output = x(r * Q) перебрать координату y точки r*Q, затем вычислить r*P = (1/e) * (r*Q) mod n. На основе r*P он может предсказать все будущие результаты и восстановить внутреннее состояние. Знание e и есть закладка — оно эквивалентно дискретному логарифму Q относительно P. Стандарт NIST задавал значения P и Q, не объясняя, как они были выбраны, поэтому невозможно было проверить, что они сгенерированы случайным образом и не содержат секретной закладки.

В августе 2007 года Дэн Шумоу и Нилс Фергюсон представили на секции коротких докладов конференции CRYPTO основополагающую статью под названием «О возможности наличия скрытой лазейки в NIST SP800-90 Dual EC Prng». Они строго доказали, что если кому-либо известно значение e (ECDLP для Q относительно P), то этот человек может предсказать все выходные данные Dual EC DRBG, имея примерно 32 байта выходных данных. Они продемонстрировали это на учебном примере. Их выступление широко обсуждалось в сообществе специалистов по криптографии. Брюс Шнайер написал: «у нас нет возможности узнать, может ли NSA читать выходные данные Dual_EC_DRBG или нет». Несмотря на это предупреждение, Dual EC DRBG оставался в стандарте ещё шесть лет.

В сентябре 2013 года газеты «Нью-Йорк таймс», «Гардиан» и ProPublica опубликовали материалы, основанные на документах, переданных Эдвардом Сноуденом. В них раскрывалось, что NSA тайно внедряла уязвимости в криптографические стандарты. В одном из документов под названием «Проект содействия сбору разведданных» описывалась программа стоимостью 250 миллионов долларов в год, направленная на «тайное влияние» на стандарты шифрования и продукты. Хотя в документе Dual EC DRBG прямо не упоминался, в сочетании с математической демонстрацией Шумоу и Фергюсона это привело сообщество специалистов по криптографии к широко распространённому выводу, что NSA внедрила скрытую лазейку, выбрав P и Q с известным соотношением e, сохранив e в тайне и передав константы в NIST.

В декабре 2013 года Reuters сообщило, что NSA заплатила RSA Security 10 миллионов долларов за то, чтобы Dual EC DRBG стал алгоритмом по умолчанию в криптографическом наборе инструментов BSAFE компании RSA. RSA Security, в то время подразделение EMC, распространяла BSAFE в составе корпоративного программного обеспечения, которым пользовались финансовые учреждения, медицинские компании и государственные подрядчики. В заявлении RSA отрицалось, что компания сознательно внедрила скрытую лазейку, но признавалось принятие контракта. Это открытие нанесло особенно серьёзный ущерб: BSAFE продвигался как продукт для обеспечения безопасности, и клиенты выбирали его именно ради криптографической надёжности. Этот инцидент серьёзно подорвал репутацию RSA Security и привёл к бойкотам конференции RSA в 2014 году.

После разоблачений, связанных со Сноуденом, NIST предпринял несколько действий. В сентябре 2013 года NIST вновь открыл SP 800-90A для публичного обсуждения и рекомендовал не использовать Dual EC DRBG до завершения проверки. В апреле 2014 года NIST опубликовал SP 800-90A, редакцию 1, из которой Dual EC DRBG был полностью удалён — остались только Hash_DRBG, HMAC_DRBG и CTR_DRBG. NIST также начал проверку всех своих криптографических стандартов и руководств, уделив особое внимание тому, не повлияло ли NSA на другие стандарты и не поставило ли их под угрозу. Для повышения прозрачности и участия общественности в будущих усилиях по стандартизации была создана рабочая группа по процессу разработки криптографических стандартов и руководств NIST.

Скрытая лазейка в Dual EC DRBG имела глубокие последствия для доверия сообщества специалистов по криптографии к органам стандартизации. Она показала, что национальное разведывательное ведомство готово намеренно ослаблять криптографические стандарты, используемые во всём мире, затрагивая не только противников, но и союзников, компании и частных лиц. Этот инцидент ускорил распространение открытых алгоритмов, допускающих проверку, с числами, происхождение которых не вызывает подозрений: в SHA-3 используется Keccak с документированным алгоритмом получения констант; BLAKE2 и BLAKE3 получают константы из дробных частей математических констант; в Curve25519 используется простое число 2^255 - 19, специально выбранное так, чтобы его можно было проверить. Генерация параметров эллиптических кривых с «проверяемой случайностью» стала стандартной практикой.

Скандал вокруг Dual EC DRBG сделал популярной концепцию констант «nothing-up-my-sleeve» (NUMS) — криптографических параметров, полученных из общедоступных источников, которые можно проверить и которые не могут содержать скрытых лазеек. Примеры: SHA-2 использует начальные значения хеширования, полученные из квадратных корней первых 8 простых чисел; константы раундов — из кубических корней первых 64 простых чисел. BLAKE2 получает константы из дробных разложений числа π и других математических констант. Ed25519 использует простое число 2^255 - 19 и базовую точку, для которой дискретный логарифм относительно любой другой точки заведомо неизвестен (она выбирается как хеш строки). Благодаря этим практикам любой человек может проверить, что константы не были выбраны с использованием секретной информации.

В декабре 2015 года Juniper Networks раскрыла, что в ScreenOS (операционной системе их межсетевых экранов) с 2012 года присутствовал несанкционированный код. Расследование выявило две скрытые лазейки: первая заменила константу Q в Dual EC DRBG на значение, контролируемое атакующим, что позволило атакующему, знавшему соответствующее e, расшифровывать трафик VPN; вторая находилась в административном пароле SSH. Подмена Q в Dual EC была особенно сложной: Juniper уже использовала нестандартное значение Q, а атакующий заменил его собственным, дважды воспользовавшись структурой скрытой лазейки Dual EC. Это показало, что даже реализации, отклонявшиеся от значений P и Q из NIST, могли быть атакованы любым человеком, разместившим собственное Q.

Инцидент с Dual EC DRBG преподносит несколько уроков. (1) Прозрачность: криптографические параметры должны иметь проверяемое происхождение — к константам без документации их получения следует относиться с подозрением. (2) Проектирование алгоритмов: алгоритмы не должны иметь структур, способных скрывать лазейки (соотношение Q/P в Dual EC не даёт преимуществ в безопасности по сравнению с более простыми конструкциями DRBG). (3) Конфликт интересов: органы стандартизации должны строго регулировать конфликты с разведывательными ведомствами. (4) Проверка сообществом: академическим специалистам по криптографии следует дать возможность поднимать вопросы до публикации стандартов, а не после неё. (5) Бдительность при внедрении: организациям следует проверять, какие DRBG используют их криптографические библиотеки, и заранее удалять нерекомендуемые варианты.

После удаления Dual EC набор рекомендуемых DRBG сформировался вокруг Hash_DRBG, HMAC_DRBG и CTR_DRBG. Сообщество открытого исходного кода также внедрило DRBG, не относящиеся к NIST, для случаев, когда стандартам NIST не доверяют: RNG на основе ChaCha20 (используемые в ядре Линукса начиная с версии 5.17, в OpenBSD и libsodium) широко считаются устойчивыми к скрытым лазейкам, поскольку ChaCha20 — это простой потоковый шифр без структур, допускающих скрытые лазейки. Fortuna (используемая в FreeBSD и старых версиях macOS) появилась до SP 800-90A и по-прежнему пользуется доверием. Инцидент с Dual EC также возродил интерес к аппаратным RNG (RDRAND) в качестве источников энтропии, хотя RDRAND тоже подвергался обвинениям в возможном наличии скрытой лазейки. Поэтому рекомендовалось смешивать RDRAND с программно получаемой энтропией, а не использовать его исключительно.

Какое математическое соотношение делает возможной скрытую лазейку в Dual EC DRBG?

Dual EC DRBG был включён в стандарт NIST SP 800-90A в 2006 году. В 2007 году Шумоу и Фергюсон показали, что знание e (где Q=e*P) позволяет предсказать все выходные данные по 32 байтам. Утечки Сноудена в 2013 году подтвердили влияние NSA на криптографические стандарты. По сообщениям, RSA Security получила 10 миллионов долларов за то, чтобы сделать Dual EC алгоритмом по умолчанию в BSAFE. NIST удалил Dual EC из SP 800-90A в редакции 1 (2014 год). Инцидент с Juniper в 2015 году показал, что скрытая лазейка использовалась в реальном продукте. Уроки: константы NUMS, прозрачная документация их получения, управление конфликтами интересов и процессы аудита после стандартизации. RNG на основе ChaCha20 стали надёжной альтернативой.