Hash funktion kollision

En hash funktion kollision er to forskellige input data blokke og for en hash funktion sådan $x$ $y$ $H$ $H(x)=H(y).$

Kollisioner eksisterer for de fleste hashfunktioner, men for "gode" hashfunktioner er hyppigheden af deres forekomst tæt på det teoretiske minimum. I nogle specielle tilfælde, når sættet af forskellige inputdata er endeligt , er det muligt at definere en injektiv hashfunktion, som per definition ikke har kollisioner. For hashfunktioner, der tager input med variabel længde og returnerer en hash med konstant længde (såsom MD5 ), skal der dog eksistere kollisioner, fordi for mindst én hashfunktionsværdi vil det tilsvarende sæt inputdata ( fuldt præbillede ) være uendelig - og alle to sæt data fra dette sæt danner en kollision.

Eksempel

Betragt som et eksempel en hashfunktion defineret på sættet af heltal . Dets værdidomæne består af 19 elementer ( restringe modulo 19), og dets definitionsdomæne er uendeligt. Da sættet af forbilleder åbenbart er større end værdisættet, skal der eksistere kollisioner. $H(x)=x\ {\bmod \ }19$

Lad os bygge en kollision for denne hashfunktion for inputværdien 38, hvis hashsum er nul. Da funktionen er periodisk med en periode på 19, vil værdien y + 19 for enhver inputværdi y have samme hashsum som y . Især for inputværdien 38 vil inputværdierne 57, 76 osv. have samme hashsum. Således danner parrene af inputværdier (38.57), (38.76) hashfunktionskollisioner . $H(x)$ $H(x)$

Krypteringshash funktion kollisioner

Da kryptografiske hash-funktioner bruges til at bekræfte uforanderligheden af den originale information, er evnen til hurtigt at finde en kollision for dem normalt ensbetydende med at miskreditere . For eksempel, hvis en hash-funktion bruges til at oprette en digital signatur , så svarer evnen til at finde kollisioner for den faktisk med evnen til at forfalske en digital signatur. Derfor er målet for en hashfunktions kryptografiske styrke den beregningsmæssige kompleksitet ved at finde en kollision. Ideelt set burde der ikke være nogen hurtigere måde at finde kollisioner på end brute force . Hvis der for en eller anden hash-funktion er en måde at opnå kollisioner på, der er meget hurtigere end udtømmende søgning, så anses denne hash-funktion ikke længere for at være krypto-resistent og bruges ikke længere til at transmittere og opbevare hemmelige oplysninger. Teoretiske og praktiske spørgsmål om at finde og bruge kollisioner diskuteres årligt inden for rammerne af internationale konferencer (såsom CRYPTO eller ASIACRYPT ), på en lang række internetressourcer såvel som i mange publikationer.

Egenskaber for kryptografiske hash-funktioner

For at en hashfunktion H kan betragtes som kryptografisk sikker, skal den opfylde tre grundlæggende krav, som de fleste anvendelser af hashfunktioner i kryptografi er baseret på:

Irreversibilitet : For en given hash-værdi m burde det være praktisk talt umuligt at finde en datablok for hvilken . $x$ $H(X)=m$
Kollisionsmodstand af den første slags : for en given besked M burde det være praktisk talt umuligt at finde en anden besked N , for hvilken . $H(N)=H(M)$
Kollisionsmodstand af den anden slags : det burde være praktisk talt umuligt at opfange et par beskeder , der har samme hash. $(M,M')$

Brug af kollisioner til at hacke

Som et eksempel kan du overveje en simpel brugergodkendelsesprocedure :

ved registrering i systemet indtaster brugeren sin adgangskode, som en hash-funktion anvendes på , hvis værdi er registreret i databasen ;
hver gang du indtaster en adgangskode, anvendes den samme hash-funktion på den , og resultatet sammenlignes med den, der er registreret i databasen.

Med denne tilgang, selv hvis en angriber får adgang til databasen, vil han ikke være i stand til at gendanne brugernes originale adgangskoder (forudsat at den anvendte hash-funktion er irreversibel). Men hvis en angriber ved, hvordan man finder kollisioner for den anvendte hash-funktion, vil det ikke være svært for ham at finde et ikke-originalt kodeord, der vil have samme hash-sum som brugerens kodeord.

Kollisioner kan bruges til at forfalske meddelelser: oplysninger om valutatransaktioner, for eksempel, krypteres ofte ved hjælp af hash-funktioner; en angriber, der har en metode til at finde kollisioner af denne hash-funktion, kan erstatte beskeden med en falsk og derved påvirke forløbet af en valutatransaktion.

På samme måde kan kollisioner bruges til at forfalske digitale signaturer og certifikater .

Kollisionsbeskyttelse

Der er en række metoder til beskyttelse mod hacking , beskyttelse mod forfalskning af adgangskoder, signaturer og certifikater , også selvom angriberen kender metoderne til at konstruere kollisioner for enhver hashfunktion .

En metode er at tilføje et " salt ", det vil sige at tilføje en sekvens af tegn til de hashbare data, som f.eks. bruges ved lagring af UNIX - adgangskoder. I dette tilfælde føjes det samme "salt" også til den resulterende hash , hvilket markant øger kompleksiteten af den samtidige konstruktion af førsteklasses kollisioner til en gruppe af adgangskoder, da hver i denne gruppe skal begynde med sin egen (unik) "salt" værdi. Men "salt" komplicerer ikke angrebet på hver adgangskode individuelt .

En anden populær, men brudt metode er sammenkædning af hash fra to forskellige hash-funktioner. Det antages, at i dette tilfælde, for at vælge kollisioner for hash-funktionen , som er sammenkædningen af hash-funktionerne og , er det nødvendigt at kende metoderne til at konstruere kollisioner for både , og . Samtidig er der undersøgelser, der viser, at brugen af hash-sammenkædninger øger den regulatoriske hashs modstand lidt over for kollisioner, og det er lige meget, hvor meget hash-funktionerne adskiller sig fra hinanden [1] . Hvis en af hash-funktionerne er svag nok til at finde en kollision i den, vil den anden ikke være i stand til at styrke den resulterende hash. $C(x)=y(x)\|z(x)$ $y(x)$ $z(x)$ $y(x)$ $z(x)$

Kollisionsdetektionsmetoder

En af de enkleste og mest alsidige metoder til at finde kollisioner er fødselsdagsangrebet . Med dette angreb vil det kræve et gennemsnit på omkring operationer at finde en kollision for en bit -længde hash-funktion . Derfor betragtes en n -bit hash-funktion som sikker, hvis den beregningsmæssige kompleksitet ved at finde kollisioner for den er tæt på . $n$ $2^{{n/2}}$ $2^{{n/2}}$

Derudover er der et message lengthening attack , som, givet en kendt værdi , tillader en at beregne , hvor angiver sammenkædningen af . Udvidelsesangrebet for nogle hashfunktioner virker, selv mens det giver type 1 kollisionsmodstand , type 2 kollisionsmodstand og irreversibilitetsegenskaben . Det er underforstået, at det ikke er nødvendigt at vide , men det er nok kun at kende dens hash . Således kan du for eksempel tilføje yderligere oplysninger til en andens besked. Forskellige metoder bruges til at forhindre dette angreb: de tilføjer en ekstra hashing- runde , forskellig fra de foregående; brug flere hashing; eller brug en kombination af de to foregående metoder. $H(x)$ $H(x\|y)=H(H(x)\|y)$ $\|$ $x$

Men udvidelsesangrebet kan også betragtes fra den anden side: hvis vi har en besked , og hash-funktionen er sårbar over for udvidelsesangrebet, så er det let at finde en kollision af den første slags: , , , dvs. egenskaben for modstand mod kollisioner af den første art krænkes. $x$ $M_{1}=X\|Y$ $M_{2}=H(X)\|Y$ $H(M_{1})=H(M_{2})$

De fleste moderne hash-funktioner har samme struktur, baseret på opdeling af inputteksten i blokke og derefter iteration, hvor der bruges en funktion ved hver iteration , hvor x er den næste blok af inputteksten, og y er resultatet af den forrige. operation. Et sådant skema er dog ikke perfekt, da det, ved at kende funktionen , er muligt at analysere dataene i intervallerne mellem iterationer , hvilket letter søgningen efter kollisioner. $G(x,y)$ $G$

Ofte går det forud for at finde hashfunktionskollisioner af at finde dets pseudo -kollisioner , det vil sige to forskellige værdier af den indledende buffer, som for den samme besked giver lige store hashværdier.

Kollisioner mellem MD4 og MD5 hash-funktioner

I 1996 fandt Hans Dobbertin pseudo-kollisioner i MD5 ved hjælp af visse ikke-standard initialiseringsvektorer . Det viste sig, at det er muligt at bygge en anden besked til en kendt besked, sådan at den vil have samme hash som den originale. Ud fra et matematisk synspunkt betyder det, at MD5(IV,L1) = MD5(IV,L2) , hvor IV er startværdien af bufferen, og L1 og L2 er forskellige meddelelser.

I 2004 annoncerede de kinesiske forskere Wang Xiaoyun Yu Hongbo en sårbarhed, de havde opdaget i en algoritme, der gjorde det muligt for dem atog Lai Xuejia, Feng Dengguo, ) for at finde kollisioner.

