AEAD и режимы: сломанный GCM

Аутентифицированное шифрование (AEAD) обещает сразу две вещи: данные скрыты и данные нельзя незаметно изменить. Это не «шифрование плюс MAC по вкусу», а конструкция, где обе операции связаны и проверяются вместе. GCM — самый распространённый AEAD в мире: он в TLS 1.2 и 1.3, в IPsec, в дисковом шифровании и в библиотеках, которыми пользуются все.

Именно поэтому у GCM есть одно требование, нарушение которого обнуляет обещание: nonce обязан быть уникальным для каждого сообщения при данном ключе. Не «случайным», не «секретным» — уникальным. Если nonce повторился, повторяется ключевой поток (конфиденциальность ломается так же, как в поточном шифре), а разность тегов двух сообщений превращается в уравнение на ключ аутентификации H, после чего подделка тега становится арифметикой.

Тема показывает конструкцию изнутри: умножение в GF(2^128), GHASH, сборку тега. Затем — три атаки: восстановление второго сообщения при повторе nonce, восстановление H по двум известным открытым текстам и подделку тега для изменённого сообщения. Заканчивается разбор тем, как проектировать протокол, чтобы повтор nonce был невозможен или безвреден: SIV, детерминированные nonce, разделение ключей.

Что такое AEAD

Интерфейс и гарантии

AEAD-схема принимает ключ, nonce, открытый текст и связанные данные (AAD), а возвращает шифртекст и тег. AAD не шифруется, но аутентифицируется: заголовки, номера последовательностей, версии протокола попадают в тег и потому не могут быть изменены.

Гарантия конфиденциальности: без ключа шифртекст неотличим от случайного. Гарантия целостности: любое изменение шифртекста, тега, nonce или AAD приводит к отказу проверки с вероятностью, близкой к единице. Порядок операций при расшифровании строгий: сначала проверка тега, только потом расшифрование и разбор полей. Если сделать наоборот, получится оракул — ровно тот, что разобран в апокрифе 5.

Почему «шифрование плюс MAC» — не то же самое

Собрать AEAD из двух примитивов можно, но надо угадать порядок и охват. Encrypt-then-MAC поверх CBC работает, MAC-then-encrypt оставляет оракул дополнения. GCM решает это конструктивно: один ключ, одна операция, тег охватывает всё. Плата — жёсткие требования к nonce и цена умножения в GF(2^128) на некоторых платформах ⁷.

Конструкция GCM

Ключ аутентификации и GHASH

Из ключа шифрования K выводится ключ аутентификации H = E_K(0^128). GHASH — полиномиальный хеш: входные блоки складываются и умножаются на H в поле GF(2^128) по модулю x^128 + x^7 + x^2 + x + 1 ¹. Схема: Y_0 = 0, Y_i = (Y_{i-1} ⊕ X_i) · H.

Конструкция описана Макгрю и Виегой ². Поле определено над GF(2), поэтому умножение — это сдвиги и XOR, без переносов; аппаратно оно ускоряется инструкцией PCLMULQDQ. Свойство, которое нас интересует: GHASH линеен по входу при фиксированном H и полиномиален по H при фиксированном входе. Обе линейности и эксплуатируются.

Шифрование и тег

Шифрование — CTR с начальным счётчиком J_0 = nonce || 0x00000001 для 96-битного nonce; в TLS 1.2 эта же конструкция описана в RFC 5288 ³. Тег: T = GHASH(H, AAD, C) ⊕ E_K(J_0). Расшифрование повторяет вычисления и сравнивает тег. Структура на рисунке 1.

Важно, что E_K(J_0) одинаково для всех сообщений с одним nonce. Это и есть точка, из которой растёт атака при повторе: маска сокращается при вычитании тегов.

Повтор nonce: две атаки сразу

Конфиденциальность

Если два сообщения зашифрованы с одним nonce, их потоки совпадают: C_1 ⊕ C_2 = P_1 ⊕ P_2. Зная один открытый текст, противник получает второй. Это в точности two-time pad из апокрифа 4, только внутри AEAD — и потому особенно обидно: разработчик выбрал «стойкий режим» и всё равно получил поточный шифр с повтором.

