Генераторы случайных чисел: предсказуемость как уязвимость

Криптография держится на секретах, а секреты берутся из случайности. Ключ шифрования, nonce, IV, соль, одноразовый токен, коэффициент ECDSA — всё это должно быть непредсказуемым для противника. Если генератор предсказуем, стойкость алгоритма не имеет значения: противник не подбирает ключ, он его вычисляет. Эта тема разбирает, чем криптографический генератор отличается от обычного, как восстанавливается состояние популярных PRNG и какие реальные катастрофы произошли из-за одного неверного вызова.

Она опирается на тему 3 основного курса и на апокриф 2 (модели атак, перебор). Атаки на nonce в ECDSA подробно разбираются в апокрифе 10; здесь — общая механика и восстановление состояния генератора.

Где криптографии нужна случайность

Секреты и одноразовые значения

Случайность входит в систему в четырёх ролях. Первая — долговременные ключи: их энтропия определяет стойкость всей системы. Вторая — одноразовые значения: nonce в AEAD, IV в режимах, k в ECDSA, соль в хешировании паролей. Третья — идентификаторы и токены: сессионные ключи, токены сброса пароля, промокоды. Четвёртая — маскирование и blinding в реализациях, защищающих от сторонних каналов.

Требования к этим значениям разные. Ключ должен быть равномерно распределён и секретен. Nonce — уникален для данного ключа, и его уникальность важнее секретности: в GCM повтор nonce ломает аутентификацию, даже если nonce был «непредсказуем». Соль — уникальна и не обязана быть секретной. Токен сброса — непредсказуем и одноразов.

Свойства хорошего генератора

Криптографически стойкий генератор псевдослучайных чисел (CSPRNG) обязан выдерживать различение: никакой эффективный противник, зная алгоритм и все прошлые выходы, не может предсказать следующий бит с преимуществом лучше случайного. Это сильнее статистической «похожести на шум»: последовательность может пройти все тесты NIST SP 800-22 и всё равно быть предсказуемой, если её внутреннее состояние восстанавливается ⁵.

Отсюда два независимых требования: хорошая статистика и стойкость к восстановлению состояния. Обычные PRNG обеспечивают первое и не обеспечивают второе.

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

Линейный конгруэнтный генератор

LCG задаётся рекуррентностью x_{n+1} = (a·x_n + c) mod m; выход — обычно старшие биты x_n. Параметры подбираются так, чтобы период был большим, но линейность остаётся. По нескольким последовательным выходам параметры и состояние восстанавливаются алгебраически, но число нужных выходов зависит от того, что известно. Если модуль m известен и наблюдаются полные значения x_n, трёх выходов достаточно, чтобы найти a и c. Если известны только старшие биты, а не всё состояние, трёх значений уже недостаточно: младшие разряды потеряны, и их приходится перебирать. Если неизвестен и m, выхода три мало — модуль ищется как делитель величины t_{i+2}·t_i − t_{i+1}^2, где t_i = x_{i+1} − x_i, и на практике нужны четыре-пять выходов и перебор делителей. После восстановления параметров следующий выход вычисляется точно.

Пусть m = 2^31 − 1, a = 48271, c = 0, и известны x_1, x_2, x_3. Тогда x_2 ≡ a·x_1, x_3 ≡ a·x_2, откуда a ≡ x_3·x_2^{-1} mod m; для c ≠ 0 используется разность x_{n+2} − x_{n+1} = a·(x_{n+1} − x_n), из которой a находится по обратному элементу. В лабораторной работе восстанавливаются параметры по трём-четырём выходам и проверяется предсказание четвёртого.

Mersenne Twister

MT19937, стандартный генератор Python (random), PHP, Ruby и многих других сред, имеет состояние из 624 32-битных слов и период 2^19937 − 1 ¹. Он отлично проходит статистические тесты и совершенно не годится для криптографии: каждое выданное 32-битное число после обратимой «закалки» (tempering) соответствует одному слову состояния. Собрав 624 последовательных выхода, противник обращает закалку, получает все слова состояния и может вычислить любое будущее (и прошлое) значение.

На рисунке 1 показан весь путь от выходов к предсказанию: 624 выхода, обратная закалка, состояние, следующий выход.

Закалка устроена как цепочка y ^= y >> 11, y ^= (y << 7) & 0x9D2C5680, y ^= (y << 15) & 0xEFC60000, y ^= y >> 18. Каждое преобразование обратимо: для x ^ (x >> s) старшие s бит результата совпадают с x, по ним восстанавливаются следующие s бит и так далее; для x ^ ((x << s) & mask) аналогично восстанавливаются младшие биты. После 624 обращений состояние известно полностью.

На рисунке 2 показана последовательность атаки на приложение: сбор выходов, клонирование, запрос сброса и подстановка предсказанного токена.

В лабораторной работе это применяется к учебному приложению: промокоды и токены сброса пароля берутся из одного random.Random. Собрав 624 промокода, противник клонирует генератор и вычисляет токен сброса чужой учётной записи, не зная пароля и не имея доступа к «почте».

Почему статистика не спасает

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

CSPRNG и генераторы операционной системы

Конструкции

Практические CSPRNG делятся на три семейства. Первое — на блочных шифрах: CTR_DRBG шифрует счётчик ключом, который обновляется после каждого запроса. Второе — на хешах: Hash_DRBG и HMAC_DRBG смешивают энтропию и состояние через хеш, что даёт хорошее перемешивание и простую реализацию ². Третье — на поточных шифрах: ChaCha20-based DRBG, используемый в ядре Linux и в OpenBSD.

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

Linux: getrandom и /dev/urandom

В Linux источником энтропии служат прерывания, джиттер таймеров, драйверы и инструкции RDRAND/RDSEED. Ядро поддерживает пул энтропии и выдаёт из него значения через getrandom(2), /dev/urandom и /dev/random. Историческое различие «urandom не блокируется, random блокируется» устарело: с ядра 5.6 /dev/random блокируется только до инициализации пула, а после неё ведёт себя как /dev/urandom ⁷. Правильный способ получить криптографические байты — os.urandom или secrets в Python, getrandom в C.

В Python random — это MT19937 без криптографических гарантий ⁸; secrets.token_bytes, secrets.token_hex, secrets.randbelow используют os.urandom. Замена random на secrets в коде приложения — не косметика, а устранение целого класса атак.

Dual_EC_DRBG и доверие к параметрам

NIST SP 800-90A включал Dual_EC_DRBG — генератор на эллиптических кривых, который после разоблачений 2013 года был заподозрен в наличии «черного хода»: знание секретного соотношения между константами P и Q позволяло предсказывать выход по небольшому фрагменту ². Генератор был исключён из стандарта. Урок шире конкретной истории: если генератор содержит фиксированные константы неизвестного происхождения, доверие к нему основано на вере, а не на проверке. По этой же причине существуют сомнения в параметрах NIST P-256 (апокриф 10).

Реальные провалы

Debian OpenSSL 2008

В 2006 году мейнтейнер Debian убрал из OpenSSL код, который, по его мнению, был «неинициализированным чтением памяти», и вместе с ним — почти всю энтропию. В результате генератор ключей OpenSSL стал детерминированным: пространство возможных ключей сжалось до нескольких десятков тысяч вариантов. За два года было выпущено множество уязвимых сертификатов, SSH- и TLS-ключей; их пришлось перевыпускать, а список уязвимых ключей — рассылать по всему миру ⁶. Атака на такой ключ — не «взлом RSA», а перебор 15–17 бит.

Общие простые множители RSA

Heninger, Durumeric, Wustrow и Halderman в 2012 году собрали миллионы открытых RSA-ключей из Интернета и обнаружили, что у заметной доли ключей есть общий простой множитель с другим ключом: слабый генератор выдавал одинаковые простые числа разным устройствам. НОД двух модулей мгновенно раскрывает оба ключа ⁴. Это ещё один пример, когда алгоритм в порядке, а случайность — нет.

Повтор nonce в ECDSA

Sony PlayStation 3 (2010) и Android Bitcoin wallet (2013) использовали один и тот же k для разных сообщений. Детерминированный nonce, выводимый из сообщения и ключа по RFC 6979, снимает эту проблему ⁹. Из двух подписей (r, s1), (r, s2) восстанавливается k = (z1 − z2)/(s1 − s2) mod n, а затем закрытый ключ d = (s1·k − z1)/r mod n. Атака не требует перебора и работает за миллисекунды; подробный разбор — в апокрифе 10. Здесь важен общий вывод: одноразовое значение, использованное дважды, перестаёт быть одноразовым.

Клонирование состояния: fork, снимки, восстановление

Отдельный класс провалов не связан с качеством генератора: состояние просто оказывается скопированным. Классический случай — fork() в Unix: если процесс-родитель инициализировал CSPRNG и затем породил потомка, оба могут получить одну и ту же последовательность, потому что состояние памяти скопировано целиком. Именно так в 2008 году в Debian усугубилась история с OpenSSL: одинаковые ключи у процессов, стартовавших с одного снимка. Лечение — явная реинициализация или «перемешивание» состояния после fork (в OpenSSL для этого есть RAND_poll и резервирование в pid), а для приложений — не полагаться на наследование состояния вообще.

Та же ошибка встречается в виртуализации: снимок (snapshot) работающей машины сохраняет состояние генератора, и после отката к снимку два экземпляра выдают одинаковые nonce и ключи. Восстановление из резервной копии, повторный запуск контейнера из образа с зафиксированным seed и «тёплый» старт прошивки без переинициализации энтропии дают тот же результат. Практическое правило: любое событие, меняющее контекст исполнения — новый процесс, новая машина, откат, восстановление, — требует нового источника энтропии, а не продолжения старой последовательности.

Полезно разделять три уровня, которые часто называют одним словом «генератор». Источник энтропии — физический процесс (джиттер, прерывания, RDSEED); он даёт неопределённость, но не обязан быть быстрым и равномерным. DRBG — детерминированный алгоритм, который растягивает зерно в последовательность и обновляет состояние; его стойкость зависит от зерна. Генератор приложения — то, что вызывает разработчик (secrets, os.urandom, BCryptGenRandom); он должен обращаться к системному DRBG, а не к языковому random. Путаница уровней и порождает ошибки вида «мы же используем криптостойкий алгоритм» при том, что зерно взято из времени запуска.

Тесты и их ограничения

NIST SP 800-22

Набор статистических тестов проверяет частоты, серии, корреляции, энтропию и другие свойства последовательности ⁵. Тесты полезны для поиска грубых дефектов: смещённых битов, коротких периодов, линейных зависимостей. Они не доказывают криптографическую стойкость: MT19937 проходит большинство тестов, но полностью предсказуем; последовательность, полученная шифрованием счётчика, может не пройти отдельный тест из-за малой выборки и всё равно быть стойкой.

Правильная интерпретация: провал теста — сигнал проблемы, успех — не доказательство. Для криптографического генератора важнее формальная конструкция и анализ восстановления состояния, чем батарея тестов.

Практическая проверка

В лабораторной работе сравниваются LCG, MT19937 и secrets по трём критериям: статистика (частоты, серии), восстановление состояния по выходам и предсказание следующего значения. Ожидаемый результат: LCG и MT восстанавливаются, secrets — нет; статистические тесты при этом могут не различать их вовсе.

Итоги темы

Случайность — не «шум», а секретное состояние, из которого выводятся значения. LCG и MT19937 линейны и восстанавливаются по нескольким сотням выходов; их статистическая безупречность не имеет отношения к криптографии. CSPRNG строятся на криптографических функциях, обновляют состояние и используют энтропию ОС; в Python это secrets и os.urandom, а не random.

