Generování kolizí SHA-1

Google na svém blogu věnovaném počítačové bezpečnost informuje o nalezení "reálného" způsobu generování kolizí hašovací funkce SHA-1. Podrobnosti a zdrojové kódy budou zveřejněny do 90 dnů. Již dnes lze ale na stránce SHAttered nalézt 2 pdf soubory, jejichž obsah se liší a SHA-1 otisk je stejný (infografika).

23.2.2017 17:53 | Ladislav Hagara | Bezpečnostní upozornění

Komentáře

[xkucf03]

Je zajímavé, jak málo se ty dokumenty liší. Čekal bych, že bude potřeba vygenerovat poměrně hodně dat, aby to „vyšlo“ – i když je pravda, že užitečného rozdílu je tu málo – jen jeden bit – zbytek je jeho kompenzace.

$ wget http://shattered.io/static/shattered-1.pdf
$ wget http://shattered.io/static/shattered-2.pdf

$ ll
-rw-rw-r-- 1 hacker hacker 422435 úno 22 23:42 shattered-1.pdf
-rw-rw-r-- 1 hacker hacker 422435 úno 22 23:42 shattered-2.pdf

$ hexdump -C shattered-1.pdf > shattered-1.pdf.hex
$ hexdump -C shattered-2.pdf > shattered-2.pdf.hex

$ sha1sum * | sort
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf
46b091b5b5e6a7bcd7ce34d44c07153f2bd14585  shattered-1.pdf.hex
5821146eb214448e0c2f79d47033a3d6e4a8503c  shattered-2.pdf.hex

$ sha512sum * | sort
cf9a4103cf049ee1bd1bba81780adf532c62eba708d9a02009cda449e1e12b7252d941b296f84f9248388ba5695a0b05b4a1733eb85c6967a8ccf4755f155b41  shattered-2.pdf.hex
c0389be95ee20dc7749afc473642db3201c58ed02365d6ffa6e93a4e2ab64bd5f03a106cc14405914ef3e5e32bf59e639a5062368caee45734a9c162080c24af  shattered-1.pdf.hex
f39a04842e4b28e04558496beb7cb84654ded9c00b2f873c3ef64f9dfdbc760cd0273b816858ba5b203c0dd71af8b65d6a0c1032e00e48ace0b4705eedcc1bab  shattered-2.pdf
3c19b2cbcf72f7f5b252ea31677b8f2323d6119e49bcc0fb55931d00132385f1e749bb24cbd68c04ac826ae8421802825d3587fe185abf709669bb9693f6b416  shattered-1.pdf

$ diff shattered-1.pdf.hex shattered-2.pdf.hex
13,20c13,20
< 000000c0  73 46 dc 91 66 b6 7e 11  8f 02 9a b6 21 b2 56 0f  |sF..f.~.....!.V.|
< 000000d0  f9 ca 67 cc a8 c7 f8 5b  a8 4c 79 03 0c 2b 3d e2  |..g....[.Ly..+=.|
< 000000e0  18 f8 6d b3 a9 09 01 d5  df 45 c1 4f 26 fe df b3  |..m......E.O&...|
< 000000f0  dc 38 e9 6a c2 2f e7 bd  72 8f 0e 45 bc e0 46 d2  |.8.j./..r..E..F.|
< 00000100  3c 57 0f eb 14 13 98 bb  55 2e f5 a0 a8 2b e3 31  |<W......U....+.1|
< 00000110  fe a4 80 37 b8 b5 d7 1f  0e 33 2e df 93 ac 35 00  |...7.....3....5.|
< 00000120  eb 4d dc 0d ec c1 a8 64  79 0c 78 2c 76 21 56 60  |.M.....dy.x,v!V`|
< 00000130  dd 30 97 91 d0 6b d0 af  3f 98 cd a4 bc 46 29 b1  |.0...k..?....F).|
---

> 000000c0  7f 46 dc 93 a6 b6 7e 01  3b 02 9a aa 1d b2 56 0b  |.F....~.;.....V.|
> 000000d0  45 ca 67 d6 88 c7 f8 4b  8c 4c 79 1f e0 2b 3d f6  |E.g....K.Ly..+=.|
> 000000e0  14 f8 6d b1 69 09 01 c5  6b 45 c1 53 0a fe df b7  |..m.i...kE.S....|
> 000000f0  60 38 e9 72 72 2f e7 ad  72 8f 0e 49 04 e0 46 c2  |`8.rr/..r..I..F.|
> 00000100  30 57 0f e9 d4 13 98 ab  e1 2e f5 bc 94 2b e3 35  |0W...........+.5|
> 00000110  42 a4 80 2d 98 b5 d7 0f  2a 33 2e c3 7f ac 35 14  |B..-....*3....5.|
> 00000120  e7 4d dc 0f 2c c1 a8 74  cd 0c 78 30 5a 21 56 64  |.M..,..t..x0Z!Vd|
> 00000130  61 30 97 89 60 6b d0 bf  3f 98 cd a8 04 46 29 a1  |a0..`k..?....F).|

[chrono]

Súbor, vygenerovaný týmto postupom, dokáže odhaliť napr. sha1collisiondetection

[Luděk Postrašil (SEO UX Experts s.r.o.)]

Jsem rád, že jsme před lety nepodlehli přemlouvání obchodníků s teplou vodou, kteří radili přejít na SHA-1. Moje intuice mi radila zůstat u staré dobré MD5 a dnešní události mi dávají za pravdu. Takže až vám zase někdo bude vnucovat nějaké novoty, tak mu řekněte ne a tohle mu můžete dát jako příklad, jak se mu to do pár let vymstí.

[R]

MD5 je na tom akoze lepsie?

[Heron]

Tak rozhodně se pro to rychleji hledají kolize

[Jirka W.]

Ano. MD5 je lepší než SHA-1. CRC32 je lepší než MD5. A úplně nejlepší je, když projdete data byte po byte a zavoláte na to xor.

[Luděk Postrašil (SEO UX Experts s.r.o.)]

XOR je příliš primitivní. To byl pokus o vtip? My si vyvíjíme vlastní sofistikovaný algoritmus. Navíc jde použít pro šifrování, hešování i podepisování - režim se nastavuje globální proměnnou. Interně to používáme už roky - jede na tom kompletně fakturace a výkazy práce. A letos jsme to začali instalovat i u zákazníků.

Mimochodem, kromě čísel a písmen A-F používáme i zbytek abecedy - při stejné výtěžnosti jsou stringy kratší, což se jednak líbí účetním, že toho nemusí opisovat tolik, a jednak to zabírá míň místa na disku a taky šetří FUP u našeho ISP. Na poradách se vždycky smějeme zpátečníkům, pro které svět končí písmenkem F.

[kralyk z abclinuxu]

Na poradách se vždycky smějeme zpátečníkům, pro které svět končí písmenkem F.

Nemáš něco společného s tím týpkem, co tady před pár lety navrhoval použít IP adresy s čísly vyššímy než 255? Že by kolega?

[Peter Golis]

Také IP adresy sa bežne používajú vo filmoch.

[JS]

Jo, a funguje jim to tam dobře, tak proč by to nemohlo fungovat aji jinde...

[Peter Golis]

Tak navrhni tvojmu poskytovateľovi internetu že keď nechce pridelovať verejné IPv4 a na IPv6 nemá topológiu, tak nech prejde na IPv5 alebo aspoň IPv4,5.

[Jindřich Makovička]

Samozřejmě, jen si to vyzkoušejte!

$ sha1sum shattered-1.pdf shattered-2.pdf 
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf

$ md5sum shattered-1.pdf shattered-2.pdf 
ee4aa52b139d925f8d8884402b0a750c  shattered-1.pdf
5bd9d8cabc46041579a311230539b8d1  shattered-2.pdf

[R]

Bonusova uloha: vytvorte dvojicu rozdielnych suborov, ktore budu mat rovnaky SHA-1 aj MD5 hash.

[Prohnutá nudle]

[Luděk Postrašil (SEO UX Experts s.r.o.)]

Přesně tak, zrovna dneska jsme prodali systém, který používá MD5 - a osobně jsem na těch PDF od Googlu ilustroval, jak je náš produkt odolný i proti nejnovějším hrozbám.

[nic]

Ach jo, tak vy to skutečně myslíte vážně... to je dost smutné.

[Luděk Postrašil (SEO UX Experts s.r.o.)]

Tak to prostě chodí - průměrný manažer nebo nákupčí si nepamatuje, co se psalo před lety - leda to, co si před chvílí přečetl časopise nebo slyšel na konferenci. A kdyby nás chtěl přechytračit třeba synek některého z nich a vytasil se s kolidujícími fajly, tak mu to stejně nebude fungovat, protože my všechno nejdřív XORujeme naší tajnou konstantou. To přece dělá každý, komu není bezpečnost úplně u zadeke.

[Jendа]

+1

To je tak strašně z praxe až to bolí

[koroptev]

tohle nemuze byt mysleni vazne to je vtip ze

[Sid]

Seo expert predsa

[Ladislav Hagara]

MD5 Collision Demo

[Luděk Postrašil (SEO UX Experts s.r.o.)]

Takových stránek vám vyrobím třeba deset a umístím je na přední příčky v Googlu i na Seznamu.

[nic]

Umístěte si je kam chcete, to tu neřešíme. Řešíme tu, že evidentně nechápete o čem je tu řeč. Kolize v šifrách jsou v podstatě interference, a to že nějaký soubor má interferenci / kolizi v jedné šifře nevypovídá absolutně nic o tom, že je jiná šifra bezpečná / bezpečnější, když na stejném souboru jako ta první kolizi nemá. Ve skutečnosti ji má taky, jen na jiném vstupním vzorci. Jeden čas se dokonce řešilo, že Intel procesory (první s AES jednotkou, což byl tuším Sandy Bridge, kdyžtak ať mě někdo v tomto opraví) mají kompromitované AES jednotky, aby generovaly "náhodná" čísla modulovaně právě v takových interferencích, aby (jakoukoliv) šifru oslabily.

[Luděk Postrašil (SEO UX Experts s.r.o.)]

K tomu vám můžu říct leda to, že tam žádné interfejsy nemáme - nepotřebujeme je, používáme totiž C++ a tam je vícenásobná dědičnost a vystačíme si s classami.

[koroptev]

tleskam a schvaluji miru sofistikovanosti trollingu

[roumen]

kompromitované AES jednotky

AES jednotky (ty co vykonavaji AES instrukce) jsou kompromitovane dost tezko, AES jaksi musi z principu vzdy fungovat spravne - kdyz pres SSH nebo HTTPS posilate data, druha strana musi umet dekodovat spravne (a neni zdaleka jiste ze na druhe strane je Intel), jinak by se na to prislo dost rychle (protoze tech sifrovanych dat se posila tintilion denne). Navic vetsina tech instrukci akcelerujicich AES pracuje nad SSE registry, bylo by trivialni se podivat na ty registry pocas behu..

Co mate na mysli, je RNG - jednotka pro generovani nahodnych cisel. On totiz ten generator snima nejaky kvantovy jev, pak to kvantizuje, a vysledny stream se prohani jeste AESem (aby to bylo "rovnomernejsi"). Resilo se to, jestli ve skutecnosti cely ten generator neni jen cisty AES s nejakym predvolenym klicem. Coz bohuzel nelze nijak snadno zjistit. Intel jistou chvili tlacil na Linuse, aby na Intel systemech byl tenhle generator jediny zdroj entropie, jenze zhruba v te dobe se stal Snowden a tendle "napad" sel rychle do kytek.

[nic]

Kecy v kleci. Dobře tedy když vás to zajímá, tak přesněji se jednalo o generátor náhodných čísel, který byl upraven tak, aby dával čísla "poněkud méně náhodná" a zároveň "poněkud více obsahující pravidelný vzorec"

Aha, tak vidím že v druhém odstavci jste to sám napsal. "Intel tlačil" je víc než dostatečná odpověď a zaplaťpánbůh že u Linuse h.... vytlačil.

[Martin Mareš]

Prima, tak se ještě naučte základy kryptografie a úspěch je zaručen ;)

[Matlák]

Vím že mistr z nás jenom dělá voly a trollí, ale celkem vtipně pro tentokrát. A já jen dodám že můj (a nejen můj) byznys stojí na SHA-256 a stejně se těším/bojím okamžiku, který jistě přijde relativně brzy...

[Jendа]

Ty jsi bitcoinbaron?

Škoda, že používají double-SHA-256 jen tak a nesolí ten mezivýsledek (AFAIK). Tím by šlo v případě objevení problému získat ještě nějaký čas.

[kralyk z abclinuxu]

Ohledně gitu: Linusův mail, thread.

[Luděk Postrašil (SEO UX Experts s.r.o.)]

Opět výhoda osvědčených technologií oproti módním výstřelkům - my jedeme na SVN a tam by se nic takového nestalo - Subversion přiděluje commitům unikátní ID - žádné náhodné kaše.

[nic]

Aha, troll... no tak to mění situaci. Omlouvám se ostatním netrollím návštěvníkům za krmení tohoto exempláře.

[Kate]

Spíš to beru jako břitkou parodii reality v některých firmách :)

[Mira]

Takhle dopadne svn checkout pote, co jsem commitnul oba zminene PDF soubory

$ svn co file:///home/svn/myproject/
A    myproject/shattered-1.pdf
svn: E200014: Checksum mismatch for '/home/mira/workspace/myproject/shattered-2.pdf':
   expected:  5bd9d8cabc46041579a311230539b8d1
     actual:  ee4aa52b139d925f8d8884402b0a750c

[xkucf03]

Jak funguje ten „hardened SHA-1“ algoritmus? Je někde implementace? Pokud by se tím nahradilo současné SHA-1, tak by tyhle problémy zmizely (a to původní chování by mohlo být volitelné nějakým parametrem).

[chrono]

Vyššie som posielal odkaz na program, ktorý také súbory dokáže detekovať a dá sa to použiť aj ako knižnica na generovanie (a súčasné testovanie) SHA-1. Ak tá knižnica zistí, že boli tie súbory vygenerované s cieľom vytvoriť SHA-1 kolíziu, tak na to upozorní a program (alebo knižnica) môže použiť iný algoritmus (napr. SHA-3 a použije sa len 160 bitová časť).

[Jendа]

Vypadá to, že to řeší tenhle a podobné útoky, ale nikdo nezaručuje, že nepůjde udělat kolize, kterou to detekovat nezvládne. Nebylo by nejjednodušší prostě přejít na nějakou jinou funkci?

[xkucf03]

A co zpětná kompatibilita? Třeba u verzovacího systému – nebo by tam šlo jednoduše přejít na nový algoritmus? IMHO by to řadu aplikací rozbilo (např. kdybys přešel na SHA-256, i kdybys to zkracoval na délku původního algoritmu) a v tom případě je upravená SHA-1 celkem dobrou volbou, protože všechno bude fungovat jako dosud a jen u těch kolidujících dat se budou generovat odlišné hashe.

Obecně je na to potřeba myslet už při návrhu (vím, po válce je každý generál) a předem počítat, že se budou algoritmy měnit a umožnit plynule přecházet mezi nimi – např. u hesel se to tak dělá, bývá tam prefix, který signalizuje formát/algoritmus, tudíž jde používat i více algoritmů v jednu chvíli (např. uživatelé, kteří se dosud nepřihlásili, mají heslo ještě ve starém formátu) nebo u šifrování taky programy běžně podporují starší a novější šifry a ty nejslabší se postupně vyřazují a zároveň přibývají novější. Tam, kde se počítají hashe nějakého obsahu je zase dobré mít datové struktury (model) připravené tak, aby šlo uvést víc hashů v různých formátech.

[Heron]

A co zpětná kompatibilita?

Tak ono otázkou je co by to rozbilo a zda by nebylo možné udělat přechodnou verzi vcs, která bych vnitřně přelouskala vlastní repositář (já vnitřnosti gitu znám pouze do té míry, do jaké potřebuju, ale už jsem taky (bohužel) musel dělat operace, které znamenaly změny historie repa a v podstatě přegenerování všech dalších commitů (a tím pádem i jejich hashů)) a dokázala by pracovat i se vzdáleným repositářem ještě ve starém tvaru. To by nemuselo být úplně nemožné a asi ani moc bolestivé.

vím, po válce je každý generál

No já bych to takto nenazýval. To, že kryptografické funkce bývají prolamovány se vědělo hodně dlouho před gitem, takže spíše bych použit "kdo chce kam ...".

Tam, kde se počítají hashe nějakého obsahu je zase dobré mít datové struktury (model) připravené tak, aby šlo uvést víc hashů v různých formátech.

Tak to rozhodně. Mě baví, že na webech, které deset let používali jako checksum stahovaných souborů md5, si konečně všimli, že md5 nebrat, tak tam narvali sha-1 a to i poté, co to bylo EU a NISTEM zakázáno používat pro státní správu - 2010 / 2011.

Jako fakt tahle neuvěřitelná setrvačnost mě prostě nepřestává fascinovat, nehledě na to, že to už skoro musí být generace lidí, kteří ani md5 "nezažili" (v profesním životě). Kde se to bere nevím a kdy do módy vstoupí sha-2 nebo sha-3 fakt teda netuším. Možná opět až s nějakou barvenou stránkou o jejich prolomení.

[chrono]

Pre git už existujú záplaty, ktoré dokážu využiť tú detekciu kolíznych útokov pri kontrole repozitára (a predpokladám, že podobné záplaty budú čoskoro dostupné pre všetky programy, kde to má zmysel).

Pri tom prefixe je problém s tým, že každá hash funkcia spôsobí, že bude história úplne iná (pretože objekty môžu obsahovať hash iných objektov).

Pri tej podpore viacerých hash funkcií je zase problém s tým, že by sa klient mohol prinútiť použiť tú najmenej bezpečnú hash funkciu.

Momentálne sa všetky tieto otázky preberajú na mailing liste gitu a napr. Linus Torvalds navrhuje, že staré objekty (už uložené v repozitári) by mohli používať len sha-1 a nesmeli by odkazovať na nové objekty a nové objekty by mohli používať len novú hash funkciu a až na rodiča v commite by tiež nesmeli odkazovať na staré objekty.