Модели атак и вычислительная стойкость

Стойкость — не свойство шифра «само по себе», а утверждение о противнике: что он знает, что может запросить и сколько вычислений готов потратить. Один и тот же AES-256 стоек против перебора ключа и бесполезен, если сервер сообщает, корректно ли дополнение; одна и та же схема RSA безопасна в теории и ломается на практике из-за общего простого множителя. Эта тема вводит язык, на котором такие утверждения формулируются: модели атак, энтропию и избыточность, игры неразличимости и экономику перебора.

Она опирается на тему 2 основного курса (совершенная секретность и вычислительная стойкость) и на апокриф 1 (статистический криптоанализ). Дальше этот язык используется везде: в теме 3 — для оценки ГСЧ, в темах 4–6 — для атак на режимы, в теме 9 — для оракулов RSA.

Противник и модели атак

Что известно противнику

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

Стандартная иерархия — от слабой к сильной ²⁸:

На практике сильнейшая модель почти всегда достижима: сервер, который на неверный шифртекст отвечает разной ошибкой, уже является оракулом расшифрования. Именно так работают атаки на padding oracle (тема 5) и на PKCS#1 v1.5 (тема 9).

Атака по известному открытому тексту на формате

Пусть файл — это BMP, а шифрование блочное с режимом ECB. Первые 54 байта заголовка известны и одинаковы у всех файлов; противник получает пары «заголовок — первый блок шифртекста» и может проверить гипотезу о ключе или режиме. Даже если сам ключ не извлекается, структура файла утекает: одинаковые блоки дают одинаковые шифртексты, и по ним видно, где в документе повторяется текст.

Отсюда практическое правило: криптостойкость начинается с формата. Случайный IV, уникальный nonce и AEAD убирают эту утечку; отсутствие любого из них превращает «известный открытый текст» в рабочий инструмент.

Энтропия, избыточность и расстояние единственности

Энтропия источника

Энтропия дискретного источника X с вероятностями p_i:

H(X) = −Σ p_i·log2 p_i.

Она измеряет неопределённость в битах. Для равномерного выбора из 256 значений H = 8 бит; для пароля из четырёх знаков по 10 вариантов — log2 10^4 ≈ 13,3 бита, если выбор равномерен. Реальные пароли распределены неравномерно, поэтому их энтропия ниже формальной: словарь из миллиона слов даёт около 20 бит, а не 20 «по числу символов».

Для текста на естественном языке энтропия на символ оценивается в 1,1–1,5 бита для английского и 1,5–2 бита для русского при равномерном пределе log2 26 ≈ 4,7 и log2 33 ≈ 5,04 ¹. Разница между пределом и фактической энтропией — избыточность R_L; именно она позволяет статистическому криптоанализу восстанавливать ключ по небольшому фрагменту.

Расстояние единственности

Шеннон показал, что ключ определяется однозначно, начиная с некоторого объёма шифртекста ¹:

N = H(K) / D,

где H(K) — энтропия ключа, а D = log2|A| − H(M) — избыточность открытого текста на символ. Для случайного шифртекста знаменатель равен именно избыточности языка, потому что шифртекст не содержит структуры сверх равномерной.

Пример: ключ Виженера длины 8 над русским алфавитом имеет энтропию 8·log2 33 ≈ 40,4 бита; при избыточности 3,2 бита на букву N ≈ 13 букв. Это теоретический минимум: он говорит, что информации в принципе достаточно, но не гарантирует, что конкретный алгоритм её извлечёт. На практике для надёжного взлома нужны сотни букв, а для коротких сообщений остаётся неоднозначность.

Игры неразличимости

IND-CPA

Стойкость к выбранному открытому тексту формулируется как игра ⁴. Противник A получает доступ к оракулу шифрования E_k(·) и выбирает два сообщения равной длины m0, m1. Экспериментатор бросает монету b ∈ {0,1}, шифрует m_b и отдаёт c. Противник должен угадать b. Преимущество:

Adv(A) = |2·Pr[A угадал] − 1| — та же конвенция, что и в теме 2.

Схема IND-CPA-стойка, если для любого эффективного A преимущество пренебрежимо мало. На рисунке 1 показаны роли участников игры и то, почему детерминированный шифр проигрывает её с преимуществом 1.

Важно, что противник может шифровать сколько угодно до и после выбора: именно это ловит детерминированные схемы.

IND-CCA

