Криптографически безопасный генератор псевдослучайных чисел

редактировать

Тип функций, которые невозможно решить с помощью алгоритмов поиска корней

A криптографически безопасный генератор псевдослучайных чисел ( CSPRNG ) или криптографический генератор псевдослучайных чисел (CPRNG ) - это генератор псевдослучайных чисел (PRNG) со свойствами, которые делают его пригодным для использования в криптографии. Он также широко известен как криптографический генератор случайных чисел (CRNG ) (см. Генерация случайных чисел § «Истина» по сравнению с псевдослучайными числами ).

Большинство криптографические приложения требуют случайных чисел, например:

генерация ключа
одноразовые номера
соли в определенных схемах подписи, включая ECDSA, RSASSA-PSS

«Качество» случайности, требуемой для этих приложений, различается. Например, для создания nonce в некоторых протоколах требуется только уникальность. С другой стороны, генерация главного ключа требует более высокого качества, например, большей энтропии. А в случае одноразовых блокировок информация -теоретическая гарантия полной секретности сохраняется только в том случае, если ключевой материал поступает из истинного случайного источника с высокой энтропией, и, таким образом, любого типа генератора псевдослучайных чисел недостаточно.

В идеале генерация случайных числа в CSPRNGs использует энтропию, полученную из высококачественный источник, обычно API случайности операционной системы. Однако неожиданные корреляции были обнаружены в нескольких таких якобы независимых процессах. С теоретико-информационной точки зрения количество случайности, энтропия, которая может быть сгенерирована, равна энтропии, обеспечиваемой системой. Но иногда в практических ситуациях требуется больше случайных чисел, чем доступно энтропии. Кроме того, на практике процессы извлечения случайности из работающей системы медленные. В таких случаях иногда можно использовать CSPRNG. CSPRNG может «растянуть» доступную энтропию на большее количество битов.

Содержание

1 Требования
2 Определения
3 Извлечение энтропии
4 Схемы
- 4.1 Схемы, основанные на криптографических примитивах
- 4.2 Теоретико-числовые схемы
- 4.3 Специальные конструкции
5 Стандарты
6 Клептографический бэкдор АНБ в Dual_EC_DRBG PRNG
7 Недостатки безопасности
- 7.1 Атака DUHK
  - 7.1.1 Японская машина шифрования PURPLE
8 Ссылки
9 Внешние ссылки

Требования

Требования обычного ГПСЧ также удовлетворяются криптографически безопасным ГПСЧ, но обратное неверно. Требования CSPRNG делятся на две группы: во-первых, они должны пройти статистические тесты на случайность ; и, во-вторых, они хорошо выдерживают серьезную атаку, даже когда часть их начального или рабочего состояния становится доступной для злоумышленника.

Каждый CSPRNG должен удовлетворять тесту следующего бита. То есть, учитывая первые kбитов случайной последовательности, не существует алгоритма с полиномиальным временем, который может предсказать (k+1) -й бит с вероятность успеха не менее 50%. Эндрю Яо доказал в 1982 году, что генератор, прошедший тест следующего бита, пройдет все другие полиномиальные статистические тесты на случайность.
Каждый CSPRNG должен противостоять «расширениям с нарушением состояния». В случае, если часть или все его состояние было раскрыто (или угадано правильно), будет невозможно восстановить поток случайных чисел до раскрытия. Кроме того, если во время работы есть ввод энтропии, должно быть невозможно использовать знание состояния ввода для прогнозирования будущих условий состояния CSPRNG.

Пример: если рассматриваемый CSPRNG производит вывод путем вычисления битов π в последовательности, начиная с некоторой неизвестной точки в двоичном расширении, она вполне может удовлетворять тесту следующего бита и, таким образом, быть статистически случайной, так как π кажется случайной последовательностью. (Это будет гарантировано, если, например, π является нормальным числом.) Однако этот алгоритм не является криптографически безопасным; злоумышленник, который определяет, какой бит числа Пи (т.е. состояние алгоритма) используется в настоящее время, также сможет вычислить все предыдущие биты.

Большинство ГПСЧ не подходят для использования в качестве CSPRNG и не работают по обоим счетам. Во-первых, хотя большинство выходных данных ГПСЧ кажутся случайными для различных статистических тестов, они не сопротивляются определенному обратному проектированию. Можно найти специальные статистические тесты, специально настроенные для такого ГПСЧ, который показывает, что случайные числа не являются действительно случайными. Во-вторых, для большинства ГПСЧ, когда их состояние было раскрыто, все прошлые случайные числа могут быть отнесены назад, что позволяет злоумышленнику прочитать все прошлые сообщения, а также будущие.

CSPRNG специально разработаны, чтобы противостоять этому типу криптоанализа.

Определения

В асимптотической настройке - семейство детерминированных вычислимых функций за полиномиальное время $G К: {0, 1} К → {0, 1} p (k) {\ displaystyle G_ {k} \ двоеточие \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {p (k)}}$ ${\ displaystyle G_ {k} \ двоеточие \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {p (k)} }$ для некоторого полинома p, является генератором псевдослучайных чисел (PRNG или PRG в некоторых ссылках), если он растягивает длину своего ввода ( $p (k)>k {\ displaystyle p (k)>k}$ $p(k)>k$ для любого k), и если его результат вычислительно неотличим от истинной случайности, т.е. для любого алгоритма A с вероятностным полиномиальным временем, который выводит 1 или 0 в качестве отличителя,

| Pr x ← {0, 1} k [A (G (x)) = 1] - Pr r ← {0, 1 } p (k) [A (r) = 1] | < μ ( k) {\displaystyle \left|\Pr _{x\gets \{0,1\}^{k}}[A(G(x))=1]-\Pr _{r\gets \{0,1\}^{p(k)}}[A(r)=1]\right|<\mu (k)}

{\ displaystyle \ left | \ Pr _ {x \ gets \ {0,1 \} ^ {k}} [A (G (x)) = 1] - \ Pr _ {r \ gets \ {0,1 \} ^ { p (k)}} [A (r) = 1] \ right | <\ mu (k)}

для некоторой незначительной функции $μ {\ displaystyle \ mu}$ $\ mu$ . (Обозначение $x ← X {\ displaystyle x \ gets X}$ ${\ displaystyle x \ gets X}$ означает, что x выбирается равномерно случайным образом из множества X.)

Там эквивалентная характеристика: для любого семейства функций $G k: {0, 1} k → {0, 1} p (k) {\ displaystyle G_ {k} \ двоеточие \ {0,1 \} ^ {k } \ to \ {0,1 \} ^ {p (k)}}$ ${\ displaystyle G_ {k} \ двоеточие \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {p (k)} }$ , G является ГПСЧ тогда и только тогда, когда следующий выходной бит G не может быть предсказан алгоритмом полиномиального времени.

A с прямой защитой ГПСЧ с длиной блока $t (k) {\ displaystyle t (k)}$ ${\ displaystyle t (k)}$ - это ГПСЧ $G k: {0, 1} k → {0, 1} к × {0, 1} t (k) {\ displaystyle G_ {k} \ двоеточие \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {k} \ times \ {0,1 \} ^ {t (k)}}$ ${\ displaystyle G_ {k} \ двоеточие \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {k} \ times \ {0,1 \} ^ {t (k)}}$ , где входная строка $si {\ displaystyle s_ {i}}$ $s_ {i}$ с длиной k - текущее состояние в периоде i, а вывод ( $si + 1 {\ displaystyle s_ {i + 1}}$ ${\ displaystyle s_ {i + 1}}$ , $yi {\ displaystyle y_ {i}}$ $y_ {i}$ ) состоит из следующего состояния $si + 1 {\ displaystyle s_ {i + 1}}$ ${\ displaystyle s_ {i + 1}}$ и блок псевдослучайного вывода $yi {\ displaystyle y_ {i}}$ $y_ {i}$ периода i, так что он выдерживает расширения компрометации состояния в следующем смысле. Если начальное состояние $s 1 {\ displaystyle s_ {1}}$ $s_ {1}$ выбирается равномерно случайным образом из ${0, 1} k {\ displaystyle \ {0,1 \} ^ { k}}$ $\ {0,1 \} ^ {k}$ , тогда для любого i последовательность $(y 1, y 2,…, yi, si + 1) {\ displaystyle (y_ {1}, y_ {2}, \ точки, y_ {i}, s_ {i + 1})}$ ${\ displaystyle (y_ {1}, y_ {2}, \ dots, y_ {i}, s_ {я + 1})}$ должны быть вычислительно неотличимы от $(r 1, r 2,…, ri, si + 1) {\ displaystyle (r_ { 1}, r_ {2}, \ dots, r_ {i}, s_ {i + 1})}$ ${\ displaystyle (r_ {1}, r_ {2}, \ dots, r_ {i}, s_ {i + 1})}$ , в котором $ri {\ displaystyle r_ {i}}$ $r_ {i}$ выбираются равномерно случайным образом из ${0, 1} t (k) {\ displaystyle \ {0,1 \} ^ {t (k)}}$ ${\ displaystyle \ {0,1 \} ^ {t (k)}}$ .

Любой ГПСЧ $G: {0, 1} К → {0, 1} п (к) {\ Displaystyle G \ двоеточие \ {0,1 \} ^ {k} \ к \ {0,1 \} ^ {p (k)}}$ ${\ Displaystyle G \ двоеточие \ {0,1 \} ^ {k} \ to \ {0,1 \} ^ {p (k)}}$ можно превратить в безопасный PRNG с длиной блока $p (k) - k {\ displaystyle p (k) -k}$ ${\ displaystyle p (k) -k}$ , разделив его вывод на следующее состояние и фактический выход. Это делается путем установки $G (s) = G 0 (s) ‖ G 1 (s) {\ displaystyle G (s) = G_ {0} (s) \ Vert G_ {1} (s)}$ ${\ displaystyle G (s) = G_ { 0} (s) \ Vert G_ {1} (s)}$ , в котором $| G 0 (s) | = | s | = k {\ displaystyle | G_ {0} (s) | = | s | = k}$ ${\ displaystyle | G_ {0} (s) | = | s | = k}$ и $| G 1 (s) | знак равно п (к) - к {\ displaystyle | G_ {1} (s) | = p (k) -k}$ ${\ displaystyle | G_ {1} (s) | = p (k) -k}$ ; тогда G - это прямой защищенный ГПСЧ с $G 0 {\ displaystyle G_ {0}}$ $G_{0}$ в качестве следующего состояния и $G 1 {\ displaystyle G_ {1}}$ $G_ {1}$ как блок псевдослучайного вывода текущего периода.

Извлечение энтропии

Санта и Вазирани доказали, что несколько битовых потоков со слабой случайностью могут быть объединены для создания квазислучайного битового потока более высокого качества. Еще раньше Джон фон Нейман доказал, что простой алгоритм может устранить значительную величину смещения в любом потоке битов, который должен применяться к каждому потоку битов перед использованием любого варианта алгоритма Santha. –Vazirani design.

Конструкции

В нижеследующем обсуждении конструкции CSPRNG разделены на три класса:

те, которые основаны на криптографических примитивах, таких как шифры и криптографические хэши,
те, которые основаны на математических задачах, которые считаются сложными, и
специальные конструкции.

Последние часто вводят дополнительную энтропию, когда они доступны, и, строго говоря, не являются «чистыми» генераторами псевдослучайных чисел, поскольку их выход не полностью определяется их исходным состоянием. Это дополнение может предотвратить атаки, даже если начальное состояние нарушено.

Конструкции на основе криптографических примитивов

Защищенный блочный шифр может быть преобразован в CSPRNG, запустив его в режиме счетчика. Это делается путем выбора случайного ключа и шифрования 0, затем шифрования 1, затем шифрования 2 и т. Д. Счетчик также может быть запущен с произвольным числом, отличным от нуля. Предполагая n-битный блочный шифр, выходные данные можно отличить от случайных данных примерно через 2 блока, поскольку после проблемы дня рождения в этот момент должны стать вероятными конфликтующие блоки, тогда как блочный шифр в режиме CTR никогда не выводить идентичные блоки. Для 64-битных блочных шифров это ограничивает безопасный выходной размер до нескольких гигабайт, для 128-битных блоков ограничение достаточно велико, чтобы не влиять на типичные приложения. Однако при использовании в одиночку он не соответствует всем критериям CSPRNG (как указано выше), поскольку он не силен против «расширений компрометации состояния»: зная состояние (в данном случае счетчик и ключ), вы можете предсказывать весь прошлый вывод.
Криптографически безопасный хэш счетчика может также действовать как хороший CSPRNG в некоторых случаях. В этом случае также необходимо, чтобы начальное значение этого счетчика было случайным и секретным. Тем не менее, эти алгоритмы были мало изучены для использования таким образом, и, по крайней мере, некоторые авторы предостерегают от такого использования.

Большинство потоковых шифров работают, генерируя псевдослучайный поток битов, которые объединены ( почти всегда XORed ) с открытым текстом ; запуск шифра на счетчике вернет новый псевдослучайный поток, возможно, с более длинным периодом. Шифр может быть безопасным только в том случае, если исходный поток является хорошим CSPRNG, хотя это не обязательно так (см. RC4 cipher ). Опять же, начальное состояние должно храниться в секрете.

Теоретико-числовые планы

Алгоритм Блюма Блюма Шуба имеет доказательство безопасности, основанное на сложности квадратичной проблемы остаточности. Поскольку единственный известный способ решить эту проблему - разложить модуль на множители, обычно считается, что сложность целочисленной факторизации обеспечивает условное доказательство безопасности для алгоритма Блюма-Блюма-Шуба. Однако алгоритм очень неэффективен и, следовательно, непрактичен, если не требуется особая безопасность.
Алгоритм Блюма – Микали имеет доказательство безопасности, основанное на сложности задачи дискретного логарифмирования, но также очень неэффективен.
Дэниел Браун из Certicom написал подтверждение безопасности 2006 года для Dual_EC_DRBG, основанное на предполагаемой твердости Decisional Diffie –Предположение Хеллмана, проблема x-логарифма и проблема усеченной точки. Доказательство 2006 г. явно предполагает более низкий диапазон значений, чем в стандарте Dual_EC_DRBG, и что значения P и Q в стандарте Dual_EC_DRBG (которые, как выяснилось в 2013 г., вероятно, поддерживаются NSA) заменены значениями без резервирования.

Существует ряд практических ГПСЧ, которые были разработаны для криптографической защиты, включая

алгоритм Ярроу, который пытается оценить энтропийное качество своих входных данных. Ярроу используется в macOS (также как / dev / random ).
алгоритм ChaCha20 заменил RC4 в OpenBSD ( версия 5.4), NetBSD (версия 7.0) и FreeBSD (версия 12.0).
ChaCha20 также заменил SHA-1 в Linux в версии 4.8.
алгоритм Fortuna, преемник Yarrow, который не пытается оценивать энтропийное качество своих входных данных. Fortuna используется во FreeBSD.
функция CryptGenRandom, предоставляемая в Microsoft Интерфейс программирования криптографических приложений
ISAAC на основе варианта RC4 cipher
Эволюционный алгоритм на основе NIST Statistical Test Suite.
arc4random
AES - CTR DRBG часто используется в качестве генератор случайных чисел в системах, использующих шифрование AES.
Стандарт ANSI X9.17 (Управление ключами финансовых учреждений (оптовая торговля)), который также был принят в качестве стандарта FIPS. принимает в качестве входных данных набор ключей k TDEA (вариант 2 ) и (начальное значение) 64-битное случайное начальное число s. Каждый раз, когда требуется случайное число, оно:
- Получает текущую дату / время D с максимально возможным разрешением.
- Вычисляет временное значение t = TDEA k (D)
- Вычисляет случайное значение x = TDEA k (s ⊕ t), где ⊕ означает побитовое исключающее или.
- Обновляет начальное значение s = TDEA k (x ⊕ t)

Очевидно, эту технику легко обобщить на любой блочный шифр; AES был предложен.

Стандарты

Несколько CSPRNG были стандартизированы. Например,

Этот отозванный стандарт имеет четыре ГПСЧ. Два из них бесспорны и проверены: CSPRNG с именами Hash_DRBG и HMAC_DRBG.

Третий PRNG в этом стандарте, CTR_DRBG, основан на блочном шифре, работающем в счетчике. режим. Он имеет бесспорный дизайн, но было доказано, что он слабее с точки зрения распознавания атак, чем уровень безопасности базового блочного шифра, когда количество битов, выводимых из этого ГПСЧ, больше двух в степени размер блока базового блочного шифра в битах.

Когда максимальное количество битов, выводимых из этого PRNG, равно 2, результирующий вывод обеспечивает математически ожидаемый уровень безопасности, который, как ожидается, будет генерироваться размером ключа, но вывод показано, что он неотличим от настоящего генератора случайных чисел. Когда максимальное количество битов, выводимых из этого ГПСЧ, меньше указанного, обеспечивается ожидаемый уровень безопасности, и вывод кажется неотличимым от истинного генератора случайных чисел.

В следующей редакции отмечается, что заявленная сила защиты для CTR_DRBG зависит от ограничения общего количества запросов генерации и битов, предоставляемых для каждого запроса генерации.

Четвертый и последний PRNG в этом стандарте называется Dual_EC_DRBG. Было показано, что он не является криптографически безопасным и, как полагают, имеет клептографический бэкдор АНБ.

NIST SP 800-90A Rev.1: по сути, это NIST SP 800-90A с удаленным Dual_EC_DRBG и является заменой отозванного стандарта.
ANSI X9.17-1985, приложение C
ANSI X9.31-1998, приложение A.2.4
ANSI X9.62-1998, приложение A.4, устарело в соответствии с ANSI X9.62-2005, приложение D (HMAC_DRBG)

Хорошая ссылка поддерживается NIST.

. Также существуют стандарты для статистического тестирования новых проектов CSPRNG :

Набор статистических тестов для генераторов случайных и псевдослучайных чисел, Специальная публикация NIST 800-22.

клептографический бэкдор NSA в Dual_EC_DRBG PRNG

The Guardian и The New York Times сообщили в 2013 году, что Агентство национальной безопасности (АНБ) вставило бэкдор в генератор псевдослучайных чисел (PRNG) NIST SP. 800-90A, что позволяет АНБ легко расшифровать материалы, которые был зашифрован с помощью Dual_EC_DRBG. В обоих документах сообщается, что, как давно подозревали независимые эксперты по безопасности, АНБ вводит слабые места в стандарт 800-90 CSPRNG; это впервые подтверждается одним из совершенно секретных документов, просочившихся в «Гардиан» Эдвардом Сноуденом. АНБ тайно работало над получением собственной версии проекта стандарта безопасности NIST, одобренного для использования во всем мире в 2006 году. В просочившемся документе говорится, что «в конечном итоге АНБ стало единственным редактором». Несмотря на известный потенциал клептографического бэкдора и другие известные существенные недостатки Dual_EC_DRBG, некоторые компании, такие как RSA Security, продолжали использовать Dual_EC_DRBG до тех пор, пока бэкдор не был подтвержден в 2013 году. RSA Security получила за это выплату от АНБ в размере 10 миллионов долларов.

Бреши в безопасности

Атака DUHK

23 октября 2017 года Мэтью Грин и Надя Хенингер, криптографы из Пенсильванского университета и Университет Джона Хопкинса обнародовали подробную информацию о DUHK (Дон ' t Использовать жестко запрограммированные ключи) атака на WPA2, где поставщики оборудования используют жестко запрограммированный начальный ключ для алгоритма ANSI X9.31 RNG в сочетании с использованием генератора случайных чисел ANSI X9.31, "злоумышленник может подобрать зашифрованные данные, чтобы обнаружить остальные параметры шифрования и определить главный ключ шифрования, используемый для шифрования веб-сеансов или виртуальной частной сети (VPN) подключения ons. "

Японская шифровальная машина ФИОЛЕТОВОГО

Во время Второй мировой войны Япония использовала шифровальную машину, используемую для дипломатической связи; Соединенные Штаты смогли взломать его и прочитать его сообщения, в основном потому, что используемые «ключевые значения» были недостаточно случайными.

Ссылки

Внешние ссылки

В Wikibook Криптография есть страница по теме: Генерация случайных чисел

RFC 4086, Требования случайности для безопасности
«Пул энтропии» Java для криптографически безопасных непредсказуемых случайных чисел.
Стандартный класс Java, обеспечивающий криптографически стойкий генератор псевдослучайных чисел (PRNG).
Криптографически безопасное случайное число в Windows без использования CryptoAPI
Предполагаемая безопасность эллиптической кривой ANSI-NIST RNG, Дэниел Р.Л. Браун, IACR ePrint 2006/117.
Анализ безопасности эллиптического теста NIST SP 800-90 Генератор случайных чисел кривых, Дэниел Р.Л. Браун и Кристиан Джостин, IACR ePrint 2007/048. Появится в CRYPTO 2007.
Криптоанализ псевдослучайного генератора двойной эллиптической кривой, Берри Шонмейкерс и Андрей Сидоренко, IACR ePrint 2006/190.
Эффективные псевдослучайные генераторы на основе предположения DDH, Реза Резаэиан Фарашахи и Берри Шонмейкерс и Андрей Сидоренко, IACR ePrint 2006/321.
Анализ генератора случайных чисел Linux, Цви Гуттерман, Бенни Пинкас и Цаки Рейнман.
Документация и загрузка программного обеспечения пакета статистических тестов NIST 127>