CBC-MAC

В криптографии, CBC MAC является технологией построения аутенфикационного кода сообщения из блочного шифра. Сообщение шифруется при помощи некоторого блочного алгоритма шифрования в режиме CBC, для создания цепочки блоков с правилом — каждый блок зависит от надлежащего(верного) шифрования предыдущего. Эта взаимозависимость гарантирует, что изменение в любом бите открытого текста приведёт к изменению конечного зашифрованного блока в сторону, которая не может быть предсказана или высчитана в случае, если ключ блочного шифра не известен. Использовался (с подстановкой в качестве E алгоритма DES) как государственный стандарт США — DAA.

Справочная информация

Алгоритм CBC MAC является хорошо известным методом для генерации имитовставки (имитовставка, англ. message authentication code — код аутентичности сообщения), основанный на блочном шифре. Bellare, Kilian и Rogaway доказали безопасность (защищённость) алгоритма при фиксированной длине сообщения в m*n бит, где n — длина базового блочного шифра Е. Однако, хорошо известно, что CBC MAC не является безопасным, если длина сообщения не является фиксированной. Таким образом, было предложено несколько вариантов алгоритма для варьируемой длины сообщения. Сначала была предложена зашифрованная имитовставка(EMAC). Она получается шифрованием CBC MAC значения с помощью E и новым ключом $K^2$. То есть $EMAC_{K_1,K_2}(M) = E_{K_2}(CBC_{K_1}(M)))$, где M — сообщение, $K_1$ — ключ CBC MAC и $CBC_{K_1}(M)$ — значение CBC MAC сообщения М. Petrank и Rackoff позже доказали, что EMAC защищён, если длина сообщения кратна n (Vaudenay используя декорреляционную теорию, опубликовал другое доказательство). Однако, EMAC требует два ключевых расписания базового блочного шифра E. Далее Black и Rogaway предложили XCBC, который требует только одного ключевого расписания базового блочного шифра E. XCBC даёт три ключа: один ключ блочного шифра K1, и два ключа по n бит. XCBC описывается следующей схемой

На таблице приведено сравнение длин ключей.

	XCBC	TMAC	OMAC
Длина ключа	(k + 2n) бит	(k + n) бит	k бит

Если $\left | M \right | = mn$ для некоторого m > 0, то XCBC вычисляется в точности, как и CBC MAC, за исключением операции XOR(«исключающее или») ключа $K_2$ (n бит) до шифрования последнего блока.

В противном случае, $\ 10^i$ (где $i = n-1-\left | M \right | \mod \ n$) добавляется к М и XCBC вычисляется в точности, как и CBC MAC для полученного сообщения. За исключением операции XOR другого ключа $K_3$(n бит) до шифрования последнего блока. Однако, недостатком XCBC заключается в требовании трёх ключей, то есть в сумме (k + 2n) бит. В итоге, Kurosawa и Iwata предложили двуключевой CBC MAC (TMAC). TMAC принимает два ключа, в сумме (k + n) бит: ключ $K_1$ блочного шифра и ключ $K_2$ (n бит). TMAC получается из XCBC перемещением (или заменой) $\ (K_2,K_3)$ на $(K_2 \cdot u,K_2)$, где u — некоторая ненулевая константа, а «•» обозначает умножение в $\ GF(2^n)$. Как уже было сказано, OMAC (one-key CBC MAC) принимает только один ключ К блочного шифра Е. Длина ключа, k бит, минимальна, так как базовый шифр должен содержать ключ K, состоящий из k бит в любом случае.

OMAC

OMAC является родительским названием для OMAC1 и OMAC2. OMAC1 получается из XCBC с помощью замены $\ (K_2,K_3)$ на $(L \cdot u, L \cdot u^2)$ для некоторой не равной нулю константе u в $\ GF(2^n)$, где L — даётся с помощью следующего выражения: $L \ = \ EK( 0 ^ n )$. OMAC2 аналогично получается используя $(L \cdot u, L \cdot u^{-1})$. Мы можем вычислть $(L \cdot u)$, $(L \cdot u^{-1})$ и $(L \cdot u^2) = \{(L \cdot u) \cdot u\}$ эффективно одним сдвигом и условием XOR на $\ L$ и $(L \cdot u)$, соответственно. OMAC1 (соотв. OMAC2) описывается следующей схемой:

