Vlastní hash

miskith:
Hash je jednosměrná šifra, takže myslím, že ikdyž někdo uvidí kód, tak to nerozluští. Jinak, místo md5 spíše používejte sha1. Nevím, jak to bylo přesně uděláno, ale md5 se podařilo prolomit.

miskith:
Nechci podceňovat, ale dokážete navrhnout nějakou novou a přitom bezpečnou hashovací funkci?

Bylo probíráno už několikrát - k hashům se zpravidla přidává tzv. salt:

• šifrování hesla
• šifrováni
• Sbohem, SQL injection?
• Bezpečné uložení hesel do DB
• md5, sha1 nebo oboje

Má PHP i nějaký kvalitní hash na vyhledávací tabulku (tj. ne takový, ze kterého vyleze 64 znaků, ale číslo)?

imploder:
„tj. ne takový, ze kterého vyleze 64 znaků, ale číslo“
Výsledkem MD5 je číslo.
Nebo respektive... výsledkem jakéhokoliv hashe je sekvence bitů a pak už záleží jen na softwaru, jestli to bude reprezentovat jako znaky nebo jako číslo.
Nicméně MD5 hash se obvykle reprezentuje jako číslo (dodatek: 32-místné číslo v šestnáctkové soustavě).

V PHP5 jde vypsat výsledek MD5 jako surový binární řetězec pomocí funkce hash():

miskith:
Viz Joker, SHA vyvíjí NSA a ikdyž sha0 a sha1 nejsou dokonalé, tak osobně bych se necítil na něco lepšího,
použij třeba sha2 (sha512) s unikátním saltem a máš to

Okolo prolomení MD5 se šíří hrubý omyl. MD5 nebylo prolomeno ve smyslu nalezení původního řetězce (tedy "dešifrování") rychlejším způsobem než zkoušením všech kombinací. Byl nalezen algoritmus, který pro daná data umí v relativně dobrém čase nalézt jiná data se stejným MD5 hashem. Toto je nešťastné, pokud MD5 chráníte nějaký "důvěryhodný" soubor (klient ověří, že soubor je pravý, tím, že má stejné MD5, jaké uvádí vydavatel); hacker může napsat škodlivý kód, který doplní tak, aby měl stejný MD5. Nicméně pro šifrování hesel toto nevadí, jediné, co to znamená, je, že pokud někdo zná Vaše heslo, může nalézt "alternativní" heslo, které bude mít stejný MD5.

AM:
„MD5 nebylo prolomeno ve smyslu nalezení původního řetězce (tedy "dešifrování") rychlejším způsobem než zkoušením všech kombinací.“
Poznámka: Nijak, ani zkoušením kombinací, nelze ze samotného hashe (bez dalších informací) zjistit původní řetězec, použitý jako vstup hashovací funkce.

„Toto je nešťastné, pokud MD5 chráníte nějaký "důvěryhodný" soubor ... Nicméně pro šifrování hesel toto nevadí“
Za prvé to není "šifrování" hesel, za druhé to není pravda.
Podle mého názoru vyhledání kolize je nebezpečnější pro heslo uložené jako jednoduchý (nesolený) hash, než pro ověřování souborů.
K podstrčení škodlivého obsahu musím najít kolizní data se specifickými vlastnostmi: musí to být fungující soubor daného typu a musí obsahovat můj škodlivý kód.
Naproti tomu při prolamování hesla uloženého prostým MD5 mi stačí najít libovolný kolizní řetězec.
Samozřejmě v obou situacích existují další opatření, která útok ztíží, ale "v základu" je podle mě jednodušší útok na heslo, než podstrčení škodlivého kódu.

„jediné, co to znamená, je, že pokud někdo zná Vaše heslo, může nalézt "alternativní" heslo, které bude mít stejný MD5.“
Není pravda.
Znamená to to, že pokud někdo zjistí hash mého hesla (třeba se nějakým způsobem dostane k datům z databáze), může si vyrobit kolizní heslo a s ním se pak přihlásit k mému účtu.

miskith:
„hmm...napadlo mě udělat teda kombinaci hashů. Není toto blbé?:“
Je, stejnou práci odvede i přidání obyčejného saltu.

Ja používám tak, že to dám přes sha1(md5(heslo)) a to následně zkrátím na 32 znaků, takže to vypadá jako md5, ale přitom to není nic z toho.

Já posledně použil něco takového:

Když útočník chce heslo konkrétního uživatele a sůl pro jednotlivé uživatele je mu známá, tak pro něj rozluštění hesla není problém, protože ví, co si musí předgenerovat. Vygeneruje si tabulku hashů všech možných hesel do nějaké délky nebo podle slovníku, akorát ke každému heslu přidá před zahashováním uživatelovu sůl. Pak si může vyhledat podle hashe heslo toho uživatele, jako by solené nebylo.

Joker, DJ Miky::
„Nebo respektive... výsledkem jakéhokoliv hashe je sekvence bitů a pak už záleží jen na softwaru, jestli to bude reprezentovat jako znaky nebo jako číslo.“
Na to právě narážím - s tak dlouhým řetězcem se jako s číslem nedá počítat. Bylo by to neuvěřitelně velké číslo. Ale když je to číslo, tak se dá udělat modulo (stejně by se dělalo, když je menší tabulka).



Takže obyčejná md5() funkce je na to nakonec vhodnější.

Joker:
„Naproti tomu při prolamování hesla uloženého prostým MD5 mi stačí najít libovolný kolizní řetězec.“
Rád bych k tomuto slyšel vyjádření někoho, kdo ví něco více o kryptologii. Hledání kolizí, z toho, co vím (kamarád značně znalý v oboru IT security), znamená, že mám řetězec s daným hashem a k němu umím najít stejný řetězec s daným hashem, nikoli že z hashe samotného dokážu spočítat řetězec, který má tento hash. Nicméně nemůžu najít žádný důvěryhodný zdroj, takže pokud někdo víte, kde to ověřit, prosím :)

AM:
„Hledání kolizí, z toho, co vím (kamarád značně znalý v oboru IT security), znamená, že mám řetězec s daným hashem a k němu umím najít stejný řetězec s daným hashem, nikoli že z hashe samotného dokážu spočítat řetězec, který má tento hash.“
To je teda zamotaná věta :-)

Vysvětlím názorně, co znamená hledání kolize:
1. Vím, že systém používá prostý md5 hash pro kontrolu hesla a nějak zjistím, že účet který mě zajímá má hash třeba 955db0b81ef1989b4a4dfeae8061a9a6.
2. Vezmu hash 955db0b81ef1989b4a4dfeae8061a9a6 a různými postupy se snažím najít kolizní řetězec
3. Zjistím, že vstup "heslo" generuje hash 955db0b81ef1989b4a4dfeae8061a9a6. Přitom nevím (a nikdy nezjistím), jestli "heslo" je skutečně to, co bylo použité k vytvoření hashe! Ale to mi může být jedno, protože mám kolizní řetězec.
4. Zadám kolizní řetězec ("heslo") jako přihlašovací heslo do systému. Přestože to nemusí být skutečné uživatelovo heslo, systém mě přihlásí.

Joker:

„Vezmu hash 955db0b81ef1989b4a4dfeae8061a9a6 a různými postupy se snažím najít kolizní řetězec“
takové způsoby právě zatím neexistují. Hledání kolizí je něco jiného.

Jak říká AM, kolize jsou něco jiného. Rozlišují se dvě kolize, prvního a druhého řádu. Kolize prvního řádu je, že jsem schopný najít nějaké dva řetězce, které mají stejnou výslednou hash. Prolomení tohohle řádu asi moc nevadí z pohledu ukládání hesel, ale pro nějaké digitální podpisy apod. už je to velká díra. Konkrétní útoky založené na této koliznosti se dají někde najít, z hlavy si je nepamatuji. Kolize druhého řádu je, že mám předem daný řetězec a já jsem schopný k tomuto řetězci najít jiný řetězec, který má stejnou hash. Klímův algoritmus z roku 2006 umožňoval generovat kolize prvního řádu, viz například jeho vyjádření na Rootu. Jestli je možné v přijatelném čase generovat kolize druhého řádu teď nevím. Černé mraky se stahují už i nad SHA-1, která je teoreticky prolomena, a už se nesmí u nás používat pro certifikační služby. Ale bezpečnost při hashování hesel by to asi nemělo ovlivnit. Jestli chcete bezpečí, počkejte, až se Klímova nová hashovací funkce Blue Midnight Wish [PDF] stane SHA-3 standardem ;-).

Timy:
Díky, tohle jsem chtěl slyšet :) takže jsem měl pravdu.

Na krátká hesla jsou na webu stejně rainbow tabulky, ale ty lze předgenerovat pro sebe"bezpečnější" hash.

AM, Timy:
„takové způsoby právě zatím neexistují. Hledání kolizí je něco jiného.“
Ale existují. Právě tohle dělá ten asi nejtriviálnější útok, hrubá síla. Anebo raibow tables.

„Kolize druhého řádu je, že mám předem daný řetězec a já jsem schopný k tomuto řetězci najít jiný řetězec, který má stejnou hash.“
A to je přesně to, co demonstruje můj příspěvek.
Mám předem daný řetězec (akorát nevím jaký přesně to je, protože útok na heslo založený na znalosti toho hesla by byl trochu trapný :-) ) a snažím se najít řetězec, který dává stejný hash.

AM:
Pravdu jsi měl, ale vyjádřil ses dost svérázně :-).

„mám řetězec s daným hashem a k němu umím najít stejný řetězec s daným hashem“
Tam má být jiný. Dva stejné řetězce budou určitě mít stejnou hash :-).

Joker:
„Ale existují. Právě tohle dělá ten asi nejtriviálnější útok, hrubá síla. Anebo raibow tables.“
Rainbow tables i brutal force můžeš aplikovat na sebebezpečnější hash, tomu neodolá nic, žeano.

„Mám předem daný řetězec (akorát nevím jaký přesně to je)“
tak to pak není předem daný :) snad je to z Timyho příspěvku dost jasné, ne? Předem daný znamená:
Znám : řetězec A, hash md5(A)
Umím najít: řetězec B, md5(B)=md5(A)

NIKOLI TOTO, takovýto algoritmus rychlejší než brutal-force znám není:
znám: md5(A) (neznám A)
umím najít: B, md5(B)=md5(A)

[#25] Timy
spíš sem se vyjádřil blbě, jasněže jiný, prostě jsem se přepsal :)

Joker:
„A to je přesně to, co demonstruje můj příspěvek.“
To je přesně to, co nedemonstruje. V tvém příkladě máš na vstupu algoritmu hash H a snažíš se k tomu najít nějaký řetězec S, pro který platí hash(S)=H. U kolize máš na vstupu řetězec S a na výstupu řetězec S', pro který platí hash(S)=hash(S'). Výsledkem pak jsou dva kolizní řetězce S != S'. Tedy z informace o tom, jak vypadá S vygeneruješ S'. Kdyby hledání kolizí bylo to, co popisuješ, tak by — vzhledem k tomu, že pro md5 je známý algoritmus hledání kolizí — tady Klíma vyhodil „původní“ řetězec a igigi by rozluštil 100 % hesel a ne jen 92 % ;-).

Timy:
OK, OK, zjevně s těmi termíny operuji poněkud volněji.

Přesto myslím, že moje původní tvrzení je pravdivé. Na prolomení hesla mi stačí najít jakýkoliv kolizní řetězec (pokud "kolizní řetězce" říkám těm, které mají stejný hash).
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- což nevím jak jde (na odkazované diskusi V. Klíma píše že nejde, ale to už je skoro 4 roky)

AM:
„Rainbow tables i brutal force můžeš aplikovat na sebebezpečnější hash, tomu neodolá nic, žeano.“
Ale časová náročnost zde roste exponenciálně k délce a parabolicky ke složitosti hesla. Delší a složitější hesla tak není možné hrubou silou zlomit a jejich hashe nebudou obsaženy v žádné rainbow tabulce.

DoubleThink:
Myslím, žes netrefil pointu AM_ova příspěvku. Šlo o to, že jakákoliv hashovací funkce nemůže být z principu odolná proti útoku hrubou silou nebo slovníkovému útoku. Hashovací funkce může být odolná proti těmto útokům jen při dodání dalších podmínek jako je třeba dostatečná délka vstupu nebo netriviální vstup.