neprihlásený Sobota, 31. októbra 2020, dnes má meniny Aurélia
Praktický útok našiel špeciálnu kolíziu SHA-1, plná kolízia len za 75 tisíc

Značky: kryptografiabezpečnosťútoky

DSL.sk, 13.10.2015


Trojica kryptoanalytikov Marc Stevens, Pierre Karpman a Thomas Peyrin na konci uplynulého týždňa oznámila zlepšenie špeciálneho zľahčeného útoku na hashovaciu funkciu SHA-1 a reálne našla kolíziu špeciálneho tvaru.

Zároveň s ich praktickými vylepšeniami má byť možné zrealizovať útok na štandardnú formu SHA-1 iba za 75 až 120 tisíc dolárov.

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.

V posledných rokoch najviac používaná hashovacia funkcia SHA-1 vytvára odtlačok dĺžky 20 bajtov, teda 160 bitov. Útok hrubou silou by dokázal nájsť dve správy s rovnakým odtlačkom na 2 ^ 80 výpočtov SHA-1, čo je samozrejme 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í. Útok z roku 2013 by to dokázal na 2 ^ 61 výpočtov SHA-1, doteraz ale stále nebol považovaný za praktický a zatiaľ nie je verejne známa žiadna kolízia.

Kolízia s tzv. voľným štartom

Trojica kryptoanalytikov aktuálne našla kolíziu pre plnú 80-kolovú SHA-1 ale s tzv. voľným štartom, pri ktorom je možné použiť ľubovoľný počiatočný vnútorný stav SHA-1 prípadne nezhodný u dvoch nájdených správ s výsledným rovnakým odtlačkom.

Pri štandardnej SHA-1 je počiatočný stav pevne daný v definícii SHA-1.

Kryptoanalytici zlepšili pre takýto špeciálny útok doteraz najlepší útok a kolíziu dokázali nájsť na 2 ^ 57 výpočtov SHA-1. Zároveň vyvinuli efektívnu implementáciu na Nvidia GPU a kolíziu našli približne po desiatich dňoch výpočtov na 64 Nvidia GTX 970.

Kolízia štandardnej SHA-1

Nájdenie kolízie s voľným štartom neumožňuje ani neuľahčuje priame skonštruovanie kolízie štandardnej formy SHA-1.

Na základe získaných experimentálnych dát pri nájdení tejto kolízie ale kryptoanalytici dokázali výrazne zlepšiť odhad reálnej komplikovanosti praktického útoku na štandardnú SHA-1 s využitím už známeho útoku so zložitosťou 2 ^ 61.

Ten by tiež vďaka efektívnejšej implementácii na GPU bolo možné podľa nich realizovať na 512 GPU za niekoľko mesiacov. Napríklad pri prenajatí GPU v službe Amazon EC2 by bolo možné kolíziu SHA-1 nájsť s nákladmi na úrovni 75 až 120 tisíc dolárov, čo je už aj v rámci možností bežných kriminálnych gangov.

Doterajšie odhady počítali s cenou za nájdenie kolízie SHA-1 cca na úrovni 700 tisíc dolárov.

Čo keď sa nájde kolízia SHA-1

Nájdenie jednej kolízie štandardnej formy SHA-1, teda dvoch konkrétnych rozdielnych správ s rovnakým SHA-1 odtlačkom, ešte nemusí znamenať nájdenie efektívneho spôsobu generovania kolízií na praktické zneužitie.

Napríklad v prípade hashovacej funkcie MD5 ale jej prelomenie v podobe schopnosti generovať kolízie viedlo až k praktickým útokom s falšovaním SSL certifikátov a nájdenie akejkoľvek kolízie SHA-1 by bolo vážnym varovným signálom.

Po zlepšeniach teoretických útokov tvorcovia softvéru a riešení tak už minulý rok začali postupne intenzívne odchádzať od SHA-1 k ďalším hashovacím funkciám a napríklad webové prehliadače prestanú akceptovať certifikáty podpísané pomocou SHA-1 od začiatku 2017, certifikačné autority by mali prestať vydávať takéto certifikáty na konci tohto roka.

Autori najnovšieho útoku v každom prípade odporúčajú čo najskorší odchod od SHA-1.


      Zdieľaj na Twitteri



Najnovšie články:

Xiaomi už predbehlo Apple a mieri na druhú pozíciu
Odštartovala druhá séria The Mandalorian
Orange zariadenia majú problém s časom kvôli zlému pravidlu pre posun času
NASA úspešne uložila vzorku z asteroidu do návratovej kapsule
WD začal predávať 20 TB disk
Intel avizuje výrazné zvýšenie výkonu 14-nm desktopových CPU
Prima v českom DVB-T zvýšila rozlíšenie na HD
Celé 6 GHz pásmo pre WiFi uvoľňuje aj Južná Kórea
Jarná verzia Windows 10 je už najpoužívanejšou
Orange má ďalší problém, zrejme nezvládol posun času


Diskusia:
                               
 

Kde su tie istoty? To tu uz nikto nic negarantuje?
Odpovedať Známka: 7.8 Hodnotiť:
 

Ja by som všetky tie SHAčka zakázal...
Odpovedať Známka: 8.1 Hodnotiť:
 

Zakáž to všetko a aj invazistov ktorí nám rozdrbávajú už aj tak pošramotenú Úniu...
Odpovedať Známka: -3.3 Hodnotiť:
 

to ne privezenci rozdrbavaju, to americanie, lebo oni robia bordel tam dole a my to mosime potom secko odrobit.
Odpovedať Známka: -6.0 Hodnotiť:
 

Co by si cakal od blbych amikov...
Odpovedať Známka: -7.5 Hodnotiť:
 

Thanks Obama...
Odpovedať Známka: 7.5 Hodnotiť:
 

A tým štvrtým, ktorý vraj rozumie Močizukiho hypotéze, je ktorý maniak?
Odpovedať Známka: 5.6 Hodnotiť:
 

Bitcoin intenzívne hľadá hashové kolízie... A to nepíšem nič o Ethereum...
Odpovedať Známka: -4.3 Hodnotiť:
 

Bitcoin nehľadá kolízie, ale výsledok hashovacej funkcie v určitom intervale. To je rozdiel.
Odpovedať Známka: 10.0 Hodnotiť:
 

no predsa nas pan birnovany predseda
Odpovedať Známka: -8.0 Hodnotiť:
 

Nebola by bruteforce metóda pri takýchto veľkých výpočtoch lepšia?
Odpovedať Známka: -7.1 Hodnotiť:
 

Stále ide o útok hrubou silou, len je optimalizovaný, takže sa časť dát nemusí testovať (pretože je hneď zrejmé, že nejde o správne dáta).

PS: Ak by nepoužili tie optimalizácie, tak by nájdenie kolízie nestálo 75k$ (boli by to 4 miliardy dolárov).
Odpovedať Známka: 10.0 Hodnotiť:
 

Samozrejme ze nie, prave naopak. Hashovacie funkcie su prave tak konstruovane, aby aj minimalne zmena vstupnych dat (napr. JEDEN JEDINY bajt/bit v 1 GB subore) mal za nasledok TOTALNE odlisnu hash hodnotu, napr. JicphaptijUjavOpiac7 a WharUkMacsopCyshwilk (v skutocnosti to nie su hese, ale generovane hesla, nechcelo sa mi vypocitavat hash z nejakych retazcov dat/suborov). V pripade SHA1 existuje 2^80 moznosti, teda presne 1 208 925 819 614 629 174 706 176, co je dost.

1,2 kvadrioliona moznosti je pomerne dost a brutal force ide systematicky. A nemas sajnu ktora z tych moznosti to bude, pretoze ako pisem vyssie, absolutne minimalna zmena vstupnych dat = totalna znema hash vysledku.

Odpovedať Známka: 10.0 Hodnotiť:
 

Samozrejme, že jednoznačná odpoveď neexistuje. Vždy je možné naslepo trafiť na prvý pokus(tzv. hurá systém). A vždy je možné minúť všetko na optimalizáciu útoku(tzv. bojím, bojím metóda).
Ide o to, o koľko energie sa pripravíš kvôli mačke vo vreci. A samozrejme, aký postoj k tomu zaujme dotyčná mačka.
Odpovedať Známka: 10.0 Hodnotiť:
 

preto používam zo srandy len tak bez dôvodne, nezáväzne, absolútne neopodstatnené, nikým nenútené SHA512.
Odpovedať Hodnotiť:
 

Samozrejme, že je možné míňať prostriedky aj na posilňovanie ochrany. Existencia neprekonateľnej obrany predsa garantuje maximálnu efektivitu ich využitia. Len k tomu treba kvantový počítač s kvantovým diskom.
Odpovedať Hodnotiť:
 

Ak uvazujeme s nekonecnym priestorom vsetkych moznych hashovanych retazcov, tak pocet kolizii je tym padom tiez nekonecny, kedze nekonecno/2^80 = tiez nekonecno. Proste nekonecno moznosti sa ma zobrazit "iba" do 2^80 moznosti a tych kolizii je tym padom nekonecno vela. Tym padom zobrazenie samozrejme nie je bijekcia (kde prave jednemu obrazu zodpoveda prave jeden vzor). Nie je ani injekcia, kde moze mat obraz aj viac vzorov, ale je to surjekcia, kde sa priraduje na každý prvok cieľovej množiny (mnoziny vzorov) aspoň jeden prvok z východiskovej množiny (mnozina obrazov). "Aspon jeden" v matematika znamena jeden a viac. Inak povedane jeden obraz moze mat viac vzorov. Ak je mnozina vzorov mensia ako mnozina obrazov, je to dokonca nevyhnutne.

Odpovedať Známka: 3.3 Hodnotiť:
 

sorry 20 bajtov cili 160 bitov = 2^160 moznosti pre hodnoty SHA1

na celkovej uvahe to ale nic nemeni
Odpovedať Hodnotiť:
 

Len najst tie kolizie (t.j. dva hashovane stringy s tym istym hash vysledokm) je kurevsky tazke. Ak uvazujeme len o konecnom priestore vsetkych moznych hashovanych retazcov (napr. subory/retazce do velkosti 1 TB), tam je dokonca aj pocet kolizii konecny. Mnozina vzorov ma 256^1000000000000 prvkov a mnozina vzorov iba 2^80 prvkov. Kolizii je potom 256^1000000000000/2^80 co je prakticky stale 256^1000000000000, co je kurevsky velke cislo.
Odpovedať Známka: 10.0 Hodnotiť:
 

plus za prvu otazku k veci :)
Odpovedať Hodnotiť:
 

Mimo tému, ale musím sa niekde posťažovať:
Práve mi volal technik z Orange, ze mi zrušia zmluvu na dsl, lebo vraj dostali stanovisko z Telekomu, že už mi nemôžu poskytovať službu - (zhodou okolností sa práve pripojil sused cez Telekom). To znamená, že v tomto banánistane Telekom uprednostňuje vlastné zmluvy pred dodržaním poskytovania služby, ktorá bola sprostredkovaná cez Orange.

Už asi 4, alebo 5 rokov som bol nepretržite zazmluvnený.
Odpovedať Známka: 10.0 Hodnotiť:
 

Su to ich kable, tebe by sa tiez nepacilo keby si natahas vlastne kable a konkurencna firma by ta za to zjebala ze mas monopol. A kto dnes pouziva dsl???
Odpovedať Známka: -5.4 Hodnotiť:
 

Tú otázku čo si položil myslíš vážne? Asi žiješ v nejakom vysnenom svete, kde už nikto ani nevie čo to DSL je a nie na Slovensku...
Odpovedať Známka: 10.0 Hodnotiť:
 

Pokiaľ máš viazanosť, tak Ti zmluvu zrušiť nemôžu presne tak, ako ju ty bez zmluvnej pokuty nemôžeš tiež zrušiť. A ak už je po viazanosti, pripoj sa aj ty cez Telekom, ak nemáš inú možnosť, čo pravdepodobne nemáš.
Odpovedať Známka: 10.0 Hodnotiť:
 

A sťažuješ sa na to, že Telekom Ti objasnil skutočné garancie, poskytované Orange-om na x stranách zmluvy ?
Odpovedať Známka: 10.0 Hodnotiť:
 

Nieco podobne riesil brat. Mal DSL od Telekomu, po viazanosti ho prerusil a hned sa pripojil sused. Potom sa uz pripojit nemohol. Telekom odkazal, ze nema na ulici uz volne porty. Takze to v tvojom pripade vyzera podobne, len s tym, ze zakaznik Telekomu ma prednost predtym z Orange a je mozne, ze uz ta nepripoji ani Telekom. Telekom na DSL uz jebe, porty uz nerozsiruje.
Odpovedať Známka: 10.0 Hodnotiť:
 

Telekom serie na porty uz asi 10 rokov !!

Asi od toho casu som sa chcel na ulici pripojit (aj s 3 dalsimi susedmi) a nic.. nestali sme za to.. Ani 1 z nas.
Odpovedať Známka: 10.0 Hodnotiť:
 

telekom podla vsetekho metaliku odpaja, kde sa da. :-(
Odpovedať Známka: 10.0 Hodnotiť:
 

som zvedavý aké ceny "zajeb link" tu zajebe v Seredi, kde je už roky labuť, či dá dvojnásobnú rýchlosť za polovicu ceny alebo čím bude konkurovať...neverím že budem prekvapkaný
Odpovedať Známka: 2.0 Hodnotiť:
 

A prečo by ju odpájal? Práveže si myslím presný opak. Využívaju ešte všade kde sa to len trochu dá...
Aj za cenu prehadzovania párov.
Oni totiž majú symetrické vedenia a teda nemôžu použiť jeden drôt z jedného páru a druhý drôt z iného páru. To by išlo na Internet veľmi pomaly...
Odpovedať Hodnotiť:
 

Nemozu ti zrusit zmluvu absolutne pokial to ty nechces, napisem ti ako to bolo mne vysvetlene v nitre na telekomunikacnom urade, (inak na to tam su) no telekom ma po komousoch zdedene linky co uz su natahane a musia umoznit aj konkurencnym firmam poskytovat internet, nic viac nic menej, cize musia ti nechat port ktory mas pre koho ty len budes chciet nielen telekom. Inak aj orange dsl zapaja telekom servisaci, ja som chcel dve linky este na starom byte a v telekome mi to vysvetlili tak ze na kazdy byt je jeden port, cize musel mi sused potvrdit ze si neda internet od telekomu a potom mi zapojili dva dsl na jeden byt, cize treba za tym ist, v prvom rade skor ako pojdes do orange si zavolaj na telekomunikacny urad a potom nabity informaciami tam zbehni a vyhras :), ludia co pisu ze telekom uprednostni svojich to je blbost totalna, oni musia orange dsl umoznit napojenie a nemozu nutit aby si clovek dal len dsl od telekomu.
Odpovedať Známka: 2.0 Hodnotiť:
 

Skutočne niekto tvrdí, že v prípade konfliktu záujmov, je povinnosťou Telekomu uprednostniť záujmy komerčného sprostredkovateľa pred záväzkami voči vlastným zákazníkom?

Odpovedať Známka: 10.0 Hodnotiť:
 

Ešte nemám definitívne stanovisko ako to dopadne.
Podľa článku 7 - Zánik zmluvy je Orange oprávnená písomne ukončiť platnosť zmluvy z dôvodu technickej neuskutočniteľnosti ďalšieho poskytovania služby.
Inými slovami, keď budú chcieť ma tak, či tak odpália.
Odpovedať Známka: 10.0 Hodnotiť:
 

Technickú (ne)uskutočniteľnosť určuje Telekom.
Inými slovami, keď Telekom povie, je nepodstatné, čo chcú.
Odpovedať Hodnotiť:
 

ty asi nechapes o com pisem, ja nepisem o tom ze si das ziadost ci sa da zaviest alebo nie, kde rozhoduje telekom, respektive dojde technik od nich a zisti ci sa da alebo neda a pride ti rozhodnutie o zavedeni alebo nie, ano tam rozhoduje technik od telekom a je jedno ci ide o orange alebo ineho, ale bavyme sa o funkcnej linke a uz zapojenej a to je rozdiel, telekom musi mat jednu linku pre ineho poskytovatela, dokonca sa mi stalo uz ze sam telekom povedal ze nemoze zapojit dsl pretoze musi nechat porty aj pre inych operatorov a nezaviedli znamemu net a musel cez orange, toto su skusenosti, a co sa tyka kablov tak oni nerusia dokonca menia za nove cize ani to by nemohlo prejst.
Odpovedať Hodnotiť:
 

Chápem veľmi dobre. Odporúčaš postup na základe čiastočných informácií, ktoré "povedala pani na telekomunikacnom urade v nitre" v inom prípade, pričom, ako uvádza aj vyššie Boxer, "zakaznik Telekomu ma prednost".
Áno, má. Telekom má totiž povinnosť, v prípade žiadosti o zriadenie pripojenia, danú zákonom. Sprostredkovateľovi(Orange) môže umožniť iba využitie zvyšných voľných portov.
Odpovedať Hodnotiť:
 

cize co ty pises o uskutocneni alebo nie je odveci lebo sa nebavíme o zavedeni ale o funkcnej linke a to je uplne nieco ine o com pises ty, pretoze ked je zapojena a podpisana zmluva na net napr na dva roky tak telekom s tym nemoze nic urobit pretoze ma orange prenajatu tu konkretnu linku kedze ide, tam uz technik nemoze nic spravit a ani telekom.
Odpovedať Hodnotiť:
 

Orange môže zákazníkovi podstrčiť aj zmluvnú viazanosť na 100 rokov. Ale to je stále iba vizitka jeho prístupu ku zákazníkom.
Odpovedať Hodnotiť:
 

odpoviem na oba dotazi, telekom nemoze zrusit sluzbu orange, spravne si poznamenal ze z technickeho neuskutocnenia, ale ty mas sluzbu a nic nemenis. Proste keby prehadzujes link niekde inde ano to by platilo co pisu, ale pokial nie, tak telekom nemoze zrusit sluzbu ktoru poskytuje orange to proste nieje mozne ani na slovensku :), pisem jedine kedy by toto bolo mozne je pri premiestneni linky kde si v nemilosti telekomu ale inak nemozu, lebo protimonopolny urad rozhodol ze oni musia orange prenajat kable na dsl mne to povedala pani na telekomunikacnom urade v nitre vsak pisem ze som nieco podobne riesil. Pokial tam sluzba je dostupna a nemenis nic tak pojde dalej aj keby telekom sa na hlavu postaví, na to je ten telekomunikacny urad a keby nieco spravia v momente to ries cez nich a uvidis :) ja mam len dobre skusenosti s TUSR, tiez som mal problem s telekomom a linkami a uz mam orange a telekom mi vratil 6 faktur.
Odpovedať Hodnotiť:
 

inak aj tu na dsl bol clanok ze telekom musi ci chce alebo nie poskytnut kable pre orange http://www.dsl.sk/article.php?article=15391
Odpovedať Hodnotiť:
 

Teraz ide o to, či zavádzaš z neznalosti alebo úmyselne.



Odpovedať Hodnotiť:
 

Vďaka za radu, zatiaľ mi linka funguje, hoci so zníženým profilom -reálne cca 14/0,6, namiesto 15/1, ako šla doteraz v pohode. V najhoršom prípade skúsim zabojovať aspoň za zachovanie statusu quo. Ak ma budú chcieť odstrihnúť, určite skúsim TUSR.
Odpovedať Hodnotiť:
 

Drzim ti palce, ale toto urcite vyhras pokial sa nedas, mne to stale pride ze pokial sa clovek neozve tak ma smolu, tu v okoli sme uz tolko krat riesili telekom a ich technikov ze az. Tí ktory sa nedali a isli za tym tak maju dnes net a tí co kaslali a uspokojili sa z rozhodnutim technika maju dnes ine nety a kaslali na to.
Odpovedať Hodnotiť:
 

Ja už som si s nimi užil svoje. Cca každý 1/4 rok mi menili svojvoľne profil linky a kdečo sa nedalo, čo napokon spokojne dlhodobo bežalo. Ale toto už je predsa len trochu moc.
Odpovedať Hodnotiť:
 

ja osobne za 10 rokov som riesil asi 80 pripojeni telekomu a orange. Uz by som mohol knihu napisat o nich, hlavne o telekome ich jednani a neschopnych pracovnikoch na pobockach. Raz davno mi tu jeden dobre poradil este ked som ja mal problem a mal pravdu a zenska na pobocke sa mi ospravedlnovala ze ona to nevedela ze sa daju urcite veci zmenit. Preto pomozem pokial viem alebo som sa stretol s nejakym problemom, co uz tu telekom vystraja je neskutocne, ono pokial sa to niekoho netyka tak kaslu na to a to je chyba, lebo ja mam telekom riadne v zuboch.
Odpovedať Hodnotiť:
 

Nateraz som to uhral iba tak, že mi zostal profil linky na parametroch 16,564/0,796. S tým samozrejme môžem zabudnúť na 15/1, za ktoré platím, ale druhá alternatíva bola, že mi orange nechá preveriť, či mi môžu nechať 10/1. Tak som radšej zostal pri tom, čo mi beží za 22€.
Odpovedať Hodnotiť:
 

V súčastnosti je SHA1 zastaraly a nahradzuje sa SHA256
Odpovedať Hodnotiť:
 

To je sice fajn, ale plno softov len pred 1-2 rokmi zacalo podporovat SHA2, dovtedy ficali len na SHA1.

Detto plno certifikatov je s SHA1.
Odpovedať Hodnotiť:
 

Este lepsie SHA-512 :)
Odpovedať Hodnotiť:
 

224,256,384,512 to je jedno, hlavne za nie sha3 - ta uz je vobec vybrana?
Odpovedať Hodnotiť:

Pridať komentár