zharkevich.ru
Случайные числа не такие случайные, как вы думаете

Случайные числа не такие случайные, как вы думаете

· 14 мин чтения

В 1999 году группа программистов из компании Cigital обнаружила, что онлайн-покер-рум ASF Software перемешивает колоду генератором псевдослучайных чисел, который инициализируется от системных часов Windows. Начальное значение (seed) — 32-битная метка времени с миллисекундной точностью.

Колода из 52 карт допускает 52! ≈ 2^226 возможных перестановок. Генератор с 32-битным seed может создать максимум 2^32 ≈ 4 миллиарда различных раскладок. Это значит, что из всех возможных раздач покер-рум использовал ничтожную долю — примерно одну из 10^58.

Зная приблизительное время начала раздачи (а его можно определить с точностью до секунды) и пять собственных карт, исследователи перебрали все возможные seed’ы и за считанные секунды определили карты всех соперников. Уязвимость продемонстрировали в прямом эфире на конференции. Покер-рум закрылся на исправление.

Это не курьёз и не единичный случай. Некорректное использование генераторов случайных чисел стоит за десятками критических уязвимостей — от бага в Debian OpenSSL, который два года порождал предсказуемые ключи, до бэкдора АНБ, заложенного прямо в стандарт NIST. Но чтобы понять, почему эти уязвимости вообще возможны, нужно сначала разобраться, что такое «случайное число» для компьютера.

Компьютер — детерминированная машина

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

Это значит, что компьютер может либо измерять физические процессы через аппаратный генератор, либо имитировать случайность алгоритмически. Второй подход называется PRNG — Pseudorandom Number Generator, генератор псевдослучайных чисел.

PRNG — это детерминированный алгоритм. Он принимает начальное значение (seed), и по нему генерирует длинную последовательность чисел, которая выглядит случайной. Но стоит задать тот же seed — и вы получите ту же самую последовательность. Всегда.

Вот простейший пример — Xorshift64, генератор Джорджа Марсальи:

struct Xorshift64 { state: u64 }

impl Xorshift64 {
    fn next(&mut self) -> u64 {
        let mut x = self.state;
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        self.state = x;
        x
    }
}

Три XOR, три сдвига — и на выходе последовательность, проходящая большинство статистических тестов. Но она полностью детерминирована:

let mut rng1 = Xorshift64::new(42);
let mut rng2 = Xorshift64::new(42);
// rng1.next() == rng2.next() — всегда true, для любого вызова

Два генератора с одинаковым seed выдают побитово идентичные последовательности. Это, кстати, полезное свойство: баг, зависящий от «случайности», можно воспроизвести, сохранив seed. Но для безопасности это катастрофа: если атакующий узнает seed, он знает всё.

LCG: генератор, с которого всё начиналось

Линейный конгруэнтный генератор (Linear Congruential Generator) предложил Деррик Лемер в 1951 году. Формула укладывается в одну строку:

state = (a * state + c) mod m

Умножить, прибавить, взять остаток. При правильно подобранных параметрах a, c и m период генератора равен m — каждое число от 0 до m−1 появляется ровно один раз, прежде чем последовательность начнёт повторяться.

struct LCG { state: u32 }

impl LCG {
    fn next(&mut self) -> u32 {
        // параметры из Numerical Recipes
        self.state = self.state.wrapping_mul(1664525).wrapping_add(1013904223);
        self.state
    }
}

LCG использовался десятилетиями — в функции rand() стандартной библиотеки C, в java.util.Random, в ранних версиях PHP. Причина проста: он быстрый и тривиальный в реализации.

Но у LCG есть серьёзные проблемы. Младшие биты катастрофически коррелированы — младший бит чередуется строго 0-1-0-1. А если брать пары или тройки последовательных чисел и рисовать их как точки в двумерном или трёхмерном пространстве, они выстраиваются в параллельные линии (гиперплоскости). Это свойство открыл Джордж Марсалья в 1968 году, и с тех пор оно носит его имя — Marsaglia effect. Для статистических симуляций это может полностью исказить результаты.

Mersenne Twister: стандарт с подвохом

В 1997 году Макото Мацумото и Такудзи Нисимура предложили MT19937 — генератор с периодом 2^19937 − 1 (это простое число Мерсенна, отсюда и название). Период настолько огромен, что записать его в десятичной форме потребовалось бы около шести тысяч цифр. Распределение проходит тесты равномерности в 623 измерениях.

Mersenne Twister быстро стал стандартом де-факто. random в Python, rand в Ruby, mt_rand в PHP, std::mt19937 в C++ — все используют MT19937.

Но у него есть свойство, которое делает его непригодным для чего-либо, связанного с безопасностью: наблюдая 624 последовательных 32-битных числа, можно полностью восстановить внутреннее состояние генератора. Внутреннее состояние MT19937 — это массив из 624 четырёхбайтных слов. Каждое выходное значение получается из элемента этого массива операцией tempering — обратимым преобразованием из XOR и сдвигов. Обратимым — значит, по выходу можно восстановить вход.

Получили 624 числа → восстановили состояние → предсказываете каждое следующее число. MT19937 — не CSPRNG.

CSPRNG: когда «выглядеть случайным» недостаточно

Здесь и проходит водораздел. PRNG достаточно для симуляций Монте-Карло, игровых движков, рандомизации тестов — ситуаций, где никто не пытается предсказать следующее число.

Монте-Карло — это метод, при котором вместо точного аналитического решения задачу «забрасывают» случайными сценариями и смотрят на статистику. Нужно вычислить π? Бросьте миллион случайных точек в квадрат с вписанной четвертью круга — доля попавших внутрь приблизится к π/4. Нужно оценить риск финансового портфеля? Сгенерируйте сто тысяч случайных сценариев движения рынка. Метод придумали Улам и фон Нейман в 1940-х годах во время работы над Манхэттенским проектом (название — от казино). Для Монте-Карло важна статистическая равномерность, но не криптографическая непредсказуемость, а детерминированность PRNG — даже плюс: зафиксировав seed, можно воспроизвести прогон для отладки. CSPRNG (Cryptographically Secure PRNG) нужен там, где от непредсказуемости зависит безопасность: токены аутентификации, криптографические ключи, nonce в подписях, перемешивание колоды в азартных играх.

CSPRNG отличается от обычного PRNG дополнительным свойством: даже зная все предыдущие числа, вычислительно невозможно предсказать следующее без знания внутреннего состояния. Это называют forward security. Обратное свойство (backward security) означает, что по текущему состоянию нельзя восстановить предыдущие выходные значения.

На практике CSPRNG — это либо обращение к операционной системе, которая собирает энтропию из аппаратных источников, либо потоковый шифр (ChaCha20, AES-CTR), используемый как генератор.

Разница в коде минимальна, разница в последствиях — фундаментальна:

// PRNG — для симуляций, игр, тестов
import mrand "math/rand/v2"
n := mrand.IntN(100) // быстро, воспроизводимо с фиксированным seed

// CSPRNG — для безопасности
import "crypto/rand"
var buf [8]byte
rand.Read(buf[:])  // непредсказуемо, даже зная все предыдущие вызовы

// Rust: чтение из ОС напрямую
fn read_urandom() -> [u8; 8] {
    use std::io::Read;
    let mut f = std::fs::File::open("/dev/urandom").unwrap();
    let mut buf = [0u8; 8];
    f.read_exact(&mut buf).unwrap();
    buf
}
// Результат: 8 непредсказуемых байт, например a7 3f 01 c9 88 2d e4 50

// Zig: CSPRNG из стандартной библиотеки
var buf: [8]u8 = undefined;
std.crypto.random.bytes(&buf);
// buf содержит 8 криптографически стойких байт

Современные генераторы: PCG, xoshiro, ChaCha

После Mersenne Twister появилось несколько генераторов, которые исправляют его слабости, оставаясь при этом быстрыми.

PCG (Мелисса О’Нил, 2014)

Permuted Congruential Generator, перестановочный конгруэнтный генератор — элегантная конструкция. Внутри — обычный LCG с хорошими математическими свойствами периода. Но выходное значение пропускается через случайную перестановку, которая зависит от самого состояния. LCG обеспечивает структуру, перестановка разрушает корреляции.

Результат: компактный генератор, который проходит все тесты BigCrush из набора TestU01 — самого строгого стандартного бенчмарка качества PRNG. При этом PCG быстрее MT19937 и имеет состояние всего в 16 байт против 2,5 КБ у MT.

xoshiro256** (Блэкман и Винья, 2018)

Семейство генераторов, оптимизированных для современных процессоров. xoshiro256** — рекомендуемый вариант для 64-битных платформ. Четыре 64-битных слова состояния, период 2^256 − 1, скорость выше, чем у MT. Используется в нескольких языковых рантаймах.

ChaCha (Дэниел Бернштейн)

Потоковый шифр, который работает и как генератор случайных чисел. ChaCha20 (20 раундов) — полноценный криптографический шифр. Сокращённые варианты — ChaCha12, ChaCha8 — используются как быстрые PRNG с большим запасом криптостойкости. Именно ChaCha стал генератором по умолчанию в Go и Rust.

/dev/random vs /dev/urandom: спор, который закончился

На протяжении десятилетий в Linux-сообществе шёл спор о двух устройствах для генерации случайных чисел.

/dev/random блокировал читающий процесс, если ядро считало, что «энтропия исчерпана». Разработчики из осторожности предпочитали его для криптографии — мол, оно «более случайное».

/dev/urandom не блокировался, и потому считался некоторыми «менее безопасным».

Криптограф Дэниел Бернштейн и другие эксперты годами объясняли, что этот страх необоснован. Суть аргумента: CSPRNG, получив достаточно начальной энтропии (скажем, 256 бит), может генерировать неограниченный поток криптографически стойких чисел. «Исчерпание энтропии» — бессмысленная концепция для правильно инициализированного CSPRNG. Блокировка /dev/random создавала ложное чувство безопасности и практическую проблему: серверы зависали в ожидании энтропии.

В Linux 5.6 (март 2020) спор был формально разрешён: /dev/random перестал блокироваться после инициализации пула энтропии. Оба устройства теперь эквивалентны.

Рекомендуемый интерфейс — системный вызов getrandom() (Linux 3.17, 2014). Он блокируется только при первом вызове, если пул энтропии ещё не инициализирован (первые секунды после загрузки ОС), и затем возвращает криптографически стойкие данные без ограничений.

Модульное смещение: когда правильный генератор не спасает

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

Наивный подход — rand() % N. Допустим, генератор выдаёт числа от 0 до 7, а нам нужен диапазон [0, 5):

// Все возможные значения rand() и их остатки при делении на 5:
// 0 % 5 = 0    ←
// 1 % 5 = 1    ←
// 2 % 5 = 2    ←
// 3 % 5 = 3
// 4 % 5 = 4
// 5 % 5 = 0    ← снова 0
// 6 % 5 = 1    ← снова 1
// 7 % 5 = 2    ← снова 2

Значения 0, 1, 2 выпадают по два раза, а 3 и 4 — по одному. Смещение — 33 %. Для игрового кубика это незаметно, для лотереи или криптографического протокола — недопустимо.

Правильный подход — rejection sampling: генерировать числа до тех пор, пока результат не попадёт в равномерно делимый диапазон. Отбросить «лишние» значения и попробовать снова. Go IntN() и Rust gen_range() делают это автоматически — но если вы пишете генератор вручную, об этом легко забыть.

Катастрофы, вызванные плохими генераторами

Модульное смещение, слабый seed, предсказуемый PRNG вместо CSPRNG — всё это не теоретические придирки. Каждая из описанных выше ошибок приводила к реальным инцидентам. Вот самые показательные.

Debian OpenSSL (CVE-2008-0166)

В 2006 году мейнтейнер пакета OpenSSL для Debian закомментировал две строки, которые Valgrind помечал как чтение неинициализированной памяти. Эти строки добавляли энтропию в пул генератора. Без них seed сводился к PID процесса — числу от 1 до 32 768.

Два года все ключи SSH, SSL-сертификаты и другие криптоматериалы, сгенерированные на Debian и Ubuntu, выбирались из набора в ~32 000 вариантов. Атакующий мог перебрать их за секунды на обычном ноутбуке.

Уязвимость обнаружили только в мае 2008 года. Сотни тысяч серверов использовали предсказуемые ключи. Это один из самых масштабных инцидентов в истории криптографии — и произошёл он из-за двух закомментированных строк.

Dual_EC_DRBG — бэкдор АНБ

В 2004 году NIST включил в стандарт SP 800-90A генератор Dual_EC_DRBG, основанный на эллиптических кривых. Уже в 2007 году Дэн Шумоу и Нильс Фергюсон из Microsoft показали: фиксированные точки кривой в стандарте позволяют тому, кто их выбрал, предсказывать выход генератора. Их доклад занял два слайда — настолько прямолинейной была атака.

В 2013 году документы Сноудена подтвердили: АНБ заплатило RSA Security 10 миллионов долларов за то, чтобы Dual_EC_DRBG стал генератором по умолчанию в библиотеке BSAFE. Государственное агентство за бюджетные деньги заложило бэкдор в стандарт и оплатило его внедрение в популярную криптобиблиотеку. NIST отозвал стандарт в 2014 году.

PlayStation 3 ECDSA (2010)

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

Sony подписывала код для PS3 алгоритмом ECDSA — и использовала одно и то же k для каждой подписи. Хакеры из fail0verflow восстановили закрытый ключ Sony и получили возможность подписывать произвольный код для PS3. На конференции 27C3 они показали атаку с формулой на одном слайде.

PuTTY (CVE-2024-31497)

В апреле 2024 года обнаружилось, что PuTTY версий 0.68–0.80 генерировал смещённые nonce для ECDSA P-521. Из 521-битного nonce первые 9 бит всегда были нулями. PuTTY пытался избежать необходимости уменьшения по модулю, но создал систематическое смещение, которого оказалось достаточно для восстановления закрытого ключа по ~60 подписям. Уязвимость затронула не только PuTTY, но и FileZilla, WinSCP, TortoiseGit — все они использовали тот же код генерации ключей.

Четыре случая, четыре десятилетия. Общий паттерн: разработчик недооценил требования к случайности — и криптографическая система развалилась.

Генераторы в Go, Rust, Zig и Nim

Все четыре языка предоставляют и PRNG, и CSPRNG, но различаются в том, что считают «разумным умолчанием».

Go: ChaCha8 по умолчанию

С Go 1.22 (февраль 2024) пакет math/rand/v2 использует ChaCha8 и получает начальное значение от ОС автоматически. Разработчику не нужно вызывать Seed() — генератор готов к работе сразу:

import mrand "math/rand/v2"

fmt.Println(mrand.IntN(100)) // случайное число [0, 100)
// Каждый запуск — разный результат

Для воспроизводимости можно создать генератор с фиксированным seed:

src := mrand.NewChaCha8([32]byte{42})
rng := mrand.New(src)
fmt.Println(rng.IntN(100)) // всегда одно и то же число

Для криптографии — crypto/rand:

import "crypto/rand"

var buf [32]byte
rand.Read(buf[:])
// 32 криптографически стойких байта для ключа или токена

До Go 1.22 math/rand использовал LCG и требовал ручного Seed(). Без него генератор при каждом запуске выдавал одну и ту же последовательность — это было источником бесконечных багов. Переход на ChaCha8 с автосевом — радикальный шаг: даже «некриптографический» генератор теперь непредсказуем.

Rust: ThreadRng = ChaCha12

В Rust генераторы случайных чисел живут не в стандартной библиотеке, а в крейте rand — осознанное решение, чтобы std оставалась минимальной. ThreadRng, получаемый через rand::rng(), использует ChaCha12 и автоматически пересевается от OsRng через каждые 16 КБ:

use rand::Rng;

let mut rng = rand::rng();
let n: u32 = rng.random_range(0..100);
// Случайное число [0, 100), криптографически стойкое

OsRng — обёртка над getrandom() (Linux) или SecRandomCopyBytes (macOS). Крейт getrandom абстрагирует платформенные различия.

Для воспроизводимых симуляций — генератор с фиксированным seed:

use rand::SeedableRng;
use rand_chacha::ChaCha8Rng;

let mut rng = ChaCha8Rng::seed_from_u64(42);
// Одна и та же последовательность при каждом запуске

Zig: максимальная явность

Zig предоставляет std.crypto.random для криптографически стойких чисел (обёртка над getrandom()). Для PRNG стандартная библиотека включает несколько алгоритмов в std.Random, но выбор — всегда за разработчиком:

// CSPRNG
var buf: [32]u8 = undefined;
std.crypto.random.bytes(&buf);

// PRNG — ручной xorshift
var rng = Xorshift64.init(12345);
const n = rng.next() % 100;

Философия Zig здесь та же, что и везде: ничего неявного. Каждый вызов генератора прозрачен, каждый seed виден.

Nim: знакомый API, знакомые грабли

Nim разделяет генераторы на два модуля: std/random для PRNG и std/sysrand для CSPRNG.

std/random использует xoroshiro128+ — генератор из семейства Блэкмана и Виньи. API приятно лаконичный:

import std/random

randomize()        # посеять от системного времени
echo rand(100)     # случайное число 0..100 (включительно)
echo rand(1.0)     # случайное float 0.0..1.0

var deck = @[1, 2, 3, 4, 5]
shuffle(deck)      # Fisher-Yates на месте

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

Для воспроизводимых тестов — явный seed:

import std/random

randomize(42)       # детерминированная последовательность
echo rand(100)      # всегда одно и то же значение

Для независимых генераторов (например, в многопоточном коде) — initRand:

var rng = initRand(12345)
echo rng.rand(100)  # не трогает глобальное состояние

std/sysrand — обёртка над ОС: getrandom() на Linux, SecRandomCopyBytes на macOS, BCryptGenRandom на Windows. API минимальный — одна функция:

import std/sysrand

let bytes = urandom(32)  # 32 криптографически стойких байта

Nim, в отличие от Go и Rust, не стал делать PRNG криптостойким по умолчанию. xoroshiro128+ — быстрый и статистически хороший генератор, но для токенов и ключей — только std/sysrand.

Полные примеры: random_demo.rs, random_demo.go, random_demo.zig, random_demo.nim.

Практические правила

Для безопасности — только CSPRNG. Токены сессий, криптографические ключи, nonce в подписях, пароли. В Go это crypto/rand, в Rust — OsRng или ThreadRng, в Zig — std.crypto.random, в Nim — std/sysrand. Никаких исключений.

Для симуляций и тестов — PRNG с фиксированным seed. Воспроизводимость — ценное свойство. Баг, зависящий от случайности, можно поймать повторно, сохранив seed. Используйте PCG, xoshiro или ChaCha8.

Никогда не сейте от системного времени для безопасности. Атакующий знает время с точностью до секунд, часто — до миллисекунд. Пространство перебора сводится к тривиальному. Именно так взломали покер ASF Software.

Не используйте rand() % N в чувствительных контекстах. Модульное смещение реально. Используйте библиотечные функции (IntN(), gen_range()), которые реализуют rejection sampling.

Не доверяйте Mersenne Twister для безопасности. MT19937 — отличный статистический генератор, но 624 наблюдений достаточно для полного восстановления состояния. Если MT используется для генерации токенов — система уязвима.

Заключение

Генерация случайных чисел — одна из тех задач, которые выглядят простыми. Вызвал rand() — получил число. Но за этим вызовом стоит алгоритм, у которого есть конкретные свойства: период, распределение, предсказуемость. И разница между «выглядит случайным» и «невозможно предсказать» — это разница между игровым кубиком и банковским токеном.

Go сделал радикальный шаг, переведя даже math/rand/v2 на ChaCha8 — стирая границу между PRNG и CSPRNG для большинства применений. Rust предоставляет богатый выбор через крейт rand, но разумный default (ThreadRng = ChaCha12) тоже криптостойкий. Zig, как обычно, требует явного выбора на каждом шаге.

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

Источники

Предыдущий
Наверх