SWIFFT

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 februari 2021; kontroller kräver 3 redigeringar .

SWIFFT
Utvecklare	Vadim Lyubashevsky, Daniel Michiancio, Chris Peikert, Alon Rosen
Skapad	2008
publiceras	2008
Sorts	hash-funktion

SWIFFT är en uppsättning kryptografiska hashfunktioner med beprövad säkerhet [1] [2] [3] . De är baserade på Fast Fourier Transform ( FFT ) och använder den LLL-reducerade basalgoritmen . Den kryptografiska säkerheten för SWIFFT-funktioner (i asymptotisk mening) [4] är matematiskt bevisad med hjälp av de rekommenderade parametrarna [5] . Att hitta kollisioner i SWIFFT är minst lika tidskrävande i värsta fall som att hitta korta vektorer i cykliska/ ideala gitter . Den praktiska tillämpningen av SWIFFT kommer att vara värdefull just i de fall där motståndet mot kollisioner är särskilt viktigt. Till exempel digitala signaturer, som måste förbli tillförlitliga under lång tid.

Denna algoritm ger en genomströmning på cirka 40 Mb/s på en Intel Pentium 4-processor med en klockfrekvens på 3,2 GHz [6] [1] . Det har gjorts forskning för att påskynda FFT, som används i SWIFFT [7] . Som ett resultat ökades hastigheten på algoritmen med mer än 13 gånger [6] . Denna implementering av SWIFFT visade sig vara snabbare än implementeringar av allmänt använda hashfunktioner [8] .

Vid tävlingen 2012 National Institute of Standards and Technology [2] föreslogs SWIFFTX (en modifiering av SWIFFT) som SHA-3 (för att ersätta den äldre SHA-2 och särskilt SHA-1 [9] ), men avvisades i första omgången [10] .

Beskrivning av arbetet

SWIFFT-funktionerna kan beskrivas som ett enkelt algebraiskt uttryck över någon polynomring [1] [11] . Funktionsfamiljen beror på tre huvudparametrar : låt vara en potens av 2, - ett litet heltal, och - inte nödvändigtvis ett primtal , men det är bättre att välja det primtal. Vi definierar det som en ring av formen . Till exempel, ringen av polynom i , vars koefficienter är heltal, är talet med vilket vi utför modulo division, och . Ett element från kan vara ett polynom av lägre grad med koefficienter från . $R$ $n$ $m>0$ $p>0$ $R$ $R=\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ $\alfa$ $sid$ $\alpha ^{n}+1$ $R$ $n$ $Z P}$

En definierad funktion i SWIFFT-familjen definieras som fasta ringelement , kallade multiplikatorer. Denna funktion över ringen kan skrivas i följande form: $m$ $a_{1},\ldots ,a_{m}\i R$ $R$ $R$

$\sum _{i=1}^{m}(a_{i}\cdot x_{i})$ ,

där är polynom med binära koefficienter som motsvarar ett binärt ingångsmeddelande av längd . $x_{1},\ldots ,x_{m}\i R$ $mn$

Operationsalgoritmen är som följer: [1] [12] [11]

Tagen är ett irreducerbart polynom över $\alfa$ $\mathbb {Z} [\alpha ]$
Ingången är ett meddelande av längd $M$ $mn$
$M$ omvandlas till en uppsättning polynom i en viss polynomring med binära koefficienter $m$ $pi}$ $R$
Fourierkoefficienter beräknas för varje $pi}$
Fasta Fourier-koefficienter ställs in beroende på SWIFFT-familjen $a_{i}$
Fourierkoefficienterna multipliceras i par med för varje $pi}$ $a_{i}$ $i$
Den inversa Fouriertransformen används för att erhålla högst gradpolynom $m$ $f_{i}$ $2n$
Beräknad modulo och . $f=\summa _{i=1}^{m}(f_{i})$ $sid$ $\alpha ^{n}+1$
$f$ konverteras till bitar och skickas till utgången $n\log(p)$

Den snabba Fourier-transformationen i steg 4 är lätt att vända. Det utförs för att uppnå förvirring - blandning av bitar som ges till ingången.
Den linjära kombinationen i steg 6 är förvirrande eftersom den komprimerar ingången.

Exempel

Specifika värden för parametrarna n , m och p väljs enligt följande: n = 64, m = 16, p = 257 [13] . För dessa parametrar kommer alla fasta komprimeringsfunktioner i familjen att acceptera ett meddelande med längden mn = 1024 bitar (128 byte) som indata. Utgången är i ett intervall som har storlek . Utdata kan representeras med 528 bitar (66 byte). $\mathbb {Z} _{p}^{n}$ $p^{n}=257^{64}$ $\mathbb {Z} _{p}^{n}$

Beräkning av resultatet av multiplikation av polynom

Det svåraste med att beräkna uttrycket ovan är att beräkna resultatet av multiplikation [1] [14] . Ett snabbt sätt att beräkna en given produkt är att använda faltningssatsen , som säger att under vissa förhållanden: $a_{i}\cdot x_{i}$

{\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}

Här betecknar Fouriertransformen , och operation innebär att multiplicera koefficienter med samma index. I allmänhet har faltningssatsen innebörden av faltning , inte multiplikation. Det kan dock visas att multiplikationen av polynom är en faltning. ${\mathcal {F}}$ $\cdot$ $*$

Snabb Fourier Transform

För att hitta Fouriertransformen använder vi Fast Fourier Transform (FFT), som tar [1] . Multiplikationsalgoritmen är som följer [14] : vi beräknar alla Fourierkoefficienter för alla polynom samtidigt med FFT. Vi multiplicerar sedan parvis de motsvarande Fourierkoefficienterna för de två polynomen. Efter använder vi den inversa FFT, varefter vi får ett polynom med grad som inte är högre än . $O(n\log(n))$ $2n$

Diskret Fouriertransform

Istället för den vanliga Fouriertransformen använder SWIFFT den Diskreta Fouriertransformen (DFT) [1] [14] . Den använder enhetsrötter i stället för komplexa enhetsrötter. Detta kommer att vara sant om det är ett ändligt fält och dess 2 :e enkla enhetsrötter finns i det givna fältet. Dessa villkor kommer att uppfyllas om vi tar ett sådant primtal som är delbart med . $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$ $sid$ $p-1$ $2n$

Val av alternativ

Parametrarna m , p , n måste uppfylla följande krav [15] :

n måste vara en tvåpotens
p måste vara ett primtal
p -1 måste vara delbart med 2 n
$\log(p)<$ m

Du kan till exempel ta följande parametrar: n =64, m =16, p =257. Vi tar genomströmningen på nivån 40 Mb/s [6] , säkerhet från sökandet efter kollisioner - operationer. $2^{106}$

Statistiska egenskaper

Universal hashing. SWIFFT-familjen av funktioner är universell [1] . Med andra ord, för vilken som helst annan fast och slumpmässigt vald funktion från familjen är sannolikheten för att likheten kommer att gälla omvänt proportionell mot värdet på det valda området. $x,x*$ $f$ $f(x)=f(x*)$
Regelbundenhet. Funktioner från SWIFFT-familjen av krympningsfunktioner är vanliga [1] .
entropigenerator. SWIFFT är en entropigenerator [1] . För hashtabeller och relaterade applikationer är det önskvärt att nycklarna för de värden som matas in i funktionen är enhetligt fördelade (eller nära enhetlig fördelning), även om ingångsvärdena är ojämnt fördelade. Hashfunktioner som beter sig på detta sätt kallas entropigeneratorer eftersom de kan göra ojämnt fördelade parametrar till (nästan) enhetlig utdata. Formellt har denna egenskap vanligtvis en familj av funktioner, från vilken en funktion valdes slumpmässigt.

Kryptografiska egenskaper och säkerhet

SWIFFT är inte en pseudo-slumpmässig funktion på grund av linjäritet [1] . För en godtycklig funktion från SWIFFT-familjen gäller följande: för två ingångsparametrar , sådana som också kan vara en ingångsparameter, . Uppfyllelsen av denna relation är inte lämplig för en slumpmässig funktion, och en angripare kan lätt skilja vår funktion från en slumpmässig. $f$ $x_{1}$ $x_{2}$ $x_{1}+x_{2}$ $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$

För SWIFFT-funktionsfamiljen har kryptografiskt motstånd mot kollisioner (i asymptotisk mening) bevisats under ett relativt måttligt antagande om komplexiteten i problemet med att hitta korta vektorer i cykliska/ideala gitter i värsta fall. Detta betyder att SWIFFT-familjen av funktioner också är resistent mot den andra förbildsattacken [4] [16] .

Teoretisk stabilitet

SWIFFT - Beprövade säkerhetskrypteringsfunktioner [1] [3] . Som i de flesta fall bygger beviset på funktioners säkerhet på att det matematiska problemet som används i funktionerna inte kan lösas i polynomtid. Det betyder att styrkan med SWIFFT bara ligger i det faktum att den är baserad på ett komplext matematiskt problem.

I fallet med SWIFFT ligger den bevisade säkerheten i problemet med att hitta korta vektorer i cykliska/ ideala gitter [17] . Det kan bevisas att följande påstående är sant: anta att vi har en algoritm som kan hitta funktionskollisioner för en slumpmässig version av SWIFFT erhållen från , i en möjlig tid med sannolikhet . Detta innebär att algoritmen bara fungerar på en liten men märkbar bråkdel av familjens funktioner. Sedan kan vi också hitta en algoritm som alltid kan hitta en kort vektor på vilket idealiskt gitter som helst över en ring under en möjlig tid beroende på och . Detta betyder att det inte är mindre svårt att hitta kollisioner i SWIFFT, problemet med att hitta korta vektorer i ett gitter över , för vilka det bara finns exponentiella algoritmer. $f$ $f$ $T$ $sid$ $f_{2}$ $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ $T_{2}$ $T$ $sid$ $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$

Praktisk hållbarhet

Författarna till denna hashfunktion undersökte den för sårbarheter för olika attacker och fann att attacken "födelsedagar" kräver minsta hashräkningsoperationer (2 106 ) för att hitta kollisioner. [18] [1] . Permutationsattacker kräver 2 448 räkningar för standardparametrar. En fullständig uppräkning av de möjliga värdena skulle kräva 2 528 hashberäkningar. Detta är vanligtvis tillräckligt för att göra en fiendeattack omöjlig.

Se även

Snabb Fourier Transform

Anteckningar

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 Lyubashevsky et al., 2008 .
↑ 12 Arbitman et al., 2008 .
↑ 1 2 Györfi et al., 2012 , sid. 2.
↑ 12 Arbitman et al., 2008 , sid. ett.
↑ Buchmann och Lindner 2009 , sid. 1-2.
↑ 1 2 3 Györfi et al., 2012 , sid. femton.
↑ Györfi et al., 2012 , sid. 15-16.
↑ Györfi et al., 2012 , sid. 16.
↑ TÄVLING PRE-SHA-3 . National Institute of Standards and Technology (15 april 2005). Arkiverad från originalet den 9 augusti 2017. (obestämd)
↑ Andra rundan kandidater . National Institute of Standards and Technology (19 januari 2010). Hämtad 14 februari 2010. Arkiverad från originalet 10 april 2012. (obestämd)
↑ 1 2 Györfi et al., 2012 , sid. 3.
↑ Arbitman et al., 2008 , sid. 4-5.
↑ Györfi et al., 2012 .
↑ 1 2 3 Györfi et al., 2012 , sid. fyra.
↑ Buchmann, Lindner, 2009 .
↑ Sarinay, 2010 , sid. 9.
↑ Arbitman et al., 2008 , sid. 10-11.
↑ Buchmann och Lindner 2009 , sid. 2.

Litteratur

Böcker

Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .

Artiklar

Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFT: A Modest Proposal for FFT Hashing (engelska) // 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: A Proposal for the SHA-3 Standard (engelska) - 2008.
Buchmann J. , Lindner R. Secure Parameters for SWIFFT (engelska) // Progress in Cryptology - INDOCRYPT 2009 : 10th International Conference on Cryptology i Indien, New Delhi, Indien, 13-16 december 2009. 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 (engelska) // Provable Security : 4th International Conference, ProvSec 2010, Malacca, Malaysia, 13-15 oktober 2010. 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.

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Hud Snefru Tiger Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA