Luffa (hashovací funkce)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. dubna 2014; kontroly vyžadují 16 úprav .

Luffa
Vývojáři	Dai Watanabe, Hisayoshi Sato, Christophe De Canniere
Vytvořeno	2008
zveřejněno	2008
Velikost hash	224, 256, 384, 512
Typ	hashovací funkce

Lúffa [1] (hashovací funkce, vyslovováno „luffa“) je kryptografický algoritmus (rodina algoritmů) pro hašování proměnné délky bitů, vyvinutý Dai Watanabe , Hisayoshi Sato z Hitachi Yokohama Research Laboratory a Christophe De Cannière ( Niderl. Christophe De Cannière ) z výzkumné skupiny COSIC ( en: COSIC ) Katolické univerzity v Lovani k účasti v soutěži [2] , US National Institute of Standards and Technology ( NIST ). Lúffa je variantou funkce houby navržené Guido Bertonim et al., jejíž kryptografická síla je založena pouze na náhodnosti základní permutace . Na rozdíl od původní funkce houby , Lúffa používá více paralelních permutací a funkcí vkládání zpráv.

Historie účasti v soutěži NIST SHA-3 [2]

9. prosince 2008 byl Luffa jedním z 51 kandidátů na vstup do prvního kola soutěže SHA-3 .
Ve dnech 25. – 28. února 2009 byla hašovací funkce představena na konferenci NIST .
24. července 2009 byl zveřejněn seznam [3] 14 kandidátů, kteří se dostali do druhého kola, na kterém byl i Luffa.
Ve dnech 23. – 24. srpna 2010 se konala konference [4] , na které byli zvažováni kandidáti [3] , kteří postoupili do druhého kola.
10. prosince 2010 bylo vyhlášeno 5 kandidátů posledního kola soutěže SHA-3 , Luffa ze soutěže vypadla kvůli nízké kryptografické síle kompresní funkce [5] .

Algoritmus Lúffa [6]

Zpracování zpráv se provádí pomocí řetězce funkcí kulatého míchání s pevnou vstupní a výstupní délkou, což je funkce houby . Řetězec se skládá z mezilehlých směšovacích bloků C' (kruhové funkce) a dokončovacího bloku C''. Kruhové funkce jsou tvořeny rodinou nelineárních permutací, tzv. krokovými funkcemi. Vstupem funkce prvního kola je : první blok zprávy a inicializační hodnoty , kde je počet permutací. Vstupní parametry -tého kola jsou : výstup předchozího kola a -tý blok zpráv . $(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)))$

Dokončení zprávy

Přidání zprávy o délce až násobku 256 bitů se provádí řetězcem , kde počet nul je určen z porovnání $M$ $l$ $1000\cdots 0$ $k$ $l+1+k\equiv 0\mod 256$

Inicializace

Kromě prvního bloku zprávy jsou na vstupu funkce prvního kola uvedeny vektory jako inicializační hodnoty . $M^{(1)}$ $V_{i}$

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

Kulatá funkce

Funkce zaokrouhlení je sekvenční aplikací funkce vkládání zpráv MI a permutační funkce P.

Funkce vkládání zpráv

Funkce vkládání zpráv může být reprezentována jako transformační matice přes kruh . Generování polynomu pole . $GF(2^{8})^{32}$ $f(x)=x^{8}+x^{4}+x^{3}+x+1$

Funkce vkládání zpráv $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}}$

kde čísla označují polynomy ${1,2,3,4}$ ${1,x,x+1,x^{2}}$

Funkce vkládání zpráv $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}}$

Funkce vkládání zpráv $w=5$

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

Permutační funkce

Funkce nelineární permutace má bitový vstup, délka sub-permutace je pevně stanovena ve specifikaci Lúffa [6] , ; počet permutací závisí na velikosti hashe a je uveden v tabulce. ${\displaystyle w\cdot n_{b))$ ${\displaystyle n_{b))$ $n_{b}=256$ $w$

Délka hash ${\displaystyle n_{h))$	Počet permutací $w$
224	3
256	3
384	čtyři
512	5

Permutační funkce je 8násobná iterace krokovací funkce přes blok získaný z funkce vkládání zpráv . Blok je reprezentován jako 8 32bitových slov: . Funkce krok se skládá ze 3 funkcí: SubCrumb, MixWord, AddConstant. $Qi}$ $MI$ $Qi}$ ${\displaystyle a_{0},a_{1},a_{2},a_{3},a_{4},a_{5},a_{6},a_{7))$

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

SubCrumb je funkce nahrazení l-tých bitů v nebo podél S-boxu , výsledkem provedení je nahrazení , index S-boxu se získá zřetězením odpovídajících bitů : , bity jsou nahrazeny odpovídajícími bity z podle na následující schéma: ${\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$ $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}||a_ {7,l}||a_{6,l}||a_{5,l}],0\leq l<32,$

MixWord

