SWIFFT

SWIFFT je sada kryptografických hašovacích funkcí s ověřenou bezpečností [1] [2] [3] . Jsou založeny na rychlé Fourierově transformaci ( FFT ) a používají algoritmus LLL-redukovaných bází . Kryptografické zabezpečení funkcí SWIFFT (v asymptotickém smyslu) [4] je matematicky prokázáno pomocí doporučených parametrů [5] . Nalezení kolizí v SWIFFT v nejhorším případě nezabere méně času než hledání krátkých vektorů v cyklických / ideální mřížky . Praktická aplikace SWIFFT bude cenná právě v těch případech, kde je obzvláště důležitá odolnost proti kolizím. Například digitální podpisy, které musí zůstat spolehlivé po dlouhou dobu.

Tento algoritmus poskytuje propustnost asi 40 Mb/s na procesoru Intel Pentium 4 s taktovací frekvencí 3,2 GHz [6] [1] . Byl proveden výzkum pro urychlení FFT, který se používá ve SWIFFT [7] . V důsledku toho se rychlost algoritmu zvýšila více než 13krát [6] . Tato implementace SWIFFT se ukázala být rychlejší než implementace široce používaných hashovacích funkcí [8] .

Na soutěži National Institute of Standards and Technology [2] v roce 2012 byl SWIFFTX (modifikace SWIFFT) navržen jako SHA-3 (nahradit starší SHA-2 a zejména SHA-1 [9] ), ale byl zamítnut v první kolo [10] .

Popis práce

Funkce SWIFFT lze popsat jako jednoduché algebraické vyjádření přes nějaký polynomiální okruh [1] [11] . Rodina funkcí závisí na třech hlavních parametrech : nechť je mocnina 2, - malé celé číslo a - nemusí být nutně prvočíslo , ale je lepší zvolit prvočíslo. Definujeme jej jako prstenec formuláře . Například okruh polynomů v , jehož koeficienty jsou celá čísla, je číslo, kterým provádíme modulo dělení, a . Prvek z může být polynom nižšího stupně s koeficienty od .

Definovaná funkce v rodině SWIFFT je definována jako pevné prstencové prvky , nazývané multiplikátory. Tato funkce přes prsten může být zapsána v následujícím tvaru:

,

kde jsou polynomy s binárními koeficienty odpovídajícími binární vstupní zprávě o délce .

Operační algoritmus je následující: [1] [12] [11]

1. Taken je neredukovatelný polynom nad
2. Vstupem je zpráva délky
3. se převede na množinu polynomů v určitém polynomickém kruhu s binárními koeficienty
4. Fourierovy koeficienty jsou vypočteny pro každý z nich
5. Pevné Fourierovy koeficienty jsou nastaveny v závislosti na rodině SWIFFT
6. Fourierovy koeficienty se násobí ve dvojicích s pro každý z nich
7. Inverzní Fourierova transformace se používá k získání polynomů nejvýše stupně
8. Vypočtené modulo a .
9. převedeny na bity a odeslány na výstup

• Rychlou operaci Fourierovy transformace v kroku 4 lze snadno obrátit. Provádí se za účelem dosažení zmatku - smíchání bitů přidaných na vstup.
• Lineární kombinace v kroku 6 je matoucí , protože komprimuje vstup.

Příklad

Konkrétní hodnoty pro parametry n , ma p se volí následovně: n = 64, m = 16, p = 257 [13] . Pro tyto parametry bude jakákoli pevná kompresní funkce rodiny přijímat jako vstup zprávu o délce mn = 1024 bitů (128 bajtů). Výstup je v rozsahu , který má velikost . Výstupní data mohou být reprezentována pomocí 528 bitů (66 bajtů).

Výpočet výsledku násobení polynomů

Nejtěžší na výpočtu výše uvedeného výrazu je vypočítat výsledek násobení [1] [14] . Rychlý způsob, jak vypočítat daný součin, je použít konvoluční teorém , který říká, že za určitých podmínek:

Zde označuje Fourierovu transformaci a operace znamená násobení koeficientů se stejným indexem. Obecně má konvoluční teorém význam konvoluce , nikoli násobení. Lze však ukázat, že násobení polynomů je konvoluce.

Rychlá Fourierova transformace

K nalezení Fourierovy transformace použijeme rychlou Fourierovu transformaci (FFT), která trvá [1] . Algoritmus násobení je následující [14] : všechny Fourierovy koeficienty pro všechny polynomy vypočítáme najednou pomocí FFT. Poté párově vynásobíme odpovídající Fourierovy koeficienty dvou polynomů. Poté, co použijeme inverzní FFT, po kterém dostaneme polynom stupně ne vyššího než .

Diskrétní Fourierova transformace

Místo obvyklé Fourierovy transformace používá SWIFFT diskrétní Fourierovu transformaci (DFT) [1] [14] . Používá kořeny jednoty v místo komplexních kořenů jednoty. To bude platit, pokud je konečné pole a jeho 2. jednoduché kořeny jednoty existují v daném poli. Tyto podmínky budou splněny, pokud vezmeme takové prvočíslo , které je dělitelné .

Výběr možností

Parametry m , p , n musí splňovat následující požadavky [15] :

• n musí být mocninou dvou
• p musí být prvočíslo
• p -1 musí být dělitelné 2 n
• m

Můžete si vzít například následující parametry: n =64, m =16, p =257. Propustnost bereme na úrovni 40 Mb/s [6] , zabezpečení z vyhledávání kolizí - operace.

Statistické vlastnosti

• Univerzální hashování. Rodina funkcí SWIFFT je univerzální [1] . Jinými slovy, pro jakoukoli jinou pevnou a náhodně vybranou funkci z rodiny je pravděpodobnost, že bude platit rovnost, nepřímo úměrná hodnotě zvoleného rozsahu.
• Pravidelnost. Funkce z rodiny zmenšovacích funkcí SWIFFT jsou regulérní [1] .
• generátor entropie. SWIFFT je generátor entropie [1] . U hashovacích tabulek a souvisejících aplikací je žádoucí, aby klíče pro hodnoty dodávané do funkce byly rovnoměrně rozmístěny (nebo blízko rovnoměrnému rozdělení), i když jsou vstupní hodnoty rozloženy nerovnoměrně. Hashovací funkce, které se chovají tímto způsobem, se nazývají generátory entropie, protože dokážou vykreslit nerovnoměrně rozložené parametry do (téměř) jednotného výstupu. Formálně má tato vlastnost obvykle rodinu funkcí, ze kterých byla náhodně vybrána jedna funkce.

Kryptografické vlastnosti a zabezpečení

• SWIFFT není pseudonáhodná funkce kvůli linearitě [1] . Pro libovolnou funkci z rodiny SWIFFT platí následující: pro dva vstupní parametry , které mohou být také vstupním parametrem, . Naplnění tohoto vztahu není pro náhodnou funkci vhodné a útočník naši funkci od náhodné snadno odliší.

• Pro rodinu funkcí SWIFFT byla prokázána kryptografická odolnost vůči srážkám (v asymptotickém smyslu) za relativně mírného předpokladu o složitosti problému hledání krátkých vektorů v cyklických/ideálních mřížkách v nejhorším případě. To znamená, že rodina funkcí SWIFFT je odolná i vůči druhému útoku preimage [4] [16] .

Teoretická stabilita

SWIFFT - Prověřené bezpečnostní kryptografické funkce [1] [3] . Jako ve většině případů je důkaz bezpečnosti funkcí založen na skutečnosti, že matematický problém použitý ve funkcích nelze vyřešit v polynomiálním čase. To znamená, že síla SWIFFT spočívá pouze v tom, že je založen na složitém matematickém problému.

V případě SWIFFT spočívá osvědčená bezpečnost v problému hledání krátkých vektorů v cyklických/ ideálních svazech [17] . Lze dokázat, že platí následující tvrzení: předpokládejme, že máme algoritmus, který dokáže najít kolize funkcí pro náhodnou verzi SWIFFT získanou z , v nějakém možném čase s pravděpodobností . To znamená, že algoritmus pracuje pouze na malém, ale znatelném zlomku funkcí rodiny. Pak můžeme také najít algoritmus , který vždy dokáže najít krátký vektor na jakékoli ideální mřížce nad prstencem v nějakém možném čase v závislosti na a . To znamená, že hledání kolizí ve SWIFFT není o nic méně obtížné, problém hledání krátkých vektorů v mřížce nad , pro které existují pouze exponenciální algoritmy.

Praktická životnost

Autoři této hashovací funkce ji zkoumali z hlediska zranitelnosti vůči různým útokům a zjistili, že útok „narozeniny“ vyžaduje k nalezení kolizí nejméně operací počítání hash (2 106 ). [18] [1] . Permutační útoky vyžadují 2 448 počtů standardních parametrů. Úplný výčet možných hodnot by vyžadoval 2 528 hašovacích výpočtů. To obvykle stačí k tomu, aby byl nepřátelský útok nemožný.

Viz také

• Rychlá Fourierova transformace

Poznámky

1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 Lyubashevsky a kol., 2008 .
2. ↑ 12 Arbitman a kol., 2008 .
3. ↑ 1 2 Györfi et al., 2012 , str. 2.
4. ↑ 12 Arbitman a kol., 2008 , s. jeden.
5. ↑ Buchmann a Lindner 2009 , str. 1-2.
6. ↑ 1 2 3 Györfi et al., 2012 , str. patnáct.
7. ↑ Györfi et al., 2012 , s. 15-16.
8. ↑ Györfi et al., 2012 , s. 16.
9. ↑ SOUTĚŽ PRE-SHA-3 . Národní institut pro standardy a technologie (15. dubna 2005). Archivováno z originálu 9. srpna 2017. (neurčitý)
10. ↑ Druhé kolo kandidátů . Národní institut pro standardy a technologie (19. ledna 2010). Získáno 14. února 2010. Archivováno z originálu 10. dubna 2012. (neurčitý)
11. ↑ 1 2 Györfi et al., 2012 , str. 3.
12. ↑ Arbitman a kol., 2008 , s. 4-5.
13. ↑ Györfi et al., 2012 .
14. ↑ 1 2 3 Györfi et al., 2012 , str. čtyři.
15. ↑ Buchmann, Lindner, 2009 .
16. ↑ Sarinay, 2010 , str. 9.
17. ↑ Arbitman a kol., 2008 , s. 10-11.
18. ↑ Buchmann a Lindner 2009 , str. 2.

Literatura

Knihy

• Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků.  - ISBN 5-89392-055-4 .

Články

• Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFT: A Modest Offer for FFT Hashing  (anglicky) // Fast Software Encryption - 2008. - Vol. 5086. - S. 54-72. doi:10.1007/ 978-3-540-71039-4_4
• Arbitman Y. , Dogon G. , Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFTX: Návrh na standard SHA-3  (anglicky) – 2008.
• Buchmann J. , Lindner R. Secure Parameters for SWIFFT  (anglicky) // Progress in Cryptology - INDOCRYPT 2009 : 10th International Conference on Cryptology in India, New Delhi, India, December 13-16, 2009. Proceedings / B. Roy , N Sendrier - Springer Berlin Heidelberg , 2009. - S. 1-17. - ISBN 978-3-642-10627-9 - doi:10.1007/978-3-642-10628-6_1
• Šarinay J. Interpreting Hash Function Security Proofs  (anglicky) // Provable Security : 4th International Conference, ProvSec 2010, Malacca, Malajsie, October 13-15, 2010. Proceedings / S. Heng , K. Kurosawa - Springer Berlin Heidelberg , 2010 . -Str. 119-132. — ISBN 978-3-642-16279-4 — doi:10.1007/978-3-642-16280-0_8
• Győrfi T. , Cret O. , Hanrot G. , Brisebarre N. Vysoce výkonná hardwarová architektura pro hashovací funkce SWIFFT / SWIFFTX  // Archiv kryptologie ePrint - Mezinárodní asociace pro kryptologický výzkum , 2012.