Hash založený na rychlém syndromu

FSB (Fast Syndrome-Based Hash Function) je sada kryptografických hašovacích funkcí vytvořená v roce 2003 a přihlášená v roce 2008 jako kandidát do soutěže SHA-3 [1] . Na rozdíl od mnoha v současnosti používaných hašovacích funkcí lze do určité míry prokázat kryptografickou sílu FSB. Síla FSB dokazuje, že prolomit FSB je stejně obtížné jako vyřešit nějaký NP-úplný problém známý jako dekódování regulárního syndromu. Ačkoli stále není známo, zda jsou NP-úplné problémy řešitelné v polynomiálním čase , obecně se předpokládá, že nejsou.

Během procesu vývoje bylo navrženo několik verzí FSB, z nichž poslední byla předložena v soutěži SHA-3, ale byla zamítnuta v prvním kole. Zatímco všechny verze FSB tvrdí, že jsou bezpečné , některé předběžné verze byly nakonec prolomeny [2] . Při vývoji nejnovější verze FSB byly zohledněny všechny zranitelnosti a v tuto chvíli zůstává algoritmus kryptograficky odolný vůči všem aktuálně známým útokům.

Na druhou stranu odolnost něco stojí. FSB je pomalejší než tradiční hashovací funkce a využívá poměrně hodně paměti RAM, takže je nepraktický v prostředích, kde je omezený. Navíc kompresní funkce používaná v FSB vyžaduje velkou velikost výstupní zprávy, aby byla zaručena šifrovací síla. Tento problém byl vyřešen v posledních verzích, kde je výstup komprimován funkcí Whirlpool . Ačkoli však autoři tvrdí, že přidání této poslední kontrakce nesníží stabilitu, znemožňuje ji formálně prokázat [3] .

Popis hashovací funkce

Kompresní funkce má parametry jako a . Tato funkce bude fungovat pouze se zprávami o délce .  - výstupní velikost. Navíc a musí být přirozená čísla  - binární logaritmus). Důvodem je , že chceme, aby to byla kompresní funkce, takže vstup musí být větší než výstup. Později použijeme Merkle-Damgardovu konstrukci k rozšíření vstupní domény pro zprávy libovolné délky.

Základem této funkce je (náhodně vybraná) binární matice , která interaguje se zprávou bitů násobením matice . Zde zakódujeme -bitovou zprávu jako vektor v -rozměrném vektorovém prostoru přes pole dvou prvků, takže výstupem bude zpráva o bitech.

Z bezpečnostních důvodů a také z důvodu rychlé hašovací frekvence se jako vstup do naší matice používají pouze „váha pravidelných slov“.

Definice

Zpráva se nazývá slovo o hmotnosti a délce , pokud se skládá z bitů a právě z těchto bitů jsou nenulové.

Slovo o hmotnosti a délce se nazývá pravidelné, pokud každý interval obsahuje právě jeden nenulový prvek pro všechny . To znamená, že pokud zprávu rozdělíme na w stejných částí, pak každá část obsahuje právě jeden nenulový prvek.

Funkce komprese

Existují přesně odlišná běžná slova o hmotnosti a délce , takže potřebujeme přesně ty bity dat, abychom tato běžná slova zakódovali. Opravte vzájemnou korespondenci mezi sadou dlouhých bitových řetězců a sadou běžných slov hmotnosti a délky a poté definujte funkci komprese FSB takto:

1. Vstupem je zpráva velikosti
2. Převod na běžné slovo hmotnosti a délky
3. Maticové násobení
4. Na výstupu získáme hash velikosti

Tato verze je obecně označována jako syndromická komprese. To je poměrně pomalé a v praxi se to provádí jiným a rychlejším způsobem, který se nazývá rychlá syndromická komprese. Rozdělíme na podmatice velikosti a stanovíme korespondenci jedna ku jedné mezi bitovými řetězci délky a sadou sekvencí čísel od 1 do . To je ekvivalentní korespondenci jedna ku jedné se sadou pravidelných slov délky a váhy , protože toto slovo můžeme vidět jako posloupnost čísel od 1 do . Kompresní funkce vypadá takto:

1. Vstupem je zpráva velikosti
2. Převede se na posloupnost čísel od 1 do
3. Přidáním příslušných sloupců matic získáte binární řetězec délky
4. Na výstupu získáme hash velikosti

Nyní můžeme použít Merkle-Damgardovu strukturu ke zobecnění kompresní funkce, takže vstup může mít libovolnou délku.

Příklad komprese

Počáteční podmínky :

Zprávu hašujeme pomocí matice , která je rozdělena na podmatice , , .

Algoritmus :

