☰

» »

Izračunana uspešna kolizija nad SHA-1

Izračunana uspešna kolizija nad SHA-1

Slo-Tech - Zgostitveni algoritmi danes tvorijo osnovo varnosti na internetu. Uporabljajo se za zaščito gesel (hramba v obliki kontrolne vsote), kot pseudonaključni generator števil, pri generiranju naključnih imen datotek, za preverjanje integritete pri prenosu datotek (npr. v P2P omrežjih), za preverjanje integritete arhivskih datotek (tim. checksum), pri implementaciji digitalnega podpisa, časovnega žigosanja, overovitvi digitalnih potrdil, za digitalno podpisovanje datotek, gonilnikov ter seveda pri digitalni forenziki. Iz vsega tega je jasno, da morajo biti algoritmi za izračun kontrolnih vsot karseda varni.

To ne velja več za algoritem SHA-1.

Skupina raziskovalcev iz CWI Amsterdam in Google Research je namreč te dni objavila rezultate svoje raziskave, ki je pokazala, da je SHA-1 mogoče zlomiti tudi v praksi. Konkretno, raziskovalci so objavili dve PDF datoteki (prva in druga) z različno vsebino, a istim SHA-1 digitalnim podpisom.

Za izračun kolizije je sicer na običajnem enoprocesorskem računalniku potrebnih 110 let, a z uporabo 110 grafičnih procesorjev (GPU) je ta čas mogoče zmanjšati na eno leto. Z uporabo dodatnih GPU procesorjev pa seveda še na manj.

Podrobnosti o napadu so objavljene na spletni strani shattered.it, rešitev pa je uporaba novejših zgostitvenih algoritmov, na primer SHA-256 ali SHA-3.

Ker se SHA-1 marsikje še vedno uporablja pri HTTPS digitalnih potrdilih, brskalnik Google Chrome od različice 56 (izdana januarja 2017) spletne strani zaščitene z digitalnimi potrdili, ki za digitalno podpisovanje uporabljajo samo SHA-1 obravnava kot ne-varne. Brskalnik Firefox bo podobno funkcionalnost uvedel v bližnji prihodnosti. Na voljo je tudi orodje sha1collisiondetection, ki skuša zaznati kolizijski napad na SHA-1 v datotekah, in s katerim je mogoče preveriti integriteto datotek.

Velik problem pa predstavlja GIT, ki za preverjanje integritete podatkov na veliko uporablja SHA-1. Zato bi napadalec lahko teoretično postavil zlonamerno različico GIT skladišča, ki bi vsebovala programsko kodo z vgrajenimi stranskimi vrati, ta zlonamerna programska koda pa bi imela enako kontrolno vsoto kot neokužena različica.

18 komentarjev

čuhalev ::

Tudi za SHA-256 ali SHA-3 se lahko zgodi enako. Po teoriji.

poweroff ::

Jasno.

Bitnost algoritma je ključna beseda.

Pomembno je, kdaj se to zgodi v praksi.
sudo poweroff

vostok_1 ::

That sucks.

NSA ima cele poslopja polna GPU like procesorjev ravno za te namene.
There will be chutes!
It came from the lab.
Like tears in rain. Time to die. v_1 2012-21

GizmoX ::

Začetek obeh datotek:
%PDF-1.3
%âăĎÓ


1 0 obj
<</Width 2 0 R/Height 3 0 R/Type 4 0 R/Subtype 5 0 R/Filter 6 0 R/ColorSpace 7 0 R/Length 8 0 R/BitsPerComponent 8>>
stream
˙Ř˙ţ $SHA-1 is dead!!!!!&#8230;/ě	#9uś9&#177;ˇĆ<L&#8212;á˙ţ
Obe datoteki enako dolgi, manj kot 100 bajtov različne vsebine. Ko naj bi že en znak popolnoma spremenil izhod funkcije.
SHA-1 is dead!!!!! Long live SHA-2:)
udirač => uni. dipl. inž. rač.

poweroff ::

vostok_1 je izjavil:

NSA ima cele poslopja polna GPU like procesorjev ravno za te namene.

Ne samo NSA... 8-)
sudo poweroff

jype ::

konspirator ::

vostok_1 je izjavil:

That sucks.

NSA ima cele poslopja polna GPU like procesorjev ravno za te namene.

