Tiger (hashfunktion)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 mars 2013; kontroller kräver 20 redigeringar .

Tiger är en kryptografisk hashfunktion utvecklad av Ros Anderson och Eli Biham 1995.

Tiger designades för att köras särskilt snabbt på 64-bitars datorer. Tiger har inga patentrestriktioner, kan användas fritt både med referensimplementeringen och med dess modifieringar. Storleken på hashvärdet är 192 bitar (Tiger/192), även om det även finns kortare versioner för kompatibilitet med SHA-1 (Tiger/160) och med MD4 , MD5 , RIPEMD, Snefru (Tiger/128). Drifthastighet - 132 Mbps (testad på en Alpha 7000-processor, modell 660). På moderna processorer är det mycket snabbare (även när det testas på en 32-bitars AMD Sempron 3000+ är hastigheten cirka 225 Mbps).

Tiger2 är en version av Tiger som skiljer sig från den huvudsakliga endast i en annan algoritm för att lägga till bitar, liknande MD5 / SHA-1 . Testvektorer finns tillgängliga för Tiger2.

Origins

Algoritmen utvecklades 1995 av Ross Anderson och Eli Biham. Den tiden präglades av att det redan fanns kollisioner för de populära hashfunktionerna MD4 och Snefru . De senare, enligt författarna, ifrågasatte tillförlitligheten av deras derivat, såsom MD5 och Snefru-8 . Huvudmålen i utvecklingen av Tiger var:

säkerhet ;
snabbt arbete på nya 64-bitars processorer med rimlig hastighet på 32-bitars;
möjlig ersättning av MD- och SHA-serien.

Algoritm

Antalet S-boxar som används är 4. S-box konverterar 8 bitar till 64 bitar. Det vill säga att var och en av dem har 256 64-bitars ord och den totala mängden minne som krävs för att lagra S-boxar är 4*256*8 = 8192 = 8 KB. För detta räcker cachen för de flesta processorer, även om det kan vara svårt att implementera på mikrokontroller.

Som med MD4- familjen läggs en "1"-bit till meddelandet följt av nollor. Indata är uppdelad i n block om 512 bitar.

Välj det första 512-bitarsblocket. Detta block är uppdelat i åtta 64-bitars ord x0, x1, ..., x7. Byte-ordningen är little-endian .

Tre 64-bitars register tas med initiala värden (hashvärde ): $h_{0}$

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

Nu, för att gå från värde till värde , utförs följande operationer: $Hej}$ $h_{{i+1}}$

save_abc
godkänt(a, b, c, 5)
nyckel_schema
pass(c, a, b, 7)
nyckel_schema
pass(b, c, a,9)
feedforward

Här sparar save_abc värdet : $Hej}$

aa = a bb = b cc=c

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

rund (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)

där runda (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-lådan

key_schedule - nyckelgenerering, en reversibel funktion som är ansvarig för att ändra ett litet antal bitar av meddelandet x för att få ett stort antal bitar att ändras vid nästa körning av 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

där <<och >> är logiska förskjutningar till vänster och höger, ~ är inversionen

feedforward - feedback:

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

Det vill säga att vi får 24 omgångar totalt. Sammankopplingen av de mottagna värdena a , b , c ger ett mellanliggande hashvärde , som används som initialvärde för nästa 512-bitars datablock. Ett mellanvärde på det sista blocket ger ett 192-bitars Tiger/192-värde. $h_{{i+1}}$ $h_{n}$

Testa vektorer

Exempel på hashvärden som erhållits med testtigerprogrammet från författarens sida [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

Säkerhet

Viktiga säkerhetsaspekter av tigern:

icke-linjäritet för transformation av S-boxar;
användningen av 64-bitars register påskyndar lavinbytet av alla tre registren när någon bit av meddelandet ändras;
nyckelgenerering ger betydande förändringar i alla bitar vid efterföljande omvandlingar med en liten förändring i meddelandet;
multiplicera registret b i varje omgång främjar också blandning och ökar motståndet mot attacker på relaterade nycklar;
feedback förhindrar mellanliggande födelsedagsattacker .

En länkad nyckelattack är en attack där en kryptoanalytiker kan beräkna en hash för flera olika värden av initialiseringsvektorer som han inte känner till, men känner till något samband mellan dem (till exempel att de skiljer sig med en bit eller att någon del av alla vektorer är en och samma). På grund av denna typ av attack var WEP- kryptering tvungen att bytas till WPA .

En mellanliggande födelsedagsattack är en födelsedagsattack som tillämpas i mellanrundor för att uppnå önskade hashvärden. Även om det, enligt författarna, är osannolikt att attacker av denna typ leder till mindre komplexitet (i enlighet med födelsedagsparadoxen ). $2^{{96}}$

Kryptanalys

Låt h(x, m) vara en hashfunktion , där x är en initialiseringsvektor, m är ett meddelandeblock. ^ är XOR-operationen, w{} är Hamming-vikten (antalet komponenter som inte är noll i det binära talet ). Sedan:

Med kollision menar vi situationen när w{h(x, ml) ^ h(x, m2)} = 0;
under nästan kollision - w{h(x, m1) ^ h(x, m2)} = a, där a är ett litet värde;
under pseudo -kollision - w{h(xl,ml) ^ h(x2,m2)} = 0;
under nästan pseudo -kollision - w{h(x1,m1) ^ h(x2,m2)} = a, där a är ett litet värde.

Helst, i enlighet med födelsedagsparadoxen , skulle det kräva åtminstone operationer för att hitta en kollision av en N-bitars hashfunktion . $O(2^{{N/2}})$

2006 introducerade John Kelsey och Stefan Lax en Tiger-16- kollision (med 16 omgångar istället för 24) med svårighet , och en nästan pseudo-kollision för Tiger-20 med svårighet . Senare samma år visade Florian Mendel et al hur man tillämpar John Kelsey och Stefan Lax attackteknik för att få en Tiger-19 kollision, och föreslog även två olika tekniker för att få denna kollision med och . $2^{{44}}$ $2^{{48}}$ $2^{{62}}$ $2^{{69}}$

Översikt över attacker mot Tiger

Antal omgångar	Sorts	Komplexitet	Beskrivning
Tiger-16	kollision	$2^{{44}}$	[Artikel 1]
Tiger-19	kollision	$2^{{62}}$ och $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ästan pseudo-kollision	$2^{{48}}$	[Artikel 1]
Tiger-21	nästan pseudo-kollision	$2^{{44}}$	[artikel 2]
Tiger-22	nästan pseudo-kollision	$2^{{44}}$	[artikel 2]
Tiger-24	nästan pseudo-kollision	$2^{47}$	[artikel 3]

Attack mot Tiger-16

Låt oss förklara idén med att hitta en kollision för Tiger-16, d.v.s. för en Tiger med 16 omgångar, skisserad av John Kelsey och Stefan Laks [artikel 1] .

Vi överväger 64-bitars ord. Vi kommer att ta itu med en skillnad mellan två typer av ord: xor-skillnaden och den additiva skillnaden . Den första av dem är resultatet av den vanliga skillnaden modulo , och den andra är resultatet av XOR-operationen. Vanligtvis är omvandlingen av en typ av skillnad till en annan en fråga om slumpen. Men det finns ett fall när två typer av skillnader är lika med varandra med sannolikhet 1. Nämligen, när skillnaden är giltig i detta fall, skiljer sig orden helt enkelt från varandra med den mest signifikanta biten. Vi noterar också skillnadsegenskapen - den ändras inte om ordet multipliceras med ett udda tal (vilket är mycket bekvämt, eftersom algoritmen använder udda mul = 5, 7, 9). $2^{64}$ $I=2^{63}$

Låt . Under set $I=2^{63}$

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

vi menar att skillnaden mellan nycklarnas j-th (j = 0, 1, ..., 7) 64-bitars ord är lika (det spelar ingen roll vilken typ, eftersom vi bara kommer att överväga skillnader och 0) . Det vill säga = xj ^ xj'. $I j$ $2^{{63}}$ $I j$

John Kelsey och Stefan Laks föreslog att man skulle ta två block (512 bitar vardera) med en skillnadsvektor . Om du följer algoritmen, med hänsyn till egenskaperna hos skillnader, kan du visa att efter det första passet (efter omgångarna 0, 1, ..., 7) och key_schedule kommer det att finnas en vektor . Efter omgångarna 8-9 får vi , och omgångarna 10-15 påverkar inte skillnaden. Således får vi tekniken att hålla skillnader mellan nycklar med en sannolikhet på 1. $(Jag,Jag,Jag,Jag,0,0,0,0)$ $(I,I,0,0,0,0,0,0)$ $(0,0,0,0,0,0,0,0)$

Samtidigt, med hjälp av meddelandemodifieringar genom mellanliggande attacker av födelsedagar , löses problemet med att upprätthålla skillnaden i hashvärden a, b, c, så att det efter omgång 6 fanns en skillnadsvektor och efter omgångar 7-9 - . Meddelandemodifieringstekniken är den mest tidskrävande, vilket är där den resulterande komplexiteten erhålls . Omgångarna 10-15 kommer inte att göra någon skillnad (nycklarna till detta steg är faktiskt redan desamma). $(jag, jag, 0)$ $(0,0,0)$ $2^{{44}}$

Det vill säga, efter 16 omgångar kommer hashvärdena att matcha.

Användning

Tiger används i TTH- teknik , där hash beräknas i trädform. TTH används i sin tur i fildelningsprotokollen Gnutella , Gnutella2 , Direct Connect , samt Phex-, BearShare-, LimeWire- , Shareaza- , DC++- och Valknut -filvärden .

Anteckningar

↑ Testresultat av testtiger . Hämtad 30 september 2017. Arkiverad från originalet 8 maj 2018. (obestämd)

Artiklar

↑ 1 2 3 John Kelsey och Stefan lycka till, kollisioner och nästan kollisioner för Tiger med reducerad runda arkiverad 4 mars 2016 på Wayback Machine , processer av Fast Software Encryption 13, Graz, 2006 ( PDF )
↑ 1 2 3 4 5 6 Florian Mendel, Bart Preneel, Vincent Rijmen, Hirotaka Yoshida och Dai Watanabe, Update on Tiger (länk ej tillgänglig) , förfaranden för Indocrypt 7, Kolkata, 2006 ( PDF )
↑ 1 2 Mendel, Florian; Rijmen Vincent., Cryptanalysis of the Tiger Hash Function (ej tillgänglig länk) , ASIACRYPT 2007. Springer Berlin / Heidelberg. pp. 536-550 ( PDF )

Länkar

Tiger författares sida

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H 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 Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA