Jednosměrná funkce komprese - One-way compression function

V kryptografii , je kompresní funkce jednosměrný je funkce, která transformuje dvě pevné délky vstupy do výstupu pevnou délkou. Transformace je „jednosměrná“ , což znamená, že vzhledem k určitému výstupu je obtížné vypočítat vstupy, které se na tento výstup komprimují. Jednosměrné funkce komprese nesouvisejí s konvenčními algoritmy komprese dat, které lze naopak převést přesně (bezeztrátová komprese) nebo přibližně (ztrátová komprese) na původní data.

Jednosměrné kompresní funkce se například používají v konstrukci Merkle – Damgård uvnitř kryptografických hashovacích funkcí .

Jednosměrné kompresní funkce jsou často postaveny z blokových šifer . Některé metody, jak přeměnit jakoukoli normální blokovou šifru na funkci jednosměrné komprese, jsou Davies – Meyer , Matyas – Meyer – Oseas , Miyaguchi – Preneel (funkce komprimace s délkou jednoho bloku) a MDC-2/Meyer – Schilling , MDC-4 , Hirose (kompresní funkce s dvojitou délkou bloku). Tyto metody jsou podrobně popsány níže. ( MDC-2 je také název hashovací funkce patentované společností IBM .)

Komprese

Funkce komprese kombinuje dva vstupy s pevnou délkou a produkuje jeden výstup s pevnou délkou stejné velikosti jako jeden ze vstupů. To lze také vidět jako to, že funkce komprese transformuje jeden velký vstup s pevnou délkou na výstup s kratší pevnou délkou.

Například vstup A může mít 128 bitů, vstup B 128 bitů a jsou komprimovány dohromady na jeden výstup 128 bitů. To je ekvivalentní komprimaci jednoho 256bitového vstupu na jeden výstup 128 bitů.

Některé funkce komprese se nekomprimují na polovinu, ale na základě jiného faktoru. Například vstup A může mít 256 bitů a vstup B 128 bitů, které jsou komprimovány na jeden výstup 128 bitů. To znamená, že celkem 384 vstupních bitů je komprimováno dohromady na 128 výstupních bitů.

Míchání se provádí takovým způsobem, aby bylo dosaženo plného lavinového účinku . To znamená, že každý výstupní bit závisí na každém vstupním bitu.

Jednosměrný

Jednosměrná funkce je funkce, která je snadno vypočítat, ale těžko klenbou. Jednosměrná funkce komprese (také nazývaná hashovací funkce) by měla mít následující vlastnosti:

• Snadný výpočet: Pokud máte nějaké vstupy, je snadné vypočítat výstup.
• Odolnost před obrazem: Pokud útočník zná pouze výstup, mělo by být nemožné vypočítat vstup. Jinými slovy, vzhledem k výstupu by mělo být nemožné vypočítat vstup tak, že .${\ displaystyle h}$${\ displaystyle m}$${\ displaystyle \ operatorname {hash} (m) = h}$
• Odpor druhého preimage: Vzhledem k vstupu, jehož výstup je , by mělo být nemožné najít jiný vstup, který má stejný výstup , tzn .${\ displaystyle m_ {1}}$${\ displaystyle h}$${\ displaystyle m_ {2}}$${\ displaystyle h}$${\ displaystyle \ operatorname {hash} (m_ {1}) \ neq \ operatorname {hash} (m_ {2})}$
• Kolize odolnost: Mělo by být těžké najít nějaké dva různé vstupy, které stlačují ke stejnému výstupu, tj útočník by neměly být schopni najít pár zpráv taková, že . Vzhledem k narozeninovému paradoxu (viz také narozeninový útok ) existuje 50% šance, že v době, kdy je počet bitů ve výstupu funkce hash, může dojít ke kolizi . Útok na hashovací funkci by tedy neměl být schopen najít kolizi s méně než prací.${\ Displaystyle m_ {1} \ neq m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2^{n/2}}$${\ displaystyle n}$${\ displaystyle 2^{n/2}}$

