Luffa (hash függvény)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2014. április 26-án felülvizsgált verziótól ; az ellenőrzések 16 szerkesztést igényelnek .

Luffa
Fejlesztők	Dai Watanabe, Hisayoshi Sato, Christophe De Canniere
Létrehozva	2008
közzétett	2008
Hash méret	224, 256, 384, 512
Típusú	hash függvény

A Lúffa [1] (kivonatoló függvény, ejtsd: „luffa”) egy kriptográfiai algoritmus (algoritmuscsalád) a változó bithosszúságú kivonatoláshoz , amelyet Dai Watanabe , Hisayoshi Sato , a Hitachi Yokohama Research Laboratory és Christophe De Cannière ( Niderl. Christophe De Cannière ) fejlesztettek ki. ) a Leuveni Katolikus Egyetem COSIC ( en: COSIC ) kutatócsoportjától , hogy részt vegyen a versenyen [2] , az US National Institute of Standards and Technology ( NIST ). A Lúffa a Guido Bertoni és munkatársai által javasolt szivacsfunkció egy változata , amelynek kriptográfiai erőssége csak az alapul szolgáló permutáció véletlenszerűségén alapul . Az eredeti szivacs funkcióval ellentétben a Lúffa több párhuzamos permutációt és üzenetbefecskendezési funkciót használ.

A NIST SHA-3 versenyen való részvétel története [2]

2008. december 9- én Luffa egyike volt annak az 51 jelöltnek, akik bekerültek az SHA-3 verseny első fordulójába .
2009. február 25-28- án a hash függvényt a NIST konferencián mutatták be .
2009. július 24- én közzétették a második fordulóba bejutott 14 jelöltből álló listát [3] , amelyen Luffa is szerepelt.
2010. augusztus 23-24- én konferenciát [4] tartottak , amelyen a második fordulóba továbbjutott jelölteket [3] mérlegelték.
2010. december 10- én az SHA-3 verseny utolsó fordulójának 5 jelöltjét hirdették ki, Luffa a tömörítési funkció alacsony kriptográfiai erőssége miatt kiesett a versenyből [5] .

Algoritmus Lúffa [6]

Az üzenetfeldolgozást kerek keverési funkciók lánca hajtja végre, rögzített bemeneti és kimeneti hosszúsággal, amely egy szivacsfunkció . A lánc C' közbenső keverőblokkokból (kerek funkciók) és egy C'' befejező blokkból áll. A körfüggvényeket nemlineáris permutációk családja, az úgynevezett lépésfüggvények alkotják. Az első kör függvény bemenete : az üzenet első blokkja és az inicializálási értékek , ahol a permutációk száma. A -edik kör bemeneti paraméterei : az előző kör kimenete és a -edik üzenetblokk . ${\megjelenítési stílus (i=1)}$ $(M^{(1)},V_{0},\ V_{1},\cdots ,\ V_{w-1})$ $M^{(1)}$ ${\displaystyle V_{0},\ V_{1},\cdots ,\ V_{w-1))$ $w$ $én$ $(M^{(i)},H_{0}^{(i-1)},\ H_{1}^{(i-1)},\cdots ,\ H_{w-1}^ {(i-1)})$ $(i-1)$ $én$ ${\displaystyle M^{(i)))$

Az üzenet befejezése

A legfeljebb 256 bites hosszúságú üzenet összeadását a karakterlánc hajtja végre , ahol a nullák számát az összehasonlításból határozzuk meg. $M$ $l$ $1000\cdots 0$ $k$ $l+1+k\equiv 0\mod 256$

Inicializálás

Az üzenet első blokkján kívül az első kör függvény bemenetén a vektorok inicializálási értékeket kapnak . $M^{(1)}$ $V_{i}$

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

Kerek funkció

A kerek függvény az MI üzenetinjektáló függvény és a P permutációs függvény szekvenciális alkalmazása.

Üzenetbefecskendezési funkciók

Az üzenetinjektáló függvény egy gyűrűn átívelő transzformációs mátrixként ábrázolható . Mezőpolinom generálása . $GF(2^{8})^{32}$ $f(x)=x^{8}+x^{4}+x^{3}+x+1$

Üzenetbefecskendezési funkciók $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}}$

ahol a számok rendre a polinomokat jelölik ${\megjelenítési stílus {1,2,3,4}}$ ${\megjelenítési stílus {1,x,x+1,x^{2}}}$

Üzenetbefecskendezési funkciók $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}}$

Üzenetbefecskendezési funkciók $w=5$

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

A permutációs függvény

A nemlineáris permutációs függvénynek bitbemenete van, az alpermutáció hossza a Lúffa specifikációban rögzített [6] , ; a permutációk száma a hash méretétől függ, és a táblázatban látható. ${\displaystyle w\cdot n_{b))$ ${\megjelenítési stílus n_{b))$ $n_{b}=256$ $w$

Hash hossza ${\megjelenítési stílus n_{h))$	Permutációk száma $w$
224	3
256	3
384	négy
512	5

A permutációs függvény a léptető függvény 8-szoros iterációja az üzenetinjektáló függvényből kapott blokkon keresztül . A blokk 8 32 bites szóként jelenik meg: . A lépés funkció 3 funkcióból áll: 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))$

Permutáció(a[8], j){ //Permutáció 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

A SubCrumb az l-edik bitek cseréjének funkciója az S-boxban vagy annak mentén , a végrehajtás eredménye a csere , az S-box indexet a megfelelő bitek összefűzésével kapjuk meg : , a biteket a megfelelő bitekkel helyettesítjük a következő sémához: ${\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}$ $én$ $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

A MixWord egy lineáris permutációs függvény, amely bemenetként és ; a kimenet a és , amelyet az algoritmussal kapunk: $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 - elforgatás balra 2 bittel)
${\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 – a konstans hozzáadására szolgáló függvény ${\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 ,négy$

Az állandók táblázatát a Lúffa specifikáció [6] B. függeléke tartalmazza .

Befejező blokk

Az üzenetkivonat kialakításának utolsó szakasza a kilépési függvény és a kerek függvény egymást követő iterációiból áll, a bemeneten 0x00 0 nulla üzenetblokkkal . A kilépési függvény az összes köztes érték XOR-je, és az eredmény egy 256 bites szó . Az i -edik iterációnál a kimeneti függvény értékét a következőképpen határozzuk meg $\cdots$ ${\displaystyle Z_{i))$

${\displaystyle Z_{i}=\bigoplus _{k=0}^{w-1}H_{k}^{(N+j)))$ , hol , ha , különben $j=i$ $N=1$ $j=i+1$

Jelölje 32 bites szavakkal -ban , akkor a Lúffa kimenete szekvenciálisan összeáll . "||" szimbólum az összefűzést jelenti. ${\displaystyle Z_{i,j))$ ${\displaystyle Z_{i))$ ${\displaystyle Z_{i,j))$

Hash hossza ${\megjelenítési stílus n_{h))$	Hash érték $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))$

A Lúffa-224 hash valójában a Lúffa-256 hash az utolsó 32 bites szó nélkül.

Tesztvektorok [6]

Az "abc" üzenet kivonatai különböző hash -méretekben .

	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

Kriptanalízis

Az SHA-3 verseny második fordulójában a Luffa-224 és a Luffa-256 kezdetben alacsony kriptográfiai erősséget mutatott, és üzenetekre volt szükség a sikeres támadáshoz. Ezt követően az algoritmust Dai Watanabe módosította, és a Luffa v.2 nevet kapta. Luffa v.2 [5] változások : $2^{216}$

hozzáadva az üres körkiegészítő funkciót minden hash mérethez
S-blokkot cseréltek
a lépésfüggvény ismétléseinek számát 7-ről 8-ra növelte

Bart Preneel sikeres ütközésészlelési támadást [7] mutatott be a Luffa léptető funkció 4 fordulójára hashelési műveletekre és 5 körre, így bemutatva a tervezési ellenállást a differenciális ütközésérzékeléssel szemben. $2^{90}$ $2^{224}$

Teljesítmény

2010 -ben Thomas Oliviera és Giulio Lopez sikeres kutatást [8] végzett a Luffa eredeti megvalósításának teljesítményének növelésének lehetőségéről. Az algoritmus optimalizált megvalósítása 20%-os teljesítménynövekedést eredményez a Luffa-512 hash kiszámításában, ha 1 szálban hajtják végre; a Luffa-256/384 esetében az egyszálú implementáció teljesítménynövekedése különböző tesztekben nem több, mint 5%. A teszt eredményeit a táblázat mutatja ciklusonként bájtonként :

SSE nélküli 64 bites platformokon:

Az algoritmus megvalósítása	Luffa-256	Luffa-384	Luffa-512
Eredeti megvalósítás 2009
Egyszálas megvalósítás	27	42	58
Thomas Oliviera 2010
Egyszálas megvalósítás	24	42	46
Többszálú megvalósítás	húsz	24	36

SSE használata:

Az algoritmus megvalósítása	Luffa-256	Luffa-384	Luffa-512
Eredeti megvalósítás 2009
Egyszálas megvalósítás	17	19	harminc
Thomas Oliviera 2010
Egyszálas megvalósítás	tizenöt	16	24
Többszálú megvalósítás	tizenöt	tizennyolc	25

Összehasonlításképpen, a Keccak ( az SHA-3 verseny győztese ) tesztekben [9] egy hasonló, SSE-t használó processzoron a következő eredményeket mutatta: Keccak-256 - 15 c/b, Keccak-512 - 12 c/b .

Jegyzetek

↑ A Hash Function Family Luffa . Letöltve: 2013. november 22. Az eredetiből archiválva : 2013. december 28.. (határozatlan)
↑ 12 NIST sha-3 verseny . Letöltve: 2013. november 22. Az eredetiből archiválva : 2011. július 9.. (határozatlan)
↑ 1 2 Második forduló jelöltjei . Letöltve: 2013. december 28. Az eredetiből archiválva : 2012. április 10.. (határozatlan)
↑ A második SHA-3 jelölt konferencia . Letöltve: 2013. december 28. Az eredetiből archiválva : 2014. január 12.. (határozatlan)
↑ 1 2 Állapotjelentés az SHA-3 második fordulójáról . Letöltve: 2013. december 28. Az eredetiből archiválva : 2011. március 14.. (határozatlan)
↑ 1 2 3 4 Luffa specifikáció V.2.01 . Letöltve: 2013. november 29. Az eredetiből archiválva : 2013. február 20.. (határozatlan)
↑ Ütközések keresése csökkentett Luffa-256 v2 esetén . Hozzáférés dátuma: 2014. január 4. Az eredetiből archiválva : 2013. február 20. (határozatlan)
↑ A Luffa Hash Algorithm teljesítményének javítása . Letöltve: 2013. december 28. Az eredetiből archiválva : 2014. március 21.. (határozatlan)
↑ A Keccak szivacs funkciócsalád: Szoftverteljesítmény . Hozzáférés időpontja: 2014. január 4. Eredetiből archiválva : 2014. január 4. (határozatlan)

Irodalom

Hisayoshi Sato, Dai Watanabe, Christophe De Canni'ere. Luffa v.2 specifikáció .

Állapotjelentés az SHA-3 második fordulójáról . - S. 19-20 .

Bart Preneel, Hirotaka Yoshida, Dai Watanabe. Ütközések keresése csökkentett Luffa-256 v2 esetén .

Thomaz Oliveira, Julio Lopez. A Luffa Hash Algorithm teljesítményének javítása .

Linkek

Hash függvények
Általános rendeltetésű	Adler-32 CRC Fletcher ellenőrző összeg FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH – Hash Tree jenkins hash hash összeg
Kriptográfia	Stribog GOST R 34.11-94 Öv BLAKE BMW CubeHash VISSZHANG edonkey2k FSB Fúga 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 Bőr Snefru Tigris Örvény
Kulcsgenerálási funkciók	bcrypt PBKDF2 scrypt Argon2 Lyra2
Csekkszám ( összehasonlítás )	Ellenőrző összeg Verhouff algoritmusa Hold algoritmus Damm algoritmus Vonalkód bankszámlák bankkártyák VAN SNILS OKPO ÓN OKATO ISBN OGRN és OGRNIP VIN
Hashes	A csekkszámok összehasonlítása Hitelesítési protokollok Vonalkód összehasonlítás Kriptográfia Mágneses kapcsolat Merkle aláírása ed2k URNA