[ALG] Uniek algoritme

[Verwijderd]

Ik zoek een uniek algoritme. Hiermee bedoel ik, dat indien ik er iets bepaald insteek, een hash uitkrijg die zuiver uniek is.

Dit klinkt misschien als iets simpels, maar ik weet zelfs niet of het mogelijk is zoiets te creëeren.

voor effe sumpel te zeggen:
als x = y => H(x) = H(y)
en als x != y => H(x) != H(y)

MD5 & CRC32 benaderen dit een beetje (md5 nog vrij goed). Voor de rest eens gekeken naar Rijndael etc etc, maar in alle algoritmes bestaat er de mogelijkheid om dubbels te genereren.

Dus is het misschien beter voor mij om een paar algoritmes samen te gebruiken en dan te vertrouwen dat deze combinatie tussen als die algoritmes toch niet kan dubbelen of hoe zou ik dit het beste doen?

[Bart B]

Waarom wil je een zuiver unieke uitkomst met MD5 of CRC32? Kun je dan niet beter een methode nemen die ook te decrypten is (met sleutel)?

[Reptile209]

Is het mogelijk om aan te geven waar je het een en ander voor wil gaan gebruiken? Misschien zijn er dan makkelijker hints in de goede richting te geven...

[Opi]

Persoonlijk zou ik voor de laatste optie gaan. Overigens wil ik wel opmerken dat als een hash niet uniek is, dat niet wil zeggen dat ook daadwerkelijk één hash verschillende gebruikte inputs kan hebben. Hiermee bedoel ik dat de kans op sommige bepaalde inputs zo goed als 0 is.

Anders zou een hash naar mijn idee ook niet zinvol zijn; eerder een één-op-één mapping.

[Verwijderd]

encryptie heet zoiets.

[SWfreak]

Wat jij wil is een bijectieve afbeelding. Dus bij iedere 'bron' hoort precies een hash en bij iedere hash hoort precies een 'bron'. Het probleem met de meeste bekende hash-algoritmen (ik wou zeggen alle, maar dat weet ik natuurlijk niet zeker) is dat ze de bron afbeelden op een getal van beperkte lengte. Als je een bijjectieve afbeelding wil maken, dan moet het aantal mogelijke bronnen gelijk zijn aan het aantal mogelijke hashes. Dit is niet een eigenschap die je vaak zult tegenkomen, omdat het hele doel van een hash juist is om een kortere weergave van de bron te krijgen.
Het combineren van een aantal hash-algoritmen zal dan ook geen soelaas bieden, want zodra er uit de eerste hash voor twee verschillende bronnen hetzelfde uit komt, ben je al de pineut.
Zoals je uit bovenstaand verhaaltje misschien kunt afleiden, wordt het nogal lastig te realiseren wat jij wilt. Mag ik vragen waar je dit eigenlijk voor nodig hebt? Dan kunnen we misschien eens kijken of er misschien andere mogelijkheden zijn om het probleem op te lossen.

[Rukapul]

Zoals hierboven al gezegd is voldoet elke bijectieve functie.

Maar vertel eens wat de overige eisen zijn, bv:
- mag je van de 'hash' weer terug kunnen rekenen naar de origele waarde? Zo nee, gebruik een encryptie algorime met een (fixed) key. Zo ja, verzin zelf wat aangezien dat triviaal is.
- ???

[Tomatoman]

Het hangt nogal van het aantal inputwaarden af in hoeverre dit mogelijk is. Als voor iedere inputwaarde een unieke hash moet worden berekend en het aantal mogelijke inputwaarden is oneindig, is het mogelijke aantal hashes uiteraard ook oneindig. Daaruit volgt direct dat de hash oneindig lang moet zijn, wat nogal onpraktisch en zelfs onmogelijk is.

Wat jij zoekt is het gemakkelijkst te realiseren door een standaard encryptiemechanisme te kiezen. Zolang niemand de encryptiesleutel kent, is de versleutelde input onmogelijk terug te herleiden naar de originele input. Feitelijk is daarmee de versleutelde input equivalent aan een hash.