Если дополнительно дать доступ к оракулу расшифрования D_k(·) (с запретом запрашивать сам c), получится IND-CCA — стойкость к выбранному шифртексту. AEAD-схемы проектируются так, чтобы быть IND-CCA: подделка тега должна быть вычислительно неосуществима, иначе оракул ошибки даёт преимущество. Схема, стойкая в IND-CPA, но не в IND-CCA, ломается именно через ошибки расшифрования — это и есть padding oracle.

Почему детерминированное шифрование не IND-CPA

Пусть E_k детерминирована. Противник выбирает m0 ≠ m1, получает c = E_k(m_b) и сам вычисляет E_k(m0) (оракул доступен). Если c = E_k(m0), он отвечает 0, иначе 1. Преимущество равно 1 — максимально возможному. Формально: детерминированная функция от открытого текста не может скрывать равенство сообщений, а IND-CPA требует, чтобы шифртексты разных сообщений были неотличимы.

Отсюда требование вероятностного шифрования ⁷: случайный IV/nonce в каждом вызове. В схеме с nonce противник видит разные c для одного m и не может воспроизвести шифртекст; в схеме без nonce — может, и игра проиграна.

def adversary(encrypt):
    m0, m1 = b"A" * 16, b"B" * 16
    c0 = encrypt(m0)
    c = encrypt(m0)          # тот же открытый текст ещё раз
    return 0 if c == c0 else 1

Для детерминированного оракула этот противник угадывает всегда; для вероятностного — не лучше монеты.

Экономика перебора

Сколько стоит 2^40, 2^56, 2^64, 2^128

Оценка перебора — это произведение размера пространства ключей на стоимость одной проверки. Измеренная на учебной машине скорость SHA-256 в Python — около 2,9·10^6 операций в секунду на одно ядро (замер в лабораторной работе); специализированная GPU даёт порядка 10^10, ASIC — до 10^13 проверок в секунду для конкретной функции.

На рисунке 2 те же оценки показаны в логарифмическом масштабе: рост на 16 бит добавляет к десятичному логарифму времени примерно 4,8, то есть увеличивает время в 60 тысяч раз.

Числа читаются так: 40 бит — это «сегодня», 56 бит — «недели на GPU», 64 бита — «годы на GPU, но дни на ASIC», 80 бит — «недостижимо для перебора», 128 бит — «недостижимо при любых мыслимых технологиях». Отсюда рекомендации NIST: 112–128 бит стойкости для симметричных ключей и 2048–3072 бита для RSA на горизонте до 2030 года ³.

Закон Мура и Гровер

Закон Мура удваивает вычислительную мощность примерно каждые 18–24 месяца. За 30 лет это даёт рост в 2^15–2^20 раз, то есть прибавку 15–20 бит к достижимому перебору. Поэтому ключ 80 бит, казавшийся недостижимым в 1990-х, сегодня находится на грани, а 128 бит остаётся недостижимым: разрыв в 48 бит нельзя закрыть удвоениями.

Квантовый алгоритм Гровера даёт квадратичное ускорение перебора: 2^n превращается в 2^(n/2) ⁵. Для симметричного ключа это означает, что 128-битный ключ даёт 64-битную стойкость к квантовому перебору, поэтому для долгосрочной защиты рассматривают 256-битные ключи. Для RSA и ECC картина хуже: алгоритм Шора решает факторизацию и дискретный логарифм за полиномиальное время, и это обсуждается в теме 14.

От моделей к практике

Три вопроса перед применением схемы

Первое: какая модель атаки достижима в этой системе? Если сервер возвращает разные ошибки, противник уже имеет IND-CCA-оракул, и схема должна быть стойкой в IND-CCA. Второе: что утекает помимо шифрования — длины, время, коды ошибок, повторяющиеся блоки? Третье: какова цена перебора для конкретного пароля или ключа — не «128 бит», а сколько секунд на доступном оборудовании?

Эти вопросы превращают абстрактную стойкость в инженерное решение ⁶. AES-256 с уникальным nonce и AEAD — это не «алгоритм», а набор требований: ключ из CSPRNG, nonce не повторяется, тег проверяется до использования открытого текста, ошибки не различаются. Нарушение любого из них ломает систему быстрее, чем любой мыслимый перебор.

Что дальше

Следующая тема — генераторы случайности: откуда берутся ключи и nonce и что происходит, когда генератор предсказуем. Затем темы 4–6 покажут, как ошибки применения (повтор nonce, ECB, отсутствие MAC) превращаются в конкретные атаки. Язык этой темы — модели, энтропия, преимущество, стоимость — будет использоваться в каждой из них.

Итоги темы

Стойкость формулируется как утверждение об игре: противник с определёнными возможностями не может отличить шифртексты с преимуществом лучше случайного. Модели атак упорядочены от «только шифртекст» до «выбранный шифртекст», и практическая система должна выдерживать сильнейшую достижимую модель. Детерминированное шифрование проигрывает IND-CPA с преимуществом 1, поэтому вероятностность и уникальный nonce обязательны.

Энтропия и избыточность объясняют, почему язык помогает криптоанализу и почему короткие сообщения неоднозначны. Экономика перебора переводит биты в годы: 40 бит — сутки, 56 — недели на GPU, 80 — недостижимо, 128 — недостижимо принципиально. Квантовый перебор по Гроверу вдвое сокращает эффективную длину симметричного ключа, а алгоритм Шора обнуляет стойкость RSA и ECC — тема 14 вернётся к этому. Главный вывод: стойкость — это свойство всей системы, а не выбранного алгоритма.

Литература

1. Shannon C. E. Communication Theory of Secrecy Systems. — Bell System Technical Journal, 1949, Т. 28, № 4, С. 656–715. DOI: 10.1002/j.1538-7305.1949.tb00928.x
2. Katz J., Lindell Y. Introduction to Modern Cryptography. — 3-е изд. — CRC Press, 2020.
3. NIST. Recommendation for Key Management, Part 1: General. — SP 800-57 Part 1 Rev. 5, 2020. https://doi.org/10.6028/NIST.SP.800-57pt1r5
4. Boneh D., Shoup V. A Graduate Course in Applied Cryptography. — 2023. https://toc.cryptobook.us/
5. Grover L. K. A Fast Quantum Mechanical Algorithm for Database Search. — Proceedings of STOC 1996, С. 212–219. DOI: 10.1145/237814.237866
6. Aumasson J.-P. Serious Cryptography. — 2-е изд. — No Starch Press, 2024.
7. Ferguson N., Schneier B., Kohno T. Cryptography Engineering. — Wiley, 2010.
8. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. https://cacr.uwaterloo.ca/hac/

Дополнительные материалы к апокрифу 2

Вопросы для самопроверки

1. Что входит в модель атаки и почему она задаёт верхнюю границу стойкости?
2. Почему стойкость в сильной модели гарантирует стойкость в слабой, но не наоборот?
3. Как избыточность языка связана с числом текста, необходимого для взлома?
4. Что означает «пренебрежимо малое преимущество» и почему это асимптотическое понятие?
5. Почему детерминированное шифрование проигрывает игру с преимуществом 1?
6. Чем IND-CCA отличается от IND-CPA и какие схемы её достигают?
7. Почему случайный nonce не спасает от утечки длины сообщения?
8. Как оценить стоимость перебора, зная скорость одной проверки?
9. Сколько бит добавляет 20 лет роста по закону Мура?
10. Почему алгоритм Гровера не делает AES-128 бесполезным сегодня?
11. Что такое оракул и как сервер с разными ошибками становится оракулом?
12. Почему для паролей используют медленные KDF, а для сессионных ключей — быстрые?

Глоссарий темы

Шпаргалка

python3 oracle.py
python3 adversary_template.py
python3 check_ind.py -v
python3 check_scaling.py -v
python3 check_entropy.py -v

Что почитать и посмотреть

• Boneh D., Shoup V. A Graduate Course in Applied Cryptography — https://toc.cryptobook.us/ — главы про IND-CPA/IND-CCA с формальными играми.
• Katz J., Lindell Y. Introduction to Modern Cryptography — главы 3 и 4; аккуратные определения и доказательства.
• NIST SP 800-57 Part 1 Rev. 5 — https://doi.org/10.6028/NIST.SP.800-57pt1r5 — рекомендации по длинам ключей и уровням стойкости.
• Aumasson J.-P. Serious Cryptography — глава про вероятностное шифрование и nonce.
• Ferguson N., Schneier B., Kohno T. Cryptography Engineering — главы о моделях атак и генерации ключей.
• keylength.com — https://www.keylength.com/ — сводные таблицы эквивалентных длин ключей.
• Grover L. K. A Fast Quantum Mechanical Algorithm for Database Search — первоисточник оценки 2^(n/2).

Углубление: почему «AES-256» ничего не гарантирует

Рекламная строка «используется AES-256» описывает примитив, а не схему. Если ключ один на всех пользователей, nonce фиксирован, а шифрование детерминировано, система проигрывает IND-CPA с преимуществом 1 независимо от длины ключа. Если сервер возвращает разные ошибки, он даёт IND-CCA-оракул, и схема может быть атакована без перебора. Если ключ выведен из пароля одной итерацией SHA-256, стойкость определяется словарём, а не AES.

Поэтому вопрос «какой алгоритм используется» — только первый из трёх. Второй: как выбираются ключи и nonce. Третий: что видит противник в ответ на ошибки и повторные запросы. Стойкость системы — произведение всех трёх ответов, и самый слабый множитель определяет результат.

Лабораторная работа 2. Игра в неразличимость

• Раздел курса: апокриф 2 «Модели атак и вычислительная стойкость»

Введение

«Северный узел» хранит документы в «Сейфе». Разработчики уверяют, что «используется AES-256, взломать невозможно». Пентест начинается не с перебора ключа, а с вопроса: что именно видит противник и какую игру он может выиграть. В этой работе два оракула — детерминированный и вероятностный — отвечают на один и тот же запрос по-разному, и от этой разницы зависит стойкость всей системы.

Работа состоит из пяти частей: свойства оракулов, игра IND-CPA, энтропия и избыточность, расстояние единственности, экономика перебора. Шестая часть, продвинутая, — оценка пароля по утёкшему хешу и разбор того, почему «AES-256» в рекламе не означает стойкости.

Цель работы

Научиться формулировать стойкость как игру с противником и переводить биты стойкости в реальные затраты времени.

После выполнения работы получится:

• объяснять разницу между детерминированным и вероятностным шифрованием на эксперименте;
• реализовывать противника, выигрывающего IND-CPA с преимуществом 1;
• измерять энтропию текста и пароля и объяснять избыточность языка;
• вычислять расстояние единственности и интерпретировать его;
• измерять скорость перебора на своей машине и экстраполировать на GPU и ASIC;
• объяснять, как квантовый алгоритм Гровера меняет оценку для симметричных ключей.

Теоретический минимум

Разделы «Противник и модели атак», «Энтропия, избыточность и расстояние единственности», «Игры неразличимости», «Экономика перебора» апокрифа 2. Из основного курса — тема 2 (модели атак, IND-CPA, рекомендации по длинам ключей).

Перечень оснащения

Ubuntu 24.04, Python 3.10+, cryptography. Права root не нужны. Архив lr-env.

mkdir -p ~/lab-apocrypha-02 && cd ~/lab-apocrypha-02
unzip ~/lr-env.zip
python3 check_ind.py -v

Порядок выполнения работы

Заполняйте заготовки по частям и после каждой запускайте соответствующую проверку. В журнал записывайте предсказание (например, «преимущество будет 1»), фактическое значение и объяснение. Числа скорости перебора зависят от машины — фиксируйте свои, а не только приведённые в тексте.

Часть 1. Свойства оракулов

Задание

1. Запустите python3 oracle.py и объясните два вывода: почему ECB воспроизводим, а GCM — нет.
2. Зашифруйте b"A"*32 детерминированным оракулом и сравните первый и второй блоки. Объясните результат.
3. Зашифруйте одно и то же сообщение вероятностным оракулом десять раз. Сколько различных шифртекстов получилось? Что в них общего по длине?
4. Ответьте: какой из оракулов соответствует «шифрованию пароля» и почему это плохо.

Что должно получиться

Два вывода команд, наблюдение о равенстве блоков ECB и о случайности GCM, короткий вывод о том, что детерминированность — свойство схемы, а не алгоритма AES.

Часть 2. Игра IND-CPA

Задание

1. Реализуйте distinguish: выберите m0 = b"A"*16, m1 = b"B"*16, получите c0 = encrypt(m0) и возвращайте 0, если предъявленный шифртекст совпал с c0, иначе 1.
2. Запустите check_ind.py -v: преимущество против детерминированного оракула должно быть около 1, против вероятностного — около 0.
3. Проведите игру 10, 100 и 1000 раз. Как меняется разброс преимущества? Оцените стандартное отклонение для 100 испытаний.
4. Объясните, почему преимущество вероятностного оракула может быть слегка отрицательным и это нормально.

Что должно получиться

Код противника, три значения преимущества, оценка разброса и объяснение, что преимущество — статистическая величина, а не гарантия каждого отдельного раунда.

