🎓 Что такое CSPRNG

Зачем эта заметка

Матчасть под провабли-фейр кости. Документы 06 Честность кубиков и ADR-0008 используют слово «CSPRNG» как данность — здесь разбираем, что это, почему обычного генератора мало и что даёт JVM. Продолжение про хеши/HMAC — 🎓 Хеш, commit-reveal и HMAC.

CSPRNG = Cryptographically Secure PseudoRandom Number Generator, криптографически стойкий генератор псевдослучайных чисел. Разница с обычным генератором (как та java.util.Random, что лежит внутри scala.util.Random) — не в «качестве случайности» по статистике, а в стойкости против противника, который видит выход и пытается предсказать остальное.

---

Случайность, которая нужна костям

Есть два разных сорта случайности, и их постоянно путают.

• Энтропия (истинная случайность) — физический шум: тайминги прерываний, тепловой шум, RDRAND/RDSEED в CPU. Её мало, она медленная, её собирает операционная система.
• Псевдослучайность — детерминированный поток чисел, «размотанный» из короткого сида (seed) математической формулой. Быстрая и бесконечная, но полностью определяется сидом.

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

---

Обычный PRNG — это детерминированный поток

Классический пример — линейный конгруэнтный генератор (LCG), ровно он лежит в java.util.Random (и, как мы выяснили, в библиотеке evolution-gaming/random — это её чистый функциональный клон):

$s_{n+1}=(s_n\cdot \text{0x5DEECE66D}+\text{0xB})\mathrm{mod}{2}^{48}$

Очередное «случайное» число — это старшие биты состояния $s_n$, после чего состояние прокручивается формулой дальше.

flowchart LR
    seed["сид s₀<br/>(48 бит)"] --> f1["LCG"]
    f1 --> s1["s₁"] --> out1["выход₁<br/>(старшие биты)"]
    s1 --> f2["LCG"]
    f2 --> s2["s₂"] --> out2["выход₂"]
    s2 --> f3["LCG"]
    f3 --> dots["…"]

Ключевое: весь бесконечный поток однозначно определяется сидом s₀. Это прекрасно для симуляций и тестов (воспроизводимость!), но смертельно для костей, если противник умеет вычислить s₀ или текущее состояние.

---

Что делает генератор «криптостойким»

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

1. Непредсказуемость вперёд (next-bit test). Видя сколько угодно бит уже выданного потока, никакой эффективный алгоритм не предскажет следующий бит с вероятностью заметно выше $\frac{1}{2}$. По теореме Яо это эквивалентно «проходит вообще все полиномиальные тесты».
2. Стойкость при компрометации состояния (backtracking resistance). Даже если внутреннее состояние утекло прямо сейчас, нельзя восстановить прошлые выходы (это ровно то, на чём стоит commit-reveal), а после подсева свежей энтропии — и будущие.

Плюс подразумевается большое пространство сида (≥ 128 бит), чтобы его нельзя было тупо перебрать.

	Обычный PRNG (LCG, MT)	CSPRNG
Цель	статистически «похоже на случай»	стойкость к противнику
Предсказать следующее по прошлым	тривиально	вычислительно невозможно
Восстановить сид / состояние	легко	невозможно
Скорость	максимальная	высокая (чуть дороже)
Примеры	java.util.Random, evolution-gaming/random, MT19937	SecureRandom, /dev/urandom, ChaCha20/DRBG
Годится для костей?	❌	✅ (для сида)

---

Почему LCG и Mersenne Twister проваливаются

• LCG (java.util.Random). Рекуррента линейна. Имея пару последовательных выходов, состояние $s_n$ восстанавливается решением линейной системы (отброшенные младшие биты добираются перебором или LLL-атакой на решётке). Дальше предсказуемы и будущее, и прошлое. Сам сид — всего 48 бит: $2^{48}\approx 2.8\cdot 10^{14}$ перебирается на обычном железе.
• Mersenne Twister (MT19937). Огромное состояние (19937 бит), отличная статистика — но не криптостойкий: 624 подряд идущих выхода позволяют обратить его tempering-преобразование, восстановить всё состояние и предсказать весь дальнейший поток.

flowchart LR
    obs["противник видит<br/>2–3 выхода"] --> solve["решает линейную<br/>систему / инвертирует"]
    solve --> state["полное состояние sₙ"]
    state --> past["все прошлые кости"]
    state --> future["все будущие кости"]
    style past fill:#7f1d1d,color:#fff
    style future fill:#7f1d1d,color:#fff

Оба — отличный инструмент для Monte-Carlo и тестов, катастрофа для криптографии.

---

Как устроен настоящий CSPRNG

Всегда на базе криптопримитива, чей выход неотличим от случайного без знания ключа/состояния. Общая конструкция:

