Апокриф 05

Блочные шифры: ECB, CBC и padding oracle

Блочные шифры: ECB, CBC и padding oracle

Блочный шифр сам по себе умеет ровно одно: превратить шестнадцать байт в шестнадцать байт и обратно. Всё остальное — режим работы. Режим решает, как связать блоки, откуда взять случайность и что произойдёт, если противник изменит один байт. Тема показывает, что слабость почти никогда не сидит в AES: она сидит в том, как его вызвали.

Разбор идёт по возрастанию сложности. Сначала ECB, где одинаковые блоки открытого текста дают одинаковые блоки шифртекста, и отсюда сразу следуют две атаки: распознавание структуры данных и перестановка блоков. Потом CBC, где цепочка прячет повторы, но добавляет предсказуемую реакцию на изменение предыдущего блока. Кульминация — оракул дополнения: сервер, который на неверное дополнение отвечает одним битом «ошибка», позволяет расшифровать весь токен без ключа. Это одна из самых разрушительных ошибок проектирования в веб-приложениях, и она до сих пор встречается в самописных форматах.

Что такое режим работы

Блочный шифр как перестановка

AES с ключом K — перестановка на множестве 128-битных блоков: E_K: {0,1}^128 → {0,1}^128. Она детерминирована: один и тот же блок при одном ключе всегда даёт один и тот же результат. Это не недостаток шифра, а его определение, и именно это свойство режимы обязаны нейтрализовать.

Сообщение произвольной длины разбивается на блоки, при необходимости дополняется по схеме PKCS#7 (k байт со значением k, где 1 ≤ k ≤ 16), и каждый блок шифруется. Способ, которым режим связывает блоки и вносит случайность, определяет и стойкость, и цену.

Свойства, которые нужны режиму

Хороший режим даёт три вещи: разные шифртексты для одинаковых сообщений (рандомизация через IV, nonce или счётчик), отсутствие утечки структуры (блоки не должны повторяться там, где повторяется открытый текст) и, в идеале, обнаруживаемую целостность. Последнее режим шифрования сам по себе не даёт: ECB, CBC и CTR конфиденциальны, но не аутентифицированы, и это источник большинства атак темы.

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

ECB: детерминированность и её последствия

Одинаковые блоки видны

В режиме ECB каждый блок шифруется независимо: C_i = E_K(P_i). Одинаковые 16-байтовые фрагменты открытого текста дают одинаковые блоки шифртекста. Если данные имеют структуру — изображение, таблица, повторяющиеся поля, — она проступает сквозь шифрование.

Канонический пример — «ECB-пингвин»: изображение, зашифрованное ECB, сохраняет контуры, потому что области с одинаковым цветом состоят из одинаковых блоков 8. На рисунке 1 показано, как повторяющиеся блоки складываются в узнаваемый силуэт.

Повторяющиеся блоки в ECB
Рисунок 1. ECB: одинаковые блоки открытого текста дают одинаковые блоки шифртекста, и структура данных видна

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

Перестановка блоков

Второе следствие — блоки можно тасовать и склеивать. Если приложение шифрует структуру вида email=<адрес>&uid=10&role=user, противник не знает ключ, но может собрать токен из кусков чужих токенов. Это атака «вырезать и вставить»: подбираются два адреса так, чтобы нужные поля оказались на границах блоков, после чего блок с admin переносится в конец другого токена.

Атака работает без ключа и без оракула, потому что ECB не связывает блоки между собой: каждый блок действителен сам по себе. Пошаговые учебные задачи на эту схему собраны в наборе Cryptopals 6. Защита — либо AEAD, либо связывание блоков (CBC с MAC), либо контроль целостности на уровне протокола.

CBC: цепочка и её цена

Как устроена цепочка

В CBC каждый блок открытого текста складывается с предыдущим шифртекстом и только потом шифруется: C_i = E_K(P_i ⊕ C_{i-1}), где C_0 = IV. Одинаковые блоки открытого текста дают разные шифртексты, структура скрыта, а IV должен быть случайным и непредсказуемым 1.

Обратная операция: P_i = D_K(C_i) ⊕ C_{i-1}. Из этой формулы видно главное свойство: изменение байта в C_{i-1} предсказуемо меняет соответствующий байт P_i, а сам C_i при этом остаётся валидным. Целостности нет — есть предсказуемость.

Бит-флиппинг в CBC

Пусть противник знает открытый текст блока i и хочет заменить role=user на role=admin. Он вычисляет Δ = P_i ⊕ P_i' и накладывает Δ на C_{i-1}. После расшифрования блок i станет желаемым, а блок i-1 превратится в мусор — часто это приемлемая цена, особенно если мусор попадает в поле, которое не проверяется. На рисунке 2 показано, какие блоки портятся.

Изменение предыдущего блока в CBC
Рисунок 2. Правка C(i−1) меняет P(i) предсказуемо; P(i−1) при этом разрушается

Для первого блока роль предыдущего играет IV: если IV передан вместе с шифртекстом и не проверяется, его можно менять так же свободно. Отсюда правило: IV аутентифицируется вместе с данными, иначе он не отличается от ещё одного блока шифртекста.

Оракул дополнения

Идея атаки

Сервер, который после расшифрования проверяет дополнение PKCS#7, знает больше, чем говорит: он различает «дополнение верное» и «дополнение неверное». Если эта разница видна снаружи — кодом ответа, текстом ошибки, временем, — возникает оракул. Ваденай доказал, что одного бита достаточно для полного восстановления открытого текста 2.

Механика опирается на формулу P_i = D_K(C_i) ⊕ C_{i-1}. Противник не может вычислить D_K(C_i), но может подставлять разные C_{i-1} и спрашивать: «дополнение верное?». Перебирая последний байт предыдущего блока, он находит значение, при котором последний байт открытого текста равен 0x01, — это единственный случай, когда дополнение из одного байта верно. Отсюда D_K(C_i) в последней позиции, а значит, и байт открытого текста.

Дальше — итеративно: зафиксировав последний байт как 0x02, перебирается предпоследний, потом 0x03, и так до начала блока. В среднем около 128 запросов на байт, то есть примерно 2000–4000 на блок; для токена из трёх блоков это несколько тысяч запросов и несколько секунд. На рисунке 3 — схема шага.

Шаг атаки на оракул дополнения
Рисунок 3. Перебор байта C(i−1) до верного дополнения: найденный байт раскрывает байт D(C(i))

Разновидности и реальные инциденты

Оракул не обязан быть явным. POODLE (2014) использовал различие в реакции на дополнение в SSL 3.0 и позволял постепенно раскрывать cookie 3. Lucky13 (2013) эксплуатировал разницу во времени вычисления MAC в TLS 4. В ASP.NET ошибка обработки дополнения (CVE-2010-3332) давала оракул через коды ответа и позволяла читать и подделывать аутентификационные cookie 5.

Общее у всех случаев: разработчик считал, что «сообщение об ошибке дополнения» — безобидная диагностика, а на деле это канал утечки. Защита: не различать причины отказа, использовать AEAD, проверять MAC до расшифрования (encrypt-then-MAC), а для CBC — константное по времени сравнение и единый ответ на любую ошибку.

Почему оракул так опасен

Стойкость AES здесь ни при чём: ключ не перебирается и не компрометируется. Утекает не ключ, а функция расшифрования, доступная по одному биту за запрос. Это иллюстрация общего принципа: криптографическая система ломается на стыке примитива и протокола, а не в примитиве.

CTR и почему это не выход

