Двойной_EC_DRBG

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

Слабость: потенциальный бэкдор

Слабости в криптографической безопасности алгоритма были известны и публично критиковались задолго до того, как алгоритм стал частью формального стандарта, одобренного ANSI , ISO , а ранее — Национальным институтом стандартов и технологий (NIST). Одной из публично выявленных слабостей была способность алгоритма содержать в себе криптографический бэкдор, правительства США выгодный только тем, кто о нем знает — Агентству национальной безопасности (АНБ) — и никому другому . В 2013 году The New York Times сообщила, что документы, находящиеся в их распоряжении, но так и не обнародованные, «по-видимому, подтверждают», что бэкдор был реальным и был намеренно вставлен АНБ в рамках своей Bullrun программы дешифрования . В декабре 2013 года в новостной статье Reuters утверждалось, что в 2004 году, до того как NIST стандартизировал Dual_EC_DRBG, АНБ заплатило RSA Security 10 миллионов долларов в рамках секретной сделки за использование Dual_EC_DRBG по умолчанию в криптографической библиотеке RSA BSAFE , в результате чего RSA Security стала наиболее важной распространитель небезопасного алгоритма. RSA ответило, что они «категорически отрицают» тот факт, что они когда-либо сознательно вступали в сговор с АНБ с целью принятия алгоритма, который, как известно, был ошибочным, но также заявили, что «мы никогда не держали [наши] отношения [с АНБ] в секрете».

Незадолго до его первой известной публикации в 2004 году возможный клептографический бэкдор был обнаружен в конструкции Dual_EC_DRBG, при этом конструкция Dual_EC_DRBG обладала необычным свойством, заключающимся в том, что теоретически невозможно было подтвердить существование бэкдора кому-либо, кроме разработчиков Dual_EC_DRBG (АНБ). Брюс Шнайер вскоре после стандартизации пришел к выводу, что «довольно очевидный» бэкдор (наряду с другими недостатками) будет означать, что никто не будет использовать Dual_EC_DRBG. Бэкдор позволит АНБ расшифровать, например, шифрование SSL/TLS , которое использует Dual_EC_DRBG в качестве CSPRNG.

Члены группы стандартов ANSI, в которую впервые был отправлен Dual_EC_DRBG, знали точный механизм потенциального бэкдора и способы его отключения. но не решил отключить или опубликовать бэкдор. Первоначально широкое криптографическое сообщество не знало о потенциальном бэкдоре до Дэна Шумоу и Нильса Фергюсона публикации или до заявки на патент Дэниела Р. Л. Брауна и Скотта Ванстона от Certicom в 2005 году, описывающей механизм бэкдора.

В сентябре 2013 года газета The New York Times сообщила, что во внутренних записках АНБ, опубликованных Эдвардом Сноуденом, указывалось, что АНБ работало в процессе стандартизации, чтобы в конечном итоге стать единственным редактором стандарта Dual_EC_DRBG. и пришел к выводу, что стандарт Dual_EC_DRBG действительно содержит бэкдор для АНБ. В ответ NIST заявил, что «NIST не будет намеренно ослаблять криптографический стандарт». но, согласно статье New York Times , АНБ тратило 250 миллионов долларов в год на внедрение бэкдоров в программное и аппаратное обеспечение в рамках программы Bullrun . Президентский консультативный комитет, созданный впоследствии для изучения поведения АНБ, рекомендовал, среди прочего, правительству США «полностью поддерживать, а не подрывать усилия по созданию стандартов шифрования».

21 апреля 2014 г. NIST исключил Dual_EC_DRBG из своего проекта руководства по генераторам случайных чисел, рекомендуя «нынешним пользователям Dual_EC_DRBG как можно быстрее перейти на один из трех оставшихся утвержденных алгоритмов».

Хронология Dual_EC_DRBG

Время	Что случилось
май 1997 г.	Адам Л. Янг и Моти Юнг представляют свою статью по криптовирусологии «Клептография: использование криптографии против криптографии» на выставке Eurocrypt 1997. В статье показано, как встроить скрытый обмен ключами в протокол обмена ключами Диффи-Хеллмана. Бэкдор EC-DRBG с незначительной модификацией эквивалентен бэкдору Янга-Юнга в Диффи-Хеллмане из Eurocrypt 1997.
август 1997 г.	Адам Л. Янг и Моти Юнг представляют свою статью по криптовирусологии «Распространенность клептографических атак на криптосистемы на основе дискретного журнала» на Crypto 1997. В статье представлен рецепт, как встроить асимметричные бэкдоры в криптоалгоритмы на основе дискретных журналов. В статье обобщается парадигма, использованная для атаки на Диффи-Хеллмана из Eurocrypt 1997. В статье представлена ​​«клептограмма дискретного логарифма», которая позже будет преобразована в EC-DRBG.
Процесс стандартизации ANSI X9.82 начался в начале 2000-х годов.	АНБ стремится включить Dual_EC_DRBG в ANSI X9.82 , когда в начале 2000-х годов начнется процесс стандартизации.
После начала процесса стандартизации ANSI X9.82 и до публикации NIST.	По словам Джона Келси (который числился автором NIST SP 800-90A вместе с Элейн Баркер), возможность бэкдора с помощью тщательно выбранных значений P и Q была поднята на встрече ANSI X9.82 . В результате разработчики получили возможность выбирать собственные P и Q. значения Позже выяснилось, что конкретная тонкая формулировка, которую NIST включил в стандарт, означала, что пользователи могли получить решающую проверку своей реализации по стандарту FIPS 140-2 только в том случае, если они использовали исходные скомпрометированные P и Q. значения
октябрь 2003 г.	Го, Боне, Пинкас и Голле публикуют исследовательскую работу по проблеме добавления восстановления ключей в протоколы SSL/TLS и SSH. Они заявляют: «Правительство может убедить крупных поставщиков программного обеспечения распространять реализации SSL/TLS или SSH2 со скрытым и нефильтруемым восстановлением ключей... Пользователи не заметят механизм восстановления ключей, поскольку схема скрыта». Затем они предполагают, что, когда серверу нужен случайный одноразовый номер, он может вместо этого использовать шифрование сеансового ключа, вычисленного с использованием ключа условного депонирования. При этом не используется эллиптическая кривая дискретно-логарифмической клептограммы, и в результате для работы требуется подсознательный канал с большой пропускной способностью.
июнь 2004 г.	черновой вариант ANSI X9.82, часть 3 , который включает Dual_EC_DRBG. Опубликован Неизвестно, были ли опубликованы более ранние черновики.
Где-то в 2004 году	RSA делает Dual_EC_DRBG CSPRNG по умолчанию в BSAFE. В 2013 году агентство Reuters сообщило, что это результат секретной сделки на 10 миллионов долларов с АНБ.
21 января 2005 г.	Дата приоритета заявки на патент двумя членами Certicom комитета по стандартизации ANSI X9.82. В патенте описывается работа бэкдора CSPRNG с эллиптической кривой, идентичного потенциальному бэкдору в Dual_EC_DRBG, а также способы нейтрализации такого скрытого бэкдора путем выбора альтернативных точек кривой и большего усечения битов в выходной функции.
Где-то в 2005 году	стандарт ISO/IEC 18031 :2005, который включает Dual_EC_DRBG. Опубликован
декабрь 2005 г.	Публикуется первый проект NIST SP 800-90A, который включает Dual_EC_DRBG.
16 марта 2006 г.	Кристиан Гьёстин публикует комментарии к Dual-EC-DRBG/NIST SP 800-90, черновой вариант от декабря 2005 г., показывая, что часть Dual_EC_DRBG «криптографически ненадежна», и создает бит-предиктор с преимуществом 0,0011, что считается неприемлемым для CSPRNG.
29 марта 2006 г.	Дэниел Р.Л. Браун публикует « Предполагаемую безопасность ГСЧ с эллиптической кривой ANSI-NIST », в которой приходит к выводу, что «[Dual_EC_DRBG] следует серьезно учитывать», предполагая меньшее усечение точек кривой, чем присутствует в Dual_EC_DRBG, как показано в статье Гьёстина 2006 года. . В статье также предвосхищается заявление Шумова и Фергюсона в 2007 году о возможном бэкдоре: «В этом доказательстве существенно используется случайность Q. Причина этого не просто в том, чтобы доказательство работало. Если Q не случайно, то оно может быть если злоумышленник знает d такой, что dQ = P. Тогда dR i = dS i +1 , так что такой распознаватель может немедленно восстановить секретные предварительные состояния из выходных данных. Как только различитель получит предварительные состояния, он может легко отличить выходные данные от. случайный. Поэтому обычно предпочтительнее, чтобы выбирался случайным образом относительно P. Q
29 мая 2006 г.	Берри Шенмейкерс и Андрей Сидоренко публикуют криптоанализ псевдослучайного генератора двойной эллиптической кривой , показывающий, что эмпирически выходные данные Dual_EC_DRBG можно отличить от случайных битов, делая вывод, что Dual_EC_DRBG небезопасен как CSPRNG. Обратите внимание, что это отдельная проблема, связанная с бэкдором. Авторы также отмечают, что утверждение безопасности Dual_EC_DRBG подтверждается только неформальным обсуждением. Никаких доказательств безопасности (например, посредством аргумента редукции) не дается. Отсюда следует, что NIST игнорировал доказуемо безопасные генераторы псевдослучайных чисел, которые уже давно существовали в рецензируемой академической литературе.
июнь 2006 г.	Опубликован NIST SP 800-90A, включает Dual_EC_DRBG, причем дефекты, на которые указали Кристиан Гьёстин, Берри Шенмейкерс и Андрей Сидоренко, не исправлены.
июнь 2007 г.	Янг и Юнг публикуют исследовательскую работу, в которой подробно описывается доказуемо безопасный асимметричный бэкдор в SSL. Асимметричный бэкдор использует витую пару эллиптических кривых, в результате чего получается дискретная логарифмическая клептограмма, которая легко вписывается в hello nonce. Атака представляет собой атаку на генерацию случайных чисел SSL. Генерация одноразового номера приветствия с использованием EC-DRBG, который использует бэкдор NIST, в точности имитирует атаку на SSL, предпринятую Янгом и Юнгом.
август 2007 г.	Дэн Шумоу и Нильс Фергюсон проводят неформальную презентацию, демонстрирующую, что злоумышленник с бэкдором и небольшим объемом вывода может полностью восстановить внутреннее состояние EC-DRBG и, следовательно, предсказать весь будущий вывод.
15 ноября 2007 г.	статью под названием « Включено ли АНБ секретный бэкдор в новый стандарт шифрования? » Брюс Шнайер публикует в журнале Wired , основанную на презентации Дэна Шумоу и Нильса Фергюсона.
6 июня 2013 г.	Опубликованы первые новости (не имеющие отношения к Dual_EC_DRBG), основанные на утечке Эдвардом Сноуденом документов АНБ.
5 сентября 2013 г.	АНБ Bullrun На основе утечек Сноудена раскрыто существование программы . Одна из целей Bullrun описывается как « тайное внесение слабых мест в стандарты шифрования, которым следуют разработчики аппаратного и программного обеспечения по всему миру » . Газета «Нью-Йорк Таймс» утверждает, что «АНБ ввело лазейку в стандарт 2006 года, принятый NIST... называется стандартом Dual EC DRBG", подтверждая, что АНБ осуществило атаку с использованием вредоносного программного обеспечения.
10 сентября 2013 г.	Гейл Портер, директор отдела по связям с общественностью NIST, опубликовала заявление, в котором говорится, что «NIST не будет намеренно ослаблять криптографический стандарт». В заявлении не упоминается тот факт, что NIST в конечном итоге проигнорировал предупреждение о возможном бэкдоре в стандарте от собственного криптографа NIST Джона Келси.
19 сентября 2013 г.	RSA Security советует своим клиентам прекратить использование Dual_EC_DRBG в наборе инструментов BSAFE и Data Protection Manager компании RSA Security , ссылаясь на рекомендации NIST от 12 сентября 2013 г., в которых указано: «NIST настоятельно рекомендует, до разрешения проблем безопасности и повторного выпуска SP 800-90A, Dual_EC_DRBG, как указано в версии SP 800-90A от января 2012 года, больше не используется». Первоначальные сообщения в средствах массовой информации вызывают подозрения в отношении продолжающегося использования RSA Dual_EC_DRBG по умолчанию в своих продуктах BSAFE и Data Protection Manager, особенно после 2007 года в свете ранее опубликованных опасений по поводу возможности наличия бэкдора в алгоритме. Руководитель технического отдела RSA Сэм Карри кратко обосновывает решение RSA Security использовать Dual_EC_DRBG по умолчанию, что широко критикуется криптографами. Карри не обсуждает позже раскрытую сделку на 10 миллионов долларов с АНБ по использованию Dual_EC_DRBG.
18 декабря 2013 г.	Президентский консультативный комитет, созданный для проверки АНБ, рекомендовал правительству США «полностью поддерживать, а не подрывать усилия по созданию стандартов шифрования».
20 декабря 2013 г.	Reuters сообщает о существовании сделки на сумму 10 миллионов долларов между RSA и АНБ по установке Dual_EC_DRBG в качестве CSPRNG по умолчанию в BSAFE.
22 декабря 2013 г.	RSA Security публикует заявления, категорически отрицающие, что она «заключила «секретный контракт» с АНБ на включение известного ошибочного генератора случайных чисел в свои библиотеки шифрования BSAFE», хотя в ее заявлениях не отрицается существование сделки на 10 миллионов долларов между RSA и АНБ установит Dual_EC_DRBG в качестве стандарта в BSAFE. Некоторые новостные сайты, такие как BBC, резюмируют пресс-релиз как прямое отрицание существования сделки на 10 миллионов долларов. в то время как в других комментариях отмечается, что неясно, какие именно утверждения опровергает тщательно сформулированный пресс-релиз RSA Security, если таковые имеются.
25 февраля 2014 г.	В своей программной речи на конференции RSA 2014 года исполнительный председатель RSA Security (и исполнительный вице-президент EMC) Арт Ковьелло намекнул, что RSA Security не увидела достоинств в исследовательских работах 2006 и 2007 годов, в которых указывали на недостатки Dual_EC_DRBG, пока NIST не выпустил руководство по прекращению использования CSPRNG. Ковьелло сказал, что RSA Security столкнулась с уменьшением доходов от шифрования и больше не хочет тратить ресурсы на исследования в области шифрования, но, будучи «соавтором и бенефициаром открытых стандартов», будет доверять рекомендациям NIST и АНБ, и обвинила АНБ в обмане компании.
21 апреля 2014 г.	После периода общественного обсуждения и проверки NIST удалил Dual_EC_DRBG в качестве криптографического алгоритма из своего проекта руководства по генераторам случайных чисел, рекомендуя «нынешним пользователям Dual_EC_DRBG как можно быстрее перейти на один из трех оставшихся утвержденных алгоритмов».
август 2014 г.	Чековей и др. опубликовать исследовательскую работу, в которой анализируется практичность использования EC-DRBG для создания асимметричного бэкдора в SSL и TLS.
Январь 2015 г.	Майкл Вертхаймер, директор по исследованиям АНБ, написал: «Оглядываясь назад, АНБ следовало прекратить поддержку алгоритма Dual EC DRBG сразу после того, как исследователи безопасности обнаружили потенциальную возможность лазейки. Честно говоря, я не могу придумать лучшего способа описать нашу неудачу. отказаться от поддержки алгоритма Dual EC DRBG как нечто иное, чем прискорбное».

Описание

Обзор

В качестве состояния алгоритм использует одно целое число s . Всякий раз, когда запрашивается новое случайное число, это целое число обновляется. k -е состояние определяется выражением

$s_{k}=g_{P}(s_{k-1})$

Возвращаемое случайное целое число r является функцией состояния. k -е случайное число

$r_{k}=g_{Q}(s_{k})$

Функция $g_{P}(x)$ зависит от фиксированной точки P эллиптической кривой . $g_{Q}(x)$ за исключением того, что он использует точку Q. аналогично , Точки P и Q остаются постоянными для конкретной реализации алгоритма.

Подробности

Алгоритм допускает использование различных констант, переменной длины вывода и других настроек. Для простоты описанный здесь будет использовать константы из кривой P-256 (один из трех доступных наборов констант) и иметь фиксированную выходную длину. Алгоритм работает исключительно над простым конечным полем. $F_{p}$ ( $\mathbb {Z} /p\mathbb {Z}$), где p — простое число. Состояние, начальное число и случайные числа — все это элементы этого поля. Размер поля

$p={\mathtt {ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551}}_{16}$

Эллиптическая кривая над $F_{p}$ дан

$y^{2}=x^{3}-3x+b$

где константа b равна

$b={\mathtt {5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b}}_{16}$

