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

Криптографически стойкий генератор псевдослучайных чисел (англ. Cryptographically secure pseudorandom number generator, CSPRNG) — это генератор псевдослучайных чисел с определенными свойствами, позволяющими использовать его в криптографии. Многие прикладные задачи криптографии требуют случайных чисел, например

• Генерация ключей
• Одноразовые случайные числа (англ. Nonces)
• Одноразовые шифроблокноты
• Соль в схемах цифровой подписи, например ECDSA

Требуемое «качество» случайности меняется от задачи к задаче. Например, генерация одн. случайного числа в некоторых протоколах требует только уникальности, тогда как генерация мастер-ключа или одноразового шифроблокнота требует высокой энтропии. В идеале, генерация случайных чисел в КСГПСЧ использует энтропию из высоконадежного источника, которым может быть аппаратный генератор случайных чисел или ход непредсказуемых процессов в системе — хотя во втором случае возможны неожиданные уязвимости ^[1]. С точки зрения теории информации количество случайности — энтропия которая может быть получена равна энтропии предоставляемой системой. Но зачастую в реальных ситуация требуется больше случайных чисел, чем можно получить при существующей энтропии. К тому же процедура получения случайности из самой системы достаточно ресурсозатратны. В таких случаях, оправданно использование КСГПСЧ — это позволяет «растянуть» имеющуюся энтропию на большее число бит. Когда вся энтропия доступна до выполнения криптографического алгоритма, получается потоковый шифр^[2]. Однако некоторые криптосистемы позволяют добавлять энтропию по мере работы, в таком случае алгоритм не является эквивалентом потокового шифра и не может использоваться в этом качестве. Таким образом, разработка потоковых шифров и КСГПСЧ тесно связаны.

Требования ^[3][4]

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

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

  Пример

  Пусть генератор основывается на выводе бит какого-то представления числа Пи, начиная с какой то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью (это было бы гарантированно, если доказать что Пи является нормальным числом). Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие биты.

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

Реализации

Рассмотрим три класса реализации КСГПСЧ:

1. На основе криптографических алгоритмов
2. На основе вычислительно сложных математических задач
3. Специальные реализации

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

Реализации на основе криптографических алгоритмов

• Безопасный блочный шифр можно преобразовать в КСГПСЧ запустив его в режиме счетчика. Таким образом, выбрав случайный ключ, можно получать следующий случайный блок применяя алгоритм к последовательным натуральным числам. Счет можно начинать с произвольного натурального числа. Очевидно, что периодом будет не больше чем 2ⁿ для n-битного блочного шифра. Также очевидно, что безопасность такой схемы полностью зависит от секретности ключа.

• Криптографически стойкая хеш-функция также может быть преобразованна в КСГПСЧ. В таком случае исходное значение счетчика должно оставаться в секрете. Однако, некоторые авторы предостерегают от такого использования хеш-функций^[5].

• Большинство потоковых шифров работают на основе генерации псевдослучайного потока бит, которые некоторым образом комбинируется (почти всегда с помощью операции XOR) с битами открытого текста. Запуск такого шифра на последовательности натуральных чисел даст новую псевдослучайную последовательность, возможно, даже с более длинным периодом. Такой метод безопасен только если в самом потоковом шифре используется надежный КСГПСЧ (что не всегда так). Опять же, начальное состояние счетчика должно оставаться секретным.

Реализации на основе математических задач

• Алгоритм Блюма — Блюма — Шуба имеет высокую криптостойкость, основанную на предполагаемой сложности факторизации целых чисел. Однако, этот алгоритм отличается очень медленной работой.
• Алгоритм Блюма — Микали (англ. Blum-Micali algorithm) основан на задаче дискретного логарифма.

Специальные реализации

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

• Алгоритм Ярроу (англ. Yarrow algorithm)^[6] который пытается определить энтропию входных данных. Он используется в FreeBSD, OpenBSD и Mac OS X
• Алгоритм Fortuna (англ. Fortuna algorithm), наследник алгоритма Ярроу.
• Специальный файл ОС UNIX /dev/random, в частности, /dev/urandom, реализованный в Linux.
• Функция CryptGenRandom предоставленная в CryptoAPI компании Microsoft ^[7]

Примечания

1. ↑ Zvi Gutterman Open to Attack: Vulnerabilities of the Linux Random Number Generator  (англ.). Проверено 15 ноября 2010.
2. ↑ Шнайер Б. 16 Генераторы псевдослучайных последовательностей и потоковые шифры // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
3. ↑ Шнайер Б. 2.8 Генерация случайных и псевдослучайных последовательностей // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
4. ↑ Peter Gutmann (1998). «Software Generation of Practically Strong Random Numbers». Proceedings of the 7th USENIX Security Symposium.
5. ↑ Adam Young, Moti Yung Malicious Cryptography: Exposing Cryptovirology. — sect 3.2: John_Wiley_&_Sons. — P. 416. — ISBN 978-0-7645-4975-5
6. ↑ Yarrow
7. ↑ Описание функции CryptoGenRandom на MSDN  (англ.). Microsoft. Архивировано из первоисточника 4 июля 2012. Проверено 15 ноября 2010.

Ссылки

• Юрий Лифшиц. Лекция 9: Псевдослучайные генераторы // Современные задачи криптографии. — Курс лекций.
• Cryptographic Random Numbers (англ.)
• Theory and Practice of Random Number Generation (англ.)
• Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Analysis of the Linux Random Number Generator (англ.)
• A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (англ.) NIST SP 800-22