Pravděpodobnost stejného hashe u sha1*

kdyz dve veci nemaji stejnou hodnotu pak jejich hash se nemuze rovnat. Kdyz maji, pak je jejich hash stejny.

fuckin
„kdyz dve veci nemaji stejnou hodnotu pak jejich hash se nemuze rovnat.“
S veľmi malou pravdepodobnosťou môže.

nightrider
rodné číslo by nemělo být stejné ;)

nightrider
Tá pravdepodobnosť je tak malá, že sa prakticky môžeš riadiť tým, čo napísal fuckin.

jso
„rodné číslo by nemělo být stejné ;)“
Nemalo, no niekedy sa aj to stane, myslím, že sa to môže týkať len starších občanov.

nightrider
„Aha :-) takže pokud budou udaje odlišny, tak se nemůže u hash1 stát schoda :-)“
Ak je veľmi málo pravdepodobné, že ťa teraz zasiahne meteorit, tak to ešte neznamená, že sa to nemôže stať.

„Co je velmi malá pravděpodobnost?“
SHA1 poskytuje jako výstup 160bitový hash. Teoretická minimální pravděpodobnost kolize je 1 : 2^160.
V praxi bude pravděpodobnost větší, protože algoritmus samozřejmě není dokonalý.

Výsledkem pro tebe budiž to, že pro tvé účely je pravděpodobnost dostatečně malá a nemusíš ztrácet čas řešením blbostí.

Když už je odemčeno…

Reaguji mimo téma na nightridera:
Co kdyby sis příště namáhal mozek a vymyslel pro svoji otázku konečně normální nadpis? Připadá ti, že „sha1“ vystihuje podstatu tvého dotazu? Ne, je to jen jméno hashe. K ničemu.
Připadá ti dostatečně výstižné „Podmínka if“? O čem by asi takový dotaz mohl být — poznáš to z názvu na první pohled? Ne.
A co třeba „Copyright“? Odpověz mi na otázku „Copyright“. Nebo na „Datum“. Nebo na „Kapacita“.

Příští dotaz nazvaný špatně skončí … špatně.


Reaguji na DoubleThinka:
„V praxi bude pravděpodobnost větší“
Pokud ten hash skutečně počítá z řetězce složeného z rodného čísla a mailu, tak bych řekl, že bude spíš menší, pokud vůbec bude kolize ve stejném formátu existovat.

„bych řekl, že bude spíš menší, pokud vůbec bude kolize ve stejném formátu existovat.“
Nevím. Je to možné, že pokud je vstup menší než výstup, nedojde ke kolizi nikdy.

nightrider
naopak, bráno z teoretického hlediska, můžou existovat dvě spojení RČ+email, který mají stejný hash a přitom platí RČ1!=RČ2 & email1!=email2.

jso:
To právě probíráme. Pravděpodobnost, že ty konkrétně vyhraješ jackpot sportky je zhruba o 40 řádů větší.
Pokud by IBM Roadrunner nedělal nic jiného, než zkoušel rodné čísla emaily na kolize hashů, trvalo by mu asi 10^30 let, než by k ní pravděpodobně došlo. Stáří vesmíru je 10^9 let, to se nightrider načeká.

DoubleThink:
„Pravděpodobnost, že ty konkrétně vyhraješ jackpot sportky je zhruba o 40 řádů větší.“
Přesto bych se držel toho, že to není "nemožné", ale jen "vysoce nepravděpodobné".
Názor, že různé vstupy nikdy nemohou dostat stejný hash pak vede k názoru, že je možné z hashe ten vstup zrekonstruovat a následně dotazům na tohle téma :-)

Joker
souhlasím s tebou. Lze je i zpětně zrekonstruovat, ovšem jak podotkl DoubleThink, je to při současné výpočetní technice velice nepravděpodobné.
Ovšem, stalo se vám, vám nesázejícím, že jste šli, koupili los (podali sportku či co) a vyhráli něco napoprvé?

jso: „Lze je i zpětně zrekonstruovat“
???

jso:
„souhlasím s tebou. Lze je i zpětně zrekonstruovat“
Ehm, ale to je jaksi protiklad toho, co píšu já :-D
Jen se znalostí hashe nelze a nikdy nepůjde jednoznačně rekonstruovat vstup, který hash vytvořil- hash tuhle informaci prostě neobsahuje.

Aneb: Soubor má 15 825 bajtů. Jaký je jeho obsah?
Rekonstrukce vstupu podle hashe je jenom jiná varianta takovéhle otázky.

„Ovšem, stalo se vám, vám nesázejícím, že jste šli, koupili los (podali sportku či co) a vyhráli něco napoprvé?“
Jo. Moje snad první setkání s hazardem bylo, když mi kdysi dávno rodiče koupili stírací los za 10 korun. Vyhrál 10 korun, za které jsem si nechal koupit další los, který už nic nevyhrál :-)

jso
„Lze je i zpětně zrekonstruovat“
Nešlo o nájdenie pôvodného vstupu ale o nájdenie takého vstupu, ktorý dá rovnaký výstup ako pôvodný vstup.
Aj keď, ak by podľa DoubleThinka platilo: „Je to možné, že pokud je vstup menší než výstup, nedojde ke kolizi nikdy.“, tak by vtedy vlastne išlo o nájdenie pôvodného vstupu.

Ještě poznámka k původnímu předmětu: Pokud mám rodné číslo a mail, možná už není potřeba ten hash (leda by bylo třeba, aby v identifikátoru ty údaje nebyly vidět)- že by někdo vlastnil nějaký mail, pak by ho zrušil a potom si stejnou adresu zaregistroval jiný člověk se stejným rodným číslem, je asi tak stejně pravděpodobné jako ta kolize hashe :-)

Ešte k tej "rekonštrukcii":
Rodné čislo z hashu len samotného rodného čísla by nebolo až tak ťažké zistiť. Teoretický maximálny počet rodných čísel nie je až tak veľký. RČ je zostavené z dátumu narodenia, musí byť deliteľné 11 a pod. Pre veľkú databázu s hashami RČ by sa to mohlo vyplatiť. Ak je navyše známy dátum narodenia, tak stačí na zistenie overiť len 909 RČ na osobu.

_es:
„Rodné čislo z hashu len samotného rodného čísla by nebolo až tak ťažké zistiť.“
Je to tak.
Kombinování RČ a e-mailu by tenhle způsob zesložitilo (i když ne nezbytně, jednak mail jde lámat hrubou silou, hlavně pokud jsou to třeba zaměstnanci jedné firmy a všichni mají jméno.příjmení@firma.cz... a pokud bych dokázal ke každému člověk přiřadit e-mail, což taky není tak nereálné zjistit, je složitost stejná jako u samotného RČ)

V tomhle ohledu nejbezpečnější by bylo udělat solený hash, tj. hash(RČ + náhodný řetězec)

nightrider:
předpokládám, že to bude použito k například ověření emailu? Lidé se registrují, ty jim pošleš odkaz na soubor over.php?hash=...
a podle toho v DB nastavíš aktivní = 1.?
Pokud tomu tak je, tak pak by bylo asi nejsnazší udělat over.php?hash=...-id
hash má vždy stejnou délku, takže substringem si vyřízneš id, a tím už by nemělo ke kolizi dojít nikdy že :)