CRC32B dubbele output

[L0g0ff]

Dag Allemaal,

Ik ben aan het kijken om een 9 cijferige ASCII code om te zetten naar een CRC32B code (123456789 = CBF43926). Deze CRC output moet alleen uniek zijn en ik moet er zeker van zijn dat een 9 cijferige code nooit dezelfde CRC uitput krijgt.

Nu heb ik al gevonden dat de kans 1 op 4 miljard is dat de output hetzelfde is maar er zal toch maar net een dubbele tussen zitten dan heb ik een probleem met de dubbele waarde.

Nu heb ik geprobeerd de formule om te rekenen maar ik ben er achter gekomen dat mijn hersens dat niet aankunnen

Is er iemand die me dit zo kan vertellen?

Groeten,
Thomas

[farlane]

Ehm, waarom zorg je niet gewoon dat de code uniek is dan? Trouwens, CRC32B kende ik niet maar het lijkt ook eigenlijk niet te bestaan, het is een PHP dingetje dat eigenlijk een 'normale' CRC32 is.

[ Voor 54% gewijzigd door farlane op 29-10-2014 16:00 ]

[YellowOnline]

Deze formule (hash collision) bedoel je?

The probability of collision between n files in H space is typically written as:

1 - e ^(-n^2 / 2 * H) or 1 - e ^ (-n(n-1) / 2 * H), which is nearly the same for large numbers.

Where n is the number of evenly distributed hashes to compare and H is the size of the element count of all possible hashes.

This means that you stand a 1% chance of collision with roughly 10,000 hashes, and you stand a 50% chance of collision with roughly 80,000 hashes.

If you want to be really sure that you don't have a collision, make your hash the same size as your data (duh). That is, clearly, unhelpful advice.

Bron

[RobIII]

Als je uitsluitend 9 digits moet omzetten dan heb je helemaal geen CRC nodig en heb je automatisch 0 collisions. 9 digits passen makkelijk in 32 bits -> elke combinatie is uniek want dat is 't getal (als integer) gewoon zélf. Ik snap dus niet waarom je zou gaan ouwehoeren met CRC's.

Wil je 't dan nog een beetje "spannend" maken dan representeer je het getal gewoon als (al-dan-niet zero-padded) hexadecimale value (dus: 999999999₁₀ => 3B9AC9FF₁₆, 123456789₁₀ => 075BCD15₁₆) et voila. (zie Getallen en talstelsels FAQ). Maar linksom of rechtsom; als je enkel de getallen 0 t/m 99999999 wil "hashen" in een space van 32 bits dan is het getal automatisch de hash (althans: dat zou ik doen en is gegarandeerd 0 kans op collisions).

[ Voor 52% gewijzigd door RobIII op 29-10-2014 16:22 ]

[frickY]

Ik sluit me volledig aan bij RobIII

[L0g0ff]

De reden waarom het CRC32 moet zijn is omdat dit niet zomaar terug te rekenen is naar het oorspronkelijke getal. Dit is namelijk iets wat in mijn geval niet mag (iig niet op het eerste oog). Ik begrijp dat ik beter met hash + salt kan werken, maar dat is in mijn geval echt niet nodig.

Ik wil dus de getallen 000000000 t/m 999999999 hashen in idd een 32bits hash. Begrijp ik RobIII nu goed en dat dit geen collisions oplevert?

Nee dus Zoals ik aangaf kan ik helaas geen getal gebruiken. Dit moet echt een hash zijn.

Is er misschien een andere hash vorm met het zelfde resultaat waar ik zeker van kan zijn dat 000000000 t/m 999999999 geen collisions oplevert? Het liefst wel een hash methode waar het niet zomaar terug te rekenen is en die maar 8 karakters heeft.

[ Voor 30% gewijzigd door L0g0ff op 29-10-2014 17:28 ]

[RobIII]

