Hashfunktionskollision

En hashfunktionskollision  är två olika indatablock och för en hashfunktion sådan

Kollisioner finns för de flesta hashfunktioner, men för "bra" hashfunktioner är frekvensen av deras förekomst nära det teoretiska minimum. I vissa speciella fall, när uppsättningen av olika indata är finit , är det möjligt att definiera en injektiv hashfunktion, som per definition inte har kollisioner. För hashfunktioner som tar indata med variabel längd och returnerar en hash med konstant längd (som MD5 ), måste kollisioner förekomma, eftersom för minst ett hashfunktionsvärde kommer motsvarande uppsättning indata ( full preimage ) att vara oändlig - och två valfria data från denna uppsättning bildar en kollision.

Exempel

Betrakta som ett exempel en hashfunktion definierad på uppsättningen av heltal . Dess värdedomän består av 19 element ( restringar modulo 19), och dess definitionsdomän  är oändlig. Eftersom uppsättningen av förbilder uppenbarligen är större än uppsättningen av värden, måste kollisioner existera.

Låt oss bygga en kollision för denna hashfunktion för ingångsvärdet 38, vars hashsumma är noll. Eftersom funktionen  är periodisk med en period på 19, för vilket inmatningsvärde y som helst , kommer värdet y + 19 att ha samma hashsumma som y . Speciellt för ingångsvärdet 38 kommer ingångsvärdena 57, 76, etc. att ha samma hashsumma. Således bildar paren av ingångsvärden (38.57), (38.76) hashfunktionskollisioner .

Kryptografiska hashfunktionskollisioner

Eftersom kryptografiska hashfunktioner används för att bekräfta den ursprungliga informationens oföränderlighet, är förmågan att snabbt hitta en kollision för dem vanligtvis detsamma som att misskreditera . Till exempel, om en hash-funktion används för att skapa en digital signatur , då är förmågan att hitta kollisioner för den faktiskt likvärdig med förmågan att förfalska en digital signatur. Därför är måttet på den kryptografiska styrkan hos en hashfunktion den beräkningsmässiga komplexiteten för att hitta en kollision. Helst borde det inte finnas något snabbare sätt att hitta kollisioner än brute force . Om det för någon hashfunktion finns ett sätt att få kollisioner som är mycket snabbare än uttömmande sökning, så anses denna hashfunktion inte längre vara kryptoresistent och används inte längre för att överföra och lagra hemlig information. Teoretiska och praktiska frågor om att hitta och använda kollisioner diskuteras årligen inom ramen för internationella konferenser (som CRYPTO eller ASIACRYPT ), på ett stort antal internetresurser, såväl som i många publikationer.

Egenskaper för kryptografiska hashfunktioner

För att en hashfunktion H ska anses vara kryptografiskt säker måste den uppfylla tre grundläggande krav som de flesta tillämpningar av hashfunktioner inom kryptografi baseras på:

Använda kollisioner för att hacka

Som ett exempel, överväg en enkel användarautentiseringsprocedur :

Med detta tillvägagångssätt, även om en angripare får tillgång till databasen, kommer han inte att kunna återställa användarnas ursprungliga lösenord (förutsatt att hashfunktionen som används är oåterkallelig). Men om en angripare vet hur man hittar kollisioner för hashfunktionen som används kommer det inte att vara svårt för honom att hitta ett icke-originallösenord som kommer att ha samma hashsumma som användarens lösenord.

Kollisioner kan användas för att förfalska meddelanden: information om valutatransaktioner, till exempel, krypteras ofta med hashfunktioner; en angripare, som har en metod för att hitta kollisioner av denna hashfunktion, kan ersätta meddelandet med ett falskt meddelande och därigenom påverka förloppet av en valutatransaktion.

På samma sätt kan kollisioner användas för att förfalska digitala signaturer och certifikat .

Kollisionsskydd

Det finns ett antal metoder för skydd mot hacking , skydd mot förfalskning av lösenord, signaturer och certifikat , även om angriparen känner till metoderna för att konstruera kollisioner för någon hashfunktion .

En metod är att lägga till ett " salt ", det vill säga att lägga till någon sekvens av tecken till hashbara data, som används till exempel vid lagring av UNIX- lösenord. I det här fallet läggs samma "salt" också till den resulterande hashen , vilket avsevärt ökar komplexiteten i den samtidiga konstruktionen av förstklassiga kollisioner till en grupp lösenord, eftersom var och en i denna grupp måste börja med sin egen (unika) "salt" värde. Men "salt" komplicerar inte attacken mot varje lösenord individuellt .

En annan populär men trasig metod är sammanlänkningen av hash från två olika hashfunktioner. Man tror att i det här fallet, för att välja kollisioner för hashfunktionen , som är sammanlänkningen av hashfunktionerna och , är det nödvändigt att känna till metoderna för att konstruera kollisioner för både , och . Samtidigt finns det studier som visar att användningen av hashsammansättningar ökar motståndet hos den regulatoriska hashen något mot kollisioner, och det spelar ingen roll hur mycket hashfunktionerna skiljer sig från varandra [1] . Om en av hashfunktionerna är tillräckligt svag för att hitta en kollision i den, kommer den andra inte att kunna förstärka den resulterande hashen.

Kollisionsdetekteringsmetoder

En av de enklaste och mest mångsidiga metoderna för att hitta kollisioner är födelsedagsattacken . Med denna attack kommer att hitta en kollision för en bit -längd hash-funktion att kräva i genomsnitt cirka operationer. Därför anses en n -bitars hashfunktion vara säker om beräkningskomplexiteten för att hitta kollisioner för den är nära .

Dessutom finns det en meddelandeförlängningsattack , som, givet ett känt värde , gör att man kan beräkna , där anger sammankopplingen av . Tilläggsattacken för vissa hashfunktioner fungerar även när den tillhandahåller typ 1-kollisionsmotstånd , typ 2-kollisionsmotstånd och irreversibilitetsegenskapen . Det är underförstått att det inte är nödvändigt att veta , men det räcker att bara känna till dess hash . Således kan du till exempel lägga till ytterligare information till någon annans meddelande. Olika metoder används för att förhindra denna attack: de lägger till en extra hashingrunda , annorlunda än de tidigare; använd multipla hashing; eller använd en kombination av de två föregående metoderna.

Men tilläggsattacken kan också betraktas från andra sidan: om vi har något meddelande och hashfunktionen är sårbar för tilläggsattacken, så är det lätt att hitta en kollision av det första slaget: , , , dvs. egenskapen motstånd mot kollisioner av det första slaget kränks.

De flesta moderna hashfunktioner har samma struktur, baserat på att dela upp den inmatade texten i block och sedan iterera, där någon funktion används vid varje iteration , där x  är nästa block i inmatningstexten och y  är resultatet av föregående drift. Ett sådant schema är dock inte perfekt, eftersom det, med kännedom om funktionen , är möjligt att analysera data i intervallen mellan iterationer , vilket underlättar sökningen efter kollisioner.

Ofta föregås att hitta hashfunktionskollisioner av att hitta dess pseudo -kollisioner , det vill säga två olika värden av den initiala bufferten, som för samma meddelande ger lika hashvärden.

Kollisioner mellan MD4 och MD5 hashfunktioner

1996 hittade Hans Dobbertin pseudokollisioner i MD5 med hjälp av vissa icke-standardiserade initialiseringsvektorer . Det visade sig att det är möjligt att bygga ett andra meddelande för ett känt meddelande, så att det kommer att ha samma hash som det ursprungliga. Ur matematisk synvinkel betyder detta att MD5(IV,L1) = MD5(IV,L2) , där IV är buffertens initiala värde och L1 och L2 är olika meddelanden.

2004 tillkännagav de kinesiska forskarna Wang Xiaoyun Yu Hongbo en sårbarhet som de hade upptäckt i en algoritm som gjorde det möjligt för dem attochLai Xuejia, Feng Dengguo, ) för att hitta kollisioner.

År 2005 publicerade forskarna Wang Xiaoyun och Yu Hongbo från Shandong University i Kina en algoritm för att hitta kollisioner i MD5-hashfunktionen , och deras metod fungerar för vilken initieringsvektor som helst, inte bara vektorn som används av standarden. Genom att tillämpa denna metod på MD4 kan du hitta en kollision på mindre än en sekund. Det gäller även andra hashfunktioner som RIPEMD och HAVAL .

2008 publicerade Alexander Sotirov, Marc Stevens, Jacob Appelbaum en artikel på den 25:e Chaos Communication Congress som visade möjligheten att generera falska digitala certifikat baserat på användningen av MD5-kollisioner.

SHA-1 hashfunktionskollisioner

I januari 2005 publicerade Vincent Rayman och Elisabeth Oswald en attack mot en trunkerad version av SHA-1 (53 omgångar istället för 80 ), vilket gör att kollisioner kan hittas i mindre än 280 operationer.

I februari 2005 presenterade Wang Xiaoyun , Lisa Yin Yiqun och Yu Hongbo en attack mot full SHA-1 som kräver mindre än 269 operationer.

I augusti 2005, vid CRYPTO 2005, presenterade samma experter en förbättrad version av attacken mot den fullfjädrade SHA-1, med en beräkningskomplexitet på 263 operationer. I december 2007 granskades detaljerna i denna förbättring av Martin Cochran.

Christophe de Kanier och Christian Rechberg presenterade senare en förbättrad attack mot SHA-1, för vilken de belönades med det bästa dokumentet vid 2006 års ASIACRYPT- konferens . De presenterade en tvåblockskollision på en 64-rundsalgoritm med en beräkningskomplexitet på cirka 2 35 operationer.

Eftersom teoretiska attacker mot SHA-1 har varit framgångsrika planerar NIST att helt fasa ut användningen av SHA-1 i digitala signaturer .

Kollisioner med andra hashfunktioner

RIPEMD- och HAVAL- hashfunktionerna är också sårbara för MD5- kollisionsalgoritmen som publicerades av Wang Xiaoyun, Feng Dengguo, Lai Xuejia och Yu Hongbo 2004.

För den andra modifieringen av WHIRLPOOL- hashfunktionen , kallad Whirlpool-T, föreslås inga algoritmer för att hitta kollisioner eller pseudokollisioner för 2009; en betydande begränsning för att hitta dem är komplexiteten hos själva funktionen och den stora längden (512 bitar) på utmatningsnyckeln.

Hashfunktionen GOST R 34.10-2001 i termer av kryptografisk styrka skiljer sig lite från GOST R 34.10-94 , att hitta kollisioner för vilka reduceras till att beräkna en diskret logaritm i en grupp av punkter i en elliptisk kurva med antagligen exponentiell komplexitet . Till exempel, för 256- bitars parametrar kommer diskret logaritm som använder ρ-metoden eller Pollards λ-metod att kräva cirka 2 operationer.

Kollisionsupplösning i hashtabeller

Kollisioner komplicerar användningen av hashtabeller , eftersom de bryter en-till-en-överensstämmelsen mellan hashkoder och data. Det finns dock speciella tekniker för att övervinna de svårigheter som uppstår:

Anteckningar

  1. ↑ Antoine Joux . Hämtad 3 oktober 2017. Arkiverad från originalet 19 maj 2017.

Se även

Länkar

Litteratur