CBC MAC -in kryptografie je technologie pro konstrukci autentizačního kódu zprávy z blokové šifry . Zpráva je zašifrována pomocí nějakého algoritmu blokové šifry v režimu CBC, aby se vytvořil řetězec bloků s pravidlem, že každý blok závisí na správném (správném) šifrování předchozího. Tato vzájemná závislost zajišťuje, že změna libovolného bitu otevřeného textu povede ke změně konečného zašifrovaného bloku způsobem, který nelze předvídat ani vypočítat, pokud není znám klíč blokové šifry .
Byl použit (s substitucí jako E algoritmu DES ) jako americký vládní standard - DAA .
Algoritmus CBC MAC je dobře známá metoda pro generování ověřovacího kódu zprávy na základě blokové šifry .
Bellare, Kilian a Rogaway prokázali bezpečnost ( zabezpečení ) algoritmu pro pevnou délku zprávy m * n bitů, kde n je délka šifry základního bloku E.
Je však dobře známo, že MAC CBC není bezpečný, pokud není pevně stanovena délka zprávy. Bylo tedy navrženo několik variant algoritmu pro proměnnou délku zprávy. Jako první bylo navrženo vkládání šifrované imitace (EMAC) , získává se zašifrováním hodnoty CBC MAC pomocí E a nového klíče . To znamená
,kde M je zpráva, je klíč CBC MAC a hodnota CBC MAC zprávy. M. Petrank a Rackoff později prokázali, že EMAC je bezpečný, pokud je délka zprávy násobkem n (Vaudenay, s použitím teorie dekorací , publikoval další důkaz). EMAC však vyžaduje dva plány klíčů pro základní blokovou šifru E.
Dále Black a Rogaway navrhli XCBC, které vyžaduje pouze jeden klíčový plán základní blokové šifry E. XCBC poskytuje tři klíče: jeden klíč blokové šifry K1 a dva klíče, každý o n bitech. XCBC je popsána následujícím diagramem
Tabulka ukazuje srovnání délek klíčů.
XCBC | TMAC | OMAC | |
---|---|---|---|
Délka klíče | (k + 2n) bit | (k + n) bitů | k bitů |
Je-li pro některé m > 0, pak se XCBC vypočítá přesně jako CBC MAC, s výjimkou operace XOR ("exclusive or") klíče (n bitů), dokud není zašifrován poslední blok.
Jinak se k M přidá (kde ) a XCBC se vypočítá přesně jako MAC CBC pro přijatou zprávu. Kromě XORingu další klíč (n bitů), dokud není zašifrován poslední blok. Nevýhodou XCBC však je, že vyžaduje tři klíče, tedy celkem (k + 2n) bitů. V důsledku toho Kurosawa a Iwata navrhli dvouklíčový CBC MAC (TMAC). TMAC přijímá dva klíče o součtu (k + n) bitů: klíč blokové šifry a klíč (n bitů). TMAC se získá z XCBC přesunem (nebo nahrazením) s , kde u je nějaká nenulová konstanta a "•" označuje násobení v . Jak již bylo zmíněno, OMAC ( one-key CBC MAC ) akceptuje pouze jeden klíč K z blokové šifry E. Délka klíče, k bitů, je minimální, protože základní šifra musí obsahovat klíč K, který se v každém případě skládá z k bitů. .
OMAC je nadřazený název pro OMAC1 a OMAC2. OMAC1 se získá z XCBC nahrazením za nějakou nenulovou konstantu u v , kde L je dáno následujícím výrazem: . OMAC2 se podobně získá za použití . Můžeme vypočítat , a efektivně s jediným posunem a XOR na a , resp. OMAC1 (resp. OMAC2) je popsán následujícím diagramem:
1. Pokud pro některé m > 0, pak se OMAC vypočítá přesně jako CBC MAC, kromě operace XOR před zašifrováním posledního bloku.
2. V opačném případě je (kde ) přidáno k M a OMAC Vypočteno přesně jako CBC MAC pro přijatou zprávu M, kromě operace XOR pro (resp. před zašifrováním posledního bloku.
V TMAC je klíč součástí klíče, zatímco v OMAC není L součástí klíče a je generován z K. Toto zachování délky klíče činí zabezpečení OMAC mnohem obtížnějším prokázat než TMAC, jak je uvedeno níže. . Na obrázku 2 nechť M[1] = . Pak L je výstupem prvního . L se vždy objeví znovu v posledním bloku. V zásadě by takové opětovné použití L vedlo k uváznutí v bezpečnostním důkazu. (V režimu OCB a PMAC se také používá jako univerzální hash klíč. L se však objevuje jako výstup nějakého vnitřního bloku se zanedbatelnou pravděpodobností.) Dokázali jsme však, že OMAC je stejně bezpečný jako XCBC, kde bezpečnostní analýza je příkladem absolutní bezpečnosti [1]. Dále OMAC získal všechny další pozitivní vlastnosti, kterými byl obdařen XCBC (a TMAC). Oblast OMAC je tedy {0,1}, je potřeba jednoklíčový plán volání (referencí) základní blokové šifry E a blokové šifry.
Pro množinu A x←A znamená, že x je vybráno náhodně z A a výběr libovolné hodnoty z množiny A je ekvipravděpodobný. Jestliže a, b (∈ {0, 1}*) jsou řetězce stejné velikosti, pak a ⊕ b je jejich bitová operace XOR. Pokud a, b (∈ {0, 1}*) nejsou stejné řetězce, pak a ◦ b značí jejich zřetězení . (Pro zjednodušení je zaveden následující zápis: ab:= a ◦ b). Pro n-bitový řetězec ∈ {0, 1}* označte << 1 = n-bitový řetězec, který je posunut doleva o 1 bit, mezitím označte >> 1 =
n-bitový řetězec, který je posunut o jeden bit doprava. Je-li a ∈ {0, 1}* řetězec, pak |a| označují jeho bitovou délku. Pro libovolný bit je řetězec a ∈ {0, 1}* takový, že |a| ≤ n,
definujme , kde se prázdný řetězec počítá jako jeden blok.
Bloková šifra E je funkce E : × → , kde každé E(K, •) = EK(•) je permutací , dále je sada možných klíčů a n je délka bloku. CBC MAC [6, 7] je nejjednodušší a nejznámější algoritmus pro vytvoření MAC z blokové šifry E. Nechť zpráva je M = M[1] ◦M[2] ◦ … ◦M[m], kde | M [1]| = |M[2]| = … = |M[m]| = n. Potom CBCK(M), CBC MAC zprávy M, daný klíč K, je definován jako Y [m], kde Y [i] = EK(M[i] ⊕ Y [i − 1]) pro i = 1, … ,ma Y[0] = . Bellare, Kilian a Rogaway prokázali bezpečnost CBC MAC pro pevnou délku zprávy mn bitů.
Bod a můžeme považovat některým z následujících způsobů: (1) jako abstraktní bod v poli a ; (2) jako n-bitový řetězec ∈ ; (3) jako formální polynom s binárními koeficienty. Chcete-li přidat 2 body k , zvažte bitovou operaci XOR na nich. Tuto operaci označte a ⊕ b. Pro vynásobení dvou bodů fixujeme nějaký polynom f(u) s binárními koeficienty a stupněm n. Pro větší přesnost volíme lexikograficky první polynom ze stejných polynomů stupně n s minimálním počtem koeficientů. Vyjmenujeme některé z těchto polynomů
pro n = 64,
pro n = 128 a
pro n = 256.
Chcete-li vynásobit dva body a ∈ a b ∈ , uvažujte a a b jako polynomy a , výsledek operace c(u), kde koeficienty v GF(2) se sečtou a vynásobí a vezme se zbytek oddělení c(u) pomocí f(u). Navíc je obzvláště snadné vynásobit bod a ∈ u. Například, je-li n = 128,
také vydělte bod a ∈ u, přičemž mějte na paměti, že a je násobeno převrácenou hodnotou u v poli: . Například,
Rodina OMAC je definována blokovou šifrou E : KE × → , n-bitovou konstantou Cst, univerzální hašovací funkcí H : × X → a dvěma jedinečnými konstantami ∈ X , kde X je konečný obor funkce H. H, a musí splňovat následující podmínku: (konstanty jsou náhodné. Zapišme HL(•) pro H(L, •).
1. Pro libovolné y ∈ je číslo L ∈ takové, že HL( ) = y nejvýše pro některé dostatečně malé .
2. Pro libovolné y ∈ je číslo L ∈ takové, že HL( ) = y nejvýše pro některé dostatečně malé .
3. Pro libovolné y ∈ je číslo L ∈ takové, že HL( ) ⊕ HL( ) = y maximálně pro nějaké dostatečně malé .
4. Pro libovolné y ∈ je číslo L ∈ takové, že HL( ) ⊕L = y nejvýše pro některé dostatečně malé .
5. Pro libovolné y ∈ je číslo L ∈ takové, že HL( ) ⊕L = y nejvýše pro některé dostatečně malé .
6. Pro libovolné y ∈ je číslo L ∈ takové, že HL( ) ⊕ HL(Cst2) ⊕ L = y nejvýše pro nějaké dostatečně malé .
Následuje pseudokód, který popisuje rodinu OMAC.
Algorithm
L ← ;
Y [0] ← ;
Partition M into M[1] ... M[m]
for i ← 1 to m − 1 do
X[i] ← M[i] ⊕ Y [i − 1];
Y [i] ← );
X[m] ← ) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ ;
else X[m] ← X[m] ⊕ ;
T ← );
return T;
Algoritmus rodiny OMAC je znázorněn na obr. 3, kde (•) je definováno v (1). Klíčový prostor K rodiny OMAC: . Přebírá hodnotu klíče K ∈ a zprávu M ∈ {0, 1}* a vrací řetězec z oblasti .
V OMAC1 nastavíme Cst = , (x) = L•x, = u a = , kde "•" znamená násobení v . a jsou ekvivalentní. OMAC2 je podobný OMAC1 kromě . a jsou ekvivalentní. Navíc , a lze efektivně vypočítat s jedním posunem a jednou operací XOR z a , jak je znázorněno v (2) a (3). Je snadné vidět, že podmínky v Sec. 3 jsou prováděny pro v OMAC1 a OMAC2. OMAC1 a OMAC2 jsou znázorněny na obrázku 2 a jsou popsány následovně:
1. Pro OMAC1:
Algorithm
L ← ;
Y [0] ← ;
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] ⊕ ;
else Y[i] ← E_k(X[i]);
X[m] ← ) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ ;
else X[m] ← X[m] ⊕ ;
T ← );
return T;
1. Pro OMAC2:
Algorithm
L ← ;
Y [0] ← ;
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] ⊕ ;
else Y[i] ← E_k(X[i]);
X[m] ← ) ⊕ Y [m − 1];
if |M[m]| = n then X[m] ← X[m] ⊕ ;
else X[m] ← X[m] ⊕ ;
T ← );
return T;
Nechť Perm(n) je množina všech permutací z , a nechť P je náhodná permutace , pokud P je náhodný vzorek z Perm(n). Bezpečnost blokové šifry E lze kvantifikovat jako maximální výhodu, kterou může protivník A získat, když se pokusí extrahovat (s náhodně vybraným klíčem K) z náhodné permutace P(•), když jsou povoleny doby dotazu t a q ( což je buď ). Tato výhoda je definována následovně.
Řekněme, že bloková šifra E je bezpečná, pokud je v podstatě malá. Podobně algoritmus MAC je F : × → , kde je sada klíčů, pak píšeme pro F(K, •). Řekněme, že protivník se zlomí, pokud se A vrátí , kde A nikdy nepožaduje M od . Pak definujeme výhodu jako
kde maximum je převzato ze všech protivníků, kteří „pracují“ ne déle než čas t, nedávají více než q požadavků a každý požadavek ne více než μ bitů. Řekneme, že algoritmus MAC je chráněný (safe), pokud je hodnota zanedbatelná. Označme Rand(∗, n) množinu všech funkcí od {0, 1}* do . Tato množina je dána mírou pravděpodobnosti za předpokladu, že náhodný prvek R množiny Rand(∗, n) je spojen nebo asociován s každým řádkem M ∈ {0, 1}* náhodného řádku R(M)∈ . Dále definujeme výhodu jako místo,
kde je maximum převzato ze všech protivníků, kteří „odpracují“ čas ne více než t, nedělají více než q požadavků a každý požadavek ne více než μ bitů. Pak můžeme říci, že MAC algoritmus je pseudonáhodný, pokud je hodnota zanedbatelná (viprf je nastaven pro Variablelength Input PseudoRandom Function - vstupní pseudonáhodné funkce proměnné délky). Bez ztráty obecnosti se předpokládá, že protivníci nikdy nepodávají požadavky mimo doménu a také nikdy žádosti neopakují.
Dále uvedeme hlavní věty (jejich formulace bez důkazů).
Lemma 5.1 (hlavní lemma pro rodinu OMAC). Předpokládejme, že H, Cst1 a Cst2 splňují podmínky Sec. 3 pro nějaké zanedbatelně malé , a také nechť Cst je libovolná n-bitová konstanta. Předpokládejme také, že v rodině OMAC (rodina OMAC) je jako základní bloková šifra použita náhodná permutace P ∈ Perm(n). Nechť A je protivník, který nevydává více než q požadavků a každý požadavek ne více než nm bitů. (m je maximální počet bloků v každém dotazu.) Nechť m ≤ 2n/4. Pak
kde . Následující výsledky platí pro OMAC1 i OMAC2. Nejprve jsme získali následující lemma nahrazením є = 2−n v lemmatu 5.1.
Lemma 5.2 (hlavní lemma pro rodinu OMAC). Předpokládejme, že náhodná permutace P ∈ Perm(n) je použita v OMAC jako základní bloková šifra. Nechť A je protivník, který odešle nejvýše q požadavků a každý požadavek má nejvýše nm bitů. Nechť m ≤ 2n/4. Dále
ukážeme, že OMAC je pseudonáhodný, pokud je základní bloková šifra E bezpečná.
Poznámka 5.1. Nechť E : × → je základní bloková šifra, která se používá v OMAC. Potom
, kde t' = t + O(mq) a q' = mq + 1.
Nakonec ukážeme, že OMAC je chráněn jako algoritmus aMAC z poznámky 5.1 v obvyklém smyslu. Věta 5.1. Nechť E : KE × → je základní bloková šifra používaná v OMAC. Potom ,
kde t' = t + O(mq) a q' = mq + 1.
Většina technologií pro konstrukci autentizačního kódu zprávy je reprezentována jako hashovací funkce odesílané zprávy a specifický klíč, který odesílatel a příjemce znají, mezi ně patří: RIPE-MAC, IBC-MAC, UMAC, VMAC. CBC-MAC se zásadně liší od MAC pomocí proudové šifry (pomocí generátoru pseudonáhodných čísel se informační proud rozdělí na dva proudy, které se odesílají odděleně), nevýhodou jsou však slabé změny s malou změnou zpráva. Zvažte také Poly1305-AES, kde je jako klíč použit 128bitový klíč pro AES, 106bitový dvojkový doplňkový kód a také je vytvořeno 128bitové pseudonáhodné generování. Jako nevýhodu CBC-MAC můžete označit menší zabezpečení a jako výhodu - menší náročnost na výpočetní zdroje.