NIST SP 800-90A — («SP» — сокращение от , «специальная публикация») — публикация Национального института стандартов и технологий () с названием «Рекомендация для генерации случайных чисел с использованием детерминированных генераторов случайных битов» (). Публикация содержит описания трех предположительно криптографически стойких генераторов псевдослучайных чисел для использования в криптографии: Hash_DRBG (на основе хеш-функций), HMAC_DRBG (на основе хеш-кода аутентификации сообщений) и CTR_DRBG (на основе блочных шифров в режиме счетчика).
С 24 июня 2015 года текущей версией издания является Редакция 1 (). Более ранние версии включали четвёртый генератор, Dual_EC_DRBG (основанный на эллиптической криптографии). Позже сообщалось, что Dual_EC_DRBG, вероятно, содержит клептографический бэкдор, внедренный Агентством национальной безопасности, в то время как другие три генератора случайных чисел принимаются как непротиворечивые и безопасные несколькими криптографами.
NIST SP 800-90А является общественным достоянием и находится в свободном доступе, так как представляет из себя исследование федерального правительства США.
Hash_DRBG
HASH-DRBG основан на хеш-функции SH : {0, 1}∗ → {0, 1}l из семейства криптографических хеш-функций SHA. Состояние имеет вид S = (V, C, cnt), где V ∈ {0, 1}len — счетчик, который хешируется для создания конечных блоков, значение которого обновляется во время каждого вызова генератора; С — константа, зависящая от порождающего элемента (), а cnt — счетчик повторного заполнения. cnt указывает количество запросов псевдослучайных битов с момента получения нового значения, принятого от истинно случайного генератора во время создания экземпляра или повторного заполнения.
Алгоритм генерации для HASH-DRBG. Если в вызове generate используется дополнительный вход, он хэшируется и добавляется в счетчик V по модулю 2len во время процесса инициализации. Выходные блоки rj затем формируются путем хеширования счетчика V. В конце вызова счетчик хэшируется с отдельным префиксом, а результирующая строка вместе с константой C и cnt добавляется к V, результат такой операции задается как обновленный счетчик.
Константа C обновляется только во время повторного заполнения (когда она снова является производной от новой переменной V) и добавляется в переменную состояния V во время каждого обновления состояния. Константа C позволяет убедиться, что даже если предыдущий счетчик V дублируется в какой-то момент в разных периодах повторного заполнения (почти наверняка различных), счетчик при следующем обновлении значения будет препятствовать повторению предыдущей последовательности состояний. Стандарт определяет V и C как переменные критического состояния безопасности.
Входные данные: S = (V, C, cnt), β, addin Выходные данные: S' = (V', C, cnt'), R if 0 ← check(S, β, addin) then Return (error, ⊥) if addin ≠ ε then w ← SH(0x02||V||addin) V0 = (V + w) mod 2^len else V(0) ← V temp ← ε m ← [β/l] for j = 1, . . . , m do r(j) ← SH(V(j−1)) V(j) ← (V(j−1) + 1) mod 2^len temp ← temp||r(j) R ← left(temp, β) H ← SH(0x03||V(0)) V' ← (V(0) + H + C + cnt) mod 2^len cnt' ← cnt + 1 return (V', C, cnt')
HMAC_DRBG
HMAC — это код аутентификации (проверки подлинности) сообщений, использующий хеш-функции, который был введен Михиром Беллэром () и его коллегами и впоследствии стандартизирован. HMAC-DRBG использует HMAC: {0, 1}l×{0, 1}* → {0, 1}l для генерации блоков псевдослучайного вывода. Состояние имеет вид S = (K, V, cnt), где стандарт определяет K и V как критические для безопасности переменные секретного состояния. Предполагается, что после инициализации начальным состоянием является S0 = (K0, V0, cnt0), где cnt0 = 1 и K0, V0 ← {0, 1}len. Здесь K ∈ {0, 1}l используется в качестве ключа HMAC, V ∈ {0, 1}l является счетчиком, и cnt обозначает счетчик повторного заполнения.
Алгоритм генерации использует функцию update, которая используется для добавления любых дополнительных входных данных в переменные состояния K и V, и обновляет оба в одностороннем порядке. Если в вызов включены дополнительные входные данные, выполняется дополнительная пара обновлений. Сам алгоритм генерации для HMAC-DRBG работает следующим образом: процесс инициализации добавляет любые дополнительные входные данные в переменные состояния через функцию update; если дополнительные входные данные не включены в вызов, состояние остается неизменным. За К0, V0 обозначим переменные состояния, соответствующие этому процессу, после чего результирующие блоки автоматически генерируются путем итеративного применения алгоритма HMAC(К0,·) для текущего счетчика Vj-1, выходному блоку rj и следующему значению счетчика Vj приравнивается результирующая строка. Ключ K0 остается неизменным на протяжении каждой итерации. По завершении вызова окончательный процесс обновляет K и V с помощью функции update.
Функция update Входные данные: addin, K, V Выходные данные: K, V K ← HMAC(K, V||0x00||addin) V ← HMAC(K, V) if addin ≠ ε then K ← HMAC(K, V||0x01||addin) V ← HMAC(K, V) return (K, V)
функция generate Входные данные: S = (K, V, cnt), β, addin Выходные данные: S' = (K', V', cnt'), R if 0 ← check(S, β, addin) then return (error, ⊥) if addin ≠ ε then (K0, V0) ← update(addin, K, V) else (K0, V(0)) ← (K, V) temp ← ε ; m ← [β/l] for j = 1, . . . , m do V(j) ← HMAC(K0, V(j−1)) r(j) ← V(j) temp ← temp||r(j) R ← left(temp, β) (K', V') ← update(addin, K0, V(m)) cnt' ← cnt + 1 return (R, (K', V', cnt'))
CTR_DRBG
CTR_DRBG основан на алгоритме блочного шифра, функция шифрования которого E : {0, 1}k × {0, 1}l → {0, 1}l используется в CTR-режиме (режиме счетчика). Состояние имеет вид S = (K, V, cnt), где K ∈ {0, 1}k используется в качестве ключа для блочного шифра, V ∈ {0, 1}l является счетчиком, а cnt обозначает счетчик повторного заполнения. Стандарт утверждает, что K и V являются критическими переменными состояния безопасности. Инициализация возвращает начальное состояние S0 = (К0, V0, cnt0), где cnt0 = 1 и K0 ← {0, 1}k, V0 ← {0, 1}l.
Как и в HMAC_DRBG алгоритм использует функцию update для одностороннего обновления переменных состояния K и V, а также для включения любых дополнительных входов данных (которые передаются функции update с помощью параметра provided_data). Функция запускает блочный шифр в CTR-режиме с использованием текущего ключа и счетчика, объединяя результирующие выходные блоки rj. Затем крайние слева κ+l бит отсекаются, и значения provided_data встраиваются внутрь с помощью операции XOR. Функция update вызывается каждым из других процессов таким образом, что это гарантирует, что provided_data точно имеет длину в κ+l бит.
Существует два варианта CTR_DRBG в зависимости от того, используется ли производящая функция. Производящая функция CTR_DRBG df объединяет в себе функцию, основанную на CBC-MAC, и возможность извлечения почти равномерного выхода из достаточно высокоэнтропийных входов. В случае, если производящая функция df не используется, строки дополнительного входа addin ограничены до не более (κ + l) — бит в длину. Процесс инициализации подключает каждый дополнительный вход к функции update: если производящая функция используется, то строка дополнительного входа представляет из себя строку (κ + l)-бит с CTR_DRBG df до начала этого процесса. Если дополнительный вход не используется, состояние остается неизменным, и addin имеет значение 0(κ+l) (для формирования входных данных для функции update во время финальной процедуры при завершении вызова). Выходные блоки rj затем создаются итеративно с помощью блочного шифра в CTR-режиме. Ключ K остаётся неизменным на протяжении всех этих итераций. При завершении вызова окончательный процесс обновляет оба K и V через вызов функции update.
Функция update Входные данные: provided data, K, V Выходные данные: K, V temp ← ε m ← [(κ + l)/l] for j = 1, . . . , m do V ← (V + 1) mod 2^l C(i) ← E(K, V) temp ← temp||Ci temp ← left(temp, (κ + l)) K||V ← temp ⊕ provided data return (K, V)
функция generate Входные данные: S = (K, V, cnt), β, addin Выходные данные: S' = (K', V', cnt'), R if 0 ← check(S, β, addin) then return (error, ⊥) if addin ≠ ε then if derivation function used then addin ← df(addin, (κ + l)) else if len(addin) < (κ + l) then addin ← addin||0^(κ+l−len(addin)) (K0, V0) ← update(addin, K, V ) else addin ← 0^κ+l; (K0, V(0)) ← (K, V) temp ← ε ; m ← [β/l] for j = 1, . . . , m do V(j) ← (V(j−1) + 1) mod 2^l r(j) ← E(K0, V(j)) temp ← temp||r(j) R ← left(temp, β) (K', V') ← update(addin, K0, V(m)) cnt' ← cnt + 1 return (R, (K', V', cnt'))
Бэкдор в Dual_EC_DRBG
Dual_EC_DRBG была изъята из публикации с выпуском первой редакции документа. Причиной этому стало потенциальное существование бэкдора. Бэкдор — намеренно встроенный дефект алгоритма, позволяющий получить несанкционированный доступ к данным или удалённому управлению компьютеромJ.P. Aumasson Cryptographic bacdooring .
В рамках программы Bullrun АНБ вставляет бэкдоры в криптографические системы. Dual_EC_DRBG был предположительно одной из целей в 2013 году. В процессе работ по стандартизации, АНБ добилось того, что в конечном итоге стало единственным редактором стандарта. При получении доступа к Dual_EC_DRBG, принятого в NIST SP 800-90A, АНБ процитировало использование Dual_EC_DRBG известной охранной фирмой RSA Security в своих продуктах. Однако компании RSA Security было выплачено NSA в размере 10 миллионов долларов США за использование Dual_EC_DRBG по умолчанию в своих продуктах. Reuters описывает эту сделку как «обработанную бизнес-лидерами, а не чистыми технологами». Поскольку контракт на 10 миллионов долларов, чтобы заставить RSA Security использовать Dual_EC_DRBG, был описан Reuters как секретный, люди, участвовавщие в процессе принятия Dual_EC_DRBG в NIST SP 800-90A, предположительно не были осведомлены об этом очевидном конфликте интересов. Это может помочь объяснить, как генератор случайных чисел, который позже показал, что он уступает альтернативным аналогам (в дополнение к вероятному бэкдору), приняли как стандарт в NIST SP 800-90A.
Хотя потенциал для бэкдора в Dual_EC_DRBG уже был задокументирован Дэном Шумовым и Нильсом Фергюсоном в 2007 году, он продолжал использоваться в выпускаемых продуктах такими компаниями, как RSA Security до 2013 года. Учитывая известные недостатки в Dual_EC_DRBG, впоследствии появились обвинения в том, что RSA Security сознательно вставила бэкдор NSA в свои продукты. RSA отрицает сознательную вставку бэкдора в свои продукты.
После того, как бэкдор был обнаружен, NIST возобновил процесс государственной проверки стандарта NIST SP 800-90А. Пересмотренная версия NIST SP 800-90A, в которой Dual_EC_DRBG был удален, опубликована в июне 2015 года.
Анализ безопасности Hash_DRBG и HMAC_DRBG имеют доказательства безопасности для генерации псевдослучайных последовательностей. Документ, подтверждающий безопасность Hash_DRBG и HMAC_DRBG цитирует попытки доказательства безопасности для Dual_EC_DRBG, высказывая, что не следует использовать CTR_DRBG, потому что это единственный генератор в NIST SP 800-90А, для которого отсутствуют доказательства безопасности.
HMAC_DRBG также имеет машинно-подтвержденное доказательство безопасности. Тезис, содержащий проверенное вычислительными методами доказательство безопасности, также доказывает, что взлом правильно реализованного экземпляра HMAC_DRBG не ставит под угрозу безопасность чисел, созданных до взлома.