Точки на кривой $E({\displaystyle F_{p}})$. Две из этих точек заданы как неподвижные точки P и Q.

$P,Q\in E(F_{p})$

Их координаты

${\begin{aligned}P_{x}&={\mathtt {6b17d1f2\ e12c4247\ f8bce6e5\ 63a440f2\ 77037d81\ 2deb33a0\ f4a13945\ d898c296}}_{~16}\\P_{y}&={\mathtt {4fe342e2\ fe1a7f9b\ 8ee7eb4a\ 7c0f9e16\ 2bce3357\ 6b315ece\ cbb64068\ 37bf51f5}}_{~16}\\Q_{x}&={\mathtt {c97445f4\ 5cdef9f0\ d3e05e1e\ 585fc297\ 235b82b5\ be8ff3ef\ ca67c598\ 52018192}}_{~16}\\Q_{y}&={\mathtt {b28ef557\ ba31dfcb\ dd21ac46\ e2a91e3c\ 304f44cb\ 87058ada\ 2cb81515\ 1e610046}}_{~16}\end{aligned}}$

Используется функция для извлечения координаты x. Он «конвертирует» точки эллиптической кривой в элементы поля.

$X(x,y)=x$

Выходные целые числа усекаются перед выводом

$t(x)=x\ {\text{mod}}\ {\frac {p}{2^{16}}}$

Функции $g_{P}$ и $g_{Q}$. Эти функции возводят неподвижные точки в степень. «Возведение в степень» в данном контексте означает использование специальной операции, определенной для точек на эллиптических кривых .

$g_{P}(x)=X(P^{x})$

$g_{Q}(x)=t(X(Q^{x}))$

Генератор засеян элементом из $F_{p}$

$s_{1}=g_{P}(seed)$

k -е состояние и случайное число

$s_{k}=g_{P}(s_{k-1})$

$r_{k}=g_{Q}(s_{k})$

Случайные числа

$r_{1},r_{2},\ldots$

Безопасность

Заявленная цель включения Dual_EC_DRBG в NIST SP 800-90A заключается в том, что его безопасность основана на предположениях о вычислительной сложности из теории чисел. Математическое доказательство снижения безопасности может затем доказать, что, пока задачи теории чисел сложны, сам генератор случайных чисел безопасен. Однако создатели Dual_EC_DRBG не опубликовали снижение безопасности для Dual_EC_DRBG, и вскоре после публикации проекта NIST было показано, что Dual_EC_DRBG действительно небезопасен, поскольку выводит слишком много битов за раунд. Вывод слишком большого количества битов (вместе с тщательно выбранными точками эллиптической кривой P и Q ) делает возможным использование бэкдора АНБ, поскольку он позволяет злоумышленнику отменить усечение путем грубого угадывания. Вывод слишком большого количества битов не был исправлен в окончательном опубликованном стандарте, в результате чего Dual_EC_DRBG оказался небезопасным и закрытым.

Во многих других стандартах константы, которые должны быть произвольными, выбираются по принципу чисел «ничего в рукаве» , где они получаются из числа «пи» или аналогичных математических констант таким образом, что не остается места для корректировки. Однако Dual_EC_DRBG не уточнил, как были выбраны константы P и Q по умолчанию , возможно, потому, что они были созданы АНБ для использования в качестве бэкдора. Поскольку комитет по стандартизации знал о потенциале бэкдора, способ, позволяющий разработчику выбирать свои собственные безопасные P и Q. был включен Но точная формулировка в стандарте была написана так, что использование предполагаемых P и Q требовалось для проверки FIPS 140-2 с бэкдором , поэтому проект OpenSSL решил реализовать P и Q с бэкдором , даже несмотря на то, что они знали о потенциальном бэкдоре. предпочли бы генерировать свои собственные безопасные P и Q. и New York Times позже напишет, что АНБ работало в процессе стандартизации и в конечном итоге стало единственным редактором стандарта.

