» »

Nov, učinkovitejši napad na SHA1

Slo-Tech - Kot na svojem blogu poroča prof. Luke O'Connor so avstralski raziskovalci Cameron McDonald, Philip Hawkes in Josef Pieprzyk odkrili nov, izboljšan napad na algoritem SHA-1.

Napad s katerim je mogoče izračunati kolizijo, zahteva 252 računskih operacij in je 2000-krat izboljšan glede na prej znane napade. Napad z grobo silo bi zahteval 280 računskih operacij, leta 2005 pa so trije kitajski raziskovalci predstavili napad, ki je zahteval le 269 operacij. Omenjeni avstralski raziskovalci pa so nov napad predstavili na neformalnem delu konference Eurocrypt 2009, podrobnosti pa bodo znane v kratkem, ko bo o omenjeni tematiki objavljen članek.

Nov napad večjim organizacijam z bogatejšimi proračuni že potencialno omogoča zlorabe. Po drugi strani pa se v praksi še vedno uporablja celo MD5, za katerega je že dlje časa znano, da ni več zanesljiv.

17 komentarjev

Bellzmet ::

Aloha!

A lahko kdo poda kakšen link oz. pove, koliko časa potem rabi računalnik (ker mi 2 na 52 potenco ne pove dosti), da razvozlja npr. 6-mestno geslo sestavljeno iz črk, številk, znakov, velike, majhne,... in sicer recimo imamo: Intel s 4 jedri, 4gb RAMA, pa navaden 640gb disk (če je sploh važno).

lp

stegy ::

252 ni prav velika cifra. Danes ima že marsikateri manjši superračunalnik ranga 1TFlopa in več (operacij s plavajočo vejico na sekundo). Če deliš 252 z 1012 je to okoli 4500 s za razbitje. Kar pa je zelo malo. Mogoče ima kdo kaj več znanja o tem.

Zgodovina sprememb…

  • spremenil: stegy ()

arjan_t ::

ne moreš tega kr tako delit, Tflops so samo koliko operacij lahko opravi, samo preverjanje in racunanje SHA1 pa porabi vec operacij

stegy ::

V članku je navedeno, da za izračun ključa potrebuješ 252operacij. Ne piše, da je potrebno še kaj dodatno preverjati. Tako, da če se govori o številu operacij je to najbrž bruto.

arjan_t ::

Dvomom da misli operacije, že če prebereš to:

SHA-1 produces a 160-bit output, which according to the birthday paradox, implies that a collision attack should require approximately 2^{80} operations to succeed.


za birthday attack bos potreboval n/2 poskusov ne opreracij

black ice ::

CUDA je kar nalašč za to. Z GT200 so dodali še podporo za dvojno natančnost (double). Ne vem zakaj ne bi na katerem izmed tekmovanj poskusili na ta način.

ozbolt ::

To je že strašno! Vsaa zaščita je laho predrta v kakih 1000 sekundah. Spet naloga strokovnjakov za nove načine kriptiranja.

Matthai ::

Ni tako hudo. Govorimo pa o KOLIZIJI!
Zloraba oblasti, avtokracija in tema nikoli ne pridejo hipoma, vedno je vmesno
obdobje mračenja, ko se dan preveša v noč; biti moramo pozorni opazovalci
okolja in varuhi luči, da ne postanemo nemočni ujetniki teme. --W. Douglas

NoOrdinary ::

Preverjanje MD5 in SHA-1 istočasno kaj pomaga al sta si algoritma tok sorodna da padeta oba naenkrat ko se rešiš težjega?
brez ideje sem za podpis

arjan_t ::

ne

antonija ::

Ni tako hudo. Govorimo pa o KOLIZIJI!

Lahko malo bolj podrobno razlozis za kaj gre?
Statistically 3 out of 4 involved usually enjoy gang-bang experience.

Bistri007 ::

V P2P omrežjih ima vsaka datoteka hash. S tem napadom lahko narediš drugačno (pokvarjeno) datoteko, ki ima isti hash.
Največja napaka desetletja je bila narejena 4. novembra 2008
Oni so goljufali in Alah je goljufal, Alah je najboljši prevarant. (Koran 3:54)
Citiraj svetega očeta Benedikta XVI. in postani "persona rudis"...

JercSI ::

Sam sem si naredil en lookup table za md5, md4, sha1, sha512,... Imam shranjenih cca 100mio kombinacij.. Diska je šlo cca 100gb. Da sem spisal funkcijo in vse vnose v bazo je trajal 1 dan. Imam pa malce starejši računalnik.

Pyr0Beast ::

Račuaj na nekje 2x2.5 mio gesel/s z bruteforce že z starim X2. Zip arhiv pade v 12 min s dokaj kratkim ali enoličnim geslom.

CUDA poseka kaj takega vsaj za faktor 10, če ne več.
Some nanoparticles are more equal than others

Good work: Any notion of sanity and critical thought is off-topic in this place

fiction ::

Kolizija pomeni, da najdes dve razlicni zaporedji bitov, ki imata enak hash. Torej s pomocjo dolgotrajnega postopka dobis, da imata npr. "zblj" in "foobar" isto SHA-1 vrednost. Zelo uporabno. :)
To se ne pomeni, da lahko za tocno dolocen niz najdes pripadajoc drug niz z istim hashom, ce bi se to zgodilo bi bilo precej bolj kriticno. Seveda to tudi ne pride prav pri bruteforcanju gesel, saj moras tam se vedno iz hasha odkriti dejanski tekst.

Za MD5 podoben napad lahko izvedes nekje v priblizno eni sekundi na navadnem PC-ju. Pri cemer obstaja varianta pri kateri se v bistvu dobi dve zaporedji bitov z istim prefiksem. V stilu "zblj" in "zbfoobar", kar je malo bolj problematicno.

Kako se da to potem zlorabiti? V bistvu je moznosti precej malo. Napadalec mora pripraviti en "dober" in en "zloben" dokument.
Pri tem pomaga dejstvo, da algoritmi delujejo s pomocjo blokov in v bistvu nima veze, ce dvema nakljucnima blokoma (ki dajeta isti hash) dodas enako vsebino. Izvrsljivo datoteko bi npr. naredil tako, da pogleda svoj zacetek in se glede na to odloci ali bo delovala kot "dober" program ali pa kot "zloben".

Pri MD5 jim je recimo uspelo narediti dva zahtevka za certifikat, od katerih je eden izgledal normalno in ga je CA podpisal, s tem pa je spravil v veljavo tudi svojega "zlobnega dvojcka", ki je v bistvu rekel, da je lastnik svoj CA, ki mu originalni CA zaupa. Tako je lastnik certifikata pridobil zaupanje tudi od vseh, ki zaupajo originalnemu CA-ju.

Poenostavljeno povedano bi pri elektronskem poslovanju tak napad pomenil, da ti nekdo da v "podpis" dokument, ki ima zraven se indigo papir. Ko se ti podpises na ta pravi (vrhnji) papir si s tem podpisal se nekaj cisto drugega spodaj.

Se pa da take napade precej lahko odkriti (z malo truda vedno vidis tudi drugo verzijo dokumenta), poleg tega pa lahko cisto majhna oblikovna sprememba na datoteki preden se podpise prekriza zlobnezeve nacrte.

fiction ::

Preverjanje MD5 in SHA-1 istočasno kaj pomaga al sta si algoritma tok sorodna da padeta oba naenkrat ko se rešiš težjega?
Glede na to, da je ista "operacija" nad MD5 tako enostavno izvedljiva je pomoje (MD5, SHA-1) priblizno tako dobro kot samo (SHA-1). Si pa napadalec z napadom na SHA-1 najbrz nic ne pomaga pri napadu na MD5 in obratno.

V P2P omrežjih ima vsaka datoteka hash. S tem napadom lahko narediš drugačno (pokvarjeno) datoteko, ki ima isti hash.
S tem se resuje to, da ti nekdo ne podtakne cesa drugega pa se napake pri prenosu odkrijes. Ampak v praksi to pomeni, da moras biti ti avtor prave in pokvarjene datoteke. Ne mores enostavno za neko ze obstojeco datoteko izracunati drugacne datoteke z istim hashem.

fiction ::

za birthday attack bos potreboval n/2 poskusov ne opreracij
Pri birthday napadu (kjer te zanima poljuben par) namesto H moznosti lahko pregledas samo priblizno 1.25 * sqrt(H) moznosti. Namesto 2^160 imas ~2^80 poskusov, kar pa NI pol od 2^160 (polovica je 2^159). Ce si to predstavljas kot bite, ki jih moras uganiti jih pa je pol manj.

Danes ima že marsikateri manjši superračunalnik ranga 1TFlopa in več (operacij s plavajočo vejico na sekundo). Če deliš 2^52 z 10^12 je to okoli 4500 s za razbitje.
Operacije s plavajoco vejico niso prevec relevantne glede na to, da se SHA-1 racuna v celostevilski aritmetiki. Pa tudi ni receno, da je operacija res en ukaz kot ga vidi procesor. Najbrz moras vse skupaj pomnoziti z neko konstanto. Je pa jasno zdaj mogoce v razumnem casu izracunati collision tudi za navadne smrtnike.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Nov način ribarskega napada

Oddelek: Novice / Zasebnost
142928 (1487) mitja
»

Raziskovalci uspeli rekonstruirati 1024-bitni RSA ključ v 104 urah

Oddelek: Novice / Varnost
52798 (1954) MatevĹžk
»

Nov, uspešnejši napad na AES

Oddelek: Novice / Varnost
122467 (1701) Matthai
»

Prvi uspešen napad na AES

Oddelek: Novice / Varnost
92394 (1809) KoKi
»

Nov napad na ključe za daljinsko odklepanje KeeLoq

Oddelek: Novice / Varnost
216222 (4697) FrizzleFry

Več podobnih tem