Целостность

Теги двух сообщений с одним nonce: T_1 ⊕ T_2 = GHASH(H, AAD_1, C_1) ⊕ GHASH(H, AAD_2, C_2), потому что E_K(J_0) сокращается. Правая часть — полином по H с коэффициентами, известными из шифртекстов; его степень равна числу блоков GHASH-входа, то есть включает и блок длины. Уравнение решается не как система линейных уравнений, а как задача о корнях полинома над GF(2^128): стандартный приём атаки — построить два таких полинома по двум парам сообщений и взять их наибольший общий делитель, который с высокой вероятностью равен H − h; стоимость полиномиальна по числу блоков ⁴.

Получив H, противник подделывает тег для любого сообщения: T' = T ⊕ GHASH(H, AAD, C) ⊕ GHASH(H, AAD, C'). Ключ шифрования при этом не нужен — нужен только один валидный тег и H.

Наглядный расчёт в упрощённой модели

В учебной модели, где GHASH определён как Y_i = (Y_{i-1} ⊕ C_i)·H без блока длины, для сообщения из одного блока и пустого AAD получается GHASH(H, C) = C · H, и разность тегов даёт (C_1 ⊕ C_2) · H = T_1 ⊕ T_2. Если C_1 ≠ C_2, то H = (T_1 ⊕ T_2) · (C_1 ⊕ C_2)^{-1} — одно деление в поле. Эта модель удобна для первого знакомства, но лабораторная работа использует полный GHASH с блоком длины: там после деления требуется ещё извлечь квадратный корень, а для много-блочных сообщений — решать полиномиальное уравнение. Смысл атаки тот же; отличается только объём арифметики.

В стандартном GCM (NIST SP 800-38D) GHASH получает на вход ещё и блок длины L = 0^64 ‖ len(C)_64, поэтому для одного блока шифртекста GHASH(H, C) = C·H^2 ⊕ L·H: степень повышается, и «одного деления» уже нет. Атака остаётся рабочей — меняется только техника решения уравнения на H, — но формула C·H верна лишь для оговорённой учебной модели и не должна переноситься на реальный GCM.

Подделка тега

Атака без ключа шифрования

Имея H и один валидный (C, T), противник меняет шифртекст на C' и пересчитывает тег по формуле выше. Сервер принимает сообщение: тег верный, шифртекст расшифровывается в желаемый текст. Целостность исчезла полностью, хотя AES не взломан и ключ не извлечён.

Почему это не «теоретическая» атака

В 2016 году группа исследователей просканировала Интернет и нашла тысячи TLS-серверов и библиотек, которые повторяли nonce в GCM из-за ошибок в генерации или из-за отката при перезапуске ⁶. Атака на nonce-reuse в GCM входит в стандартный арсенал; в учебных заданиях она воспроизводится за десятки строк кода.

Как проектировать правильно

Уникальность nonce

Nonce должен быть уникален для каждой пары «ключ, сообщение». Два рабочих способа: счётчик, который никогда не повторяется (и хранится надёжно), или случайные 96 бит с вероятностью коллизии, приемлемой для объёма сообщений. Второй способ требует оценки: при 2^32 сообщениях вероятность коллизии около 2^-33, что для большинства протоколов приемлемо, но для долгоживущих ключей — нет.

Ключ обязан меняться до исчерпания счётчика или до накопления слишком большого числа сообщений. В TLS 1.3 это зашито в дизайне: ключи обновляются, номера последовательностей не повторяются, а nonce выводится из ключа и счётчика ⁸.

SIV и детерминированное шифрование

Если nonce негде хранить (например, шифрование файлов), используют SIV: тег вычисляется первым как синтетический IV и подаётся в режим шифрования. Повтор nonce становится безвредным, потому что IV получается из самого сообщения; цена — невозможность параллельного шифрования и необходимость двух проходов ⁵.

Другой вариант — детерминированный nonce из счётчика с гарантией уникальности на уровне хранилища: база данных выдаёт монотонный номер, и он же служит nonce.

Разделение ключей и домены

Один ключ — одно назначение. Если один и тот же ключ используется и для GCM, и для чего-то ещё, требования к nonce складываются, и ошибка в одном месте ломает другое. Вывод ключей по назначению (HKDF с разными метками) стоит дёшево и снимает целый класс ошибок.

Итоги темы

• AEAD связывает конфиденциальность и целостность в одной операции; порядок «сначала тег, потом текст» обязателен.
• GCM: H = E_K(0^128), GHASH — полиномиальный хеш, тег маскируется E_K(J_0).
• Повтор nonce ломает конфиденциальность (поток повторяется) и целостность (H восстанавливается).
• В упрощённой учебной модели (без блока длины) с одним блоком сообщения H вычисляется одним делением в GF(2^128); в стандартном GCM уравнение на H полиномиально и решается через НОД полиномов.
• Защита: уникальный nonce, счётчики, ротация ключей, SIV, разделение ключей по назначению.

Литература

1. NIST. SP 800-38D: Recommendation for Block Cipher Modes of Operation — Galois/Counter Mode. 2007. — спецификация GCM и требования к nonce.
2. McGrew D., Viega J. The Galois/Counter Mode of Operation (GCM). 2004. — исходное описание конструкции и доказательства.
3. RFC 5288: AES Galois Counter Mode for TLS. 2008. — как GCM встроен в TLS 1.2.
4. Joux A. Authentication Failures in NIST Version of GCM. 2006. — разбор последствий повтора nonce и слабостей аутентификации.
5. Rogaway P., Shrimpton T. A Provable-Security Treatment of the Key-Wrap Problem. 2006. — основания SIV и детерминированного шифрования.
6. Böck H., Zauner A., Devlin S., Somorovsky J., Jovanovic P. Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS. 2016. — измерение реальных повторов nonce в Интернете.
7. RFC 5116: An Interface and Algorithms for Authenticated Encryption. 2008. — общий интерфейс AEAD и требования к nonce.
8. RFC 8446: The Transport Layer Security (TLS) Protocol Version 1.3. 2018. — обновление ключей и построение nonce в TLS 1.3.

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

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

1. Чем AEAD отличается от «шифрование плюс отдельный MAC»?
2. Что входит в тег GCM, а что нет?
3. Почему AAD не шифруется, но должен аутентифицироваться?
4. Как из ключа получается H и почему он один на все сообщения?
5. Почему GHASH линеен по входу при фиксированном H?
6. Что произойдёт, если в GHASH забыть блок длин?
7. Почему повтор nonce ломает конфиденциальность так же, как в поточном шифре?
8. Почему при повторе nonce сокращается E_K(J_0)?
9. Как восстановить H для сообщения из одного блока и почему после деления нужен квадратный корень?
10. Почему сообщение из n блоков даёт полиномиальное уравнение на H, а не систему линейных уравнений, и как его решают?
11. Почему для подделки тега не нужен ключ шифрования?
12. Почему порядок «сначала тег, потом расшифрование» обязателен?
13. Что даёт ротация ключей и как оценить её частоту?
14. Почему SIV устойчив к повтору nonce и какова его цена?
15. Какие требования к nonce в TLS 1.3 и как они выполняются?

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

Шпаргалка

cp gcm_core_template.py gcm.py        && python3 check_aead.py
cp nonce_reuse_template.py nonce_reuse.py && python3 nonce_reuse.py
python3 aead_service.py

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

• NIST SP 800-38D — спецификация GCM с тестовыми векторами.
• McGrew, Viega. The Galois/Counter Mode of Operation — исходное описание и обоснование.
• Joux. Authentication Failures in NIST Version of GCM (2006) — почему повтор nonce смертелен.
• Böck et al. Nonce-Disrespecting Adversaries (2016) — сколько реальных серверов повторяют nonce.
• RFC 5116 — интерфейс AEAD и требования к nonce.
• RFC 8446, раздел 5.3 — построение nonce и обновление ключей в TLS 1.3.
• Rogaway, Shrimpton — SIV и детерминированное шифрование.
• Документация cryptography по AESGCM — https://cryptography.io/en/latest/hazmat/primitives/aead/.