Позднее Дэниел Р. Л. Браун и Кристиан Гьёстин опубликовали доказательство безопасности для Dual_EC_DRBG, показывающее, что сгенерированные точки эллиптической кривой будут неотличимы от равномерно случайных точек эллиптической кривой, и что если при окончательном усечении вывода будет выведено меньше битов, и если две точки эллиптической кривой P и Q были независимыми, тогда Dual_EC_DRBG безопасен. Доказательство основывалось на предположении, что три проблемы являются трудными: предположение Диффи-Хеллмана о принятии решения (которое обычно считается трудным) и две новые, менее известные проблемы, которые обычно не считаются сложными: проблема усеченной точки и задача о логарифме х . Dual_EC_DRBG работал довольно медленно по сравнению со многими альтернативными CSPRNG (которые не имеют снижения безопасности). ), но Дэниел Р. Л. Браун утверждает, что снижение безопасности делает медленный Dual_EC_DRBG допустимой альтернативой (при условии, что разработчики отключат очевидный бэкдор). Обратите внимание, что Дэниел Р.Л. Браун работает в компании Certicom, основном владельце патентов на криптографию на основе эллиптических кривых, поэтому при продвижении EC CSPRNG может возникнуть конфликт интересов.

Предполагаемый бэкдор АНБ позволит злоумышленнику определить внутреннее состояние генератора случайных чисел, просматривая выходные данные одного раунда (32 байта); Затем все будущие выходные данные генератора случайных чисел можно легко вычислить до тех пор, пока CSPRNG не будет повторно заполнен внешним источником случайности. Это делает, например, SSL/TLS уязвимым, поскольку настройка соединения TLS включает отправку случайно сгенерированного криптографического одноразового номера в открытом виде. Предполагаемый бэкдор АНБ будет зависеть от знания им единственной буквы e, такой, что $eQ=P$. Это сложная задача, если P и Q заданы заранее, но проще, если P и Q. выбраны e — секретный ключ, предположительно известный только АНБ, а предполагаемый бэкдор — это клептографический асимметричный скрытый бэкдор. Сообщение в блоге Мэтью Грина «Множество недостатков Dual_EC_DRBG» имеет упрощенное объяснение того, как работает предполагаемый бэкдор АНБ, используя клептограмму дискретного журнала, представленную в Crypto 1997.

Стандартизация и реализации

АНБ впервые представило Dual_EC_DRBG в ANSI X9.82 DRBG в начале 2000-х годов, включая те же параметры, которые создали предполагаемый бэкдор, а Dual_EC_DRBG был опубликован в проекте стандарта ANSI. Dual_EC_DRBG также существует в стандарте ISO 18031 .

По словам Джона Келси (который вместе с Элейн Баркер числился автором NIST SP 800-90A), возможность бэкдора с помощью тщательно выбранных P и Q обсуждалась на заседании группы по стандартам и рекомендациям для инструментов ANSI X9F1. Когда Келси спросил Дона Джонсона из Cygnacom о происхождении Q , Джонсон ответил в электронном письме Келси от 27 октября 2004 года, что АНБ запретило публичное обсуждение генерации Q , альтернативного тому, который поставлялось АНБ.

По крайней мере, два члена группы по стандартам и рекомендациям для инструментов ANSI X9F1, написавшей ANSI X9.82, Дэниел Р.Л. Браун и Скотт Ванстон из Certicom , были осведомлены о точных обстоятельствах и механизме возникновения бэкдора, поскольку подали заявку на патент в январе 2005 г. о том, как именно вставить или предотвратить бэкдор в DUAL_EC_DRBG. Работа «люка», упомянутого в патенте, идентична той, которая позже подтверждена в Dual_EC_DRBG. Комментатор Мэтью Грин, рассказывая о патенте в 2014 году, описывает его как « пассивно-агрессивный » способ плюнуть на АНБ путем обнародования бэкдора, одновременно критикуя всех членов комитета за то, что они на самом деле не отключили бэкдор, о котором они, очевидно, знали. В патенте Брауна и Ванстона перечислены два необходимых условия существования бэкдора:

1) Выбранный Q

Генератор случайных чисел на эллиптической кривой позволяет избежать использования ключей условного депонирования, выбирая точку Q на эллиптической кривой как проверяемо случайную. Преднамеренное использование ключей условного депонирования может обеспечить функциональность резервного копирования. Связь между P и Q используется в качестве ключа условного депонирования и хранится в домене безопасности. Администратор регистрирует выходные данные генератора, чтобы восстановить случайное число с помощью ключа условного депонирования.

2) Небольшое усечение вывода

[0041] Другой альтернативный метод предотвращения атаки условного депонирования ключа на выходные данные ECRNG, показанный на рисунках 3 и 4, заключается в добавлении функции усечения к ECRNG для усечения выходных данных ECRNG примерно до половины длины точки сжатой эллиптической кривой. Предпочтительно, чтобы эта операция выполнялась в дополнение к предпочтительному способу, показанному на фиг. 1 и 2, однако следует понимать, что она может выполняться в качестве основной меры для предотвращения атаки на условное депонирование ключа. Преимущество усечения состоит в том, что список значений R, связанных с одним выходом ECRNG r, обычно невозможен для поиска. Например, для 160-битной группы эллиптических кривых количество потенциальных точек R в списке составляет около 2. ⁸⁰ , и поиск по списку будет примерно таким же трудным, как решение задачи дискретного логарифма. Цена этого метода заключается в том, что ECRNG становится вдвое менее эффективным, поскольку длина вывода фактически уменьшается вдвое.

По словам Джона Келси, возможность выбора проверяемого случайного Q была добавлена ​​в стандарт в качестве опции в ответ на подозрение на бэкдор: хотя таким образом, что проверка FIPS 140-2 может быть достигнута только с помощью Q , возможно, с бэкдором . Стив Маркесс (который помог внедрить NIST SP 800-90A для OpenSSL) предположил, что это требование использования потенциально скрытых точек может быть свидетельством соучастия NIST. Непонятно, почему в стандарте не указано значение Q по умолчанию как проверяемое число, не генерирующее ничего , или почему в стандарте не используется большее усечение, которое, как говорится в патенте Брауна, может использоваться в качестве «основной меры для предотвращения атака на условное депонирование ключей». Небольшое усечение было необычным по сравнению с предыдущими PRG EC, которые, по словам Мэтью Грина, выдавали только от 1/2 до 2/3 битов в выходной функции. В 2006 году Гьёстин показал, что низкое усечение делает ГСЧ предсказуемым и, следовательно, непригодным для использования в качестве CSPRNG, даже если Q не был выбран для содержания бэкдора. Стандарт гласит, что реализации «должны» использовать небольшой предоставленный max_outlen, но дает возможность выводить на 8 бит меньше. В приложении C стандарта приводится расплывчатый аргумент о том, что вывод меньшего количества битов сделает вывод менее равномерно распределенным. Доказательство безопасности Брауна в 2006 году основано на том, что outlen намного меньше значения max_outlen по умолчанию в стандарте.

В группу по стандартам и рекомендациям для инструментов ANSI X9F1, которая обсуждала бэкдор, также входили три сотрудника известной охранной компании RSA Security. В 2004 году компания RSA Security реализовала Dual_EC_DRBG, которая содержала бэкдор АНБ в качестве CSPRNG по умолчанию в их RSA BSAFE, в результате секретной сделки на 10 миллионов долларов с АНБ. В 2013 году, после того как газета New York Times сообщила, что Dual_EC_DRBG содержит бэкдор, созданный АНБ, RSA Security заявила, что не знала о каком-либо бэкдоре, когда заключала сделку с АНБ, и посоветовала своим клиентам переключиться на CSPRNG. В своем выступлении на конференции RSA 2014 года исполнительный председатель RSA Security Арт Ковьелло объяснил, что RSA увидела снижение доходов от шифрования и решила перестать быть «движущей силой» независимых исследований в области шифрования, а вместо этого «довериться» стандартам и рекомендации организаций по стандартизации, таких как NIST.

Черновой вариант NIST SP 800-90A, включая Dual_EC_DRBG, был опубликован в декабре 2005 года. Окончательный вариант NIST SP 800-90A, включая Dual_EC_DRBG, был опубликован в июне 2006 года. Документы, просочившиеся Сноуденом, были истолкованы как предполагающие, что АНБ использовало Dual_EC_DRBG с помощью бэкдора, причем те, кто сделал утверждение ссылается на работу АНБ в процессе стандартизации, которая в конечном итоге стала единственным редактором стандарта. Раннее использование Dual_EC_DRBG компанией RSA Security (за которое, как позже сообщалось, АНБ тайно заплатило 10 миллионов долларов) было названо АНБ аргументом в пользу принятия Dual_EC_DRBG в стандарт NIST SP 800-90A . Впоследствии RSA Security назвала принятие Dual_EC_DRBG стандартом NIST причиной использования Dual_EC_DRBG.

В статье Дэниела Р. Л. Брауна о снижении безопасности Dual_EC_DRBG от марта 2006 года упоминается необходимость большего усечения вывода и случайно выбранного Q , но в основном вскользь, и не упоминаются его выводы из его патента о том, что эти два дефекта в Dual_EC_DRBG вместе могут использоваться как черный ход. В заключении Браун пишет: «Поэтому к ECRNG следует относиться серьезно, а его высокая эффективность делает его подходящим даже для ограниченных сред». Обратите внимание, что другие критиковали Dual_EC_DRBG как чрезвычайно медленный, а Брюс Шнайер заключил: «Он слишком медленный, чтобы кто-либо мог его добровольно использовать». и Мэтью Грин говорит, что Dual_EC_DRBG «до тысячи раз медленнее», чем альтернативы. Потенциал наличия бэкдора в Dual_EC_DRBG не получил широкой огласки за пределами собраний группы внутренних стандартов. Только после презентации Дэна Шумоу и Нильса Фергюсона в 2007 году потенциал бэкдора стал широко известен. Шумову и Фергюсону было поручено реализовать Dual_EC_DRBG для Microsoft, и, по крайней мере, Фергюсон обсуждал возможный бэкдор на встрече X9 в 2005 году. Брюс Шнайер написал в статье Wired 2007 года, что недостатки Dual_EC_DRBG настолько очевидны, что никто не будет использовать Dual_EC_DRBG: «Он не имеет смысла в качестве люка: он общедоступен и довольно очевиден. Это не имеет смысла с инженерной точки зрения: это слишком медленно для того, чтобы кто-то охотно использовал его». Шнайер, очевидно, не знал, что RSA Security использовала Dual_EC_DRBG по умолчанию в BSAFE с 2004 года.

OpenSSL реализовал все NIST SP 800-90A, включая Dual_EC_DRBG, по запросу клиента. Разработчики OpenSSL знали о потенциальном бэкдоре из-за презентации Шумова и Фергюсона и хотели использовать метод, включенный в стандарт, для выбора гарантированных P и Q без бэкдора , но им сказали, что для получения проверки FIPS 140-2 они должны придется использовать P и Q по умолчанию . OpenSSL решил реализовать Dual_EC_DRBG, несмотря на его сомнительную репутацию в плане полноты, отметив, что OpenSSL пытался быть полным и реализует множество других небезопасных алгоритмов. OpenSSL не использовал Dual_EC_DRBG в качестве CSPRNG по умолчанию, и в 2013 году было обнаружено, что из-за ошибки реализация Dual_EC_DRBG в OpenSSL стала нефункциональной, а это означает, что никто не мог ее использовать.

Брюс Шнайер сообщил в декабре 2007 года, что Microsoft добавила поддержку Dual_EC_DRBG в Windows Vista, хотя она не включена по умолчанию, и Шнайер предупредил об известном потенциальном бэкдоре. Windows 10 и более поздние версии автоматически заменят вызовы Dual_EC_DRBG вызовами CTR_DRBG на основе AES.

9 сентября 2013 года, после утечки информации Сноудена и сообщения New York Times о бэкдоре в Dual_EC_DRBG, Национальный институт стандартов и технологий (NIST) ITL объявил, что в свете проблем безопасности сообщества он переиздает SP 800-90A. в качестве проекта стандарта и повторное открытие SP800-90B/C для общественного обсуждения. NIST теперь «настоятельно рекомендует» не использовать Dual_EC_DRBG, как указано в версии SP 800-90A от января 2012 года. Обнаружение бэкдора в стандарте NIST стало для NIST большим затруднением .

RSA Security сохранила Dual_EC_DRBG в качестве CSPRNG по умолчанию в BSAFE даже после того, как более широкое криптографическое сообщество узнало о потенциальном бэкдоре в 2007 году, но, похоже, в сообществе не было общей осведомленности об использовании BSAFE Dual_EC_DRBG в качестве пользовательской опции. Только после всеобщего беспокойства по поводу бэкдора была предпринята попытка найти программное обеспечение, использующее Dual_EC_DRBG, из которых BSAFE был, безусловно, наиболее известным из обнаруженных. После разоблачений 2013 года руководитель отдела технологий безопасности RSA Сэм Карри предоставил Ars Technica обоснование первоначального выбора ошибочного стандарта Dual EC DRBG в качестве стандарта по умолчанию вместо альтернативных генераторов случайных чисел. Техническая точность заявления подверглась широкой критике со стороны криптографов, в том числе Мэтью Грина и Мэтта Блейза . 20 декабря 2013 года агентство Reuters сообщило, что RSA приняла секретный платеж в размере 10 миллионов долларов от АНБ за установку генератора случайных чисел Dual_EC_DRBG по умолчанию в двух своих продуктах шифрования. 22 декабря 2013 года RSA опубликовало в своем корпоративном блоге заявление, «категорически» отрицающее секретную сделку с АНБ о вставке «генератора случайных чисел с известными недостатками» в свой набор инструментов BSAFE.

После статьи New York Times, в которой утверждалось, что Dual_EC_DRBG содержит бэкдор, Браун (который подал заявку на патент на бэкдор и опубликовал снижение безопасности) написал электронное письмо в список рассылки IETF, защищая стандартный процесс Dual_EC_DRBG:

позволяет альтернативный выбор констант P и Q. 1. Dual_EC_DRBG, как указано в NIST SP 800-90A и ANSI X9.82-3 , Насколько мне известно, альтернативы не допускают известного возможного бэкдора. На мой взгляд, неверно утверждать, что Dual_EC_DRBG всегда имеет бэкдор, хотя я признаю, что формулировка для определения затронутых случаев может быть неудобной.

2. Многие вещи становятся очевидными задним числом. Я не уверен, было ли это очевидно.[...]

8. Учитывая все вышесказанное, я не понимаю, как стандарты ANSI и NIST для Dual_EC_DRBG можно рассматривать как извращенный стандарт как таковой. Но, возможно, это просто потому, что я предвзят или наивен.

— Дэниел Браун,

Программное и аппаратное обеспечение, содержащее возможный бэкдор

Реализации, использующие Dual_EC_DRBG, обычно получали его через библиотеку. По крайней мере, RSA Security (библиотека BSAFE), OpenSSL , Microsoft и Cisco. есть библиотеки, включающие Dual_EC_DRBG, но по умолчанию его использует только BSAFE. Согласно статье Reuters, в которой раскрывается секретная сделка на 10 миллионов долларов между RSA Security и АНБ, BSAFE RSA Security была самым важным дистрибьютором алгоритма. В реализации OpenSSL Dual_EC_DRBG был недостаток, из-за которого он не работал вне тестового режима, из чего Стив Маркесс из OpenSSL заключает, что никто не использовал реализацию OpenSSL Dual_EC_DRBG.

Список продуктов, реализация CSPRNG которых прошла проверку на соответствие FIPS 140-2, доступен в NIST. Проверенные CSPRNG перечислены в поле «Описание/Примечания». Обратите внимание: даже если Dual_EC_DRBG указан как проверенный, возможно, он не включен по умолчанию. Многие реализации основаны на переименованной копии реализации библиотеки.

