Názory k článku Shambles je útok, který snižuje bezpečnost SHA-1 na úroveň MD5

V jednom z případů autoři využili obrázku JPG (respektive prostor za koncem obrázku). Pokud je hash tvořen pouze z viditelných hodnot, tak by neměl být problém. Ale když už jde prakticky generovat výsledky otisku na požádání, je na čase přejít na nový algoritmus. Vlastně už jen to, že lze předvídat změnu otisku při konkrétní změně vstupu, je selhání algoritmu.

> Pokud je hash tvořen pouze z viditelných hodnot, tak by neměl být problém.

To by vyžadovalo mít parser na všechny možné typy dokumentů, který řekne, co je a co není viditelné. A někdy to ani nemusí jít snadno určit -- třeba tam mohou být nějaké komentáře, které skoro nikdo nečte. A někdy tam mohou být naprosto oprávněně pseudonáhodná data, třeba kryptografické klíče.

> Ale když už jde prakticky generovat výsledky otisku na požádání

Nejde, a to ani u slabší a déle zlomené MD5. Jde udělat, aby dva výpočty zkonvergovaly do stejného otisku, ale nemůžeš si vybrat, jaký ten otisk bude. Takže si třeba nemůžeš najít Linusův podpis otisku ABCD123 a vygenerovat jiný dokument s tímto otiskem. Ale i tak se s tím už dají dělat některé útoky - viz červ Flame, kde generovali kolizní (MD5) certifikáty.

> Vlastně už jen to, že lze předvídat změnu otisku při konkrétní změně vstupu, je selhání algoritmu.

Co tím myslíš? To, jak se změní otisk při změně vstupu, zjistím vždycky prostě tím, že ten hash znova spočítám.

Textová data jsou jen speciálním případem binárních dat

Ano, může tu být praktická komplikace, že textová data s potřebnými vlastnostmi je těžší vygenerovat než obecná binární data. Záleží i na kódování. Jiná omezení klade UTF-8 a jiná klade pouhý zákaz 0x00.

Použití textových dat tak sice může být určitým faktorem, který ztěžuje útok, ale rozhodně si nemyslím, že by to měl být důvod pro použití textových dat. Ono podobně je v principu možné hashovaná data před hashováním třeba proložit nějakými specifickými byty (třeba každý druhý bude 0x06) nebo převést do base64. Toto je zjevnější vlastnost návrhu, lze tomu lépe nastavit požadované parametry a nerozsype se to při změně kódování. I to bych ale bral spíše jako nouzovku, kterou si člověk kupuje čas. Co víme o těchto útocích? Jsme si jisti, že nepůjde rozumně cílit nějaký specifický druh dat bez přílišného nárůstu výpočetní a finanční náročnosti? Možná. Tedy nevíme.

Navíc takovéto opatření předem předpokládá, že se hashovací funkce neplní svůj účel správně. Může to znít jako další (vedlejší) úroveň obrany, ale:

1. Když už, takovéto věci mají řešit kryptologové, kteří navrhují hashovací funkce. Ne každý po svém s různými chybami. Rozhodně to nemá ovlivňovat návrh přes X dalších vrstev.
2. Lze to řešit i lépe, třeba použitím několika různých hashovacích funkcí. Pokud jsou na sobě nezávislé, je možné je i vzájemně xorovat.
3. Mám tušení, že něco jako (2) už používá třeba SHA-3.

jinak u gitu právě použití více nezávislých hashovacích funkcí a vzití 160b z výsledku právě v dané konverzaci navrhoval kdysi sám Linus.

Je samozřejmě pravda, že ochcávka s textovými daty kulhá na obě nohy, avšak u gitu zatím reálně funguje, podle všeho.

Sha-1 je již řadu let nedoporučované, podobné útoky se nejspíš budou i nadále objevovat a už se dávno mělo přejít. Kombinace více hashovacích funkcí opět posouvá náročnost, stejně tak ale posouvá schopnost vůbec říct o kolik a jestli to nemá přesně opačný efekt.

> jestli to nemá přesně opačný efekt.

Jediný problém by mohl být, kdyby ty hashovací funkce měly podobnou konstrukci. Pak by jednotlivé bity mohly být korelované a vzájemně se vyrušit (1^1 = 0^0 = 0). Myslím si ale, že něco takového udělat by muselo být celkem nápadné každému, kdo vidí více do hloubky jednotlivých hashovacích funkcí. Pro opatrnost bych tedy nevolil kombinace jako SHA-256 a SHA-512 (obojí patří do SHA2), ale třeba SHA2 s SHA3 by mělo být OK.

Jinak v tom problém nevidím. Budou-li funkce produkovat nekorelovaný výstup, pak snad jakékoliv selhání kterékoliv funkce zachrání přítomnost alespoň jedné dobré funkce.

V případě sřetězení místo xoru dokonce ani nevadí korelovaný výstup, akorát dostaneme delší hash.

Nelze ovšem moc spoléhat, že takto ze dvou nebezpečných hashovacích funkcí (např. MD5 a SHA1) vznikne jedna bezpečná. Útok to může ztížit, ale zrovna u MD5 a SHA1 jsem po zceřejnění Shattered popisoval, že najít současnou kolizi MD5 s SHA1 je zřejmě realizovatelné s dostatečným (byť ne malým) rozpočtem. Stručně, je potřeba najít několik (na sobě závislých) kolizí SHA1, z toho spočítat multikolize (počet kolizních párů nám naroste exponenciálně) a následně mezi nimi dělat kolize MD5 hrubou silou. Kolize MD5 hrubou silou sice může znít jako špatný vtip, ale je to díky narozeninovému paradoxu zvládnutelné a lépe to neumím, pokud chci vybírat z kolizních párů pro SHA1.

No právě, jak provést zřetězení, abych oba dva algoritmy neoslabil? Xor? Concat? Chain? Hash z hashe? O jakémkoliv zřetězení chce uvažovat jako o novém hashovacím algoritmu a posuzovat ho jako celek, nikoliv se snažit odvozovat z vlastností samostatných algoritmů.

Sřetězením jsem myslel concat. Když najdete kolizi (jakéhokoliv druhu), znamená to, že máte kolizi toho druhu pro oba algoritmy, navíc současně (jedna kolize použitelná samostatně u obou základních algoritmů). Obdobně i u preimage, pokud původní vstup nelze uhodnout.

Komplikovanější to může být u odolnosti vůči length extension attack (tam podobná úvaha neplatí, byť protipříklady budou asi spíše teoretického rázu, jako že vezmeme zleva ořezanou sha-512 na 256b a zprava ořezanou sha-512 na 256b).

Bude to komplikovanější i pro hledání preimage z malé množiny, jako se dělá u lámání hesel – tam nalezení preimage nejspíš znamená nalezení původního vstupu a stačí nám to najít pro jednu z těch funkcí a pro druhou to bude automaticky sedět. Ale pro tyto účely jsou již nějakou dobu klasické hashovací funkce považovány za nevhodné, protože z hlediska rychlosti sledují opačný cíl – být co nejrychlejší.

Uznávám, že u xoru to může být komplikovanější, jak jsem sám zmiňoval.

Jo, obecně to teď nejde, ale když budeme předpokládat, že ty commity připraví útočník a požádá Alici o podpis toho nevinného...

Nojo, máš pravdu. Já už radši nic psát nebudu ;)