MMH-Badger MAC - MMH-Badger MAC - Wikipedia

Tento článek může vyžadovat vyčištění setkat se s Wikipedií standardy kvality. Specifický problém je: příliš mnoho (konkrétního) obsahu, vhodně se rozdělte Prosím pomozte vylepšit tento článek jestli můžeš. (Březen 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Jezevec je Ověřovací kód zprávy (MAC) na základě myšlenky univerzální hash a byl vyvinut společnostmi Boesgaard, Scavenius, Pedersen, Christensen a Zenner.^[1] Je konstruována posílením ∆-univerzální hash rodiny MMH pomocí ϵ-téměř silně univerzální (ASU) rodiny hash funkcí po aplikaci ENH (viz níže), kde hodnota ϵ je ${ displaystyle 1 / (2 ^ {32} -5)}$.^[2] Vzhledem k tomu, Badger je funkce MAC na základě univerzální hash funkční přístup, podmínky potřebné pro bezpečnost Badgera jsou stejné jako u jiných univerzálních hash funkcí, jako je UMAC.

Úvod

Badger MAC zpracovává zprávu o délce až ${ displaystyle 2 ^ {64} -1}$ bity a vrací ověřování štítek délky ${ displaystyle u cdot 32}$ bity, kde ${ displaystyle 1 leq u leq 5}$. Podle bezpečnostní potřeby, uživatel si může vybrat hodnotu ${ displaystyle u}$, to je počet paralelních hash stromy v Badgerovi. Lze zvolit větší hodnoty u, ale tyto hodnoty dále neovlivňují bezpečnost MAC. The algoritmus používá 128bitový klíč a omezená délka zprávy, která má být zpracována pod tímto klíčem, je ${ displaystyle 2 ^ {64}}$.^[3]

Nastavení klíče musí být spuštěno pouze jednou na klíč, aby bylo možné spustit Badger algoritmus pod daným klíčem, protože výsledný vnitřní stav MAC lze uložit pro použití s ​​jakoukoli další zprávou, která bude zpracována později.

ENH

Hash rodiny lze kombinovat za účelem získání nových hashovacích rodin. Pro rodiny ϵ-AU, ϵ-A∆U a ϵ-ASU jsou tyto rodiny obsaženy v první. Například rodina A∆U je také rodina AU, ASU je také rodina A∆U atd. Na druhou stranu lze silnější rodinu snížit na slabší, pokud lze dosáhnout zvýšení výkonu. Metoda pro snížení ∆-univerzální hashovací funkce na univerzální hash funkce budou popsány dále.

Věta 2^[1]

Nechat ${ displaystyle H ^ { trojúhelník}}$ být hash rodinou ϵ-AΔU ze sady A do sady B. Zvažte zprávu ${ displaystyle (m, m_ {b}) v A krát B}$. Pak rodina H skládající se z funkcí ${ displaystyle h (m, m_ {b}) = H ^ { trojúhelník} (m) + m_ {b}}$ je ϵ-AU.

Li ${ displaystyle m neq m '}$, pak pravděpodobnost že${ displaystyle h (m, m_ {b}) = h (m ', m' _ {b})}$ je nanejvýš ϵ, protože ${ displaystyle H ^ { trojúhelník}}$ je rodina ϵ-A∆U. Li ${ displaystyle m = m '}$ ale ${ displaystyle m_ {b} neq m_ {b} '}$, pak pravděpodobnost je triviálně 0. Důkaz pro Větu 2 byl popsán v ^[1]

Rodina ENH je postavena na základě univerzální hash skupina NH (která se také používá v UMAC ):

${ displaystyle NH_ {K} (M) = součet _ {i = 1} ^ { frac { ell} {2}} (k _ {(2i-1)} + _ {w} m _ {(2i- 1)}) times (k_ {2i} + _ {w} m_ {2i}) mod 2 ^ {2w}}$

Kde${ displaystyle + _ {w}}$„Znamená„ přidání modulo ${ displaystyle 2 ^ {w}}$', a ${ displaystyle m_ {i}, k_ {i} in { big {} 0, ldots, 2 ^ {w} -1 { big }}}$. Je to ${ displaystyle 2 ^ {- w}}$-A∆U hash rodina.

Lemma 1^[1]

Následující verze NH je ${ displaystyle 2 ^ {- w}}$-A∆U:

${ displaystyle NH_ {K} (M) = (k_ {1} + _ {w} m_ {1}) krát (k_ {2} + _ {w} m_ {2}) mod 2 ^ {2w} }$

Volbou w = 32 a použitím věty 1 lze získat ${ displaystyle 2 ^ {- 32}}$-AU funkční rodina ENH, která bude základním stavebním kamenem jezevce MAC:

${ displaystyle ENH_ {k_ {1}, k_ {2}} (m_ {1}, m_ {2}, m_ {3}, m_ {4}) = (m_ {1} + _ {32} k_ {1 }) (m_ {2} + _ {32} k_ {2}) + _ {64} m_ {3} + _ {64} 2 ^ {32} m_ {4}}$

kde jsou všechny argumenty dlouhé 32 bitů a výstup má 64 bitů.

Konstrukce

Badger je konstruován pomocí silně univerzální hashovací rodiny a lze jej popsat jako

${ displaystyle { mathcal {H}} = H ^ {*} krát F,}$^[1]

kde ${ displaystyle epsilon _ {H ^ {*}}}$-UU univerzální funkční rodina H * se používá k hašování zpráv jakékoli velikosti na pevnou velikost a ${ displaystyle epsilon _ {F}}$Rodina funkcí ASU F slouží k zajištění silné univerzálnosti celkové konstrukce. NH a ENH se používají ke konstrukci H *. Maximální velikost vstupu rodiny funkcí H * je ${ displaystyle 2 ^ {64} -1}$ a velikost výstupu je 128 bitů, rozdělená na 64 bitů pro zprávu a hash. Pravděpodobnost kolize pro H *-funkce se pohybuje od ${ displaystyle 2 ^ {- 32}}$ na ${ displaystyle 2 ^ {- 26.14}}$. Vybudovat silně univerzální funkční skupinu F, ∆-univerzální hash rodina MMH * se transformuje do silně univerzální hash rodiny přidáním dalšího klíče.

Dva kroky na Badgera

U každé zprávy je třeba provést dva kroky: fázi zpracování a fázi finalizace.

Fáze zpracování^[3]V této fázi jsou data hašována na 64bitový řetězec. Základní funkce ${ displaystyle h}$ : ${ displaystyle { big {} 0,1 { big }} ^ {64} krát { big {} 0,1 { big }} ^ {128} až { big { } 0,1 { big }} ^ {64}}$ se používá v této fázi zpracování, která hashuje 128bitový řetězec ${ displaystyle m_ {2} paralelní m_ {1}}$ na 64bitový řetězec ${ displaystyle h (k, m_ {2}, m_ {1})}$ jak následuje:

${ displaystyle h (k, m_ {2}, m_ {1}) = (L (m_ {1}) + _ {32} L (k)) cdot (U (m_ {1}) + _ {32 } U (k)) + _ {64} m_ {2} ,}$

pro všechny n, ${ displaystyle + _ {n}}$ znamená přidání modulo ${ displaystyle 2 ^ {n}}$. Vzhledem k 2n-bitový řetězec X, L (x) znamená nejméně významný n bity a U (x) znamená nejvýznamnější n bity.

Pomocí této funkce lze zpracovat zprávu. Označte level_key [j] [i] podle ${ displaystyle k_ {j} ^ {i}}$.

Pseudokód fáze zpracování je následující.

L = | M | if L = 0M ^ 1 = ⋯ = M ^ u = 0 Přejít na finalizaci r = L mod 64if r ≠ 0: M = 0 ^ (64-r) ∥M for i = 1 to u: M ^ i = Mv ^ '= max {1, ⌈log_2 L⌉-6} pro j = 1 až v ^': rozdělte M ^ i na 64bitové bloky, M ^ i = m_t ^ i∥ ⋯ ∥m_1 ^ i t je sudé : M ^ i = h (k_j ^ i, m_t ^ i, m_ (t-1) ^ i) ∥ ⋯ ∥ h (k_j ^ i, m_2 ^ i, m_1 ^ i) elseM ^ i = m_t ^ i∥h (k_j ^ i, m_ (t-1) ^ i, m_ (t-2) ^ i) ∥ ⋯ ∥ h (k_j ^ i, m_2 ^ i, m_1 ^ i)

Dokončit fáze^[3]V této fázi je řetězec 64, který je výsledkem fáze zpracování, transformován na požadovanou značku MAC. Tato fáze finalizace používá Králičí proudová šifra a používá jak nastavení klíče, tak nastavení IV tím, že finalizační klíč final_key [j] [i] vezme jako ${ displaystyle k_ {j} ^ {i}}$.

Pseudokód fáze finalizace

RabbitKeySetup (K) RabbitIVSetup (N) pro i = 1 až u: Q ^ i = 0 ^ 7∥L∥M ^ identifikuje Q ^ i do 27bitových bloků, Q ^ i = q_5 ^ i∥ ⋯ ∥q_1 ^ iS ^ i = (∑_ (j = 1) ^ 5 (q_j ^ i K_j ^ i)) + K_6 ^ i mod pS = S ^ u∥ ⋯ ∥S ^ 1S = S ⨁ RabbitNextbit (u ∙ 32) návrat S

Notace:

Z výše uvedeného pseudokódu, k označuje klíč v Rabbit Key Setup (K), který inicializuje Rabbit pomocí 128bitového klíče k. M označuje hashovanou zprávu a |M| označuje délku zprávy v bitech. q_i označuje zprávu M který je rozdělen na i bloky. Za dané 2n-bitový řetězec X pak L (X) a U (X) označil jeho nejméně významné n bitů a nejvýznamnější n bity.

Výkon

Boesgard, Christensen a Zenner uvádějí výkon Badgeru měřený na 1,0 GHz Pentium III a na 1,7 GHz Pentium 4 procesor.^[1] Rychlostně optimalizované verze byly naprogramovány v assembleru inline v C a kompilovány pomocí Intel C ++ Překladač 7.1.

V následující tabulce jsou uvedeny Badgerovy vlastnosti pro různé délky zpráv s omezeným přístupem. "Požadavek na paměť." označuje množství paměti potřebné k uložení vnitřního stavu včetně klíčového materiálu a vnitřního stavu souboru Králičí proudová šifra . „Setup“ označuje klíčové nastavení a „Fin“. označuje finalizaci pomocí IV-nastavení.

Max. Velikost zprávy	Padělání vázáno	Regulace paměti	Nastavit Pentium III	Ploutev. Pentium III	Nastavit Pentium III	Ploutev. Pentium III
${ displaystyle 2 ^ {11}}$ bajtů (např. IPsec)	${ displaystyle 2 ^ {- 57,7}}$	400 bajtů	1133 cyklů	409 cyklů	1774 cyklů	776 cyklů
${ displaystyle 2 ^ {15}}$ bajtů (např. TLS)	${ displaystyle 2 ^ {- 56,6}}$	528 bajtů	1370 cyklů	421 cyklů	2100 cyklů	778 cyklů
${ displaystyle 2 ^ {32}}$ bajtů	${ displaystyle 2 ^ {- 54,2}}$	1072 bajtů	2376 cyklů	421 cyklů	3488 cyklů	778 cyklů
${ displaystyle 2 ^ {61} -1}$ bajtů	${ displaystyle 2 ^ {- 52,2}}$	2 000 bytů	4093 cyklů	433 cyklů	5854 cyklů	800 cyklů

MMH (multilineární modulární hash)

Název MMH znamená Multilinear-Modular-Hashing. Aplikace v Multimédia jsou například k ověření integrita online multimediálního titulu. Výkon MMH je založen na vylepšené podpoře celého čísla skalární produkty v moderních mikroprocesorech.

MMH používá jako svou nejzákladnější operaci jednoduché skalární produkty. Skládá se z (upraveného) vnitřní produkt mezi zprávou a klíčem modulo A primární ${ displaystyle p}$. Stavba MMH funguje v konečné pole ${ displaystyle F_ {p}}$ pro nějaké hlavní celé číslo ${ displaystyle p}$.

MMH *

MMH * zahrnuje konstrukci rodiny hashovací funkce skládající se z multilineární funkce zapnuty ${ displaystyle F_ {p} ^ {k}}$ pro nějaké kladné celé číslo ${ displaystyle k}$. Rodina MMH * funkcí z ${ displaystyle F_ {p} ^ {k}}$ na ${ displaystyle F_ {p}}$ je definována následovně.

${ displaystyle mathrm {MMH} ^ {*} = {g_ {x}: F_ {p} ^ {k} rightarrow F_ {p} | x ve F_ {p} ^ {k} } , }$

kde x, m jsou vektory a funkce ${ displaystyle g_ {x}}$ jsou definovány následovně.

${ displaystyle ! g_ {x} (m)}$ = ${ displaystyle mx mod p}$ = ${ displaystyle sum _ {i = 1} ^ {n} m_ {i} , x_ {i} mod p}$

V případě MAC ${ displaystyle m}$ je zpráva a ${ displaystyle x}$ je klíč, kde ${ displaystyle m = (m_ {1}, ldots, m_ {k})}$ a ${ displaystyle x = (x_ {1}, ldots, x_ {k}), x_ {i}, m_ {i} in ! F_ {p}}$.

MMH * by měl splňovat bezpečnostní požadavky MAC, umožňující říkat Ana a Bob komunikovat autentizovaným způsobem. Mají tajný klíč ${ displaystyle x}$. Řekněme, že Charles poslouchá rozhovor mezi Ana a Bobem a chce změnit zprávu na svou vlastní zprávu Bobovi, která by měla předat jako zprávu od Ana. Takže jeho zpráva ${ displaystyle m '}$ a Ana zpráva ${ displaystyle m}$ se bude lišit alespoň v jednom bitu (např. ${ displaystyle m_ {1} neq m '_ {1}}$).

Předpokládejme, že Charles ví, že funkce má formu ${ displaystyle g_ {x} (m)}$ a zná Aninu zprávu ${ displaystyle m}$ ale nezná klíč X potom pravděpodobnost, že Charles může změnit zprávu nebo poslat vlastní zprávu, lze vysvětlit následující větou.

Věta 1^[4]: Rodina MMH * je ∆-univerzální.

Důkaz:

Vzít ${ displaystyle a v F_ {p}}$a nechte ${ displaystyle m, m '}$ být dvě různé zprávy. Převzít bez ztráty obecnosti že ${ displaystyle m_ {1} neq m '_ {1}}$. Pak pro jakoukoli volbu ${ displaystyle x_ {2}, x_ {3}, ldots, x_ {s}}$, tady je

${ displaystyle { begin {aligned} { Pr} _ {x_ {1}} [g_ {x} (m) -g_ {x} (m ') equiv a mod p] & = { Pr} _ {x_ {1}} [(m_ {1} x_ {1} + m_ {2} x_ {2} + cdots + m_ {k} x_ {k}) - (m '_ {1} x_ {1 } + m '_ {2} x_ {2} + cdots + m' _ {k} x_ {k}) equiv a mod p] & = { Pr} _ {x_ {1}} [ (m_ {1} -m '_ {1}) x_ {1} + (m_ {2} -m' _ {2}) x_ {2} + cdots + (m_ {k} -m '_ {k }) x_ {k}] equiv a mod p] & = { Pr} _ {x_ {1}} [(m_ {1} -m '_ {1}) x_ {1} + textový styl sum _ {k = 2} ^ {s} (m_ {k} -m '_ {k}) x_ {k} equiv a mod p] & = { Pr} _ {x_ {1} } [(m_ {1} -m '_ {1}) x_ {1} equiv a- textstyle suma _ {k = 2} ^ {s} (m_ {k} -m' _ {k}) x_ {k} mod p] & = { frac {1} {p}} end {zarovnáno}}}$

Chcete-li vysvětlit větu výše, vezměte ${ displaystyle F_ {p}}$ pro ${ displaystyle p}$ prvočíslo představuje pole jako ${ displaystyle F_ {p} = podprsenka {{ big {} 0,1, ldots, p-1 { big }}} _ {p}}$. Pokud někdo vezme prvek dovnitř ${ displaystyle F_ {p}}$, řekněme ${ displaystyle 0 ve F_ {p}}$ pak pravděpodobnost, že ${ displaystyle x_ {1} = 0}$ je

${ displaystyle { Pr} _ {x_ {1} in ! {F_ {p}}} (x_ {1} = 0) = { frac {1} {p}}}$

To, co člověk vlastně potřebuje k výpočtu, je

${ displaystyle { Pr} _ {(x_ {1}, ldots, x_ {k}) in ! {F_ {p} ^ {k}}} (g_ {x} (m) equiv g_ { x} (m ') mod p)}$

Ale,

${ displaystyle { begin {aligned} { Pr} _ {(x_ {1}, ldots, x_ {k}) in ! {F_ {p} ^ {k}}} (g_ {x} ( m) equiv g_ {x} (m ') mod p) & = sum _ {(x_ {2}, ldots, x_ {k}) in ! {F_ {p} ^ {k-1 }}} { Pr} _ {(x_ {2} ^ {'} cdots, x_ {k} ^ {'}) in ! {F_ {p} ^ {k-1}}} ({x_ {2} = x_ {2} ^ {'}}, ldots, {x_ {k} = x_ {k} ^ {'}}) cdot { Pr} _ {x_ {1} in ! F_ {p}} (g_ {x} (m) equiv g_ {x} (m ') mod p) & = sum _ {(x_ {2}, ldots, x_ {k}) in ! {F_ {p} ^ {k-1}}} { frac {1} {p ^ {k-1}}} cdot { frac {1} {p}} & = p ^ { k-1} cdot { frac {1} {p ^ {k-1}}} cdot { frac {1} {p}} & = { frac {1} {p}} konec {zarovnaný}}}$

Z výše uvedeného dokladu ${ displaystyle { frac {1} {p}}}$ je srážka pravděpodobnost útočníka v 1 kole, tedy v průměru ${ displaystyle p}$ k přijetí jedné zprávy stačí ověřovací dotazy. Chcete-li snížit srážka pravděpodobnost, je nutné zvolit velký p nebo zřetězit ${ displaystyle n}$ takové MAC pomocí ${ displaystyle n}$ nezávislé klíče tak, aby srážka pravděpodobnost se stává ${ displaystyle { frac {1} {p ^ {n}}}}$. V tomto případě se počet klíčů zvýší o faktor ${ displaystyle n}$ a výstup se také zvýší o ${ displaystyle n}$.

MMH * 32

Halevi a Krawczyk^[4] zkonstruujte variantu nazvanou ${ displaystyle MMH_ {32} ^ {*}}$. Konstrukce funguje s 32bitovou verzí celá čísla a s primární celé číslo ${ displaystyle p = 2 ^ {32} +15}$. Vlastně primární p může být zvolen jakýkoli prime, který uspokojí ${ displaystyle 2 ^ {32}$

. Tato myšlenka je převzata z návrhu Cartera a Wegmana používat prvočísla ${ displaystyle 2 ^ {16} +1}$ nebo ${ displaystyle 2 ^ {31} -1}$.

${ displaystyle mathrm {MMH} _ {32} ^ {*}}$ je definována takto:

${ displaystyle MMH_ {32} ^ {*} = { big {} g_ {x} ({ big {} 0,1 { big }} ^ {32}) ^ {k} { big }} na F_ {p},}$

kde ${ displaystyle { big {} 0,1 { big }} ^ {32}}$ prostředek ${ displaystyle { big {} 0,1, ldots, 2 ^ {32} -1 { big }}}$ (tj. binární reprezentace)

Funkce ${ displaystyle g_ {x}}$ jsou definovány následovně.

${ displaystyle { begin {aligned} g_ {x} (m) & { overset { underset { mathrm {def}} {}} {=}} m cdot x mod (2 ^ {32} + 15) & = textstyle sum _ {i = 1} ^ {k} m_ {i} cdot x_ {i} mod (2 ^ {32} +15) end {zarovnáno}}}$

kde

${ displaystyle x = (x_ {1}, ldots, x_ {k})}$, ${ displaystyle m = (m, ldots, m_ {k})}$

Podle věty 1 se srážka pravděpodobnost je asi ϵ = ${ displaystyle 2 ^ {- 32}}$a rodina ${ displaystyle MMH_ {32} ^ {*}}$ lze definovat jako ϵ - téměř ∆ univerzální s ϵ = ${ displaystyle 2 ^ {- 32}}$.

Hodnota k

Hodnota k který popisuje délku zprávy a klíč vektory má několik efektů:

• Protože nákladná modulární redukce skončila k se operace násobení a přidávání zvyšují k by měla snížit rychlost.
• Od klíče X skládá se z k 32bitová celá čísla se zvyšují k bude mít za následek delší klíč.
• Pravděpodobnost rozbití systému je ${ displaystyle 1 / p}$ a ${ displaystyle p přibližně 2 ^ {k}}$ tak roste k ztěžuje rozbití systému.

Výkon

Níže jsou uvedeny výsledky časování pro různé implementace MMH^[4] v roce 1997, navrhli Halevi a Krawczyk.

• 150 MHz PowerPC 604 RISC stroj se systémem AIX

• Stroj 150 MHz Pentium-Pro běží Windows NT

• Stroj 200 MHz Pentium-Pro běží Linux

Viz také

• UMAC
• VMAC
• Poly1305-AES

Reference