Углубление: почему восстановление H — это задача о корнях полинома

GHASH по сообщению из n блоков — многочлен степени n от H над GF(2^128). Точная форма зависит от того, включён ли блок длины: в стандартном GCM он входит последним блоком и добавляет ещё одну степень, поэтому для одного блока шифртекста с пустым AAD получается C·H^2 ⊕ L·H, а не C·H.

упрощённая модель:  GHASH = X_1·H^n ⊕ X_2·H^(n−1) ⊕ … ⊕ X_n·H
стандартный GCM:    GHASH = (AAD||0^pad||C||0^pad||L) · H^m

При фиксированных блоках это многочлен от одной неизвестной H. Разность тегов двух сообщений с одним nonce даёт уравнение P(H) = T_1 ⊕ T_2 с известными коэффициентами. Для одного блока это уравнение степени 2 (или 1 в упрощённой модели): степень 1 решается делением в поле, степень 2 — делением и извлечением квадратного корня, единственного в характеристике 2 (H = (H^2)^(2^127)). Для нескольких блоков получается уравнение высокой степени, и его решают как задачу о корнях над GF(2^128): строят два полинома по двум парам сообщений и берут их наибольший общий делитель (метод Жу — «forbidden attack»), либо применяют факторизацию над полем. Приведение к системе линейных уравнений над GF(2) для степени больше единицы не работает: уравнение нелинейно по битам H.

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

Углубление: почему уникальность nonce — требование протокола, а не библиотеки

Библиотека не может проверить, что nonce уникален: она не знает, сколько сообщений уже зашифровано и не было ли перезапуска. Поэтому ответственность лежит на протоколе. Практические схемы:

• счётчик с гарантией монотонности (TLS: номер записи, ключи обновляются до переполнения);
• случайный nonce с оценкой вероятности коллизии по числу сообщений (2^32 сообщений при 96-битном nonce дают около 2^-33);
• SIV: тег вычисляется первым и становится IV, повтор nonce безвреден, но теряется параллелизм;
• разделение ключей по назначению: ошибка в одном домене не переносится на другой.

Правило, которое стоит запомнить: AEAD защищает от подделки только при выполнении своих предусловий. Предусловие GCM — уникальный nonce; нарушение предусловия превращает AEAD в поточный шифр с известным ключом аутентификации.

Лабораторная работа 6. Сломанный GCM

• Раздел курса: апокриф 6 «AEAD и режимы: сломанный GCM»

Введение

«Сейф» перешёл на AEAD: разработчик прочитал, что GCM даёт и шифрование, и целостность, и заменил CBC на AES-GCM. Nonce он вынес в константу модуля — «чтобы не плодить случайность». В результате сервис выдаёт одинаковые шифртексты для одинаковых сообщений, два разных сообщения дают два тега с одним и тем же E_K(J_0), а разность тегов позволяет восстановить ключ аутентификации H и подделать любое сообщение.

Работа собирает GCM по частям: умножение в GF(2^128), GHASH, тег. Затем — три атаки по возрастанию: восстановление второго сообщения при повторе nonce, восстановление H по двум тегам, подделка тега для изменённого текста. В продвинутой части — как проектировать так, чтобы повтор nonce был невозможен или безвреден.

Части: ядро GCM, повтор nonce, восстановление H, подделка тега, AAD и порядок проверки, продвинутая.

Цель работы

Научиться реализовывать AEAD-конструкцию и показывать, почему уникальность nonce — не пожелание, а условие стойкости.

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

