Luffa (hash-funktion)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. april 2014; checks kræver 16 redigeringer .

Luffa
Udviklere	Dai Watanabe, Hisayoshi Sato, Christophe De Canniere
Oprettet	2008
offentliggjort	2008
Hash størrelse	224, 256, 384, 512
Type	hash funktion

Lúffa [1] (hash-funktion, udtales "luffa") er en kryptografisk algoritme (familie af algoritmer) til hashing af variabel bitlængde, udviklet af Dai Watanabe , Hisayoshi Sato fra Hitachi Yokohama Research Laboratory og Christophe De Cannière ( Niderl. Christophe De Cannière ) fra forskningsgruppen COSIC ( en: COSIC ) fra det katolske universitet i Leuven for at deltage i konkurrencen [2] , US National Institute of Standards and Technology ( NIST ). Lúffa er en variant af svampefunktionen foreslået af Guido Bertoni et al., hvis kryptografiske styrke kun er baseret på tilfældigheden af den underliggende permutation . I modsætning til den originale svampefunktion bruger Lúffa flere parallelle permutationer og beskedinjektionsfunktioner.

Historie om deltagelse i NIST SHA-3- konkurrencen [2]

Den 9. december 2008 var Luffa en af 51 kandidater til at deltage i første runde af SHA-3- konkurrencen .
Den 25.-28. februar 2009 blev hash-funktionen præsenteret på NIST- konferencen .
Den 24. juli 2009 blev en liste [3] med 14 kandidater, der nåede videre til anden runde, offentliggjort, som omfattede Luffa.
Den 23.-24. august 2010 blev der afholdt en konference [4] , hvor kandidater [3] som gik videre til anden runde blev overvejet.
Den 10. december 2010 blev 5 kandidater i den sidste runde af SHA-3- konkurrencen annonceret , Luffa droppede ud af konkurrencen på grund af den lave kryptografiske styrke af komprimeringsfunktionen [5] .

Algoritme Lúffa [6]

Beskedbehandling udføres af en kæde af runde blandefunktioner med en fast input- og outputlængde, som er en svampefunktion . Kæden består af mellemblandingsblokke C' (runde funktioner) og en færdiggørelsesblok C''. Runde funktioner er dannet af en familie af ikke-lineære permutationer, de såkaldte trinfunktioner. Indgangen til den første runde funktion er : den første blok af beskeden og initialiseringsværdier , hvor er antallet af permutationer. Indgangsparametrene for den -te runde er : outputtet fra den foregående runde og den -te beskedblok . $(i=1)$ $(M^{(1)},V_{0},\ V_{1},\cdots ,\ V_{w-1})$ $M^{(1)}$ ${\displaystyle V_{0},\ V_{1},\cdots ,\ V_{w-1))$ $w$ $jeg$ $(M^{(i)},H_{0}^{(i-1)},\ H_{1}^{(i-1)},\cdots ,\ H_{w-1}^ {(i-1)})$ $(i-1)$ $jeg$ ${\displaystyle M^{(i)))$

Færdiggørelse af meddelelsen

Tilføjelsen af en besked med længde op til et multiplum af 256 bit udføres af strengen , hvor antallet af nuller bestemmes ud fra sammenligningen $M$ $l$ $1000\cdots 0$ $k$ $l+1+k\equiv 0\mod 256$

Initialisering

Ud over den første blok af meddelelsen er vektorer givet som initialiseringsværdier ved input af den første runde funktion . $M^{(1)}$ $V_{i}$

$V_{i,j}$
jeg	j
jeg	0	en	2	3	fire	5	6	7
0	0x6d251e69	0x44b051e0	0x4eaa6fb4	0xdbf78465	0x6e292011	0x90152df4	0xee058139	0xdef610bb
en	0xc3b44b95	0xd9d2f256	0x70eee9a0	0xde099fa3	0x5d9b0557	0x8fc944b3	0xcf1ccf0e	0x746cd581
2	0xf7efc89d	0x5dba5781	0x04016ce5	0xad659c05	0x0306194f	0x666d1836	0x24aa230a	0x8b264ae7
3	0x858075d5	0x36d79cce	0xe571f7d7	0x204b1f67	0x35870c6a	0x57e9e923	0x14bcb808	0x7cde72ce
fire	0x6c68e9be	0x5ec41e22	0xc825b7c7	0xaffb4363	0xf5df3999	0x0fc688f1	0xb07224cc	0x03e86cea

Rund funktion

Den runde funktion er en sekventiel anvendelse af meddelelsesinjektionsfunktionen MI og permutationsfunktionen P.

Meddelelsesindsprøjtningsfunktioner

Meddelelsesindsprøjtningsfunktionen kan repræsenteres som en transformationsmatrix over en ring . Generering af feltpolynomium . $GF(2^{8})^{32}$ $f(x)=x^{8}+x^{4}+x^{3}+x+1$

Meddelelsesindsprøjtningsfunktioner $w=3$

${\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\end{pmatrix}}={\begin{pmatrix}3&2&2&1\\2&3&2&2\\2&2&3&4\end{pmatrix} }{\begin{pmatrix}H_{0}^{(i-1)}\\H_{1}^{(i-1)}\\H_{2}^{(i-1)}\\M_ {i}\end{pmatrix}}$

hvor tallene henholdsvis betegner polynomierne ${1,2,3,4}$ ${1,x,x+1,x^{2}}$

Meddelelsesindsprøjtningsfunktioner $w=4$

${\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\end{pmatrix}}={\begin{pmatrix}4&6&6&7&1\\7&4&6&6&2\\ 6&7&4&6&4\\6&6&7&4&8\end{pmatrix}}{\begin{pmatrix}H_{0}^{(i-1)}\\H_{1}^{(i-1)}\\H_{2}^{ (i-1)}\\H_{3}^{(i-1)}\\M_{i}\end{pmatrix}}$

Meddelelsesindsprøjtningsfunktioner $w=5$

${\begin{pmatrix}X_{0}\\X_{1}\\X_{2}\\X_{3}\\X_{4}\end{pmatrix}}={\begin{pmatrix} 0F&08&0A&0A&08&01\\08&0F&08&0A&0A&02\\0A&08&0F&08&0A&04\\0A&0A&08&0F&08&08\\08&0A&0A&08&0F&0A&08&0F&08&0A&04\\0A&0A&08&0F&08&08\\08&0A&0A&08&0F&0F&10_\end){0}\{0}^matrix}\{0_^){0}\}\{H}}\}\{H}\}\}\}\}\{0}^matrix}\}\}\}\{0}\end ^{(i-1)}\\H_{3}^{(i-1)}\\H_{4}^{(i-1)}\\M_{i}\ end{pmatrix}}$

Permutationsfunktionen

Den ikke-lineære permutationsfunktion har en bit-input, længden af sub-permutationen er fastsat i Lúffa-specifikationen [6] , ; antallet af permutationer afhænger af størrelsen af hashen og er vist i tabellen. ${\displaystyle w\cdot n_{b))$ ${\displaystyle n_{b))$ $n_{b}=256$ $w$

Hash længde ${\displaystyle n_{h))$	Antal permutationer $w$
224	3
256	3
384	fire
512	5

Permutationsfunktionen er en 8-fold iteration af trinfunktionen over blokken opnået fra meddelelsesinjektionsfunktionen . Blokken er repræsenteret som 8 32-bit ord: . Trinfunktionen består af 3 funktioner: SubCrumb, MixWord, AddConstant. $Q_{i}$ $MI$ $Q_{i}$ ${\displaystyle a_{0},a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7))$

Permute(a[8], j){ //Permutation Q_j for (r = 0; r < 8; r++){ Subcrumb(a[0],a[1],a[2],a[3]); Subcrumb(a[5],a[6],a[7],a[4]); for (k = 0; k < 4; k++) MixWord(a[k],a[k+4]); AddConstant(a, j, r); } } SubCrumb

SubCrumb er funktionen til at erstatte l-te bits i eller langs S-boksen , resultatet af udførelsen er erstatningen , S-box-indekset opnås ved at sammenkæde de tilsvarende bits : , bitsene erstattes med de tilsvarende bits fra iflg . til følgende ordning: ${\displaystyle a_{0},a_{1},a_{2},a_{3))$ ${\displaystyle a_{4},a_{5},a_{6},a_{7))$ ${\displaystyle S[16]={13,14,0,1,5,10,7,6,11,3,9,12,15,8,2,4))$ $a_{i}\rightarrow x_{i}$ $jeg$ ${\displaystyle a_{j,l))$ ${\displaystyle i=a_{3,l}||a_{2,l}||a_{1,l}||a_{0,l))$ ${\displaystyle x_{j,l))$ $S[i]$

$x_{3,l}||x_{2,l}||x_{1,l}||x_{0,l}=S[i]=S[a_{3,l}||a_ {2,l}||a_{1,l}||a_{0,l}],0\leq l<32$
$x_{4,l}||x_{7,l}||x_{6,l}||x_{5,l}=S[i]=S[a_{4,l}||a_ {7,l}||a_{6,l}||a_{5,l}],0\leq l<32,$

MixWord

MixWord er en lineær permutationsfunktion, den tager og , som input ; outputtet er og , opnået af algoritmen: $x_k$ $x_{k+4}$ $0\leq k<4$ $y_{k}$ $y_{k+4}$

${\displaystyle y_{k+4}=x_{k+4}\oplus x_{k))$
$y_{k}=x_{k}<<<2$ , (<<< 2 - drej til venstre med 2 bit)
${\displaystyle y_{k}=y_{k}\oplus y_{k+4))$
$y_{k+4}=y_{k+4}<<<14$
${\displaystyle y_{k+4}=y_{k+4}\oplus y_{k))$
$y_{k}=y_{k}<<<10$
${\displaystyle y_{k}=y_{k}\oplus y_{k+4))$
$y_{k+4}=y_{k+4}<<<1$

AddConstant

AddConstant - funktion til at tilføje en konstant til ${\displaystyle c_{j,k}^{(r-1)))$ ${\displaystyle a_{j,k}^{(r-1)))$

$a_{j,k}^{(r)}=a_{j,k}^{(r-1)}\oplus c_{j,k}^{(r-1)},k=0 ,fire$

En tabel med konstanter er givet i appendiks B til Lúffa-specifikationen [6] .

Fuldførelsesblok

Det sidste trin af meddelelsessammenslutningsdannelsen består af successive iterationer af exitfunktionen og rundfunktionen med en nul-meddelelsesblok 0x00 0 ved indgangen. Exit-funktionen er en XOR af alle mellemværdier, og resultatet er et 256-bit ord . Ved den i -te iteration bestemmes værdien af outputfunktionen som $\cdots$ ${\displaystyle Z_{i))$

${\displaystyle Z_{i}=\bigoplus _{k=0}^{w-1}H_{k}^{(N+j)))$ , hvor , hvis , ellers $j=i$ $N=1$ $j=i+1$

Betegn med 32-bit ord i , så er output fra Lúffa sekventielt sammensat . Symbol "||" står for sammenkædning. ${\displaystyle Z_{i,j))$ ${\displaystyle Z_{i))$ ${\displaystyle Z_{i,j))$

Hash længde ${\displaystyle n_{h))$	Hash værdi $H$
224	$Z_{0,0}\|\|\cdots \|\|Z_{0,6}$
256	${\displaystyle Z_{0,0}\|\|\cdots \|\|Z_{0,7))$
384	${\displaystyle Z_{0,0}\|\|\cdots \|\|Z_{0,6}\|\|Z_{1,0}\|\|\cdots \|\|Z_{1,3))$
512	${\displaystyle Z_{0,0}\|\|\cdots \|\|Z_{0,6}\|\|Z_{1,0}\|\|\cdots \|\|Z_{1,7))$

Lúffa-224-hash er faktisk Lúffa-256-hash uden det sidste 32-bit ord.

Test vektorer [6]

Sammendrag af meddelelsen "abc" ved forskellige hash- størrelser .

	224	256	384	512
Z0.0 _	0xf29311b8	0xf29311b8	0x9a7abb79	0xf4024597
Z0.1 _	0x7e9e40de	0x7e9e40de	0x7a840e2d	0x3e80d79d
Z0.2 _	0x7699be23	0x7699be23	0x423c34c9	0x0f4b9b20
Z 0,3	0xfbeb5a47	0xfbeb5a47	0x1f559f68	0x2ddd4505
Z0.4 _	0xcb16ea4f	0xcb16ea4f	0x09bdb291	0xb81b8830
Z0.5 _	0x5556d47c	0x5556d47c	0x6fb2e9ef	0x501bea31
Z0.6 _	0xa40c12ad	0xa40c12ad	0xfec2fa0a	0x612b5817
Z 0,7		0x764a73bd	0x7a69881b	0xaae38792
Z 1,0			0xe9872480	0x1dcefd80
Z 1,1			0xc635d20d	0x8ca2c780
Z 1,2			0x2fd6e95d	0x20aff593
Z 1,3			0x046601a7	0x45d6f91f
Z 1,4				0x0ee6b2ee
Z 1,5				0xe113f0cb
Z 1,6				0xcf22b643
Z 1,7				0x81387e8a

Krypteringsanalyse

Under anden runde af SHA-3- konkurrencen viste Luffa-224 og Luffa-256 i første omgang lav kryptografisk styrke, og meddelelser var nødvendige for et vellykket angreb. Derefter blev algoritmen modificeret af Dai Watanabe og fik navnet Luffa v.2. Luffa v.2 [5] ændringer : $2^{216}$

tilføjet tom rund færdiggørelsesfunktion for alle hashstørrelser
ændret S-blok
øgede antallet af gentagelser af trinfunktionen fra 7 til 8

Bart Preneel præsenterede et vellykket kollisionsdetektionsangreb [7] for 4 runder af Luffa stepping-funktionen til hashing-operationer og i 5 runder, hvilket viste designmodstanden mod differentiel kollisionsdetektion. $2^{90}$ $2^{224}$

Ydeevne

I 2010 udførte Thomas Oliviera og Giulio Lopez succesfuld forskning [8] om muligheden for at øge ydeevnen af den oprindelige implementering af Luffa. Den optimerede implementering af algoritmen har en ydelsesforøgelse på 20 % i beregningen af Luffa-512-hashen, når den udføres i 1 tråd; for Luffa-256/384 er ydeevnegevinsten for en enkelt-trådet implementering i forskellige tests ikke mere end 5 %. Testresultaterne er vist i tabellen i cyklusser pr. byte :

På 64-bit platforme uden SSE:

Implementering af algoritmen	Luffa-256	Luffa-384	Luffa-512
Oprindelig implementering 2009
Enkelt gevind implementering	27	42	58
Thomas Oliviera 2010
Enkelt gevind implementering	24	42	46
Multithreaded implementering	tyve	24	36

Brug af SSE:

Implementering af algoritmen	Luffa-256	Luffa-384	Luffa-512
Oprindelig implementering 2009
Enkelt gevind implementering	17	19	tredive
Thomas Oliviera 2010
Enkelt gevind implementering	femten	16	24
Multithreaded implementering	femten	atten	25

Til sammenligning viste implementeringen af Keccak (vinderen af SHA-3-konkurrencen ) i test [9] på en lignende processor ved brug af SSE følgende resultater: Keccak-256 - 15 c/b, Keccak-512 - 12 c/b .

Noter

↑ Hash-funktionsfamilien Luffa . Hentet 22. november 2013. Arkiveret fra originalen 28. december 2013. (ubestemt)
↑ 12 NIST sha-3 konkurrence . Hentet 22. november 2013. Arkiveret fra originalen 9. juli 2011. (ubestemt)
↑ 1 2 Anden runde kandidater . Hentet 28. december 2013. Arkiveret fra originalen 10. april 2012. (ubestemt)
↑ Den anden SHA-3-kandidatkonference . Hentet 28. december 2013. Arkiveret fra originalen 12. januar 2014. (ubestemt)
↑ 1 2 Statusrapport om anden runde af SHA-3 . Hentet 28. december 2013. Arkiveret fra originalen 14. marts 2011. (ubestemt)
↑ 1 2 3 4 Luffa-specifikation V.2.01 . Hentet 29. november 2013. Arkiveret fra originalen 20. februar 2013. (ubestemt)
↑ Find kollisioner for reduceret Luffa-256 v2 . Dato for adgang: 4. januar 2014. Arkiveret fra originalen 20. februar 2013. (ubestemt)
↑ Forbedring af ydeevnen af Luffa Hash Algorithm . Hentet 28. december 2013. Arkiveret fra originalen 21. marts 2014. (ubestemt)
↑ Keccak svampefunktionsfamilien: Softwareydelse . Dato for adgang: 4. januar 2014. Arkiveret fra originalen 4. januar 2014. (ubestemt)

Litteratur

Hisayoshi Sato, Dai Watanabe, Christophe De Canni'ere. Luffa v.2 specifikation .

Statusrapport om anden runde af SHA-3 . - S. 19-20 .

Bart Preneel, Hirotaka Yoshida, Dai Watanabe. Find kollisioner for reduceret Luffa-256 v2 .

Thomaz Oliveira, Julio Lopez. Forbedring af ydeevnen af Luffa Hash Algorithm .

Links

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge Grostl HAVAL Hamsi JH 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 Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE