Безопасная последовательность¶

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

¶История и предпосылки

Понятие безопасной последовательности возникло в середине XX века в связи с развитием теории информации и криптографии. В 1949 году Клод Шеннон в работе «Теория связи в секретных системах» заложил основы теории секретности, показав, что для абсолютной стойкости шифра требуется ключ, длина которого не меньше длины сообщения. Это привело к поиску методов генерации последовательностей, которые были бы практически неотличимы от истинно случайных.

В 1960-х годах, с появлением электронных вычислительных машин, возникла необходимость в программных генераторах случайных чисел. Однако первые генераторы, такие как линейный конгруэнтный метод (ЛКМ), оказались криптографически слабыми: их состояние можно было восстановить по небольшой выборке выходных данных. Это привело к разработке специализированных криптостойких генераторов, таких как Blum Blum Shub (1986) и Yarrow (1999).

¶Криптостойкость и требования

Криптостойкость безопасной последовательности определяется тремя основными свойствами:

1. Непредсказуемость вперёд: зная первые n битов последовательности, невозможно вычислить n+1-й бит с вероятностью, отличной от 1/2.
2. Непредсказуемость назад: зная полную последовательность, невозможно восстановить внутреннее состояние генератора или предыдущие биты.
3. Статистическая неотличимость: последовательность должна быть неотличима от истинно случайной последовательности той же длины с помощью любого полиномиального теста.

Для выполнения этих требований генератор безопасной последовательности обычно использует:

• Криптографическую хеш-функцию (например, SHA-256) или блочный шифр (например, AES) в режиме счётчика.
• Энтропийный источник — физический или аппаратный источник случайности (например, шум диода, тепловой шум резистора, джиттер тактового генератора).
• Защиту от атак по времени и по питанию.

¶Классификация генераторов

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

• Аппаратные генераторы (True Random Number Generators, TRNG) — используют физические процессы, такие как радиоактивный распад, тепловой шум, квантовые эффекты. Примеры: Intel RDRAND, генераторы на основе квантовых точек.
• Программные генераторы (CSPRNG) — получают начальное состояние (seed) из аппаратного источника или из операционной системы, а затем генерируют последовательность детерминированным алгоритмом. Примеры: /dev/urandom (Linux), CryptGenRandom (Windows), ChaCha20 (OpenBSD).

¶По алгоритму

• На основе блочных шифров: AES-CTR, AES-GCM. Используют шифрование счётчика с последующим XOR с открытым текстом.
• На основе хеш-функций: HMAC_DRBG, Hash_DRBG (NIST SP 800-90A). Используют хеширование состояния с добавлением энтропии.
• На основе эллиптических кривых: Dual_EC_DRBG (рекомендован NIST, но скомпрометирован — содержал потенциальный backdoor).
• На основе поточных шифров: ChaCha20, Salsa20. Используются как генераторы псевдослучайных чисел в протоколах TLS 1.3 и WireGuard.

¶Применение

¶Криптография

• Генерация ключей: безопасные последовательности используются для создания симметричных ключей (AES-256), асимметричных ключей (RSA, ECDSA) и сессионных ключей в протоколах TLS, IPsec, SSH.
• Шифрование: в поточных шифрах (ChaCha20, RC4) безопасная последовательность комбинируется с открытым текстом через XOR.
• Аутентификация: в протоколах HMAC, GCM, CCM последовательность используется для генерации меток аутентичности.

¶Компьютерная безопасность

• Генерация nonce и IV: в протоколах TLS, IPsec, Wi-Fi (WPA2, WPA3) для предотвращения повторных атак.
• Создание токенов: для аутентификации (JWT, OAuth 2.0), сессионных идентификаторов, одноразовых паролей (TOTP, HOTP).
• Соль и PBKDF2: для хранения паролей (bcrypt, scrypt, Argon2).

¶Научные исследования

• Моделирование Монте-Карло: в физике, биологии, экономике для статистических расчётов.
• Квантовая криптография: для генерации ключей на основе квантовых состояний.

¶Примеры безопасных последовательностей

¶/dev/urandom (Linux)

В операционных системах семейства Unix/Linux безопасная последовательность предоставляется через файл устройства /dev/urandom. Он использует аппаратный энтропийный пул, смешанный с алгоритмом ChaCha20. В Linux 5.4 и новее /dev/urandom блокируется только при первом запуске, пока не будет накоплено достаточно энтропии.

¶CryptGenRandom (Windows)

В Windows функция CryptGenRandom (или BCryptGenRandom в новом API) использует аппаратный генератор (RDRAND) или системный энтропийный пул, смешанный с AES-256 в режиме счётчика.

¶ChaCha20 (OpenBSD, WireGuard)

Поточный шифр ChaCha20, разработанный Дэниелом Бернштейном, используется как CSPRNG в OpenBSD (с 2013 года) и в протоколе WireGuard. Он обеспечивает скорость до 3 Гбит/с на современных процессорах и считается криптостойким.

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

¶Dual_EC_DRBG

В 2007 году NIST опубликовал стандарт SP 800-90A, включающий генератор Dual_EC_DRBG на основе эллиптических кривых. В 2013 году, после разоблачений Эдварда Сноудена, выяснилось, что NSA (Агентство национальной безопасности США) могло внедрить в него backdoor — зная определённые параметры, можно было восстановить внутреннее состояние генератора и предсказать все последующие биты. В 2014 году NIST удалил Dual_EC_DRBG из стандарта.

¶Атаки по времени

Некоторые программные реализации CSPRNG могут быть уязвимы к атакам по времени, когда злоумышленник измеряет время выполнения операций и восстанавливает внутреннее состояние. Например, в 2012 году была продемонстрирована атака на генератор в библиотеке OpenSSL (CVE-2012-2333).

¶Атаки на энтропийный пул

Если злоумышленник может контролировать или истощить энтропийный пул (например, через атаку на виртуальную машину), он может заставить генератор выдавать предсказуемые последовательности. В 2018 году была обнаружена уязвимость в Linux-генераторе /dev/random, когда при низком уровне энтропии он блокировался, что могло привести к отказу в обслуживании.

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

• В 2018 году исследователи из Университета Мичигана показали, что генератор случайных чисел в процессорах AMD Ryzen (RDRAND) имел дефект, приводящий к появлению предсказуемых последовательностей в некоторых режимах работы.
• В 2020 году в протоколе TLS 1.3 была обнаружена уязвимость, связанная с использованием слабого генератора случайных чисел в некоторых реализациях, что позволяло восстанавливать сессионные ключи.
• В 2023 году компания Google объявила о переходе на квантово-устойчивые генераторы случайных чисел для своих сервисов, чтобы подготовиться к появлению квантовых компьютеров.

¶Источники

• Шеннон К. «Теория связи в секретных системах». 1949.
• NIST SP 800-90A Rev. 1. «Recommendation for Random Number Generation Using Deterministic Random Bit Generators». 2015.
• Menezes A., van Oorschot P., Vanstone S. «Handbook of Applied Cryptography». 1996.
• Bernstein D. «ChaCha, a variant of Salsa20». 2008.
• Сноуден Э. «Разоблачения о NSA и Dual_EC_DRBG». 2013.
• CVE-2012-2333 — уязвимость OpenSSL.
• CVE-2018-1000001 — уязвимость /dev/random в Linux.