• реализовывать умножение в GF(2^128) и GHASH и сверять GCM с библиотекой;
• показывать, что повтор nonce возвращает и конфиденциальность, и целостность к состоянию поточного шифра;
• восстанавливать ключ аутентификации H из двух тегов;
• подделывать тег для изменённого сообщения, не зная ключа шифрования;
• объяснять, зачем нужны AAD, порядок «тег, потом текст» и ротация ключей;
• формулировать требования к nonce для реального протокола.

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

Разделы «Что такое AEAD», «Конструкция GCM», «Повтор nonce: две атаки сразу», «Подделка тега», «Как проектировать правильно» апокрифа 6. Соотношения:

H = E_K(0^128)
GHASH: Y_i = (Y_(i−1) ⊕ X_i) · H
T = GHASH(H, AAD, C) ⊕ E_K(J_0)
C_1 ⊕ C_2 = P_1 ⊕ P_2            при повторe nonce
T_1 ⊕ T_2 = GHASH(H, AAD, C_1) ⊕ GHASH(H, AAD, C_2)

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

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

mkdir -p ~/lab-apocrypha-06 && cd ~/lab-apocrypha-06
unzip ~/lr-env.zip
cp gcm_core_template.py gcm.py
python3 check_aead.py

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

В журнал записывайте: совпадение с библиотекой, длину потока, который удалось восстановить, число блоков в сообщениях и формулу, которой подделан тег. Для каждой атаки — что именно утекло: открытый текст, H или целостность.

Часть 1. Ядро GCM

Задание

1. Реализуйте gf_mult по правилам GCM: 128 итераций, сдвиг вправо, редукция по R = 0xE1 << 120.
2. Реализуйте ghash и ghash_aad_ct: AAD, дополнение нулями, шифртекст, заключительный блок длин в битах.
3. Реализуйте gcm_encrypt и gcm_decrypt. Расшифрование обязано проверять тег до расшифрования и сравнивать его без ранних выходов.
4. Запустите python3 check_aead.py: шифртекст и тег должны совпасть с AESGCM из cryptography, испорченный тег — отвергаться.
5. Ответьте: почему H зависит только от ключа и почему это удобно атакующему при повторе nonce.
6. Объясните, что произойдёт, если в ghash_aad_ct забыть блок длин.

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

Совпадение с библиотекой на случайных данных, отказ на испорченном теге и понимание, что тег — линейная функция шифртекста при фиксированном H.

Часть 2. Повтор nonce и конфиденциальность

Задание

1. Изучите aead_service.py: nonce — константа, ключ создаётся при импорте.
2. Зашифруйте два сообщения одной длины и убедитесь, что одинаковые сообщения дают одинаковый шифртекст.
3. Реализуйте recover_keystream: ks = ct1 XOR pt1.
4. Реализуйте decrypt_with_keystream и восстановите второе сообщение.
5. Запустите python3 check_aead.py и посмотрите раздел «часть 2».
6. Ответьте: почему AEAD не спасает от повтора nonce в части конфиденциальности и чем это отличается от CBC с повторным IV.

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

Восстановленное второе сообщение и вывод: внутри AEAD работает поточный шифр, и повтор nonce возвращает его слабости.

Часть 3. Восстановление H

Задание

1. Возьмите два сообщения по одному блоку, зашифрованных одним nonce. Выпишите C_1, C_2, T_1, T_2.
2. Покажите, что при одинаковой длине сообщений блок длины L в GHASH сокращается и остаётся T_1 ⊕ T_2 = (C_1 ⊕ C_2) · H^2.
3. Реализуйте вычисление H^2 = (T_1 ⊕ T_2) · (C_1 ⊕ C_2)^{-1} в GF(2^128), а затем извлеките квадратный корень. В характеристике 2 корень единствен: H = (H^2)^(2^127), то есть 127 последовательных возведений в квадрат через уже написанное gf_mult; проверьте результат, возведя его в квадрат обратно.
4. Сверьте результат с aead_service.leak_auth_key() — в учебной работе это «дамп памяти», в реальной атаке он не нужен.
5. Для сообщений из нескольких блоков выпишите GHASH как полином по H степени, равной числу блоков, и решите уравнение о корнях: постройте полиномы для двух пар сообщений и возьмите их НОД над GF(2^128). Сравните стоимость с вариантом одного блока.
6. Ответьте: почему для восстановления H достаточно одного повтора nonce, а не «многих миллионов сообщений».

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

