CSPRNG¶

CSPRNG (от англ. Cryptographically Secure Pseudo-Random Number Generator) — это криптографически стойкий генератор псевдослучайных чисел, алгоритм или устройство, предназначенное для генерации последовательностей чисел, которые неотличимы от истинно случайных для любого вероятностного полиномиального противника. В отличие от обычных генераторов псевдослучайных чисел (PRNG), CSPRNG удовлетворяет строгим требованиям безопасности, предъявляемым в криптографии, и используется для создания ключей шифрования, инициализирующих векторов, одноразовых номеров (nonce) и других критических для безопасности данных.

¶История

Потребность в CSPRNG возникла с развитием компьютерной криптографии в середине XX века. Ранние криптографические системы, такие как шифр Вернама (одноразовый блокнот), требовали истинно случайных ключей, но их генерация была медленной и дорогой. Псевдослучайные генераторы, основанные на линейных конгруэнтных методах (например, алгоритм Лемера, 1949 год), оказались предсказуемыми и непригодными для криптографии.

В 1980-х годах были разработаны первые криптостойкие генераторы, в том числе алгоритм Блюма — Блюма — Шуба (BBS), предложенный в 1986 году. Его безопасность основана на сложности факторизации больших целых чисел. В 1990-х годах стандартизация CSPRNG началась с появлением алгоритмов, таких как Yarrow (1999 год, разработан Брюсом Шнайером и Джоном Келси) и Fortuna (2003 год, улучшенная версия Yarrow). В 2000-х годах были приняты национальные стандарты, включая американский NIST SP 800-90A (2007 год) и российский ГОСТ Р 34.10-2012 (в части генерации случайных чисел).

¶Требования к CSPRNG

Криптографически стойкий генератор должен удовлетворять следующим свойствам:

• Статистическая случайность: выходная последовательность должна проходить все статистические тесты на случайность (например, тесты NIST STS, Diehard).
• Непредсказуемость: знание предыдущих выходных битов не должно позволять вычислить последующие биты с вероятностью, существенно превышающей 1/2.
• Устойчивость к атакам с восстановлением состояния: даже если злоумышленник узнает внутреннее состояние генератора в некоторый момент, он не сможет восстановить предыдущие выходные данные (свойство forward secrecy).
• Устойчивость к атакам с компрометацией энтропии: если источник энтропии даёт меньше случайности, чем ожидалось, генератор не должен выдавать предсказуемые результаты.

¶Классификация

CSPRNG можно разделить на несколько типов по принципу работы:

¶Детерминированные генераторы (DRBG)

Эти алгоритмы используют только начальное значение (seed) и детерминированную функцию для генерации последовательности. Примеры:

• Алгоритм Блюма — Блюма — Шуба (BBS): основан на квадратичных вычетах по модулю составного числа. Безопасность доказана при условии сложности факторизации.
• Генераторы на основе блочных шифров: например, режим CTR (Counter) с использованием AES. Выходные биты получаются шифрованием последовательных значений счётчика.
• Генераторы на основе хеш-функций: например, Hash_DRBG (NIST SP 800-90A), использующий SHA-256.

¶Генераторы с накоплением энтропии

Эти генераторы периодически смешивают выходные данные с новыми случайными значениями из внешних источников (энтропийных пулов). Примеры:

• Yarrow: использует два пула энтропии (быстрый и медленный) и алгоритм на основе блочного шифра.
• Fortuna: улучшенная версия Yarrow с 32 пулами, что позволяет избежать атак на основе задержек.
• Linux /dev/urandom: в современных ядрах Linux использует алгоритм ChaCha20 для генерации и смешивает энтропию из аппаратных источников (например, тайминги прерываний).

¶Аппаратные генераторы (HRNG)

Хотя формально CSPRNG является программным алгоритмом, часто в системах используются аппаратные источники истинной случайности (TRNG), которые затем подаются на вход CSPRNG для увеличения пропускной способности. Примеры: чипы Intel RDRAND, микроконтроллеры с датчиками шума.

¶Применение

CSPRNG используется в следующих областях:

• Криптографические протоколы: генерация ключей для TLS, SSH, IPsec, PGP.
• Электронная подпись: создание одноразовых случайных чисел (nonce) для алгоритмов, таких как ECDSA и DSA. Утечка nonce (например, при повторном использовании) позволяет восстановить закрытый ключ.
• Генерация паролей и токенов: создание криптостойких паролей, сессионных идентификаторов, API-ключей.
• Инициализирующие векторы (IV): для режимов шифрования (CBC, GCM) требуется случайный IV, который не должен повторяться.
• Соль для хешей: предотвращение атак по радужным таблицам при хранении паролей.

¶Примеры алгоритмов и стандартов

¶NIST SP 800-90A

Стандарт Национального института стандартов и технологий США (NIST) определяет три детерминированных генератора:

• Hash_DRBG: на основе хеш-функции (SHA-256, SHA-512).
• HMAC_DRBG: на основе HMAC.
• CTR_DRBG: на основе блочного шифра (AES-128, AES-256).

Эти генераторы используются в операционных системах (Windows, macOS) и библиотеках (OpenSSL, Crypto++).

¶ГОСТ Р 34.10-2012

Российский стандарт на электронную подпись включает требования к CSPRNG. В частности, используется генератор на основе хеш-функции «Стрибог» (ГОСТ Р 34.11-2012) или блочного шифра «Кузнечик» (ГОСТ Р 34.12-2015). Алгоритм определён в методических рекомендациях Р 1323565.1.006-2017.

¶ChaCha20

Потоковый шифр ChaCha20 (разработан Дэниелом Бернштейном в 2008 году) часто используется как CSPRNG. Например, в ядре Linux (начиная с версии 4.8) генератор /dev/urandom основан на ChaCha20. Алгоритм быстр, устойчив к атакам и не требует сложных вычислений.

¶Критика и уязвимости

Несмотря на теоретическую стойкость, на практике CSPRNG могут быть скомпрометированы:

• Недостаточная энтропия: если источник начальной случайности (seed) предсказуем, генератор выдаёт предсказуемые числа. Пример — атака на генератор Debian OpenSSL (2006–2008 годы), когда из-за ошибки в коде энтропия была снижена до 15–20 бит, что позволило восстановить все сгенерированные ключи.
• Атаки на состояние: злоумышленник, имеющий доступ к памяти процесса, может прочитать внутреннее состояние генератора. Для защиты используется свойство backtracking resistance (невозможность восстановления прошлых значений).
• Аппаратные закладки: в 2013 году в документах Эдварда Сноудена упоминалось, что АНБ США могло влиять на стандарт NIST SP 800-90A, чтобы ослабить генератор Dual_EC_DRBG (на основе эллиптических кривых). Этот генератор был признан скомпрометированным и исключён из стандарта в 2014 году.
• Проблемы с реализацией: ошибки в коде (например, в библиотеке OpenSSL в 2012 году) могут приводить к повторению случайных чисел.

¶Интересные факты

• В 2018 году исследователи из Университета Мичигана показали, что некоторые микроконтроллеры (например, ESP32) имеют встроенные аппаратные CSPRNG, которые при неправильной инициализации могут выдавать предсказуемые значения.
• В операционной системе FreeBSD используется генератор Yarrow, а в OpenBSD — ChaCha20.
• Российский стандарт ГОСТ Р 34.10-2012 требует использования CSPRNG, сертифицированного Федеральной службой по техническому и экспортному контролю (ФСТЭК России).

¶Источники

• NIST Special Publication 800-90A Rev. 1, «Recommendation for Random Number Generation Using Deterministic Random Bit Generators», 2015.
• Bruce Schneier, «Applied Cryptography», 2nd edition, 1996.
• ГОСТ Р 34.10-2012, «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».
• RFC 4086, «Randomness Requirements for Security», 2005.
• Документация ядра Linux: «/dev/random and /dev/urandom implementation», 2016.
• M. Blum, S. Micali, «How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits», 1984.