НИСТ СП 800-90А

NIST SP 800-90A («SP» означает « специальная публикация ») — это публикация Национального института стандартов и технологий под названием «Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» . Публикация содержит спецификацию трех якобы криптографически безопасных генераторов псевдослучайных чисел для использования в криптографии : Hash DRBG (на основе хеш-функций ), HMAC DRBG (на основе HMAC ) и CTR DRBG (на основе блочных шифров в режиме счетчика ). Более ранние версии включали четвертый генератор Dual_EC_DRBG (основанный на криптографии эллиптических кривых ). Позже сообщалось, что Dual_EC_DRBG, вероятно, содержит клептографический бэкдор, США установленный Агентством национальной безопасности (АНБ).

История

NIST SP 800-90A был опубликован Национальным институтом стандартов и технологий в июне 2006 года под названием NIST SP 800-90 под названием « Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» . ^[1] Публикация содержит спецификацию трех якобы криптографически безопасных генераторов псевдослучайных чисел для использования в криптографии : Hash DRBG (на основе хеш-функций ), HMAC DRBG (на основе HMAC ) и CTR DRBG (на основе блочных шифров в режиме счетчика ).

С 24 июня 2015 года текущей версией публикации является Revision 1. Более ранние версии включали четвертый генератор Dual_EC_DRBG (на основе криптографии эллиптических кривых ). Позже сообщалось, что Dual_EC_DRBG, вероятно, содержит клептографический бэкдор США , установленный Агентством национальной безопасности (АНБ), в то время как три других генератора случайных чисел считаются бесспорными и безопасными многими криптографами. ^[2]^[3]

Являясь разработкой федерального правительства США , NIST SP 800-90A находится в общественном достоянии и доступен бесплатно.

Анализ безопасности

NIST утверждает, что каждая из четырех (измененных до трех) DBRG «устойчива к возврату» и «устойчива к прогнозированию». Первое — это общее понятие «прямой секретности» ГПСЧ: в случае компрометации состояния злоумышленник не может восстановить исторические состояния и выходные данные. Последнее означает, что если состояние будет скомпрометировано и впоследствии повторно заполнено с достаточной энтропией, безопасность будет восстановлена. ^[4]

Двойной_EC_DRBG

Попытка доказательства безопасности для Dual_EC_DRBG гласит, что для того, чтобы Dual_EC_DRBG был безопасным, необходимо, чтобы три задачи были математически сложными: решающая проблема Диффи-Хеллмана , проблема x-логарифма и проблема усеченной точки . ^[5] Решающая задача Диффи-Хеллмана широко признана сложной. ^[5] Проблема х-логарифма не считается сложной. Приводятся некоторые доказательства того, что эта проблема сложна, но эти доказательства не являются убедительными. ^[5] Таким образом, доказательство безопасности является сомнительным и будет признано недействительным, если будет доказано, что проблема x-логарифма эффективно разрешима. Проблема усеченной точки требует отсечения достаточного количества битов от точки, выбранной Dual_EC_DRBG, чтобы сделать ее неотличимой от действительно случайного числа. ^[5] Однако усечение 16 бит, значение по умолчанию, указанное стандартом Dual_EC_DRBG, оказалось недостаточным, чтобы сделать выходные данные неотличимыми от истинного генератора случайных чисел. ^[6] и, следовательно, делает недействительным доказательство безопасности Dual_EC_DRBG, когда используется значение усечения по умолчанию.

Бэкдор в Dual_EC_DRBG

В рамках программы Bullrun АНБ внедрило бэкдоры в криптографические системы. Одной из таких целей в 2013 году было предложено назвать Dual_EC_DRBG. ^[7] АНБ добилось этого, работая в процессе стандартизации и в конечном итоге став единственным редактором стандарта. ^[8] Принимая Dual_EC_DRBG в NIST SP 800-90A, АНБ сослалось на то, что известная охранная фирма RSA Security использует Dual_EC_DRBG в своих продуктах. Однако АНБ заплатило RSA Security 10 миллионов долларов за использование Dual_EC_DRBG по умолчанию в рамках сделки, которую Reuters описывает как «совершенную бизнес-лидерами, а не чистыми технологами». Поскольку контракт стоимостью 10 миллионов долларов на то, чтобы заставить RSA Security использовать Dual_EC_DRBG, был описан Reuters как секретный, люди, участвующие в процессе принятия Dual_EC_DRBG в NIST SP 800-90A, по-видимому, не были проинформированы об этом очевидном конфликте интересов. ^[9] Это может помочь объяснить, как генератор случайных чисел, который, как позже выяснилось, уступал альтернативам (помимо «черного хода»), попал в стандарт NIST SP 800-90A.

Возможность бэкдора в Dual_EC_DRBG уже была задокументирована Дэном Шумоу и Нильсом Фергюсоном в 2007 году. ^[10] но продолжал использоваться на практике такими компаниями, как RSA Security, до открытия в 2013 году. ^[2] Учитывая известные недостатки Dual_EC_DRBG, впоследствии появились обвинения в том, что RSA Security сознательно внедрила в свои продукты бэкдор АНБ. RSA отрицает намеренное использование бэкдора в своих продуктах. ^[11]

После разоблачения бэкдора АНБ NIST возобновил процесс публичной проверки стандарта NIST SP 800-90A. ^[7]^[12] Пересмотренная версия NIST SP 800-90A, в которой удален Dual_EC_DRBG, была опубликована в июне 2015 года. ^[13]

Hash_DRBG и HMAC_DRBG

Hash_DRBG и HMAC_DRBG имеют доказательства безопасности для одного вызова для генерации псевдослучайных чисел. ^[14] В документе, подтверждающем безопасность Hash_DRBG и HMAC_DRBG, цитируется попытка доказательства безопасности для Dual_EC_DRBG, использованная в предыдущем абзаце, в качестве доказательства безопасности, чтобы сказать, что не следует использовать CTR_DRBG, поскольку это единственный DRBG в NIST SP 800-90A, которому не хватает безопасности. доказательство. ^[14]

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

Вудадж и Шумоу (2019) более подробно анализируют схемы NIST; в частности, они предоставляют доказательства безопасности, учитывающие начальную генерацию и повторное заполнение, которые ранее вообще не анализировались. В модели случайного оракула и при условии, что источник энтропии не зависит от оракула: ^[4]

Hash_DBRG является надежным в смысле Додиса и др., т.е. соответствует обоим требованиям безопасности NIST.
HMAC_DBRG является надежным при соблюдении двух условий: он должен вызываться с дополнительной входной энтропией, и указанная энтропия должна удовлетворять дополнительным условиям. Все источники энтропии, одобренные NIST, удовлетворяют этим «дополнительным условиям».
HMAC_DBRG не является защищенным от пересылки при вызове без дополнительных входных данных.

CTR_DRBG

Было показано, что CTR_DRBG имеет теоретический недостаток при использовании с определенными параметрами, поскольку криптографы не учитывали размер блока шифра при разработке этого генератора псевдослучайных чисел. ^[16] CTR_DRBG кажется безопасным и неотличимым от настоящего случайного источника, когда AES используется в качестве основного блочного шифра и 112 бит берутся из этого генератора псевдослучайных чисел . ^[16] Когда в качестве основного блочного шифра используется AES и из каждого экземпляра берется 128 бит, требуемый уровень безопасности обеспечивается с оговоркой, что выходные данные 128-битного шифра в режиме счетчика можно отличить от истинного генератора случайных чисел. ^[16] Когда в качестве основного блочного шифра используется AES и из этого генератора псевдослучайных чисел берется более 128 бит, результирующий уровень безопасности ограничивается размером блока, а не размером ключа, и поэтому фактический уровень безопасности намного меньше, чем уровень безопасности. уровень, подразумеваемый размером ключа. ^[16] Также показано, что CTR_DRBG не обеспечивает ожидаемый уровень безопасности при использовании Triple DES , поскольку размер его 64-битного блока намного меньше размера 112-битного ключа, используемого для Triple DES. ^[16]

В настоящее время не существует известного способа использования этой проблемы при использовании AES.

Удаление ключа

Схема NIST CTR_DRBG стирает ключ после вывода запрошенной случайности, создавая дополнительную случайность для замены ключа. Это расточительно с точки зрения производительности, но не сразу вызывает проблемы с прямой секретностью. Однако, осознавая влияние на производительность, NIST рекомендует «расширенный интерфейс AES-CTR-DRBG» для своих проектов пост-квантовой криптографии . Этот интерфейс позволяет генерировать несколько наборов случайных чисел без промежуточного стирания, стирая только тогда, когда пользователь явно сигнализирует об окончании запросов. В результате ключ может оставаться в памяти в течение длительного времени, если «расширенный интерфейс» используется неправильно. Альтернатива, предложенная Бернштейном, состоит в том, чтобы создать случайность для замены ключа до того, как будет выведена запрошенная случайность, как это делается в ГСЧ с «быстрым стиранием ключа». ^[17]

Границы безопасности, о которых сообщает Кампанья (2006), не учитывают какую-либо процедуру замены ключей. ^[17]

Вудадж и Шумоу (2019) представляют предварительный анализ ситуации, упомянутой Бернштейном, то есть утечки состояния, предполагающей большое количество случайности ( next), генерируемый между повторным набором ключей ( final). ^[4]

История версий NIST SP 800-90A

Баркер, Элейн; Келси, Джон (июнь 2006 г.). «Специальная публикация NIST 800-90: Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . Национальный институт стандартов и технологий . Проверено 27 ноября 2016 г. Снято в марте 2007 г.
Баркер, Элейн; Келси, Джон (март 2007 г.). «Специальная публикация NIST 800-90: Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов (пересмотренная версия)» (PDF) . Национальный институт стандартов и технологий . Проверено 27 ноября 2016 г. Снято в январе 2012 г.
Баркер, Элейн; Келси, Джон (январь 2012 г.). «Специальная публикация NIST 800-90A: Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . Национальный институт стандартов и технологий . doi : 10.6028/NIST.SP.800-90A . Проверено 19 ноября 2016 г. Снято в июне 2015 г.
Баркер, Элейн; Келси, Джон (июнь 2015 г.). «NIST выпустил специальную публикацию (SP) 800-90A, редакция 1: Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . Национальный институт стандартов и технологий . doi : 10.6028/NIST.SP.800-90Ar1 . Проверено 19 ноября 2016 г.

См. также

НИСТ СП 800-90Б

Ссылки

^ Баркер, Элейн; Келси, Джон (июнь 2006 г.). «Специальная публикация NIST 800-90: Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . Национальный институт стандартов и технологий . Проверено 27 ноября 2016 г.
^ Jump up to: ^а ^б Грин, Мэтью (20 сентября 2013 г.). «RSA предупреждает разработчиков не использовать продукты RSA» . Проверено 23 августа 2014 г.
^ Шнайер, Брюс (15 ноября 2007 г.). «Странная история Dual_EC_DRBG» . Проверено 25 ноября 2016 г.
^ Jump up to: ^а ^б ^с Вудадж, Джоан; Шумоу, Дэн (2019). «Анализ NIST SP 800-90A» (PDF) . Достижения в криптологии – EUROCRYPT 2019 . Том. 11477. стр. 151–180. дои : 10.1007/978-3-030-17656-3_6 .
^ Jump up to: ^а ^б ^с ^д Браун, Дэниел Р.Л.; Йёстин, Кристиан (15 февраля 2007 г.). «Анализ безопасности генератора случайных чисел с эллиптической кривой NIST SP 800-90» (PDF) . Проверено 19 ноября 2016 г.
^ Шенмейкерс, Берри; Сидоренко, Андрей (29 мая 2006 г.). «Криптоанализ псевдослучайного генератора двойной эллиптической кривой» (PDF) . Проверено 20 ноября 2016 г.
^ Jump up to: ^а ^б Перлрот, Николь (10 сентября 2013 г.). «Правительство объявляет о шагах по восстановлению доверия к стандартам шифрования» . Нью-Йорк Таймс . Проверено 23 августа 2014 г.
^ Болл, Джеймс; Боргер, Джулиан; Гринвальд, Гленн (5 сентября 2013 г.). «Раскрыто: как шпионские агентства США и Великобритании нарушают конфиденциальность и безопасность в Интернете» . Хранитель . Проверено 23 августа 2014 г.
^ Менн, Джозеф (20 декабря 2013 г.). «Эксклюзив: секретный контракт, связывающий АНБ и пионера индустрии безопасности» . Рейтер . Проверено 23 августа 2014 г.
^ Брюс Шнайер (15 ноября 2007 г.). «Включило ли АНБ секретный бэкдор в новый стандарт шифрования?» . Проводные новости . Архивировано из оригинала 23 ноября 2015 г. Проверено 23 августа 2014 г. Альтернативный URL
^ Гудин, Дэн (20 сентября 2013 г.). «Мы не используем бэкдоры в наших криптопродуктах, — сообщает RSA клиентам» . Арс Техника . Проверено 23 августа 2014 г.
^ «NIST предлагает комментарии к проекту SP 800-90A, редакция 1» . Национальный институт стандартов и технологий . 21 апреля 2014 г. Архивировано из оригинала 23 июля 2014 г. Проверено 23 августа 2014 г.
^ Баркер, Элейн; Келси, Джон (июнь 2015 г.). «NIST выпустил специальную публикацию (SP) 800-90A, редакция 1: Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . Национальный институт стандартов и технологий . doi : 10.6028/NIST.SP.800-90Ar1 . Проверено 19 ноября 2016 г.
^ Jump up to: ^а ^б Кан, Уилсон (4 сентября 2007 г.). «Анализ основных предположений в DRBG NIST» (PDF) . Проверено 19 ноября 2016 г.
^ Jump up to: ^а ^б Йе, Кэтрин Цинру (апрель 2016 г.). «Печально известная PRG: формальная проверка генератора псевдослучайных чисел HMAC-DRBG» (PDF) . Проверено 19 ноября 2016 г.
^ Jump up to: ^а ^б ^с ^д ^и Кампанья, Мэтью Дж. (1 ноября 2006 г.). «Границы безопасности для детерминированного генератора случайных битов на основе кодовой книги NIST» (PDF) . Проверено 19 ноября 2016 г.
^ Jump up to: ^а ^б Бернштейн, Дэниел Дж. «2017.07.23: Генераторы случайных чисел с быстрым стиранием ключей: попытка устранить несколько беспорядков одновременно. #rng #forwardsecrecy #urandom #cascade #hmac #rekeying #proofs» .

