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

Криптостойкий генератор случайных чисел (КГСЧ, также криптографически стойкий генератор псевдослучайных чисел, CSPRNG — Cryptographically Secure Pseudorandom Number Generator) — это алгоритм или устройство, предназначенное для генерации последовательности чисел, свойства которой неотличимы от истинно случайной последовательности для любого вероятностного противника, действующего в рамках вычислительных ограничений. В отличие от обычных генераторов псевдослучайных чисел (ГПСЧ), используемых в симуляциях или играх, КГСЧ должен удовлетворять строгим требованиям криптографической безопасности, основным из которых является непредсказуемость: знание предыдущих выходных значений не должно позволять вычислить последующие или предыдущие значения с вероятностью, существенно превышающей случайное угадывание.

Определение и основные требования

Криптостойкий генератор случайных чисел является фундаментальным строительным блоком современной криптографии. Его ключевая задача — обеспечить секретность ключей шифрования, параметров аутентификации, одноразовых номеров (nonce) и других критических данных, где случайность является обязательным условием безопасности.

Основные требования к КГСЧ:

1. Статистическая случайность: Выходная последовательность должна проходить все статистические тесты на случайность (например, тесты NIST SP 800-22 или тесты Diehard). Однако одного этого требования недостаточно, так как многие простые ГПСЧ (например, линейный конгруэнтный генератор) также проходят эти тесты, но не являются криптостойкими.
2. Непредсказуемость: Ключевое свойство. Зная полную историю выходных значений, злоумышленник не должен иметь возможности эффективно предсказать следующее или предыдущее значение. Это требование вытекает из того, что КГСЧ является детерминированным алгоритмом, работающим на основе внутреннего состояния (seed).
3. Стойкость к компрометации состояния (Forward Secrecy и Backward Secrecy): Если злоумышленник каким-либо образом узнает внутреннее состояние генератора в момент времени t, он не должен иметь возможности восстановить выходные значения, сгенерированные до момента t (backward secrecy). Также, если состояние скомпрометировано, генератор должен быть способен восстановить безопасность после добавления нового энтропийного материала (forward secrecy). На практике это достигается использованием односторонних функций (например, хеш-функций) для обновления состояния.

Отличие от обычных генераторов псевдослучайных чисел

Обычные ГПСЧ, такие как rand() в языке C или Random в Java, оптимизированы для скорости и равномерности распределения, но не для безопасности. Их внутреннее состояние часто невелико (например, 32 или 48 бит), и оно может быть восстановлено по нескольким выходным значениям. Например, для линейного конгруэнтного генератора (LCG) достаточно четырех последовательных значений, чтобы вычислить все параметры и предсказать всю последующую последовательность. КГСЧ, напротив, использует большие внутренние состояния (от 128 бит и выше) и сложные, вычислительно необратимые преобразования, что делает атаку восстановления состояния практически невыполнимой.

Устройство и принцип работы

КГСЧ обычно состоит из двух основных компонентов:

1. Источник энтропии: Это недетерминированный источник, который предоставляет начальное случайное зерно (seed) и периодически обновляет внутреннее состояние генератора. Источниками энтропии могут быть:

• Аппаратные генераторы истинных случайных чисел (TRNG), использующие физические процессы: тепловой шум в полупроводниках, джиттер тактовых генераторов, радиоактивный распад, атмосферный шум.
• Программные источники энтропии: временные метки нажатий клавиш, движения мыши, задержки ввода-вывода, вариации времени доступа к диску, сетевые пакеты. В современных операционных системах существуют специальные пулы энтропии (например, /dev/random и /dev/urandom в Linux, CryptGenRandom в Windows).

1. Детерминированный генератор (DRBG — Deterministic Random Bit Generator): Это криптографический алгоритм, который расширяет начальное зерно (энтропию) в длинную псевдослучайную последовательность. Он использует односторонние функции, такие как:

• Блочные шифры (например, AES в режиме CTR): Шифрование счетчика с использованием секретного ключа, полученного из зерна.
• Хеш-функции (например, SHA-256): Итеративное хеширование состояния.
• Специализированные алгоритмы (например, ChaCha20): Потоковый шифр, который может быть использован как генератор.

Процесс работы:

1. Инициализация: Генератор получает начальное зерно от источника энтропии. Это зерно должно иметь достаточную энтропию (обычно не менее 256 бит).
2. Генерация: При каждом запросе на получение случайных бит, генератор применяет одностороннюю функцию к своему внутреннему состоянию, выдает результат и обновляет состояние (например, увеличивает счетчик или хеширует состояние с новым значением).
3. Пересев (Reseeding): Периодически или по запросу генератор получает новую порцию энтропии из источника, чтобы предотвратить утечку состояния и обеспечить forward secrecy.

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

КГСЧ можно классифицировать по нескольким признакам:

По источнику энтропии

• Аппаратные (Hardware CSPRNG): Используют физические источники энтропии. Примеры: процессоры Intel с инструкцией RDRAND (основана на тепловом шуме), специализированные микросхемы (например, TrueRNG). Обеспечивают высокую скорость и качество случайности.
• Программные (Software CSPRNG): Используют программные источники энтропии (события ОС). Примеры: /dev/urandom в Linux, CryptGenRandom в Windows. Более медленные, но не требуют специального оборудования.

По стандартизации

• Стандартизированные алгоритмы DRBG: Определены в стандартах, таких как NIST SP 800-90A. Включают:
• Hash_DRBG: Использует хеш-функцию (например, SHA-256).
• HMAC_DRBG: Использует HMAC на основе хеш-функции.
• CTR_DRBG: Использует блочный шифр (например, AES-256) в режиме счетчика.
• Dual_EC_DRBG: Использовал эллиптические кривые. Был скомпрометирован (см. ниже).
• Нестандартизированные, но широко используемые: Например, генератор на основе потокового шифра ChaCha20 (используется в Linux /dev/urandom начиная с ядра 4.8).

Применение

КГСЧ являются критически важными для безопасности практически всех современных криптографических систем:

• Генерация ключей: Создание секретных ключей для симметричного (AES, ChaCha20) и асимметричного (RSA, ECDSA) шифрования.
• Протоколы аутентификации: Генерация одноразовых паролей (OTP), сессионных токенов, nonce для предотвращения атак повторения.
• Цифровые подписи: Генерация случайных значений (например, k в ECDSA), которые должны быть абсолютно непредсказуемыми. Утечка k позволяет восстановить закрытый ключ.
• Шифрование: Генерация векторов инициализации (IV) и соли для хеширования паролей.
• Безопасность сетей: Генерация случайных идентификаторов пакетов, портов, последовательных номеров в TCP/IP.
• Азартные игры и криптовалюты: Обеспечение честности и непредсказуемости результатов.

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

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

1. Недостаточная энтропия: Самая распространенная проблема. Если начальное зерно имеет низкую энтропию (например, при загрузке системы, когда еще не накоплено достаточно событий), генератор может выдавать предсказуемые последовательности. Это привело к уязвимости в Android-приложениях, использующих SecureRandom до версии 4.4.
2. Атаки на источник энтропии: Злоумышленник может попытаться исчерпать пул энтропии или влиять на события, используемые для его пополнения.
3. Закладки и бэкдоры: Самый известный пример — алгоритм Dual_EC_DRBG, стандартизированный NIST. В 2007 году было обнаружено, что он содержит потенциальную закладку (backdoor), позволяющую АНБ (Агентство национальной безопасности США) предсказывать его выходные данные, зная определенные параметры. Впоследствии этот алгоритм был дискредитирован и исключен из рекомендаций NIST. В России данный алгоритм не рекомендован к использованию.
4. Реализация: Ошибки в реализации алгоритма (например, неправильное обновление состояния) могут свести на нет всю криптографическую стойкость. Пример — уязвимость Debian OpenSSL (2006-2008), когда из-за удаления двух строк кода из генератора случайных чисел, все ключи SSH и SSL/TLS, сгенерированные в системе, были предсказуемы.

Правовое регулирование в России

В Российской Федерации требования к криптографическим генераторам случайных чисел регулируются национальными стандартами. Основным документом является ГОСТ Р 34.10-2012 (Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи), который определяет требования к генерации случайных чисел для формирования ключей подписи. Также действует ГОСТ Р 34.11-2012 (Стрибог) — стандарт хеш-функции, которая может использоваться в составе КГСЧ. Для использования в государственных информационных системах и системах, обрабатывающих персональные данные, требуется применение сертифицированных ФСБ России криптографических средств, которые включают в себя аттестованные реализации КГСЧ на основе российских криптоалгоритмов (ГОСТ 28147-89, ГОСТ Р 34.10-2012, ГОСТ Р 34.11-2012). Использование несертифицированных КГСЧ (например, из зарубежных библиотек) в таких системах не допускается.

Источники

1. NIST Special Publication 800-90A Rev. 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators.
2. NIST Special Publication 800-22 Rev. 1a: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications.
3. Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
4. Schneier, B. (2015). Applied Cryptography: Protocols, Algorithms and Source Code in C. John Wiley & Sons.
5. ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.
6. ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хеширования.
7. Bernstein, D. J. (2008). ChaCha, a variant of Salsa20. Workshop Record of SASC 2008.