[DB] Hash gebruiken ter identificatie *

[Profidiam]

Wij hebben op school het probleem dat wij een uniek nummer willen voor identificatie van alle leerlingen, maar deze identificatie moet te genereren zijn, want het zit verwerkt in 4 applicaties. Nu had ik gedacht om gebruik te maken van het rijksregister nummer. Probleem is dat in België dit niet mag gebruikt worden voor dit soort doeleinden. Wat ik dus in gedachten had is om het rijksregister nummer te hashen en zodoende de verkregen tekenreeks te gebruiken als identificatie.

In deze optiek ben ik eens gaan snuffelen in de RFC die ene MD5 hash beschrijft. Deze schrijft voor dat de kan om 2 identieke hashes te vinden met verschillende brondata 1 kan op 2^64 is en de kans dat je van een hash het origineel kan achterhalen 1 kans op 2^128 is.
Nu heb ik volgende vragen :
- Kan ik de kan om 2 gelijke hashes te krijgen verwaarlozen ?
- Bestaat er een (andere) methode om dit nummer onomkeerbaar te transformeren en toch 0 kans te hebben dat de nieuwe code buddel voorkomt (vooropgesteld dat de brondata ook uniek is.) ?

meer info : http://www.freesoft.org/CIE/RFC/1321/index.htm

[Opi]

- Gezien de kansen die je hier toont lijkt het mij veroorloofbaar om de kans op twee gelijke hashes te verwaarlozen.
- Volgens mij niet; dit zou dan betekenen dat de output-range groter is dan de input-range.

[P_de_B]

Je zou hier ook een guid voor kunnen gebruiken. Een guid ziet er als volgt uit: C190F404-D231-4663-B270-C265BB07BBE9


Ik weet niet welke db je gebruikt, maar bijv. SQL Server kan deze automatisch genereren.

[Zoijar]

Ik denk dat je die kans wel kan verwaarlozen. Hoewel de kans wel groter is dan je zou denken aan de hand van die 2^64, het is namelijk het "verjaardags probleem". Kans dat twee mensen op dezelfde dag jarig zijn is maar 1/365, en toch heb je met 23 mensen al meer dan 50% kans op een zelfde verjaardag.
Maar dan nog denk ik dat die kans erg klein blijft...2^64 is enorm, en daar moet je ongeveer de wortel uit nemen dacht ik als benadering, dus 2^32 dan wat nog steeds enorm is.

Je kan SHA gebruiken, dat is dacht ik 160 bit, heb je iets minder kans (1 op 2^80).. oh md5 is al 128, dus in die 2^64 zat al het verjaardags probleem...

[Bosmonster]

Kun je niet beter een nummer nemen dat iets meer semantische waarde heeft?

Op school hadden wij bijvoorbeeld nummers als:

960011234

De eerste 2 cijfers waren het jaar van aanmelding en de rest was gewoon een opeenvolgend nummer.

[MissingDog]

79022384 yymmddxxx (geboortedatum met volgnummer, zoals ook tientallen jaren al door 't ministerie van defensie gebruikt wordt hier in NL)

[Soultaker]

De kans dat je twee gelijke hashes krijgt is onvoorstelbaar klein. De kans dat je morgen overreden wordt door een bus is veel groter en dat risico neem je ook. Verder zou het kunnen zijn dat als de invoer klein genoeg is (in ieder geval minder dan de 128 bits die MD5 als uitvoer levert) gegarandeerd unique hash codes worden gevonden. Ik moet bekennen dat ik niet zeker weet of en bij welk aantal bits dit waar is.

P_de_B: het criterium was geloof ik dat het identificatienummer te genereren moest zijn uit al beschikbare gegevens (zoals blijkbaar dat rijksnummer). Een willekeurige id genereren gaat dan niet op. Als dat wel zou kunnen zou ik voorstellen om ze gewoon oplopend te nummeren ofzo. Een leerlingnummer van 5 cijfers is wel wat praktischer dan een leerlingnummer van 32 karakters.

[P_de_B]

Soultaker schreef op 14 mei 2004 @ 14:10:
P_de_B: het criterium was geloof ik dat het identificatienummer te genereren moest zijn uit al beschikbare gegevens (zoals blijkbaar dat rijksnummer). Een willekeurige id genereren gaat dan niet op. Als dat wel zou kunnen zou ik voorstellen om ze gewoon oplopend te nummeren ofzo. Een leerlingnummer van 5 cijfers is wel wat praktischer dan een leerlingnummer van 32 karakters.

Hmm, dat kan. Zo had ik het niet begrepen.

Als dat wel zou kunnen zou ik voorstellen om ze gewoon oplopend te nummeren ofzo

Daar ben ik het mee eens, ik dacht dat dat juist niet kon. Waarom ik dat dacht ben ik alleen even kwijt

[Profidiam]

Hmmm veel interessante replies ...

Misschien moeten we toch maar eens onderzoeken of we niet de id van ons administratief pakket kunnen gebruiken ?

Ok, bij nader inzien zal dit niet lukken, wij hebben pakket a , een andere school pakket b. De id's kunnen gelijk zijn over die paketten heen, dus we zitten niet met iets unieks. Van het rijksregister nummer ben ik 100% zeker dat er geen 2 belgen zin met hetzelfde nummer. Iedereen heeft dit nummer al, dus het zou ideaal zijn om dit te gebruiken. Dit mag spijtig genoeg niet van de overheid Daarom die hash. Ook moeten we de mogelijkheid hebben op in onze hoofdpakketten die code aan te maken (hash) en al die leerlingen dan achteraf in te voeren in onze database (mail, etc ...). Dus ze moeten eigenlijk al een unieke ID hebben nog voor ze ons systeem binnen komen. Daarom is het niet mogelijk om een oplopend nummer te gebruiken.

Ik kan het beter als volgt uitleggen :

School 1 -> leerlingenlijst 1
School 2 -> leerlingenlijst 2
School 3 -> leerlingenlijst 3
School 4 -> leerlingenlijst 4


- mailserver : School 1 en 3
- ICt platform : School 1 enn 4

Later wil school 2 ook mails en school 3 ook ICT paltform. als we de codes in elk subdeel genereren zijn we elke vorm van mogelijke koppeling kwijt. als we de codes al maken op de School (x) zelf en we weten dat deze uniek zijn, is er geen probleem meer.

[ Voor 46% gewijzigd door Profidiam op 14-05-2004 14:21 ]

[P_de_B]

Kun je niet een simpeler bewerking toepassen op het rijksregister nummer?

Ik noem maar wat geks: een letter ervoor en het nummer * 2 of zo? Je moet even kijken wat kan, maar daat is denk ik eenvoudiger dan hashen.

[lordsnow]

Kan ik de kans om 2 gelijke hashes te krijgen verwaarlozen?

Volgens de RFC zijn er 2^128 mogelijke combinaties. De kans dat twee studenten dezelfde hash krijgen is dan: 1 op 2^128 / aantal studenten. Als het resultaat acceptabel groot is kan je het gewoon gebruiken. Volgens mij is het geen probleem.

de kans dat je van een hash het origineel kan achterhalen

Het origineel achterhalen zou moeten gebeuren volgens de "Brute Force" methode. Oftewel, de kraker moet alle Rijksregister nummers die er bestaan, doorlopen en hashen, en dan kijken of dit de hash produceerd waar hij naar op zoek is.

Oftewel, dit ligt aan hoeveel (mogelijke) Rijksregister nummers er (kunnen) bestaan. Hoe ziet zo'n Rijksregisternummer er uit?

Bestaat er een (andere) methode om dit nummer onomkeerbaar te transformeren

Alle hashes zijn, wiskundig gezien, onomkeerbaar. Er bestaat dus geen mogelijkheid om je originele input "terug te rekenen".

en toch 0 kans te hebben dat de nieuwe code buddel voorkomt.

Er is geen 0 kans. Alleen een hele kleine kans.

Des te meer bits je gebruikt voor de hash, des te kleiner de kans.
Maar als je het toch niet vertrouwd kan je bv HAVAL (256 bits), SHA-1 (160 bits?), SHA-2 (256/384/512 bits), of Tiger (192 bits) gebruiken.

En wat is een "buddel" ?

Oh.. dubbel. Sorry... dacht dat het iets Belgisch was. Hahaha.. dom van mij.

[ Voor 8% gewijzigd door lordsnow op 14-05-2004 14:34 ]

[bigbeng]

P_de_B schreef op 14 mei 2004 @ 14:29:
Kun je niet een simpeler bewerking toepassen op het rijksregister nummer?

Ik noem maar wat geks: een letter ervoor en het nummer * 2 of zo? Je moet even kijken wat kan, maar daat is denk ik eenvoudiger dan hashen.

Het zal ongetwijfeld iets met privacy te maken hebben en daarom gaat het er ook om dat je vanuit een bepaalde code niet terug mag kunnen redeneren naar dat oorspronkelijke nummer.

[Soultaker]

P_de_B schreef op 14 mei 2004 @ 14:29:
Kun je niet een simpeler bewerking toepassen op het rijksregister nummer?

Ik noem maar wat geks: een letter ervoor en het nummer * 2 of zo? Je moet even kijken wat kan, maar daat is denk ik eenvoudiger dan hashen.

Het probleem is dat dat eenvoudig omkeerbaar is. Je 'simpele bewerking' moet onomkeerbaar zijn en toch unieke uitvoer genereren. Dat is niet zo eenvoudig.

lordsnow schreef op 14 mei 2004 @ 14:30:
Oftewel, dit ligt aan hoeveel (mogelijke) Rijksregister nummers er (kunnen) bestaan. Hoe ziet zo'n Rijksregisternummer er uit?

Dat heb ik ook net al zitten Google'n; het zijn 11 cijfers, waarvan de eerste 6 de geboortedatum zijn (en de volgende 5 dus waarschijnlijk gewoon een volgnummer).

Alle hashes zijn, wiskundig gezien, onomkeerbaar. Er bestaat dus geen mogelijkheid om je originele input "terug te rekenen".

Dat geldt alleen als je oneindig veel invoer hebt. Het kan best zijn dat alle mogelijke nummers een unieke uitvoer opleveren en dan is de operatie dus gewoon omkeerbaar. Het maximum aantal rijksregisternummers is hooguit 10¹¹, wat 100 miljard is, maar het zijn er minder omdat de eerste 6 cijfers een geldige datum moeten vormen. In de praktijk zijn er natuurlijk maar enkele tientallen of honderden miljoenen daadwerkelijk in gebruik (geweest).

[lordsnow]

Soultaker schreef op 14 mei 2004 @ 14:35:
Dat geldt alleen als je oneindig veel invoer hebt. Het kan best zijn dat alle mogelijke nummers een unieke uitvoer opleveren en dan is de operatie dus gewoon omkeerbaar.

Volgens mij zijn wij het niet oneens met elkaar.

Even ter verduidelijking:
(1) Een hash is absoluut onomkeerbaar,
(2) Door middel van een "Brute Force attack" zou je achter de input kunnen komen.

En een "Brute Force attack" is niet te doen, praktisch gezien, als het aantal mogelijke inputs groot is. Of, anders gezegd, je kan achter de input komen als het aantal mogelijke inputs klein is.

[T-MOB]

Profidiam schreef op 14 mei 2004 @ 14:17:

School 1 -> leerlingenlijst 1
School 2 -> leerlingenlijst 2
School 3 -> leerlingenlijst 3
School 4 -> leerlingenlijst 4


- mailserver : School 1 en 3
- ICt platform : School 1 enn 4

Later wil school 2 ook mails en school 3 ook ICT paltform. als we de codes in elk subdeel genereren zijn we elke vorm van mogelijke koppeling kwijt. als we de codes al maken op de School (x) zelf en we weten dat deze uniek zijn, is er geen probleem meer.

Wat is er dan tegen om *School_id*-*studentnummer* te gebruiken? Dan pak je een administratief id van school a en prefixed dat met een school_id. Dito voor school b t/m X

[Skaah]

Soultaker schreef op 14 mei 2004 @ 14:10:
De kans dat je twee gelijke hashes krijgt is onvoorstelbaar klein. De kans dat je morgen overreden wordt door een bus is veel groter en dat risico neem je ook. Verder zou het kunnen zijn dat als de invoer klein genoeg is (in ieder geval minder dan de 128 bits die MD5 als uitvoer levert) gegarandeerd unique hash codes worden gevonden. Ik moet bekennen dat ik niet zeker weet of en bij welk aantal bits dit waar is.

Ik moet dit ff tegenspreken, ik heb hier een keer mee geëxperimenteerd.

Na 32.000x een MD5 hash van een random input genereren kwam ik al 300x een hash tegen die ik al eerder gemaakt had.

Des te meer bits je gebruikt voor de hash, des te kleiner de kans.
Maar als je het toch niet vertrouwd kan je bv HAVAL (256 bits), SHA-1 (160 bits?), SHA-2 (256/384/512 bits), of Tiger (192 bits) gebruiken.

Er was ergens een website tégen MD5, die droegen dit ook aan.

[ Voor 18% gewijzigd door Skaah op 15-05-2004 11:37 ]

[Anoniem: 79717]

Een computer genereert nooit uit zichzelf 32.000 keer iets compleet random, dat kunnen ze gewoon niet. Er zit altijd een soort van patroon in. Kijk bijvoorbeeld naar de shuffle functie van Winamp o.i.d., daar kom je ook heel vaak dezelfde nummers tegen, ook al heb je er ontzettend veel in je playlist staan, en sommige kom je nooit tegen.

En ik denk dat na het 32.000 keer oversteken van een busbaan je grote kans hebt om wel een keertje geraakt te zijn Maar dat de kans dat je met 32.000 echt random input 300 keer dezelfde hash tegenkomt, laat staan zelfs eentje, ontzettend veel kleiner is.

Edit: Ja ik bedoel dus 32.000 keer verschillende invoer, maar dat een computer vaak hetzelfde zal 'kiezen', verkeerd verwoord.

[ Voor 10% gewijzigd door Anoniem: 79717 op 15-05-2004 12:39 ]

[Soultaker]

Skaah schreef op 15 mei 2004 @ 11:33:
Ik moet dit ff tegenspreken, ik heb hier een keer mee geëxperimenteerd.

Na 32.000x een MD5 hash van een random input genereren kwam ik al 300x een hash tegen die ik al eerder gemaakt had.

Dat lijkt me bijna onmogelijk. Zo slecht is MD5 ook weer niet. Als we aannemen dat de MD5 uitvoer van een willekeurige invoer ook een willekeurig getal is (van 128 bits in het geval van MD5), dan valt het vinden van collisions te omschrijven als een verjaardagsprobleem.

Zonder verdere uitleg stel ik:

code:

X = 2^128                  # aantal mogelijke waarden
Y = 32000                  # aantal experimenten 
P = prod 0<=y<Y: (X-y)/X   # kans dat alle experimenten verschillen
  = (X! / (X-Y)!) / X^Y
Q = 1 - P                  # kans op 1 of meer collissions

Je kunt dit wel nazoeken op andere websites; ik heb het net zelf even gereconstrueerd aan de hand van het verjaardagsprobleem (waaruit blijkt dat er al meer dan 50% kans is op twee gelijke verjaardagen in een groep van 23 personen).

Je kunt op basis van bovenstaande formules wel aanvoelen dat Y verwaarloosbaar klein is ten opzichte van X, en dat P dus wel heel erg dicht bij 1 gaat uitkomen. De kans op een collisions zal dus nagenoeg 0 zijn. Als je verstandig bent geloof je me niet op mijn woord, maar over een echt bewijs moet ik nog even nadenken.

edit:
Ik heb het numeriek benaderd en de eerste 12 decimalen van Q zijn in ieder geval 0.

[ Voor 4% gewijzigd door Soultaker op 15-05-2004 12:36 ]

[Soultaker]

Anoniem: 79717 schreef op 15 mei 2004 @ 11:45:
Een computer genereert nooit uit zichzelf 32.000 keer iets compleet random, dat kunnen ze gewoon niet. Er zit altijd een soort van patroon in.

Het gaat er niet zozeer om of het random invoer is, maar meer of het verschillende invoer is. 32000 verschillende getallen genereren is zelfs voor de simpelere pseudo-random number generators een peuleschil. Dat de generatie aan een patroon onderhevig is zou voor MD5 niet uit mogen maken (als het een 'perfecte' hash zou zijn en de hypothese is dat MD5 daar bij in de buurt komt).

Ik heb bijvoorbeeld ook een test gedaan met de MD5 uitvoer van de getallen 1 tot en met 1 miljoen. De uitvoer is steeds verschillend, hoewel de invoerwaarden bepaald niet random zijn (en duidelijk aan een 'patroon' onderhevig zijn).

[Profidiam]

De reden waarom we geen <schoolcode><leerlingnummer> kunnen gebruiken is omdat 1 school verschillende 'instellingen' heeft. Dit wil zeggen dat wanneer een leerling van jaar verhuist (van 3 naar 4) wijzigt zijn 'instelling' en zijn we track kwijt van die leerling ( tenzij dat we hem uitschrijven en terug inschrijven).

We moeten dus iets vinden dat die mensen identificeert over de scholen heen en laat dat nu net het rijksregisernummer zijn.

Hmm volgens wat ik lees is er dus wel een reële kans dat je dubbele hashes tegen komt. Heeft iemand nog een suggestie over hoe ik dit dan kan aanpakken ? Misschien een ander soort encryptie van het rijksregisternummer ?

Dit soort probleem moet toch wel al eens ergen voor gekomen zijn, een persoon identificeren en hem ook kunnen 'tracken' over de scholen heen (Als ll X naar andere school gaat in de groep kan gewoon zijn klas + school gewijzigd worden, dan hoeft er verder niks te gebeuren).
Het is ook geen optie om een combined primary key te nemen, want de 'code' moet gedrukt worden op de leerlingebadges en zal gebruikt worden voor diverse identificatie doeleinden (terug in de volledige scholengroep).

Dit is blijkbaar toch iets om eens over na te denken ...

[Soultaker]

Profidiam schreef op 15 mei 2004 @ 15:38:
Hmm volgens wat ik lees is er dus wel een reële kans dat je dubbele hashes tegen komt. Heeft iemand nog een suggestie over hoe ik dit dan kan aanpakken ? Misschien een ander soort encryptie van het rijksregisternummer ?

Dan neem je dus zomaar aan dat Skaah gelijk heeft en negeer je wat SF3 en ik zeggen. Er zijn geen MD5 collissions bekend. De kans dat jij ze gaat vinden met je lullige paar duizend (of desnoods tien miljoen; hoeveel Belgen zijn er helemaal?) invoerwaarden is praktisch nihil.

Overigens heeft elke hash functie als nadeel dat de uitvoer redelijk makkelijk om te keren is. Ik weet niet in hoeverre dat nog een bezwaar is? Als koste wat het kost die rijksregisternummers onbekend moeten blijven, is het hashen daarvan ten behoeve van de identificatie gewoon niet geschikt.

[ Voor 20% gewijzigd door Soultaker op 15-05-2004 17:29 ]

[Profidiam]

Ok Soultaker, ik heb jouw uitleg nogmaals nagelezen en begrijp nu pas goed wat je bedoelde. Sta me toe om het even in een ander ebewoording te zeggen.
Wat jij zeg is dat als ik een tabel zou maken met 2 kolommen met daarin alle mogelijke rijksregisternummers en aan de andere kant de hashes dat ik dan gewoon uit da hash het nummer haal.

Als dit hetgeen is wat je bedoelt, en dat denk ik ook dan is het idd zo dat een hash eigenlijk geen toegevoegde waarde heeft, dan zou je eigenlijk ook het rijksregisternummer konnen ROT-13'en of zo, want de zorg van onze directie was dat dit nummer leesbaar was.

Ik heb blijkbaar niet volledig begrepen wat je bedoelde. Mijn excuses. Maar als Skaah zegt dat hij bi 32K waarden 300 dezelfde heeft, mag ik dan veronderstellen dat bij 3k waarden mogelijks 30 dezelfde hash waarden zijn ? of gaat deze redenering niet op ?

[Soultaker]

Je redenering klopt wel, maar die is gebaseerd op de veronderstelling dat wat Skaah beweert klopt. Ik denk niet dat Skaah bij 32k waarden 300 collissions had; ik denk dat hij iets fout heeft gedaan bij het genereren van invoerwaarden waardoor zijn invoerwaarden niet uniek waren (en z'n uitvoerwaarden daardoor ook niet). Nogmaals: er is geen enkele MD5 collision bekend; het lijkt me dus vrijwel onmogelijk dat Skaah er 300 heeft gevonden.

Ik heb dat hier ook al toegelicht. Ga er dus maar vanuit dat je geen collisions gaat krijgen. Als Skaah er anders over denkt kan 'ie natuurlijk heel simpel het tegenbewijs leveren: geef twee invoerwaarden die dezelfde MD5 uitvoerwaarde opleveren. Dan ben niet alleen ik overtuigd, maar dan staat het ook vandaag nog op slashdot en ZDnet.

edit:
Qua hashing heb ik trouwens nog wel een andere suggestie voor je; gebruik een 32-bits FNV hash. Het voordeel daarvan is dat de uitvoerwaarde wat korter is (32 bits, dus maximaal 10 decimalen).

Als mijn gegevens kloppen is het rijksregisternummer als volgt opgebouwd: jjmmdd-vvv-cc. jj is een jaartal (zonder eeuwaanduiding), mm een maand, dd een dag, vvv een volgnummer en cc een controlegetal. Het controlegetal volgt uit de overige gevens dus die kun je buiten beschouwing laten. Het aantal mogelijke rijksregisternummers is dan (slechts) 100*12*31*1000 oftewel 37.200.000 en dat is minder dan 2²⁶.

Als je simpelweg van de getallen van 0 tot en met 37.200.000 de 32-bits FNV hash berekent, dan zie je dat er geen collisions zijn. Je kunt dus veilig deze hashfunctie gebruiken. Eventueel wil ik de programmacode voor deze test wel plaatsen, als je interesse hebt, dan kun je zelf zien dat het klopt.

[ Voor 42% gewijzigd door Soultaker op 15-05-2004 18:25 ]

[Profidiam]

Ok, ik versta wat je wil zeggen

Dus ik moet niet bang zijn van collisions, maar moet mij wel weer de vraag stellen of het wel nut heeft van dit nummer zo om te vormen, omdat hij eigenlijk omkeerbaar is als je zulk een tabel maakt ?

[ Voor 45% gewijzigd door Profidiam op 15-05-2004 18:20 ]

[Soultaker]

Als je enige criterium het omzeilen van de wetgeving over dat nummer is, dan kun je controleren of het voor de wet afdoende is dat je 'm zo transformeert. Technisch gezien is 'ie dan nog steeds om te keren, maar in de prakijkt is het niet al te duidelijk zichtbaar. Het is natuurlijk ook geen supergeheim nummer: iedereen die toegang heeft tot jullie scholierendatabase kan 'm zo van iedereen uitlezen.

Het is sowieso niet echt een geweldig geheim nummer; als ik iemands geboortedatum weet (wat meestal publieke informatie is) dan heb ik al een kans van 1 op 1000 om het volgnummer goed te gokken (en dan volgt het controlegetal automatisch). Als er meer patroon in het volgnummer zit (bijvoorbeeld: hij begint elke dag op 0) dan kan die kans al veel groter worden.

[ Voor 33% gewijzigd door Soultaker op 15-05-2004 18:24 ]

[Profidiam]

Ik ga dit maandag met mijn collega's bespreken, uit al deze berichten heb ik zeer veel geleerd en nu heb ik wat meer materiaaal om over te spreken. Ook naar het ministerie toe kan ik nu wel die vraag stellen of dit een goede manier is om met deze code om te springen, ze deden vooral moeilijk ove rhet feit dat wij dat nummer in onze database zitten hadden op een andere plaats dan waar zij dit wouden hebben.

Het is zoals je aangeeft inderdaad geen supergeheim, we willen enkel wettelijke problemen vermijden.

[Skaah]

Soultaker schreef op 15 mei 2004 @ 18:11:
Je redenering klopt wel, maar die is gebaseerd op de veronderstelling dat wat Skaah beweert klopt. Ik denk niet dat Skaah bij 32k waarden 300 collissions had; ik denk dat hij iets fout heeft gedaan bij het genereren van invoerwaarden waardoor zijn invoerwaarden niet uniek waren (en z'n uitvoerwaarden daardoor ook niet). Nogmaals: er is geen enkele MD5 collision bekend; het lijkt me dus vrijwel onmogelijk dat Skaah er 300 heeft gevonden.

Hmm mijn input bestond uit een random integer, en de tijd in milliseconden. (D'r zat een database insert bij, dus misschien was de procedure toch niet helemaal goed...

Update:
Ik heb 2^16 unieke hashes gegenereerd en ze gaven allemaal een unieke md5 hash.

[ Voor 7% gewijzigd door Skaah op 16-05-2004 15:50 ]