Vlastní hash

DoubleThink:
„Ale časová náročnost zde roste exponenciálně k délce a parabolicky ke složitosti hesla.“
Přesně, jak říká Timy: Ano, to já nepopírám, nicméně nezávisí už tam tak moc na síle hashe (maximálně o konstantu), to jsem se snažil říct.

Joker:
„Na prolomení hesla mi stačí najít jakýkoliv kolizní řetězec (pokud "kolizní řetězce" říkám těm, které mají stejný hash).“
Ano, toto je samozřejmě pravda, nicméně "rychlé algoritmy" jsou známy jen v tom případě, kdy už jeden řetězec s daným hashem znáš - což jsi sám uznal, že pak je nesmysl hledat další :)

„Pro podstrčení škodlivého kódu potřebuju najít nejen kolizi, ale zároveň ta kolize musí obsahovat na určitých místech určitá data“
bohužel opět nemám ověřený zdroj, ale dle známých zběhlých v IT security to již dnes lze - je znám algoritmus, jak k řetězci představujícímu třeba virus "dopočítat" zbytek tak, aby vyhovoval hashi.

Joker:
„Na prolomení hesla mi stačí najít jakýkoliv kolizní řetězec (pokud "kolizní řetězce" říkám těm, které mají stejný hash).“
Jenže to právě není možné. Není znám obecný postup, jak z libovolného hashe získat zpět nějaký řetězec se stejnou hashí. Ale s pouhou znalostí kolizních řetězců se už dají dělat kejkle a falšovat podpisy a soubory, takže zneužití je horší. Některé příklady psal Klíma v Kryptologii pro praxi [PDF].

Ještě editace: princip tamějších útoků je použitelný jen pro MD5 a podobné funkce — je to kvůli tomu, že výslednou hashí je hash vzniklá po poslední rundě. Jiné hashovací funkce už jsou (mohou být) lépe ošetřené, takže ten útok jak je tam popsán, by neprošel.

miskith:
„jaká je šance, že když přidám salt a dám md5 a sha1 a pak výsledek zkrátím na 32 znaků“
Pokud "32 znaků" = 32-místné hexadecimální číslo = 128 bitů, měla by pravděpodobnost kolize být 1 : 2^128 - což je to samé, jako normální MD5.

Dodám ale, že přidání soli nemá snížit pravděpodobnost, že jiné heslo dá stejný hash- to lze zařídit leda použitím hashovací funkce s delším hashem (prostě zvětšením počtu možných hashů).
Sůl má jiné pozitivní efekty:
- Má-li každý uživatel jinou sůl, nejde zjistit, když více uživatelů má stejné heslo (s prostým hashem je možný útok typu založit si několik účtů s častými hesly, pak získat přístup pro čtení k databázi a podívat se, kdo má stejná hesla).
- Na prolomení hesla nestačí najít libovolný kolizní řetězec, je nutný kolizní řetězec obsahující sůl na správném místě.
- Sůl prodlužuje heslo a zvyšuje jeho složitost, takže je hůř napadnutelné třeba přes rainbow tables.

miskith:
„jestli je možnost (popřípadě jak velká), že když někdo bude zkoušet heslo a zadá nějaké jiné, tak po zhashování bude sice hash úplně jiný, ale po zkrácení na 32 znaků bude stejný jako správné heslo.“
Tak samozřejmě že je.

Zvolím si náhodné číslo větši než 0 a menší než 10. Jaká je pravděpodobnost, že to bude 2?
Zvolím si náhodné číslo větší než 0 a menší než 1000. Jaká je pravděpodobnost, že jeho první číslice bude 2?

...v obou případech stejná, protože dojdete k náhodnému číslu od 1 do 9, jenom jiným způsobem.
To s těmi hashi je to samé, jenom s většími čísly.

Joker:
„- Sůl prodlužuje heslo a zvyšuje jeho složitost, takže je hůř napadnutelné třeba přes rainbow tables.“
Když útočník má zdrojáky, tak ví, jak se sůl aplikuje a dokáže zjistit i sůl pro jednotlivé uživatele (musí se nějak počítat - tj. je jasná ze zdrojáku - nebo být někde uložená), tak mu nic nebrání si předgenerovat rainbow-tables pro ty samé hesla, ale se solí. Pokud má každý uživatel jinou sůl, tak to ale musí udělat pro každého uživatele zvlášť, v tom sůl pomáhá. Prodloužení hesla ale sebelepší sůl nenahradí, protože heslo není zjistitelné (systém žádnou jeho část nemá, uživatel si ho musí celé pamatovat), zatímco sůl zjistitelná je (je někde uložená).

miskith:
„Přeci 1-10 vylosuješ třeba 9 a 1-1000 vylosuješ třeba 687...“
Ano. A první číslice ze 687 je 6.

„Jinak pořád nevim, jestli odpovídáš na to, na co se ptám, ale nechci tu zbytečně spamovat“
No jestli já to pochopil, tak dotaz byl, jaká bude pravděpodobnost kolize, když do databáze uložím 128 bitů z nějakého delšího hashe.

Odpověď je: Stejná jako se 128-bitovým hashem.
Když si uložím jen prvních 128 bitů, je mi celkem na nic, že za nimi byly ještě další bity. Stejně jako s těmi čísly.

Dodatek: Napsal jsem to už jasně?

Polopaticky: zkracování hashe je naprostá kravina, prostě to nedělej. krom pár ušetřených bajtů na serveru (ano, pouze bajtů) nic nezískáš a hodně nabouráš bezpečnost hashe.

Sůl je pěkná věc, nicméně tak i tak je nezbytně nutné, aby uživatel neměl hesla typu "aaa", takové heslo neochrání ani indické koření.