Is het mogelijk om identieke SHA1-hash te krijgen?

Gegeven twee verschillende strings S1 en S2 (S1 != S2) is het mogelijk dat:

SHA1(S1) == SHA1(S2)

is waar?

1. Zo ja – met welke kans?
2. Zo niet – waarom niet?
3. Is er een bovengrens voor de lengte van een invoertekenreeks, waarvoor de kans op duplicaten 0 is? OF is de berekening van SHA1 (vandaar de kans op duplicaten) onafhankelijk van de lengte van de string?

Het doel dat ik probeer te bereiken is om een ​​gevoelige ID-string te hashen (mogelijk samengevoegd met enkele andere velden zoals ouder-ID), zodat ik in plaats daarvan de hash-waarde als ID kan gebruiken (bijvoorbeeld in de database).

Voorbeeld:

Resource ID: X123
Parent ID: P123

Ik wil de aard van mijn bronidentificatie niet onthullen zodat de klant “X123-P123” kan zien.

In plaats daarvan wil ik een nieuwe kolomhash (“X123-P123”) maken, laten we zeggen dat het AAAZZZ is. Dan kan de klant een resource aanvragen met id AAAZZZ en weet hij niet van mijn interne id’s enz.

Antwoord 1, autoriteit 100%

Wat u beschrijft, wordt een botsinggenoemd. Er zijn noodzakelijkerwijs botsingen, aangezien SHA-1 veel meer verschillende berichten als invoer accepteert en verschillende uitvoer kan produceren (SHA-1 kan elke reeks bits tot 2^64 bits opeten, maar voert slechts 160 bits uit; dus ten minste één uitvoer waarde moet meerdere keren verschijnen). Deze observatie is geldig voor elke functie met een output die kleiner is dan de input, ongeacht of de functie een “goede” hashfunctie is of niet.

Ervan uitgaande dat SHA-1 zich gedraagt ​​als een “willekeurig orakel” (een conceptueel object dat in feite willekeurige waarden retourneert, met als enige beperking dat zodra het uitvoer vheeft geretourneerd op invoer m, het moet daarna altijd vretourneren op invoer m), dan moet de kans op een botsing, voor elke twee verschillende strings S1 en S2, 2^(- zijn 160). Nog steeds in de veronderstelling dat SHA-1 zich als een willekeurig orakel gedraagt, als je veel invoerstrings verzamelt, zul je botsingen gaan waarnemen nadat je ongeveer 2^80 van dergelijke strings hebt verzameld.

(Dat is 2^80 en niet 2^160 omdat je met 2^80 snaren ongeveer 2^159 paar snaren kunt maken. Dit wordt vaak de “verjaardagsparadox” genoemd omdat het voor de meeste mensen als een verrassing komt wanneer toegepast op botsingen op verjaardagen. Zie de Wikipedia-paginaover dit onderwerp.)

Nu vermoeden we sterk dat SHA-1 zich nietecht gedraagt ​​als een willekeurig orakel, omdat de verjaardag-paradox-benadering het optimale algoritme voor het zoeken naar botsingen is voor een willekeurig orakel. Toch is er een gepubliceerde aanval die een botsing zou moeten vinden in ongeveer 2^63 stappen, dus 2^17 = 131072 keer sneller dan het verjaardag-paradox-algoritme. Zo’n aanval zou niet uitvoerbaar moeten zijn op een echt willekeurig orakel. Let wel, deze aanval is niet echt voltooid, het blijft theoretisch (sommige mensen hebben geprobeerd maar konden blijkbaar niet genoeg CPU-kracht vinden )(Update:vanaf begin 2017 heeft iemand heefteen SHA-1-botsingmet de bovengenoemde methode, en het werkte precies zoals voorspeld). Toch ziet de theorie er goed uit en het lijkt er echt op dat SHA-1 geen willekeurig orakel is. Dienovereenkomstig, wat betreft de kans op een botsing, zijn alle weddenschappen uitgeschakeld.

Wat betreft uw derde vraag: voor een functie met een n-bit uitvoer, dan zijn er noodzakelijkerwijs botsingen als u meer dan 2^nverschillende berichten kunt invoeren, dwz als de maximale lengte van het invoerbericht groter is dan n. Met een grens mlager dan nis het antwoord niet zo eenvoudig. Als de functie zich gedraagt ​​als een willekeurig orakel, dan wordt de kans op het bestaan ​​van een botsing kleiner met m, en niet lineair, maar met een steile grens rond m=n/2. Dit is dezelfde analyse als de verjaardagsparadox. Bij SHA-1 betekent dit dat als m < 80dan is de kans groot dat er geen botsing is, terwijl m > 80maakt het bestaan ​​van ten minste één botsing zeer waarschijnlijk (met m > 160wordt dit een zekerheid).

Merk op dat er een verschil is tussen “er bestaat een botsing” en “u vindt een botsing”. Zelfs als er een botsing moetbestaan, heb je nog steeds je 2^(-160) kans elke keer dat je het probeert. Wat de vorige paragraaf betekent, is dat zo’n kans nogal zinloos is als je (conceptueel) geen 2^160 paar strings kunt proberen, b.v. omdat je je beperkt tot strings van minder dan 80 bits.

Antwoord 2, autoriteit 29%

Ja, het is mogelijk vanwege het duivengatprincipe.

De meeste hashes (ook sha1) hebben een vaste uitvoerlengte, terwijl de invoer een willekeurige grootte heeft. Dus als je lang genoeg probeert, kun je ze vinden.

Crypografische hashfuncties (zoals de sha-familie, de md-familie, enz.) zijn echter ontworpen om dergelijke botsingen te minimaliseren. De best bekende aanval kost 2^63 pogingen om een ​​botsing te vinden, dus de kans is 2^(-63), wat in de praktijk 0 is.

Antwoord 3, autoriteit 5%

gitgebruikt SHA1-hashes als ID’s en er zijn noggeen bekende SHA1-botsingen in 2014. Het SHA1-algoritme is duidelijk magisch. Ik denk dat het een goede gok is dat er geen botsingen bestaan ​​voor snaren van jouw lengte, zoals ze inmiddels zouden zijn ontdekt. Als u magie echter niet vertrouwt en geen gokker bent, kunt u willekeurige reeksen genereren en deze koppelen aan uw ID’s in uw DB. Maar als u SHA1-hashes gebruikt en de eerste wordt die een botsing ontdekt, kunt u uw systeem op dat moment gewoon wijzigen om willekeurige tekenreeksen te gebruiken, waarbij u de SHA1-hashes behoudt als de “willekeurige” reeksen voor oudere ID’s.

Antwoord 4, autoriteit 4%

Een botsing is bijna altijd mogelijk in een hash-functie. SHA1 is tot op heden behoorlijk veilig geweest in het genereren van onvoorspelbare botsingen. Het gevaar is dat wanneer botsingen kunnen worden voorspeld, het niet nodig is om de originele hash-invoer te kennen om dezelfde hash-uitvoer te genereren.

Er zijn bijvoorbeeld vorig jaar aanvallen op MD5 gedaan tegen het ondertekenen van SSL-servercertificaten, zoals te zien is op de Beveiliging Nupodcastaflevering 179. Hierdoor konden geavanceerde aanvallers een nep SSL-servercertificaat genereren voor een frauduleuze website en dit leek de echte zaak te zijn. Om deze reden wordt het ten zeerste aanbevolen om geen door MD5 ondertekende certificaten te kopen.

Antwoord 5, autoriteit 3%

Waar je het over hebt heet een botsing. Hier is een artikel over SHA1-botsingen:
http://www.rsa.com/rsalabs/node.asp?id= 2927

Bewerken: Dus een andere antwoorder was me voor met het noemen van het duivengatprincipe LOL, maar om dit te verduidelijken, is dit waarom het het duivengatprincipe wordt genoemd, want als je wat gaten hebt uitgesneden voor postduiven om in te nestelen, maar je hebt meer duiven dan gaten, dan moeten sommige duiven (een invoerwaarde) een gat delen (de uitvoerwaarde).