MD5 Collisions

Altså det hjælper jo klart - det vil formindske chancen for kollision (ok, jeg skal faktisk ikke kunne svare 100% sikkert på det, da jeg ikke er helt inde i hvordan MD5 virker, men efter al min bredde viden om emnet antager jeg det) - men det er ikke at gardere sig helt ind.

Du må jo huske at MD5 har til opgave at lave en tilsyneladende tilfældig representation af noget data og "koge det ned til" 128bit kort sagt er min pointe at antallet af forskellige hashes du kan lave er endeligt (helt præcist 2^128 muligheder). Dvs. hvis data på længde X (i binær form) kan antage flere værdier (igen i binær form) end 2^128 - så kan du ikke med sikkerhed føle dig kollisions fri.

Nu skal det jo så siges at medmindre du er ved at indeksere RIGTIG mange dokumenter - vi snakker nok omkring en milliard eller lignende - så er chancen for kollision så forsvindende lille at der overhovedet ikke er grund til overhovedet at bekymre sig om dette.

Hvis du derimod har gang i at indeksere så mange dokumenter, må jeg så foreslå at skifte til et hash som har et større data område, f.eks. SHA-1?

Ved enhver form for hashing er der jo mange kollisioner. Det siger jo sig selv når man reducerer længden af tallet, så er der også færre valgmuligheder. Og det er ret simpel matematik at hvis du har alle tal af længden X bit, og md5 har længden 128, så vil der altid være kollisioner sålænge X>128, helt præcist vil der være mindst X/128 kollisioner for den værste hashværdi.

Men det er jo hele ideen med hashes at der sagtens kan forekomme kollisioner, men der er bare yderst lille sandsynlighed.

Hvis din brug ikke er sikkerhedskritisk (fx hvis du ikke er bange for at nogen laver laver dine binære filer bevidst med det formål at have kolliderende md5-værdier), så kan du sagtens bruge md5. Hvis det er en risiko i dit system at nogen bevidst prøver at lave filer med samme hashværdi, bør du bruge en bedre hashfunktion end md5.

Det med at prøve at kombinere flere funktioner som fx længde+md5 eller sha1+md5 skal man ikke prøve. Med mindre du er meget dybt inde i matematikken kan du ikke lave bedre hashfunktioner end de standardfunktioner der findes, og man risikerer bare at lavet hash'et dårligere.

Hejsa

Jeg sider og arbejder lidt med MD5 og jeg forsøger at afgøre omfanget af det impact MD5 collisions har på min anvendelse.

Så vidt jeg har forstået det vil MD5 á X stadig være unik såfremt alle X har samme længde? Er dette korrekt?

Nej. Der er 2^128 forskellige md5 hash værdier, så hvis dine data er 1000 bits lange, så vil der altså være en hel del kollisioner. Men det er usandsynligt, at du falder over dem uden at lede.

Mit formål er til at indeksere binære filer, jeg har behov for at afgøre om en bestemt fil er indekseret tidligere. Jeg laver derfor pt. en md5 sum af filen, og søger min database igennem.

Der er en, omend teoretisk, så ihvertfald en chance for at to filer kan have samme MD5 hash. Min løsning er at sammenligne både MD5 og filens længde, vil det være en skudsikker løsning?

Nej, men sikkert god nok. Ellers kan du (hvis du er paranoid nok) bruge både md5 og sha, så er den ved at være temmelig sikker.

Nej. Der er 2^128 forskellige md5 hash værdier, så hvis dine data er 1000 bits lange, så vil der altså være en hel del kollisioner. Men det er usandsynligt, at du falder over dem uden at lede.

Nu afhænger det jo ikke af hvor langt hans data (det som han vil hashe) er - men hvor mange stykker af disse data han har - og i tilfældet hvor data længden hæftes ved hashet også - hvor mange data af samme længde han besidder - eller forventer at komme i besiddelse af.

Ved enhver form for hashing er der jo mange kollisioner. Det siger jo sig selv når man reducerer længden af tallet, så er der også færre valgmuligheder. Og det er ret simpel matematik at hvis du har alle tal af længden X bit, og md5 har længden 128, så vil der altid være kollisioner sålænge X>128, helt præcist vil der være mindst X/128 kollisioner for den værste hashværdi.

Men det er jo hele ideen med hashes at der sagtens kan forekomme kollisioner, men der er bare yderst lille sandsynlighed.

Hvis din brug ikke er sikkerhedskritisk (fx hvis du ikke er bange for at nogen laver laver dine binære filer bevidst med det formål at have kolliderende md5-værdier), så kan du sagtens bruge md5. Hvis det er en risiko i dit system at nogen bevidst prøver at lave filer med samme hashværdi, bør du bruge en bedre hashfunktion end md5.

Det med at prøve at kombinere flere funktioner som fx længde+md5 eller sha1+md5 skal man ikke prøve. Med mindre du er meget dybt inde i matematikken kan du ikke lave bedre hashfunktioner end de standardfunktioner der findes, og man risikerer bare at lavet hash'et dårligere.

Han skal ikke lave sin egen, men at gemme BÅDE md5 OG sha (ikke en kombination ala (sha(md5($data))) er en helt almindelig teknik for at gøre det endnu sværere at generere kollisioner.