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

Криптографически безопасный генератор псевдослучайных чисел ( CSPRNG ) или криптографический генератор псевдослучайных чисел ( CPRNG ) — это генератор псевдослучайных чисел (PRNG) со свойствами, которые делают его пригодным для использования в криптографии . Его также называют криптографическим генератором случайных чисел ( CRNG ).

Фон

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

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

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

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

Требования

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

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

Например, если рассматриваемый ГПСЧ выдает выходные данные путем последовательного вычисления битов числа π , начиная с какой-то неизвестной точки в двоичном представлении, он вполне может удовлетворять тесту следующего бита и, таким образом, быть статистически случайным, поскольку π кажется случайным. последовательность. Однако этот алгоритм не является криптографически безопасным; Злоумышленник, который определяет, какой бит числа Пи (т. е. состояние алгоритма) используется в данный момент, сможет также вычислить все предыдущие биты.

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

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

Определения

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

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

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

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

PRNG с прямой защитой и длиной блока. $t(k)$ это ГПСЧ $G_{k}\colon \{0,1\}^{k}\to \{0,1\}^{k}\times \{0,1\}^{t(k)}$, где входная строка $s_{i}$ длиной k — это текущее состояние в период i , а выход ( $s_{i+1}$, $y_{i}$) состоит из следующего состояния $s_{i+1}$ и псевдослучайный выходной блок $y_{i}$ периода i , который выдерживает расширение состояния компромисса в следующем смысле. Если исходное состояние $s_{1}$ выбирается равномерно случайным образом из $\{0,1\}^{k}$, то для любого i последовательность $(y_{1},y_{2},\dots ,y_{i},s_{i+1})$ должны быть вычислительно неотличимы от $(r_{1},r_{2},\dots ,r_{i},s_{i+1})$, в котором $r_{i}$ выбираются равномерно случайным образом из $\{0,1\}^{t(k)}$.

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

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

Основная статья: Экстрактор случайности

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

Дизайны

Проекты CSPRNG делятся на два класса:

1. те, которые основаны на криптографических примитивах, таких как шифры и криптографические хеши ,
2. те, которые основаны на математических задачах, считались трудными.

Проекты на основе криптографических примитивов

• Безопасный блочный шифр можно преобразовать в CSPRNG, запустив его в режиме счетчика , используя, например, специальную конструкцию, которую NIST в SP 800-90A называет CTR_DRBG . CTR_DBRG обычно использует AES.
  • AES — CTR DRBG часто используется в качестве генератора случайных чисел в системах, использующих шифрование AES.
  • Схема NIST CTR_DRBG стирает ключ после вывода запрошенной случайности путем выполнения дополнительных циклов. Это расточительно с точки зрения производительности, но не сразу вызывает проблемы с прямой секретностью. Однако, осознавая влияние на производительность, NIST рекомендует «расширенный интерфейс AES-CTR-DRBG» для своих проектов пост-квантовой криптографии . Этот интерфейс позволяет генерировать несколько наборов случайных чисел без промежуточного стирания, стирая только тогда, когда пользователь явно сигнализирует об окончании запросов. В результате ключ может оставаться в памяти в течение длительного времени, если «расширенный интерфейс» используется неправильно. Новые ГСЧ с «быстрым стиранием ключа» стирают ключ случайным образом, как только случайность запрашивается.
• Поточный шифр можно преобразовать в CSPRNG. Это было сделано с помощью RC4, ISAAC и ChaCha20 , и это лишь некоторые из них.
• Криптографически безопасный хеш также может быть основой хорошего CSPRNG, используя, например, конструкцию, которую NIST называет Hash_DRBG .
• Примитив HMAC может использоваться в качестве основы CSPRNG, например, как часть конструкции, которую NIST называет HMAC_DRBG .

Теоретико-числовые конструкции

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

Практические схемы

«Практические» схемы CSPRNG включают не только алгоритм CSPRNG, но и способ его инициализации (« начального числа »), сохраняя при этом начальное число в секрете. Был определен ряд таких схем, в том числе:

• Реализации /dev/random в Unix-подобных системах.
  • Yarrow , который пытается оценить энтропийное качество входных данных и использует SHA-1 и 3DES внутри себя. Yarrow использовался в macOS и других ОС Apple примерно до декабря 2019 года, после чего перешел на Fortuna.
  • Fortuna , преемник Yarrow, который не пытается оценить энтропийное качество своих входных данных; он использует SHA-256 и «любой хороший блочный шифр». Фортуна используется во FreeBSD. Примерно с декабря 2019 года Apple перешла на Fortuna для большинства или всех ОС Apple.
  • Ядро Linux CSPRNG, которое использует ChaCha20 для генерации данных. и BLAKE2 для поглощения энтропии.
• arc4random — CSPRNG в Unix-подобных системах, который берет начало из /dev/случайный . Первоначально он основан на RC4 , но все основные реализации теперь используют ChaCha20 .
• CryptGenRandom , часть Microsoft CryptoAPI , предлагаемая в Windows. В разных версиях Windows используются разные реализации.
• ANSI Стандарт X9.17 ( Управление ключами финансовых учреждений (оптовая торговля) был принят в качестве стандарта FIPS ), который также . В качестве входных данных он принимает TDEA ( вариант шифрования 2 набор ключей ) k и (начальное значение) 64-битное случайное начальное число s . Каждый раз, когда требуется случайное число, оно:
  • Получает текущую дату/время D с максимально возможным разрешением.
  • Вычисляет временное значение t = TDEA _k ( D )
  • Вычисляет случайное значение x = TDEA _k ( s ⊕ t ) , где ⊕ обозначает побитовое исключающее или .
  • Обновляет начальное число s = TDEA _k ( x ⊕ t )
  Очевидно, что этот метод легко обобщается на любой блочный шифр; AES . Был предложен Если ключ k утек, можно предсказать весь поток X9.17; эта слабость упоминается как причина создания Тысячелистника.

Все эти вышеупомянутые схемы, за исключением X9.17, также смешивают состояние CSPRNG с дополнительным источником энтропии. Следовательно, они не являются «чистыми» генераторами псевдослучайных чисел в том смысле, что результат не полностью определяется их начальным состоянием. Это дополнение направлено на предотвращение атак, даже если исходное состояние скомпрометировано.

Стандарты

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

• ФИПС 186-4
• НИСТ СП 800-90А :

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

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

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

  В следующей версии отмечено, что заявленная степень безопасности для 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.

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

Основная статья: Dual_EC_DRBG

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

Недостатки безопасности

Атака ДУХК

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

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

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

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

• RFC   4086 , Требования случайности для безопасности
• «Энтропийный пул» Java для криптографически безопасных непредсказуемых случайных чисел. Архивировано 2 декабря 2008 г. в Wayback Machine.
• Стандартный класс Java, обеспечивающий криптостойкий генератор псевдослучайных чисел (PRNG).
• Криптографически безопасное случайное число в Windows без использования CryptoAPI
• Предполагаемая безопасность ГСЧ с эллиптической кривой ANSI-NIST , Дэниел Р.Л. Браун, 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 Statistical Test Suite и загрузка программного обеспечения.