MixWord je lineární permutační funkce , jako vstup bere a ; výstupem jsou a získané algoritmem: $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 - otočit doleva o 2 bity)
${\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 - funkce pro přidání konstanty ${\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 ,čtyři$

Tabulka konstant je uvedena v příloze B Lúffovy specifikace [6] .

Dokončovací blok

Závěrečná fáze tvorby přehledu zpráv se skládá z postupných iterací funkce exit a funkce round s nulovým blokem zprávy 0x00 0 na vstupu. Funkce exit je XOR všech mezilehlých hodnot a výsledkem je 256bitové slovo . Při i -té iteraci je hodnota výstupní funkce určena jako $\cdots$ ${\displaystyle Z_{i))$

${\displaystyle Z_{i}=\bigoplus _{k=0}^{w-1}H_{k}^{(N+j)))$ , kde , pokud , jinak $j=i$ $N=1$ $j=i+1$

Označte 32bitovými slovy v , pak se výstup Lúffa postupně skládá . Symbol "||" znamená zřetězení. ${\displaystyle Z_{i,j))$ ${\displaystyle Z_{i))$ ${\displaystyle Z_{i,j))$

Délka hash ${\displaystyle n_{h))$	Hodnota hash $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))$

Hash Lúffa-224 je ve skutečnosti hash Lúffa-256 bez posledního 32bitového slova.

Testovací vektory [6]

Digesty zprávy „abc“ při různých velikostech hash .

	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

Kryptoanalýza

Během druhého kola soutěže SHA-3 Luffa-224 a Luffa-256 zpočátku vykazovaly nízkou kryptografickou sílu a pro úspěšný útok byly vyžadovány zprávy. Poté byl algoritmus upraven Dai Watanabe a byl pojmenován Luffa v.2. Luffa v.2 [5] změny : $2^{216}$

přidána funkce dokončení prázdného kola pro všechny velikosti hash
změněný S-blok
zvýšil počet opakování funkce kroku ze 7 na 8

Bart Preneel prezentoval úspěšný útok detekce kolizí [7] pro 4 kola funkce Luffa stepping pro hašovací operace a pro 5 kol, čímž ukázal konstrukční odolnost vůči diferenciální detekci kolizí. $2^{90}$ $2^{224}$

Výkon

V roce 2010 provedli Thomas Oliviera a Giulio Lopez úspěšný výzkum [8] o možnosti zvýšení výkonu původní implementace Luffa. Optimalizovaná implementace algoritmu má 20% zvýšení výkonu při výpočtu hash Luffa-512 při spuštění v 1 vláknu; pro Luffa-256/384 není zvýšení výkonu jednovláknové implementace v různých testech větší než 5 %. Výsledky testu jsou uvedeny v tabulce v cyklech na bajt :

Na 64bitových platformách bez SSE:

Implementace algoritmu	Luffa-256	Luffa-384	Luffa-512
Původní provedení 2009
Jednovláknová implementace	27	42	58
Thomas Oliviera 2010
Jednovláknová implementace	24	42	46
Vícevláknová implementace	dvacet	24	36

Pomocí SSE:

Implementace algoritmu	Luffa-256	Luffa-384	Luffa-512
Původní provedení 2009
Jednovláknová implementace	17	19	třicet
Thomas Oliviera 2010
Jednovláknová implementace	patnáct	16	24
Vícevláknová implementace	patnáct	osmnáct	25

Pro srovnání, implementace Keccak (vítěz soutěže SHA-3 ) v testech [9] na podobném procesoru pomocí SSE ukázala následující výsledky: Keccak-256 - 15 c/b, Keccak-512 - 12 c/b .

Poznámky

↑ Rodina hashovacích funkcí Luffa . Získáno 22. listopadu 2013. Archivováno z originálu dne 28. prosince 2013. (neurčitý)
↑ Soutěž 12 NIST sha-3 . Získáno 22. listopadu 2013. Archivováno z originálu 9. července 2011. (neurčitý)
↑ 1 2 Kandidáti druhého kola . Získáno 28. prosince 2013. Archivováno z originálu 10. dubna 2012. (neurčitý)
↑ Druhá konference kandidátů SHA-3 . Získáno 28. prosince 2013. Archivováno z originálu 12. ledna 2014. (neurčitý)
↑ 1 2 Zpráva o stavu druhého kola SHA-3 . Získáno 28. prosince 2013. Archivováno z originálu dne 14. března 2011. (neurčitý)
↑ 1 2 3 4 Specifikace Luffa V.2.01 . Získáno 29. listopadu 2013. Archivováno z originálu 20. února 2013. (neurčitý)
↑ Hledání kolize pro Reduced Luffa-256 v2 . Datum přístupu: 4. ledna 2014. Archivováno z originálu 20. února 2013. (neurčitý)
↑ Zlepšení výkonu Luffa Hash Algorithm . Získáno 28. prosince 2013. Archivováno z originálu dne 21. března 2014. (neurčitý)
↑ Skupina funkcí houby Keccak: Výkon softwaru . Datum přístupu: 4. ledna 2014. Archivováno z originálu 4. ledna 2014. (neurčitý)

Literatura

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

Zpráva o stavu druhého kola SHA-3 . - S. 19-20 .

Bart Preneel, Hirotaka Yoshida, Dai Watanabe. Hledání kolizí pro sníženou Luffa-256 v2 .

Thomaz Oliveira, Julio Lopez. Zlepšení výkonu algoritmu Luffa Hash Algorithm .

Odkazy

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga 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 Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA