CBC-MAC

редактировать

В криптографии, код проверки подлинности сообщения цепочки блоков шифрования (CBC-MAC ) - это метод построения кода аутентификации сообщения из блочного шифра . Сообщение шифруется некоторым алгоритмом блочного шифрования в режиме CBC для создания цепочки блоков, так что каждый блок зависит от надлежащего шифрования предыдущего блока. Эта взаимозависимость гарантирует, что изменение любого из битов открытого текста приведет к изменению окончательного зашифрованного блока таким образом, который невозможно предсказать или противодействовать, не зная ключа к блочному шифру.

Чтобы вычислить CBC-MAC сообщения m, шифруют m в режиме CBC с нулевым вектором инициализации и сохраняют последний блок. На следующем рисунке показано вычисление CBC-MAC сообщения, содержащего блоки $m 1 ‖ m 2 ‖ ⋯ ‖ mx {\ displaystyle m_ {1} \ | m_ {2} \ | \ cdots \ | m_ {x }}$ $m_ {1} \ | m_ {2} \ | \ cdots \ | m_ {x}$ с использованием секретного ключа k и блочного шифра E:

Содержание

1 Безопасность с сообщениями фиксированной и переменной длины
- 1.1 Добавление длины
- 1.2 Encrypt-last-block
2 Методы атак
- 2.1 Использование одного и того же ключа для шифрования и аутентификации
- 2.2 Разрешение изменения вектора инициализации по значению
- 2.3 Использование предсказуемого вектора инициализации
3 Стандарты, определяющие алгоритм
4 См. Также
5 Ссылки

Безопасность с сообщениями фиксированной и переменной длины