Bedenk verder dat als je n mogelijke inputwaarden allemaal wilt kunnen omzetten in een unieke hash, er minstens n mogelijke hashwaarden zijn. Daardoor is de hash (gerekend in het aantal benodigde bytes) altijd minstens even groot als de inputwaarde. Waarom zou je dan nog een hash willen gebruiken ?

[ Voor 3% gewijzigd door Tomatoman op 30-08-2003 18:10 ]

[Verwijderd]

zoals SWfreak al zei, ik wil een 1<->1 relatie leggen, maar dan wel kleiner gemaakt (moet gestokeerd worden in een database). Ook moet ik niet vanuit de 'hash' het originele prentje (in dit geval) terug kunnen vinden.

Ja, natuurlijk is het de bedoeling om de prenten te "verkleinen". Ik moet vanuit (laten we dit nu zo effe noemen) de hash NIET terug de prent kunnen afleiden. Ik weet dat ze daar aan aan het werken zijn, dat is holografie dacht ik. Maar dat zoek ik dus niet Mag wel, moet niet.

Dit is zoals ik het nu doe:
ik bereken CRC & MD5 van een prent & stokeer die in een databaseje.
Als er nu iemand anders eenzelfde prent submit weet ik van how! die staat hier al ergens in mijn directory tree... Maw, moet ik deze niet meer gaan opzoeken, wat me enorm veel werk bespaard.

Maar ik heb hier al een paar submits gekregen van verschillende prenten, maar die hebben zelfde EN crc EN md5 (misschien maar 5 op de 100k die ik nu al heb).

btw, als md5 van een prent hetzelfde is als een andere, betekend dit NIET dat de crc ook hetzelfde is hé! Dit zijn 2 verschillende algoritmes, dus 2 verschillende resultaten.

[ Voor 66% gewijzigd door Verwijderd op 30-08-2003 18:26 ]

[Rukapul]

*** voor edit ***

zoals SWfreak al zei, ik wil een 1<->1 relatie leggen, maar dan wel kleiner gemaakt (moet gestokeerd worden in een database). Ook moet ik niet vanuit de 'hash' het originele prentje (in dit geval) terug kunnen vinden.

Je oplossing heet compressie En daar zijn weer genoeg algoritmen voor beschikbaar

Met name als je niet weet welke invoerwaarden allemaal voor kunnen komen dan is een generiek compressie algoritme te gebruiken.
Weet je wel welke invoerwaarden voor kunnen komen dan kun je het algoritme er op toespitsen danwel een toepasselijk algoritme zoeken.

Als je vervolgens niet wilt dat het teruggerekend kan worden dan kun je
- bepaalde parameters van het compr
essiealgoritme geheim houden (niet cryptografisch sterk)
- de gecomprimeerde data door een encryptie-algoritme halen met een (fixed) key

*** na edit ***

Verwijderd schreef op 30 August 2003 @ 18:21:
Dit is zoals ik het nu doe:
ik bereken CRC & MD5 van een prent & stokeer die in een databaseje.
Als er nu iemand anders eenzelfde prent submit weet ik van how! die staat hier al ergens in mijn directory tree... Maw, moet ik deze niet meer gaan opzoeken, wat me enorm veel werk bespaard.

Maar ik heb hier al een paar submits gekregen van verschillende prenten, maar die hebben zelfde EN crc EN md5 (misschien maar 5 op de 100k die ik nu al heb).

btw, als md5 van een prent hetzelfde is als een andere, betekend dit NIET dat de crc ook hetzelfde is hé! Dit zijn 2 verschillende algoritmes, dus 2 verschillende resultaten.

Had bovenstaande info meteen gegeven!

Dezelfde md5 voor verschillende prenten is haast onmogelijk. De kans is veel groter dat je een fout hebt gemaakt bij het berekenen van de md5 hash (bereken je de hash wel over alle data?) dan dat 2 verschillende objecten dezelfde md5 waarde tot gevolg hebben. Er zijn 2^128 verschillende mogelijkheden voor een md5 waarde en de kans dat jij daar met je 100k = 2^17 gevallen een collission vindt is heel ongeloofwaardig

Voor jouw probleem moet elk hashing algoritme voldoen waarbij je niet een een secure hash algoritme hoeft te gebruiken. (SHA1 is trouwens 160 bits, MD5 128, CRC32 maar 32 wat de kans op collissions wel groter maakt uiteraard)

[ Voor 93% gewijzigd door Rukapul op 30-08-2003 18:37 ]

[Verwijderd]

Rukapul schreef op 30 August 2003 @ 18:24:

Had bovenstaande info meteen gegeven!

Ik was aan het typen

Dezelfde md5 voor verschillende prenten is haast onmogelijk. De kans is veel groter dat je een fout hebt gemaakt bij het berekenen van de md5 hash (bereken je de hash wel over alle data?) dan dat 2 verschillende objecten dezelfde md5 waarde tot gevolg hebben. Er zijn 2^128 verschillende mogelijkheden voor een md5 waarde en de kans dat jij daar met je 100k = 2^17 gevallen een collission vindt is heel ongeloofwaardig

Laten we er dan even van uitgaan dat de functie md5() in php niet deftig werkt?

Dus eigenlijk hoe groter de hash key, hoe minder kans op fouten... Hmmm misschien als ik dan SHA1 & Tiger samen pak... (160 & 192bits)... Als ik deze 2 samenpak, moet de combinatie toch vrij uniek zijn schijnt me.

Pfff, nu nog implementeren

[ Voor 16% gewijzigd door Verwijderd op 30-08-2003 18:40 ]

[Rukapul]

Verwijderd schreef op 30 August 2003 @ 18:38:
Laten we er dan even van uitgaan dat de functie md5() in php niet deftig werkt?

Dus eigenlijk hoe groter de hash key, hoe minder kans op fouten... Hmmm misschien als ik dan SHA1 & Tiger samen pak... (160 & 192bits)... Als ik deze 2 samenpak, moet de combinatie toch vrij uniek zijn schijnt me.

Pfff, nu nog implementeren

Voor je nu als een gek begint te implementeren lijkt het me verstandiger hier even exact uit de doeken te doen hoe je die md5 toepast. MD5 alleen zou voldoende moeten zijn.

[curry684]

Zolang MD5 voldoende is om zonder bekende clashes systemen als eDonkey en BitTorrent te laten draaien (we hebben het hier dus over honderden miljoenen gehashte bestanden...) vermoed ik op z'n zachtst gezegd ook een fout in jouw implementatie.

[ Voor 4% gewijzigd door curry684 op 30-08-2003 18:56 . Reden: foutje ]

[Verwijderd]

Rukapul schreef op 30 augustus 2003 @ 18:47:
Voor je nu als een gek begint te implementeren lijkt het me verstandiger hier even exact uit de doeken te doen hoe je die md5 toepast. MD5 alleen zou voldoende moeten zijn.

ik krijg een prent binnen, ik doe een readfile, ik doe md5 ik doe mysql_query & move_uploadedfile... Daar komt het op neer.

Ik kan nu niet aan de source aan (staat op't werk), maar the main idea staat hierboven.
En het moet echt heel nauwkeurig zijn, dat is 't grootste probleem. Ik kan ofc natuurlijk de prent in zijn gehele stokeren, maar dat is lange wachttijden (nog langer als nu) bij het uppen van een prent en mega-database. En ik mis cpupower & hdd ruimte daar op't werk

[vinnux]

De enige manier om er ZEKER 100% ipv 99,9999% van te zijn dat de link uniek is, is om exact de prent als link te gebruiken. Het enige wat je kunt doen is inderdaad compressie technieken. Maar waarom zou je die 0,00001% meer zekerheid willen hebben?

En simpele check of de MD5 hash al bestaat is genoeg. En ik kan je garanderen dat het geen 1 keer voorkomt.

Dus gewoon MD5 toepassen, kijken of deze al voorkomt zo ja dan plak je er iets achter ofzo.

[ Voor 13% gewijzigd door vinnux op 30-08-2003 19:01 ]

[ACM]

Verwijderd schreef op 30 augustus 2003 @ 18:21:
zoals SWfreak al zei, ik wil een 1<->1 relatie leggen, maar dan wel kleiner gemaakt (moet gestokeerd worden in een database). Ook moet ik niet vanuit de 'hash' het originele prentje (in dit geval) terug kunnen vinden.

Als je voor elke afbeelding een bepaalde waarde wilt en voor elke waarde een enkele afbeelding wilt, waarom geef je ze dan niet gewoon een uniek-identificerende ID-waarde? Zoals uit mysql's auto_increment af te leiden is bijvoorbeeld.

Ja, natuurlijk is het de bedoeling om de prenten te "verkleinen". Ik moet vanuit (laten we dit nu zo effe noemen) de hash NIET terug de prent kunnen afleiden. Ik weet dat ze daar aan aan het werken zijn, dat is holografie dacht ik. Maar dat zoek ik dus niet Mag wel, moet niet.

Wat wil je met de hash doen? Verifieren of de file goed is, of hem identificeren? Het eerste is prima te doen met een niet-uniek-garantie-hash en het tweede met een apart gegenereerde identificatie.

Als er nu iemand anders eenzelfde prent submit weet ik van how! die staat hier al ergens in mijn directory tree... Maw, moet ik deze niet meer gaan opzoeken, wat me enorm veel werk bespaard.

Ah, je wilt dus juist aan de hand van de crc/md5 bepalen of de file al bestaat...
Sla dan de bestandsgrootte, de md5/sha en de crc op, als die alle 3/4 gelijk zijn dan is het gewoon dezelfde file of je hebt een fout in je eigen testcode.

Maar ik heb hier al een paar submits gekregen van verschillende prenten, maar die hebben zelfde EN crc EN md5 (misschien maar 5 op de 100k die ik nu al heb).

Hoe zeker ben jij dat het verschillende afbeeldingen zijn die nog eens dezelfde filegrootte, crc en md5 hebben
Dat lijkt me vrijwel onmogelijk, kansrekeningstechnisch gezien... Magoed, je kan ook de ruwe afbeeldingsinformatie gebruiken ervoor, ipv de gecomprimeerde jpg/png/etc-files, misschien scheelt dat.

btw, als md5 van een prent hetzelfde is als een andere, betekend dit NIET dat de crc ook hetzelfde is hé! Dit zijn 2 verschillende algoritmes, dus 2 verschillende resultaten.

Nee, die zouden niet hetzelfde hoeven/mogen zijn.

Ik zou toch eerst eens op zoek naar fouten in je eigen software, als je in 100k 5 dezelfde md5-jes vindt die ook nog eens dezelfde crc's bevatten en ook nog eens even groot zijn...

Ow, wat je ook nog kan doen...

Gewoon alleen de md5 opslaan en als je dan een md5-clash tegenkomt, de files zelf beschouwen... Heb je 100% zekerheid met een simpele en snelle hashing.

[ Voor 4% gewijzigd door ACM op 30-08-2003 19:10 ]

[crisp]

een 1 op 1 hash zal in de meeste gevallen denk ik net zo groot zijn als het origineel, tenzij er op het origineel nog non-destructieve compressie toegepast kan worden....

je praat dan denk ik ook niet meer over een hash, maar meer over een versleuteling

[ Voor 21% gewijzigd door crisp op 30-08-2003 19:30 ]

[G33rt]

als je nou eens over een CRC32 een MD5 heenhaalt, word ie dan uniek of niet?

[curry684]

G33rt schreef op 30 augustus 2003 @ 19:25:
als je nou eens over een CRC32 een MD5 heenhaalt, word ie dan uniek of niet?

Niet meer, maximaal evenveel, wellicht minder.

[brokenp]

je mag nooit data dubbel hashen!!! in de bovenstaande suggestie doe je eigenlijk hetvolgende:
je hebt een oneindige range invoergetallen, en beeld dit af op een range van 2^32 (CRC32)
Deze range gooi je in MD5(128bits), maar aangezien md5 slechts een 32 bit invoer krijgt, zijn er slechts maximaal 2^32 verschillende md5 hashes mogelijk...

Je kan bij het hashen dus beter gewoon het beste hash algoritme nemen, of je voert de verschillende algoritme's naast elkaar uit op de originele data.

[Reptile209]

Verwijderd schreef op 30 August 2003 @ 18:21:

Maar ik heb hier al een paar submits gekregen van verschillende prenten, maar die hebben zelfde EN crc EN md5 (misschien maar 5 op de 100k die ik nu al heb).

Met de twijfel over deze zin in dit topic zou ik je vragen om beide plaatjes + MD5 te posten of te linken (mits toegestaan/niet verboden in de FAQ), dan worden er hier nog eens 30 verschillende encoders overheen gehaald. Kijken wie er gelijk heeft .

[slm]

Misschien zou je eens moeten kijken naar de veldgrootte (in de database) waar je je MD5 hash instopt. Waarschijnlijk is dat gewoon te klein en is de kans vervolgens een stuk groter dat je op dubbele hashwaarden stuit.

Edit/
er bestaat trouwens een functie md5_file() in php, speciaal voor files dus

[ Voor 17% gewijzigd door slm op 31-08-2003 00:19 ]

[MrBucket]

Verwijderd schreef op 30 August 2003 @ 18:21:
Maar ik heb hier al een paar submits gekregen van verschillende prenten, maar die hebben zelfde EN crc EN md5 (misschien maar 5 op de 100k die ik nu al heb).

Ehm, en je hebt ook gekeken naar de prenten die erbij horen, en dat zijn niet toevallig ook echt dezelfde bestanden? Lijkt me dat je met 100000 prenten best een paar keer dubbelen ertussen kunt hebben.
In dat geval werkt de methode perfect, maar klopt je dataset niet helemaal.

Ik weet niet, ik noem maar een dwarsstraat...

[Olaf van der Spek]

Verwijderd schreef op 30 August 2003 @ 18:21:
Dit is zoals ik het nu doe:
ik bereken CRC & MD5 van een prent & stokeer die in een databaseje.
Als er nu iemand anders eenzelfde prent submit weet ik van how! die staat hier al ergens in mijn directory tree... Maw, moet ik deze niet meer gaan opzoeken, wat me enorm veel werk bespaard.

Als dat de enige reden voor een hash is kun je wel een hash gebruiken, alleen moet je daarna ook nog even de bestanden controleren waarvan de hash matched. Dan hoef je niet al je prents langs te gaan, maar alleen de prents waarvan de hash matched. Dan heb je performance winst zonder verandering van functionaliteit.

Zou je die twee verschillende prents met zelfde md5 anders even kunnen uploaden?

[Verwijderd]

je kan de hash inderdaad opbouwen uit meerdere dingen.. bij bestanden bijvoorbeeld kan je de bestandsgroote, filename, modiefied timestamp etc MD5 hashen, die concateneren en opnieuw hashen... niet dat het heel veel uitmaakt..
een md5 hash blijft een 128 bit fingerprint.. dwz dat je altijd een beperkt aantal combinaties blijft houden.. de kans op dezelfde hash blijft altijd bestaan..

je kan echter wel de hash als primary key in je database zetten.. mocht het dan een keer voorkomen dat de hash al bestaat in de database.. dan zal hij een foutmelding geven.. of je maakt eerst een recursieve functie die kijkt of de hash al in de database staat.. (is wat netter )

ik hoop dat je er wat aan hebt

[Soultaker]

Een aantal domme 'slimme' trucs zijn al ontmaskerd, maar dit is er ook weer een:

Verwijderd schreef op 31 August 2003 @ 23:19:
je kan de hash inderdaad opbouwen uit meerdere dingen.. bij bestanden bijvoorbeeld kan je de bestandsgroote, filename, modiefied timestamp etc MD5 hashen, die concateneren en opnieuw hashen... niet dat het heel veel uitmaakt..

Bestandsgrootte meehashen helpt helemaal nergens voor, (dus ook niet "niet veel"; gewoon niets!) Het meehashen van bestandsnaam en wijzigingsdatum helpt ook niets voor het unieker maken van de hash, maar wijzigt wel het identificatiecritericum. Dat kan wel eens de bedoeling zijn: als je wilt dat een bestand van 0 bytes genaamd "a.jpg" als anders gezien wordt dan een bestand van 0 bytes genaamed "b.gif", dan moet je inderdaad de bestandsnaam meehashen; anders niet. Hetzelfde geldt voor wijzigingsdatum (waarvan ik me niet kan voorstellen dat 'ie relevant is).

Met het meehashen van irrelevante of impliciete gegevens (zoals de bestandsgrootte die toch al volgt uit de inhoud van het bestand) verhoog je wel je CPU gebruik, maar niet de kwaliteit van je hash code. (Wel krijg je een grotere weerstand tegen het brute force kraken van de invoer, maar daar gaat het hier niet om.) Als je de hash code vergelijkt voor het vergelijken, moet je je ook afvragen op basis van welke gegevens je bestanden als gelijk wilt beschouwen; meestal komen zaken als bestandsnaam en datum van laatste wijziging daar niet bij te pas.

SWfreak schreef op 30 August 2003 @ 17:51:
Het combineren van een aantal hash-algoritmen zal dan ook geen soelaas bieden, want zodra er uit de eerste hash voor twee verschillende bronnen hetzelfde uit komt, ben je al de pineut.

Het combineren door een hash algoritme over een hash code te halen, werkt inderdaad niet, maar je kunt wel twee hash codes concateneren en zo een grotere, sterke code verkrijgen. De kans dat verschillende invoer bij verschillende algoritmen dezelfde uitvoer opleveren, is bijzonder klein: als je dus twee verschillende bestanden hebt met dezelfde MD5-code, dan is het zeer onwaarschijnlijk dat ze ook nog dezelfde SHA-code hebben (en vice versa). Dat gaat natuurlijk alleen op zolang je verschillende algoritmen gebruikt.

In deze situatie zijn deze maatregelen echter overbodig; het gaat geloof ik over 100.000 relatief grote bestanden. De kans dat daar bestanden tussen zitten die verschillend zijn maar met een gangbare hash code dezelfde code opleveren, is miniem. Mocht het toch zo zijn, dan wil ik de bestanden in kwestie wel eens zien.

Tenslotte wil ik nog kwijt dat het niet zinnig is om een checksum (bv. CRC32) te gebruiken als hash code (zoals o.a. MD5) en vice versa. Verder is het waarschijnlijk ook niet zinnig om een hash code te gebruiken om lokaal aan een bestand te refereren (om bijvoorbeeld in een database een thumbnail aan een plaatje te koppelen); gebruik dan liever een eenmalig uniek gekozen database id.

[ Voor 4% gewijzigd door Soultaker op 01-09-2003 11:20 ]

[Reptile209]

Soultaker schreef op 01 September 2003 @ 11:18:
Tenslotte wil ik nog kwijt dat het niet zinnig is om een checksum (bv. CRC32) te gebruiken als hash code (zoals o.a. MD5) en vice versa. Verder is het waarschijnlijk ook niet zinnig om een hash code te gebruiken om lokaal aan een bestand te refereren (om bijvoorbeeld in een database een thumbnail aan een plaatje te koppelen); gebruik dan liever een eenmalig uniek gekozen database id.

De TS wil de hash volgens mij niet voor referentie gebruiken, maar alleen om te voorkomen dat hetzelfde bestand meer dan 1x in zijn database voorkomt.
Even een geschatte situatie:
TS heeft een p0rn sportfoto-server waarvoor iedereen uitgenodigd wordt om meer p0rn foto's te uploaden. Op een gegeven moment gaat iedere tennisliefhebber dezelfde foto's van Anna Kurnikova uppen, terwijl 1 kopietje voldoende is. Via die hash moet de DB dan zeggen dat de pic al bestaat (en dan evt zeggen waar hij staat, toch een indirecte referentie), ongeacht bestandsnaam/datum/etc.
Klopt dit, TS? Want je bent nog niet echt duidelijk in wat je nou wil bereiken...

[Soultaker]

Als dat de situatie is, dan zou ik gewoon dat bestand hashen (md5_file in PHP) en verder niet moeilijk doen. Meest simpele oplossing die werkt.

[Tomatoman]

De kans dat twee willekeurige foto's dezelfde MD5-hash hebben is 1/(2^128), er zijn immers 2^128 mogelijke hashes. Hierbij ga ik er dan wel vanuit dat de hashfunctie alle hashwaarden even vaak gebruikt; anders gezegd: dat er geen hashwaarden zijn die met geen enkele foto kunnen corresponderen. Natuurlijk is MD5 niet helemaal perfect, waardoor de kans dat de ene hashwaarde wordt berekend een stukje groter is dan dat een andere hashwaarde wordt berekend. De kans dat twee verschillende foto's dezelfde hashwaarde hebben wordt daardoor een stukje groter, laten we zeggen 1/(2^100). Dat is echter nog steeds een kans van 1 op 1267650600228229401496703205376. Zelfs als je een miljard foto's in de database hebt zitten is de kans op twee foto's met dezelfde hashwaarde 0,00000000000000000000078 - zeg maar gewoon nul.

Kortom, het is met MD5 hashing praktisch onmogelijk dat twee foto's dezelfde hashwaarde hebben. Je zult dus wel iets fout doen of beide foto's zijn daadwerkelijk precies gelijk aan elkaar.

[Soultaker]

tomatoman schreef op 01 September 2003 @ 13:02:
De kans dat twee verschillende foto's dezelfde hashwaarde hebben wordt daardoor een stukje groter, laten we zeggen 1/(2^100). Dat is echter nog steeds een kans van 1 op 1267650600228229401496703205376. Zelfs als je een miljard foto's in de
database hebt zitten is de kans op twee foto's met dezelfde hashwaarde 0,00000000000000000000078 - zeg maar gewoon nul.

Volgens mij klopt die berekening niet; je doet 1/(2^100) * 1.000.000.000, maar feitelijk is de kans dat er bij een miljard foto's (tenminste) twee dezelfde waarde hebben, veel groter.

De exacte berekening weet ik niet zo 1-2-3, maar het is te vergelijken met de berekening dat er in een schoolklas in de orde van 50% kans is dat er tenminste twee personen op dezelfde dag jarig zijn, terwijl de simpele berekening van (1/365)*30 minder doet vermoeden (zo'n 8%).

Kortom, het is met MD5 hashing praktisch onmogelijk dat twee foto's dezelfde hashwaarde hebben. Je zult dus wel iets fout doen of beide foto's zijn daadwerkelijk precies gelijk aan elkaar.

Bij die conclusie kan ik me echter wel aansluiten.

[Olaf van der Spek]

Soultaker schreef op 01 September 2003 @ 13:55:
De exacte berekening weet ik niet zo 1-2-3, maar het is te vergelijken met de berekening dat er in een schoolklas in de orde van 50% kans is dat er tenminste twee personen op dezelfde dag jarig zijn, terwijl de simpele berekening van (1/365)*30 minder doet vermoeden (zo'n 8%).

Iedereen moet dan op een andere dag jarig zijn. Dus je krijgt iets als 365 * 364 * 363 * 362 * 361 / 365^5 volgens mij.

[ACM]

De berekening wordt verstoord door het feit dat je elke combinatie van twee (of meer) moet hebben, ipv alleen maar het aantal files enzo beschouwd.

De kans dat twee of meer mensen van de tien op dezelfde dag jarig zijn is dan ook iets ala: 1 - 365/365 * 364/365 * 363/365 ... * 356/365 (1 - de kans dat ze allemaal een eigen dag hebben) en dat is 12%
Je kan wel raden dat de kans dat 30 mensen _niet_ op dezelfde dag jarig zijn aardig wat kleiner is, dan 10 (die slechts 88% is).

't Zelfde zal ook voor de hashed files gelden, dus 1 - alle hashes / alle hashes * alle hashes - 1 / alle hashes * ... * alle hashes - aantal files / alle hashes

En hoewel die kans nog steeds vrij klein is, is dat met een miljard files die volkomen random gekozen en een volkomen random hash hebben gekregen al akelig groot aan het worden.
Let ook op de 'volkomen random' termen, want een hash en de file inhoud zullen niet volkomen random zijn...
Ondanks dat is de kans op dubbele bestanden bij 100k files nog steeds erg klein en is de simpele workaround natuurlijk het domweg controleren van de fysieke files.

Maar met een plaatjes-server ben je er dan nog niet, aangezien twee dezelfde afbeeldingen prima kunnen verschillen. Bijvoorbeeld omdat de ene png is en de andere jpg of de ene een paar pixels groter is dan de andere...