Zkrácení haše pro identifikaci

[_Tomáš_]

Jirsaku, Jirsaku, diskutovat s tebou je zbytecne. Ze git neco dela spatne neznamena ze to maji delat vsichni. Co nastane az uzivatel dostane od aplikace dva ruzne zaznamy se stejnym hashem? Ze je to mala pravdepodobnost? Vyhra jackpotu v loterii $1B ma taky silene nizkou pravdepodonost a presto lidi obcac vice nez miliardu $ vyhraji.

Mluvíš moc obecně. Git ti nedovolí uložit dva stejné hashe do repositáře, pokud chceš synchronizovat (pull/push) repositář s duplicitními hashi, odmítne to udělat. V kódu na to má kontroly a aktivně s takovou možností pracuje.

Hashe nejsou nikdy unikátní a pokud je použiješ jako identifikátor, musíš s neunikátnosti nějak pracovat, třeba dát na výběr víc možnosti, když existují. To je pak úplně jedno, jestli bereš celý hash nebo jeho část, s tím hejbeš jen s tou loterií. Git se nezhroutí, když se stane duplicita, ale líbit se mu to nebude.

[Reklama]

[Filip Jirsák]

Jirsaku, Jirsaku, diskutovat s tebou je zbytecne.

To jste špatně pochopil. Když něčemu nerozumíte, je zbytečné, abyste o tom diskutoval vy – a to úplně s kýmkoli. Místo diskuse si radši problematiku nastudujte.

Ze git neco dela spatne neznamena ze to maji delat vsichni.

Já jsem schválně zmínil Git až úplně na závěr. Popsal jsem hlavně obecný princip a ptal jsem se, co je na něm špatně. Proč jste stále nenapsal, co je na tom špatně?

Co nastane az uzivatel dostane od aplikace dva ruzne zaznamy se stejnym hashem?

To se v aplikaci, kterou jsem popsal, nestane. Ne že by byla pravděpodobnost malá, ta pravděpodobnost je nulová.

Ze je to mala pravdepodobnost? Vyhra jackpotu v loterii $1B ma taky silene nizkou pravdepodonost a presto lidi obcac vice nez miliardu $ vyhraji.

Teď jste se odkopal a ukázal jste, že o tom vůbec nic nevíte. Nejdřív si spočítejte, jaká je pravděpodobnost výhry v té vaší loterii. Pak si spočítejte, jaká je pravděpodobnost, že náhodně vznikne stejný 160bitový hash pro dva různé vstupy. A pak nám přijďte povědět, proč k sobě připodobňujete dvě tak diametrálně odlišné hodnoty.

[Martin Poljak]

Jirsaku, Jirsaku, diskutovat s tebou je zbytecne.

Ehm, pan Jirsák je sice velice zvláštní... jev, ale v tomhle případě má naprosto stroze pravdu. Obávám se, vzhledem k tomu, co píšete, že v tomto případě je podle všeho dost zbytečné diskutovat spíš s vámi.

[Filip Jirsák]

Hashe nejsou nikdy unikátní a pokud je použiješ jako identifikátor, musíš s neunikátnosti nějak pracovat, třeba dát na výběr víc možnosti, když existují.

Hash je vlastně vždycky použit jako identifikátor. Když se hash podepisuje, je to identifikátor podepsaného obsahu; když se používá pro ověření integrity dat, je to identifikátor těch dat.

S tím, že hash teoreticky nemusí být unikátní, se drtivá většina použití vypořádává velmi jednoduše – pravděpodobnost je tak malá, že nemá smysl to řešit. Pokud se ta pravděpodobnost postupem času zvýší, protože došlo k prolomení hashovací funkce, řeší se to opět jednoduše – přechodem na lepší hashovací funkci. Git má bohužel konkrétní hashovací funkci zadrátovanou velmi hluboko, takže tam ta oprava potrvá déle.

Ale to vůbec nesouvisí se zkracováním hashů v UI. To je čistě věc UX. Některé CLI programy dělají to, že když napíšete začátek příkazu, který je jednoznačný, samy si to doplní na celé jméno příkazu a nenutí vás to dopisovat. git tohle dělá s identifikátory commitů – když napsaný začátek hashe odpovídá jednomu konkrétnímu commitu, git si to sám doplní. Dopisovat ten zbytek hashe by bylo zbytečné, gitu by to nepřineslo žádnou novou informaci.

Petr Branik zpochybnil princip hashování jako takový (pravděpodobně aniž by to tušil).

[RDa]

S tím, že hash teoreticky nemusí být unikátní, se drtivá většina použití vypořádává velmi jednoduše – pravděpodobnost je tak malá, že nemá smysl to řešit. Pokud se ta pravděpodobnost postupem času zvýší, protože došlo k prolomení hashovací funkce, řeší se to opět jednoduše – přechodem na lepší hashovací funkci. Git má bohužel konkrétní hashovací funkci zadrátovanou velmi hluboko, takže tam ta oprava potrvá déle.

To jsou zas jirso-kydy. Hash se nemusi prolamovat ci oslabovat, staci kdyz prestane slouzit ucelu - coz napr. v pripade zkracenych hashu na gitu znamena ze repo narostlo do uplneho nepomeru.

Ted jsem zrovna resil, jak zahashovat 128 individualnich 32bit hodnot, at mam treba 8bit hash a tudiz 50% sanci na hit/miss, s 0 kolizema... a jendoduchym xorem to fakt nejde. Pokud podminky polevim, ze bych akceptoval 9-bit hash, tj. 25% sanci na hit (75% miss), tak to je bez kolizi.

Takze vzdy zalezi na tom, kolik zprav se hashuje vs. jak dlouhy ten hash je. Kolize nastanou drive nebo pozdeji. Neni treba nic lamat. Je to primitivni statistika.

[Reklama]

[Filip Jirsák]

To jsou zas jirso-kydy. Hash se nemusi prolamovat ci oslabovat, staci kdyz prestane slouzit ucelu - coz napr. v pripade zkracenych hashu na gitu znamena ze repo narostlo do uplneho nepomeru.

Je od vás hezké, že jste nám hned v první větě oznámil, že tomu nerozumíte.

Git nepoužívá žádné zkrácené hashe, používá SHA-1, což je standardní kryptografický hash.

Už tady bylo několikrát řečeno, že zkrácená verze hashe je jenom věc UI. Když zadáte začátek hashe, git vyhledá všechny hashe, které mu odpovídají. Pokud je to jen jeden, je vše v pořádku a git ví, který commit jste chtěl. Když jich odpovídá víc, git vypíše chybu a nepokračuje. To samé při výpisu – git vypisuje začátek hashe o konfigurovatelné minimální délce tak, aby prefix unikátně označoval objekt. Tj. kdyby minimální délka nestačila a prefixu odpovídalo víc objektů, přidá git z hashe další písmena – tak, aby ten prefix byl unikátní.

Takže ani velké git repository ten mechanismus nerozbije. Podívejte se třeba na repository se zdrojovými kódy Linuxu. Normálně funguje a hashe se tam používají jako v jakémkoli jiném repository. On totiž git napsal Linus právě pro správu zdrojových kódů Linuxu, takže jaksi s velkými repository počítal…

Ted jsem zrovna resil, jak zahashovat 128 individualnich 32bit hodnot, at mam treba 8bit hash a tudiz 50% sanci na hit/miss, s 0 kolizema... a jendoduchym xorem to fakt nejde. Pokud podminky polevim, ze bych akceptoval 9-bit hash, tj. 25% sanci na hit (75% miss), tak to je bez kolizi.

My se tu ale bavíme o kryptografických hashích, ne o samodomo pokusech amatérů.

Takze vzdy zalezi na tom, kolik zprav se hashuje vs. jak dlouhy ten hash je. Kolize nastanou drive nebo pozdeji. Neni treba nic lamat. Je to primitivni statistika.

Tak si tu primitivní statistiku spočítejte. Abyste věděl, co znamená to „později“.

Hashe se používají tak (teda když někdo problematice rozumí a navrhne rozumné použití), že pravděpodobnost kolize je tak extrémně malá, že nemá smysl se jí zabývat. Protože to „později“ je nesmyslně daleko v budoucnosti. Takže problém hashe nejsou přirozeně vzniklé kolize, ty jsou extrémně nepravděpodobné (je to primitivní statistika, konkrétně narozeninový paradox). Problém je, pokud je hash prolomen a někdo dokáže kolize generovat záměrně.

[RDa]

To jsou zas jirso-kydy. Hash se nemusi prolamovat ci oslabovat, staci kdyz prestane slouzit ucelu - coz napr. v pripade zkracenych hashu na gitu znamena ze repo narostlo do uplneho nepomeru.

Je od vás hezké, že jste nám hned v první větě oznámil, že tomu nerozumíte.

Git nepoužívá žádné zkrácené hashe, používá SHA-1, což je standardní kryptografický hash.

Ja ti nevim cece, ale asi mas nejaky stary git, ten nas jede v SHA-256 s 32-byte hashem.

Kód: [Vybrat]

$ git rev-parse --show-object-format
sha256
$ git log
commit 4e164c03fe8dc6ed2a6a6f92ebd1d2a0b40e85f45390295b63aa7138179f42a0
..
..


[Filip Jirsák]

Ja ti nevim cece, ale asi mas nejaky stary git, ten nas jede v SHA-256 s 32-byte hashem.

Ne, nemám starou verzi Gitu. Výchozí pro Git je pořád SHA-1. Jaká hashovací funkce se používá je navíc (logicky) věcí konkrétního repository, ne verze Gitu.

Víc k přechodu Gitu z SHA-1 na silnější hashovací funkce máte tady: https://git-scm.com/docs/hash-function-transition/

[_Jenda]

Ted jsem zrovna resil, jak zahashovat 128 individualnich 32bit hodnot, at mam treba 8bit hash a tudiz 50% sanci na hit/miss, s 0 kolizema... a jendoduchym xorem to fakt nejde. Pokud podminky polevim, ze bych akceptoval 9-bit hash, tj. 25% sanci na hit (75% miss), tak to je bez kolizi.

To se mi nějak nezdá. Když nacpete 128 prvků náhodně do 512 přihrádek, tak je kolize v podstatě jistá. Aby jistá nebyla, musí být přihrádek kvadraticky hodně (Birthday problem).

Lineárně velkou hashovací tabulku bez kolizí skutečně lze vytvořit, říká se tomu perfektní hashování, a funguje to tak, že uděláte tabulku jako jste udělal vy tu první, a kolize rozřešíte dalšími malinkými tabulkami - které jsou kvadraticky velké, ale protože prvků v každém slotu té první tabulky je „málo“, tak to nevadí.

Další zajímavá možnost je kukačkové hashování. To je vlastně podobný koncept - používá také dvě různé hashovací funkce, aby vyřešilo ten problém s kolizemi, ale na rozdíl od perfektního hashování to tlačí do jedné (větší, ale jenom konstantně-krát) tabulky a je to šikovně matematicky vymyšlené, že to vyjde. Opět to ale není tak jednoduché jako váš příklad -- máte ty hashovací funkce dvě a při vyhledání prvku se tak díváte na dvě místa. A opět se tomu nedá říkat, že je to „bez kolizí“, protože tam kolize jsou - ale maximálně jedna pro každý prvek.

A mě fascinuje, jak si tyhle věci pamatuju, i když jsem to viděl jen ve škole, kterou jsem dokončil před 5 lety, a od té doby jsem to nepoužil. Oproti tomu třeba věci z matematické analýzy nebo lingebry vůbec nedám.

[_Jenda]

Ze je to mala pravdepodobnost? Vyhra jackpotu v loterii $1B ma taky silene nizkou pravdepodonost a presto lidi obcac vice nez miliardu $ vyhraji.

Teď jste se odkopal a ukázal jste, že o tom vůbec nic nevíte. Nejdřív si spočítejte, jaká je pravděpodobnost výhry v té vaší loterii. Pak si spočítejte, jaká je pravděpodobnost, že náhodně vznikne stejný 160bitový hash pro dva různé vstupy.

Stejně jako výše bych chtěl upozornit, že nás to nezajímá pro dva různé vstupy, ale alespoň jednou pro N různých vstupů, což je výrazně a neintuitivně jiné číslo (narozeninový paradox). Nicméně máte pravdu, že je stále nepředstavitelně menší než ta výhra v loterii a pro praktické účely je to i pro 160bit hash „nula“.

[Filip Jirsák]

Ted jsem zrovna resil, jak zahashovat 128 individualnich 32bit hodnot, at mam treba 8bit hash a tudiz 50% sanci na hit/miss, s 0 kolizema... a jendoduchym xorem to fakt nejde. Pokud podminky polevim, ze bych akceptoval 9-bit hash, tj. 25% sanci na hit (75% miss), tak to je bez kolizi.

To se mi nějak nezdá. Když nacpete 128 prvků náhodně do 512 přihrádek, tak je kolize v podstatě jistá. Aby jistá nebyla, musí být přihrádek kvadraticky hodně (Birthday problem).

Myslím, že zakopaný pes je v tom slovíčku náhodně. Podle toho, co psal RDa, si myslím, že neměl náhodná data, ale má nějakou předem danou množinu dat, která mají interně nějakou strukturu. Proto mu pak ani XOR nedával náhodné rozdělení a proto pak mohl psát, že s 8 bity to nejde a s 9 bity to jde. Kdyby neměl na začátku pevně danou množinu záznamů, nemůže psát „je tam kolize“ a „není tam kolize“, ale musel by uvádět pravděpodobnost.

Ze je to mala pravdepodobnost? Vyhra jackpotu v loterii $1B ma taky silene nizkou pravdepodonost a presto lidi obcac vice nez miliardu $ vyhraji.

Teď jste se odkopal a ukázal jste, že o tom vůbec nic nevíte. Nejdřív si spočítejte, jaká je pravděpodobnost výhry v té vaší loterii. Pak si spočítejte, jaká je pravděpodobnost, že náhodně vznikne stejný 160bitový hash pro dva různé vstupy.

Stejně jako výše bych chtěl upozornit, že nás to nezajímá pro dva různé vstupy, ale alespoň jednou pro N různých vstupů, což je výrazně a neintuitivně jiné číslo (narozeninový paradox). Nicméně máte pravdu, že je stále nepředstavitelně menší než ta výhra v loterii a pro praktické účely je to i pro 160bit hash „nula“.

Bylo to myšleno tak, že pro N vstupů budou existovat dva takové, které budou mít stejný hash. V pozdějším komentáři jsem to napsal, že jde o narozeninový paradox.

[Vietnanka]

Mělo by to být ireleventní  při ideální implementaci hashovací funkce. Libovolně zvolený rozsah pro "substringování" by měl mít stejnou vypovídající hodnotu . Lze to ad absurdum dovést až  na bitovou úroveň, že budu vybírat jednotlivé bity a ještě  je poskládám v nějakém pořadí. Ale vždy konzistentní. (Tím si nejsem jistý, ale tipl bych, že ani to tohle nehraje roli)

Samozřejmě to má ale důsledek, že v tom hashi bude méně bitů informace.

Ale mám otázku do pléna,  možná se to tu řešil na této stránce :
Pokud chci zkrátit hash (v podstatě to co tazatel), například na poloviční délku, mohu prostě ořezem dat a nebo xorováním.

Já si myslím (tvrdím). že na základě vlastnosti ideální hashovací funkce
1-sub: Při zkracování hashe nemusí  v rámci testování být předpis pro substring   pro každý vstup stejný (indexy bajtů, který zahodím) , může se lišit
1-xor: Při zkracování hashe   xorováním nemusí být předpis pro xorování stejný (které dvojice bitů xoruji a jejich pořadí)
2-equ: Oba způsoby (zkrácení a XOR)) mají "stejnou výstupní kvalitu" . Nebo jak to formulovat... jsou rovnocenné


Samozřejmě že pak pro body 1 pro stejný vstup bude výsledek xoru nebo substr jiný, ale myslím to tak, že když budu testovat unikátní vstupy, tak pole výstupů (jako celek) bude mít stejnou distribuci náhodnosti jako když  pro všechny unikátní vstupy použiju stejný parametry  (v kurzívě )

[Vietnanka]

K loterii:

Ze je to mala pravdepodobnost? Vyhra jackpotu v loterii $1B ma taky silene nizkou pravdepodonost a presto lidi obcac vice nez miliardu $ vyhraji.

Teď jste se odkopal a ukázal jste, že o tom vůbec nic nevíte. Nejdřív si spočítejte, jaká je pravděpodobnost výhry v té vaší loterii. Pak si spočítejte, jaká je pravděpodobnost, že náhodně vznikne stejný 160bitový hash pro dva různé vstupy.

Stejně jako výše bych chtěl upozornit, že nás to nezajímá pro dva různé vstupy, ale alespoň jednou pro N různých vstupů, což je výrazně a neintuitivně jiné číslo (narozeninový paradox). Nicméně máte pravdu, že je stále nepředstavitelně menší než ta výhra v loterii a pro praktické účely je to i pro 160bit hash „nula“.

Jenže losování v loterii a hledání kolizí je jiná úloha.
Loterie  náhodné losování z N losů a to se ví.
Ale vstupy pro hashe jsou neomezená množina, protože není specifikovaná délka řetězce a může to  být dlouhá jak prsa ženy afrického kmenu. Věc druhá je ,že hash nabývá 2^N hodnot

[Filip Jirsák]

Jenže losování v loterii a hledání kolizí je jiná úloha.

Za prvé, jestli je to stejná nebo jiná úloha je úplně jedno. V obou případech máme na konci pravděpodobnost, zda se najde kolize / bude vylosováno správné číslo. Takže jenom porovnáváme dvě pravděpodobnosti, tedy dvě bezrozměrná čísla v rozsahu <0; 1>.

Ale vstupy pro hashe jsou neomezená množina, protože není specifikovaná délka řetězce a může to  být dlouhá jak prsa ženy afrického kmenu. Věc druhá je ,že hash nabývá 2^N hodnot

Nemůžete počítat s neomezenou množinou vstupů, protože pokud bude počet vstupů 2^N+1 a více, pravděpodobnost, že dojde ke kolizi, je 1.

Ve skutečnosti se počítá s tím, kolik máte různých vstupů. Třeba u gitu je to počet commitů v repository. Když nemáte konkrétní repository, uděláte odhad – kolik by tak nějaké obří repository mohlo mít commitů. Vtip je v tom, že na určení počtu commitů v repository vlastně nezáleží, pokud to bude nějaká myslitelná hodnota. Protože to pořád vede na tak nízkou pravděpodobnost, že nemá smysl se tím zabývat. Když budete počítat, že na git repository (s SHA-1) bude pracovat milion programátorů, kteří každý vyprodukují milion commitů denně a budou to dělat milion dnů (tj. přes 2700 let), pořád bude na konci pravděpodobnost kolize v řádu 10^-13. Pravděpodobnost výhry hlavního tahu ve sportce je někde v řádu 10^-8. Mimochodem, linuxové jádro mělo milion commitů před necelými třemi roky. Pravděpodobnost, že by v repository s milionem commitů byla kolize, je v řádu 10^-37. Takže je pořád podstatně pravděpodobnější, že vyhrajete hlavní tah Sportky čtyřikrát, než že bude (neúmyslná!) kolize mezi hashi commitů zdrojů linuxového jádra.

Proto to celé nabourá jenom situace, kdy dojde k prolomení hashovací funkce a útočník dokáže generovat kolize záměrně v historicky krátké době (tj. v řádu dejme tomu měsíců a méně). Jako už se to stalo s SHA-1 (proto se přestala používat v kryptografii).

[xyz]

Mělo by to být ireleventní  při ideální implementaci hashovací funkce. Libovolně zvolený rozsah pro "substringování" by měl mít stejnou vypovídající hodnotu . Lze to ad absurdum dovést až  na bitovou úroveň, že budu vybírat jednotlivé bity a ještě  je poskládám v nějakém pořadí. Ale vždy konzistentní. (Tím si nejsem jistý, ale tipl bych, že ani to tohle nehraje roli)

Samozřejmě to má ale důsledek, že v tom hashi bude méně bitů informace.

Ale mám otázku do pléna,  možná se to tu řešil na této stránce :
Pokud chci zkrátit hash (v podstatě to co tazatel), například na poloviční délku, mohu prostě ořezem dat a nebo xorováním.

Já si myslím (tvrdím). že na základě vlastnosti ideální hashovací funkce
1-sub: Při zkracování hashe nemusí  v rámci testování být předpis pro substring   pro každý vstup stejný (indexy bajtů, který zahodím) , může se lišit
1-xor: Při zkracování hashe   xorováním nemusí být předpis pro xorování stejný (které dvojice bitů xoruji a jejich pořadí)
2-equ: Oba způsoby (zkrácení a XOR)) mají "stejnou výstupní kvalitu" . Nebo jak to formulovat... jsou rovnocenné


Samozřejmě že pak pro body 1 pro stejný vstup bude výsledek xoru nebo substr jiný, ale myslím to tak, že když budu testovat unikátní vstupy, tak pole výstupů (jako celek) bude mít stejnou distribuci náhodnosti jako když  pro všechny unikátní vstupy použiju stejný parametry  (v kurzívě )

Uz se to tu resilo
Pro kryptograficke hashovaci funkce: "při jakékoliv změně vstupu se na výstupu změní každý bit s pravděpodobností 50%."

To znamena, ze kdyz mas hash velikosti treba 128 bitu, tak muzes vzit prvnich 64 bitu nebo druhych 64 bitu nebo kazdy lichy bit nebo kazdy sudy a nebo i nahodne. Vzdy proste pro jakoukoliv malou zmenu vstupni zpravy (i zmena v jednom bitu), dostanes kompletne jiny hash.