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 является «устойчивым к обратному отслеживанию» и «устойчивым к предсказанию». Первое — это общее понятие «прямой секретности» PRNG: в случае компрометации состояния злоумышленник не может восстановить исторические состояния и выходы. Последнее означает, что если состояние скомпрометировано и впоследствии повторно заполнено с достаточной энтропией, безопасность восстанавливается. [4]
Попытка доказательства безопасности для Dual_EC_DRBG утверждает, что для обеспечения безопасности Dual_EC_DRBG требуется, чтобы три проблемы были математически сложными: задача принятия решений Диффи-Хеллмана , задача икс-логарифма и задача усеченной точки. [5] Задача принятия решений Диффи-Хеллмана широко признана сложной. [5] Задача икс-логарифма не широко признана сложной. Приводятся некоторые доказательства того, что эта задача сложная, но эти доказательства не являются окончательными. [5] Таким образом, доказательство безопасности сомнительно и будет признано недействительным, если будет показано, что задача икс-логарифма эффективно решаема. Задача усеченной точки требует достаточного количества битов для усечения точки, выбранной Dual_EC_DRBG, чтобы сделать ее неотличимой от действительно случайного числа. [5] Однако было показано, что усечение 16 бит, значение по умолчанию, указанное стандартом Dual_EC_DRBG, недостаточно для того, чтобы сделать вывод неотличимым от истинного генератора случайных чисел [6], и, следовательно, делает недействительным доказательство безопасности Dual_EC_DRBG при использовании значения усечения по умолчанию.
В рамках программы Bullrun АНБ внедрило бэкдоры в криптографические системы. Одной из таких целей в 2013 году было предложено сделать Dual_EC_DRBG. [7] АНБ добилось этого, работая в процессе стандартизации, чтобы в конечном итоге стать единственным редактором стандарта. [8] При принятии Dual_EC_DRBG в NIST SP 800-90A АНБ сослалось на использование Dual_EC_DRBG известной фирмой по безопасности RSA Security в своих продуктах. Однако 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 имеют доказательства безопасности для одного вызова для генерации псевдослучайных чисел. [14] В статье, доказывающей безопасность Hash_DRBG и HMAC_DRBG, приводится попытка доказательства безопасности для Dual_EC_DRBG, использованная в предыдущем абзаце, в качестве доказательства безопасности, чтобы сказать, что не следует использовать CTR_DRBG, поскольку это единственный DRBG в NIST SP 800-90A, для которого отсутствует доказательство безопасности. [14]
HMAC_DRBG также имеет машинно-проверенное доказательство безопасности. [15] Тезис, содержащий машинно-проверенное доказательство безопасности, также доказывает, что компрометация правильно реализованного экземпляра HMAC_DRBG не ставит под угрозу безопасность чисел, сгенерированных до компрометации. [15]
Woodage и Shumow (2019) более подробно анализируют схемы NIST; в частности, они предоставляют доказательства безопасности, которые учитывают начальную генерацию семян и повторное заполнение, которые ранее вообще не анализировались. В модели случайного оракула и при условии, что источник энтропии независим от оракула: [4]
Было показано, что 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» для своих заявок на проект Post-Quantum Cryptography . Этот интерфейс позволяет генерировать несколько наборов случайности без промежуточного стирания, стирая только тогда, когда пользователь явно сигнализирует об окончании запросов. В результате ключ может оставаться в памяти в течение длительного времени, если «расширенный интерфейс» используется неправильно. Альтернатива, предложенная Бернстайном, заключается в создании случайности для замены ключа до вывода запрошенной случайности, как это делается в ГСЧ «быстрого стирания ключа». [17]
Границы безопасности, указанные Кампаньей (2006), не учитывают никакую процедуру замены ключа. [17]
Вудедж и Шумов (2019) предлагают проект анализа ситуации, упомянутой Бернштейном, то есть утечки состояния, предполагающей большое количество случайности ( next), генерируемой между повторными ключами ( final). [4]