[1] Баркер, Элейн; Келси, Джон (июнь 2006 г.). «Специальная публикация NIST 800-90: Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . Национальный институт стандартов и технологий . Проверено 27 ноября 2016 г.

[green-2] Jump up to: ^а ^б Грин, Мэтью (20 сентября 2013 г.). «RSA предупреждает разработчиков не использовать продукты RSA» . Проверено 23 августа 2014 г.

[3] Шнайер, Брюс (15 ноября 2007 г.). «Странная история Dual_EC_DRBG» . Проверено 25 ноября 2016 г.

[Woodage2019-4] Jump up to: ^а ^б ^с Вудадж, Джоан; Шумоу, Дэн (2019). «Анализ NIST SP 800-90A» (PDF) . Достижения в криптологии – EUROCRYPT 2019 . Том. 11477. стр. 151–180. дои : 10.1007/978-3-030-17656-3_6 .

[DualECProof-5] Jump up to: ^а ^б ^с ^д Браун, Дэниел Р.Л.; Йёстин, Кристиан (15 февраля 2007 г.). «Анализ безопасности генератора случайных чисел с эллиптической кривой NIST SP 800-90» (PDF) . Проверено 19 ноября 2016 г.

[6] Шенмейкерс, Берри; Сидоренко, Андрей (29 мая 2006 г.). «Криптоанализ псевдослучайного генератора двойной эллиптической кривой» (PDF) . Проверено 20 ноября 2016 г.

[nyt-7] Jump up to: ^а ^б Перлрот, Николь (10 сентября 2013 г.). «Правительство объявляет о шагах по восстановлению доверия к стандартам шифрования» . Нью-Йорк Таймс . Проверено 23 августа 2014 г.

[8] Болл, Джеймс; Боргер, Джулиан; Гринвальд, Гленн (5 сентября 2013 г.). «Раскрыто: как шпионские агентства США и Великобритании нарушают конфиденциальность и безопасность в Интернете» . Хранитель . Проверено 23 августа 2014 г.

[NSApaid-9] Менн, Джозеф (20 декабря 2013 г.). «Эксклюзив: секретный контракт, связывающий АНБ и пионера индустрии безопасности» . Рейтер . Проверено 23 августа 2014 г.

[wired-schneier-10] Брюс Шнайер (15 ноября 2007 г.). «Включило ли АНБ секретный бэкдор в новый стандарт шифрования?» . Проводные новости . Архивировано из оригинала 23 ноября 2015 г. Проверено 23 августа 2014 г. Альтернативный URL

[11] Гудин, Дэн (20 сентября 2013 г.). «Мы не используем бэкдоры в наших криптопродуктах, — сообщает RSA клиентам» . Арс Техника . Проверено 23 августа 2014 г.

[12] «NIST предлагает комментарии к проекту SP 800-90A, редакция 1» . Национальный институт стандартов и технологий . 21 апреля 2014 г. Архивировано из оригинала 23 июля 2014 г. Проверено 23 августа 2014 г.

[13] Баркер, Элейн; Келси, Джон (июнь 2015 г.). «NIST выпустил специальную публикацию (SP) 800-90A, редакция 1: Рекомендации по генерации случайных чисел с использованием детерминированных генераторов случайных битов» (PDF) . Национальный институт стандартов и технологий . doi : 10.6028/NIST.SP.800-90Ar1 . Проверено 19 ноября 2016 г.

[Kan-14] Jump up to: ^а ^б Кан, Уилсон (4 сентября 2007 г.). «Анализ основных предположений в DRBG NIST» (PDF) . Проверено 19 ноября 2016 г.

[HMACProof-15] Jump up to: ^а ^б Йе, Кэтрин Цинру (апрель 2016 г.). «Печально известная PRG: формальная проверка генератора псевдослучайных чисел HMAC-DRBG» (PDF) . Проверено 19 ноября 2016 г.

[CTRProof-16] Jump up to: ^а ^б ^с ^д ^и Кампанья, Мэтью Дж. (1 ноября 2006 г.). «Границы безопасности для детерминированного генератора случайных битов на основе кодовой книги NIST» (PDF) . Проверено 19 ноября 2016 г.

[fke-17] Jump up to: ^а ^б Бернштейн, Дэниел Дж. «2017.07.23: Генераторы случайных чисел с быстрым стиранием ключей: попытка устранить несколько беспорядков одновременно. #rng #forwardsecrecy #urandom #cascade #hmac #rekeying #proofs» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]