Hash Collision

Hva er Hash Collision?

Hash Collision skjer når to forskjellige inndata gir nøyaktig samme hashverdi. Tenk deg to ulike nøkler som på en merkelig måte åpner samme digitale lås. Sjelden, men hvis det skjer med en svak algoritme, kan det skape problemer.

Hvordan Hash Collision fungerer

Tenk på en hash som en liten etikett for store mengder data. Her er en kort gjennomgang fra inndata til problem.

1. Inndata: Du starter med en melding, fil eller transaksjon.
2. Hash: En funksjon fra familien av kryptografiske hashfunksjoner gjør den inndataen om til en streng med fast lengde.
3. Kollisjon: Fordi utdata er begrenset mens inndata kan være uendelige, kan to forskjellige inndata gi samme utdata.
4. Angrep: En alvorlig trussel er når noen bevisst kan utforme to forskjellige inndata som kolliderer, og så bytte den ene med den andre.
5. Forsvar: Gode algoritmer gjør den søken astronomisk kostbar, så tilfeldig gjetting koster tid og penger.

Ja, det er poenget.

Hvorfor Hash Collision er viktig

Hvorfor bør du bry deg om dette stille området i matematikk og kode?

• Fordel: Sterk motstand holder dine dataetiketter unike, noe som gir mindre rom for lureri.
• Perspektiv: Kollisjoner truer integriteten for ting som blockchain, programvareoppdateringer og filverifisering.
• Relevans: Du møter det i lommebøker, børser, bevis og revisjonsverktøy som stoler på hashlikhet.

Hovedtrekk ved Hash Collision

Hva som gjør dette fenomenet spesielt og verdt å merke seg:

• Uunngåelig: Med et begrenset antall utdata og ubegrensede inndata vil noen par kollidere.
• Vanskelig: For moderne hasher er det laget for at det skal være beregningsmessig svært krevende å finne en kollisjon med vilje.
• Signaturer: Mange digitale signaturer signerer en hash, så kollisjonssikkerhet beskytter de som signerer mot å bli lurt av bytteangrep.

Hvordan beregnes Hash Collision?

Du kan anslå arbeidet med fødselsdagsparadokset. For en k bits hash er antall tilfeldige forsøk som trengs for omtrent femti prosent sjanse for en kollisjon omtrent kvadratroten av to opphøyd i k, ganget med cirka 1.1774.

n_fifty_percent ≈ 1.1774 * sqrt(2^k)

Eksempel: med k lik 256 er antallet forsøk ufattelig stort, derfor er brute force for å finne en kollisjon ikke et helgeprosjekt.

Varianter

Ulike varianter dukker opp i forskning og angrep:

• Kollisjon: To forskjellige inndata deler samme hash.
• Second preimage: Gitt én inndata, finn en annen som matcher dens hash.
• Preimage: Gitt en hash, finn en inndata som gir den.
• Prefix: Valgt prefix-kollisjon lager to meldinger med ulike valgte starter som ender med samme hash.

Eksempel

Hvis en angriper kunne lage to forskjellige transaksjoner med samme txid, kunne de prøve et dobbelbruktriks ved å bytte ut den ene etter at du har signert.

Morsomt faktum

MD5 kollisjoner ble demonstrert for flere tiår siden, og prosjektet SHAttered viste en offentlig SHA 1 kollisjon med to forskjellige PDFer, en hendelse som førte til at bransjen gikk bort fra den.

Oppsummering

Kort sagt er Hash Collision den sjeldne situasjonen hvor to forskjellige inndata deler ett digitalt fingeravtrykk, og moderne kryptografi gjør mye for å holde det som et sjeldent trivia og ikke en reell trussel.