Программное обеспечение BlackBerry является примером использования не по умолчанию. Он включает поддержку Dual_EC_DRBG, но не по умолчанию. Однако компания BlackBerry Ltd не предоставила рекомендаций ни одному из своих клиентов, которые могли ее использовать, поскольку они не считают вероятный бэкдор уязвимостью. Джеффри Карр цитирует письмо Blackberry:

Алгоритм Dual EC DRBG доступен только сторонним разработчикам через криптографические API на платформе [Blackberry]. В случае с Криптографическим API он доступен, если сторонний разработчик пожелал использовать эту функциональность и явно спроектировал и разработал систему, запросившую использование API.

Брюс Шнайер отметил, что, даже если он не включен по умолчанию, реализация CSPRNG с бэкдором в качестве опции может облегчить АНБ шпионаж за целями, у которых есть программно-управляемый переключатель командной строки для выбора алгоритма шифрования или " реестра », как и большинство продуктов Microsoft , таких как Windows Vista :

Троянец действительно очень большой. Нельзя сказать, что это была ошибка. Это огромный фрагмент кода, собирающий нажатия клавиш. Но изменение бита один на бит два [в реестре для изменения генератора случайных чисел по умолчанию на компьютере], вероятно, останется незамеченным. Это низкий уровень заговора и весьма сомнительный способ получить бэкдор. Так что есть польза от включения его в библиотеку и в продукт.

— Брюс Шнайер,

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

В декабре 2015 года Juniper Networks объявила. что некоторые версии их прошивки ScreenOS использовали Dual_EC_DRBG с подозрительными точками P и Q , создавая бэкдор в их брандмауэре. Первоначально предполагалось использовать точку Q, выбранную Juniper, которая могла быть сгенерирована, а могла и не быть доказуемо безопасным способом. Затем Dual_EC_DRBG использовался для заполнения PRNG ANSI X9.17. Это запутало бы вывод Dual_EC_DRBG, тем самым уничтожив бэкдор. Однако «ошибка» в коде обнажила необработанный вывод Dual_EC_DRBG, что поставило под угрозу безопасность системы. Затем этот бэкдор был заблокирован неизвестной стороной, которая изменила точку Q и некоторые тестовые векторы. Утверждения о том, что АНБ имело постоянный бэкдор-доступ через брандмауэры Juniper, уже было опубликовано в 2013 году изданием Der Spiegel . Клептографический АНБ, заключающейся в наличии дыр в безопасности , бэкдор является примером политики NOBUS которыми могут воспользоваться только они.

См. также

• Атака на генератор случайных чисел
• Crypto AG — швейцарская компания, специализирующаяся на коммуникациях и информационной безопасности , которая, как широко распространено мнение, позволила западным службам безопасности (включая АНБ) вставлять бэкдоры в свои криптографические машины.

Внешние ссылки

• NIST SP 800-90A – Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов
• Dual EC DRBG — Сбор информации Dual_EC_DRBG, Дэниел Дж. Бернштейн , Таня Ланге и Рубен Нидерхаген .
• О практической возможности использования Dual EC в реализациях TLS – ключевая исследовательская работа Стивена Чековея и др.
• Распространенность клептографических атак на криптосистемы на основе дискретного журнала - Адам Л. Янг , Моти Юнг (1997)
• Публикация заявки на патент США США 2007189527 , Браун, Дэниел Р.Л. и Ванстон, Скотт А., «Генерация случайных чисел на основе эллиптической кривой», поручено Certicom Corp.   по бэкдору Dual_EC_DRBG и способам отрицания бэкдора.
• Комментарии к Dual-EC-DRBG/NIST SP 800-90, проект от декабря 2005 г., статья Кристиана Гьёстина от марта 2006 г., в которой делается вывод о том, что Dual_EC_DRBG предсказуем и, следовательно, небезопасен.
• Анализ безопасности генератора случайных чисел с эллиптической кривой NIST SP 800-90 . Анализ безопасности Dual_EC_DRBG Дэниела Р. Л. Брауна и Кристиана Гьёстина в 2007 году. Хотя Браун, по крайней мере, знал о бэкдоре (из его патента 2005 года), бэкдор прямо не упоминается. Предполагается использование констант без бэкдора и большее усечение выходных битов, чем указано в Dual_EC_DRBG.
• О возможности бэкдора в NIST SP800-90 Dual Ec Prng Дэн Шумоу и Нильс Фергюсон представили презентацию, которая сделала потенциальный бэкдор широко известным.
• Многие недостатки Dual_EC_DRBG — упрощенное объяснение Мэтью Грина того, как и почему работает бэкдор.
• Еще несколько замечаний о генераторах случайных чисел АНБ – Мэтью Грин
• Извините, RSA, я просто не верю в это – краткое изложение и график Dual_EC_DRBG и общеизвестные сведения.
• [Cfrg] Dual_EC_DRBG ... [было RE: Запрос об отстранении сопредседателя CFRG] Электронное письмо Дэниела Р.Л. Брауна от декабря 2013 года, защищающее Dual_EC_DRBG и стандартный процесс.
• ДУЭЛЬ ИЗ-ЗА DUAL_EC_DRBG: ПОСЛЕДСТВИЯ ПОВРЕЖДЕНИЯ ПРОЦЕССА КРИПТОГРАФИЧЕСКОЙ СТАНДАРТИЗАЦИИ Статья Костюка и Ландау о том, что международное криптографическое сообщество в значительной степени продолжает доверять NIST, несмотря на Dual EC DRBG.