Реальные катастрофы — Debian 2008, общие простые множители RSA, повтор nonce в ECDSA — показывают, что слабый генератор ломает систему целиком, независимо от стойкости алгоритма. Статистические тесты ловят грубые дефекты, но не предсказуемость. Следующая тема — поточные шифры — покажет, что происходит, когда одноразовое значение всё-таки повторилось.

Литература

1. Matsumoto M., Nishimura T. Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator. — ACM Transactions on Modeling and Computer Simulation, 1998, Т. 8, № 1, С. 3–30. DOI: 10.1145/272991.272995
2. NIST. Recommendation for Random Number Generation Using Deterministic Random Bit Generators. — SP 800-90A Rev. 1, 2015. https://doi.org/10.6028/NIST.SP.800-90Ar1
3. Eastlake D., Schiller J., Crocker S. Randomness Requirements for Security. — RFC 4086, IETF, 2005. https://www.rfc-editor.org/rfc/rfc4086
4. Heninger N., Durumeric Z., Wustrow E., Halderman J. A. Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. — USENIX Security Symposium, 2012.
5. NIST. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. — SP 800-22 Rev. 1a, 2010. https://doi.org/10.6028/NIST.SP.800-22r1a
6. Yilek S., Rescorla E., Shacham H., Enright B., Savage S. When Private Keys are Public: Results from the 2008 Debian OpenSSL Vulnerability. — Internet Measurement Conference, 2009. DOI: 10.1145/1644893.1644896
7. Linux man-pages project. getrandom(2). — https://man7.org/linux/man-pages/man2/getrandom.2.html
8. Aumasson J.-P. Serious Cryptography. — 2-е изд. — No Starch Press, 2024.
9. Pornin T. Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). — RFC 6979, IETF, 2013. https://www.rfc-editor.org/rfc/rfc6979

Дополнительные материалы к апокрифу 3

Вопросы для самопроверки

1. Почему один и тот же генератор может быть хорош для симуляции и непригоден для ключей?
2. Сколько бит состояния у MT19937 и как это связано с числом выходов для клонирования?
3. Почему закалка не защищает от восстановления состояния?
4. Чем secrets отличается от random на уровне системных вызовов?
5. Что означает «непредсказуемость следующего бита» и как её проверить?
6. Почему nonce важнее держать уникальным, чем секретным?
7. Как связаны слабый ГСЧ и общие простые множители RSA?
8. Что произошло в Debian в 2008 году и почему это затронуло SSH и TLS?
9. Почему Dual_EC_DRBG вызвал подозрения и чем закончилась история?
10. Какие ограничения у статистических тестов NIST SP 800-22?
11. Что такое детерминированный nonce по RFC 6979 и какую проблему он решает?
12. Как проверить, что приложение не использует random для секретов?

Глоссарий темы

Шпаргалка

cp mt_clone_template.py mt_clone.py
python3 check_lcg.py -v
python3 check_mt.py -v
python3 attack_reset.py
python3 attack_reset.py secure
python3 recover_template.py && python3 check_recover.py

Что почитать и посмотреть

• Matsumoto, Nishimura. Mersenne Twister (1998) — первоисточник; понятно, почему генератор быстрый и линейный.
• NIST SP 800-90A Rev. 1 — конструкции DRBG и требования к ним.
• RFC 4086 — классический текст о том, откуда брать энтропию.
• Heninger et al. «Mining Your Ps and Qs» — исследование слабых ключей в Интернете.
• Yilek et al. «When Private Keys are Public» — разбор Debian OpenSSL.
• NIST SP 800-22 Rev. 1a — батарея статистических тестов и её ограничения.
• RFC 6979 — детерминированный ECDSA.
• Документация Python secrets — https://docs.python.org/3/library/secrets.html.

Углубление: почему random.seed(os.urandom(16)) не помогает

Кажется, что если засеять MT19937 криптографической случайностью, то выходы станут непредсказуемыми. Это верно только до первого наблюдения: как только противник получил 624 выхода, состояние восстановлено, и засев больше не имеет значения. Безопасность генератора определяется не только энтропией начального состояния, но и стойкостью к восстановлению по выходам. MT19937 линеен, поэтому восстановление тривиально; CSPRNG строится так, чтобы даже полное знание текущего состояния не позволяло предсказать прошлые выходы и чтобы восстановление состояния требовало криптографической атаки.

Отсюда практическое правило: генератор выбирается по назначению, а не по скорости. random — для игр, моделей и тестов; secrets — для всего, что попадает в криптографию.

Лабораторная работа 3. Предсказуемый хаос

• Раздел курса: апокриф 3 «Генераторы случайных чисел: предсказуемость как уязвимость»

Введение

В «Сейфе» есть промокоды и сброс пароля по ссылке. Разработчик взял random «потому что так короче», и это решение превращает защиту в формальность: Мэллори собирает 624 промокода, восстанавливает состояние Mersenne Twister и вычисляет токен сброса чужой учётной записи. Работа показывает всю цепочку — от линейного генератора до ECDSA — и заканчивается проверкой того, что замена random на secrets обрывает атаку.

Части: LCG, MT19937, захват учётной записи, повтор nonce в ECDSA, продвинутая — HMAC_DRBG по тестовому вектору и сравнение статистики с предсказуемостью.

Цель работы

Научиться восстанавливать состояние некриптографических генераторов и объяснять, почему статистические тесты не заменяют криптографический анализ.

После выполнения работы получится:

• восстанавливать параметры LCG по нескольким выходам и предсказывать следующее значение;
• обращать закалку MT19937 и клонировать состояние по 624 выходам;
• проводить атаку на токен сброса пароля через открытый интерфейс приложения;
• восстанавливать ключ ECDSA по двум подписям с общим nonce и подделывать подпись;
• объяснять, почему secrets закрывает атаку, а random — нет;
• оценивать энтропию уязвимого пространства ключей на примере Debian 2008.

Теоретический минимум

Разделы «Некриптографические генераторы и их вскрытие», «CSPRNG и генераторы операционной системы», «Реальные провалы» апокрифа 3. Формулы: LCG x_{n+1} = a·x_n + c mod m; ECDSA s = k^{-1}(z + r·d) mod n.

Перечень оснащения

Ubuntu 24.04, Python 3.10+, cryptography. Права root не нужны. Архив lr-env.

mkdir -p ~/lab-apocrypha-03 && cd ~/lab-apocrypha-03
unzip ~/lr-env.zip
cp mt_clone_template.py mt_clone.py
python3 check_mt.py -v

Порядок выполнения работы

Каждая часть заканчивается проверкой. Заготовки копируются в файлы без суффикса _template (mt_clone.py, lcg_attack.py, attack_reset.py, recover.py) — проверки ищут именно их. В журнал записывайте предсказание, число понадобившихся выходов и фактический результат.

Часть 1. Линейный конгруэнтный генератор

Задание

1. Реализуйте recover_ac(xs, m): по трём последовательным выходам найдите a и c для известного модуля. Для простого m используйте обратный элемент; для m = 2^32 учитывайте, что разность может быть чётной — берите тройку с нечётной разностью.
2. Реализуйте recover_modulus(xs) по разностям и НОД.
3. Реализуйте predict и проверьте предсказание на 10 следующих значениях.
4. Запустите python3 check_lcg.py -v на 200 случайных экземплярах.
5. Ответьте: почему для LCG достаточно трёх выходов, а для MT — 624?

Что должно получиться

Проходящие проверки, восстановленные параметры на одном примере (значения a, c, m) и оценка числа уравнений, необходимых для взлома.

Часть 2. Mersenne Twister

Задание

1. Реализуйте undo_xor_rshift, undo_xor_lshift_mask, untemper.
2. Реализуйте MTClone.getrandbits с учётом порядка слов CPython: первое слово — младшие 32 бита.
3. Реализуйте clone_from_outputs и проверьте: 5 предсказанных чисел должны совпасть с реальными.
4. Запустите python3 check_mt.py -v. Сколько выходов нужно, чтобы клон стал точным? Что произойдёт при 623?
5. Сравните: random.Random(0) и random.Random(1) — совпадают ли первые 624 выхода? Объясните, почему зерно не спасает, если выходы видны.

Что должно получиться

Клон, предсказывающий последовательность, вывод о 624 словах состояния и объяснение, почему засев из os.urandom не устраняет утечку.

Часть 3. Захват учётной записи

Задание

1. Реализуйте take_over(app), пользуясь только открытыми методами: собрать 624 промокода, построить клон, запросить сброс для alice, предсказать 128-битный токен и применить его.
2. Запустите python3 attack_reset.py: должны появиться предсказанный токен, совпадение с «почтой» и успешный вход под новым паролем.
3. Запустите python3 attack_reset.py secure: атака должна провалиться. Объясните, что изменилось в генераторе.
4. Посчитайте число обращений к приложению и время атаки. Оцените, заметна ли она по журналам.
5. Предложите минимальное исправление, не меняющее интерфейс приложения.

Что должно получиться

Успешная атака на уязвимую версию, провал на исправленной, числа обращений и времени, вывод о замене генератора.

Часть 4. Повтор nonce в ECDSA

Задание

1. Реализуйте восстановление k и d по двум подписям из nonce_reuse.json:

k = (z1 − z2) / (s1 − s2) mod n
d = (s1·k − z1) / r mod n

2. Проверьте, что d·G совпадает с открытым ключом жертвы.
3. Подпишите target_message восстановленным ключом, сохраните forged.sig (DER) и victim_pub.pem.
4. Запустите python3 check_recover.py: подпись должна проверяться открытым ключом жертвы и не совпадать с исходными.
5. Ответьте: почему одного совпадения r достаточно, чтобы заподозрить повтор nonce, и как RFC 6979 предотвращает проблему.

Что должно получиться

Восстановленный ключ, проверенная подпись чужого документа и вывод о том, что повтор nonce — не «теоретическая» ошибка, а мгновенный захват ключа.

Часть 5. Продвинутая: DRBG и пределы тестов

Задание

1. Реализуйте hmac_drbg_template.py по SP 800-90A и сверьте с тестовым вектором из HMAC_DRBG_SHA256.rsp.
2. Возьмите 10 000 выходов MT19937 и 10 000 байт из secrets. Посчитайте частоты битов, длину серий и автокорреляцию. Объясните, почему оба источника могут выглядеть одинаково.
3. Оцените пространство ключей Debian 2008, если энтропия упала до 15 бит: сколько ключей нужно перебрать и сколько времени это займёт при 10^6 проверок в секунду.
4. Сформулируйте, какие проверки в CI могли бы поймать использование random в криптографическом коде.

Что должно получиться

Совпадение с тестовым вектором, таблица статистик, оценка перебора Debian и список организационных мер (запрет random в криптокоде, ревью, статический анализ).

Журнал работы

Фиксируйте: сколько выходов понадобилось, совпало ли предсказание, сколько заняла атака, чем отличается поведение уязвимой и исправленной версии. Для каждого провала проверки — причина, а не только факт.

Контрольные вопросы

1. Чем криптографический генератор отличается от статистически хорошего?
2. Почему LCG восстанавливается по трём выходам?
3. Сколько слов состояния у MT19937 и почему именно столько?
4. Что делает закалка и почему она обратима?
5. Почему random.Random(seed) не годится для токенов, даже если seed случайный?
6. Как из двух подписей ECDSA с общим k восстанавливается ключ?
7. Что такое прямая секретность состояния DRBG и зачем она нужна?
8. Почему /dev/urandom считается достаточным после инициализации пула?
9. Что показал инцидент Debian 2008 и как он связан с энтропией?
10. Почему общие простые множители RSA ломают ключи без перебора?
11. Какие тесты NIST SP 800-22 не ловят предсказуемость?
12. Какое минимальное изменение кода закрывает атаку из части 3?