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

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

Изложение идёт от источников энтропии к потребителям. Сначала — где физическая случайность берётся и как её оценивают. Затем — почему линейный конгруэнтный генератор и Mersenne Twister непригодны для криптографии, хотя дают статистически хорошие последовательности. После — конструкции CSPRNG и DRBG, стандарты NIST SP 800-90A/B и история Dual_EC_DRBG. Завершают тему генераторы операционных систем, API языков программирования и реальные провалы: Debian OpenSSL 2008, общие простые множители RSA, повтор nonce в Android.

Паспорт темы. Нужно знать: темы 0, 2. Освоите: оценивать min-entropy источника и объяснять conditioning; различать истинные и псевдослучайные генераторы; описывать prediction и backtracking resistance; различать nonce, IV, соль, seed и ключ; разбирать инциденты с генераторами. Проверяет: ЛР 3. Минимум: разделы 1–4. Углубление: раздел 5.

Зачем криптографии случайность

Где случайность нужна

Случайные значения используются почти в каждом механизме курса. Ключи симметричных шифров и MAC должны быть непредсказуемы. Одноразовые числа (nonce) и векторы инициализации (IV) должны быть уникальны, а для CBC — ещё и непредсказуемы. Соли в хранении паролей должны быть уникальны, чтобы одинаковые пароли давали разные хеши. Маскирование в схемах подписи и обмене ключами требует свежих значений. Даже дополнение в RSA-OAEP использует случайность.

У каждого потребителя свои требования. Для ключа нужна непредсказуемость и равномерность. Для nonce в ChaCha20 или AES-GCM достаточно уникальности в рамках ключа, но на практике уникальность достигается случайным выбором с запасом. Для соли достаточно уникальности, а непредсказуемость желательна, но не обязательна. Смешение этих требований — источник ошибок: «случайный» IV в CBC, выбранный как счётчик, предсказуем и позволяет атаку BEAST.

Nonce, IV, соль, seed и ключ

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

Ключ и seed обязаны быть непредсказуемыми: если противник угадает их, схема ломается целиком. Nonce и IV передаются открыто, и их секретность не предполагается — важно лишь, чтобы они не повторялись (или, для CBC, не были предсказуемы). Соль тоже открыта; её задача — исключить одинаковые хеши для одинаковых паролей и сделать предвычисление бесполезным.

Отсюда практическое правило: требование формулируется для конкретного объекта, а не «нужен хороший генератор». Для nonce в GCM достаточно счётчика, и это законно; для ключа счётчик недопустим. Для соли достаточно os.urandom(16), и её не нужно держать в секрете; для seed это было бы катастрофой.

Истинная и псевдослучайная последовательность

Истинный генератор (англ. true random number generator, TRNG) извлекает случайность из физического процесса: теплового шума, дробового шума, кольцевых осцилляторов, радиоактивного распада, джиттера. Его выход недетерминирован: повторить его невозможно. Псевдослучайный генератор (PRNG) — детерминированный алгоритм, который из короткого зерна (seed) выдаёт длинную последовательность, неотличимую от случайной для противника, не знающего зерно.

Криптографически стойкий генератор (CSPRNG) — PRNG, для которого невозможно предсказать следующий бит по предыдущим с вероятностью, заметно большей 1/2, без знания состояния. Это определение важно: статистические тесты проверяют распределение, но не непредсказуемость. Последовательность может проходить все тесты и при этом быть полностью предсказуемой — именно так ведут себя LCG и MT19937.

Модель противника

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

Требования к генераторам для разных задач сформулированы в RFC 4086 ³.

Prediction и backtracking resistance

Два свойства описывают, что происходит при компрометации состояния генератора, и они независимы.

Устойчивость к предсказанию (prediction resistance) означает, что после компрометации состояния будущие выходы остаются непредсказуемыми. Достигается только добавлением свежей энтропии в состояние после каждого запроса или периодически: если состояние полностью определено и новой энтропии нет, следующий выход предсказуем по определению. Поэтому prediction resistance — свойство не алгоритма, а архитектуры: генератор должен иметь доступ к источнику энтропии в момент работы.

Устойчивость к откату (backtracking resistance, её же называют forward secrecy генератора) означает, что по текущему состоянию нельзя восстановить прошлые выходы. Достигается однонаправленным обновлением состояния: новое состояние вычисляется как хеш или шифрование старого, и обратная операция невозможна. Даже если противник получил состояние сегодня, вчерашние ключи остаются недоступными.

Свойства дополняют друг друга и стоят по-разному. Backtracking resistance даётся бесплатно — достаточно обновлять состояние односторонней функцией. Prediction resistance требует доступа к источнику энтропии, а значит, может блокироваться и не всегда доступна: в контейнере без virtio-rng её просто нет. Стандарты (NIST SP 800-90A) описывают обе функции обновления — Update и Reseed — и явно указывают, какая из них что даёт.

Источники энтропии

Физические источники

Аппаратные генераторы используют шум электронных компонентов. Кольцевой осциллятор (ring oscillator) — нечётное число инверторов, замыкающих цепь; частота колеблется от шума, и сэмплирование даёт случайные биты. Лавинный диод даёт шумовой ток. Процессоры Intel и AMD предоставляют инструкции RDRAND и RDSEED: первая выдаёт выход внутреннего DRBG, вторая — «сырую» энтропию. RDRAND не следует считать безусловно доверенным: его выход проходит через алгоритм, и в теории производитель может знать состояние. Поэтому ОС смешивают несколько источников.

Виртуальные машины и контейнеры усложняют картину. Гость видит virtio-rng, но если хост не передаёт энтропию, генератор гостя может оказаться в плохом состоянии. Снимок виртуальной машины (snapshot) воспроизводит состояние генератора при откате, и два клона могут выдать одинаковые «случайные» значения. Это реальная причина повторного использования ключей и nonce.

Отдельного упоминания заслуживают источники, построенные на временных дрожаниях (jitter). Задержка распространения сигнала в цепи зависит от температуры, питающего напряжения и технологического разброса; если измерить её с высокой точностью и взять младшие биты результата, получится шум. Такой подход применяется в jitterentropy — библиотеке, которую использует ядро Linux, — и в реализациях для встраиваемых систем. Достоинство в том, что источник работает там, где нет специализированного оборудования; недостаток — сильная зависимость от условий эксплуатации и риск коррелированных выборок при слишком частом опросе. Оценивать такой источник приходится консервативно, с запасом по худшему режиму.

Второй практический момент — пропускная способность. Физический источник даёт порядка сотен килобит в секунду, тогда как приложению нужны килобайты ключевого материала, а серверу — десятки килобайт. Поэтому архитектура всегда двухступенчатая: медленный, но качественный источник наполняет состояние, а быстрый детерминированный генератор растягивает его до нужного объёма. Смешивание устраивают так, чтобы выход нельзя было предсказать, зная только одну из частей.

Третий момент — доверие к поставщику. Выход RDRAND нельзя ни проверить извне, ни воспроизвести: он приходит из внутреннего генератора процессора готовым. Если допустить, что производитель знает состояние этого генератора, конструкция, опирающаяся только на инструкцию, теряет стойкость. Поэтому зрелые системы трактуют аппаратный источник как один из многих, добавляют собственную энтропию при каждой загрузке и не позволяют единственному источнику определять состояние пула.

Оценка энтропии

Энтропию источника оценивают в битах на сэмпл. Для этого собирают статистику: распределение значений, корреляции, сжатие, тесты NIST SP 800-90B ². Оценка — не измерение «истинной» случайности, а консервативная нижняя граница: предполагается худший случай в рамках модели источника.

Практическая сложность: оценка энтропии легко завышается. Шум, который выглядит случайным на коротком интервале, может иметь медленную корреляцию; источник, зависимый от температуры, может «залипать». Поэтому зрелые системы используют несколько источников, консервативную оценку и периодическое перемешивание.

Стандарт SP 800-90B предлагает два подхода к оценке ². Первый — оценка по модели источника: исследователь описывает, как именно устроен шумовой процесс, и выводит нижнюю границу аналитически. Второй — набор статистических оценщиков (min-entropy estimators), которые применяются к записи выхода и дают консервативную оценку «со стороны данных»: наиболее осторожную из всех оценок, а не среднюю. Отдельно проверяют устойчивость к перезапуску (restart test): источник не должен при повторной инициализации выдавать ту же последовательность — иначе снимок состояния или сброс устройства обнуляет всю энтропию.

Практическая сложность в том, что оценка легко завышается. Шум, который выглядит случайным на коротком интервале, может иметь медленную корреляцию; источник, зависящий от температуры, способен «залипать» в одном режиме; АЦП с недостаточным разрешением отдаёт младшие биты, в которых больше структуры, чем кажется. Поэтому зрелые системы используют несколько независимых источников, консервативную оценку и периодическое перемешивание. Ядро Linux, например, ведёт учёт «запаса» энтропии и до его набора блокирует выдачу через getrandom(2) без флага GRND_NONBLOCK; после инициализации пула блокировка снимается, потому что дальше работает уже детерминированный генератор с защищённым состоянием.

Полезно запомнить простое правило: оценка энтропии — утверждение о противнике, а не о природе. Она отвечает на вопрос «сколько бит неопределённости останется у противника, знающего устройство источника и его окружение», и любой оптимизм в этом ответе переносится на все ключи, которые из источника выработаны.

Кондиционирование

Сырой выход источника редко используют напрямую: он может быть смещён (единиц больше, чем нулей) или коррелирован. Кондиционирование (conditioning) — преобразование, повышающее качество: хеширование (SHA-256 от пула), извлечение энтропии (HKDF-extract), простые методы вроде устранения смещения фон Неймана. Важно, чтобы кондиционирование не создавало иллюзию энтропии: если на входе её мало, хеш не добавит.

Формально извлечение энтропии (extractor) гарантирует близость выхода к равномерному при условии, что вход имеет достаточно min-энтропии. Это ещё одна причина, по которой оценка источника критична: без неё нельзя утверждать, что выход пригоден для ключей.

Аппаратная и программная части этой архитектуры показаны на схеме ниже: несколько независимых источников наполняют пул, кондиционирование приводит выход к равномерному виду, детерминированный генератор растягивает полученный запас до нужного объёма, а прикладной код получает готовые ключи, nonce и соли через системный интерфейс.

Схема подчёркивает и границу ответственности прикладного программиста: всё, что находится левее системного вызова, — забота ядра и оборудования, а выбор между random и secrets в коде приложения определяет, какая ветвь схемы будет использована. Ошибки возникают именно на этой границе, а не внутри проверенных десятилетиями генераторов.

Псевдослучайные генераторы

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

Линейный конгруэнтный генератор (LCG) задаётся рекурсией

x_{n+1} = (a·x_n + c) mod m

При удачных параметрах он имеет большой период и проходит простые статистические тесты. Но его состояние — одно число, и по нескольким выходам параметры восстанавливаются алгебраически. Если модуль известен, из трёх последовательных значений:

x₂ − x₁ ≡ a(x₁ − x₀) (mod m)
a ≡ (x₂ − x₁)·(x₁ − x₀)⁻¹ (mod m)
c ≡ x₁ − a·x₀ (mod m)

Если модуль неизвестен, используют разности t_i = x_{i+1} − x_i: величина t_{i+2}·t_i − t_{i+1}² кратна m, и модуль находится как НОД нескольких таких величин. В лабораторной работе это выполняется на данных с модулем около 2^48.

Мораль: LCG годится для имитационного моделирования, но не для криптографии. Его используют в старых библиотеках (rand() в C), и это регулярно приводит к уязвимостям.

Разберём восстановление на числовом примере с параметрами, которые десятилетиями стояли в библиотеке rand(): m = 2^31 = 2147483648, a = 1103515245, c = 12345, начальное значение x₀ = 42. Первые выходы:

x₀ =         42
x₁ = 1250496027
x₂ = 1116302264
x₃ = 1000676753
x₄ = 1668674806

Проверим формулу при известном модуле. Разность x₁ − x₀ = 1250495985 нечётна, поэтому обратный элемент по модулю 2^31 существует и равен 1379943185. Тогда a ≡ (x₂ − x₁)·1379943185 ≡ 1103515245, а c ≡ x₁ − a·x₀ ≡ 12345 — исходные параметры восстановлены по трём выходам. Никакого перебора: два умножения и одно обращение модульной инверсии.

Теперь тот же пример при неизвестном модуле. Разности t_i = x_{i+1} − x_i равны 1250495985, −134193763, −115625511, 667998053, −760579071. Величины u_0 = t_2·t_0 − t_1² = −162597203297173504, u_1 = −103010431202754560, u_2 = −358279055071510528 кратны искомому модулю, и их НОД равен 2147483648 — ровно 2^31. Модуль найден по шести выходам, после чего параметры восстанавливаются как выше.

Схема на рисунке ниже обобщает оба случая: сверху — сама рекурсия, снизу — две ветви восстановления в зависимости от того, известен ли модуль.

Практический вывод для аудита: если в системе встречается последовательность вида x_{n+1} = (a·x_n + c) mod m с модулем-степенью двойки, она вскрывается моментально. Так устроены не только rand() и java.util.Random, но и множество самодельных «генераторов паролей» и токенов, которые пишут, чтобы избежать зависимости от криптографической библиотеки. Именно такие реализации попадают в отчёты о предсказуемых токенах сброса пароля.

Mersenne Twister

Mersenne Twister MT19937 — генератор с периодом 2^19937 − 1, состоянием из 624 32-битных слов и хорошими статистическими свойствами ⁷. Он широко применяется в моделировании и в стандартной библиотеке Python (random). Для криптографии он непригоден по двум причинам. Во-первых, состояние восстанавливается по 624 последовательным 32-битным выходам: каждое выходное слово связано с состоянием обратимым преобразованием (tempering), и обратное преобразование даёт состояние полностью. Во-вторых, зная состояние, можно предсказать весь дальнейший выход.

В лабораторной работе это демонстрируется на учебном приложении: 624 промокода, выданных генератором, достаточно, чтобы клонировать состояние и предсказать токен сброса пароля. Атака не требует перебора и занимает секунды.

Внутреннее устройство генератора и атака на него показаны на схеме ниже. Состояние — регистр из 624 слов; выход каждого слова проходит через обратимую темперацию; атака снимает темперацию с 624 подряд идущих выходов и получает полное состояние.

Обратное преобразование пишется в несколько строк. Каждый шаг темперации — операция вида y ^= (y >> s) или y ^= (y << s) & mask, и она обращается итеративно, потому что сдвиг уже восстановленных битов может уточнить ещё не восстановленные:

def undo_right(y, shift):
    x = y
    for _ in range(32 // shift + 1):
        x = y ^ (x >> shift)
    return x


def undo_left(y, shift, mask):
    x = y
    for _ in range(32 // shift + 1):
        x = y ^ ((x << shift) & mask)
    return x


def untemper(y):
    y = undo_right(y, 18)
    y = undo_left(y, 15, 0xEFC60000)
    y = undo_left(y, 7, 0x9D2C5680)
    y = undo_right(y, 11)
    return y

Проверка на стандартном модуле: после 624 вызовов getrandbits(32) восстановленное состояние совпадает с внутренним, и клонированный генератор выдаёт те же следующие значения. В лабораторной работе эта же процедура применяется к последовательности промокодов учебного приложения, чтобы предсказать токен сброса пароля.

Существенно, что атака не требует ни перебора, ни знания зерна, ни доступа к процессу. Достаточно наблюдать выход — например, получать токены сброса пароля для собственной учётной записи и видеть, как они меняются. Ровно поэтому random в Python не является генератором секретов, хотя и не имеет видимых статистических дефектов.

Криптографически стойкие генераторы

CSPRNG строят из криптографических примитивов: хеш-функций, HMAC, блочных шифров, поточных шифров. Общая схема: секретное состояние, функция обновления, функция выхода. Требования: выход неотличим от случайного, состояние нельзя восстановить по выходу, компрометация состояния не должна раскрывать прошлые выходы (backtracking resistance).

Сравнение генераторов, которые встречаются в курсе, по трём практическим признакам.

Столбец «период» у криптографических генераторов намеренно не заполнен числом: у них нет наблюдаемого цикла, а стойкость определяется не длиной периода, а неотличимостью выхода от случайного.

NIST SP 800-90A определяет семейство DRBG (deterministic random bit generator): Hash_DRBG, HMAC_DRBG, CTR_DRBG ¹. Каждый имеет операции Instantiate, Reseed, Generate и счётчик обращений. HMAC_DRBG, разобранный в лабораторной работе, устроен через два значения K и V: обновление перемешивает их с входными данными, генерация выдаёт HMAC(K, V) и обновляет состояние. Тестовые векторы CAVP позволяют проверить реализацию побитово.

Dual_EC_DRBG

Dual_EC_DRBG — генератор на эллиптических кривых, включённый в раннюю версию SP 800-90A. В 2013 году после публикаций Эдварда Сноудена выяснилось, что в спецификации могли быть заложены константы, позволяющие автору предсказывать выход. NIST отозвал рекомендацию, а в последующих редакциях генератор исключён. История показательна: стандартизация не гарантирует отсутствие закладок, а «слишком удобные» константы заслуживают scrutiny.

Урок для инженера: если алгоритм содержит фиксированные константы неизвестного происхождения, это риск. Современные стандарты требуют объяснять происхождение параметров (nothing-up-my-sleeve numbers), а независимые исследователи проверяют их генерацию.

Генераторы операционных систем

Linux

В Linux исторически было два устройства: /dev/random, который блокировался при исчерпании «пула энтропии», и /dev/urandom, который не блокировался. На практике /dev/random часто оказывался не лучше, а хуже: он мог блокироваться на минуты и не давал гарантий качества. В ядре 5.6 семантика изменена: /dev/random блокируется только до инициализации пула, после чего ведёт себя как /dev/urandom; в 5.18 переработан учёт энтропии ⁸.

Рекомендуемый интерфейс — системный вызов getrandom(2), который блокируется до инициализации и затем возвращает случайные байты. В Python os.urandom использует его; модуль secrets строит на его основе удобные функции (token_bytes, token_hex, token_urlsafe). Модуль random — это MT19937, и он категорически не подходит для ключей.

Windows и другие системы

В Windows криптографически стойкий генератор доступен через BCryptGenRandom; старый RtlGenRandom (он же SystemFunction036) считается устаревшим. В macOS и iOS — SecRandomCopyBytes, в BSD — arc4random_buf. Общее правило: использовать системный CSPRNG, а не язык-специфичный random.

API и типичные ошибки

Ошибки в использовании API однотипны. Первая — взять random вместо secrets или os.urandom. Вторая — засеять генератор предсказуемым значением: временем, PID, идентификатором пользователя. Третья — использовать «случайное» число модульно с bias: randrange(256) корректен, а random() % 256 может дать смещение. Четвёртая — кэшировать сгенерированный ключ и переиспользовать его. Пятая — считать, что RDRAND всегда доступен и всегда качественен.

Провалы и их последствия

Debian OpenSSL 2008

В 2006–2008 годах в Debian и производных использовалась пропатченная версия OpenSSL, из которой удалили сбор энтропии (причина — жалобы анализаторов на «неинициализированные» чтения). Генератор засевался только PID, временем и UID, что давало около 15 бит энтропии и порядка 32 тысяч возможных ключей. Уязвимыми оказались ключи SSH, TLS, OpenVPN, DNSSEC и сеансовые ключи, сгенерированные на этих системах ⁴.

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

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

В 2012 году исследователи просканировали открытые ключи RSA в Интернете и обнаружили, что у части ключей совпадают простые множители ⁵. Причина — слабая случайность при генерации: устройства с плохим генератором иногда выбирали одни и те же простые числа. Доля затронутых хостов составила около 0,2 % для TLS и 5,6 % для SSH. Атака тривиальна: НОД двух модулей даёт общий множитель, после чего ключ факторизуется.

Этот случай важен тем, что дефект не виден в отдельном ключе: каждый ключ выглядит нормально. Уязвимость проявляется только в совокупности, поэтому обнаруживается массовым сканированием, а не аудитом одного сервера.

Повтор nonce в Android

В 2013 году в Android обнаружили ошибку в SecureRandom: при определённых условиях генератор возвращал повторяющиеся значения. В ECDSA повтор nonce означает, что из двух подписей восстанавливается закрытый ключ. Пострадали биткоин-кошельки: злоумышленники подписывали транзакции от имени владельцев ⁶. Подробно формула восстановления разбирается в теме 13.

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

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

NIST SP 800-22 описывает набор статистических тестов: частотный, блочный, серий, ранг матрицы, дискретное преобразование Фурье и другие ⁹. Тесты полезны для обнаружения грубых дефектов, но не доказывают криптографическую стойкость: последовательность MT19937 проходит большинство тестов, оставаясь предсказуемой. Обратное тоже верно: хороший CSPRNG может случайно провалить тест с малой вероятностью, и это не означает дефекта.

Поэтому тесты применяют как дополнительный контроль, а не как критерий пригодности. Критерий — конструкция и анализ, а не «прошло 15 тестов из 15».

Итоги темы

Случайность в криптографии — не удобство, а предпосылка стойкости. Истинные генераторы извлекают энтропию из физических процессов, но требуют оценки и кондиционирования; псевдослучайные генераторы детерминированы и пригодны для криптографии только при выполнении строгих требований непредсказуемости. LCG и MT19937 этим требованиям не удовлетворяют, хотя статистически выглядят хорошо.

Стойкие конструкции — Hash_DRBG, HMAC_DRBG, CTR_DRBG и системные CSPRNG — защищают состояние и проверяются по тестовым векторам. Их использование обязательно для ключей, nonce и солей; API random для этого непригоден. История Debian, общих простых множителей и Android показывает, что ошибка в генераторе обходится дороже ошибки в алгоритме: она затрагивает все ключи сразу и часто остаётся незаметной.

Обзор современных требований к генераторам и типичных ошибок приведён также в ¹⁰. Следующая тема переходит к математическим основам асимметричной криптографии. Там случайность тоже нужна — для генерации простых чисел и показателей, — и требования к ней те же.

Литература

1. 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
2. NIST. Recommendation for the Entropy Sources Used for Random Bit Generation. — SP 800-90B, 2018. https://doi.org/10.6028/NIST.SP.800-90B
3. Eastlake D., Schiller J., Crocker S. Randomness Requirements for Security. — RFC 4086, IETF, 2005. https://www.rfc-editor.org/rfc/rfc4086
4. Debian. DSA-1571-1: openssl — predictable random number generator. — Debian Security Advisory, 2008. https://www.debian.org/security/2008/dsa-1571
5. Heninger N., Durumeric Z., Wustrow E., Halderman J. A. Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. — USENIX Security, 2012.
6. Krebs B. Android Bug Batters Bitcoin Wallets. — Krebs on Security, 2013. https://krebsonsecurity.com/2013/08/android-bug-batters-bitcoin-wallets/
7. 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.
8. Linux kernel documentation. Random Number Generation. — Documentation/admin-guide/random.rst. https://docs.kernel.org/admin-guide/random.html
9. 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
10. Aumasson J.-P. Serious Cryptography: A Practical Introduction to Modern Encryption. 2nd ed. — No Starch Press, 2024.

Дополнительные материалы

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

1. Почему криптографическая стойкость схемы зависит от качества случайных чисел?
2. Чем истинный генератор отличается от псевдослучайного?
3. Что означает непредсказуемость следующего бита и почему статистические тесты её не проверяют?
4. Какие физические процессы используют аппаратные генераторы?
5. Зачем нужно кондиционирование энтропии и что оно не может исправить?
6. Почему LCG восстанавливается по трём выходам?
7. Как найти неизвестный модуль LCG по последовательности выходов?
8. Почему MT19937 клонируется по 624 выходам?
9. Что такое tempering и как выполняется обратное преобразование?
10. Как устроен HMAC_DRBG: какие значения хранит состояние и как они обновляются?
11. Что произошло с Dual_EC_DRBG и какой урок следует для выбора стандартов?
12. Чем отличаются /dev/random, /dev/urandom и getrandom(2) в современном Linux?
13. Почему random в Python непригоден для ключей, а secrets пригоден?
14. В чём была причина уязвимости Debian OpenSSL 2008?
15. Как слабый генератор приводит к появлению общих простых множителей у RSA-ключей?
16. Почему снимок виртуальной машины может привести к повтору случайных значений?

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

Шпаргалка по инструментам

# генерация данных и проверки
python3 gen_data.py 0
python3 check_lcg.py -v
python3 check_mt.py -v
python3 check_drbg.py

# учебное приложение и атака
python3 reset_app.py
python3 attack_reset.py
python3 attack_reset.py secure

# случайные байты в Python
python3 -c "import secrets; print(secrets.token_hex(16))"
python3 -c "import os; print(os.urandom(16).hex())"
python3 -c "import random; print(random.getrandbits(128))"   # НЕ для секретов

# энтропия Linux
cat /proc/sys/kernel/random/entropy_avail

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

1. NIST SP 800-90A Rev. 1 — нормативное описание Hash_DRBG, HMAC_DRBG и CTR_DRBG; именно по нему выполняется часть 4.
2. NIST SP 800-90B — методы оценки энтропии источников; полезно, если интересно, откуда берётся «достаточно случайно».
3. RFC 4086 «Randomness Requirements for Security» — инженерное введение в требования к случайности; хорошо читается до лабораторной.
4. Документация Linux random.rst — устройство пула энтропии и семантика /dev/random и getrandom.
5. Debian DSA-1571-1 — первоисточник инцидента 2008 года; короткий и точный документ.
6. Heninger et al., «Mining Your Ps and Qs» (USENIX Security 2012) — методика массового поиска слабых ключей; пример того, как дефект генератора проявляется статистически.
7. Krebs on Security, «Android Bug Batters Bitcoin Wallets» — популярное, но точное описание инцидента с повторным nonce.
8. Документация Python secrets — краткое руководство, какие функции использовать вместо random.
9. Блог Cloudflare о случайности в TLS — как генератор используется в реальном протоколе и что проверяют браузеры.
10. Доклады Real World Crypto о генераторах — обзоры инцидентов и современных требований; записи доступны на сайте конференции.

Углубление

Как работает пул энтропии Linux

Ядро собирает шум из прерываний, таймеров, дисковых операций и других событий, перемешивает его в пул и использует для инициализации CSPRNG. Исторически /dev/random отслеживал «количество энтропии» и блокировался, когда оно падало до нуля; это создавало иллюзию большей безопасности, но на практике приводило к блокировкам и не давало лучшего качества. В современном ядре учёт переработан: после инициализации генератор выдаёт байты без блокировки, а getrandom(2) гарантирует, что инициализация произошла. Для инженера практический вывод прост: используйте getrandom/os.urandom, не открывайте /dev/random вручную и не пытайтесь «подождать энтропию».

Почему Dual_EC_DRBG стал скандалом

Dual_EC_DRBG использовал эллиптическую кривую с фиксированными константами. Если автор констант знает секретное соотношение между ними, он может по нескольким байтам выхода восстановить состояние и предсказать всё остальное. Формально генератор проходил тесты и был стандартизован; фактически он мог содержать закладку. После публикаций 2013 года NIST отозвал рекомендацию, а крупные компании убрали поддержку. Урок шире одного алгоритма: стандартизация — социальный процесс, и доверие к константам должно подкрепляться объяснением их происхождения.

Случайность и воспроизводимость

Разработчики иногда засевают генератор фиксированным значением для воспроизводимости тестов. Это допустимо только в тестах и только для несекретных данных. В производственном коде такое зерно превращает все «случайные» значения в детерминированные, а если оно попадает в репозиторий — становится известным. Отдельная ловушка — CI/CD: контейнеры, клонированные из одного образа, могут иметь одинаковое состояние генератора до первой инициализации. Проверка: генерировать ключи после инициализации системы и использовать getrandom, который блокируется до готовности пула.

Лабораторная работа 3. Предсказуемые и непредсказуемые генераторы

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

Введение

Работа показывает разницу между статистической «похожестью на случайность» и криптографической непредсказуемостью. Сначала восстанавливаются параметры линейного конгруэнтного генератора по нескольким выходам — задача, которая решается алгеброй, а не перебором. Затем по 624 выходам клонируется Mersenne Twister и предсказывается токен сброса пароля в учебном приложении. После этого реализуется HMAC_DRBG и проверяется по официальным тестовым векторам. Завершает работу сравнение статистических тестов на хорошем и плохом генераторе.

Базовая часть — части 1–4; часть 5 выполняется по желанию, но именно она показывает ограниченность статистических критериев.

Цель работы

Продемонстрировать предсказуемость нестойких генераторов и проверить реализацию криптографически стойкого DRBG по стандартным векторам.

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

• восстановить параметры LCG по нескольким последовательным выходам;
• клонировать состояние MT19937 по 624 выходам и предсказать будущие значения;
• провести атаку на учебный токен сброса пароля;
• реализовать HMAC_DRBG по SP 800-90A и сверить с векторами CAVP;
• объяснить, почему статистические тесты не доказывают стойкость генератора.

Уровни работы

• Минимум (обязательно): части 1–4. Выполняется без внешней сети, только с пакетами из перечня оснащения.
• Практический уровень: нет.
• Углубление (по желанию): 5 (статистические тесты).

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

Нужны разделы «Зачем криптографии случайность», «Псевдослучайные генераторы» и «Генераторы операционных систем» темы 3.

Команды:

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

• Linux, Python 3.10+; внешние пакеты не нужны.
• Архив окружения: lr-env.zip.
• Права root не нужны.

Ограничения ресурсов

Восстановление MT требует 624 выхода (около 2,5 КБ); статистические тесты — до 10^6 бит, память — единицы мегабайт. Время выполнения не нормируется: проверяются свойства и совпадение с тестовыми векторами, а не абсолютные секунды. Если на конкретной машине шаг занимает заметно больше ожидаемого, это фиксируется в журнале вместе с параметрами оборудования.

Безопасная область эксперимента

Работа выполняется в отдельном каталоге ~/crypto-lab-03; всё необходимое лежит в архиве окружения. Учебные серверы и оракулы слушают только 127.0.0.1. Внешняя сеть не используется.

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

mkdir -p ~/lab03 && cd ~/lab03
unzip ~/Downloads/lr-env.zip -d .
cd lr-env
python3 gen_data.py 0
python3 check_lcg.py -v

Файлы заготовок копируются в рабочие имена без суффикса _template: например, lcg_attack_template.py → lcg_attack.py. Проверки сначала ищут файл без суффикса и только потом заготовку. Это позволяет держать решение рядом, не меняя исходную заготовку.

Часть 1. Восстановление параметров LCG

Задание

1. Изучите данные: lcg_known_m.txt содержит модуль и пять выходов, lcg_unknown_m.txt — только выходы.

cat lcg_known_m.txt
cat lcg_unknown_m.txt

2. Реализуйте recover_ac(xs, m): по трём выходам найти a и c. Обратите внимание на случай m = 2^32, где разность может быть чётной и необратимой; в проверке такие тройки пропускаются.

3. Реализуйте predict(xs, m, a, c, count) и проверьте предсказание на известных значениях.

4. Реализуйте recover_modulus(xs) для неизвестного модуля: используйте разности и НОД величин t_{i+2}·t_i − t_{i+1}².

5. Восстановите параметры обоих файлов и предскажите следующие пять значений.

python3 check_lcg.py -v
python3 - <<'PY'
import lcg_attack as l
xs = l.read_values("lcg_known_m.txt")
print("a, c:", l.recover_ac(xs, 2**31 - 1))
PY

6. Сравните восстановленные значения с ответами генератора.

python3 gen_data.py 0 --answers

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

Работающие функции; верные a, c и следующие значения для обоих файлов; совпадение с ответами; объяснение, почему для восстановления достаточно трёх выходов при известном модуле.

Часть 2. Клонирование Mersenne Twister

Задание

1. Реализуйте обратные преобразования undo_xor_rshift и undo_xor_lshift_mask, затем untemper.

2. Реализуйте класс MTClone: инициализация состоянием из 624 слов, twist, getrandbits32, getrandbits(k).

3. Реализуйте clone_from_outputs(outputs): по 624 последовательным 32-битным выходам восстановить состояние.

4. Проверьте клон: сгенерируйте 1000 значений исходным random.Random и клоном, сравните.

python3 check_mt.py -v

5. Объясните, почему для клонирования нужно ровно 624 выхода, а не 625, и что произойдёт при нехватке одного слова.

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

Работающие untemper и MTClone; совпадение 1000 значений; прохождение check_mt.py; объяснение связи размера состояния и числа выходов.

Часть 3. Атака на сброс пароля

Задание

1. Изучите учебное приложение reset_app.py. Мэллори — зарегистрированный пользователь; он видит промокоды и может инициировать сброс пароля, но не видит токен.

2. Реализуйте take_over(app, victim, new_password): собрать 624 промокода, клонировать генератор, запросить сброс, предсказать токен, установить новый пароль.

3. Проведите атаку на уязвимую и на исправленную версию.

python3 attack_reset.py
python3 attack_reset.py secure

4. Запустите проверку.

python3 check_mt.py -v

5. Объясните, почему исправленная версия (SecureResetApp) не поддаётся атаке, хотя использует тот же алгоритм MT: что именно изменилось.

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

Успешный захват учётной записи в уязвимой версии и отказ в исправленной; прохождение проверки; вывод о том, что уязвимость не в MT как таковом, а в его использовании для секретов.

Часть 4. HMAC_DRBG по стандарту

Задание

1. Скопируйте hmac_drbg_template.py в hmac_drbg.py и реализуйте операции Instantiate, Update, Reseed, Generate по SP 800-90A, раздел 10.1.2.

2. Проверьте реализацию по векторам CAVP.

python3 check_drbg.py

Файл HMAC_DRBG_SHA256.rsp содержит 96 векторов: 48 без повторного засева и 48 с ним. Для режима pr_false перед генерацией выполняется Reseed, а выход первого Generate отбрасывается.

3. Измерьте, сколько байт выдаёт генератор за секунду, и сравните с os.urandom.

python3 - <<'PY'
import os, time
import hmac_drbg as d
r = d.HmacDrbg(b"e" * 32, b"n" * 16)
t0 = time.perf_counter(); n = 0
while time.perf_counter() - t0 < 1:
    r.generate(1024); n += 1024
print("HMAC_DRBG, байт/с:", n)
t0 = time.perf_counter(); n = 0
while time.perf_counter() - t0 < 1:
    os.urandom(1024); n += 1024
print("os.urandom, байт/с:", n)
PY

4. Объясните, почему в реальной системе не используют самодельный DRBG, даже если он проходит векторы.

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

Реализация, проходящая все 96 векторов; измеренная скорость; вывод о том, что векторный тест проверяет соответствие спецификации, но не отсутствие побочных каналов и ошибок эксплуатации.

Часть 5. Статистические тесты (по желанию)

Задание

1. Реализуйте частотный тест (доля единиц) и тест серий (длины серий одинаковых бит) для последовательности байт.

2. Сравните три источника: os.urandom, LCG с хорошими параметрами, MT19937.

3. Для каждого источника постройте распределение статистики на 100 испытаниях и сравните с теоретическим.

4. Сделайте вывод: какой из источников проходит тесты и какой при этом предсказуем.

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

Таблица «источник — доля единиц — средняя длина серии — проходит/не проходит»; вывод о том, что MT19937 проходит большинство тестов, но клонируется по 624 выходам.

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

Для каждой части фиксируйте предсказание до запуска: сколько промокодов потребуется, совпадёт ли клон с оригиналом на 1000 значениях, пройдут ли все 96 векторов с первого раза. Расхождения объясняйте: например, если клон разошёлся на 625-м значении, проверьте, не пропущено ли слово состояния.

Критерии проверки

Работа считается выполненной, если:

• проверки check_lcg.py, check_mt.py и check_drbg.py завершаются без ошибок;
• состояние LCG и MT восстановлено, секретный токен предсказан, HMAC_DRBG совпал с тестовым вектором;
• измерения и наблюдения записаны в журнал вместе с объяснением расхождений с предсказанием;
• на контрольные вопросы даны ответы своими словами, а не пересказ команд.

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

1. Чем истинный генератор отличается от псевдослучайного и почему для ключей нужен именно CSPRNG?
2. Почему LCG восстанавливается по трём выходам при известном модуле?
3. Как восстановить неизвестный модуль LCG и почему помогает НОД разностей?
4. Почему MT19937 непригоден для криптографии, несмотря на огромный период?
5. Что такое tempering и почему оно обратимо?
6. Как связано число 624 с размером состояния MT19937?
7. Сформулируйте требование непредсказуемости следующего бита.
8. Что проверяют тестовые векторы CAVP и чего они не проверяют?
9. Почему random в Python нельзя использовать для токенов, а secrets можно?
10. В чём была ошибка Debian OpenSSL 2008 и почему она затронула столько систем?
11. Как слабый генератор приводит к общим простым множителям у RSA-ключей?
12. Почему статистические тесты не доказывают криптографическую стойкость?