Слабая случайность и предсказуемые ключи

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

Слабая случайность — использование предсказуемого источника «случайных» данных (обычного ГПСЧ, плохого seed, времени, PID) там, где нужна криптографическая непредсказуемость. Это превращает огромное пространство ключей в маленькое и перебираемое.

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

Зачем это знать защитнику

Это одна из самых частых и самых тихих ошибок: код выглядит правильным, тесты проходят, а ключи при этом предсказуемы. Защитник должен на уровне рефлекса отличать «случайность для симуляций» (быстрый ГПСЧ) от «случайности для безопасности» (CSPRNG) и аудировать каждое место, где рождается секрет: чем он сгенерирован и сколько в нём реальной энтропии.

Что такое энтропия на пальцах

Энтропия измеряет непредсказуемость в битах: сколько в среднем нужно «честных вопросов да/нет», чтобы угадать значение. Если все символы одинаковы — энтропия нулевая (угадывать нечего). Чем разнообразнее и равновероятнее — тем выше. Посмотрим на формулу Шеннона и на грубую оценку «битов в ключе»:

import math
from collections import Counter

def shannon_entropy(data: str) -> float:
    counts = Counter(data)
    n = len(data)
    bits = 0.0
    for c in counts.values():
        p = c / n
        bits -= p * math.log2(p)
    return bits

weak = "111111111111"   # один символ -> предсказуемо
mixed = "a1b2c3d4e5f6"   # 12 разных символов
print("Слабый (всё одинаковое):", round(shannon_entropy(weak), 3), "бит/символ")
print("Разнообразный:          ", round(shannon_entropy(mixed), 3), "бит/символ")

def key_entropy(length: int, alphabet: int) -> float:
    return length * math.log2(alphabet)

print("PIN 4 цифры:    ", round(key_entropy(4, 10), 1), "бит")
print("Пароль 8 из 95: ", round(key_entropy(8, 95), 1), "бит")
print("Ключ 128 бит:   ", key_entropy(128, 2), "бит")

Вывод:

Слабый (всё одинаковое): 0.0 бит/символ
Разнообразный:           3.585 бит/символ
PIN 4 цифры:     13.3 бит
Пароль 8 из 95:  52.6 бит
Ключ 128 бит:    128.0 бит

13 бит у PIN — это всего ~8000 вариантов, перебираемых мгновенно. 128 бит — это 2^128 вариантов, что физически неперебираемо. Слабый генератор сжимает реальное пространство ключей до чего-то ближе к первому, чем ко второму.

Почему обычный ГПСЧ губит криптографию

Стандартные генераторы (линейный конгруэнтный метод, Mersenne Twister в random) спроектированы для скорости и статистической равномерности, а не для непредсказуемости. Их выход детерминированно зависит от внутреннего состояния: зная несколько выходов, можно восстановить состояние и предсказать все последующие — и предыдущие. Покажем это на простом линейном конгруэнтном генераторе:

def lcg(seed, a=1103515245, c=12345, m=2**31):
    state = seed
    while True:
        state = (a * state + c) % m
        yield state

gen = lcg(seed=42)
first = [next(gen) for _ in range(5)]
print("Первые 5 'случайных':", first)

# Тот же seed -> ровно та же последовательность
gen2 = lcg(seed=42)
again = [next(gen2) for _ in range(5)]
print("Повтор с тем же seed: ", again)
print("Совпадает полностью? ", first == again)

Вывод:

Первые 5 'случайных': [1250496027, 1116302264, 1000676753, 1668674806, 908095735]
Повтор с тем же seed:  [1250496027, 1116302264, 1000676753, 1668674806, 908095735]
Совпадает полностью?  True

Если ещё и seed предсказуем (например, time.time() или PID), атакующий просто перебирает разумный диапазон seed и находит ваш ключ. Так появлялись реальные провалы: ключи Bitcoin-кошельков, сгенерированные приложениями со слабым ГПСЧ; знаменитый баг Debian OpenSSL (2006–2008), когда из-за неудачной правки пространство ключей схлопнулось до десятков тысяч вариантов; предсказуемые токены сессий и кодов сброса пароля, привязанные ко времени.

Как это работает под капотом

CSPRNG (cryptographically secure PRNG) отличается двумя свойствами: непредсказуемость вперёд (по прошлым выходам нельзя предсказать следующий лучше, чем угадыванием) и backtracking resistance (по текущему состоянию нельзя восстановить прошлые выходы). Питается он из системного пула энтропии ОС (/dev/urandom, getrandom(), CryptGenRandom), который собирает шум аппаратуры. В Python это даёт модуль secrets и os.urandom. Обычный random ни одним из этих свойств не обладает.

Как защититься

• Для любых секретов — только CSPRNG. В Python это secrets (secrets.token_bytes, secrets.token_hex, secrets.token_urlsafe, secrets.randbelow) или os.urandom. Никогда не используйте random для ключей, токенов, паролей.
• Не задавайте seed вручную и не подмешивайте время/PID как источник «случайности» для крипто. CSPRNG берёт энтропию у ОС сам.
• Хватает ли битов? Для ключей и токенов — минимум 128 бит энтропии (16 байт). secrets.token_hex(16) даёт ровно столько.
• Не путайте кодировку с энтропией. Длинная строка из base64 может нести мало реальной случайности, если источник слабый. Считается источник, а не длина.
• Доверяйте библиотекам. Генерацию ключей оставляйте проверенным крипто-библиотекам (cryptography, libsodium) — они используют CSPRNG корректно.

Правовое напоминание: анализировать слабую генерацию ключей допустимо только на собственных данных или в разрешённой лаборатории; восстановление чужих ключей — преступление (УК РФ ст. 272).

Итоги

• Стойкость криптографии упирается в энтропию: предсказуемый ключ ломает любую систему без атаки на алгоритм.
• Обычный ГПСЧ (random, LCG, Mersenne Twister) детерминирован — по нескольким выходам предсказуем целиком.
• Реальные провалы — Debian OpenSSL, слабые ключи кошельков, предсказуемые токены, привязанные ко времени.
• Защита: CSPRNG (в Python — secrets / os.urandom), ≥128 бит энтропии, никакого ручного seed, доверять проверенным библиотекам.