WikiSort.ru - Не сортированное

Dual_EC_DRBG (англ.; от Dual Elliptic Curve Deterministic Random Bit Generator) — криптографически стойкий генератор псевдослучайных чисел, разработанный Агентством национальной безопасности США, один из четырёх криптографически стойких генераторов, стандартизованных NIST как «Special Publication 800-90» (NIST SP 800-90A) в 2006 году^[1]. Одна из областей применения - криптографические системы для генерации ключей. Алгоритм основан на использовании эллиптических кривых.

Алгоритм

В стандарте NIST SP 800-90A, в описании алгоритма используются 2 функции:^[2] [3]

• φ(a) - функция, преобразующая целое число в бинарную последовательность
• x(A) - функция, возвращающая x-координату точки A

Ход работы:

1) Задается случайное значение значение t = randomseed()

2) В цикле производятся операции

1. Вычисляется значение s = φ ( x ( t * P ) )
2. Вычисляется значение r = φ ( x ( s * Q ) )
3. Обрезаются старшие 2 байта r
4. Вывод оставшихся 30 байт r
5. t = s

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

Безопасность Dual_EC_DRBG основана на сложной проблеме теории чисел — проблема Диффи-Хэлмана. Это являлось заявленной причиной включения в NIST SP 800-90.^[2] Однако производители генератора не опубликовали математическое доказательство безопасности генератора, и после публикации проекта NIST было показано, что Dual_EC_DRBG не является безопасным из-за того, что на выходе получается большое количества бит за раунд.^[4][5] Если использовать точки эллиптической кривой, заданные в стандарте, то из-за слишком большого количества бит на выходе создаётся возможность бэкдора, что даёт возможность злоумышленнику взломать генератор полным перебором. Эта проблема не была исправлена в окончательно опубликованном стандарте, оставив Dual_EC_DRBG небезопасным.^[6]

Во многих других стандартах константы, которые должны быть произвольными, выбираются принципом Nothing up my sleeve number. В Dual_EC_DRBG производители не указали как задаются константы - точки эллиптической кривой P и Q. Поскольку комитет о стандартизации был осведомлен о возможном бэкдоре, в стандарт был включен способ получения своих констант P и Q.^[7][8] Но точная формулировка в стандарте была написана так, что использование P и Q, предоставленных в стандарте, требуется для прохождения проверки FIPS 140-2, поэтому в OpenSSL были реализованы именно эти константы, несмотря на осведомленность о бэкдоре и желании использовать более надежные параметры.^[9] New York Times позже написала, что АНБ работала во время процесса стандартизации так, чтобы в конечном итоге стать единственным редактором стандарта.^[10]

Спустя некоторое время, Дэниел Браун и Кристиан Гьёстин опубликовали доказательство безопасности Dual_EC_DRBG, в котором было показано, что сформированные точки эллиптической кривой будут неотличимы от случайных, если ^[4] :

1. на выходе будет меньшее количество бит за раунд
2. точки P и Q будут независимы
3. следующие три проблемы будут принадлежать классу NP:
   • проблема Диффи-Хэлмана
   • проблема дискретного логарифмирования
   • проблема усеченной точки

Dual_EC_DRBG является довольно медленным генератором в сравнении с альтернативными генераторами, включенными в тот же стандарт, однако эти альтернативы не имеют доказательства безопасности.^[11] Дэниел Браун утверждает, что, благодаря доказательству безопасности, генератор можно использовать, несмотря на скорость его работы, при условии что использованы надежные параметры.^[11]

Предполагаемый бэкдор позволяет злоумышленнику определить внутреннее состояние генератора случайных чисел после просмотра выхода одного раунда размером 30 байт. Все будущие выходные данные генератора случайных чисел могут быть легко посчитаны, пока внешний источник энтропии не перезагрузит генератор с новым значением t₀ ^[3]. Например, использование данного генератора делает небезопасным SSL / TLS, поскольку установка TLS-соединения включает в себя отправку случайно сгенерированного числа в открытом виде.^[6] Бэкдор состоит в том, что при использовании констант P и Q из стандарта, АНБ знает такое e, что e * Q = P.^[3][12] Таким образом, e является секретным ключом, предположительно известным АНБ, а предполагаемый бэкдор является клептографическим скрытым бэкдором.^[13]

Бэкдор

Первый вывод 30 байт r₀ - это x - координата точки без начальных 16 бит. Для каждой кривой, заданной в стандарте, написаны значения X, нуля и одной или двух точек на этой кривой. Таким образом, требуется полностью перебрать не более 17 бит для восстановления исходной точки A.^[3]

Если предположить, что:

1. Что бы найти точку A, нужно s₀ * Q = A
2. Известен секретный ключ e, который задает соотношение Q * e = P

3.То домножив каждую сторону уравнения

e * A = s₀ * e * Q = s₀ * P ^[3]

Исходя из этого, есть возможность посчитать s₁ = φ ( x ( e * A) ), а затем и r₁, затем и последующие s₂,...,s_n и r₂,...,r_n. Для этого нужно лишь полным перебором найти A, умножить полученное A на e, затем умножить полученное значение на Q и вывести значение координаты x полученной точки без первых двух цифр.^[3]

История и стандартизация

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

По крайней мере два участника комиссии по стандартам и рекомендациям ANSI X9F1, Дэниель Браун и Скотт Ванстон из Certicom,^[7] были осведомлены о точном механизме и обстоятельствах, при которых возможен бэкдор, так как в январе 2005 года они подали заявку на патент ^[14], в котором было описано, как вставить или предотвратить бэкдор в Dual_EC_DRBG. Позже было подтверждено, что данная "ловушка" идентична бэкдору генератора. В 2014 году Мэтью Грин, криптограф и профессор университета Джона Хопкинса,^[15][16] критиковал комитет, за то что не был убран этот заранее известный бэкдор.^[17] В патенте были описаны 2 условия существования этого бэкдора:

1) Выбрано Q.

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

2) Не сокращен выход генератора

Усечение выхода генератора - это альтернативный способ предотвращения атаки с помощью escrow key. Усечение выхода примерно на половину обеспечит то, что выход значений R, связанных с одним выходом r, не будет поддаваться поиску. Например, для 160-битной группы эллиптических кривых число потенциальных точек R в списке составляет около 280, и поиск будет таким же сложным, как задача дискретного логарифмирования. Недостаток этого метода в том, что эффективность генератора уменьшается вдвое, так как вдвое сокращается его выход

По словам Джона Келси, одного из авторов NIST SP 800-90A, вариант выбора достоверного случайного Q был добавлен в стандарт в ответ на бэкдор^[8], но таким образом, что проверку FIPS 140-2 генератор проходил бы только с использованием Q от АНБ.^[18] Не было понятно, почему стандарт не указывал принцип выбора точки как Nothing up my sleeve number, или почему стандарт не сокращал выход генератора, который предотвращал бы атаку с помощью escrow key.

По сравнению с предыдущим генератором EC PRG усечение выхода было реализовано в Dual_EC_DRBG, который выводил от 1/2 до 2/3 от результата раунда EC PRG.^[19] Такое сокращение выхода, все равно оставляло выход генератора предсказуемым и непригодным в качестве криптографически стойкого генератора псевдослучайных чисел. В стандарте говорится, что реализации должны использовать малый max_outlen, но при этом позволяет использовать его только кратным 8 битам. В приложении C стандарта сказано, что вывод меньшего количества бит, сделает выход менее равномерно распределенным, но доказательство безопасности от Брауна полагается на то, что значение показателя max_outlen значительно меньше.

Комиссия по стандартам и рекомендациям ANSI X9F1, в которой обсуждался бэкдор, также включала в себя сотрудников из RSA Security.^[20] В 2004 году, RSA Security внедрила реализацию Dual_EC_DRBG, в которой содержался бэкдор, в RSA BSAFE как результат секретной сделки с АНБ. В 2013 году, после того, как New York Times сообщила, что Dual_EC_DRBG содержала бэкдор, в RSA Security заявили, что не знали о бэкдоре при заключении сделки с АНБ, после чего попросили пользователей переключить генератор. На конференции RSA 2014 года исполнительный председатель RSA Security Art Coviello пояснил, что компания терпела убытки от шифрования и решила перестать им заниматься, и вместо этого стала доверять стандартам и организациям по утверждениям стандартов, таких как NIST.^[21]

Предварительный вариант NIST SP 800-90A, включая Dual_EC_DRBG, был опубликован в декабре 2005 года. Окончательный вариант был опубликован в июне 2006 года. Документы, показанные Сноуденом, были интерпретированы как предположение, что в Dual_EC_DRBG реализован бэкдор от АНБ, ссылаясь на стремление АНБ быть единственным редактором стандарта.^[22] Раннее использование Dual_EC_DRBG в RSA Security было выдвинуто АНБ как аргумент для включения генератора в NIST SP 800-90A.^[23] RSA Security впоследствии сказала, что принятие Dual_EC_DRBG в NIST было причиной для его использования.^[24]

Потенциальный бэкдор не публиковался за пределами комиссии по стандартизации. Только после презентации Дана Шумова и Нильса Фергюсона в 2007 году бэкдор стал широко известен. Им было поручено реализовать Dual_EC_DRBG для Майкрософт. Кроме того, Фергюсон обсудил возможный бэкдор в 2005 году на совещании X9.^[8] Брюс Шнайер написал в статье Wired 2007 года о том, что недостатки Dual_EC_DRGB настолько очевидны, что никто не станет его использовать.^[25]

В OpenSSL реализованы все части NIST SP 800-90A, включая Dual_EC_DRBG, несмотря на его сомнительную репутацию. При этом создатели OpenSSL отметили, что они стремятся сделать OpenSSL полным и поэтому реализуют даже небезопасные алгоритмы. OpenSSL не использовал Dual_EC_DRBG по-умолчанию, и в 2013 году было обнаружено, что реализация OpenSSL Dual_EC_DRBG не работает и никто не мог ее использовать.^[18]

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

9 сентября 2013 года, из-за информации полученной от Сноудена, а также из-за доклада New York Times о бэкдоре в Dual_EC_DRBG, NIST объявил, что переиздает SP 800-90A и открывает SP 800-90B/C для общественного обсуждения. Сейчас NIST «настоятельно рекомендует» не использовать Dual_EC_DRBG.^[28][29] Публикация бэкдора в принятом стандарте стало для NIST серьезным конфузом.^[30]

RSA Security сохранила Dual_EC_DRBG как генератор по умолчанию в BSAFE даже после того, как бэкдор стал широко известен. После широко распространившегося беспокойства по поводу бэкдора была предпринята попытка найти программное обеспечение, которое использовало Dual_EC_DRBG, среди которого выделялся BSAFE. В 2013 году, начальник службы безопасности RSA Сэм Карри предоставил сайту Ars Technica обоснование выбора ошибочного стандарта Dual_EC_DRBG по умолчанию по сравнению с альтернативными генераторами.^[31] Техническая часть заявления широко критиковалась криптографами.^[32] 20 декабря 2013 года агентство Reuters сообщило, что RSA принял секретный платеж в размере 10 миллионов долларов от АНБ, чтобы установить Dual_EC_DRBG по умолчанию в двух продуктах шифрования.^[23][33]

Примечания

Ссылки

• The Many Flaws of Dual_EC_DRBG // Matthew Green (Johns Hopkins University), September 18, 2013