Криптография
Модели безопасности
Разработчик утверждает 'наш шифр безопасен - мы проверили 1000 атак'. Криптограф спрашивает: 'есть ли security reduction?'. Без формального доказательства любая уверенность в безопасности - интуиция, а не наука. RSA-OAEP имеет ROM-доказательство. Textbook RSA - нет. Это и есть разница между научной и ненаучной криптографией.
- **OAEP**: Bellare-Rogaway (1994) доказали IND-CCA2 в ROM. До этого RSA шифрование 'казалось безопасным'. После - доказательство редуцирует к RSA проблеме.
- **EdDSA**: tight security reduction в стандартной модели. ECDSA - нетайтовая редукция, что означает большую неопределённость в параметрах безопасности.
- **AES-GCM**: безопасность GHASH аутентификации доказана через security of polynomial MACs. GCM = CTR (IND-CPA) + GHASH (authentication).
- **Groth16 (ZK-SNARK)**: security proof в AGM (Algebraic Group Model) - ещё одна идеализированная модель, более сильная чем ROM. Доказательства звучности через generic group model.
Модели атак: CPA, CCA1, CCA2
Модели атак определяют что может делать атакующий. Схема шифрования считается безопасной только если устойчива против наиболее сильной реалистичной модели. Три стандартные модели: Chosen Plaintext Attack (CPA), Chosen Ciphertext Attack 1 (CCA1), CCA2 (adaptive).
Атака Блейхенбахера на RSA-PKCS1 v1.5 (1998) - реальная CCA2 атака. Сервер TLS является 'оракулом расшифровки': ошибка PKCS padding vs другая ошибка раскрывает информацию. За 1 млн запросов расшифровывает RSA ciphertext без ключа. DROWN (2016) - эксплуатация той же уязвимости против SSL серверов.
Почему HTTPS-сервер является CPA оракулом для атакующего?
IND-CPA: формальная безопасность
IND-CPA (INDistinguishability under Chosen Plaintext Attack): атакующий не может различить шифртексты двух сообщений с вероятностью значительно лучшей чем 1/2. Формально: для любого PPT (probabilistic polynomial time) атакующего advantage = |Pr[win] - 1/2| пренебрежимо мало.
IND-CPA => нельзя определить соответствие plaintext-ciphertext, но не обязательно целостность. AES-CTR IND-CPA, но malleable: изменение ciphertext бита меняет ровно тот же бит plaintext. Для защиты от модификации нужно IND-CCA2 = AEAD (AES-GCM).
Почему детерминированное шифрование (ECB, книжный RSA) не является IND-CPA безопасным?
Random Oracle Model и стандартная модель
Random Oracle Model (ROM): хэш-функция H моделируется как идеальный случайный оракул - каждый запрос возвращает независимый случайный ответ. Доказательства в ROM проще, но схемы могут быть небезопасны при реальных хэш-функциях.
Почему доказательства в ROM ценны несмотря на идеализацию хэш-функции?
Доказательства через игры и редукции
Доказательство безопасности: показать что успешный атакующий A на схему S может быть использован для решения трудной задачи P (например, DLP или факторизация). Редукция: алгоритм B использует A как подпрограмму и решает P.
Tight reduction: advantage A точно равен advantage B. Loose reduction: advantage B = advantage A / polynomial(n). Tight reductions предпочтительны: параметры схемы напрямую определяются assumed hardness. ECDSA имеет нетайтовую редукцию - один из аргументов для перехода на EdDSA с тайтовым доказательством.
Что означает 'редукция безопасности' в контексте доказательств криптографических схем?
Итоги
- **Иерархия атак**: EAV < CPA < CCA1 < CCA2. Безопасность против более сильной модели = защита от широкого класса реальных атак.
- **IND-CPA**: атакующий не различает шифртексты. Требует вероятностное шифрование. ECB и textbook RSA не IND-CPA.
- **ROM**: хэш-функция как идеальный оракул. Упрощает доказательства. Реальные хэши не являются ROM, но ROM-доказательства ценны.
- **Security reduction**: безопасность схемы = трудность задачи (DLP, факторизация). Tight reduction = прямое соответствие параметров.
Связанные темы
Модели безопасности - основа для понимания всей криптографии:
- Атаки на асимметричные системы — Атака Блейхенбахера - реальная CCA2. RSA-PKCS1 v1.5 уязвима, OAEP - нет именно потому что IND-CCA2 безопасна.
- ZK-SNARKs — Безопасность SNARKs доказана в AGM и ROM. Понимание моделей критично для оценки 'насколько верить' доказательству.
- RSA на практике — OAEP IND-CCA2 безопасен в ROM. PKCS#1 v1.5 уязвим к CCA2 (Bleichenbacher). Модели объясняют почему одно работает, другое нет.
Вопросы для размышления
- AES-CTR IND-CPA безопасен но не IND-CCA2. Что означает на практике: атакующий может незаметно модифицировать шифртекст?
- Canetti et al. (1998) показали что ROM-безопасная схема может быть небезопасной при реальных хэшах. Означает ли это что ROM-доказательства бесполезны?
- Tight vs loose reduction: ECDSA имеет loose reduction. Если предположение 'DLP за 2^128 трудна', что loose reduction говорит о реальной безопасности ECDSA?