Криптография
Вероятность и случайность в криптографии
Соберите 23 человека в комнате - и с вероятностью больше 50% у двоих совпадёт день рождения. Этот контринтуитивный факт не просто забавная математика: он лежит в основе атак, которые сокращают стойкость хеш-функций с 2^128 до 2^64 попыток. А плохой генератор случайных чисел в Android привёл к краже биткоинов в 2013 году. Случайность в криптографии - это не «примерно непредсказуемо», а строгое математическое свойство, ошибка в котором = полный взлом.
- **Birthday attack** - реальная угроза для MD5 (коллизии найдены за минуты на обычном ноутбуке)
- **Android SecureRandom bug (2013)** - слабый PRNG позволил украсть биткоины из кошельков
- **Debian OpenSSL bug (2008)** - ошибка в 1 строке кода сократила энтропию до 15 бит (32768 возможных ключей)
- **PS3 взлом (2010)** - Sony использовала фиксированное значение k в ECDSA → приватный ключ консоли восстановлен
Предварительные знания
Парадокс дней рождения
В комнате 23 человека. Какова вероятность, что у двоих совпадёт день рождения? Интуиция подсказывает «мизерная» - ведь дней в году 365. Но реальный ответ: **больше 50%**. Это и есть **birthday paradox** - результат, который ломает интуицию и ломает криптосистемы.
Секрет в том, что поиск идёт не конкретного совпадения (один конкретный день = чей-то), а **любого** совпадения среди всех пар. В группе из 23 человек таких пар: C(23, 2) = 253. Каждая пара - отдельный «шанс» на совпадение.
**Birthday attack на хеш-функции:** для нахождения коллизии в хеше длиной B бит нужно не 2^B попыток (полный перебор), а всего ~2^(B/2). Для 128-битного хеша: не 2^128 ≈ 3.4 × 10^38, а ~2^64 ≈ 1.8 × 10^19 - разница в **10^19 раз**. Поэтому криптографические хеши должны быть минимум 256 бит.
Сколько попыток нужно для birthday attack на 256-битный хеш?
Генераторы псевдослучайных чисел (PRNG)
Настоящая случайность - дорогое удовольствие (нужны физические процессы). На практике используют **PRNG (Pseudorandom Number Generator)** - детерминированный алгоритм, который по начальному значению (seed) генерирует последовательность, *похожую* на случайную. Одинаковый seed → одинаковая последовательность.
**Linear Congruential Generator (LCG)** - простейший PRNG, используемый в ранних реализациях `rand()` на C:
**LCG предсказуем!** Зная всего 3 последовательных выхода, атакующий может вычислить параметры a, c, m и предсказать все будущие числа.
**Mersenne Twister (MT19937)** - PRNG по умолчанию в Python (`random`), Java, Ruby, PHP. Период 2^19937 − 1, проходит большинство статистических тестов. Но и он **не криптографически безопасен**: наблюдая 624 последовательных 32-битных выхода, можно полностью восстановить внутреннее состояние и предсказать все будущие числа.
**Правило:** `random.random()` в Python - для симуляций и игр. Для криптографии, токенов, паролей - **никогда**. Используйте модуль `secrets`.
Почему Mersenne Twister не подходит для криптографии, несмотря на период 2^19937?
Криптографически стойкий PRNG (CSPRNG)
**CSPRNG (Cryptographically Secure PRNG)** отличается от обычного PRNG двумя ключевыми свойствами:
- **Next-bit test:** имея первые k бит последовательности, невозможно предсказать (k+1)-й бит с вероятностью заметно выше 50% за полиномиальное время
- **State compromise resistance:** если атакующий узнал текущее внутреннее состояние, он не может восстановить предыдущие выходы
**Реальная катастрофа: Android Bitcoin Wallet (2013).** Приложение для Android использовало класс `SecureRandom` из Java, который на Android имел критический баг - недостаточная инициализация entropy pool при генерации ECDSA-ключей. Результат: повторное использование параметра `k` в подписи. Из двух подписей с одинаковым `k` можно **вычислить приватный ключ**. Итог - украдены биткоины на десятки тысяч долларов.
**Мораль:** не реализуйте CSPRNG самостоятельно. Используйте проверенные примитивы ОС: `os.urandom()` в Python, `crypto.randomBytes()` в Node.js, `SecureRandom` (исправленный) в Java. Одна ошибка в генерации случайности = полный взлом системы.
В Android Bitcoin vulnerability 2013 проблема была в том, что:
Тестирование случайности
Как проверить, что генератор выдаёт «хорошую» случайность? Стандарт **NIST SP 800-22** определяет набор из 15 статистических тестов. Каждый проверяет отсутствие определённого паттерна:
Результат для `os.urandom`: p-value близко к 0.5 (оба теста пройдены). Для счётчика: p-value ≈ 0.0 (провал). Но вот в чём подвох...
**Прохождение статистических тестов ≠ криптографическая безопасность!** Mersenne Twister проходит все тесты NIST с отличными p-value, но при этом полностью предсказуем после 624 выходов. Статистические тесты проверяют *распределение*, но не проверяют *предсказуемость*.
**Для криптографии нужны оба уровня:** хорошая статистика (тесты NIST) **плюс** доказуемая вычислительная стойкость (невозможность предсказать следующий бит). CSPRNG обеспечивает оба свойства, обычный PRNG - только первое.
Если данные проходят статистические тесты на случайность, значит они криптографически безопасны
Статистические тесты проверяют только распределение. Криптостойкость требует вычислительной непредсказуемости - невозможности определить следующий бит быстрее, чем за экспоненциальное время
Mersenne Twister проходит все тесты NIST, но полностью предсказуем после наблюдения 624 выходов. Статистическая «случайность» и криптографическая «непредсказуемость» - разные математические свойства
Генератор проходит все 15 тестов NIST SP 800-22 с отличными p-value. Можно ли его использовать для генерации криптографических ключей?
Ключевые идеи
- **Birthday paradox:** вероятность коллизии растёт как ~n²/2N - для 128-битного хеша нужно не 2^128, а ~2^64 попыток
- **PRNG (LCG, Mersenne Twister)** - детерминированы и предсказуемы, годятся для симуляций, но не для криптографии
- **CSPRNG** - использует реальную энтропию ОС + криптостойкий алгоритм, непредсказуем даже при частичной утечке состояния
- **Статистические тесты (NIST)** - необходимое, но не достаточное условие: проверяют распределение, не предсказуемость
- Birthday paradox (23 человека в комнате) работает везде, где ищут совпадения - именно поэтому длину хешей приходится удваивать
Связанные темы
Случайность пронизывает всю криптографию - от генерации ключей до протоколов:
- Теория информации — Энтропия - мера случайности, определяет минимальную длину ключей
- Хеш-функции — Birthday attack определяет минимальную длину хеша для безопасности
- Цифровые подписи — ECDSA требует уникальный случайный k для каждой подписи - иначе утечка ключа
- Вычислительная сложность — Криптостойкость CSPRNG основана на вычислительной неразличимости
Вопросы для размышления
- Mersenne Twister проходит все статистические тесты - как именно доказать его непригодность для криптографии?
- Почему Debian OpenSSL bug (удаление одной строки кода) привёл к катастрофическому снижению энтропии? Какой урок из этого для разработчиков?
- Как спроектировать CSPRNG для embedded-устройства без мыши, клавиатуры и диска - откуда брать энтропию?