Tiger (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 13. marts 2013; checks kræver 20 redigeringer .

Tiger er en kryptografisk hashfunktion udviklet af Ros Anderson og Eli Biham i 1995.

Tiger er designet til at køre særligt hurtigt på 64-bit computere. Tiger har ingen patentrestriktioner, kan frit bruges både med referenceimplementeringen og med dens modifikationer. Størrelsen af hashværdien er 192 bit (Tiger/192), selvom der også er kortere versioner for kompatibilitet med SHA-1 (Tiger/160) og med MD4 , MD5 , RIPEMD, Snefru (Tiger/128). Driftshastighed - 132 Mbps (testet på én Alpha 7000-processor, model 660). På moderne processorer er det meget hurtigere (selv når det testes på en 32-bit AMD Sempron 3000+, er hastigheden omkring 225 Mbps).

Tiger2 er en version af Tiger, der kun adskiller sig fra den primære i en anden bit-tilføjelsesalgoritme, der ligner MD5 / SHA-1 . Testvektorer er tilgængelige for Tiger2.

Oprindelse

Algoritmen blev udviklet i 1995 af Ross Anderson og Eli Biham. Den tid var præget af, at man allerede fandt kollisioner for de populære hash-funktioner MD4 og Snefru . Sidstnævnte satte ifølge forfatterne spørgsmålstegn ved pålideligheden af deres derivater, såsom MD5 og Snefru-8 . Hovedmålene i udviklingen af Tiger var:

sikkerhed ;
hurtigt arbejde på nye 64-bit processorer med rimelig hastighed på 32-bit;
mulig udskiftning af MD- og SHA-serien.

Algoritme

Antallet af brugte S-bokse er 4. S-boks konverterer 8 bit til 64 bit. Det vil sige, at hver af dem har 256 64-bit ord, og den samlede mængde hukommelse, der kræves til at gemme S-bokse, er 4*256*8 = 8192 = 8 KB. Til dette er cachen på de fleste processorer nok, selvom det kan være svært at implementere på mikrocontrollere.

Som med MD4- familien tilføjes en "1" bit til meddelelsen efterfulgt af nuller. Indgangsdataene er opdelt i n blokke af 512 bit.

Vælg den første 512-bit blok. Denne blok er opdelt i otte 64-bit ord x0, x1, ..., x7. Byte-rækkefølgen er little-endian .

Tre 64-bit registre tages med startværdier (hashværdi ): $h_{0}$

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

For nu at gå fra værdi til værdi udføres følgende handlinger: $Hej}$ $h_{{i+1}}$

gem_abc
bestå(a, b, c, 5)
nøgleplan
bestå(c, a, b, 7)
nøgleplan
bestå (b, c, a, 9)
feedforward

Her gemmer save_abc værdien : $Hej}$

aa = a bb = b cc=c

pass(a, b, c, mul) betyder:

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

hvor runde (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-te byte c (0 <= i <= 7);

^ - XOR operation;

ti - i-te S-kasse

key_schedule - nøglegenerering, en reversibel funktion , der er ansvarlig for at ændre et lille antal bits af beskeden x for at få et stort antal bit til at ændre sig ved næste udførelse af pass :

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

hvor <<og >> er logiske skift til venstre og højre, ~ er inversionen

feedforward - feedback:

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

Det vil sige, at vi får 24 runder i alt. Sammenkædningen af de modtagne værdier a , b , c giver en mellemliggende hashværdi , som bruges som startværdien for den næste 512-bit datablok. En mellemværdi på den sidste blok giver en 192-bit Tiger/192 værdi. $h_{{i+1}}$ $h_{n}$

Test vektorer

Eksempler på hash-værdier opnået ved hjælp af testtiger-programmet fra forfatterens side [1] .

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

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

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

Sikkerhed

Vigtigste sikkerhedsaspekter af tigeren:

ikke-linearitet af transformation af S-bokse;
brugen af 64-bit registre fremskynder lavineændringen af alle tre registre, når en hvilken som helst bit af meddelelsen ændres;
nøglegenerering giver væsentlige ændringer i alle bits ved efterfølgende konverteringer med en lille ændring i meddelelsen;
multiplicering af register b i hver runde fremmer også blanding og øger modstanden mod angreb på relaterede nøgler;
feedback forhindrer mellemliggende fødselsdagsangreb .

Et koblet nøgleangreb er et angreb, hvor en kryptoanalytiker kan beregne en hash for flere forskellige værdier af initialiseringsvektorer, som han ikke kender, men kender et forhold mellem dem (for eksempel at de adskiller sig med en bit eller en del af alle vektorer er en og samme). På grund af denne type angreb måtte WEP -kryptering skiftes til WPA .

Et mellemliggende fødselsdagsangreb er et fødselsdagsangreb, der anvendes i mellemrunder for at opnå de ønskede hashværdier. Selvom angreb af denne type ifølge forfatterne næppe vil føre til mindre kompleksitet (i overensstemmelse med fødselsdagsparadokset ). $2^{{96}}$

Krypteringsanalyse

Lad h(x, m) være en hashfunktion , hvor x er en initialiseringsvektor, m er en beskedblok. ^ er XOR-operationen, w{} er Hamming-vægten (antallet af ikke-nul-komponenter af det binære tal ). Derefter:

Med kollision mener vi situationen hvornår w{h(x, ml) ^ h(x, m2)} = 0;
under næsten kollision - w{h(x, m1) ^ h(x, m2)} = a, hvor a er en lille værdi;
under pseudo -kollision - w{h(xl,ml) ^ h(x2,m2)} = 0;
under næsten pseudo -kollision - w{h(x1,m1) ^ h(x2,m2)} = a, hvor a er en lille værdi.

Ideelt set, i overensstemmelse med fødselsdagsparadokset , ville det i det mindste kræve operationer at finde en kollision af en N-bit hashfunktion . $O(2^{{N/2}})$

I 2006 introducerede John Kelsey og Stefan Lax en Tiger-16- kollision (med 16 runder i stedet for 24) med besvær , og en næsten pseudo-kollision for Tiger-20 med besvær . Senere samme år viste Florian Mendel et al., hvordan man anvender John Kelsey og Stefan Lax' angrebsteknik for at få en Tiger-19 kollision, og foreslog også to forskellige teknikker til at få denne kollision med og . $2^{{44}}$ $2^{{48}}$ $2^{{62}}$ $2^{{69}}$

Oversigt over angreb på Tiger

Antal runder	Type	Kompleksitet	Beskrivelse
Tiger-16	kollision	$2^{{44}}$	[artikel 1]
Tiger-19	kollision	$2^{{62}}$ og $2^{{69}}$	[artikel 2]
Tiger-19	pseudokollision	$2^{{44}}$	[artikel 2]
Tiger-21	pseudokollision	$2^{{66}}$	[artikel 2]
Tiger-23/128	pseudokollision	$2^{{44}}$	[artikel 2]
Tiger-23	pseudokollision	$2^{47}$	[artikel 3]
Tiger-20	næsten pseudo-kollision	$2^{{48}}$	[artikel 1]
Tiger-21	næsten pseudo-kollision	$2^{{44}}$	[artikel 2]
Tiger-22	næsten pseudo-kollision	$2^{{44}}$	[artikel 2]
Tiger-24	næsten pseudo-kollision	$2^{47}$	[artikel 3]

Angreb på Tiger-16

Lad os forklare ideen om at finde en kollision for Tiger-16, dvs. for en Tiger med 16 runder, skitseret af John Kelsey og Stefan Laks [artikel 1] .

Vi betragter 64-bit ord. Vi vil beskæftige os med en forskel mellem to typer ord: xor-forskellen og den additive forskel . Den første af dem er resultatet af den sædvanlige difference modulo , og den anden er resultatet af XOR-operationen. Normalt er transformationen af en type forskel til en anden et spørgsmål om tilfældigheder. Men der er et tilfælde, hvor to typer forskelle er lig med hinanden med sandsynlighed 1. Nemlig, når forskellen , er gyldig i dette tilfælde, adskiller ordene sig simpelthen fra hinanden med den mest signifikante bit. Vi bemærker også differenceegenskaben - den ændrer sig ikke, hvis ordet ganges med et ulige tal (hvilket er meget praktisk, da algoritmen bruger ulige mul = 5, 7, 9). $2^{64}$ $I=2^{63}$

Lad . Under sæt $I=2^{63}$

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

vi mener, at forskellen mellem nøglernes j-th (j = 0, 1, ..., 7) 64-bit ord er ens (det er lige meget hvilken type, da vi kun vil overveje forskelle og 0) . Det vil sige = xj ^ xj'. $Ij$ $2^{{63}}$ $Ij$

John Kelsey og Stefan Laks foreslog at tage to blokke (512 bit hver) med en forskelsvektor . Hvis du følger algoritmen, under hensyntagen til egenskaberne af forskelle, kan du vise, at efter det første gennemløb (efter runder 0, 1, ..., 7) og key_schedule vil der være en vektor . Efter runde 8-9 får vi , og runder 10-15 påvirker ikke forskellen. Således får vi teknikken til at holde forskelle mellem nøgler med en sandsynlighed på 1. $(I,I,I,I,0,0,0,0)$ $(I,I,0,0,0,0,0,0)$ $(0,0,0,0,0,0,0,0)$

Samtidig løses problemet med at opretholde forskellen i hashværdierne a, b, c ved hjælp af meddelelsesændringer gennem mellemliggende angreb af fødselsdage , så der efter runde 6 var en forskelsvektor og efter runder 7-9 - . Meddelelsesmodifikationsteknikken er den mest tidskrævende, og det er her den resulterende kompleksitet opnås . Runde 10-15 vil ikke gøre nogen forskel (faktisk, nøglerne til dette trin er allerede de samme). $(jeg, jeg, 0)$ $(0,0,0)$ $2^{{44}}$

Det vil sige, at efter 16 runder vil hashværdierne matche.

Brug

Tiger bruges i TTH -teknologi , hvor hashen beregnes i træform. TTH bruges igen i fildelingsprotokollerne Gnutella , Gnutella2 , Direct Connect samt Phex, BearShare, LimeWire , Shareaza , DC++ og Valknut filhosting .

Noter

↑ Testresultater af testtiger . Hentet 30. september 2017. Arkiveret fra originalen 8. maj 2018. (ubestemt)

Artikler

↑ 1 2 3 John Kelsey og Stefan Lucks, Collisions and Near-Collisions for Reduced-Round Tiger Arkiveret 4. marts 2016 på Wayback Machine , procedurer for Fast Software Encryption 13, Graz, 2006 ( PDF )
↑ 1 2 3 4 5 6 Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida og Dai Watanabe, Update on Tiger (link utilgængeligt) , procedurer fra Indocrypt 7, Kolkata, 2006 ( PDF )
↑ 1 2 Mendel, Florian; Rijmen Vincent., Cryptanalysis of the Tiger Hash Function (utilgængeligt link) , ASIACRYPT 2007. Springer Berlin / Heidelberg. pp. 536-550 ( PDF )

Links

Tiger forfatterside

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