Vlákno názorů k článku SHA-1 není bezpečná, Google ukázal kolizi od Aaa - Na konci článku píšete, že kolízia MD5 a...
-
Petr M (neregistrovaný)
Pokud mám dvě funkce F a G, který jsou na sobě nezávislý a chci najít čísla A a B tak, aby výsledky byly stejný, dostanu se na soustavu rovnic
F(A)-F(B) = 0
G(A)-G(B) = 0A při tom samozřejmě platí i vztahy
F(x) = y, G(x) = z
Tím se dostaneme 2D prostoru (najdi x pro dvě stejný y) do 3D prostoru (najdi minimálně dvě x, modu se souřednicí [?, y, z]). A to už je o poznání jinde.
-
Filip JirsákStříbrný podporovatelTímhle přístupem můžete dokázat, že MD5 i SHA-1 jsou stále bezpečné. Útok na obě dvě hashovací funkce ale spočívá v tom, že se nemusí počítat všechny možné kombinace, ale v té funkci byla nalezena jakási „zkratka“, takže těch možností, které je potřeba prohledat, je řádově méně. Protože MD5 i SHA-1 jsou ze stejné rodiny hashovacích funkcí, je možné, že bude existovat i nějaká „zkratka“, kvůli které nebudete muset porovnávat každou variantu MD5 s každou variantou SHA-1.
Žádný takový útok v současné době znám není, ale také ho nikdo nehledal. „Síla“ MD5+SHA-1 tedy nespočívá v tom, že by to byl silný algoritmus, ale prostě nikomu zatím nestálo za to to podrobit analýze. Je to velmi podobné tomu, když si někdo nějakou šifru nebo hashovací algoritmus splácá sám.
Každopádně používat dohromady MD5 a SHA-1 by se mělo jedině v případě, kdy opravdu není žádná jiná možnost. Nechápu, proč je tahle varianta v článku uvedená před SHA-2. Mělo by tam být, že je potřeba používat alespoň SHA-2, pokud to nejde, tak znovu řešit, jak použít SHA-2, když to opravdu nejde, tak to zkusit ještě jednou, a teprve kdyby neexistoval žádný způsob – tak už bych klidně zůstal u SHA-1, protože to stejně nemůže být nic kritického a z případné kolize nebude žádná škoda.
-
Petr M (neregistrovaný)
Jasně. Obecně se přeneseme z hledání průsečíku přímky s křivkou na úroveň hledání průniku přímky s plochou.
Ale pokud dokážeme jednu souřadnici určit, jsme zpátky v rovině a zase hledáme jenom tu křivku místo plochy.
A jsou tam i další zrady, například SHA-1 má výstup 160b, Výstup MD-5 je 128b. Když spočítám výsledný počet kombinací, tak se dostanu na zdánlivých 288 bitů. Z toho ale 128b se dá rychle prolomit... SHA-2 je tak, i přes menší počet bitů, bezpečnější.
-
> Je to velmi podobné tomu, když si někdo nějakou šifru nebo hashovací algoritmus splácá sám.
Hashovací funkce h(x) = sha1(x) md5(x) bych přirovnával spíše k 3DES než k něčemu úplně home-made. (A ani 3DES není uplně dokonalé přirovnání.) Lze snadno dokázat, že je odolná kolizím minimálně stejně dobře jako ta lepší ze dvojice funkcí SHA-1 a MD5. (Umíte-li nalézt kolizi pro h, najdete takto kolizi pro sha1 i md5 současně.) To sice není kdovíco, ale pořád bych tomu věřil řádově více než něčemu úplně home-made. Z hlediska jiných útoků už je argumentace někdy o něco složitější, ale i tady bych tomu věřil řádově víc než úplně home-made funkci.
Pravda, kombinace SHA-1 a MD5 není úplně šťastná, protože obě funkce jsou Merkle–Damgård, obě mají stejnou délku bloku (512b) a obě mají snad i na chlup stejný padding. (Na padding jsem se díval v rychlosti, takže jsem nějaký rozdíl mohl přehlédnout.) Takže stačí „jen“ najít společnou kolizi v kompresních funkcích, a mám hotovo. Ale to asi nebude úplně snadné.
Uznávám taky, že ne vždy kombinace dvou funkcí pomůže. Někde jsem viděl útok na kombinaci MD5+CRC32. Fungovalo to přes tzv. multikolize, kdy (zjednodušeně řečeno) nalezením n kolizí v kompresní funkci vyrobím 2^n kolizí (2^n hodnot, kde všechny mají stejný hash). Když tedy skrze multikolize vyrobím 2^33 hodnot se stejným md5 hashem (při výkonu smartphonu to trvá orientačně 33*0.5 minuty = 16.5 minuty), mohu ve výsledcích hledat kolizi CRC32 hrubou silou a jistě ji tam najdu. Ironicky bude fáze hledání kolize CRC32 trvat nejspíš déle než hledání multikolize pro MD5, protože u CRC32 by případný rychlejší postup těžko zohlednil, že chceme současně kolizi MD5.
Podobný postup u SHA1+CRC32 už se trochu prodraží, i kdybychom chtěli prohledat „pouze“ 2^16 hodnot a doufat, že to u CRC32 vyjde.
U SHA1+MD5 by to teoreticky šlo, pokud akceptujeme cca poloviční šanci na úspěch* a obrovské náklady:
1. Nalezení multikolize SHA-1 (řekněme, že by nám stačilo 2^64 hodnot, tj. 64 kolizí, výměnou za cca poloviční pravděpodobnost úspěchu) by se prodražilo (řádově 6.4 milionu USD), i když by asi nebylo mimo realitu.
2. Projít 2^64 hodnot a najít zde kolizi MD5 by se prodražilo, i když by asi taky nebylo mimo realitu. Je to ale náročné nejen časově, ale i prostorově.
3. Výsledná kolize by byla 128 bloků dlouhá, tj. 128*64B=8KiB. I toto by někdy mohl být praktický problém.Nemohu se ale ubránit pocitu, že pokud toto bude moje nejslabší místo, tak jsem na tom ještě dobře. Zkuste cenu tohoto útoku porovnat s cenou různých 0days. Navíc zde předpokládám, že kolizi kompresní funkce takto dovedeme počítat pro libovolný prefix, což se může po odhalení detailů útoku ukázat jako největší praktický problém.
Ale jinak samozřejmě doporučuji použít SHA-2 radši než MD5+SHA1. Kombinace MD5+SHA1 má smysl pouze v případě nějakých legacy záležitostí apod.
*) Díky narozeninovému paradoxu by pro poloviční šanci na úspěch mělo stačit prohledat cca 2^(n/2) hodnot, ačkoli prosím jistou kolizi potřebuju prohledat 2^n+1 hodnot.
-
Filip JirsákStříbrný podporovatel
Ano, home-made asi nebylo nejlepší přirovnání. Myslel jsem ty případy, když někdo začne amatérsky „vylepšovat“ nějakou kryptografickou funkci (použije jí opakovaně, do výsledku přimíchává globální klíč apod.), má pocit, že výsledek učinil řádově bezpečnější – a přitom se o výsledku jeho snažení dá prohlásit nanejvýš to, že není horší, než ta původní funkce, ze které vyšel. Pravda je, že tyhle pokusy často končí oslabením původní funkce, což není případ spojení MD5 a SHA-1.
Podstatou mého komentáře bylo to, co jste napsal dál – že o kombinaci MD5+SHA1 dnes víme akorát to, že není horší než lepší z těch dvou funkcí, v současné době tedy SHA1. Tedy použitím MD5+SHA1 dostanu stejnou bezpečnost, jako použitím samotného SHA1. Tedy přidáním MD5 se bezpečnost nezvýší, zvýší se jenom iluze bezpečnosti, což je vždy nebezpečné – protože se dotyčný nejspíš nechá ukolébat tím, že pro bezpečnost něco udělal, místo aby rovnou řešil přechod na SHA-2.
-
> Tedy přidáním MD5 se bezpečnost nezvýší
Podle toho, co víme dnes, to vypadá, že se bezpečnost zvýší, byť ne o tolik, kolik by si někdo mohl představovat. Nejlevnější kolize SHA-1 je dnes za cca $100,000 (nebo ještě mnohen levnější, pokud zkusíte znovupoužít známou kolizi). Za kolik zvládnete kolizi SHA1+MD5? Nejlevnější mi známý způsob odhaduju řádově na $10,000,000, a je nad ním spousta otazníků a limitací. Třeba nejasná míra paralelizovatelnosti.
Že si nemohu být jist, že není levnější způsob, který by to zvládnul za malou chvíli? To je pravda. Ale jistotu nemám ani u SHA-2/SHA-3.
> zvýší se jenom iluze bezpečnosti, což je vždy nebezpečné – protože se dotyčný nejspíš nechá ukolébat tím, že pro bezpečnost něco udělal, místo aby rovnou řešil přechod na SHA-2.
Souhlas. Pokud to jde, je přechod na SHA-2 lepší z hlediska bezpečnosti a možná i z hlediska výkonu. Vzácně se ale mohou objevit komplikace, které SHA1+MD5 může řešit – třeba absence HW akcelerace u embedded zařízení. Pak je to na zvážení rizik.
-
Filip JirsákStříbrný podporovatel
Rozdíl je v tom, že SHA-2 a SHA-3 byly navržené s tím, aby odolaly útoku, a bylo to různými způsoby ověřováno. V případě kombinace SHA1+MD5 to tak navržené nebylo a pravděpodobně to nikdo neověřoval. Osobně vnímám velký rozdíl mezi „zkoušeli jsme to rozbít a nešlo to“ a „zatím to nikdo rozbít nezkusil a doufáme, že to bude obtížné“. Proto jsem to přirovnával k home-made šifrám, pro které je typické to druhé tvrzení. A často opravdu mohou reálně „fungovat“, protože se nikomu nevyplatí je rozbíjet. Ale je to sázka do loterie, já dávám přednost těm algoritmům, které se největší experti pokoušeli rozbít a víme, jak dopadli.
-
Karel (neregistrovaný)
Ne, kombinace MD5 a SHA-1 je špatný nápad. Výsledek zabere o cca 1 hodinu déle, než louskání samotné SHA-1. Respektive před deseti lety.
https://www.root.cz/clanky/tunely-v-hasovacich-funkcich-kolize-md5-do-minuty/nazory/84760/
Člověk by čekal, že je to "stará známá věc". Ale asi si prostě noví lidé musí zopakovat staré chyby.
-
Ondřej CaletkaZlatý podporovatelHledání kolize SHA-1 trvá přibližně rok. Hledání kolize MD5 trvá na obdobném hardwaru mnohem méně než sekundu. Myslíte si, že když chcete zlomit obě, stačí ty časy prostě sečíst?
Já myslím, že musíte navrhnout nový algoritmus hledání kolize SHA-1, který z hledání předem vyloučí takové možnosti, které zároveň nejsou MD5 kolizí. Netroufám si odhadovat, o kolik bude takový algoritmus náročnější. Je dost dobře možné, že vůbec, ale může taky platit, že nesmírně.
-
To, co odkazoval, je skutečně validní útok. A čas je vyšší než součtový. Tehdy šlo najít kolizi MD5 pod minutu, takže proč přičítat celou hodinu k celkovému času?
Ale, jak jsem psal, útok předpokládá, že se ve druhé fázi na jednu z funkcí provede bruteforce. Těžko ve druhé fázi něco optimalizovat, byť vyloučené to samozřejmě není.
-
Tuto „starou známou věc“ jsem zde i zmiňoval, byť jsem na to navrhoval jít naopak. Ale pozor na podstatné detaily:
Ten příspěvek předpokládá, že SHA-1 lámete hrubou silou. Pak zmíněné skutečně platí – vygenerujete multikolizi MD5 a během „hodiny“ máte 2^80 hodnot se stejným MD5 hashem, které „jen“ musíte projít hrubou silou a najít tam (AFAIK s pravděpodobností 1/2) kolizi SHA-1. No, good luck s 2^80… A vysledná dvojkolize bude mít 160 bloků, tj. 10KiB.
Vy nejspíš predpokládáte, že tu kolizi SHA-1 uděláte pomocí algoritmu, který Google plánuje zveřejnit, a tedy se složitostí od oka pár řádů pod 2^64. No, to teď z fleku nevyvrátím, ale dost o tom pochybuju. Ten algoritmus našel kolizi na dvou po sobě jdoucích blocích, které mohl libovolně volit. Tady ji má najít na 160 blocích, kde ale může volit jen ze dvou variant, a to ještě musí volit po dvou po sobě jdoucích blocích. Jinak řečeno, algoritmus má osmdesátkrát po sobě na výběr ze dvou variant pro následucících 128B. To je dost omezující podmínka, a tuším, že ten algoritmus takto nepůjde použít.
Proto jsem ostatně navrhoval vyrobit multikolize na SHA-1 a teprve MD5 mlátit hrubou silou. Ani tady si nejsem jist, jestli mi to preconditions k útoku dovolí, ale zřejmě je to časově i prostorově úspornější varianta. (Což před deseti lety asi úplně neplatilo, tehdy se moc nevědělo, jak SHA-1 lámat rychleji než hrubou silou.)