V ideálním případě by někdo chtěl, aby „neproveditelnost“ v odolnosti vůči předobrazu a druhé odolnosti před obrazem znamenala práci o tom, kde je počet bitů na výstupu funkce hash. Obzvláště pro odolnost vůči druhému předobrazu je to však obtížný problém. ${\ displaystyle 2^{n}}$${\ displaystyle n}$

Stavba Merkle – Damgård

Běžné použití jednosměrných kompresních funkcí je v konstrukci Merkle – Damgård uvnitř kryptografických hashovacích funkcí. Tuto konstrukci používají nejpoužívanější hashovací funkce, včetně MD5 , SHA-1 (která je zastaralá) a SHA-2 .

Funkce hash musí být schopna zpracovat zprávu libovolné délky do výstupu s pevnou délkou. Toho lze dosáhnout rozdělením vstupu na řadu stejně velkých bloků a jejich postupným zpracováním pomocí funkce jednosměrné komprese. Funkce komprese může být buď speciálně navržena pro hašování, nebo může být vytvořena z blokové šifry.

Poslední zpracovaný blok by měl být také délkově polstrovaný , což je zásadní pro bezpečnost této konstrukce. Tato konstrukce se nazývá konstrukce Merkle – Damgård . Nejčastěji používané hashovací funkce, včetně SHA-1 a MD5 , mají tuto formu.

Použije-li se délka výplň (také nazývaný MD-posílení), lze útoky nenajde kolize rychlejší než narozeninový paradox ( , že velikost bloku v bitech), pokud jsou použitá funkce je kolize odolná. Konstrukce hash Merkle – Damgård proto snižuje problém nalezení správné hashovací funkce na nalezení správné kompresní funkce. ${\ displaystyle 2^{n/2}}$${\ displaystyle n}$${\ displaystyle f}$

Druhý útok před obrazem (vzhledem ke zprávě, kterou útočník najde pro uspokojení jiné zprávy, lze provést podle Kelseyho a Schneiera u zprávy -blokování v čase . Všimněte si, že složitost tohoto útoku dosahuje minima u dlouhých zpráv, když se blíží když jsou zprávy krátké. ${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2^{k}}$${\ Displaystyle k \ times 2^{n/2+1}+2^{n-k+1}}$${\ Displaystyle 2^{3n/4+2}}$${\ displaystyle k = 2^{n/4}}$${\ displaystyle 2^{n}}$

Stavba z blokových šifer

Jednosměrné kompresní funkce jsou často postaveny z blokových šifer.

Blokové šifry využívají (jako funkce jednosměrné komprese) dva vstupy pevné velikosti ( klíč a prostý text ) a vrací jeden jediný výstup ( šifrový text ), který má stejnou velikost jako vstupní prostý text.

Moderní blokové šifry jsou však jen částečně jednosměrné. To znamená, že vzhledem k prostému textu a šifrovacímu textu je nemožné najít klíč, který zašifruje prostý text do šifrového textu. Ale vzhledem k šifrovému textu a klíči lze odpovídající prostý text najít jednoduše pomocí dešifrovací funkce blokové šifry. Chcete-li tedy z blokové šifry udělat funkci jednosměrné komprese, je třeba přidat některé další operace.

Některé metody, jak přeměnit jakoukoli normální blokovou šifru na funkci jednosměrné komprese, jsou Davies – Meyer, Matyas – Meyer – Oseas, Miyaguchi – Preneel (funkce komprese s délkou jednoho bloku) a MDC-2, MDC-4, Hirose (dvojité -kompresní funkce délky bloku).

Kompresní funkce s délkou jednoho bloku produkují stejný počet bitů, jaké zpracovává základní bloková šifra. V důsledku toho produkují kompresní funkce s dvojitou délkou bloku dvojnásobek počtu bitů.

Pokud má bloková šifra velikost bloku řekněme 128 bitů, metody s délkou jednoho bloku vytvoří hashovací funkci, která má velikost bloku 128 bitů a vytvoří hash 128 bitů. Metody s délkou dvou bloků vytvářejí hash s dvojnásobnou velikostí hash ve srovnání s velikostí bloku použité šifry bloku. 128bitovou blokovou šifru lze tedy změnit na 256bitovou hashovací funkci.

Tyto metody jsou poté použity v konstrukci Merkle – Damgård k vytvoření skutečné hashovací funkce. Tyto metody jsou podrobně popsány níže.

Použití blokové šifry k vytvoření funkce jednosměrné komprese pro hashovací funkci je obvykle poněkud pomalejší než použití speciálně navržené jednosměrné kompresní funkce v hašovací funkci. Důvodem je, že všechny známé zabezpečené konstrukce provádějí plánování klíčů pro každý blok zprávy. Black, Cochran a Shrimpton ukázali, že není možné sestrojit jednosměrnou kompresní funkci, která by uskutečnila pouze jedno volání na blokovou šifru s pevným klíčem. V praxi je dosaženo rozumných rychlostí za předpokladu, že plánování klíčů vybrané blokové šifry není příliš náročná operace.

Ale v některých případech je to jednodušší, protože jedinou implementaci blokové šifry lze použít jak pro blokovou šifru, tak pro hashovací funkci. Může také ušetřit místo v kódu ve velmi malých vestavěných systémech, jako jsou například čipové karty nebo uzly v automobilech nebo jiných strojích.

Proto hash-rate nebo rate dává pohled na účinnost hashovací funkce založené na určité kompresní funkci. Rychlost iterované hashovací funkce nastiňuje poměr mezi počtem operací blokové šifry a výstupem. Přesněji řečeno, rychlost představuje poměr mezi počtem zpracovaných bitů vstupu , výstupní bitovou délkou blokové šifry a nezbytnými operacemi blokové šifry k produkci těchto výstupních bitů. Obecně platí, že použití menšího počtu operací blokové šifry má za následek lepší celkový výkon celé hashovací funkce, ale také to vede k menší hashovací hodnotě, která by mohla být nežádoucí. Sazba je vyjádřena vzorcem: ${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle s}$${\ displaystyle n}$

${\ displaystyle R_ {h} = {\ frac {\ left | m_ {i} \ right |} {s \ cdot n}}}$

Funkci hash lze považovat za bezpečnou pouze tehdy, jsou -li splněny alespoň následující podmínky:

• Bloková šifra nemá žádné speciální vlastnosti, které by ji odlišovaly od ideálních šifer, jako jsou slabé klíče nebo klíče, které vedou ke stejnému nebo souvisejícímu šifrování (pevné body nebo kolize klíčů).
• Výsledná velikost hash je dostatečně velká. Podle narozeninách zaútočit na úroveň zabezpečení ze dne 2. ⁸⁰ (obecně považovány za neproveditelné vypočítat dnes) je žádoucí, tedy velikost hash by měla být alespoň 160 bitů.
• Poslední blok je před hašováním řádně polstrován. (Viz konstrukce Merkle – Damgård .) Délkové polstrování je obvykle implementováno a zpracováváno interně ve specializovaných hashovacích funkcích, jako je SHA-1 atd.

Níže uvedené konstrukce: Davies – Meyer, Matyas – Meyer – Oseas, Miyaguchi – Preneel a Hirose byly podle analýzy black-boxu prokázány jako bezpečné . Cílem je ukázat, že jakýkoli útok, který lze nalézt, je za určitých předpokladů maximálně stejně účinný jako útok narozenin . Model black-box předpokládá, že je použita bloková šifra, která je náhodně vybrána ze sady obsahující všechny příslušné blokové šifry. V tomto modelu může útočník libovolně šifrovat a dešifrovat jakékoli bloky, ale nemá přístup k implementaci blokové šifry. Šifrovací a dešifrovací funkce jsou zastoupeny věštci, kteří obdrží dvojici buď prostého textu a klíče, nebo šifrový text a klíč. Věštci pak reagují náhodně zvoleným prostým nebo šifrovacím textem, pokud byl pár požádán poprvé. Oba sdílejí tabulku pro tyto triplety, pár z dotazu a odpovídající odpověď, a vrátí záznam, pokud byl dotaz přijat podruhé. Jako důkaz existuje algoritmus pro zjišťování kolizí, který vytváří náhodně vybrané dotazy na věštce. Algoritmus vrací hodnotu 1, pokud dvě odpovědi způsobí kolizi zahrnující hashovací funkci, která je vytvořena z kompresní funkce používající tuto blokovou šifru (0 else). Pravděpodobnost, že algoritmus vrátí 1, závisí na počtu dotazů, které určují úroveň zabezpečení.

Davies – Meyer

Jednobloková kompresní funkce Davies – Meyer napájí každý blok zprávy ( ) jako klíč k blokové šifře. Krmí předchozí hodnotu hash ( ) jako prostý text, který má být šifrován. Výstupní šifrovací text je pak také XORed (⊕) s předchozí hodnotou hash ( ) pro vytvoření další hodnoty hash ( ). V prvním kole, když neexistuje žádná předchozí hodnota hash, používá konstantní předem zadanou počáteční hodnotu ( ). ${\ displaystyle m_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {i}}$${\ displaystyle H_ {0}}$

V matematické notaci lze Daviese -Meyera popsat jako:

${\ displaystyle H_ {i} = E_ {m_ {i}} {(H_ {i-1})} \ oplus {H_ {i-1}}}$

Schéma má sazbu (k je velikost klíče):

${\ displaystyle R_ {DM} = {\ frac {k} {1 \ cdot n}} = {\ frac {k} {n}}}$

Pokud bloková šifra používá například 256bitové klíče, pak každý blok zprávy ( ) je 256bitovým blokem zprávy. Pokud stejná bloková šifra používá velikost bloku 128 bitů, pak jsou vstupní a výstupní hashovací hodnoty v každém kole 128 bitů. ${\ displaystyle m_ {i}}$

Variace této metody nahrazují XOR jakoukoli jinou skupinovou operací, například přidáním na 32bitová celá čísla bez znaménka.

Pozoruhodnou vlastností Davies -Meyerovy konstrukce je, že i když je podkladová bloková šifra zcela bezpečná, je možné pro konstrukci vypočítat pevné body : pro libovolnou lze najít hodnotu takovou, že : stačí nastavit . To je vlastnost, kterou náhodné funkce rozhodně nemají. Na této vlastnosti zatím nebyl založen žádný praktický útok, ale člověk by si měl být vědom této „vlastnosti“. Pevné body lze použít ve druhém útoku předobrazem (vzhledem ke zprávě útočník najde jinou zprávu, která Kelsey a Schneiera uspokojí pro zprávu -blok zprávy v čase . Pokud konstrukce neumožňuje snadné vytváření pevných bodů (např. Matyas – Meyer – Oseas nebo Miyaguchi – Preneel), pak lze tento útok provést včas. Všimněte si, že v obou případech je složitost výše, ale níže, pokud jsou zprávy dlouhé, a že když jsou zprávy kratší, složitost útoku se blíží . ${\ displaystyle m}$${\ displaystyle h}$${\ Displaystyle E_ {m} (h) \ oplus h = h}$${\ Displaystyle h = E_ {m}^{-1} (0)}$${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2^{k}}$${\ Displaystyle 3 \ times 2^{n/2+1}+2^{n-k+1}}$${\ Displaystyle k \ times 2^{n/2+1}+2^{n-k+1}}$${\ displaystyle 2^{n/2}}$${\ displaystyle 2^{n}}$${\ displaystyle 2^{n}}$

Zabezpečení konstrukce Davies – Meyer v modelu Ideal Cipher poprvé prokázal R. Winternitz.

Matyas – Meyer – Oseas

Jednosměrnou kompresní funkci jednoblokové délky Matyas – Meyer – Oseas lze považovat za duální (opačný) Davies – Meyer.

Krmí každý blok zprávy ( ) jako prostý text, který má být zašifrován. Výstupní šifrový text je pak také XORed (⊕) se stejným blokem zpráv ( ) pro vytvoření další hodnoty hash ( ). Předchozí klíčová hodnota ( ) je přivedena jako klíč k blokové šifře. V prvním kole, když neexistuje žádná předchozí hodnota hash, používá konstantní předem zadanou počáteční hodnotu ( ). ${\ displaystyle m_ {i}}$${\ displaystyle m_ {i}}$${\ displaystyle H_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {0}}$

Pokud má bloková šifra různé velikosti bloků a klíčů, bude mít hodnota hash ( ) nesprávnou velikost pro použití jako klíč. Šifra může mít také další speciální požadavky na klíč. Poté je hodnota hash nejprve přivedena funkcí, která má být převedena/vyplněna, aby se vešla jako klíč pro šifru. ${\ displaystyle H_ {i-1}}$${\ displaystyle g}$

V matematické notaci lze Matyas – Meyer – Oseas popsat jako:

${\ Displaystyle H_ {i} = E_ {g (H_ {i-1})} (m_ {i}) \ oplus m_ {i}}$

Schéma má sazbu:

${\ displaystyle R_ {MMO} = {\ frac {n} {1 \ cdot n}} = 1}$

Druhý útok před obrazem (vzhledem ke zprávě, kterou útočník najde pro uspokojení jiné zprávy ) lze provést podle Kelseyho a Schneiera pro zprávu -blok bloku zprávy včas . Všimněte si, že složitost je výše, ale níže, když jsou zprávy dlouhé, a že když se zprávy zkracují, přiblíží se složitost útoku . ${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2^{k}}$${\ Displaystyle k \ times 2^{n/2+1}+2^{n-k+1}}$${\ displaystyle 2^{n/2}}$${\ displaystyle 2^{n}}$${\ displaystyle 2^{n}}$

Miyaguchi – Preneel

Jednosměrná komprimační funkce jednoblokové délky Miyaguchi – Preneel je rozšířenou variantou Matyas – Meyer – Oseas. To nezávisle navrhli Shoji Miyaguchi a Bart Preneel .

Krmí každý blok zprávy ( ) jako prostý text, který má být zašifrován. Výstupní šifrovací text je potom XORed (⊕) se stejným blokem zpráv ( ) a poté také XORed s předchozí hodnotou hash ( ) pro vytvoření další hodnoty hash ( ). Předchozí hodnota hash ( ) je přiváděna jako klíč k blokové šifře. V prvním kole, když neexistuje žádná předchozí hodnota hash, používá konstantní předem zadanou počáteční hodnotu ( ). ${\ displaystyle m_ {i}}$${\ displaystyle m_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {0}}$

Pokud má bloková šifra různé velikosti bloků a klíčů, bude mít hodnota hash ( ) nesprávnou velikost pro použití jako klíč. Šifra může mít také další speciální požadavky na klíč. Poté je hodnota hash nejprve přivedena funkcí, která má být převedena/vyplněna, aby se vešla jako klíč pro šifru. ${\ displaystyle H_ {i-1}}$${\ displaystyle g}$

V matematické notaci lze Miyaguchi – Preneel popsat jako:

${\ Displaystyle H_ {i} = E_ {g (H_ {i-1})} (m_ {i}) \ oplus H_ {i-1} \ oplus m_ {i}}$

Schéma má sazbu:

${\ displaystyle R_ {MP} = {\ frac {n} {1 \ cdot n}} = 1}$

Role a mohou být přepínány, takže jsou šifrovány pod klíčem , což z této metody místo toho dělá rozšíření Davies – Meyer. ${\ displaystyle m_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle H_ {i-1}}$${\ displaystyle m_ {i}}$

Druhý útok před obrazem (vzhledem ke zprávě, kterou útočník najde pro uspokojení jiné zprávy ) lze provést podle Kelseyho a Schneiera pro zprávu -blok bloku zprávy včas . Všimněte si, že složitost je výše, ale níže, když jsou zprávy dlouhé, a že když se zprávy zkracují, přiblíží se složitost útoku . ${\ displaystyle m_ {1}}$${\ displaystyle m_ {2}}$${\ displaystyle \ operatorname {hash} (m_ {1}) = \ operatorname {hash} (m_ {2})}$${\ displaystyle 2^{k}}$${\ Displaystyle k \ times 2^{n/2+1}+2^{n-k+1}}$${\ displaystyle 2^{n/2}}$${\ displaystyle 2^{n}}$${\ displaystyle 2^{n}}$

Hirose

Jednosměrná kompresní funkce Hirose s dvoublokovou délkou se skládá z blokové šifry a permutace . To bylo navrženo Shoichi Hirose v roce 2006 a je založen na práci Mridul Nandi . ${\ displaystyle p}$

Používá blokovou šifru, jejíž délka klíče je větší než délka bloku , a vytváří hodnotu hash . Například kterýkoli z kandidátů AES s 192- nebo 256bitovým klíčem (a 128bitovým blokem). ${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle 2n}$

Každé kolo přijímá část zprávy, která je dlouhá v bitech, a používá ji k aktualizaci dvoubitových stavových hodnot a . ${\ displaystyle m_ {i}}$${\ displaystyle kn}$${\ displaystyle n}$${\ displaystyle G}$${\ displaystyle H}$

Nejprve je zřetězeno s, aby se vytvořil klíč . Poté se dvě hodnoty zpětné vazby aktualizují podle: ${\ displaystyle m_ {i}}$${\ displaystyle H_ {i-1}}$${\ displaystyle K_ {i}}$

• ${\ displaystyle G_ {i} = E_ {K_ {i}} (G_ {i-1}) \ oplus G_ {i-1}}$
• ${\ Displaystyle H_ {i} = E_ {K_ {i}} (p (G_ {i-1})) \ oplus p (G_ {i-1})}$

${\ displaystyle p (G_ {i-1})}$je libovolná permutace bez pevného bodu na anbitové hodnotě, typicky definovaná jako pro libovolnou nenulovou konstantu (všechny mohou být vhodnou volbou). ${\ displaystyle n}$${\ Displaystyle p (x) = x \ oplus c}$${\ displaystyle c}$

Každé šifrování se podobá standardní konstrukci Davies – Meyer. Výhodou tohoto schématu oproti jiným navrhovaným schématům s dvojitou blokovou délkou je, že obě šifrování používají stejný klíč, a proto může být sdíleno úsilí o plánování klíčů.

Konečný výstup je . Schéma má poměr relativní k šifrování zprávy šifrou. ${\ displaystyle H_ {t} || G_ {t}}$${\ textstyle R_ {Hirose} = {\ frac {kn} {2n}}}$

Hirose také poskytuje důkaz v ideálním šifrovacím modelu.

Sponge konstrukce

Konstrukci houby lze použít k vytvoření jednosměrných kompresních funkcí.

Viz také

• Whirlpool - Kryptografická hashovací funkce postavená pomocí konstrukce Miyaguchi – Preneel a blokové šifry podobné Square a AES .
• CBC-MAC , OMAC a PMAC -metody pro přeměnu blokových šifer na ověřovací kódy zpráv (MAC).

Reference

Citace

Prameny