Niso botneti cenejši ? In imaš na milijone "mašin".
--

matijadmin ::

vostok_1 je izjavil:

That sucks.

NSA ima cele poslopja polna GPU like procesorjev ravno za te namene.


Gamerji pa so jim financirali razvoj 'komponent' za izgradnjo njihovega Christopherja. >:D :))
Vrnite nam techno!

čuhalev ::

V srednji šoli se uči o injektivnih funkcijah in tedaj je vsakomur jasno, da injektivnih funkcij iz večje domene v manjšo kodomeno ni. Velikost pomeni število elementov v množicah. To je tako, kot da bi želel razdeliti vseh 8 jabolk 7 otrokom. Vsakdo lahko pomisli, da bo tedaj en otrok dobil dve.

Ker je izhod SHA1 predstavljen iz 160 bitov, je kodomena velikosti 2^{160}, kar pomeni, če imamo v domeni 2^{160} + 1 element, potem bo problem. Torej lahko najdemo 2 datoteki, velikosti zgolj 21 bajtov, ki imata isti SHA1, kajti prostor datotek na 21 bajtih ima 2^{168} elementov.

Rešitev je enostavna, povečati kodomeno (število otrok) in upati, da otrok ne dobi dva jabolka.

Ribič ::

vostok_1 je izjavil:

NSA ima cele poslopja polna GPU like procesorjev ravno za te namene.

Imenujejo jih "The thinking machine".

Sicer pa se že več let opozarja, da SHA1 ni več varen.

Isotropic ::

jype je izjavil:


so že začeli s crackanjem ali kako?

pivmik ::

S-T novica omenja:

Za izračun kolizije je sicer na običajnem enoprocesorskem računalniku potrebnih 110 let, a z uporabo 110 grafičnih procesorjev (GPU) je ta čas mogoče zmanjšati na eno leto. Z uporabo dodatnih GPU procesorjev pa seveda še na manj.

To je rahlo netočno oz. dvoumno napisano saj, gre se za 1 grafični procesor(GPU), ne CPU:

Who is capable of mounting this attack?
This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.



čuhalev je izjavil:

V srednji šoli se uči o injektivnih funkcijah in tedaj je vsakomur jasno, da injektivnih funkcij iz večje domene v manjšo kodomeno ni. Velikost pomeni število elementov v množicah. To je tako, kot da bi želel razdeliti vseh 8 jabolk 7 otrokom. Vsakdo lahko pomisli, da bo tedaj en otrok dobil dve.

Ker je izhod SHA1 predstavljen iz 160 bitov, je kodomena velikosti 2^{160}, kar pomeni, če imamo v domeni 2^{160} + 1 element, potem bo problem. Torej lahko najdemo 2 datoteki, velikosti zgolj 21 bajtov, ki imata isti SHA1, kajti prostor datotek na 21 bajtih ima 2^{168} elementov.

Rešitev je enostavna, povečati kodomeno (število otrok) in upati, da otrok ne dobi dva jabolka.


Imaš prav v splošnem, itak, ampak v primeru SHA1 je presenetljivo to da so našli "bližnjico" da napad 100.000-krat pohitrijo - in s tem naredijo napad praktičen. Ravno take stvari naredijo zgoščevalno funkcijo varno:

How does this attack compare to the brute force one?
The SHAttered attack is 100,000 faster than the brute force attack that relies on the birthday paradox. The brute force attack would require 12,000,000 GPU years to complete, and it is therefore impractical.
LP, Gregor GRE^

Zgodovina sprememb…

  • spremenil: pivmik ()

čuhalev ::

pivmik je izjavil:


Imaš prav v splošnem, itak, ampak v primeru SHA1 je presenetljivo to da so našli "bližnjico" da napad 100.000-krat pohitrijo - in s tem naredijo napad praktičen. Ravno take stvari naredijo zgoščevalno funkcijo varno:

How does this attack compare to the brute force one?
The SHAttered attack is 100,000 faster than the brute force attack that relies on the birthday paradox. The brute force attack would require 12,000,000 GPU years to complete, and it is therefore impractical.

To je še zame presenetljivo odkritje. Lahko so uporabili injektivnost na kakšni vmesni stopnji izračuna.

vostok_1 ::

konspirator je izjavil:

vostok_1 je izjavil:

That sucks.

NSA ima cele poslopja polna GPU like procesorjev ravno za te namene.

Niso botneti cenejši ? In imaš na milijone "mašin".


Nisem strokovnjak, ampak bi skoraj rekel da niti ne več.

Ker veliko računalnikov je dandanes mobilne narave, pa še preveliko preobremenitev se relativno hitro zazna in počisti sistem.
V halah pa lahko laufajo GPUji na peak performance, optimizirani. Pa še zlo poceni so postali.
Botnete bi rekel da uporabljajo za druge namene.
Ampak kot rečeno...i'm talking out of my ass.
There will be chutes!
It came from the lab.
Like tears in rain. Time to die. v_1 2012-21

WhiteAngel ::

čuhalev je izjavil:


Rešitev je enostavna, povečati kodomeno (število otrok) in upati, da otrok ne dobi dva jabolka.


To je res, ampak bistvo zgoscevalnih funkcij je ravno to - da naredijo iz veliko podatkov njihov (majhen) podpis. Povecati podpis ni vedno smiselno, saj je ze 2^128 dovolj kombinacij za "all practical purposes" npr. za locevanje vsebine datotek med seboj.

Dobra zgoscevalna funkcija je tista, pri kateri se polovica "nakljucnih" bitov podpisa obrne za en obrnjen bit vhodnega podatka. Problem "zlomljenih" funkcij (md5, des, zdaj sha1) je, da ze zelo dobro vnaprej vemo, kateri biti vhodnega podatka bodo vplivali na podpis in zato (pre)hitro najdemo kolizijo - se pravi vhodni podatek, kakrsnega podpis iscemo.

Ve kdo, koliko imun je ostal SHA-256? Ko bo ta padel, zna imeti bitcoin nekaj tezav ;) Me cudi, da po tejle novici se ni strmoglavil spet..

DavidJ ::

WhiteAngel je izjavil:

To je res, ampak bistvo zgoscevalnih funkcij je ravno to - da naredijo iz veliko podatkov njihov (majhen) podpis. Povecati podpis ni vedno smiselno, saj je ze 2^128 dovolj kombinacij za "all practical purposes" npr. za locevanje vsebine datotek med seboj.


Drži, 128 bitov entropije je dovolj. Težava je v "paradoksu" rojstnega dne, ki pravi, da lahko kolizijo za zgoščevalne funkcijo, ki vrača n-bitov dolge izvlečke, poiščeš v času sqrt(n). Torej je dejanska entropija izvlečka za MD-5 64-bitov, SHA-1 80 bitov in SHA-256 128-bitov.

SHA-1 je tako že dejansko bila na meji, za kakšno tričrkovno agencijo; 2^80 operacij morda ni nemogoče zanje. Da se je smatrala za ne-varno pa gre zasluga mnogim napadom, ki so uspeli skonstruirat teoretično kolizijo v precej manjšem času. Ta, o kateri je govora tukaj, je terjala nekaj manj kot 2^64 operacij.
"Do, or do not. There is no 'try'. "
- Yoda ('The Empire Strikes Back')

Zgodovina sprememb…

  • spremenil: DavidJ ()

Ribič ::

Koliko pa je dejansko SHA-3 že razširjen? Ker sem ga do danes videval le v teoretskih osnovah in parih kriptografskih knjižnicah, nisem ga pa še videl uporabljenega v kakšnem popularnem programu...

lp

matijadmin ::

SHA-3 se je zapletel v gordijski vozel okoli tega, kaj je kdo sprva priporočil in, kaj o predlogih NIST-a menijo neodvisni strokovnjaki - akademiki. Možno, da tudi zato še ni množično v rabi.

Tačas ga po levi prehiteva Skein. Celo v ZFS so ga pri FreeBSD implementirali med tem.
Vrnite nam techno!

Vredno ogleda ...

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

Izračunana uspešna kolizija nad SHA-1

Oddelek: Novice / Varnost		188818 (6521) matijadmin
»

SHA1 hash - prevod

Oddelek: Programiranje		103901 (3558) darkolord
»

Izdajanje ponarejenih CA certifikatov

Oddelek: Novice / Zasebnost		337436 (5295) denial
»

SHA-1 razbit

Oddelek: Novice / Varnost		216203 (4880) gothmorg

Več podobnih tem