Tigris (hash függvény)

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2013. március 13-án áttekintett verziótól ; az ellenőrzések 20 szerkesztést igényelnek .

A Tiger egy kriptográfiai hash függvény , amelyet Ros Anderson és Eli Biham fejlesztett ki 1995-ben.

A Tigert úgy tervezték, hogy különösen gyorsan fusson 64 bites számítógépeken. A Tigernek nincs szabadalmi korlátozása, szabadon használható mind a referencia megvalósítással, mind annak módosításaival. A hash érték mérete 192 bit (Tiger/192), bár vannak rövidebb verziók is az SHA-1 (Tiger/160) és az MD4 , MD5 , RIPEMD, Snefru (Tiger/128) kompatibilitás érdekében. Működési sebesség - 132 Mbps (egy Alpha 7000 processzoron tesztelve, 660-as modell). A modern processzorokon sokkal gyorsabb (még 32 bites AMD Sempron 3000+-on tesztelve is körülbelül 225 Mbps).

A Tiger2 a Tiger egy olyan verziója, amely csak az MD5 / SHA-1- hez hasonló bit-hozzáadási algoritmusban különbözik a fő verziótól . A Tiger2 tesztvektorai elérhetők.

Eredet

Az algoritmust 1995-ben fejlesztette ki Ross Anderson és Eli Biham. Ezt az időt az jellemezte, hogy a népszerű MD4 és Snefru hash függvényeknél már találtak ütközéseket . Ez utóbbiak a szerzők szerint megkérdőjelezték származékaik, például az MD5 és a Snefru-8 megbízhatóságát . A Tiger fejlesztésének fő céljai a következők voltak:

biztonság ;
gyors munka új 64 bites processzorokon, ésszerű sebességgel a 32 biteseken;
az MD és SHA sorozat lehetséges cseréje.

Algoritmus

A felhasznált S-boxok száma 4. Az S-box 8 bitet konvertál 64 bitessé. Vagyis mindegyikben 256 64 bites szó van, és az S-boxok tárolásához szükséges teljes memóriamennyiség 4*256*8 = 8192 = 8 KB. Ehhez a legtöbb processzor gyorsítótára is elegendő, bár mikrokontrollereken nehézkes lehet megvalósítani.

Az MD4 családhoz hasonlóan az üzenethez egy "1" bit kerül hozzáadásra, amelyet nullák követnek. A bemeneti adatok n darab 512 bites blokkra vannak osztva.

Válassza ki az első 512 bites blokkot. Ez a blokk nyolc 64 bites szóra van osztva: x0, x1, ..., x7. A bájtok sorrendje little -endian .

Három 64 bites regiszter indul kezdeti értékekkel (hash érték ): $h_{0}$

a = 0x0123456789ABCDEF b=0xFEDCBA9876543210 c = 0xF096A5B4C3B2E187

Most, hogy értékről értékre váltson , a következő műveleteket kell végrehajtani: $Szia}$ $h_{{i+1}}$

save_abc
pass(a,b,c,5)
kulcs_ütemezés
pass(c, a, b, 7)
kulcs_ütemezés
pass(b, c, a,9)
előrecsatolás

Itt save_abc menti az értéket : $Szia}$

aa = a bb = b cc=c

pass(a, b, c, mul) jelentése:

kerek(a,b,c,x0,mul) kerek(b,c,a,x1,mul) kerek(c,a,b,x2,mul) kerek (a,b,c,x3,mul) kerek (b,c,a,x4,mul) kerek (c,a,b,x5,mul) kerek (a,b,c,x6,mul) kerek(b,c,a,x7,mul)

ahol kerek (a, b, c, x, mul) :

c ^= x a -= t1[c_0] ^ t2[c_2] ^ t3[c_4] ^ t4[c_6] b += t4[c_1] ^ t3[c_3] ^ t2[c_5] ^ t1[c_7] b *= mul

c_i — i-edik bájt c (0 <= i <= 7);

^ - XOR művelet;

ti - i-edik S-doboz

key_schedule - kulcsgenerálás, egy megfordítható függvény , amely az x üzenet kis számú bitjének megváltoztatásáért felelős, hogy az átadás következő végrehajtása során nagy számú bit megváltozzon :

x0 -= x7^0xA5A5A5A5A5A5A5A5 x1 ^= x0 x2 += x1 x3 -= x2 ^ ((~x1)<<19) x4 ^= x3 x5 += x4 x6 -= x5 ^ ((~x4)>>23) x7 ^= x6 x0 += x7 x1 -= x0 ^ ((~x7)<<19) x2 ^= x1 x3 += x2 x4 -= x3 ^ ((~x2)>>23) x5 ^= x4 x6 += x5 x7 -= x6^0x0123456789ABCDEF

