Luffa (hash-funktio)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 26. huhtikuuta 2014 tarkistetusta versiosta . tarkastukset vaativat 16 muokkausta .

Luffa
Kehittäjät	Dai Watanabe, Hisayoshi Sato, Christophe De Canniere
Luotu	2008
julkaistu	2008
Hash-koko	224, 256, 384, 512
Tyyppi	hash-toiminto

Lúffa [1] (hash-funktio, lausutaan "luffa") on salausalgoritmi (algoritmien perhe) muuttuvan bitin pituuden hajauttamiseen , jonka ovat kehittäneet Dai Watanabe , Hisayoshi Sato Hitachi Yokohama Research Laboratorysta ja Christophe De Cannière ( Niderl. Christophe De Cannière) ) Leuvenin katolisen yliopiston COSIC -tutkimusryhmältä ( en: COSIC ) osallistuakseen kilpailuun [2] , US National Institute of Standards and Technology ( NIST ). Lúffa on muunnos Guido Bertonin ym . ehdottamasta sienifunktiosta , jonka kryptografinen vahvuus perustuu vain taustalla olevan permutaation satunnaisuuteen . Toisin kuin alkuperäinen sienitoiminto , Lúffa käyttää useita rinnakkaisia permutaatioita ja viestin injektiotoimintoja.

NIST SHA-3 -kilpailuun osallistumisen historia [2]

9. joulukuuta 2008 Luffa oli yksi 51 ehdokkaasta, jotka pääsivät SHA-3 -kilpailun ensimmäiselle kierrokselle .
25. -28.2.2009 hash-funktio esiteltiin NIST -konferenssissa .
24. heinäkuuta 2009 julkaistiin luettelo [3] 14:stä toiselle kierrokselle päässeestä ehdokkaasta, joka sisälsi Luffan.
23.- 24. elokuuta 2010 pidettiin konferenssi [4] , jossa tarkasteltiin toiselle kierrokselle päässeitä ehdokkaita [3] .
10. joulukuuta 2010 julkistettiin 5 ehdokasta SHA-3- kilpailun viimeiselle kierrokselle , Luffa putosi kilpailusta pakkaustoiminnon alhaisen kryptografisen vahvuuden vuoksi [5] .

Algoritmi Lúffa [6]

Viestien käsittely suoritetaan ketjulla pyöreitä sekoitustoimintoja, joilla on kiinteä tulo- ja lähtöpituus, joka on sienitoiminto . Ketju koostuu välisekoituslohkoista C' (pyöreät toiminnot) ja täydennyslohkosta C''. Pyöreät funktiot muodostuvat epälineaaristen permutaatioiden perheestä, niin kutsutuista askelfunktioista. Ensimmäisen kierroksen funktion syöte on : viestin ensimmäinen lohko ja alustusarvot , jossa on permutaatioiden lukumäärä. -: nnen kierroksen syöttöparametrit ovat : edellisen kierroksen lähtö ja -:nnen viestilohkon syöttöparametrit . ${\näyttötyyli (i=1)}$ $(M^{(1)},V_{0},\ V_{1},\cdots ,\ V_{w-1})$ $M^{(1)}$ ${\displaystyle V_{0},\ V_{1},\cdots ,\ V_{w-1))$ $w$ $i$ $(M^{(i)},H_{0}^{(i-1)},\ H_{1}^{(i-1)},\cdots ,\ H_{w-1}^ {(i-1)})$ $(i-1)$ $i$ ${\displaystyle M^{(i)))$

Viestin valmistuminen

Sanoman , jonka pituus on enintään 256 bitin kerrannainen, lisääminen suoritetaan merkkijonolla , jossa nollien lukumäärä määritetään vertailusta $M$ $l$ $1000\cdots 0$ $k$ $l+1+k\equiv 0\mod 256$

Alustus

Viestin ensimmäisen lohkon lisäksi vektorit annetaan alustusarvoina ensimmäisen kierroksen funktion sisääntulossa . $M^{(1)}$ $V_{i}$

$V_{i,j}$
i	j
i	0	yksi	2	3	neljä	5	6	7
0	0x6d251e69	0x44b051e0	0x4eaa6fb4	0xdbf78465	0x6e292011	0x90152df4	0xee058139	0xdef610bb
yksi	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
neljä	0x6c68e9be	0x5ec41e22	0xc825b7c7	0xaffb4363	0xf5df3999	0x0fc688f1	0xb07224cc	0x03e86cea

Pyöreä funktio

Pyöreä funktio on viestin injektiofunktion MI ja permutaatiofunktion P peräkkäinen sovellus.

Viestin lisäystoiminnot

Viestin injektiofunktio voidaan esittää muunnosmatriisina renkaan yli . Luodaan kenttäpolynomia . $GF(2^{8})^{32}$ $f(x)=x^{8}+x^{4}+x^{3}+x+1$

Viestin ruiskutustoiminnot $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}}$

jossa numerot vastaavat vastaavasti polynomeja ${\näyttötyyli {1,2,3,4}}$ ${\näyttötyyli {1,x,x+1,x^{2}}}$

Viestin ruiskutustoiminnot $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}}$

Viestin ruiskutustoiminnot $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&0A&0A&0A&08&0A&0A&0A&08&0&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&0A&0A&0A&08&0A&0A&0A&08&0 matrix\\H\\\\\\\\\\\\\\\{0} ^{(i-1)}\\H_{3}^{(i-1)}\\H_{4}^{(i-1)}\\M_{i}\ end{pmatrix}}$

Permutaatiofunktio

Epälineaarisella permutaatiofunktiolla on bittitulo, alipermutaation pituus on kiinteä Lúffa-spesifikaatiossa [6] , ; permutaatioiden määrä riippuu tiivisteen koosta ja näkyy taulukossa. ${\displaystyle w\cdot n_{b))$ ${\näyttötyyli n_{b))$ $n_{b}=256$ $w$

Hash pituus ${\näyttötyyli n_{h))$	Permutaatioiden määrä $w$
224	3
256	3
384	neljä
512	5

Permutaatiofunktio on 8-kertainen iteraatio askelfunktiosta viestin injektiofunktiosta saadun lohkon yli . Lohko esitetään 8 32-bittisenä sanana: . Vaihetoiminto koostuu kolmesta funktiosta: 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))$

Permutti(a[8], j){ //Permutaatio 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]); (k = 0; k < 4; k++) MixWord(a[k],a[k+4]); AddConstant(a, j, r); } } SubCrumb

SubCrumb on toiminto, jolla korvataan l:nnet bitit S-laatikossa tai sitä pitkin , suorituksen tulos on korvaaminen , S-boxin indeksi saadaan ketjuttamalla vastaavat bitit : , bitit korvataan vastaavilla bitteillä seuraavaan kaavaan: ${\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}$ $i$ ${\näyttötyyli a_{j,l))$ ${\displaystyle i=a_{3,l}||a_{2,l}||a_{1,l}||a_{0,l))$ ${\näyttötyyli x_{j,l))$ $Si]$

$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 on lineaarinen permutaatiofunktio, joka ottaa ja syötteenä ; tulos on ja , saatu algoritmilla: $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 - käännä vasemmalle 2 bittiä)
${\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 - toiminto, johon vakio lisätään ${\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 ,neljä$

Vakioiden taulukko on Lúffa-määrityksen [6] liitteessä B.

Täydennyslohko

Sanomatiivistelmän muodostuksen viimeinen vaihe koostuu peräkkäisistä exit-funktion ja pyöreän funktion iteraatioista, joiden sisääntulossa on nollaviestilohko 0x00 0. Poistumisfunktio on kaikkien väliarvojen XOR, ja tuloksena on 256-bittinen sana . i : nnessä iteraatiossa tulosfunktion arvo määritetään muodossa $\cdots$ ${\displaystyle Z_{i))$

${\displaystyle Z_{i}=\bigoplus _{k=0}^{w-1}H_{k}^{(N+j)))$ , missä , jos , muuten ${\näyttötyyli j=i}$ $N = 1$ $j=i+1$

Merkitään 32-bittisillä sanoilla , niin Lúffan tulosteet muodostuvat peräkkäin . Symboli "||" tarkoittaa ketjutusta. $Z_{i,j}$ ${\displaystyle Z_{i))$ $Z_{i,j}$

Hash pituus ${\näyttötyyli n_{h))$	Hash-arvo $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 on itse asiassa Lúffa-256 hash ilman viimeistä 32-bittistä sanaa.

Testivektorit [6]

Tiivistelmät viestistä "abc" eri hash -kooilla .

	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

Kryptanalysis

SHA-3- kilpailun toisella kierroksella Luffa-224 ja Luffa-256 osoittivat aluksi alhaista salausvoimakkuutta, ja onnistuneeseen hyökkäykseen vaadittiin viestejä. Sen jälkeen Dai Watanabe muokkasi algoritmia ja nimettiin Luffa v.2. Luffa v.2 [5] muutokset : $2^{216}$

lisätty tyhjän kierroksen täydennystoiminto kaikille hash-kokoille
vaihdettu S-lohko
lisäsi askelfunktion toistojen määrää 7:stä 8:aan

Bart Preneel esitteli onnistuneen törmäyksen havaitsemishyökkäyksen [7] 4 kierrokselle Luffa stepping -toiminnolle hajautustoimintoja varten ja 5 kierrosta, mikä osoitti mitoituskestävyyden differentiaalisen törmäyksen havaitsemiseen. $2^{90}$ $2^{224}$

Suorituskyky

Vuonna 2010 Thomas Oliviera ja Giulio Lopez tekivät menestyksekkään tutkimuksen [8] mahdollisuudesta parantaa Luffan alkuperäisen toteutuksen suorituskykyä. Algoritmin optimoidulla toteutuksella on 20 % suorituskyvyn lisäys Luffa-512 hashin laskennassa, kun se suoritetaan 1 säikeessä; Luffa-256/384:lle yksisäikeisen toteutuksen suorituskyvyn lisäys eri testeissä on korkeintaan 5 %. Testitulokset näkyvät taulukossa jaksoina tavua kohden :

64-bittisillä alustoilla ilman SSE:tä:

Algoritmin toteutus	Luffa-256	Luffa-384	Luffa-512
Alkuperäinen toteutus 2009
Yksisäikeinen toteutus	27	42	58
Thomas Oliviera 2010
Yksisäikeinen toteutus	24	42	46
Monisäikeinen toteutus	kaksikymmentä	24	36

SSE:n käyttäminen:

Algoritmin toteutus	Luffa-256	Luffa-384	Luffa-512
Alkuperäinen toteutus 2009
Yksisäikeinen toteutus	17	19	kolmekymmentä
Thomas Oliviera 2010
Yksisäikeinen toteutus	viisitoista	16	24
Monisäikeinen toteutus	viisitoista	kahdeksantoista	25

Vertailun vuoksi, Keccakin ( SHA-3-kilpailun voittaja ) käyttöönotto testeissä [9] samankaltaisella prosessorilla käyttäen SSE:tä osoitti seuraavat tulokset: Keccak-256 - 15 c/b, Keccak-512 - 12 c/b .

Muistiinpanot

↑ Hash Function Family Luffa . Haettu 22. marraskuuta 2013. Arkistoitu alkuperäisestä 28. joulukuuta 2013. (määrätön)
↑ 12 NIST sha-3 kilpailu . Haettu 22. marraskuuta 2013. Arkistoitu alkuperäisestä 9. heinäkuuta 2011. (määrätön)
↑ 1 2 Toisen kierroksen ehdokkaita . Haettu 28. joulukuuta 2013. Arkistoitu alkuperäisestä 10. huhtikuuta 2012. (määrätön)
↑ Toinen SHA-3-ehdokaskonferenssi . Haettu 28. joulukuuta 2013. Arkistoitu alkuperäisestä 12. tammikuuta 2014. (määrätön)
↑ 1 2 Tilaraportti SHA-3:n toisesta kierroksesta . Haettu 28. joulukuuta 2013. Arkistoitu alkuperäisestä 14. maaliskuuta 2011. (määrätön)
↑ 1 2 3 4 Luffa Specification V.2.01 . Haettu 29. marraskuuta 2013. Arkistoitu alkuperäisestä 20. helmikuuta 2013. (määrätön)
↑ Törmäysten etsiminen vähennetylle Luffa-256 v2:lle . Käyttöpäivä: 4. tammikuuta 2014. Arkistoitu alkuperäisestä 20. helmikuuta 2013. (määrätön)
↑ Luffa Hash Algorithmin suorituskyvyn parantaminen . Haettu 28. joulukuuta 2013. Arkistoitu alkuperäisestä 21. maaliskuuta 2014. (määrätön)
↑ Keccak-sienitoimintoperhe: Ohjelmiston suorituskyky . Käyttöpäivä: 4. tammikuuta 2014. Arkistoitu alkuperäisestä 4. tammikuuta 2014. (määrätön)

Kirjallisuus

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

Tilaraportti SHA-3:n toisesta kierroksesta . - S. 19-20 .

Bart Preneel, Hirotaka Yoshida, Dai Watanabe. Törmäysten etsiminen vähennetylle Luffa-256 v2:lle .

Thomaz Oliveira, Julio Lopez. Luffa Hash Algorithmin suorituskyvyn parantaminen .

Linkit

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga 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 Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA