Prijavi se z GoogleID

» »

SHA-1 razbit

SHA-1 razbit

Slashdot - Bruce Schneier v svojem blogu poroča, da naj bi kitajski raziskovalci Xiaoyun Wang, Yiqun Lisa Yin in Hongbo Yu uspeli najti kolizijo v SHA-1 funkciji.

To pomeni, da so raziskovalci našli dve različni sporočili, za kateri algoritem SHA-1 vrne isto vrednost, njihova metoda iskanja pa je veliko hitrejša kot metoda grobe sile, ki temelji na preiskušanju vseh možnih kombinacij.

To v praksi pomeni, da je mogoče npr. neko potrdilo banke tako prirediti, da bo izračun digitalnega podpisa pokazal, kot da je potrdilo poslala banka, čeprav bo le-to v resnici pa bo ponarejeno. Z drugimi besedami - razbitje SHA-1 je pomemben korak na poti k možnosti ponarejanja digitalnih podpisov.

21 komentarjev

Pithlit ::

Scary 8-O.
Life is as complicated as we make it...

phantom ::

Zakaj delate takšno paniko zaradi ene kolizije? Z eno samo kolizijo si skorajda nič ne morete pomagati, da bi lahko kaj konkretnega ponaredili bi jih potrebovali milijone ... Ta kolizija niti približno še ne pomeni razbitje algoritma, ampak je le droben korak do tega cilja. Odvisno od tega, koliko novih metod za iskanje kolizij so pogruntali oz. koliko so se naučili pri iskanju te kolizije.

64202 ::

phantom: Ni samo ena kolizija, ampak so nasli luknjo v SHA-1, ki potem zmanjsa kompleksnost iskanja kolizije iz 2^80 na 2^69. Skratka zdej lahko en racunalnik naredi delo gruce z 2048 racunalniki. Kolikor razumem :).

Bistri007 ::

Bodo pa daljše ključe začeli uporabljat...
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"...

sverde21 ::

ma sej za md5 so tud najdl kolizijo pa še dej ni programa k bi kej hitrej od bruteforcanja delu
<?php echo `w`; ?>

pecorin ::

ja odkrili so 2048 krat hitrejsi nacin za iskanje 2 sporocil z istim SHA-1 hashem. drugace je pa teh "kolizij" neskoncno..

ferdo ::

neki mi obrazložite..

A to je recimo mišleno - digitalni certifikat, ki ti ga dobiš na banki "nllb", da uporabljaš KLIK ?
In pol naj bi misleč keš nakazu "predpostavim - SKB" banki, ubistvu pa bi ta keš šel navidezni banki oz. bi denar šel drugam, ker sem posloval z navidezno banko?..?????

Maximus ::

V grobem povedano ja.

LP!

Quikee ::

Na-a... to kaj si ti opisal je bolj phishing.

Matthai ::

Ja, je phising, samo v tem primeru bi izgledalo, kot da je sporočilo poslala tvoja banka, v resnici pa bi bilo lažno. Se pravi phishing za bolj pazljive stranke, ki preverijo digitalni podpis.

Sicer pa v NSA velja en pregovor: attacks can only get better, not worse. Ne dvomim, da bodo o SHA odkrili še kaj...
All those moments will be lost in time, like tears in rain...
Time to die.

MrStein ::

Hmm, čudno, da sporočila , ki kolidirata, nista nikjer objavljena.
Ali samo jaz ne najdem ?

Če jih ni, pa velja logika : "imamo dokaze, samo pokazat vam jih ne moremo" Yeah , right ... ;)
Motiti se je človeško.
Motiti se pogosto je neumno.
Vztrajati pri zmoti je... oh, pozdravljen!

gothmorg ::

Hm, eno je teoretična plat zgodbe, drugo pa povsem praktična.

Pa denimo, da bi bilo v realnem času moč najti besedilo, ki bi povzročilo kolizijo. Torej: besedilo B (teoretično ponarejeno digitalno potrdilo banke), ki ima SHA-1 odtis enak besedilu A (pravemu digitalnemu potrdilu banke).

Vendar - POZOR: verjetnost, da bo kolizijsko besedilo besedila "Hello World" ali digitalnega potrdila prave banke pravilno strukturirano in bo imelo kak smisel, je zanemarljivo majhna.

Veliko verjetneje je, da bo kolizijsko besedilo popoln nesmisel in se dalec od tega, da bi bilo podobno kakemu drugemu digitalnemu potrdilu. Hej, ali ste si kdaj ogledali kak certifikat? Ta zadeva ima natancno doloceno ASN.1 notranjo strukturo, kjer lahko ze en sam spremenjen bit vse pokvari. Enako velja za elektronske pogodbe, placilne naloge in ostale stvari, ki se podpisujejo. Ze res, da bi bilo mozno najti drugo zaporedje bitov, ki bi imelo enak prstni odtis, a da bo to zaporedje bitov nov placilni nalog/pogodba ali kaj drugega... Prakticno nemogoce.

Lep pozdrav,
Andrej.

ferdo ::

mnja.. g.Andrej, tolk si me prepričal kot tisti ko hočejo razbiti to kar ti zagovarjaš..
pat položaj, pustimo se presenetit, in če nas že, mislim, da ne bo dobro..

LP

PS: v tem primeru sem raje pesimist kot optimist, pač, misliti na najhuje ;( , ker da bi me nekdo prepričeval v neki, kar nekdo hoče in mu celo nekaj uspeva, pomeni da je slednji že zelo dolgo v tem poslu, in zelo-zelo prepričan v to, da mu celo uspe. ima cilj, Cilj tistega ki pa zagovarja nadmoč tega sistema je pa samo cilj prepričevat, da to ni možno, kdo zdaj DELA? KDO zdaj DELA da bo rezultat POZITIVEN, kdo pa DELA da bo REZULTAT negativen.... eh.

Zgodovina sprememb…

  • spremenil: ferdo ()

Matthai ::

Velja pogledati kaj pravi Schneier: The paper isn't generally available yet. At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team.

More details when I have them.

Drugače je pa dobro, da se javno najde šibke točke (in potem zadewvo popravi), kot pa če bi se do tega odkritja prikopale samo kakšne tajne službe.

BTW: sporočilo bi bilo smiselno na začetku, na koncu pa dodani neki "random" znaki.
All those moments will be lost in time, like tears in rain...
Time to die.

gothmorg ::

Glede pristnega sporočila in naključnih znakov na koncu: zaradi strukture digitalnega potrdila je to - kot rečeno - praktično nemogoče. Naključnih znakov ne moreš prilepiti na konec; lahko bi jih vrinil v kako razširitveno polje (t.i. v3 extension), a zelo pomembno vprašanje je, koliko dolg bi moral biti ta niz naključnih znakov, da bi prišlo do kolizije. Verjetnost, da bi zadoščala kaka normalna količina (red velikosti do 10 kB), če sploh kakšna, je zelo zelo majhna. Enako velja za npr. plačilne naloge ali davčne napovedi. Večina se jih prenaša v kakem XML-like formatu, ki ima prav tako hude omejitve glede hranjenja naključnih binarnih znakov. Pripenjanje smeti na konec pa pri pravilni izvedbi preverjanja podpisov v omenjenih primerih (torej non-enveloped XML podpisi in digitalna potrdila oziroma ASN.1 strukture) ne bi smelo biti problem, saj naj bi preverjal fiksno in natančno določljivo dolžino podatkov, ne pa kar vsega + še malo. :-)

Prvo vprašanje je torej - ali zna predlagan postopek poiskati kolizijo ob upoštevanju nekaterih začetnih pogojev. Pri digitalnem potrdilu so to npr. (številke so seveda izmišljene, a princip drži): naključni znaki se morajo nahajati na natanko 718. zlogu v datoteku. Dolžina teh znakov mora biti zapisana v točno določeni obliki (DER pravila) pred začetkom teh znakov na 716-717. mestu. Dolžina celotne strukture, ki vsebuje razširitev in ki je zopet odvisna od dolžine naključnih znakov, mora biti napisana še na 437-438. mestu, poleg tega pa mora biti celotna dolžina digitalnega potrdila (spet odvisna od naključnih znakov) napisana na 2. do 4. mestu. Verjetnost, da taka kolizija obstaja (in je krajša od 50 terabajtov), je IMHO zanemarljiva.

Lep pozdrav,
Andrej.

Matthai ::

Ja, s tem se pa strinjam. Ampak razvoj gre kar hitro naprej. Poleti so še trdili, da je SHA-1 varen...
All those moments will be lost in time, like tears in rain...
Time to die.

64202 ::

Kje je to uporabno:

En fejstfejst vazen email<font color="#ffffff">randomsmetirandomsmeti...

--- PGP SIGNATURE ---
blabla..

Matthai ::

Ja, to bi bilo zelo izvedljivo.... Ampak OK, zaenkrat je še vednopotreben velik computer power...
All those moments will be lost in time, like tears in rain...
Time to die.

sankus ::

khm...kaj je to kolizija (da je lahko velika 50 TB)?

gothmorg ::

Hm, tisto s PGP podpisanim sporočilom naj bi bilo načeloma lažje, vendar imaš še vedno dva stroga predpogoja - smiselno sporočilo na začetku ter <font></font> tage pred in za smetmi. Nekako se mi dozdeva, da bo postopek, ko ga bodo razkrili, matematične narave - torej bo iskal kolizijo z nekimi operacijami, ki ne bodo imele ravno veliko manevrskega prostora za postavljanje začetnih ali robnih pogojev.

Kakor koli že, tako ali tako bi vsak kos programske opreme moral delovati po načelu "what you see is what you sign", kar seveda velja tudi za preverjanje. Če se ne motim, te Word zdaj že opozori, da (podpisan) dokument vsebuje dele, ki niso vidni. Načeloma naj bi tudi poštni programi delovali po istem principu.

Lep pozdrav,
Andrej.

gothmorg ::

Končno sem našel malo časa in malce pobrskal po internetu glede najnovejše šibke točke v SHA-1.

Kot kaže, so moje domneve pravilne - začetnih parametrov (npr. že podpisanega besedila) s to metodo iskanja kolizije sploh ne moreš določiti, saj postopek najde dve različni besedili, ki imata enak odtis v okoli 2^69 operacijah namesto v "običajnih" 2^80 operacijah. Obe besedili sta seveda kup čistih naključnih znakov.

Takoj, ko imajo podpisani podatki interno strukturo (torej 99,9 % podpisanih podatkov), ta metoda ni uporabna.

Lep pozdrav,
Andrej.


Vredno ogleda ...

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

Nov, učinkovitejši napad na SHA1

Oddelek: Novice / Varnost
174250 (2814) fiction
»

Izdajanje ponarejenih CA certifikatov

Oddelek: Novice / Zasebnost
335915 (3774) denial
»

Nov preboj na področju zgoščevalnih funkcij

Oddelek: Novice / Znanost in tehnologija
152951 (2506) pecorin
»

SHA-1 razbit

Oddelek: Novice / Varnost
214524 (3201) gothmorg
»

Zgostitveni algoritem SHA-0 razbit

Oddelek: Novice / Varnost
253117 (3117) darkolord

Več podobnih tem