Als je een willekeurig CRC algoritme neemt heb je (AFAIK, bij de bij mij bekende algo's) geen garantie dat je geen collisions krijgt (maar dat heb je natuurlijk snel genoeg gechecked). Neem je een hash-algoritme dan heb je al snel niet (meer) genoeg aan 32 bits en zit je al gauw aan 128 bits of meer (maar is de kans op collisions automatisch kleiner (maar nog steeds niet gegarandeerd maar wel relatief snel te checken).

Een CRC is misschien niet terug te rekenen naar 't oorspronkelijke getal maar natuurlijk easy te brute-forcen. Wil je een (klein!) drempeltje opwerpen dan goochel je gewoon met wat bits (XOR met een "key" of hussel wat bits op een andere manier) en voila: Nul collisions en toch "moeilijk(er)" te achterhalen wat het getal was.

[L0g0ff]

Ok, bedankt voor je antwoord. Ik denk dat ik alle waardes maar gewoon in een file wegschrijf en die dan check op dubbele waardes. Dan weet ik het zeker.

[Feanathiel]

Wellicht kun je niet hashen, maar een counter bijhouden. Hier een voorbeeld (kopje: A Non-Repeating Pseudo-Random Number Generator). Je zult dan wel zelf een mapping moeten bijhouden wat bij wat hoort, wat bij hashen niet nodig is.

[ Voor 10% gewijzigd door Feanathiel op 29-10-2014 20:32 ]

[L0g0ff]

Tnx voor de tip!

Ik zit alleen met 2 verschillende losstaande systemen. Deze systemen kunnen en mogen overlappen maar hebben geen centrale database. Wel moeten beide systemen elkaar kunnen voeden en hebben ze altijd 1 unieke waarde van 9 cijfers.

Ik mag alleen om bepaalde redenen die waardes niet gebruiken om zaken uit te wisselen. Ik moet dus ik moet iets doen om die waarde om te gooien naar een andere waarde. Ik dacht met de CRC32 het ei van Columbus gevonden te hebben totdat ik ineens bedacht dat er overlapping plaats kon vinden (1 op de 4 miljard)

Wanneer er nu van de 999.999.999 bijvoorbeeld 30 collisions zijn dan is dat nog niet zo'n probleem. Het wordt wel een probleem als er bijvoorbeeld 200 collisions voorkomen.

Ik heb alleen te weinig wiskundig inzicht om te kunnen tellen hoeveel overlapping er is. Ik had gehoopt dat iemand dit zo wel even uit zijn mouw schudde Omdat dit niet zo is zit er niks anders op dan het maar volledig uit te werken en eventueel met andere hashes te spelen als er blijkt wel teveel overlapping te zitten.

[Soultaker]

Als je simpelweg opzoek bent naar een bijectie kun je die getallen gewoon vermenigvuldigen met 31337 of een willekeurig ander getal dat copriem is met 2³². Dan heb je gegarandeerd geen collisions.

CRC's zijn sowieso ook inverteerbaar, dus daar zie ik hier het voordeel niet van.

Als het de bedoeling is dat de codering niet omkeerbaar is kun je een HMAC gebruiken, maar dan moet je wel een voldoende grote blocksize hebben (van bijvoorbeeld 160 of 256 bits). Het voordeel daarvan is tegelijk dat collisions hoog onwaarschijnlijk worden. Een gewone hash-functie i.pv. HMAC voldoet niet omdat je invoer te klein is: het is makkelijk om voor alle 10⁹ mogelijke inputs de output te berekenen.

[RobIII]

Even ter indicatie (vlug getest): Alle getallen tussen 0 en 999.999.999 gaf [blablabla] in ieder geval een boel collisions

(Mijn implementatie was fout )
In ieder geval moet je de birthday paradox er even bij houden

[ Voor 102% gewijzigd door RobIII op 29-10-2014 23:02 ]

[L0g0ff]

Bedankt voor het testen. Maar 37% wauw...!! Dat gaat hem idd dus echt niet worden. Ik kwam ook deze tegen:



Ik denk dat ik afstap van encryptie en dan ik er maar gewoon een formule op los laat. Die is dan wel terug te rekenen maar so be it Er kunnen dan in ieder geval geen collisions uit voort komen.

[RobIII]

OhMyGod schreef op woensdag 29 oktober 2014 @ 22:48:
Ik denk dat ik afstap van encryptie

Waar komt encryptie nou opeens vandaan Een CRC/Hash != encryptie!

OhMyGod schreef op woensdag 29 oktober 2014 @ 22:48:
en dan ik er maar gewoon een formule op los laat. Die is dan wel terug te rekenen maar so be it Er kunnen dan in ieder geval geen collisions uit voort komen.

Dat zou ik doen ja.

[L0g0ff]

RobIII schreef op woensdag 29 oktober 2014 @ 22:59:
Waar komt encryptie nou opeens vandaan Een CRC/Hash != encryptie!

Je hebt gelijk, verkeerde woord keuze...

Het is XOR geworden icm HEX. Mooi strak, zonder code niet terug te rekenen en geen kans op overlapping.

Bedankt mannen

[DanielG]

OhMyGod schreef op woensdag 29 oktober 2014 @ 23:48:
[...]
zonder code niet terug te rekenen en geen kans op overlapping.
[...]

Tenzij iemand het getal 000000000 invult, dan ziet hij meteen de XOR key.

code:

000000000 XOR key = key

of als iemand 2 codes ziet, dan ziet dat hex(nummer1) XOR output1 == hex(nummer2) XOR output2 == key

[ Voor 61% gewijzigd door DanielG op 30-10-2014 09:50 . Reden: quote toegevoegd ]

[Gomez12]

Nog 1 kleine toevoeging : Als je geen collissions mag hebben en het mag niet terug te rekenen zijn dan is een hash geen oplossing.

Zonder collisions is het uberhaupt terug te rekenen (desnoods met een rainbow table) omdat gewoon 1 output = 1 input. Dus dan gebruik je een hash als encryptie ipv als hash.

En voor encyptie zijn er weer betere algoritmen.

[Thralas]

Volgens mij is dit een typisch gevalletje van een XY problem

[L0g0ff]

DanielG schreef op donderdag 30 oktober 2014 @ 09:27:
[...]


Tenzij iemand het getal 000000000 invult, dan ziet hij meteen de XOR key.

code:

000000000 XOR key = key

of als iemand 2 codes ziet, dan ziet dat hex(nummer1) XOR output1 == hex(nummer2) XOR output2 == key

Tnx voor de tip! Ik ben bezig met een autocalculate tool en daar zal ik de 0 even blokkeren

[Barryvdh]

Je kan ook een bestaand iets gebruiken, zoals http://hashids.org/ (Al geven ze daar aan dat het niet voor security is, dus ligt er beetje aan hoe belangrijk het is dat het nooit terug te rekenen is)

[begintmeta]

Mogen/moeten twee van die 9-plaatsige-ASCII-codes eigenlijk wel dezelfde code krijgen?

[ Voor 5% gewijzigd door begintmeta op 31-10-2014 15:33 ]

[DanielG]

OhMyGod schreef op vrijdag 31 oktober 2014 @ 14:59:
[...]


Tnx voor de tip! Ik ben bezig met een autocalculate tool en daar zal ik de 0 even blokkeren

0 is gewoon een leuk voorbeeld. Maar als ze met die tool 2 nummers kunnen genereren kunnen ze al de XOR key achterhalen voor alles (en dus zelf alles genereren).

[johnkeates]

XOR is de oplossing niet. Wat je wil hebben is een hashmapping algoritme dat op allebei je systemen gelijk loopt of altijd unieke waardes genereert, maar dan heb je weer hashing nodig

Misschien is het sneller om AES te gebruiken? Of Blowfish? Of een ander symmetrisch algoritme? Als je er een hebt die lekker snel is kan je gewoon dezelfde key op beide servers gebruiken. Iemand kan zonder key dan niet terugrekenen.

En stel dat je iets wil dat gewoon helemaal niet terug te rekenen is gebruik je asymmetrische encryptie, en gooi je de private key weg maar dat is *lichtelijk* overkill.

Probleem is dat je twee systemen dat niet dezelfde data kunnen aanspreken wel dezelfde data wil laten hebben en dat zonder elkaar te controleren. Is daar niet iets aan te doen?