Восстановленный H, совпадающий с эталонным, и понимание, что уравнение на H решается алгебраически, а не перебором.

Часть 4. Подделка тега

Задание

1. Реализуйте forge_tag(gcm, h, aad, ct_old, tag_old, ct_new):

tag' = tag_old ⊕ GHASH(H, aad, ct_old) ⊕ GHASH(H, aad, ct_new)

2. Подделайте тег для сообщения, отличающегося от исходного, и проверьте aead_service.verify — сервис должен принять подделку.
3. Убедитесь, что старый тег для нового сообщения не подходит, а новый не совпадает со старым.
4. Запустите python3 check_aead.py: обе проверки части 3 должны пройти.
5. Ответьте: почему для подделки не нужен ключ шифрования и что именно проверяет сервер.

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

Принятая сервисом подделка и вывод: целостность держится на уникальности nonce, а не на стойкости AES.

Часть 5. AAD и порядок проверки

Задание

1. Добавьте в aead_service AAD — например, b"v=1;uid=42" — и проверьте, что изменение AAD ломает тег.
2. Соберите «неправильный» сервис, который сначала расшифровывает, потом проверяет тег, и показывает разные сообщения об ошибке. Опишите, какой оракул он создаёт.
3. Соберите «правильный»: сравнение тега константное по времени, единый ответ на любую ошибку, расшифрование только после проверки.
4. Сравните время работы обоих вариантов на испорченных тегах. Объясните, почему разница во времени — тоже утечка.
5. Ответьте: зачем AAD нужен, если он не шифруется, и что произойдёт, если заголовок протокола не входит в тег.

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

Работающий AAD, отвергающий подделку заголовка, и понимание, что порядок операций и единообразие ошибок — часть криптографического дизайна.

Часть 6. Продвинутая: как не повторять nonce

Задание

1. Реализуйте счётчик nonce: 4 байта идентификатора потока и 8 байт монотонного номера. Оцените, при каком объёме сообщений счётчик переполнится.
2. Реализуйте вывод ключей по назначению через HKDF: отдельные ключи для шифрования файлов, сессий и журналов. Покажите, что повтор nonce в одном домене не влияет на другой.
3. Разберите SIV: почему повтор nonce в нём безвреден, какова цена (два прохода, нет параллелизма).
4. Сформулируйте политику ротации: сколько сообщений на ключ, что делать при перезапуске процесса, где хранить счётчик.
5. Проведите ревью aead_service.py по чек-листу: nonce, порядок проверки, обработка ошибок, ротация, AAD.

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

Счётчик с оценкой переполнения, разделение ключей, разбор SIV и письменная политика ротации — то есть ответ на вопрос «как сделать так, чтобы этой работы больше не понадобилось».

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

Фиксируйте: длину сообщений, восстановленный H, формулу подделки, время выполнения атак. Провал проверки записывайте причиной — неверная редукция в gf_mult, потерян блок длин, перепутан порядок байт в теге, — а не отметкой «не получилось».

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

1. Что гарантирует AEAD и чего он не гарантирует?
2. Почему порядок «проверить тег, потом расшифровать» обязателен?
3. Как из ключа получается H и почему он один на все сообщения?
4. Что такое GHASH и почему он линеен по входу?
5. Почему повтор nonce ломает конфиденциальность?
6. Почему повтор nonce ломает целостность?
7. Как восстановить H по двум тегам для одного блока?
8. Сколько уравнений нужно для H при сообщении из n блоков?
9. Почему подделка тега не требует ключа шифрования?
10. Что даёт AAD и что будет, если заголовок не аутентифицирован?
11. Почему SIV устойчив к повтору nonce?
12. Какие требования к nonce в TLS 1.3 и как они обеспечиваются?