Если используемый блочный шифр является безопасным (что означает, что это псевдослучайная перестановка ), то CBC -MAC безопасен для сообщений фиксированной длины. Однако сам по себе он небезопасен для сообщений переменной длины. Таким образом, любой единственный ключ должен использоваться только для сообщений фиксированной и известной длины. Это связано с тем, что злоумышленник, который знает правильные пары сообщение-тег (т.е. CBC-MAC) для двух сообщений $(m, t) {\ displaystyle (m, t)}$ ${\ displaystyle (m, t) }$ и $( m ′, t ′) {\ displaystyle (m ', t')}$ $(m',t')$ может генерировать третье сообщение $m ″ {\ displaystyle m ''} $ $m''$ , CBC-MAC которого также будет $t ′ {\ displaystyle t '}$ $t'$ . Это просто выполняется путем XOR первого блока $m ′ {\ displaystyle m '}$ $m'$ с t, а затем конкатенации m с этим измененным $m ′ {\ displaystyle m'}$ $m'$ ; т.е., сделав $m ″ = m ‖ [(m 1 ′ ⊕ t) ‖ m 2 ′ ‖… ‖ mx ′] {\ displaystyle m '' = m \ | [(m_ {1} '\ oplus t) \ | m_ {2} '\ | \ точки \ | m_ {x}']}$ $m''=m\|[(m_{1}'\oplus t)\|m_{2}'\|\dots \|m_{x}']$ . При вычислении MAC для сообщения $m ″ {\ displaystyle m ''} $ $m''$ следует, что мы вычисляем MAC для m обычным способом, как t, но когда это значение связывается с этап вычисления $EK MAC (m 1 ′ ⊕ t) {\ displaystyle E_ {K _ {\ text {MAC}}} (m_ {1} '\ oplus t)}$ $E_{K_{\text{MAC}}}(m_{1}'\oplus t)$ мы выполним операция исключающее ИЛИ со значением, полученным для MAC первого сообщения. Наличие этого тега в новом сообщении означает, что оно будет отменено, не оставив никакого вклада в MAC от блоков открытого текста в первом сообщении m: $EK MAC (m 1 ′ ⊕ t ⊕ t) = EK MAC ( м 1 ′) {\ displaystyle E_ {K _ {\ text {MAC}}} (m_ {1} '\ oplus t \ oplus t) = E_ {K _ {\ text {MAC}}} (m_ {1}') }$ $E_{K_{\text{MAC}}}(m_{1}'\oplus t\oplus t)=E_{K_{\text{MAC}}}(m_{1}')$ и, следовательно, тег для $m ″ {\ displaystyle m ''} $ $m''$ равен $t ′ {\ displaystyle t '}$ $t'$ .

Эту проблему нельзя решить добавив в конец блок размера сообщения. Существует три основных способа модификации CBC-MAC, чтобы он был безопасным для сообщений переменной длины: 1) Разделение ключей входной длины; 2) добавление длины; 3) Зашифровать последний блок. В таком случае также может быть рекомендовано использовать другой режим работы, например, CMAC или HMAC, для защиты целостности сообщений переменной длины.

Добавление длины

Одно из решений - включить длину сообщения в первый блок; Фактически, CBC-MAC оказался безопасным до тех пор, пока не использовались два сообщения, которые являются префиксами друг друга, а добавление длины в начале является частным случаем этого. Это может быть проблематично, если длина сообщения может быть неизвестна в начале обработки.

Encrypt-last-block

Encrypt-last-block CBC-MAC (ECBC-MAC) определяется как CBC-MAC-ELB (m, (k1, k2)) = E(k2, CBC-MAC (k1, m)). По сравнению с другими обсуждаемыми методами расширения CBC-MAC до сообщений переменной длины, encrypt-last-block имеет то преимущество, что не нужно знать длину сообщения до конца вычислений.

Вычисление CBC-MAC Encrypt-last-block.

Методы атаки

Как и во многих криптографических схемах, наивное использование шифров и других протоколов может привести к возможности атак, снижая эффективность криптографическая защита (или даже отказ от нее). Мы представляем атаки, которые возможны из-за неправильного использования CBC-MAC.

Использование одного и того же ключа для шифрования и аутентификации

Распространенной ошибкой является повторное использование одного и того же ключа k для шифрования CBC и CBC -MAC. Хотя повторное использование ключа для различных целей в целом является плохой практикой, в данном конкретном случае ошибка приводит к эффектной атаке:

Предположим, Алиса отправила Бобу блоки зашифрованного текста $C = C 1 ‖ C 2 ‖… ‖ C n {\ displaystyle C = C_ {1} \ | C_ {2} \ | \ dots \ | C_ {n}}$ ${\ Displaystyle C = C_ {1} \ | C_ {2} \ | \ точки \ | C_ {n}}$ . В процессе передачи Ева может подделать любой из $C 1,…, C n - 1 {\ displaystyle C_ {1}, \ dots, C_ {n-1}}$ $C_ {1}, \ dots, C_ {n-1}$ cipher- текстовые блоки и отрегулируйте любые биты в них по своему усмотрению, при условии, что последний блок, $C n {\ displaystyle C_ {n}}$ $C_ {n}$ , останется прежним. Мы предполагаем, для целей этого примера и без потери общности, что вектор инициализации, используемый для процесса шифрования, является вектором нулей.

Когда Боб получает сообщение, он сначала расшифровывает сообщение, обращая процесс шифрования, примененный Алисой, с использованием блоков зашифрованного текста. $C = C 1 ‖ C 2 ‖ ⋯ ‖ C n {\ displaystyle C = C_ {1} \ | C_ {2} \ | \ cdots \ | C_ {n}}$ ${\ displaystyle C = C_ {1} \ | C_ {2} \ | \ cdots \ | C_ {n}}$ . Подделанное сообщение, доставленное Бобу вместо оригинала Алисы, имеет вид $C ′ = C 1 ′ ‖… ‖ C n - 1 ′ ‖ C n {\ displaystyle C '= C_ {1}' \ | \ dots \ | C_ {n-1} '\ | C_ {n}}$ $C'=C_{1}'\|\dots \|C_{n-1}'\|C_{n}$ .

Боб сначала расшифровывает полученное сообщение, используя общий секретный ключ K, чтобы получить соответствующий простой текст. Обратите внимание, что весь создаваемый простой текст будет отличаться от того, который изначально послала Алиса, потому что Ева изменила все, кроме последнего блока зашифрованного текста. В частности, окончательный простой текст, $P n ′ {\ displaystyle P_ {n} '}$ $P_{n}'$ , отличается от исходного, $P n {\ displaystyle P_ {n}}$ $P_ {n}$ , которое прислала Алиса; хотя $C n {\ displaystyle C_ {n}}$ $C_ {n}$ то же самое, $C n - 1 ′ ≠ C n - 1 {\ displaystyle C_ {n-1} '\ not = C_ {n-1}}$ $C_{n-1}'\not =C_{n-1}$ , поэтому другой простой текст $P n ′ {\ displaystyle P_ {n} '}$ $P_{n}'$ создается при связывании предыдущего блока зашифрованного текста в исключающее ИЛИ после расшифровки $C n {\ displaystyle C_ {n}}$ $C_ {n}$ : $P n ′ = C n - 1 ′ ⊕ EK - 1 (C n) {\ displaystyle P_ {n} '= C_ {n-1} '\ oplus E_ {K} ^ {- 1} (C_ {n})}$ $P_{n}'=C_{n-1}'\oplus E_{K}^{-1}(C_{n})$ .

Отсюда следует, что Боб теперь будет вычислять тег аутентификации, используя CBC-MAC, по всем значениям открытого текста, которые он расшифровано. Тег для нового сообщения, $t ′ {\ displaystyle t '}$ $t'$ , задается следующим образом:

t ′ = EK (P n ′ ⊕ EK (P n - 1 ′ ⊕ EK (⋯ ⊕ EK (P 1 ')))) {\ displaystyle t' = E_ {K} (P_ {n} '\ oplus E_ {K} (P_ {n-1}' \ oplus E_ {K} (\ точки \ oplus E_ {K} (P_ {1} '))))}

t'=E_{K}(P_{n}'\oplus E_{K}(P_{n-1}'\oplus E_{K}(\dots \oplus E_{K}(P_{1}'))))

Обратите внимание, что это выражение равно

t ′ = EK (P n ′ ⊕ C n - 1 ′) {\ displaystyle t '= E_ {K} (P_ {n}' \ oplus C_ {n-1} ')}

t'=E_{K}(P_{n}'\oplus C_{n-1}')

что в точности равно $C n {\ displaystyle C_ {n}}$ $C_ {n}$ :

t ′ = EK ( С n - 1 ′ ⊕ EK - 1 (C n) ⊕ C n - 1 ′) = EK (EK - 1 (C n)) = C n {\ displaystyle t '= E_ {K} (C_ {n-1 } '\ oplus E_ {K} ^ {- 1} (C_ {n}) \ oplus C_ {n-1}') = E_ {K} (E_ {K} ^ {- 1} (C_ {n})) = C_ {n}}

t'=E_{K}(C_{n-1}'\oplus E_{K}^{-1}(C_{n})\oplus C_{n-1}')=E_{K}(E_{K}^{-1}(C_{n}))=C_{n}

и, следовательно, $t ′ = C n = t {\ displaystyle t '= C_ {n} = t}$ $t'=C_{n}=t$ .

Таким образом, Ева смогла изменить зашифрованный текст в пути (не обязательно зная, какому простому тексту оно соответствует), так что было создано совершенно другое сообщение, $P '{\ displaystyle P'}$ $P'$ , но тег для этого сообщения совпал с тегом оригинала, а Боб не известно, что содержимое было изменено во время транспортировки. По определению, код аутентификации сообщения нарушается, если мы можем найти другое сообщение (последовательность пар простого текста $P '{\ displaystyle P'}$ $P'$ ), которое создает тот же тег, что и предыдущее. сообщение, P, с $P ≠ P '{\ displaystyle P \ not = P'}$ $P\not =P'$ . Отсюда следует, что протокол аутентификации сообщения в этом сценарии использования был нарушен, и Боб был обманут, поверив, что Алиса отправила ему сообщение, которое она не создавала.

Если вместо этого мы используем разные ключи для этапов шифрования и аутентификации, скажем $K 1 {\ displaystyle K_ {1}}$ $K_ {1}$ и $K 2 {\ displaystyle K_ {2}}$ $K_ {2}$ , соответственно, эта атака предотвращена. Расшифровка измененных блоков зашифрованного текста $C i ′ {\ displaystyle C_ {i} '}$ $C_{i}'$ дает некоторую текстовую строку $P i ′ {\ displaystyle P_ {i}'}$ $P_{i}'$ . Однако из-за того, что MAC использует другой ключ $K 2 {\ displaystyle K_ {2}}$ $K_ {2}$ , мы не можем «отменить» процесс дешифрования на прямом этапе вычисления аутентификации сообщения. код, чтобы создать тот же тег; каждый измененный $P i ′ {\ displaystyle P_ {i} '}$ $P_{i}'$ теперь будет зашифрован с помощью $K 2 {\ displaystyle K_ {2}}$ $K_ {2}$ в CBC -MAC для некоторого значения $MAC i ≠ C i ′ {\ displaystyle \ mathrm {MAC} _ {i} \ not = C_ {i} '}$ $\mathrm {MAC} _{i}\not =C_{i}'$ .

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

Разрешение вектора инициализации изменяться по значению

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

При вычислении кода аутентификации сообщения, например, с помощью CBC-MAC, использование вектора инициализации является возможным вектором атаки.

При операции шифрования цепочки блоков зашифрованного текста первый блок простого текста смешивается с вектором инициализации с использованием исключающего ИЛИ ( $P 1 ⊕ IV {\ displaystyle P_ {1} \ oplus IV }$ $P_ {1} \ oplus IV$ ). Результатом этой операции является вход в блочный шифр для шифрования.

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

Если мы позволяем произвольно выбирать вектор инициализации, из этого следует, что первый блок простого текста потенциально может быть изменен (передан другое сообщение) при создании того же тега сообщения.

Рассмотрим сообщение $M 1 = P 1 | P 2 | … {\ Displaystyle M_ {1} = P_ {1} | P_ {2} | \ dots}$ $M_ {1} = P_ {1} | P_ {2} | \ dots$ . В частности, при вычислении тега сообщения для CBC-MAC предположим, что мы выбираем вектор инициализации $IV 1 {\ displaystyle IV_ {1}}$ $IV_ {1}$ так, что вычисление MAC начинается с $EK (IV 1 ⊕ P 1) {\ displaystyle E_ {K} (IV_ {1} \ oplus P_ {1})}$ $E_ {K} (IV_ {1 } \ oplus P_ {1})$ . Это создает пару (сообщение, тег) $(M 1, T 1) {\ displaystyle (M_ {1}, T_ {1})}$ $(M_{1},T_{1})$ .

Теперь создайте сообщение $M 2 = P 1 ′ | P 2 | … {\ Displaystyle M_ {2} = P_ {1} '| P_ {2} | \ dots}$ $M_{2}=P_{1}'|P_{2}|\dots$ . Для каждого бита, измененного в $P 1 ′ {\ displaystyle P_ {1} '}$ $P_{1}'$ , переверните соответствующий бит в векторе инициализации, чтобы получить вектор инициализации $IV 1 ′ {\ displaystyle IV_ {1} '}$ $IV_{1}'$ . Отсюда следует, что для вычисления MAC для этого сообщения мы начинаем вычисление с $EK (P 1 ′ ⊕ IV 1 ′) {\ displaystyle E_ {K} (P_ {1} '\ oplus IV_ {1}') }$ $E_{K}(P_{1}'\oplus IV_{1}')$ . Поскольку биты как в простом тексте, так и в векторе инициализации были перевернуты в одних и тех же местах, модификация отменяется на этом первом этапе, что означает, что ввод в блочный шифр идентичен вводу для $M 1 {\ displaystyle M_ {1 }}$ $M_ {1}$ . Если в обычный текст не вносятся дальнейшие изменения, будет получен тот же тег, несмотря на то, что передается другое сообщение.

Если свобода выбора вектора инициализации удалена и все реализации CBC-MAC фиксируются на определенном векторе инициализации (часто вектор нулей, но теоретически это может быть что угодно, если все реализации согласны), эта атака не может продолжаться.

Итак, если злоумышленник может установить IV, который будет использоваться для проверки MAC, он может выполнить произвольную модификацию первого блока данных без аннулирования MAC.

Использование предсказуемого вектора инициализации

Иногда IV используется в качестве счетчика для предотвращения атак повторного воспроизведения сообщений. Однако, если злоумышленник может предсказать, какой IV будет использоваться для проверки MAC, он или она может воспроизвести ранее наблюдаемое сообщение, изменив первый блок данных, чтобы компенсировать изменение IV, которое будет использоваться для проверки. Например, если злоумышленник заметил сообщение $M 1 = P 1 | P 2 | … {\ Displaystyle M_ {1} = P_ {1} | P_ {2} | \ dots}$ $M_ {1} = P_ {1} | P_ {2} | \ dots$ с $IV 1 {\ displaystyle IV_ {1}}$ $IV_ {1}$ и знает $IV 2 {\ displaystyle IV_ {2}}$ ${\ displaystyle IV_ {2}}$ , он может произвести $M 1 ′ = (P 1 ⊕ IV 1 ⊕ IV 2) | P 2 | … {\ Displaystyle M_ {1} '= (P_ {1} \ oplus IV_ {1} \ oplus IV_ {2}) | P_ {2} | \ dots}$ $M_{1}'=(P_{1}\oplus IV_{1}\oplus IV_{2})|P_{2}|\dots$ , который пройдет проверку MAC с помощью $IV 2 {\ displaystyle IV_ {2}}$ ${\ displaystyle IV_ {2}}$ .

Простейшая контрмера - зашифровать IV перед его использованием (то есть добавить IV к данным). В качестве альтернативы можно использовать MAC в режиме CFB, потому что в режиме CFB IV зашифровывается до того, как он подвергнется операции XOR с данными.

Другое решение (в случае, если защита от атак повторного воспроизведения сообщений не требуется) - всегда использовать нулевой вектор IV. Обратите внимание, что приведенная выше формула для $M 1 ′ {\ displaystyle M_ {1} '}$ $M_{1}'$ становится $M 1 ′ = (P 1 ⊕ 0 ⊕ 0) | P 2 | ⋯ = P 1 | P 2 | ⋯ знак равно M 1 {\ Displaystyle M_ {1} '= (P_ {1} \ oplus 0 \ oplus 0) | P_ {2} | \ dots = P_ {1} | P_ {2} | \ dots = M_ {1 }}$ $M_{1}'=(P_{1}\oplus 0\oplus 0)|P_{2}|\dots =P_{1}|P_{2}|\dots =M_{1}$ . Итак, поскольку $M 1 {\ displaystyle M_ {1}}$ $M_ {1}$ и $M 1 ′ {\ displaystyle M_ {1} '}$ $M_{1}'$ по определению являются одним и тем же сообщением у них будет одинаковый тег. Это не подделка, а предполагаемое использование CBC-MAC.

Стандарты, определяющие алгоритм

FIPS PUB 113 Аутентификация компьютерных данных (теперь устаревшая) США государственный стандарт, который определяет алгоритм CBC-MAC с использованием DES в качестве блочного шифра.

Алгоритм CBC-MAC эквивалентен ISO / IEC 9797-1 MAC-алгоритм 1.

См. Также

CMAC - блочный шифр –Основанный алгоритм MAC, который является безопасным для сообщений различной длины (рекомендуется NIST ).
OMAC и PMAC - Другие методы преобразования блочных шифров в коды аутентификации сообщений (MAC).
Функция одностороннего сжатия - хеш-функции могут быть созданы из блочных шифров. Но обратите внимание, есть существенные различия в функциях и использовании для обеспечения безопасности между MAC (например, CBC-MAC) и хеши.

Ссылки