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]
Попытка доказательства безопасности для Dual_EC_DRBG утверждает, что для того, чтобы Dual_EC_DRBG был безопасным, необходимо, чтобы три задачи были математически сложными: проблема принятия решения Диффи-Хеллмана , проблема x-логарифма и проблема усеченной точки. [5] Решающая задача Диффи-Хеллмана широко признана сложной. [5] Проблема x-логарифма не считается сложной. Приводятся некоторые доказательства того, что эта проблема сложна, но эти доказательства не являются убедительными. [5] Таким образом, доказательство безопасности является сомнительным и будет признано недействительным, если будет доказано, что проблема x-логарифма эффективно разрешима. Проблема усеченной точки требует отсечения достаточного количества битов от точки, выбранной 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 АНБ сослалось на то, что известная охранная фирма 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 имеют доказательства безопасности для одного вызова для генерации псевдослучайных чисел. [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]
Было показано, что 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]