1. Если $\left | M \right | = mn$ для некоторого m > 0, тогда OMAC вычисляется в точности, как CBC MAC, за исключением операции XOR для $(L \cdot u)$ до шифрования последнего блока.
2. В противном случае, $\ 10^i$ (где $i = n-1-\left | M \right | \mod \ n$) добавляется к M и OMAC Вычисляется в точности, как CBC MAC для полученного сообщения М, за исключением операции XOR для $(L \cdot u^2)$(соотв. $(L \cdot u^{-1})$ до шифрования последнего блока.

Кроме того, в TMAC, ключ $K_2$ является частью ключа, в то время как в OMAC, L не является частью ключа и генерируется из K. Эта сохранность длины ключа делает доказательство безопасности OMAC значительно сложнее чем для TMAC, как показано ниже. На рисунке 2, пусть M[1] = $0^n$. Тогда L является выходом первого $E_K$. L всегда появляется снова в последнем блоке. В основном, подобное повторное использование L могло бы привести к тупику в доказательстве безопасности. (В OCB режиме и PMAC, $L = EK(0^n)$ так же используется как ключ универсальной хэш-функции. Однако L появляется как выход некоторого внутреннего блока с незначительной вероятностью.) Тем не менее, мы доказали, что OMAC является таким же защищённым как и XCBC, где анализ безопасности является образцом абсолютной защищённости [1]. Дальнейший OMAC получил все другие положительные свойства, которыми были наделены XCBC (и TMAC). Таким образом, область OMAC — {0,1}, необходимо одноключевое расписание базового блочного шифра E и $\max\{1,[\left|M\right|/n]\}$ блочно-шифровых вызовов(обращений).

Обозначения

Для набора A, x←A означает, что x выбирается из A случайно, причём выбор любого значения из набора А является равновероятным. Если a, b (∈ {0, 1}*) равновеликие строки, тогда a ⊕ b является их побитовой операцией XOR. Если a, b (∈ {0, 1}*) не равновеликие строки, то a ◦ b обозначает их конкатенацию. (Для упрощения далее вводится обозначение: ab:= a ◦ b). Для n-битной строки $a = a_{n-1} ... a_1a_0$ ∈ {0, 1}*, обозначим $a$ << 1 = $a_{n-2}...a_1a_00$ n-битную строку, которая сдвинута влево на 1 бит, в это же время обозначим a >> 1 = $0a_{n-1} ... a_2a_1$ n-битную строку, которая сдвинута вправо на один бит. Если a ∈ {0, 1}* является строкой, то |a| обозначим её битовую длину. Для любого бита строка a ∈ {0, 1}* такова что |a| ≤ n, положим что
$(1) \ pad_n(a) = \begin{cases} & \ a10^{n-\left| a \right|-1}, \ if \left| a \right|<n,\\ & \ a, \ if \left| a \right|= n. \end{cases}$
Определим $\left \| a \right \|_n = max\{1, [\left|a\right|/n]\}$, где пустая строка считается как один блок.

CBC MAC

Блочный шифр Е является функцией Е : $K_E$ × $\{0, 1\}^n$ → $\{0,1\}^n$, где каждое E(K, •) = EK(•) является перестановкой $\{0,1\}^n$, в свою очередь $K_E$ является набором всевозможных ключей, а n — длина блока. CBC MAC [6, 7] является наипростейшим и наиболее известным алгоритмом, для того что бы сделать MAC из блочного шифра Е. Пусть сообщение будет иметь вид M = M[1] ◦M[2] ◦ … ◦M[m], где |M[1]| = |M[2]| = … = |M[m]| = n. Тогда CBCK(M), CBC MAC сообщения M при условии ключа K, определяется как Y [m], где Y [i] = EK(M[i] ⊕ Y [i − 1]) для i = 1, … ,m и Y [0] = $0^n$. Bellare, Kilian и Rogaway доказали безопасность CBC MAC для фиксированной длины сообщения в mn бит.

Поле с $2^n$ точками

Мы вправе рассматривать точку a в $GF(2^n)$ любым из следующих способов: (1) как абстрактная точка в поле а; (2) как n-битную строку $a_{n-1} ... a_1a_0$ ∈ $\{0, 1\}^n$; (3) как формальный полином $a(u) = a_{n-1}u^{n-1}+ ... +a_1u + a_0$ с бинарными коэффициентами. Для того что бы добавить 2 точки в $GF(2^n)$, рассмотрим битовую операцию ХOR над ними. Обозначим эту операцию с помощью a ⊕ b. Для того что бы перемножить две точки, зафиксируем некоторый полином f(u) с бинарными коэффициентами и степенью n. Для большей точности, выберем лексикографически первым полином среди таких же полиномов степени n имеющий минимальное число коэффициентов. Перечислим некоторые из указанных полиномов
$\ f(u) = u^{64} + u^4 + u^3 + u + 1$ для n = 64,
$\ f(u) = u^{128} + u^7 + u^2 + u + 1$ для n = 128, и
$\ f(u) = u^{256} + u^{10} + u^5 + u^2 + 1$ для n = 256.
Для того, что бы перемножить две точки a ∈ $GF(2^n)$ и b ∈ $GF(2^n)$, рассмотрим a и b как полиномы $a(u) = a_{n-1}u^{n-1} + ... + a_1u + a_0$ и $b(u) = b_{n-1}u^{n-1} + ... + b_1u + b_0$, результат операции c(u), где коэффициенты в GF(2) прибавляются и умножаются, и берётся остаток отделения c(u) на f(u). Кроме того особенно просто умножить точку a ∈ $\{0, 1\}^n$ на u. Например, если n = 128,
$(2) \ a \cdot u = \begin{cases} & \ a\ll 1 \ if \ a_{127} = 0, \\ & \ (a\ll 1)\oplus 0^{120}10000111 \ otherwise. \end{cases}$
Также, просто разделить точку a ∈ $\{0, 1\}^n$ на u, имея ввиду, что а умножается на обратную величину u в поле: $a \cdot u^{-1}$. Например,
$(3) \ a \cdot u = \begin{cases} & \ a\gg 1 \ if \ a_{0} = 0, \\ & \ (a\gg 1)\oplus 0^{120}10000111 \ otherwise. \end{cases}$

Основная конструкция семейства ОМАС

Семейство ОМАС определяется блочным шифром Е : KE × $\{0, 1\}^n$ → $\{0, 1\}^n$, n-битной константой Cst, универсальной хэш-функцией H : $\{0, 1\}^n$ × X → $\{0, 1\}^n$, и две уникальных константы $Cst_1$, $Cst_2$ ∈ X, где X является конечной областью функции H. H, $Cst_1$ и $Cst_2$ должны удовлетворять следующему условию: (константы являются случайными. Запишем HL(•) для H(L, •).

1. Для любого y ∈ $\{0, 1\}^n$, число L ∈ $\{0, 1\}^n$ таково, что HL($Cst_1$) = y не более чем $\epsilon_1 \cdot 2^n$ для некоторого достаточно малого $\epsilon_1$.
2. Для любого y ∈ $\{0, 1\}^n$, число L ∈ $\{0, 1\}^n$ таково, что HL($Cst_2$) = y не более чем $\epsilon_2 \cdot 2^n$ для некоторого достаточно малого $\epsilon_2$.
3. Для любого y ∈ $\{0, 1\}^n$, число L ∈ $\{0, 1\}^n$ таково, что HL($Cst_1$) ⊕ HL($Cst_2$) = y не более чем $\epsilon_3 \cdot 2^n$ для некоторого достаточно малого $\epsilon_3$.
4. Для любого y ∈ $\{0, 1\}^n$, число L ∈ $\{0, 1\}^n$ таково, что HL($Cst_1$) ⊕L = y не более чем $\epsilon_4 \cdot 2^n$ для некоторого достаточно малого $\epsilon_4$.
5. Для любого y ∈ $\{0, 1\}^n$, число L ∈ $\{0, 1\}^n$ таково, что HL($Cst_2$) ⊕L = y не более чем $\epsilon_5 \cdot 2^n$ для некоторого достаточно малого $\epsilon_5$.
6. Для любого y ∈ $\{0, 1\}^n$, число L ∈ $\{0, 1\}^n$ таково, что HL($Cst_1$) ⊕ HL(Cst2) ⊕ L = y не более чем $\epsilon_6 \cdot 2^n$ для некоторого достаточно малого $\epsilon_6$.

Далее приведём пседвдокод, который описывает семейство OMAC.

Algorithm $OMAC-family_K(M)$
L ← $E_K(Cst)$;
Y [0] ← $0^n$;
Partition M into M[1] ... M[m]
for i ← 1 to m − 1 do
X[i] ← M[i] ⊕ Y [i − 1];
Y [i] ← $E_K(X[i]$);
X[m] ← $pad_n(M[m]$) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ $H_L(Cst_1)$;
else X[m] ← X[m] ⊕ $H_L(Cst_2)$;
T ← $E_K(X[m]$);
return T;


Алгоритм семейства ОМАС проиллюстрирован на Рис.3, где $pad_n$(•) определяется в (1). Пространство ключей К семейства ОМАС: $K = K_E$. Оно принимает значения ключа K ∈ $K_E$ и сообщение M ∈ {0, 1}*, и возвращает строку из области $\{0, 1\}^n$.

Предложенная спецификация

В OMAC1 положим Cst = $0^n$, $H_L$(x) = L•x, $Cst_1$ = u и $Cst_2$ = $u^2$, где «•» означает умножение в $GF(2^n)$. $L = E_K(0^n)$, $H_L(Cst_1) = L \cdot u$ и $H_L(Cst_2) = L \cdot u^2$ равносильны. OMAC2 аналогичен OMAC1, исключая $Cst_2 = u^{-1}$ вместо $Cst_2 = u^2$. $L = E_K(0^n)$, $H_L(Cst_1) = L \cdot u$ и $H_L(Cst_2) = L \cdot u^{-1}$ равносильны. Кроме того, $L \cdot u$, $L \cdot u^{-1}$ и $L \cdot u^2 = (L \cdot u) \cdot u$ могут быть эффективно вычислены с помощью одного сдвига и одной операции XOR от $L$ и $L \cdot u$, соответственно как показано в (2) и (3). Легко заметить, что условия в Sec. 3 выполняются для $\epsilon_1 = ... = \epsilon_6 = 2-n$ в OMAC1 и OMAC2. OMAC1 и OMAC2 проиллюстрированы на Рис.2 и описываются следующим образом:
1. Для OMAC1:

Algorithm $OMAC1_K(M)$
L ← $E_K(0^n)$;
Y [0] ← $0^n$;
Partition M into M[1] ... M[m]
for i ← 1 to m − 1 do
X[i] ← M[i] ⊕ Y [i − 1];
if |M[m]| = n
then X[m] ← X[m] ⊕ $L \cdot u$;
else Y[i] ← E_k(X[i]);
X[m] ← $pad_n(M[m]$) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ $L \cdot u$;
else X[m] ← X[m] ⊕ $L \cdot u^2$;
T ← $E_K(X[m]$);
return T;


1. Для OMAC2:

Algorithm $OMAC2_K(M)$
L ← $E_K(0^n)$;
Y [0] ← $0^n$;
Partition M into M[1] ... M[m]
for i ← 1 to m − 1 do
X[i] ← M[i] ⊕ Y [i − 1];
if |M[m]| = n
then X[m] ← X[m] ⊕ $L \cdot u$;
else Y[i] ← E_k(X[i]);
X[m] ← $pad_n(M[m]$) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ $L \cdot u$;
else X[m] ← X[m] ⊕ $L \cdot u^{-1}$;
T ← $E_K(X[m]$);
return T;


Безопасность семейства OMAC

Определение защищённости

Пусть Perm(n) означает набор всех перестановок из $\{0, 1\}^n$, так же пусть P является случайной перестановкой, если Р — случайная выборка из Perm(n). Безопасность блочного шифра E может быть количественно определена как $Adv^{prp}_E(t, q)$, максимальное преимущество, которое противник A может получить, когда пытается выделить $E_K( \cdot )$ (со случайно выбранным ключём K) из случайной перестановки P(•), когда допускается вычисление времени t и q запросов (который является либо $E_K(\cdot)$ либо $P(\cdot)$). Это преимущество определяется следующим образом.
$\begin{cases} & Adv^{prp}_E(A):= \left|Pr(K\overset{R}{\leftarrow}K_E : A^{E_K(\cdot)} = 1) - Pr((K\overset{R}{\leftarrow}Perm(n):A^{P(\cdot)} = 1)\right| \\ & Adv_E^{prp}(t,q) := max\{Adv^{prp}_E(A)\} \end{cases}$
Скажем, что блочный шифр E — защищён, если существенно мало. Аналогично, MAC-алгоритм — F : $K_F$ × $\{0, 1\}^n$ → $\{0, 1\}^n$, где $K_F$ — набор ключей, тогда запишем $F_K(\cdot)$ для F(K, •). Скажем, что противник $A^{F_K(\cdot)}$ взламывает, если A выдаёт $(M,F_K(M))$, где A никогда не запрашивает M из $F_K(\cdot)$. Тогда мы определяем преимущество как

$\begin{cases} & Adv^{mac}_E(A):= \Pr(K\overset{R}{\leftarrow}K_F : A^{F_K(\cdot)} forges) \\ & Adv_E^{mac}(t,q,\mu) := max\{Adv^{mac}_F(A)\} \end{cases}$

где максимум берётся по всем противникам, кто «работает» не мобее времени t, производит не более q запросов, и кадлый запрос не более μ бит. Будем говорить, MAC алгоритм защищён (безопасен), если величина пренебрежимо мала. Обозначим Rand(∗, n) набор всех функций из {0, 1}* в $\{0, 1\}^n$. Этот набор даётся вероятностной мерой в предположении, что случайный элемент R набора Rand(∗, n) связан или ассоциирован с каждой строкой M ∈ {0, 1}* случайной строки R(M)∈$\{0, 1\}^n$. Далее, мы определим преймущество как
$\begin{cases} & Adv^{viprf}_F(A):= \left|Pr(K\overset{R}{\leftarrow}K_F : A^{F_K(\cdot)} = 1) - Pr((K\overset{R}{\leftarrow}Rand(*,n):A^{R(\cdot)} = 1)\right| \\ & Adv_F^{viprf}(t,q,\mu) := max\{Adv^{viprf}_F(A)\} \end{cases}$
где максимум берётся по всем противникам, кто «работает» время не больше t, делает не более q запросов, и каждый запрос не более μ бит. Тогда можно сказать, что MAC алгоритм псевдослучайный, если величина пренебрежимо мала (viprf устанавливается для Variablelength Input PseudoRandom Function — входные псевдо случайные функции переменной длины). Без ограничения общности, как предполагается, противники никогда не делают запросы вне области $\{0, 1\}^n$, а также никогда не повторяют запросы.

Далее приведём основные теоремы(их формулировки без доказательств).

Lemma 5.1 (Главная Лемма для семейства ОМАС). Предположим, что H, Cst1 и Cst2 удовлетворяют условиям Sec. 3 для некоторых пренебрежимо малых $\epsilon_1, ... , \epsilon_6$, а также пусть Cst — произвольная n-битная константа. Так же предположим, что случайная перестановка P ∈ Perm(n) используется в семействе OMAC(OMAC-family) как базовый блочный шифр. Пусть A — противник, который делает не более q запросов, и каждый запрос не более nm бит. (m — максимальное число блоков в каждом запросе.) Положим m ≤ 2n/4. Тогда
$\left|Pr(P\overset{R}{\leftarrow}Pern(n) : A^{OMAC-family_P(\cdot)} = 1) - Pr((R\overset{R}{\leftarrow}Rand(*,n):A^{R(\cdot)} = 1)\right|\leq \frac{q^2}{2} \cdot (\frac{7m^2+2}{2^n}+3m^2\epsilon )$
где $\epsilon = max{ \epsilon_1, . . . , \epsilon_6}$. Следующие результаты присущи как OMAC1 так и OMAC2. Сначала, мы получили следующую лемму заменой є = 2−n в Lemma 5.1.

Lemma 5.2 (Главная Лемма для семейства ОМАС). Предположим, что случайная перестановка P ∈ Perm(n) используется в OMAC как базовый блочный шифр . Пусть A будет противником, который делает не более q запросов, и каждый запрос не более nm бит. Положим m ≤ 2n/4. Тогда
$\left|Pr(P\overset{R}{\leftarrow}Pern(n) : A^{OMAC_P(\cdot)} = 1) - Pr((R\overset{R}{\leftarrow}Rand(*,n):A^{R(\cdot)} = 1)\right|\leq \frac{(5m^2+1)q^2}{2^n}$
Далее покажем, что OMAC является псевдослучайным, если базовый блочный шифр Е защищён.

Замечание 5.1. Пусть E : $K_E$ × $\{0, 1\}^n$ → $\{0, 1\}^n$ является базовым блочным шифром, который используется в OMAC. Тогда $Adv_{OMAC}^{viprf}(t,q,nm)\leq \frac{(5m^2+1)q^2}{2^n} + Adv_{E}^{prp}(t',q')$, где t’ = t + O(mq) and q’ = mq + 1.
В конце покажем, что OMAC защищён как aMAC алгоритм из Замечание 5.1 в обычном смысле. Theorem 5.1. Пусть E : KE × $\{0, 1\}^n$ → $\{0, 1\}^n$ является базовым блочным шифром, используемый в OMAC. Тогда
$Adv_{OMAC}^{mac}(t,q,nm)\leq \frac{(5m^2+1)q^2+1}{2^n} + Adv_{E}^{prp}(t',q')$,
где t’ = t + O(mq) and q’ = mq + 1.

Аналоги

Большинство технологий построения аутенфикационного кода сообщения представляются как хэш-функция от отправленного сообщения и определённого ключа, который знают отправитель и получатель, к ним относятся: RIPE-MAC, IBC-MAC, UMAC, VMAC. Принципиально от CBC-MAC отличается от MAC с использованием потокового шифра (с помощью генератора псевдослучайных чисел поток информации разделяется на два потока, которые отправляются отдельно друг от друга), недостатком же является слабые изменения при небольшом изменении сообщения. Также рассмотрим Poly1305-AES, где в качестве ключа используется 128 битный ключ для AES, 106 битный дополнительный код, а также создаётся 128битная псевдослучайная генерация. В качестве недостатка CBC-MAC можно указать меньшую защищённость, а в качестве преимущества — меньшую требовательность в вычислительным ресурсам.

Литература

• Tetsu Iwata and Kaoru Kurosawa. OMAC: One-Key CBC MAC. — 4–12–1 Nakanarusawa, Hitachi, Ibaraki 316-8511, Japan.: Department of Computer and Information Sciences,Ibaraki University, 2003. — С. 32.

• M. Bellare, J. Kilian, and P. Rogaway. The security of the cipher block chaining message authentication code. JCSS, vol. 61, no. 3, 2000. Earlier version in Advances in Cryptology — CRYPTO ’94, LNCS 839, pp.341–358, Springer-Verlag, 1994.

• J. Black and P. Rogaway. CBC MACs for arbitrary-length messages: The three key constructions. Advances in Cryptology — CRYPTO 2000, LNCS 1880, pp. 197–215, Springer-Verlag, 2000.

• J. Black and P. Rogaway. Comments to NIST concerning AES modes of operations: A suggestion for handling arbitrary-length messages with the CBC MAC. Second Modes of Operation Workshop.

• R. Lidl and H. Niederreiter. Introduction to finite fields and their applications, revised edition. Cambridge University Press, 1994.

• E. Petrank and C. Rackoff. CBC MAC for real-time data sources. J.Cryptology, vol. 13, no. 3, pp. 315–338, Springer-Verlag, 2000.

• S. Vaudenay. Decorrelation over infinite domains: The encrypted CBC-MAC case. Communications in Information and Systems (CIS), vol. 1, pp. 75–85, 2001. Earlier version in Selected Areas in Cryptography, SAC 2000, LNCS 2012, pp. 57–71, Springer-Verlag, 2001.

• P. Rogaway. Bucket hashing and its application to fast message authentication. Advances in Cryptology — CRYPTO ’95, LNCS 963, pp. 29–42, Springer-Verlag, 1995.

• P. Rogaway, M. Bellare, J. Black, and T. Krovetz. OCB: a block-cipher mode of operation for efficient authenticated encryption. Proceedings of ACM Conference on Computer and Communications Security, ACM CCS 2001, ACM, 2001.