1. Příchozí zprávu rozdělíme na části délky a získáme , , .
2. Převedeme každý řetězec na číslo a dostaneme , , .
3. Z první podmatice vezmeme druhý sloupec, z druhého vezmeme první, ze třetího  - čtvrtý.
4. Přidejte vybrané sloupce a získejte výsledek: .

Bezpečnostní důkaz FSB

Konstrukce Merkle-Damgard zakládá své zabezpečení pouze na bezpečnosti použité kompresní funkce. Musíme tedy pouze ukázat, že kompresní funkce je odolná vůči kryptoanalýze .

Kryptografická hašovací funkce musí být zabezpečena třemi různými způsoby:

1. Odolnost prvního předobrazu: Vzhledem k hash h by mělo být těžké najít zprávu m takovou, že Hash( m )= h .
2. Druhý předobrazový odpor je: když dostaneme zprávu m 1 , mělo by být těžké najít zprávu m 2 takovou, že Hash ( m 1 ) = Hash ( m 2 ).
3. Odolnost proti kolizi: Mělo by být těžké najít dvě odlišné zprávy m 1 a m 2 takové, že Hash( m 1 )=Hash( m 2 ).

Stojí za zmínku, že pokud najdete druhý předobraz, můžete samozřejmě najít kolizi . To znamená, že pokud dokážeme, že náš systém je odolný proti kolizi, bude jistě zabezpečen proti nalezení druhého předobrazu.

Obtížné obvykle v kryptografii znamená něco jako „téměř jistě mimo dosah jakéhokoli protivníka, jehož narušení systému je třeba zabránit“, ale pojďme si tento pojem definovat přesněji. Budeme předpokládat: "doba provádění jakéhokoli algoritmu, který najde kolizi nebo předobraz, závisí exponenciálně na velikosti hodnoty hash." To znamená, že s relativně malými přírůstky k velikosti hashe se můžeme rychle dostat na vysokou úroveň kryptografické síly.

Odolnost předobrazu

Jak již bylo zmíněno dříve, kryptografická síla FSB závisí na úloze zvané pravidelné syndromické dekódování. Původně problém v teorii kódování , ale jeho NP-úplnost z něj udělala šikovnou aplikaci pro kryptografii. Je to speciální případ dekódování syndromu a je definován takto:

Dané matice dimenze a bitový řetězec délky tak, že existuje sada sloupců, jeden pro každý , které tvoří . Potřebujeme najít takovou sadu sloupců.

Ukázalo se, že tento problém je NP-úplný tím, že se vyhneme 3D shodě. Opět, ačkoli není známo, zda existují polynomiální algoritmy pro řešení časových NP-úplných problémů, žádný z nich není znám a nalezení jednoho by bylo obrovským objevem.

Je snadné vidět, že nalezení předobrazu daného hashe je přesně ekvivalentní tomuto problému, takže problém s předobrazem FSB musí být také NP-úplný.

Ještě musíme prokázat odolnost proti kolizi. K tomu potřebujeme další NP-úplnou variaci pravidelného syndromického kódování, nazývanou „biregular zero syndromic decoding“.

Odolnost proti kolizi

Jsou uvedeny matice rozměrů a bitový řetězec délky . Pak je zde sada sloupců, buď dva nebo žádný v každém , tvořící 0, kde . Potřebujeme najít takovou sadu sloupců. Ukázalo se, že tato metoda je NP-úplná, protože se vyhýbá 3D párování.

Stejně jako pravidelné syndromické dekódování je v podstatě ekvivalentní hledání regulárního slova tak, že , biregulární nulové syndromické dekódování je ekvivalentní hledání biregulárního slova , jako je . Biregulární slovo délky a váhy je bitový řetězec délky takový, že v každém intervalu jsou buď přesně dva záznamy 1, nebo žádný. Všimněte si, že 2-běžné slovo je prostě součet dvou běžných slov.

Předpokládejme, že jsme našli kolizi: Hash( m 1 ) = Hash ( m 2 ) pro . Pak můžeme najít dvě pravidelná slova a taková, že . Pak dostaneme , kde je součet dvou různých regulárních slov a musí to být bi-regulární slovo, jehož hash je nula, takže jsme vyřešili problém dekódování bi-regular null syndromu. Došli jsme k závěru, že nalezení kolizí v FSB je přinejmenším stejně obtížné jako řešení problému dekódování biregulárního nulového syndromu, a proto je algoritmus NP-úplný.

Nedávné verze FSB používaly kompresní funkci Whirlpool k další kompresi výstupu hašovací funkce. Přestože kryptografickou sílu v tomto případě nelze prokázat, autoři tvrdí, že tato poslední komprese ji nesnižuje. Všimněte si, že i kdyby bylo možné najít kolize ve Whirpoolu, stále by bylo nutné najít kolize předobrazu v původní funkci komprese FSB, aby bylo možné najít kolize ve FSB.

Příklady

Při řešení problému pravidelného syndromického dekódování jsme s ohledem na hašování jakoby v opačném směru. Pomocí stejných hodnot jako v předchozím příkladu dostaneme podblok a řetězec . V každém podbloku musíme najít jeden sloupec, takže budou . Očekávaná odpověď by tedy byla , , . To je notoricky obtížné vypočítat pro velké matice. Při biregulárním dekódování nulového syndromu chceme v každém podbloku najít ne jeden sloupec, ale buď dva, nebo žádný, aby vedly k (a ne k ). V příkladu bychom mohli použít druhý a třetí sloupec (počítáno od 0) z , žádný ze sloupců , nula a druhý z . Je možných více řešení, například bez použití některého ze sloupců z .

Lineární kryptoanalýza

Prokazatelné zabezpečení FSB znamená, že nalezení kolizí je NP-úplné. Důkazem je ale redukce na složitější problém. To však poskytuje pouze omezené záruky bezpečnosti, protože stále může existovat algoritmus, který snadno vyřeší problém pro podmnožinu daného prostoru. Například existuje metoda linearizace , kterou lze použít k získání kolizí během několika sekund na stolním počítači pro starší verze FSB s nárokovaným hodnocením bezpečnosti 2128 . Je ukázáno, že když je prostor zpráv zvolen určitým způsobem, hashovací funkce poskytuje minimální předobraz nebo odolnost proti kolizi.

Výsledky bezpečnosti v praxi

Tabulka ukazuje složitost nejznámějších útoků proti FSB:

Další vlastnosti

• Velikost vstupního a výstupního bloku hashovací funkce je plně škálovatelná.
• Rychlost lze upravit změnou počtu bitových operací používaných FSB na vstupní bit.
• Bezpečnost lze upravit úpravou výstupní velikosti.
• Špatné případy existují a při výběru matice je třeba postupovat opatrně .
• Matice použitá ve funkci smršťování může být v určitých případech obrovská.

Možnosti

To druhé může být problematické při použití FSB na zařízeních s relativně malou pamětí.

Tento problém byl vyřešen v roce 2007 v související hashovací funkci zvané IFSB (Improved Fast Syndrome Based Hash) [4] , která je stále prokazatelně bezpečná, ale spoléhá na poněkud silnější předpoklady.

V roce 2010 byl představen S-FSB, který má rychlost o 30 % rychlejší než FSB [5] .

V roce 2011 představili Daniel Julius Bernstein a Tanya Lange RFSB, která byla 10krát rychlejší než FSB-256 [6] . RFSB při běhu na stroji Spartan 6 FPGA dosahoval propustnosti až 5 Gbps [7] .

Poznámky

1. ↑ Augot, D.; Finiasz, M.; Sendrier, N. A Fast Provably Secure Cryptographic Hash Function (2003). Datum přístupu: 10. prosince 2015. Archivováno z originálu 3. března 2016. (neurčitý)
2. ↑ Saarinen, Markku-Juhani O. Linearization Attacks Against Syndrome Based Hashes (2007). Získáno 10. prosince 2015. Archivováno z originálu 4. března 2016. (neurčitý)
3. ↑ Finiasz, M.; Gaborit, P.; Sendrier, N. Vylepšené kryptografické hašovací funkce založené na rychlém syndromu (nepřístupný odkaz) (2007). Datum přístupu: 10. prosince 2015. Archivováno z originálu 3. března 2016. (neurčitý) 
4. ↑ Finiasz, M.; Gaborit, P.; Sendrier, N. Vylepšené kryptografické hašovací funkce založené na rychlém syndromu (2007). Datum přístupu: 12. prosince 2015. Archivováno z originálu 22. prosince 2015. (neurčitý)
5. ↑ Meziani M.; Dagdelen O.; CayrelPL; El Yousfi Alaoui SM S-FSB: Vylepšená varianta rodiny FSB Hash (nedostupný odkaz) (2010). Datum přístupu: 12. prosince 2015. Archivováno z originálu 22. prosince 2015. (neurčitý) 
6. ↑ Bernstein, DJ, Lange, T.; Peters C.; Schwabe P.;. Opravdu rychlé hašování založené na syndromu (2011). Získáno 12. prosince 2015. Archivováno z originálu 14. prosince 2014. (neurčitý)
7. ↑ Von Maurich, I.; Guneysu, T.;. Embedded Syndrome-Based Hashing (nedostupný odkaz) (2011). Datum přístupu: 12. prosince 2015. Archivováno z originálu 2. května 2015. (neurčitý)