Hashing med SHA256 og kollisjonsmuligheter

[MortenM]

Noen hash eksperter her?

 

Jeg ønsker å generere en hash verdi (SHA256) av en numerisk streng. Strengen er minimum 11 og maksimum 19 siffer. Hash verdien skal brukes som en unik id, så jeg er avhengig av at det ikke er noen kollisjonsmuligheter.

 

Jeg har forstått det slik at man i utgangspunktet ikke kan forhindre kollisjoner, men gjelder det også når man kun har en numerisk streng på 19 siffer?

 

/Morten

[Giddion]

Vel man trenger ikke være ekspert for å skjønne at det er umulig å hindre kolisjon.

 

Eks

Litt usikker på hvor stor hash verdien din skal være, men jeg tenker 32bit

 

En 19 tegns string = 8 bit (ASCII char) * 19 tegn = 152 bit

 

152 bit har flere mulige kombinasjoner enn 32bit vanskelig å tenke seg til.

 

Du kan med andre ord ikke være 100% sikker på at kolisjoner ikke kan skje med mindre du bruker like mange bit som strengen.

 

Hvis du trenger en unik ID kan du jo lage en lookup tabel.

[j000rn]

Du kan med andre ord ikke være 100% sikker på at kolisjoner ikke kan skje med mindre du bruker like mange bit som strengen.

7634144[/snapback]

 

Hvis man bruker like mange bit som streng'en og det ikke er kolisjoner, så vil jo dette bety at hvert ord kun har 1 mulig hash. Og dette hørtes veldig snodig ut for min del Da er det jo ikke noe poeng å hashe :-P

 

Fortell heller hva/hvorfor du vil bruke en hash som en ID. Det hørtes ikke så veldig fornuftig ut syntes jeg...

[vidarlo]

Du kan med andre ord ikke være 100% sikker på at kolisjoner ikke kan skje med mindre du bruker like mange bit som strengen.

7634144[/snapback]

 

Hvis man bruker like mange bit som streng'en og det ikke er kolisjoner, så vil jo dette bety at hvert ord kun har 1 mulig hash. Og dette hørtes veldig snodig ut for min del Da er det jo ikke noe poeng å hashe :-P

 

Fortell heller hva/hvorfor du vil bruke en hash som en ID. Det hørtes ikke så veldig fornuftig ut syntes jeg...

7635714[/snapback]

En string har bare en hash. Ellers hadde jo hashen vore verdiløs, om du ikkje viste kva for ein som var rett...

 

Poenget med hashing kan vere at det er ein enkel måte å oppbevare passord slik at du kan sjekke om nokon har oppgitt rett passord, men ikkje lese passordet frå hashen. Det er ikkje utan grunn det er kalla ein envegsfunksjon

[j000rn]

Du kan med andre ord ikke være 100% sikker på at kolisjoner ikke kan skje med mindre du bruker like mange bit som strengen.

7634144[/snapback]

 

Hvis man bruker like mange bit som streng'en og det ikke er kolisjoner, så vil jo dette bety at hvert ord kun har 1 mulig hash. Og dette hørtes veldig snodig ut for min del Da er det jo ikke noe poeng å hashe :-P

 

Fortell heller hva/hvorfor du vil bruke en hash som en ID. Det hørtes ikke så veldig fornuftig ut syntes jeg...

7635714[/snapback]

En string har bare en hash. Ellers hadde jo hashen vore verdiløs, om du ikkje viste kva for ein som var rett...

 

Poenget med hashing kan vere at det er ein enkel måte å oppbevare passord slik at du kan sjekke om nokon har oppgitt rett passord, men ikkje lese passordet frå hashen. Det er ikkje utan grunn det er kalla ein envegsfunksjon

7637246[/snapback]

 

Ja, det jeg bomma litt på setningen min... Hvis alle hadde fått forskjellig og UNIK hash, så vil det jo i praksis si at det IKKE er en enveisfunksjon, og derfor ganske unyttig... Det er jo også derfor man som regel bruker forskjellig salt-verdier for hver verdi som hash'es. Ikke for at den skal bli lengre, men fordi det skal ta mye mindre tid å kalkulere alle hash'ene for å kunne matche hash og "passord"...

[vidarlo]

Ja, det jeg bomma litt på setningen min... Hvis alle hadde fått forskjellig og UNIK hash, så vil det jo i praksis si at det IKKE er en enveisfunksjon, og derfor ganske unyttig... Det er jo også derfor man som regel bruker forskjellig salt-verdier for hver verdi som hash'es. Ikke for at den skal bli lengre, men fordi det skal ta mye mindre tid å kalkulere alle hash'ene for å kunne matche hash og "passord"...

7637530[/snapback]

Hææ?

Ein bruker salting for å gjere generelle ordlister ubrukelige.

 

Ved å ta summen av passord+salt så sikrer en seg mot at en som har generert ei liste over alle tenkelige kombinasjoner av md5-summer bare kan slå opp på den summen. Saltinga er en måte å gjere det vanskelegare å bruteforce.

 

Poenget med et salt er altså å legge til en verdi, som forsåvidt kan vere kjent for angriper sidan den i praksis ligg samme plass som md5-summen, men som gjer at forhåndsproduserte databaser over input og resulterande hash ikkje kan brukast, samt at to brukarar med samme passord ikkje får samme hash...

[j000rn]

Hææ?

Ein bruker salting for å gjere generelle ordlister ubrukelige.

 

Ved å ta summen av passord+salt så sikrer en seg mot at en som har generert ei liste over alle tenkelige kombinasjoner av md5-summer bare kan slå opp på den summen. Saltinga er en måte å gjere det vanskelegare å bruteforce.

 

Poenget med et salt er altså å legge til en verdi, som forsåvidt kan vere kjent for angriper sidan den i praksis ligg samme plass som md5-summen, men som gjer at forhåndsproduserte databaser over input og resulterande hash ikkje kan brukast, samt at to brukarar med samme passord ikkje får samme hash...

7638453[/snapback]

 

Jeg må begynne å lese en ekstra gang over hva jeg skriver før jeg post'er... "Mindre" skulle jo selvfølgelig være "lengre"...

[MortenM]

Vel man trenger ikke være ekspert for å skjønne at det er umulig å hindre kolisjon.

 

Eks

Litt usikker på hvor stor hash verdien din skal være, men jeg tenker 32bit

 

En 19 tegns string = 8 bit (ASCII char) * 19 tegn = 152 bit

 

152 bit har flere mulige kombinasjoner enn 32bit vanskelig å tenke seg til.

 

Du kan med andre ord ikke være 100% sikker på at kolisjoner ikke kan skje med mindre du bruker like mange bit som strengen.

 

7634144[/snapback]

 

Jeg skal bruke SHA256 som hash algoritme, den gir 256 bit ut. Altså input er mindre enn output. Kan jeg få kollisjoner?

 

Grunnen til at jeg må gjøre en hash er at input er et kortnummer. VISA tillater ikke at man lagrer kortnummer i klartekst, så jeg må hashe og salte før jeg lagrer det i databasen.

[vidarlo]

 

Jeg skal bruke SHA256 som hash algoritme, den gir 256 bit ut. Altså input er mindre enn output. Kan jeg få kollisjoner? 

 

Grunnen til at jeg må gjøre en hash er at input er et kortnummer. VISA tillater ikke at man lagrer kortnummer i klartekst, så jeg må hashe og salte før jeg lagrer det i databasen.

7639684[/snapback]

Kollisjoner er ikkje det samme som at to stringer gir samme hash. En kollisjon er at det går an å rekne seg fram til kva strenger som gir samme hash på *kortare* tid enn bruteforcing, i.e prøve seg fram.

 

SHA256 har ikkje kjente kollisjonar p.t.

 

Og eg trur ikkje du vil finne to strenger som er kortare enn hashen som gir samme hash, sjølv om eg ikkje kan sei det heilt 100% sikkert.

[Frank2004]

 

Jeg skal bruke SHA256 som hash algoritme, den gir 256 bit ut. Altså input er mindre enn output. Kan jeg få kollisjoner? 

 

Grunnen til at jeg må gjøre en hash er at input er et kortnummer. VISA tillater ikke at man lagrer kortnummer i klartekst, så jeg må hashe og salte før jeg lagrer det i databasen.

7639684[/snapback]

Kollisjoner er ikkje det samme som at to stringer gir samme hash. En kollisjon er at det går an å rekne seg fram til kva strenger som gir samme hash på *kortare* tid enn bruteforcing, i.e prøve seg fram.

Nope..

[Frank2004]

Jeg skal bruke SHA256 som hash algoritme, den gir 256 bit ut. Altså input er mindre enn output. Kan jeg få kollisjoner?

Regner med at sjansen for kollisjoner med de fleste message digests følger "the birthday paradox", men jeg skal ikke si noe sikkert. Prøv en post på sci.crypt (usenet).

 

Grunnen til at jeg må gjøre en hash er at input er et kortnummer. VISA tillater ikke at man lagrer kortnummer i klartekst, så jeg må hashe og salte før jeg lagrer det i databasen.

Start med begynnelsen du, hva prøver du å oppnå?

 

Hvorfor vil du lagre kortnummeret på noen form som helst form, og hvilket problem gir evt. kollisjoner?

 

 

Sett at du er på riktig spor så skulle det la seg gjøre å få til en en-veis kryptering fri for kollisjoner selv om du ikke finner noen egnet hash. F.eks. kan du bruke asymmetrisk kryptering, men kaste bort den ene nøkkelen.

[MortenM]

For de interesserte, så fant jeg svaret mitt her: Eliminating Card Numbers to Minimize PCI Exposure.pdf