Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: petersveter 21. 02. 2024, 20:15:15
-
Casto sa skracuje hash na zaciatocny alebo konecny string. Napriklad prvych 10 znakov. Git to robi napriklad. Zaujimalo by ma ci je riziko kolizie vyssie na zaciatku alebo na konci alebo ci je to irelevantne?
-
Je to irelevantní.
-
jen abys nedošel k mílce, git ti zakřičí, když použitý zkrácený hash není unikátní a chce to upřesnit. Nespoléhej na to, že když to zkrátíš, bude to unikátní.
Pokud by byl rozdíl, jestli vezmeš začátek nebo konec, byl by to problém pro ty hashovací algoritmy a jejich (možná i) výrazné oslabení.
-
Viz take zde
https://cs.wikipedia.org/wiki/Ha%C5%A1ovac%C3%AD_funkce
2. malou změnou vstupních dat dosáhneme velké změny na výstupu (tj. výsledný otisk se od původního zásadně na první pohled liší),
"Hash functions can have some technical properties that make it more likely that they'll have a uniform distribution when applied. One is the strict avalanche criterion: whenever a single input bit is complemented, each of the output bits changes with a 50% probability. "
https://en.wikipedia.org/wiki/Avalanche_effect
-
jen abys nedošel k mílce, git ti zakřičí, když použitý zkrácený hash není unikátní a chce to upřesnit. Nespoléhej na to, že když to zkrátíš, bude to unikátní.
Pokud by byl rozdíl, jestli vezmeš začátek nebo konec, byl by to problém pro ty hashovací algoritmy a jejich (možná i) výrazné oslabení.
Hash z principu nemůže být unikátní, když pro teoreticky neomezenou délku vstupu vytvoří otisk o délce pár set bitů. Pro každý možný hash existuje asi nekonečně mnoho možných vstupů/kolizí. Akorát těch hashů je strašně moc (160bitové číslo pro sha1), a hledat vstup pro daný hash je výpočetně mnohem náročnější, než hledat hash pro vstup. Vlastně se na to dá dívat tak, že hashovací funkce pseudonáhodně rozděluje možné vstupy do X skupin.
Zkracováním toho hashe se jen zmenšuje ten počet různých hodnot, kterých hash může nabývat a tím roste šance kolize. Až v se v krajním případě dostaneme k tomu, že jsme z toho (sha1) osekali 159 bitů, zůstal nám jediný bit, a tedy pro všechny možné vstupy to bude buď 0 nebo 1, s 50% šanci. 8bitový hash bude mít 256 možných hodnot a tedy šance kolize bude 1/256, a tak dál.
-
jen abys nedošel k mílce, git ti zakřičí, když použitý zkrácený hash není unikátní a chce to upřesnit. Nespoléhej na to, že když to zkrátíš, bude to unikátní.
Pokud by byl rozdíl, jestli vezmeš začátek nebo konec, byl by to problém pro ty hashovací algoritmy a jejich (možná i) výrazné oslabení.
To ja viem, len som chcel vediet ci je hash rovnomerne rozlozeny alebo nie tak uplne.
-
Pokud si ty hashe generujete sám, mohou se hodit algoritmy a kterých si můžete vybrat délku hashe. Pro spoustu use-case je to dobré řešení. Někdy lze alternativně místo hashe používat UUID nebo nebo jeho část nebo pro identifikaci použít jednoduše rostoucí číselnou posloupnost.
-
Hash z principu nemůže být unikátní, když pro teoreticky neomezenou délku vstupu vytvoří otisk o délce pár set bitů. Pro každý možný hash existuje asi nekonečně mnoho možných vstupů/kolizí. Akorát těch hashů je strašně moc (160bitové číslo pro sha1), a hledat vstup pro daný hash je výpočetně mnohem náročnější, než hledat hash pro vstup. Vlastně se na to dá dívat tak, že hashovací funkce pseudonáhodně rozděluje možné vstupy do X skupin.
Zkracováním toho hashe se jen zmenšuje ten počet různých hodnot, kterých hash může nabývat a tím roste šance kolize. Až v se v krajním případě dostaneme k tomu, že jsme z toho (sha1) osekali 159 bitů, zůstal nám jediný bit, a tedy pro všechny možné vstupy to bude buď 0 nebo 1, s 50% šanci. 8bitový hash bude mít 256 možných hodnot a tedy šance kolize bude 1/256, a tak dál.
Kéž by to tušil Linus, když před dvaceti lety to takhle do gitu zaháčkoval. O unikátnosti jsem samozřejmě mluvil jen v kontextu gitu, který na tom je postavený. Před pár lety jsme s upraveným zdrojákem experimentovali, co se stane při kolizním hashi a zkráceně, git neuloží duplictní hash a prostě si myslí, že už je vše uložené (tiše zapomene změny), při pokusu takový stav zmergovat (vč. fast-forward) tak končí na chybě o poškozeném repu.
-
zkraceny hash jako identifikator citelny pro cloveka ma stale smysl. vetsinou se koukate tak na 3 az 5 commitu zpet, tak tam urcite zkracenina nebude kolidovat a i v ramci celeho repozitare je ta sance velmi mala.
takze vas experiment s kolizi jen ukazuje, ze jste se museli pekne snazit abyste neco zpusobili.
-
Zkracovani hashu je nesmysl a pokud to nejaka aplikace dela tak je to problem. Z pohledu toho jestli prvnich 10 nebo poslednich 10 je lepsich - znova je to nesmysl, hash v idealnim pripade nebude obsahovat ani na zacatku ani na konci nejakou snadne zapamatovatelnou posloupnost znaku - je to spise nahoda. Psat nejakou aplikaci ve ktere budu generovat nejaky dlouhy hash abych ho pak zkratil na 10 znaku je taky nesmysl.
-
Zkracovani hashu je nesmysl a pokud to nejaka aplikace dela tak je to problem.
polozena otazka vyssie je "preco?"
Najde sa celkom dost prikladov, kde to zjavne funguje.
Teoreticky by to mohlo uspokojivo fungovat. (hash sam o sebe je kolizna funkcia)
A je to trivialne aplikovatelne.
Takze tvdenie "nezmysel" a "je to problem" by bolo fajn rozviest.
-
Zkracovani hashu je nesmysl a pokud to nejaka aplikace dela tak je to problem.
Nesmysl je přesně to, co jste napsal, kategorické tvrzení bez jakéhokoli kontextu.
Záleží plně na aplikaci. Zkracovat hash pro ověření finanční transakce nesmyslem být nemusí (na algoritmy sha192 nebo sha384 jste určitě ještě nekoual, že ne?) ale obvykle bývá.
Zkracovat hash pro urychlení výpočtů třeba při zařazování do hash tabulky, nebo pro generování jednoduchého PRNG je celkem v pohodě, ostatně třeba i ext2+ používá half-MD4.
Stejně tak zkrátit hash, pokud chcete jen detekovat "nakopnutá" data, ale v use case nemáte útočníka který se aktivně snaží, tak zkrácený (i obsolete - viz ona md4) hash je úplně v pohodě.
Na co se OP ptal - pokud mu v aplikaci nevadí vysoká pravděpodobnost kolize (a tím i snadnost brute-force), tak je to v pohodě, a pak je jedno, kterou část hashe ořízne.
-
Zkracovani hashu je nesmysl a pokud to nejaka aplikace dela tak je to problem. Z pohledu toho jestli prvnich 10 nebo poslednich 10 je lepsich - znova je to nesmysl, hash v idealnim pripade nebude obsahovat ani na zacatku ani na konci nejakou snadne zapamatovatelnou posloupnost znaku - je to spise nahoda. Psat nejakou aplikaci ve ktere budu generovat nejaky dlouhy hash abych ho pak zkratil na 10 znaku je taky nesmysl.
Představte si aplikaci, která pro identifikaci jednotlivých záznamů ve své append-only databázi používá hash záznamu. Ty záznamy potřebuje identifikovat i uživatel, a aby nemusel zbytečně opisovat celé hashe, aplikace mu to usnadní tím, že mu vedle hashe vypíše i jeho začátek, který je unikátní mezi ostatními hashi v databázi. Stejně tak, když přijímá vstup od uživatele, načte všechny záznamy, které začínají zkráceným hashem – a pokud je výsledkem jediný záznam, je aplikace spokojená a ví, se kterým záznamem má pracovat.
Proč je to podle vás nesmysl?
A ještě druhá otázka – pohybujete se v IT, a nikdy jste neviděl git?
-
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.
-
Git ty hashe zkracuje jen pro uživatele v některých pohledech, a zobrazovanou délku AFAIK upravuje tak, aby to bylo unikátní (tj. umí ji prodloužit a myslím, že se mi to i kdysi stalo). To, že může nastat kolize i při plné délce hashe je druhá věc a ta se může stát u jakéhokoliv použití hashe, zkráceného či ne. Takže nevím, co se vám na odpovědi od FJ nezdá. Git to zkracuje a přitom to zkrácení nemá žádný vliv, protože je to jen zjednodušení pro uživatele.
-
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.
-
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.
-
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.
-
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).
-
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.
-
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ě.
-
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.
$ git rev-parse --show-object-format
sha256
$ git log
commit 4e164c03fe8dc6ed2a6a6f92ebd1d2a0b40e85f45390295b63aa7138179f42a0
..
..
-
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 (https://git-scm.com/docs/git-config#Documentation/git-config.txt-extensionsobjectFormat). 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/
-
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 (https://en.wikipedia.org/wiki/Birthday_problem)).
Lineárně velkou hashovací tabulku bez kolizí skutečně lze vytvořit, říká se tomu perfektní hashování (https://en.wikipedia.org/wiki/Dynamic_perfect_hashing), 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í (https://en.wikipedia.org/wiki/Cuckoo_hashing). 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.
-
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“.
-
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 (https://en.wikipedia.org/wiki/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.
-
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ě )
-
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
-
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ů 2N+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).
-
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.
-
Pokud si ty hashe generujete sám, mohou se hodit algoritmy a kterých si můžete vybrat délku hashe. Pro spoustu use-case je to dobré řešení.
Doporučuji nějakou XOF funkci, třeba SHAKE (varianta SHA3).