CTR превращает блочный шифр в поточный: C_i = P_i ⊕ E_K(T_i), где T_i — счётчик. Он параллелится, не требует дополнения и не распространяет ошибку дальше одного блока. Но у него те же две болезни, что у поточного шифра: изменение бита шифртекста меняет тот же бит открытого текста, а повтор счётчика с тем же ключом даёт повтор потока. Дополнения нет, поэтому оракула дополнения нет, но есть побитовая подмена и повтор nonce.

Именно поэтому CTR и CBC в современном виде почти всегда используются внутри AEAD: сравнение режимов по свойствам, включая изменяемость, есть у Рогавея 7: GCM = CTR + GHASH, CCM = CTR + CBC-MAC. Конфиденциальность обеспечивает режим, целостность — отдельная конструкция, и проверка целостности должна происходить до того, как открытый текст попадёт в разбор полей.

Требования к IV и nonce по режимам

Сводка, к которой стоит возвращаться при выборе режима: требования разные, и «случайный IV» — не универсальный ответ.

РежимТребование к IV/nonceЧто ломается при нарушении
CBCнепредсказуемый, лучше случайныйпредсказуемый IV даёт атаку с адаптивным выбором открытого текста (BEAST)
CFB, OFBуникальный для ключаповтор даёт повтор потока и восстановление XOR открытых текстов
CTRуникальный счётчик, предсказуемость допустимаповтор счётчика — повтор потока, побитовая подмена
GCMуникальный nonce (96 бит)повтор ломает и конфиденциальность, и целостность (восстановление H)
ChaCha20-Poly1305уникальный nonce (96 бит)повтор nonce — та же катастрофа, что в GCM
AES-GCM-SIVnonce может повторяться (best effort)повтор приводит к раскрытию равенства сообщений, но не ключа

Ключевая мысль: CBC требует непредсказуемости, CTR и AEAD — уникальности. Это разные свойства, и режим, стойкий при случайном IV, может быть катастрофически нестойким при счётчике, который сбрасывается после перезапуска.

Итоги темы

  • Блочный шифр детерминирован; режим обязан добавить рандомизацию и связывание.
  • ECB не скрывает структуру и позволяет переставлять блоки; атака «вырезать и вставить» не требует ключа.
  • CBC скрывает повторы, но предсказуемо реагирует на изменение предыдущего блока; IV — часть шифртекста и должен аутентифицироваться.
  • Один бит информации о дополнении даёт полное восстановление открытого текста; оракул может быть в коде ответа, тексте ошибки или времени.
  • CTR наследует свойства поточного шифра: побитовая подмена и повтор счётчика.
  • Лечение общее: AEAD, encrypt-then-MAC, единообразные ошибки, константное время.

Литература

  1. NIST. SP 800-38A: Recommendation for Block Cipher Modes of Operation. 2001. — режимы ECB, CBC, CFB, OFB, CTR и их тестовые векторы.
  2. Vaudenay S. Security Flaws Induced by CBC Padding — Applications to SSL, IPSEC, WTLS. EUROCRYPT 2002. — исходная работа об оракуле дополнения.
  3. Möller B., Duong T., Kotowicz A. This POODLE Bites: Exploiting the SSL 3.0 Fallback. 2014. — атака на дополнение в SSL 3.0.
  4. AlFardan N., Paterson K. Lucky Thirteen: Breaking the TLS and DTLS Record Protocols. IEEE S&P 2013. — тайминговая атака на CBC-MAC в TLS.
  5. Microsoft. MS10-070: Vulnerability in ASP.NET Could Allow Information Disclosure. 2010. — оракул дополнения в ASP.NET.
  6. Cryptopals Crypto Challenges. Set 2, challenges 9–16. — учебные задачи на PKCS#7, CBC и cut-and-paste.
  7. Rogaway P. Evaluation of Some Blockcipher Modes of Operation. 2011. — сравнение режимов по свойствам, включая malleability.
  8. Lucas P. ECB Penguin. 2011. — наглядная демонстрация утечки структуры изображения в ECB.