Câte elemente aleatoare înainte ca MD5 să producă coliziuni?

Am o bibliotecă de imagini pe Amazon S3. Pentru fiecare imagine, am adresa URL sursă de pe serverul meu, plus un marcaj de timp pentru a obține un nume unic de fișier. Deoarece S3 nu poate avea subdirectoare, trebuie să stochez toate aceste imagini într-un singur director plat.

Trebuie să-mi fac griji în legătură cu coliziunile din valoarea hash-ului MD5 care se produce?

Bonus: Câte fișiere aș putea să am înainte de a începe să văd coliziuni în valoarea hash pe care MD5 o produce?

131
Răspunsul literal este că fișierul secundar ar putea avea același MD5 ca și primul. Cu toate acestea, cotele sunt extrem de mici.
adăugat autor Rick James, sursa

8 răspunsuri

Probabilitatea a doar două lovituri accidentale care se ciocnesc este 1/2 128 care este 1 în 340 undecillion 282 decillion 366 nonion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 cvadrilioane 607 trilioane 431 miliarde 768 milioane 211 mii 456.

Cu toate acestea, dacă păstrați toate hash-urile, atunci probabilitatea este mai mare datorită paradoxului zilei de naștere . Pentru a avea șanse de 50% ca orice hash să se ciocnească cu orice alt hash, aveți nevoie de hashes 2 64 . Aceasta înseamnă că pentru a obține o coliziune, în medie, va trebui să spargeți 6 miliarde fișiere pe secundă timp de 100 de ani .

238
adăugat
Deci, spui că există o șansă!
adăugat autor vargonian, sursa
"probabilitatea de coliziune este 1/2 ^ 64" - ce? Probabilitatea coliziunii depinde de numărul de elemente deja rulate, nu este un număr fix. De fapt, este egal cu exact 1 - sPn/s ^ n , unde s este dimensiunea spațiului de căutare ( 2 ^ 128 acest caz) și n reprezintă numărul de elemente rulate. Ceea ce probabil vă gândiți este 2 ^ 64 , care este numărul aproximativ de elemente de care aveți nevoie pentru ca MD5 hash să aibă o șansă de coliziune de 50%.
adăugat autor BlueRaja - Danny Pflughoeft, sursa
JørgenFogh: Și toate legile fizicii nu sunt "corecte" nici. Un astfel de nivel de pedantism nu este necesar deoarece nu schimbă răspunsul într-un mod semnificativ.
adăugat autor Kornel, sursa
@yaauie Nu, e cu totul imposibil. Vorbesc despre generarea a 2 ^ 64 hashes din 2 ^ 128 posibile. Este vorba de un sfert de unu la sută din totalul tuturor canalizărilor posibile generate.
adăugat autor Kornel, sursa
@ BlueRaja-DannyPflughoeft, ceea ce am avut în minte într-adevăr. Mulțumesc pentru corecție.
adăugat autor Kornel, sursa
@ConcernedOfTunbridgeWells: Am făcut corecție pentru paradoxul zilei de naștere, motiv pentru care răspunsul este în miliarde, nu în cifre. Nu am putut verifica probabilitatea cu scriptul dvs. PV = 2 ** 128; SS = 2 ** 64 : OverflowError: lung int prea mare pentru a converti la int
adăugat autor Kornel, sursa
Nu este strict adevărat. Probabilitatea unei coliziuni este mult mai mare decât aceasta, deoarece o nouă adresă URL ar putea intra în coliziune cu orice element existent din tabel. Vedeți această postare (disclaimer, i-am scris) în jos pe matematică și un mic script Python care poate fi adaptat pentru a calcula probabilitatea unui anumit număr de adrese URL.
adăugat autor ConcernedOfTunbridgeWells, sursa
Din păcate, încă nu sunteți corect. Presupunem că funcția hash este cu adevărat aleatoare. Nu este. Aceasta înseamnă că probabilitatea de coliziune este mai mare.
adăugat autor Jørgen Fogh, sursa
+1 pentru adăugarea calculului. Acest lucru este puțin mai precis: http://www.google.com/search?q=2=64%2F100* (secunde + pe + ani)
adăugat autor Mathias Bynens, sursa
(Aceasta înseamnă că pentru a obține o coliziune, în medie, va trebui să rupă 6 miliarde de fișiere pe secundă timp de 100 de ani.); incorect. acest lucru înseamnă că, de timpul , ați fost șase miliarde de fișiere pe secundă timp de 100 de ani, 50% din hash-urile pe care le generați s-ar ciocni cu hashes-urile generate anterior.
adăugat autor yaauie, sursa
+1 pentru că am dorit mereu să știu cum să numărez un trecut de 999 trilioane de lol (și da, răspunsul dvs. a fost informativ)
adăugat autor Kmeixner, sursa
Intuitiv dacă ignorăm paradoxul zilei de naștere și analizăm doar o soluție aproximativă: Adăugați 2 ^ 64 hashes într-o listă. Acum adăugați încă un hash la lista respectivă. Acest hash mai are șansa de coliziune 1/2 ^ 128 times 2 ^ 64 , adică un hash mai are un cod <1> cod> șansa unei coliziuni. Acum adăugați alte coduri 2 ^ 64 în listă și ar trebui să obțineți o coliziune. Faceți același calcul pentru 2 ^ 63 (și notați 2 ^ 63 + 2 ^ 63 = 2 ^ 64 ).
adăugat autor robocat, sursa

S3 poate avea subdirectoare. Doar puneți un "/" în numele cheii și puteți accesa fișierele ca și cum ar fi fost în directoare separate. Eu folosesc acest lucru pentru a stoca fișierele utilizator în foldere separate pe baza ID-ul lor de utilizator în S3.

De exemplu: "mybucket/users/1234/somefile.jpg". Nu este exact același ca un director într-un sistem de fișiere, dar API-ul S3 are câteva caracteristici care permit funcționarea aproape la fel. Pot să-i cer să afișeze toate fișierele care încep cu "users/1234 /" și îmi va arăta toate fișierele din acel "director".

22
adăugat
Acesta ar trebui să fie un conținut pe care îl consider, deoarece nu răspunde la întrebarea despre probabilitatea unei coliziuni
adăugat autor Ian Clark, sursa

Așteaptă, deci:

md5(filename) + timestamp

sau:

md5(filename + timestamp)

În cazul în care primul, sunteți de cele mai multe ori la un GUID, și nu aș face griji despre asta. În cazul în care acesta din urmă, a se vedea postul lui Karg despre modul în care veți colizi în cele din urmă.

16
adăugat
@BradThomas: Nu. Riscul de coliziune MD5 este același indiferent dacă este vorba de numele fișierului sau de combinația de nume de fișier + marca de timp. Dar, în primul scenariu, va trebui să aveți atât o coliziune MD5, cât și o coliziune de timbru.
adăugat autor Vincent Hubert, sursa
Acest lucru lasă în continuare o șansă de 2 ^ (128 ^ 60) de coliziune cu doi utilizatori pe minut. În mod inutil literal.
adăugat autor Berry M., sursa
Vă rugăm să detaliați modul în care includerea timestampului mărește șansa de coliziune
adăugat autor Brad Thomas, sursa
@BradThomas Pentru a fi mai clară: md5 (filename) + timestamp reduce riscul de coliziune masiv pentru că ar trebui să aveți o coliziune MD5 pentru exact același timestamp pentru a avea o coliziune globală. md5 (nume fișier + timestamp) este identic cu md5 (nume fișier) . rezultatul și problema zilei de naștere există în continuare în toate hashes-urile din md5).
adăugat autor robocat, sursa

O regulă gravă a coliziunilor este rădăcina pătrată a intervalului de valori. Sigla dvs. MD5 este probabil lungă de 128 de biți, astfel încât veți avea tendința de a vedea coliziunile de mai sus și dincolo de 2 ^ 64 de imagini.

10
adăugat
en.wikipedia.org/wiki/Birthday_Problem Mai multe informații despre această problemă.
adăugat autor Georg Schölly, sursa
Probabil că vrei să spui 128 de biți, nu 2 ^ 128. :-)
adăugat autor JesperE, sursa

Deși coliziunile MD5 aleatorii sunt extrem de rare, dacă utilizatorii pot furniza fișiere (care vor fi stocate în mod verbale), atunci pot interveni coliziuni de inginerie. Asta este, ei pot crea în mod deliberat două fișiere cu același MD5sum, dar date diferite. Asigurați-vă că aplicația dvs. poate gestiona acest caz într-un mod sensibil sau poate utiliza un hash mai puternic ca SHA-256.

7
adăugat
folosind o sare ar avea grijă de problema inginerie utilizator, nu?
adăugat autor StackOverflowed, sursa
Depinde de modul în care este aplicată sarea. Ar trebui să fie un prefix al datelor furnizate de utilizator, sau mai bine cheia pentru un HMAC. Este totuși probabil o idee bună de a practica apărarea în profunzime.
adăugat autor bdonlan, sursa
Notă, deși SHA256 are o lungime de 256 de biți, puteți compromite riscul coliziunilor cu lungimea cheii pe care o stocați prin trunchierea SHA256 la mai puțini biți, de ex. utilizați SHA256, dar trunchiați-l la 128 de biți (care este mai sigur decât utilizarea MD5, chiar dacă acestea au același număr de biți).
adăugat autor robocat, sursa

Deși au apărut probleme cu MD5 datorită coliziunilor, coliziunile UNINTENTIONAL între datele aleatorii sunt extrem rare. Pe de altă parte, dacă aveți hashing pe numele fișierului, nu sunt date aleatorii și m-aș aștepta la coliziuni rapide.

3
adăugat
Singura problemă pe care o am cu exemplul Taylors este că, dacă cineva primește o copie a bazei dvs. de date, ar putea să-și dea seama probabil numerele cărților de credit folosind o masă de curcubeu ...
adăugat autor Sam Saffron, sursa
În timp ce nu aș alege să folosesc MD5 pentru carduri de credit, o masă Rainbow cu toate numerele cărților de credit valabile între 10.000.000 (8 cifre fiind cea mai mică carte de credit pe care am văzut-o) și 9.999.999.999.999.999 (cel mai mare număr de 16 cifre) tabel pentru a genera. Există probabil modalități mai ușoare de a fura numerele respective.
adăugat autor acrosman, sursa

Coliziunea MD5 este extrem de puțin probabilă. Dacă aveți MD5 9 trilioane , există o singură șansă în 9 trilioane că va exista o coliziune.

0
adăugat
Multe dintre celelalte răspunsuri vorbesc despre probabilitatea unei coliziuni la adăugarea unui element unul mai mare. Cred ca raspunsul meu este mai util pentru ca vorbeste probabil despre intregul tabel cu un dup.
adăugat autor Rick James, sursa

Nu contează cu adevărat cât de posibil este; este posibil. S-ar putea întâmpla în primele două lucruri pe care le-ați avut (foarte puțin probabil, dar posibil), deci va trebui să sprijiniți coliziunile de la început.

0
adăugat
Există, desigur, multe alte lucruri rele care se pot întâmpla cu o probabilitate de 1/2 ^ 128. S-ar putea să nu vrei să-l lăsați pe acesta să-și facă griji.
adăugat autor Will Dean, sursa
Nu poți fi serios. Va trebui să spargeți 6 miliarde de fișiere pe secundă, fiecare secundă timp de 100 de ani pentru a obține șanse mari de coliziune. Chiar daca esti foarte ghinionist, probabil ca ar fi nevoie de o capacitate mai mare de S3 folosita mai mult decat o viata umana.
adăugat autor Kornel, sursa
Cel mai rău lucru care se poate întâmpla aici este că poți obține o fotografie. Pentru un număr relativ mic, nu mi-aș face griji. Acum, dacă software-ul dvs. controlează un autopilot care aterizează o aeronavă, aceasta este o altă poveste.
adăugat autor Jim C, sursa
Este de miliarde de ori mai probabil ca baza dvs. de date și backup-urile să nu reușească. Coliziunile nu merită să vă faceți griji.
adăugat autor Artelius, sursa
Utilizați timpul de prevenire a coliziunii construind un buncăr pentru a pune serverul dvs.! Aceste meteori plictisitori vă pot lovi (foarte puțin probabil, dar posibil), așa că va trebui să sprijiniți adăpostul meteorilor de cerșit.
adăugat autor polvoazul, sursa
Ar fi nevoie de 100 de ani pentru a obține o șansă de coliziune 50% la 6G/sec. Aveți o șansă de coliziune bună de câteva decenii mai devreme.
adăugat autor user327961, sursa