I 2005 udgav forskerne Wang Xiaoyun og Yu Hongbo fra Shandong University i Kina en algoritme til at finde kollisioner i MD5-hash-funktionen , og deres metode virker for enhver initialiseringsvektor, ikke kun vektoren, der bruges af standarden. Ved at anvende denne metode på MD4 kan du finde en kollision på mindre end et sekund. Det gælder også for andre hash-funktioner såsom RIPEMD og HAVAL .

I 2008 offentliggjorde Alexander Sotirov, Marc Stevens, Jacob Appelbaum en artikel på den 25. Chaos Communication Congress, der viste muligheden for at generere falske digitale certifikater baseret på brugen af MD5-kollisioner.

SHA-1 hash funktion kollisioner

I januar 2005 offentliggjorde Vincent Rayman og Elisabeth Oswald et angreb på en afkortet version af SHA-1 (53 runder i stedet for 80 ), som gør det muligt at finde kollisioner i mindre end 280 operationer.

I februar 2005 præsenterede Wang Xiaoyun , Lisa Yin Yiqun og Yu Hongbo et angreb på fuld SHA-1, der kræver mindre end 269 operationer.

I august 2005, ved CRYPTO 2005, præsenterede de samme eksperter en forbedret version af angrebet på den fuldgyldige SHA-1, med en beregningsmæssig kompleksitet på 263 operationer. I december 2007 blev detaljerne i denne forbedring gennemgået af Martin Cochran.

Christophe de Kanier og Christian Rechberg præsenterede senere et forbedret angreb på SHA-1, for hvilket de blev tildelt det bedste papir på ASIACRYPT- konferencen i 2006 . De præsenterede en to-blok kollision på en 64-rund algoritme med en beregningsmæssig kompleksitet på omkring 2 35 operationer.

Da teoretiske angreb på SHA-1 har været succesfulde, planlægger NIST helt at udfase brugen af SHA-1 i digitale signaturer .

Kollisioner med andre hash-funktioner

RIPEMD- og HAVAL- hash-funktionerne er også sårbare over for MD5 -kollisionsalgoritmen udgivet af Wang Xiaoyun, Feng Dengguo, Lai Xuejia og Yu Hongbo i 2004.

For den anden modifikation af WHIRLPOOL hash-funktionen kaldet Whirlpool-T, foreslås ingen algoritmer til at finde kollisioner eller pseudo-kollisioner for 2009; en væsentlig begrænsning for at finde dem er kompleksiteten af selve funktionen og den store længde (512 bit) af outputnøglen.

Hash-funktionen GOST R 34.10-2001 med hensyn til kryptografisk styrke adskiller sig lidt fra GOST R 34.10-94 , idet den at finde kollisioner er reduceret til at beregne en diskret logaritme i en gruppe af punkter i en elliptisk kurve med formodentlig eksponentiel kompleksitet . For eksempel, for 256 - bit parametre, vil diskret logaritme ved hjælp af ρ-metoden eller Pollards λ-metode kræve ca. 2 operationer. ${10}^{{30}}$

Kollisionsopløsning i hashtabeller

Kollisioner komplicerer brugen af hash-tabeller , da de bryder en-til-en-korrespondancen mellem hash-koder og data. Der er dog specielle teknikker til at overvinde de vanskeligheder, der opstår:

Kædemetode : Teknologien til at kæde elementer (kæde) består i, at elementerne i sættet , som svarer til den samme hashværdi, er forbundet i en kædeliste. Positionsnummer i gemmer en pointer til toppen af listen over de elementer, hvis hashværdi af nøglen er lig med i; hvis der ikke er sådanne elementer i sættet, skrives NULL i position i .
Åben adressering : I modsætning til kædet hashing er der med åben adressering ingen lister, og alle poster gemmes i selve hashtabellen. Hver tabelcelle indeholder enten et dynamisk sætelement eller NULL.
Kollisionseliminering : I modsætning til de to foregående metoder elimineres tilstedeværelsen af kollisioner i hash-tabellen på tidspunktet for tilføjelse af elementer. Hash-koden for det adresserede element er hashen af informationen + en tilfældig værdi. Hvis hashkoden allerede er i tabellen, gendannes den tilfældige værdi, hvor elementet med en anden hash tilføjes til hashtabellen igen. Således er tilstedeværelsen af kollisioner udelukket, og elementer kan findes ved deres unikke hashes, som adresserer dem unikt i hashtabellen.

Noter

↑ Antoine Joux . Hentet 3. oktober 2017. Arkiveret fra originalen 19. maj 2017. (ubestemt)

Se også

Litteratur

Bruce Schneier , Applied Cryptography, 2. udgave, ISBN 0-471-11709-9 , kap.18, One-Way Hash Functions
Ross Anderson , Security Engineering , Wiley, ISBN 0-471-38922-6