Zkrácení haše pro identifikaci

[petersveter]

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?

[Reklama]

[Filip Jirsák]

Je to irelevantní.

[_Tomáš_]

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í.

[xyz]

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

[Zopper]

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.

[Reklama]

[petersveter]

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.

[Ondrej Nemecek]

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.

[_Tomáš_]

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.

[alex6bbc]

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.

[Petr Branik]

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.

[Pavel...]

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.

[Wasper]

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.

[Filip Jirsák]

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?

[Petr Branik]

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.

[Zopper]

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.