neprihlásený Piatok, 28. apríla 2017, dnes má meniny Jaroslav   DonaskaKvetov.sk - donáška kvetov v SR a zahraničí Pošli kvety
Čierny deň kryptografie, zverejnená prvá kolízia SHA-1. Umožňuje falšovať PDF

Štvrtok 23. februára sa zapíše veľkými písmenami do dejín kryptografie, keď v tejto deň bola oznámená a zároveň zverejnená prvá verejne známa kolízia hashovacej funkcie SHA-1. Postaral sa o to Google, ktorý kolíziu našiel pomocou jedného z najväčších kedy uskutočnených výpočtov. Kolízia je navyše praktická a umožňuje falšovať PDF podpisované pomocou SHA-1.

Značky: kryptografiaGoogle

DSL.sk, 24.2.2017
       


Štvrtok 23. februára sa zapíše veľkými písmenami do dejín kryptografie, keď v tejto deň bola oznámená a zároveň zverejnená prvá verejne známa kolízia hashovacej funkcie SHA-1.

Postaral sa o to Google, ktorý kolíziu našiel pomocou jedného z najväčších kedy uskutočnených výpočtov.

Nevyužil pritom žiadne výrazne zlepšené teoretické poznatky, keď staval na útoku navrhnutom v roku 2013.

Nájdená kolízia je ale navyše praktická a umožňuje falšovať PDF podpisované pomocou SHA-1. Po teoretickom prekonaní je tu tak už konkrétny potvrdený praktický dôvod, prečo okamžite prestať SHA-1 veriť.

Ako býva zvykom v poslednej dobe u bezpečnostných zraniteľností, kolízia dostala aj svoje meno, Shattered s prvým t štylizovaným ako jednotka.

Hashovacia funkcia SHA-1

Úlohou hashovacej funkcie je z ľubovoľne dlhého reťazca bajtov, napríklad súboru, vypočítať na praktické účely krátky tzv. odtlačok.

Ten má byť v rámci praktických limitov jednoznačný a pri dobrej hashovacej funkcii nemôže byť možné prakticky skonštruovať tzv. kolíziu, dve správy s rovnakým odtlačkom.

Hashovacie funkcie sa okrem iného využívajú napríklad pri elektronickom podpise dokumentu na zmenšenie veľkosti podpisu, keď sa namiesto vytvorenia podpisu v podobe aplikácie kryptografického algoritmu na celý dokument tento aplikuje iba na jeho hash sumu.

Minimálne v minulých rokoch najviac používaná hashovacia funkcia SHA-1 z roku 1995 vytvára odtlačok dĺžky 20 bajtov, teda 160 bitov.

Teoreticky prekonaná

V prípade SHA-1 by tak útok hrubou silou dokázal nájsť kolíziu, dve správy s rovnakým odtlačkom, na 2 ^ 80 výpočtov SHA-1, čo je zatiaľ prakticky nerealizovateľné.

Už v roku 2005 sa objavil prvý teoretický útok na SHA-1, ktorý by dokázal nájsť kolíziu na 2 ^ 69 operácií.

Až útok z roku 2013, ktorý bol aktuálne využitý, má ale už pomerne praktickú zložitosť, keď umožňuje nájsť kolíziu s výpočtovou zložitosťou ekvivalentnou 2 ^ 61 výpočtom SHA-1. Až doteraz, aspoň podľa verejne dostupných informácií, ale útok nebol zrealizovaný a nebola známa žiadna kolízia SHA-1.

Už na základe tohto útoku experti odporúčali prestať SHA-1 používať a hashovacia funkcia sa minulý rok prestala používať u nových vydávaných certifikátov, pričom tento rok prehliadače začínajú certifikáty využívajúce SHA-1 označovať za nedôveryhodné.

Napriek tomu je vo viacerých oblastiach SHA-1 ešte bežne využívaná.

Kolízia

Vo štvrtok Google ale oznámil aj nájdenie reálnej kolízie SHA-1, teda nájdenie dvoch konkrétnych správ s rovnakou SHA-1 hash sumou.




Nájdené kolidujúce správy M(1) a M(2) (hore) skladujúce sa obe z dvoch častí pri zvolenom spoločnom začiatku P (dole), kliknite pre zväčšenie (zdroj: Google / CWI)



Spolupracoval na tom s expertami z holandského inštitútu Centrum Wiskunde and Informatica, CWI, na čele s Marcom Stevensom, ktorí stoja za pôvodným teoretickým útokom.

Tento útok umožňuje nájsť ku zvolenému začiatku P dve správy M(1) a M(2) také, že SHA-1 hash sumy spojenej správy P s M(1) a správy P s M(2) budú rovnaké. Následne samozrejme vzhľadom na postupný výpočet SHA-1 po 64-bajtových blokoch je za tieto správy možné doplniť ľubovoľný ďalší rovnaký reťazec, s ktorým budú mať obe správy stále spoločnú rovnakú hash.

Tím okrem demonštrácie kolízie navyše našiel prakticky zneužiteľnú kolíziu. Dokázal vytvoriť totiž dva PDF súbory, ktoré majú rozdielny zmysluplný obsah a pritom rovnakú SHA-1 sumu.

Za spoločný začiatok si zvolil 192 bajtov zodpovedajúcich začiatku platného PDF, ktorý umožňuje takúto kolíziu prakticky využiť. Pomocou náročného výpočtu ho doplnil dvomi rozdielnymi 128-bajtovými reťazcami, ktoré majú spolu s ním rovnakú SHA-1 hash sumu.

Detaily kolidujúcich PDF

Pre praktickosť útoku tím použil vylepšenie principiálnej metódy navrhovanej už skôr na využitie prípadnej kolízie v hashovacích funkciách vo viacerých formátoch súborov. Metóda vo všeobecnosti počíta s prítomnosťou dát pre obe podoby dokumentu zároveň v oboch kolidujúcich súboroch, pričom rozdiely v líšiacich sa častiach súborov sú využité vďaka možnostiam konkrétneho formátu na výber jednej alebo druhej podoby dát.

Tím konkrétne použil v PDF zahrnutý obrázok formátu JPEG, pričom začiatočná hlavička JPEG-u je v zvolenom spoločnom začiatku a obrazové dáta zrejme oboch podôb v rovnakej doplnenej časti súborov.


Ukážka podoby dvoch rozdielnych PDF s rozdielnou farbou pozadia s rovnakou SHA-1 sumou, kliknite pre zväčšenie (zdroj: Google / CWI)



Tím zatiaľ kompletné detaily nezverejnil, naznačuje ale využitie rozdielnych častí súborov na zmenu pozície odkiaľ sa použijú obrazové dáta JPEG-u a teda ktorá podoba sa zvolí.

Kompletné detaily použitej techniky aj kód umožňujúci uskutočniť útok plánuje tím zverejniť v súlade s politikou Google o 90 dní.


Základná schéma vygenerovaných kolidujúcich PDF, kliknite pre zväčšenie (zdroj: Google / CWI)



Nájdená kolízia je zrejme univerzálne použiteľná na vytvorenie dvojíc PDF s rovnakou SHA-1 s ľubovoľným obsahom. A teda pre vytvorenie takýchto PDF s iným obsahom nie je potrebné zopakovať výpočet tímu ale je možné využiť ním vytvorenú kolíziu. Google totiž okrem iného avizuje aj sprístupnenie nástroja, ktorý umožní vytvárať takéto kolidujúce PDF so zatiaľ nespresnenými obmedzeniami.

Zároveň Google zverejnil hneď dve dvojice rozdielnych PDF s rovnakými SHA-1 hash využívajúce rovnakú kolíziu, okrem dvojice cca 442 KB dokumentov aj dva výrazne menšie o veľkosti iba 2719 bajtov.

Keďže kolízia aj tieto dokumenty sú verejne prístupné, dá sa predpokladať, že experti po analýze využitých možností formátov JPEG a PDF prídu s návodom na vytvorenie iných kolíznych PDF výrazne skôr ako za 90 dní.

Výpočet

Tím kolíziu hľadal na serveroch Google a podľa neho išlo o jeden z najväčších doteraz realizovaných výpočtov.

Pre praktické aspekty výpočtov mal tento nakoniec väčšiu zložitosť ako teoretický útok, keď potrebné výpočty boli ekvivalentné 2 ^ 63.1 výpočtov SHA-1 namiesto 2 ^ 61. To znamenalo podľa Google cca 9.2 x 10 ^ 18 SHA-1 výpočtov.

Výpočet bol 100-tisíc krát rýchlejší ako útok hrubou silou.

Skladal sa z dvoch fáz, prvej realizovanej na CPU a druhej realizovanej na GPU. Prvá fáza vyžadovala cca 6500 rokov výpočtov na jednom jadre moderných x86 CPU, druhá náročnejšia fáza cca 110 rokov výpočtov na Nvidia Tesla K20.

Google samozrejme výpočet realizoval naraz na mnohých CPU a GPU, koľko reálneho času výpočet trval spoločnosť nespresňuje.

Pri prenajatí si výpočtového výkonu GPU od Amazonu by druhá náročnejšia fáza výpočtu pri komerčných cenách stála cca 560 tisíc dolárov, pri využívaní občasných výhodných cien pri nevyťaženej kapacite cca 110 tisíc dolárov.

Dôsledky a ochrana

Na základe dostupných informácií v súčasnosti už prakticky nie je možné veriť overeniu PDF dokumentu pomocou jeho SHA-1 sumy a užívateľom nie je napríklad odporúčané elektronicky podpisovať PDF dokument, ak sa pri podpise využíva odtlačok pomocou SHA-1.

Ako príklad zneužitia Google uvádza scenár, v ktorom prenajímateľ dá nájomcovi podpísať zmluvu s nižším nájmom ale zároveň má k dispozícii verziu s rovnakou SHA-1 a inou vyššou sumou nájmu, pre ktorú je vytvorený elektronický podpis nájomcu tiež platný.

Zverejnené informácie zároveň ukazujú, že nájdenie kolízie je pri zainvestovaní maximálne niekoľkých stoviek tisíc dolárov praktické a odporúčané je tak prestať veriť SHA-1 ako takej. Odporúčaním je prejsť na novšie hashovacie funkcie, SHA-256 prípadne iné verzie SHA-2 alebo už SHA-3.

Na SHA-1 sa spolieha okrem iného aj nástroj na správu verzií súborov a zdrojových kódov Git, ktorý pomocou SHA-1 identifikuje jednotlivé objekty. Kedy, či a ako bude Git upgradnutý zatiaľ nie je jasné.

Použitý verejne známy útok na SHA-1 v každom prípade nie je tak univerzálny ako útok na staršiu a už prakticky nepoužívanú hashovaciu funkciu MD5 z roku 1992, ktorý umožňuje u MD5 vytvoriť kolíziu aj doplnením dvoch rozdielnych zvolených začiatkov. Takýto útok bol v 2012 zneužitý škodlivým kódom Flame, keď si útočníci vďaka MD5 kolízii vytvorili certifikát pre falšovanie aktualizácií Windows Update.

Na čo všetko sa dajú využiť kolízie so spoločným zvoleným začiatkom nie je jasné.

Stevens, ktorý je spoluautorom útoku a aj členom tímu za nájdenou SHA-1 kolíziou, v každom prípade zverejnil užitočný nástroj, ktorý umožňuje detekovať súbor vygenerovaný s cieľom dosiahnuť SHA-1 kolíziu. Nástroj je podľa prezentovaných informácií pravdepodobne výrazne univerzálnejší ako iba detektor konkrétnej kolízie nájdenej tímom, keď detekuje použitie metódy využitej v pôvodnom útoku.

Testované na útok sú podľa Google automaticky aj súbory posielané a ukladané v Gmail a Google Drive a pre dokumenty neobsahujúce citlivé informácie je možné využiť aj webový test s nahratím súboru na shattered.io.

Google informoval o nájdení kolízie v tomto oznámení, bližšie informácie je možné nájsť na shattered.io a v článku popisujúcom útok a nájdenie kolízie (PDF). Väčšie kolízne PDF dokumenty je možné stiahnuť zo shattered.io, menšie sa nachádzajú priamo v článku autorov kolízie.


       
      Zdieľaj na Twitteri


Myslíte si, že NSA a prípadne iné vlády dokázali hľadať kolízie SHA-1 skôr? (hlasov: 241)

Áno      88%
Nie      12%


Najnovšie články:

Intel pomenuje svoje procesory po vzácnych kovoch, príde zlatý aj platinový
FTP má dni zrátané, prestane ho využívať aj veľká linuxová distribúcia
USA pod vedením Trumpa rušia sieťovú neutralitu
Na zachytenie mimozemského signálu máme malú šancu, tvrdí vedec
Ethernetový prepínač s latenciou 49 ns
Netypický krok, softvér výrazne zníži svoju verziu
Zákazník sa sťažuje na podobu FUP u DSL u Orange, oprávnene
Na Európe nakoniec možno pristaneme, v spoločnej misii NASA a ESA
Orange spustil veľké dátové 4G balíky so 60 až 400 GB
V Samsung TV ďalšia bezpečnostná chyba, firma opäť konala kontroverzne a odmietla ju opraviť


Diskusia:
                               
 

Prosim Vas.... Kto dnes este pouziva SHA-1 ? Uz niekolko rokov pouzivame SHA-256 a vyssie (company policy)...
Odpovedať Známka: -7.2 Hodnotiť:
 

Dnes sha-1
Zajtra sha-256
Odpovedať Známka: 7.7 Hodnotiť:
 

Stará dobrá ponožka s peniazmi pod hlavnicou.
Nie dokument v pdf-u.

Odpovedať Známka: 2.7 Hodnotiť:
 

Najistejšia je zlatá tehla zakopaná pod slivkou v babkynej záhrade.
Odpovedať Známka: 2.9 Hodnotiť:
 

To už môže pozichrovat iba babka partizánma ktorá upgraidovala útočnú pušku na vzor SA-58.
Odpovedať Známka: 4.0 Hodnotiť:
 

Staci ked musk alebo niekto oznami ze zacina projekt dolovania zlata na asteroidoch a hodnota tehlicky pojde dooole
Odpovedať Hodnotiť:
 

No, ak bude SHA-256 potencionalne UNSECURE, tak prejdeme na vyssi standard...
Je velmi nezodpovedne od spolocnosti, ze pouzivaju SHA-1, ktora bola uz v 2005 oznacena ako nevyhovujuca...
Odpovedať Známka: 6.0 Hodnotiť:
 

Pozdravujeme Linusa Torvaldsa a jeho GIT :D
Odpovedať Známka: 6.4 Hodnotiť:
 

Prejav úcty v Čierny deň kryptografie.
Odpovedať Známka: 6.4 Hodnotiť:
 

tak konecne mozme desifrovat meciarove CDcko, ta ne?
Odpovedať Známka: 7.8 Hodnotiť:
 

je suis sha-1.
Odpovedať Známka: 10.0 Hodnotiť:
 

sha1 je este pomerne rozsirena vec
Odpovedať Známka: 3.8 Hodnotiť:
 

Nástroju, umožňujúcemu detekciu, s cieľom dosiahnuť SHA-1 kolíziu vygenerovaného, súboru, vzhľadom ku zdroju na githube, samozrejme už prakticky nie je možné veriť.
Odpovedať Známka: 3.3 Hodnotiť:
 

chlapi, nasiel dakto info, ako dlho toto vytvorenie kolizie trvalo? som snad uplne blby, ale neviem to najst v clanku, ani v originali.
Odpovedať Známka: -4.0 Hodnotiť:
 

na skolach by mali zaviest predmet "citam s porozumenim"

"Google samozrejme výpočet realizoval naraz na mnohých CPU a GPU, koľko reálneho času výpočet trval spoločnosť nespresňuje."

imho radovo okolo roka, ked zapojili 110 ks. tesiel a 270 ks. 24-jadrovych 48-vlaknovych xeonov, co A) vyjde tipujem do pol melona a B) nemuselo by to zaberat vela miesta/objemu, zopar skrin

Odpovedať Známka: 2.3 Hodnotiť:
 

No urcite, 10k CPU jadier je nic. Predpokladam ze boli hodne pod mesiacom co sa vypoctu tyka, narocnejsia imho bola priprava.
Odpovedať Známka: -2.0 Hodnotiť:
 

ano mas pravdu, ak mali 1300 ks. tesiel a 3200 ks. 24-jadrovych xeonov (77k jadier), mohli to dat za mesiac

dost velka nevyhoda je, ze cenovo nam tam potom pribudaju cifry jak besne, lebo uz hento by stalo min. 7 cifier ($ ci €), resp. pravdepodobne aj 8 cifier (1 ci 2 na zaciatku)
Odpovedať Známka: 6.0 Hodnotiť:
 

uz pred 12-13 rokmi bolo sha 1 oznacene za nedostacujuce a odporucane prejst na ine.
to ze sa to nebralo do uvahy je ina vec
Odpovedať Známka: 3.8 Hodnotiť:
 

na akcentaciu vaznosti, nadpis mohol zniet, ze "...umoznuje falsovat elektronicky podpisane pdf" (ked je pouzite sha1 )
Odpovedať Známka: -3.3 Hodnotiť:
 

Ja som v pohode - ja pouzivam DES
Odpovedať Známka: 1.4 Hodnotiť:
 

des a hroza
Odpovedať Známka: 2.0 Hodnotiť:
 

BFU z toho budu vedla ako Mojsej ked sa napije omylom H2O...uricte nebudu pozerat na verziu hash sifrovania...
Odpovedať Známka: 7.1 Hodnotiť:
 

Posielam kvety
Odpovedať Známka: 3.3 Hodnotiť:
 

Potrebujete naliehavú pôžičku pre podnikanie alebo platiť účty v úrokovou sadzbou vo výške 3%? Ponúkame osobné úvery, realitné úvery, obchodné úvery a ďalšie potenciálne jednotlivcom, firmám a subjektom spolupráce a organizácie. Bez ohľadu na vašej kreditnej skóre v rozmedzí od $ 5000 dolárov na 50 miliónov dolárov dolárov za maximálne po dobu 1-30 rokov, a ak áno, kontaktujte nás s detailmi nižšie.
Celé meno:__________
Omar: __________
Rod: __________
krajina:__________
postavenie:__________
Mesto: __________
Názov: __________
Sociálny status:__________
povolania: __________
Mesačný príjem:__________
Platné mobilné telefónne číslo: __________
Požadovaný úveru: suma __________
(Úveru a suma mena slovami): __________
Termín pôžička (ktorá bude stanovená v rokoch): __________
Účelom úveru: __________

S vďaka a ocenenie
Pán Anthony William
E-mail nám: barclayfinancialgroupfirm@gmail.com
Ja hovorím: +919108362494
Odpovedať Známka: -3.3 Hodnotiť:
 

Dobrý deň, To je informovať širokú verejnosť, že pani magret JAMES renomovanej súkromných veriteľov pôžičky otvára novú ekonomickú príležitosť pre všetkých tých, ktorí potrebujú žiadnu finančnú pomoc. Potrebujete naliehavú úver zrušte svoje dlhy alebo potrebujete domáci úver zlepšiť svoje podnikanie? Už ste niekedy boli odmietnutí bánk a ďalších finančných inštitúcií? Pozrite sa žiadne ďalšie, pretože sme tu pre všetky vaše finančné problémy. Zaistili sme 2% úverov úrokovej sadzby pre jednotlivcov, firmy a korporácie za jasným a zrozumiteľným spôsobom, podmienkami. Žiadna kontrola kreditu potrebné, 100% zaručená. E-mail: (MAGRETJAMES321@GMAIL.COM)
Odpovedať Hodnotiť:
 

Že sa to konečne odhalilo, by nemalo byť označované za „čierny deň tajnopisu“, ale za „biely deň tajnopisu“!

S pozdravom: „Prajem vám pekný biely deň!“
Odpovedať Hodnotiť:
 

Myslíte si, že získať úver? Vy ste svoj vlastný biznis vážne núdzový úver? Dlhujete To je vaša príležitosť, svoje túžby, osobné pôžičky, pre viac informácií, zabezpečujeme obchodné úvery a firemné pôžičky s 2% úrokom, kontaktujte nás na e-mailu (andmoris38@gmail.com)


Odpovedať Hodnotiť:

Pridať komentár