ahol <<és >> a logikai eltolások balra és jobbra, ~ az inverzió

visszacsatolás - visszajelzés:

a ^= aa b -= bb c += cc

Vagyis összesen 24 kört kapunk. A kapott a , b , c értékek összefűzése közbenső hash értéket ad , amely a következő 512 bites adatblokk kezdőértékeként szolgál. Az utolsó blokkban egy köztes érték 192 bites Tiger/192 értéket ad. $h_{{i+1}}$ $h_{n}$

Tesztvektorok

Példák a testtiger programmal nyert hash értékekre a szerző oldaláról [1] .

Hash("") = 24F0130C63AC9332 16166E76B1BB925F F373DE2D49584E7A Hash("Tigris") = 9F00F599072300DD 276ABB38C8EB6DEC 37790C116F9D2BDF

Hash("abc") = F258C1E88414AB2A 527AB541FFC5B8BF 935F7B951C132951 Hash("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-") = 87FB2A9083851CF7 470D2CF810E6DF9E B586445034A5A386

Hash("ABCDEFGHIJKLMNOPQRSTUVWXYZ=abcdefghijklmnopqrstuvwxyz+0123456789") = 467DB80863EBCE48 8DF1CD1261655DE9 57896565975F9197

Biztonság

A Tigris legfontosabb biztonsági szempontjai:

S-boxok transzformációjának nemlinearitása;
a 64 bites regiszterek használata felgyorsítja mindhárom regiszter lavinaváltását, ha az üzenet bármely bitje megváltozik;
a kulcsgenerálás minden bitben jelentős változtatásokat biztosít a következő konverziók során, az üzenet enyhe változásával;
a b regiszter megszorzása minden körben elősegíti a keverést és növeli az ellenállást a kapcsolódó kulcsok elleni támadásokkal szemben;
a visszajelzések megakadályozzák a születésnapi támadásokat .

A linkelt kulcsú támadás olyan támadás, amelyben a kriptoanalitikus kivonatot tud kiszámítani több olyan inicializálási vektor értékéhez, amelyeket nem ismer, de tud ezek között valamilyen kapcsolatot (például, hogy egy bittel különböznek egymástól, vagy egy részük). az összes vektor közül egy és ugyanaz). Az ilyen típusú támadások miatt a WEP titkosítást WPA -ra kellett váltani .

A köztes születésnapi támadás egy születésnapi támadás , amelyet köztes körökben alkalmaznak a kívánt hash értékek elérése érdekében. Bár a szerzők szerint az ilyen típusú támadások valószínűleg nem vezetnek kevésbé bonyolultsághoz ( a születésnapi paradoxonnak megfelelően ). $2^{{96}}$

Kriptanalízis

Legyen h(x, m) egy hash függvény , ahol x egy inicializálási vektor, m egy üzenetblokk. ^ az XOR művelet, w{} a Hamming-súly (a bináris szám nullától eltérő összetevőinek száma ). Akkor:

Ütközés alatt azt a helyzetet értjük , amikor w{h(x, m1) ^ h(x, m2)} = 0;
majdnem ütközés alatt - w{h(x, m1) ^ h(x, m2)} = a, ahol a kis érték;
pszeudo ütközés alatt - w{h(x1,m1) ^ h(x2,m2)} = 0;
majdnem álütközés alatt - w{h(x1,m1) ^ h(x2,m2)} = a, ahol a kis érték.

Ideális esetben a születésnapi paradoxonnak megfelelően egy N bites hash függvény ütközésének megtalálásához legalább műveletekre lenne szükség. $O(2^{{N/2}})$

2006-ban John Kelsey és Stefan Lax egy Tiger-16 ütközést mutatott be (24 helyett 16 lövés) , és egy majdnem pszeudo-ütközést a Tiger-20 esetében nehézségekkel . Ugyanebben az évben Florian Mendel és munkatársai megmutatták, hogyan kell alkalmazni John Kelsey és Stefan Lax támadási technikáját a Tiger-19 ütközésének eléréséhez, és két különböző technikát is javasoltak a és -vel való ütközéshez . $2^{{44}}$ $2^{{48}}$ $2^{{62}}$ $2^{{69}}$

A Tiger elleni támadások áttekintése

A körök száma	Típusú	Bonyolultság	Leírás
Tigris-16	ütközés	$2^{{44}}$	[1. cikk]
Tigris-19	ütközés	$2^{{62}}$ és $2^{{69}}$	[2. cikk]
Tigris-19	pszeudoütközést	$2^{{44}}$	[2. cikk]
Tigris-21	pszeudoütközést	$2^{{66}}$	[2. cikk]
Tigris-23/128	pszeudoütközést	$2^{{44}}$	[2. cikk]
Tigris-23	pszeudoütközést	$2^{47}$	[3. cikk]
Tigris-20	szinte álütközés	$2^{{48}}$	[1. cikk]
Tigris-21	szinte álütközés	$2^{{44}}$	[2. cikk]
Tigris-22	szinte álütközés	$2^{{44}}$	[2. cikk]
Tigris-24	szinte álütközés	$2^{47}$	[3. cikk]

Támadás a Tigris-16 ellen

Magyarázzuk el a John Kelsey és Stefan Laks által felvázolt Tiger-16, azaz egy 16 töltényű Tigris ütközésének megtalálásának ötletét [1. cikk] .

A 64 bites szavakat tekintjük. Kétféle szó közötti különbséggel fogunk foglalkozni: a xor különbséggel és az additív különbséggel . Ezek közül az első a szokásos differencia modulo eredménye, a második pedig az XOR művelet eredménye. Általában az egyik típusú különbség átalakulása a másikba a véletlen műve. De van olyan eset is, amikor 1-es valószínűséggel kétféle különbség egyenlő egymással. Ha ugyanis ebben az esetben a , különbség érvényes, akkor a szavak egyszerűen a legjelentősebb bittel különböznek egymástól. Megjegyezzük a különbség tulajdonságot is - ez nem változik, ha a szót páratlan számmal szorozzuk (ami nagyon kényelmes, mivel az algoritmus páratlan mul = 5, 7, 9 értéket használ). $2^{64}$ $I=2^{63}$

Hadd . Beállítás alatt $I=2^{63}$

(I0, I1, I2, I3, I4, I5, I6, I7)

azt értjük, hogy a kulcsok j-edik (j = 0, 1, ..., 7) 64 bites szavai közötti különbség egyenlő (nem mindegy, hogy milyen típusú, mert csak a különbségeket és a 0-t vesszük figyelembe) . Vagyis = xj ^ xj'. $Ij$ $2^{{63}}$ $Ij$

John Kelsey és Stefan Laks azt javasolta, hogy vegyenek fel két blokkot (mindegyik 512 bites) különbségvektorral . Ha követi az algoritmust, figyelembe véve a különbségek tulajdonságait, akkor megmutathatja, hogy az első lépés (0, 1, ..., 7 körök után) és a key_schedule után egy vektor lesz . A 8-9. kör után kapunk , a 10-15. fordulók pedig nem befolyásolják a különbséget. Így megkapjuk a kulcsok közötti különbségek 1-es valószínűséggel való megtartásának technikáját. $(én, én, én, én, 0, 0, 0, 0)$ $(I,I,0,0,0,0,0,0)$ $(0,0,0,0,0,0,0,0)$

Ugyanakkor a születésnapok közbenső támadásain keresztül végrehajtott üzenetmódosítások segítségével megoldódik az a, b, c hash-értékek különbségének fenntartásának problémája, így a 6. kör után különbségvektor volt , körök után pedig 7-9 - . Az üzenetmódosítási technika a legidőigényesebb, ebből adódik a komplexitás . A 10-15. körök nem változtatnak (sőt, ennek a lépésnek a kulcsai már ugyanazok). $(én, én, 0)$ $(0,0,0)$ $2^{{44}}$

Ez azt jelenti, hogy 16 kör után a hash értékek megegyeznek.

Használat

A Tigert a TTH technológiában használják , ahol a hash-t fa formában számítják ki. A TTH -t viszont a Gnutella , a Gnutella2 , a Direct Connect fájlmegosztó protokollok, valamint a Phex, a BearShare, a LimeWire , a Shareaza , a DC++ és a Valknut fájltárolási protokollok használják .

Jegyzetek

↑ A teszttigris vizsgálati eredményei . Letöltve: 2017. szeptember 30. Az eredetiből archiválva : 2018. május 8.. (határozatlan)

Cikkek

↑ 1 2 3 John Kelsey és Stefan Lucks, Collisions and Near-Collisions for Reduced-Round Tiger Archiválva : 2016. március 4., a Wayback Machine , a Fast Software Encryption 13. eljárása, Graz, 2006 ( PDF )
↑ 1 2 3 4 5 6 Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida és Dai Watanabe, Frissítés a Tigerről (hivatkozás nem érhető el) , Indocrypt 7, Kolkata, 2006 ( PDF )
↑ 1 2 Mendel, Flórián; Rijmen Vincent., Cryptanalysis of the Tiger Hash Function (nem elérhető link) , ASIACRYPT 2007. Springer Berlin / Heidelberg. pp. 536-550 ( PDF )

Linkek

Tigris szerzők oldala

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