flowchart LR
    subgraph OS["источники энтропии (ОС)"]
        e1["тайминги прерываний"]
        e2["RDRAND / RDSEED"]
        e3["события железа"]
    end
    OS --> pool["энтропийный пул"]
    pool -->|"сид"| drbg["DRBG<br/>(детерминированное ядро:<br/>ChaCha20 / AES-CTR / HMAC-SHA2)"]
    drbg --> stream["стойкий поток бит"]
    pool -. "периодический подсев" .-> drbg

• Ядро (DRBG — Deterministic Random Bit Generator). Стандарт NIST SP 800-90A описывает три: Hash_DRBG, HMAC_DRBG (на SHA-2), CTR_DRBG (на AES в режиме счётчика). Именно они крутятся в промышленных системах.
• Потоковые шифры. ChaCha20 — основа Linux-RNG (системный вызов getrandom(2) и /dev/urandom) и BSD/macOS arc4random (несмотря на легаси-имя «rc4», внутри давно ChaCha20).
• Энтропия для сида. Собирается ОС и выдаётся через getrandom(2) / /dev/urandom (Linux), BCryptGenRandom (Windows).

Схема неизменна: истинная энтропия сидит детерминированное криптоядро, которое выдаёт быстрый стойкий поток и периодически подсевается свежей энтропией.

---

На JVM — java.security.SecureRandom

В нашем play-api (Scala 3 / cats-effect) CSPRNG — это java.security.SecureRandom. Практика:

• new SecureRandom() — неблокирующий, сам сидится от ОС. Для подавляющего большинства случаев (в т.ч. наш 32-байтный serverSeed) — то, что нужно; зовём nextBytes(buf).
• SecureRandom.getInstanceStrong() на Linux часто резолвится в NativePRNGBlocking (читает /dev/random) → может блокировать при нехватке энтропии. Только для долгоживущих ключей, не на каждый запрос/партию.
• Провайдер DRBG (с Java 9) — настраиваемый SP 800-90A через свойство securerandom.drbg.config.

Грабли, на которых подрывались продакшены

• Никогда не делай setSeed(константа) до первого nextBytes на legacy-провайдере SHA1PRNG — генератор станет детерминированным и предсказуемым. Классический футган «предсказуемый SecureRandom»; на недосеве SecureRandom в 2013-м массово увели Bitcoin-кошельки на Android.
• Не полагайся на конкретный алгоритм по умолчанию между платформами — фиксируй провайдер, если важна воспроизводимость самосева.

Миф про /dev/urandom мёртв

«urandom небезопасен, надо /dev/random» — устаревшее заблуждение. После инициализации пула urandom — это полноценный CSPRNG, блокировка на /dev/random не нужна. Старый флаг -Djava.security.egd=file:/dev/./urandom был про латентность старта JVM, а не про безопасность.

Функциональная обёртка под наш стек

В cats-effect есть cats.effect.std.SecureRandom[F] (с CE 3.4) — идиоматичная обёртка над java-SecureRandom в F[_]. Ровно она ложится в play-api, в отличие от evolution-gaming/random, который к секьюрности отношения не имеет (см. ниже).

---

Где CSPRNG в наших костях

Тонкий и важный момент. В провабли-фейр игрок видит детерминированный, воспроизводимый результат броска (иначе он не смог бы его перепроверить). Значит сами броски по определению не генерятся CSPRNG на лету.

CSPRNG работает ровно один раз за партию — на генерации serverSeed:

$serverSeed=\mathrm{SecureRandom}(32\text{ байта})$

Дальше непредсказуемость обеспечивает не CSPRNG, а HMAC как псевдослучайная функция (PRF) — детально в 🎓 Хеш, commit-reveal и HMAC. То есть:

• CSPRNG отвечает за «сервер не смог подобрать выгодную энтропию» — сид непредсказуем и неперебираем.
• PRF (HMAC) отвечает за «каждый бросок выглядит случайным, но пересчитывается по формуле».

Как эти два кирпича складываются в конкретный алгоритм — 06 Честность кубиков.

---

А что же evolution-gaming/random?

Раз с неё начался разговор — зафиксируем вывод. Это чистый функциональный клон java.util.Random (та же LCG-формула, те же константы), обёрнутый в StateT/cats-effect. Полезен, но не для честности:

• ✅ Годится: воспроизводимый некрипто-рандом — Monte-Carlo роллауты бота, сэмплинг, тесты. Плюс чистая Long-арифметика даёт бит-в-бит одинаковый результат на JVM и Scala.js/WASM.
• ❌ Запрещён: любой fairness-путь. Предсказуем из 48-битного состояния, сид от часов вскрывается тривиально. Для serverSeed — только SecureRandom.

---

Связанное

• 🎓 Хеш, commit-reveal и HMAC — продолжение: три примитива честности и почему HMAC ≠ RNG.
• 06 Честность кубиков — провабли-фейр и верификация — как CSPRNG + HMAC собраны в as-built алгоритм костей.
• ADR-0008 — почему commit-reveal, а не голый CSPRNG или блокчейн.