Часть 3. Энтропия и избыточность

Задание

1. Реализуйте shannon_entropy, letter_entropy, max_entropy, redundancy.
2. Измерьте энтропию texts/ru_sample.txt и texts/en_sample.txt. Сравните с пределом log2 33 ≈ 5,04 и log2 26 ≈ 4,70. Объясните, почему реальная энтропия ниже.
3. Вычислите избыточность для обоих текстов. Сравните с оценкой 3,2 бита на букву из теории.
4. Оцените энтропию пароля из четырёх цифр, из восьми символов нижнего регистра, из четырёх случайных слов словаря на 10 000 слов. Сравните с типичными правилами «минимум 8 символов».

Что должно получиться

Таблица «текст — H — предел — избыточность», расчёты энтропии паролей и вывод о том, что длина в символах без оценки алфавита ничего не говорит о стойкости.

Часть 4. Расстояние единственности

Задание

1. Реализуйте unicity_distance(key_bits, redundancy).
2. Для ключа Виженера длины 4, 8 и 16 над русским алфавитом вычислите H(K) и N при избыточности 3,2 бита на букву.
3. Сравните с длиной short_ru.txt из апокрифа 1 (243 буквы). Объясните, почему для ключа длины 4 расстояние единственности меньше длины текста, но текст всё равно не ломается надёжно.
4. Повторите расчёт для 128-битного ключа AES и избыточности 3,2. Объясните результат.

Что должно получиться

Таблица «длина ключа — H(K) — N», сравнение с длиной текста и вывод о разнице между информационной достаточностью и вычислительной достижимостью.

Часть 5. Экономика перебора

Задание

1. Реализуйте measure_sha256_rate, time_for_keyspace, format_duration, grover_bits.
2. Измерьте скорость SHA-256 на своей машине. Заполните таблицу для ключей 40, 56, 64, 80, 128 бит при своей скорости, при 10^10 и при 10^13 проверок в секунду.
3. Переведите результаты в годы и сравните с таблицей теории. Совпадают ли порядки?
4. Оцените, сколько бит добавляет 30 лет роста по закону Мура (удвоение каждые 2 года).
5. Оцените стойкость 128-битного ключа против алгоритма Гровера. Сколько бит нужно, чтобы сохранить 128-битную стойкость?

Что должно получиться

Таблица из трёх скоростей, расчёт прироста по Муру, оценка Гровера и вывод о том, какие длины ключей имеют смысл на горизонте 10–20 лет.

Часть 6. Продвинутая: цена пароля и предел модели

Задание

1. Возьмите хеш SHA-256(пароль) для пароля из словаря в 10 000 слов и оцените время перебора на вашей машине и на GPU. Сравните с паролем из 12 случайных символов.
2. Объясните, почему для паролей используют медленные функции (PBKDF2, scrypt, Argon2), а для ключей — быстрые KDF; подробно — в апокрифе 8.
3. Постройте противника для ECB, который по двум блокам шифртекста определяет, совпадали ли соответствующие блоки открытого текста. Какое преимущество это даёт в реальной системе?
4. Сформулируйте, какую модель атаки реализует сервер, который возвращает разные ошибки на неверный шифртекст, и почему это превращает IND-CPA в IND-CCA.

Что должно получиться

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

Журнал работы

Фиксируйте: предсказание преимущества, число испытаний, измеренную скорость, полученные времена. Для каждого расхождения — одна фраза о причине (шум, мало испытаний, неверная формула).

Контрольные вопросы

1. Чем отличаются модели «только шифртекст» и «выбранный шифртекст»?
2. Почему детерминированное шифрование не может быть IND-CPA-стойким?
3. Что означает преимущество противника и какой максимум оно имеет при определении |2·Pr − 1|?
4. Почему вероятностное шифрование не спасает от атаки на формат сообщения?
5. Как избыточность языка связана с расстоянием единственности?
6. Почему 80-битный ключ сегодня считается слабым, а 128-битный — нет?
7. Что даёт алгоритм Гровера и почему для AES рассматривают 256-битные ключи?
8. Почему скорость перебора на GPU и ASIC отличается на порядки?
9. Какой вывод о стойкости системы можно сделать, зная только длину ключа?
10. Почему ошибки расшифрования должны быть неотличимы?
11. Что такое оракул в криптоанализе и как он возникает в реальном сервере?
12. Почему для паролей важна не только энтропия, но и стоимость одной проверки?