SWIFFT

A SWIFFT kriptográfiai hash függvények készlete bizonyított biztonsággal [1] [2] [3] . Ezek a gyors Fourier-transzformáción ( FFT ) alapulnak, és az LLL-redukált bázisalgoritmust használják . A SWIFFT-függvények kriptográfiai biztonsága (aszimptotikus értelemben) [4] az ajánlott paraméterek [5] segítségével matematikailag bizonyított . Az ütközések megtalálása SWIFFT - ben a legrosszabb esetben legalább olyan időigényes , mint a rövid vektorok megtalálása ciklikus/ ideális rácsokban . A SWIFFT gyakorlati alkalmazása éppen azokban az esetekben lesz értékes, ahol különösen fontos az ütközésállóság. Például a digitális aláírások, amelyeknek hosszú ideig megbízhatónak kell maradniuk.  

Ez az algoritmus körülbelül 40 Mb/s átviteli sebességet biztosít egy 3,2 GHz-es órajelű Intel Pentium 4 processzoron [6] [1] . Kutatásokat végeztek az FFT felgyorsítására, amelyet a SWIFFT-ben használnak [7] . Ennek eredményeként az algoritmus sebessége több mint 13-szorosára nőtt [6] . A SWIFFT ezen megvalósítása gyorsabbnak bizonyult, mint a széles körben használt hash-függvények [8] .

A 2012-es National Institute of Standards and Technology [2] versenyen a SWIFFTX-et (a SWIFFT egy módosítása) SHA-3 néven javasolták (a régebbi SHA-2 és különösen az SHA-1 helyére [9] ), de a első kör [10] .

Munka leírása

A SWIFFT függvények egyszerű algebrai kifejezésként írhatók le valamilyen polinomgyűrűn [1] [11] . A függvénycsalád három fő paramétertől függ : legyen 2 hatványa, - egy kis egész szám, és - nem feltétlenül prímszám , de jobb, ha prímszámot választunk. A forma gyűrűjeként határozzuk meg . Például a -beli polinomok gyűrűje , amelyek együtthatói egész számok, az a szám, amellyel modulo osztást hajtunk végre, és . A -ból származó elem lehet alacsonyabb fokú polinom , melynek együtthatói -ból .

A SWIFFT családban egy meghatározott függvényt rögzített gyűrűs elemekként határoznak meg, amelyeket szorzóknak neveznek. Ez a függvény a gyűrű felett a következő formában írható fel:

,

ahol a hosszúságú bináris bemeneti üzenetnek megfelelő bináris együtthatójú polinomok vannak .

A műveleti algoritmus a következő: [1] [12] [11]

1. Taken egy irreducibilis polinom over
2. A bemenet egy hosszúságú üzenet
3. egy bizonyos polinomgyűrűben lévő polinomok halmazává alakul át bináris együtthatókkal
4. Mindegyikhez Fourier-együtthatót számítanak ki
5. A rögzített Fourier-együtthatók a SWIFFT családtól függően vannak beállítva
6. A Fourier - együtthatókat páronként megszorozzuk mindegyikre
7. Az inverz Fourier-transzformációt legfeljebb fokszámú polinomok előállítására használjuk
8. Számított modulo és .
9. bitekre konvertálva és a kimenetre küldve

• A gyors Fourier-transzformációs művelet a 4. lépésben könnyen visszafordítható. Az összetévesztés érdekében hajtják végre - a bemenethez adott bitek keverése.
• A 6. lépésben szereplő lineáris kombináció zavaró , mert tömöríti a bemenetet.

Példa

Az n , m és p paraméterek fajlagos értékeit a következőképpen választjuk ki: n = 64, m = 16, p = 257 [13] . Ezeknél a paramétereknél a család bármely rögzített tömörítési függvénye elfogad egy mn = 1024 bit (128 bájt) hosszúságú üzenetet bemenetként. A kimenet mérete tartományban van . A kimeneti adatok 528 bittel (66 bájttal) ábrázolhatók.

Polinomok szorzási eredményének kiszámítása

A fenti kifejezés kiszámításának legnehezebb része a szorzás eredményének kiszámítása [1] [14] . Egy adott szorzat kiszámításának gyors módja a konvolúciós tétel használata , amely kimondja, hogy bizonyos feltételek mellett:

Itt a Fourier-transzformációt jelöli , a művelet pedig az együtthatók azonos indexű szorzását jelenti. Általában a konvolúciós tétel jelentése konvolúció , nem szorzás. Kimutatható azonban, hogy a polinomok szorzása konvolúció.

Gyors Fourier transzformáció

A Fourier-transzformáció megtalálásához a gyors Fourier-transzformációt (FFT) használjuk, amely [1] . A szorzási algoritmus a következő [14] : az összes polinomra egyszerre számítjuk ki az összes Fourier-együtthatót az FFT segítségével. Ezután páronként megszorozzuk a két polinom megfelelő Fourier-együtthatóit. Miután az inverz FFT-t használjuk, ami után egy fokú polinomot kapunk, amely nem magasabb, mint .

Diszkrét Fourier transzformáció

A szokásos Fourier-transzformáció helyett a SWIFFT a diszkrét Fourier-transzformációt (DFT) [1] [14] használja . Az egység gyökereit használja az egység komplex gyökerei helyett. Ez akkor lesz igaz, ha egy véges mező , és az egység 2. n - edik egyszerű gyöke létezik az adott mezőben. Ezek a feltételek akkor teljesülnek, ha olyan prímszámot veszünk, amely osztható -vel .

Választási lehetőségek

Az m , p , n paramétereknek meg kell felelniük a következő követelményeknek [15] :

• n kettő hatványának kell lennie
• p prímszámnak kell lennie
• p -1 oszthatónak kell lennie 2 n -nel
• m

Vegyük például a következő paramétereket: n =64, m =16, p =257. Az átviteli sebességet 40 Mb / s [6] szintre vesszük , a biztonságot az ütközések keresésétől - műveletek.

Statisztikai tulajdonságok

• Univerzális hashelés. A SWIFFT függvénycsalád univerzális [1] . Más szavakkal, bármely , a családból eltérő rögzített és véletlenszerűen választott függvény esetén annak valószínűsége, hogy az egyenlőség fennáll, fordítottan arányos a választott tartomány értékével.
• Rendszeresség. A SWIFFT zsugorító függvénycsaládból származó függvények szabályosak [1] .
• entrópia generátor. A SWIFFT egy entrópiagenerátor [1] . A hash táblák és a kapcsolódó alkalmazások esetében kívánatos, hogy a függvénybe betáplált értékek kulcsai egyenletesen legyenek elosztva (vagy közel az egyenletes eloszláshoz), még akkor is, ha a bemeneti értékek egyenlőtlenül oszlanak el. Az így viselkedő hash-függvényeket entrópiagenerátoroknak nevezzük, mivel az egyenlőtlen eloszlású paramétereket (majdnem) egyenletes kimenetté tudják renderelni. Formálisan ennek a tulajdonságnak általában van egy függvénycsaládja, amelyek közül egy függvényt véletlenszerűen választottak ki.

Kriptográfiai tulajdonságok és biztonság

• A SWIFFT nem pszeudo-véletlen függvény a linearitás miatt [1] . A SWIFFT család tetszőleges függvényére a következő igaz: két bemeneti paraméterre , amelyek bemeneti paraméterek is lehetnek, . Ennek az összefüggésnek a teljesítése nem alkalmas véletlen függvényre, és a támadó könnyen meg tudja különböztetni a mi funkciónkat a véletlentől.

• A SWIFFT függvénycsalád esetében az ütközésekkel szembeni kriptográfiai ellenállás (aszimptotikus értelemben) bebizonyosodott egy viszonylag mérsékelt feltételezés mellett, amely a legrosszabb esetben a ciklikus/ideális rácsokban rövid vektorok megtalálásának problémája bonyolultságára vonatkozik. Ez azt jelenti, hogy a SWIFFT függvénycsalád a második preimage támadásnak is ellenáll [4] [16] .

Elméleti stabilitás

SWIFFT – Bizonyított biztonságú kriptográfiai funkciók [1] [3] . Mint a legtöbb esetben, a függvények biztonságának bizonyítása azon alapul, hogy a függvényekben használt matematikai probléma nem oldható meg polinomiális időben. Ez azt jelenti, hogy a SWIFFT ereje csak abban rejlik, hogy összetett matematikai problémán alapul.

A SWIFFT esetében a bizonyított biztonság abban rejlik, hogy ciklikus/ ideális rácsokban rövid vektorokat találunk [17] . Bebizonyítható, hogy igaz a következő állítás: tegyük fel, hogy van egy algoritmusunk, amely függvényütközéseket talál a SWIFFT egy véletlenszerű változatára, amely -ből származik , bizonyos időn belül valószínűséggel . Ez azt jelenti, hogy az algoritmus a család funkcióinak csak egy kis, de észrevehető hányadán működik. Ekkor találhatunk egy olyan algoritmust is , amely mindig képes egy rövid vektort találni bármely ideális rácson egy gyűrű felett bizonyos időn belül attól függően, hogy és . Ez azt jelenti, hogy az ütközések megtalálása SWIFFT-ben nem kevésbé nehéz, a rövid vektorok megtalálásának problémája a feletti rácsban , amelyre csak exponenciális algoritmusok léteznek.

Praktikus tartósság

Ennek a hash-függvénynek a szerzői megvizsgálták a különféle támadásokkal szembeni sebezhetőségeket, és megállapították, hogy a „születésnapi” támadáshoz van szükség a legkevesebb hash-számlálási műveletre (2 106 ) az ütközések megtalálásához. [18] [1] . A permutációs támadásokhoz 2448 számlálás szükséges a szabványos paraméterekhez. A lehetséges értékek teljes felsorolásához 2528 hash-számításra lenne szükség. Ez általában elég ahhoz, hogy lehetetlenné tegye az ellenséges támadást.

Lásd még

• Gyors Fourier transzformáció

Jegyzetek

1. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 Lyubashevsky et al., 2008 .
2. ↑ 12 Arbitman et al., 2008 .
3. ↑ 1 2 Györfi et al., 2012 , p. 2.
4. ↑ 12 Arbitman et al., 2008 , p. egy.
5. ↑ Buchmann és Lindner 2009 , p. 1-2.
6. ↑ 1 2 3 Györfi et al., 2012 , p. tizenöt.
7. ↑ Györfi et al., 2012 , p. 15-16.
8. ↑ Györfi et al., 2012 , p. 16.
9. ↑ PRE-SHA-3 VERSENY . Nemzeti Szabványügyi és Technológiai Intézet (2005. április 15.). Az eredetiből archiválva : 2017. augusztus 9. (határozatlan)
10. ↑ Második forduló jelöltjei . Nemzeti Szabványügyi és Technológiai Intézet (2010. január 19.). Letöltve: 2010. február 14. Az eredetiből archiválva : 2012. április 10.. (határozatlan)
11. ↑ 1 2 Györfi et al., 2012 , p. 3.
12. ↑ Arbitman et al., 2008 , p. 4-5.
13. ↑ Györfi et al., 2012 .
14. ↑ 1 2 3 Györfi et al., 2012 , p. négy.
15. ↑ Buchmann, Lindner, 2009 .
16. ↑ Sarinay, 2010 , p. 9.
17. ↑ Arbitman et al., 2008 , p. 10-11.
18. ↑ Buchmann és Lindner 2009 , p. 2.

Irodalom

Könyvek

• Schneier B. Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M .: Triumph, 2002. - 816 p. - 3000 példányban.  - ISBN 5-89392-055-4 .

Cikkek

• Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFT: A Modest Proposal for FFT Hashing  (angol) // Fast Software Encryption - 2008. - Vol. 5086. - P. 54-72. doi:10.1007/ 978-3-540-71039-4_4
• Arbitman Y. , Dogon G. , Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFTX: A Proposal for the SHA-3 Standard  (angol) - 2008.
• Buchmann J. , Lindner R. Secure Parameters for SWIFFT  (angol) // Progress in Cryptology - INDOCRYPT 2009 : 10. International Conference on Cryptology in India, New Delhi, India, 2009. december 13-16. Proceedings / B. Roy , N Sendrier - Springer Berlin Heidelberg , 2009. - P. 1-17. - ISBN 978-3-642-10627-9 - doi:10.1007/978-3-642-10628-6_1
• Šarinay J. Interpreting Hash Function Security Proofs  (angol) // Provable Security : 4th International Conference, ProvSec 2010, Malacca, Malaysia, 2010. október 13-15. Proceedings / S. Heng , K. Kurosawa - Springer Berlin Heidelberg , 2010. -P. 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. High-Throughput Hardware Architecture for the SWIFFT / SWIFFTX Hash Functions  // Cryptology ePrint Archive - International Association for Cryptologic Research , 2012.