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

Использовался (с подстановкой в качестве E алгоритма DES ) как государственный стандарт США — DAA .

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

Алгоритм CBC MAC является хорошо известным методом для генерации имитовставки ( англ. message authentication code — код аутентичности сообщения), основанный на блочном шифре .

Bellare, Kilian и Rogaway доказали безопасность ( защищённость ) алгоритма при фиксированной длине сообщения в m*n бит, где n — длина базового блочного шифра Е.

Однако, хорошо известно, что CBC MAC не является безопасным, если длина сообщения не является фиксированной. Таким образом, было предложено несколько вариантов алгоритма для варьируемой длины сообщения. Сначала была предложена зашифрованная имитовставка (EMAC), она получается шифрованием CBC MAC значения с помощью E и новым ключом ${\displaystyle K^{2}}$ . То есть

${\displaystyle EMAC_{K_{1},K_{2}}(M)=E_{K_{2}}(CBC_{K_{1}}(M)))}$ ,

где M — сообщение, ${\displaystyle K_{1}}$ — ключ CBC MAC и ${\displaystyle 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 бит

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

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

OMAC

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

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

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

CBC MAC

Блочный шифр Е является функцией Е : ${\displaystyle K_{E}}$ × ${\displaystyle \{0,1\}^{n}}$ → ${\displaystyle \{0,1\}^{n}}$ , где каждое E(K, •) = EK(•) является перестановкой ${\displaystyle \{0,1\}^{n}}$ , в свою очередь ${\displaystyle 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] = ${\displaystyle 0^{n}}$ . Bellare, Kilian и Rogaway доказали безопасность CBC MAC для фиксированной длины сообщения в mn бит.

Поле с ${\displaystyle 2^{n}}$ точками

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

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

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

1. Для любого y ∈ ${\displaystyle \{0,1\}^{n}}$ , число L ∈ ${\displaystyle \{0,1\}^{n}}$ таково, что HL( ${\displaystyle Cst_{1}}$ ) = y не более чем ${\displaystyle \epsilon _{1}\cdot 2^{n}}$ для некоторого достаточно малого ${\displaystyle \epsilon _{1}}$ .
2. Для любого y ∈ ${\displaystyle \{0,1\}^{n}}$ , число L ∈ ${\displaystyle \{0,1\}^{n}}$ таково, что HL( ${\displaystyle Cst_{2}}$ ) = y не более чем ${\displaystyle \epsilon _{2}\cdot 2^{n}}$ для некоторого достаточно малого ${\displaystyle \epsilon _{2}}$ .
3. Для любого y ∈ ${\displaystyle \{0,1\}^{n}}$ , число L ∈ ${\displaystyle \{0,1\}^{n}}$ таково, что HL( ${\displaystyle Cst_{1}}$ ) ⊕ HL( ${\displaystyle Cst_{2}}$ ) = y не более чем ${\displaystyle \epsilon _{3}\cdot 2^{n}}$ для некоторого достаточно малого ${\displaystyle \epsilon _{3}}$ .
4. Для любого y ∈ ${\displaystyle \{0,1\}^{n}}$ , число L ∈ ${\displaystyle \{0,1\}^{n}}$ таково, что HL( ${\displaystyle Cst_{1}}$ ) ⊕L = y не более чем ${\displaystyle \epsilon _{4}\cdot 2^{n}}$ для некоторого достаточно малого ${\displaystyle \epsilon _{4}}$ .
5. Для любого y ∈ ${\displaystyle \{0,1\}^{n}}$ , число L ∈ ${\displaystyle \{0,1\}^{n}}$ таково, что HL( ${\displaystyle Cst_{2}}$ ) ⊕L = y не более чем ${\displaystyle \epsilon _{5}\cdot 2^{n}}$ для некоторого достаточно малого ${\displaystyle \epsilon _{5}}$ .
6. Для любого y ∈ ${\displaystyle \{0,1\}^{n}}$ , число L ∈ ${\displaystyle \{0,1\}^{n}}$ таково, что HL( ${\displaystyle Cst_{1}}$ ) ⊕ HL(Cst2) ⊕ L = y не более чем ${\displaystyle \epsilon _{6}\cdot 2^{n}}$ для некоторого достаточно малого ${\displaystyle \epsilon _{6}}$ .

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

Algorithm ${\displaystyle OMAC-family_{K}(M)}$
L ← ${\displaystyle E_{K}(Cst)}$ ;
Y [0] ← ${\displaystyle 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] ← ${\displaystyle E_{K}(X[i]}$ );
X[m] ← ${\displaystyle pad_{n}(M[m]}$ ) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ ${\displaystyle H_{L}(Cst_{1})}$ ;
else X[m] ← X[m] ⊕ ${\displaystyle H_{L}(Cst_{2})}$ ;
T ← ${\displaystyle E_{K}(X[m]}$ );
return T;


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

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

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

Algorithm ${\displaystyle OMAC1_{K}(M)}$
L ← ${\displaystyle E_{K}(0^{n})}$ ;
Y [0] ← ${\displaystyle 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] ⊕ ${\displaystyle L\cdot u}$ ;
else Y[i] ← E_k(X[i]);
X[m] ← ${\displaystyle pad_{n}(M[m]}$ ) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ ${\displaystyle L\cdot u}$ ;
else X[m] ← X[m] ⊕ ${\displaystyle L\cdot u^{2}}$ ;
T ← ${\displaystyle E_{K}(X[m]}$ );
return T;


1. Для OMAC2:

Algorithm ${\displaystyle OMAC2_{K}(M)}$
L ← ${\displaystyle E_{K}(0^{n})}$ ;
Y [0] ← ${\displaystyle 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] ⊕ ${\displaystyle L\cdot u}$ ;
else Y[i] ← E_k(X[i]);
X[m] ← ${\displaystyle pad_{n}(M[m]}$ ) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ ${\displaystyle L\cdot u}$ ;
else X[m] ← X[m] ⊕ ${\displaystyle L\cdot u^{-1}}$ ;
T ← ${\displaystyle E_{K}(X[m]}$ );
return T;


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

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

Пусть Perm(n) означает набор всех перестановок из ${\displaystyle \{0,1\}^{n}}$ , так же пусть P является случайной перестановкой , если Р — случайная выборка из Perm(n). Безопасность блочного шифра E может быть количественно определена как ${\displaystyle Adv_{E}^{prp}(t,q)}$ , максимальное преимущество, которое противник A может получить, когда пытается выделить ${\displaystyle E_{K}(\cdot )}$ (со случайно выбранным ключом K) из случайной перестановки P(•), когда допускается вычисление времени t и q запросов (который является либо ${\displaystyle E_{K}(\cdot )}$ либо ${\displaystyle P(\cdot )}$ ). Это преимущество определяется следующим образом.
${\displaystyle {\begin{cases}&Adv_{E}^{prp}(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_{E}^{prp}(A)\}\end{cases}}}$
Скажем, что блочный шифр E — защищён, если существенно мало. Аналогично, MAC-алгоритм — F : ${\displaystyle K_{F}}$ × ${\displaystyle \{0,1\}^{n}}$ → ${\displaystyle \{0,1\}^{n}}$ , где ${\displaystyle K_{F}}$ — набор ключей, тогда запишем ${\displaystyle F_{K}(\cdot )}$ для F(K, •). Скажем, что противник ${\displaystyle A^{F_{K}(\cdot )}}$ взламывает, если A выдаёт ${\displaystyle (M,F_{K}(M))}$ , где A никогда не запрашивает M из ${\displaystyle F_{K}(\cdot )}$ . Тогда мы определяем преимущество как

${\displaystyle {\begin{cases}&Adv_{E}^{mac}(A):=\Pr(K{\overset {R}{\leftarrow }}K_{F}:A^{F_{K}(\cdot )}forges)\\&Adv_{E}^{mac}(t,q,\mu ):=max\{Adv_{F}^{mac}(A)\}\end{cases}}}$

где максимум берётся по всем противникам, кто «работает» не более времени t, производит не более q запросов, и каждый запрос не более μ бит. Будем говорить, MAC алгоритм защищён (безопасен), если величина пренебрежимо мала. Обозначим Rand(∗, n) набор всех функций из {0, 1}* в ${\displaystyle \{0,1\}^{n}}$ . Этот набор даётся вероятностной мерой в предположении, что случайный элемент R набора Rand(∗, n) связан или ассоциирован с каждой строкой M ∈ {0, 1}* случайной строки R(M)∈ ${\displaystyle \{0,1\}^{n}}$ . Далее, мы определим преимущество как
${\displaystyle {\begin{cases}&Adv_{F}^{viprf}(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_{F}^{viprf}(A)\}\end{cases}}}$
где максимум берётся по всем противникам, кто «работает» время не больше t, делает не более q запросов, и каждый запрос не более μ бит. Тогда можно сказать, что MAC алгоритм псевдослучайный, если величина пренебрежимо мала (viprf устанавливается для Variablelength Input PseudoRandom Function — входные псевдо случайные функции переменной длины). Без ограничения общности, как предполагается, противники никогда не делают запросы вне области ${\displaystyle \{0,1\}^{n}}$ , а также никогда не повторяют запросы.

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

Lemma 5.1 (Главная Лемма для семейства ОМАС). Предположим, что H, Cst1 и Cst2 удовлетворяют условиям Sec. 3 для некоторых пренебрежимо малых ${\displaystyle \epsilon _{1},...,\epsilon _{6}}$ , а также пусть Cst — произвольная n-битная константа. Так же предположим, что случайная перестановка P ∈ Perm(n) используется в семействе OMAC(OMAC-family) как базовый блочный шифр. Пусть A — противник, который делает не более q запросов, и каждый запрос не более nm бит. (m — максимальное число блоков в каждом запросе.) Положим m ≤ 2n/4. Тогда
${\displaystyle \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 )}$
где ${\displaystyle \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. Тогда
${\displaystyle \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 : ${\displaystyle K_{E}}$ × ${\displaystyle \{0,1\}^{n}}$ → ${\displaystyle \{0,1\}^{n}}$ является базовым блочным шифром, который используется в OMAC. Тогда ${\displaystyle 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 × ${\displaystyle \{0,1\}^{n}}$ → ${\displaystyle \{0,1\}^{n}}$ является базовым блочным шифром, используемый в OMAC. Тогда
${\displaystyle 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. . — 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. . от 5 февраля 2012 на Wayback Machine
• J. Black and P. Rogaway. .
• J. Black and P. Rogaway. .
• R. Lidl and H. Niederreiter. .
• E. Petrank and C. Rackoff. .
• S. Vaudenay. .
• P. Rogaway. .
• P. Rogaway, M. Bellare, J. Black, and T. Krovetz. .