» »

Varnost generatorjev naključnih števil

Schneier.com - Generatorji naključnih števil so zelo pomembni za varno delovanje kriptografskih aplikacij, zato je zelo pomembno, da le-ti generirajo čimbolj naključna števila. Varnost kriptografije je namreč odvisna tudi od varnosti generatorjev naključnih števil.

Žal so nekatere raziskave pokazale, da generatorji naključnih števil v nekaterih operacijskih sistemih niso dovolj zanesljivi. Raziskava Dorrendorfa, Guttermana in Pinkasa iz novembra letos je pokazala, da generator naključnih števil v Windows 2000 ni varen. Algoritem, ki se uporablja tudi za generiranje SSL ključev namreč ni bil javno objavljen, analiza pa je pokazala, da je mogoče z razmeroma preprostimi napadi predvideti prihodnje "naključne" vrednosti in s tem uganiti npr. SSL šifrirne ključe.

Seveda pa niti uporabniki operacijskega sistema Linux niso varni. Raziskava iz marca 2006 je namreč odkrila številne ranljivosti tudi v generatorju naključnih števil v tem operacijskem sistemu.

Ameriški National Institute of Standards and Technology je letos pripravil nov standard za generiranje naključnih števil. Pripravili so štiri standardizirane tehnike oz. algoritme, med katerimi se eden imenuje Dual_EC_DRBG.

Algoritem je sicer najpočasnejši med vsemi štirimi, Schneier pa poroča, da je postal standard izključno zato, ker ga je priporočila tajna služba NSA.

V začetku leta 2006 so v algoritmu sicer opazili nekaj pomanjkljivosti (algoritem proizvaja nekaj tim. pristranosti), letos pa sta na konferenci Crypto 2007 Shumow in Ferguson iz Microsofta pripravila predstavitev, v kateri se sprašujeta, če algoritem Dual_EC_DRBG ne vsebuje tim. "stranskih vrat".

Raziskovalca sta namreč ugotovila, da algoritem uporablja konstante za definiranje eliptične krivulje, ki pa so povezane z nekim naborom skritih številk. Kdor pozna, ali bi poznal te številke, bi lahko s pomočjo poznavanja prvih 32 naključno generiranih znakov algoritma Dual_EC_DRBG uganil vse naslednje "naključno" generirane znake. Povedano drugače: v algoritem je morda vrinjen "tajni ključ" napadalca, saj konstante morda predstavljajo javni ključ napadalca, skrito število pa predstavlja napadalčev tajni ključ, kar napadalcu omogoči uspešen napad na sam algoritem.

S tem bi bilo mogoče razmeroma enostavno razbiti praktično vsak kriptografski algoritem, ki bi temeljil na generatorju naključnih števil Dual_EC_DRBG.

Sicer ni znano, ali NSA oziroma kdorkoli drug v resnici poseduje omenjene skrite številke. A dejstvo, da ji bi kdo utegnil posedovati je verjetno dovolj močan argument proti uporabi tega algoritma.

Nič ni naključno, vse je dovoljeno.

48 komentarjev

Golnar ::

Tole me spominja na Dan Brown-ovo knjigo, Digitalna Trdnjava.
... če vrjameš u palčke.

edge540 ::

Naj dajo radioaktiven izotop v računalnik pa števec ki šteje razpade, na podlagi tega pa se naj''naključna števila'' naredi . Bolj random ne gre:)

gumby ::

termični šum na uporu ni dovolj random?
my brain hurts

rolihandrej ::

Ja digitalna trdnjava je zanimiva knjiga, ki govori o tem! Hvala, da si me spomnil - grem še enkrat brat. Čeprav ene trikrat sem jo že. ampak je vredna nakupa.
http://www.r00li.com

Zgodovina sprememb…

FireSnake ::

Ali je kdo zmozen potegniti vzporednico s clankom "Razbita zaščita brezžičnih Microsoftovih tipkovnic "?

Paranoja.press
" In The Sound Of Silence Time Is Standing Still" " You Have To Learn To Crawl Before You Learn To Walk"

Dark Angel ::

Prav žalostno, da novice o novi grafični kartici, ki je 1-10% hitrejšja in 30% dražja od predhodne dobijo prec 100+ komentarjev... Novica, ki je pa dejansko bolj pomembna kot se večini zdi ima pa po celem dnevu 4 komentarje :\

Kar se tiče povezanosti z novico o MS tipkovnici... dejansko so to dve čisto različne zadeve.... Tam je bistvo o slaben načinu kodiranja, ta novica pa govori o čisti osnovi za skoraj vsa današnja kodiranja.

Dobro da je lahko kdo to objavil, ne da bi ga prej kakšna tajna služba "pospravila".

sammy73 ::

Če je algoritem priporočila NSA, me prav nič ne čudi, da (morda) vsebuje stranska vrata.

[D]emon ::

Prvo pravilo varne enkripcije je, varnost naj bo popolnoma odvisna od varnosti kljuca, algoritem pa naj gre v javni pregled. Security through obscurity v koncni fazi opece avtorja. In pa posledicno tudi vse, ki tako resitev uporabljajo. Da o neustreznosti Rnd() za crypto-secure nakljucne stevilke niti ne govorim.

Trdi ::

Tudi danes obstajajo 100% zanesljivi RNG-ji, vsi pa so kombinacija več različnih faktorjev, nekateri med njimi tudi povsem fizični, npr. nihanje temperature na stotinko stopinje natančno ali pa število bitov prenešnih skozi določeno točko s strani 100000 uporabnikov.

To je popolnoma varno.
Trdota d.o.o.

[D]emon ::

Trdi, ne mesaj softverskih CSPRNGjev in fizicnih, t.j. hardverskih RNGjev.

Edit: typo..

Zgodovina sprememb…

  • spremenilo: [D]emon ()

ender ::

Pri enkripciji ne moreš uporabljati generatorja naključnih števil, ki se zanaša na neke res naključne dogodke, pač pa uporabljaš generator psevdo-naključnih števil, kjer obe strani začneta z istim seedom, in potem generirata isto sekvenco. Pri tem je pomembno to, da napadalec, ki bi prestregel tako generirana števila, iz le-teh čim težje ugotovi katero bo naslednje generirano število.
There are only two hard things in Computer Science:
cache invalidation, naming things and off-by-one errors.

Odyn ::

strictom ::

Naključni generator števil?

Generator naključnih števil?
"Violence is the last refuge of the incompetent" - Salvor Hardin

Trdi ::

Demon, od kje ti mnenje, da to mešam? Tam kjer je to res pomembno, uporabljajo fizične generatorje že zelo dolgo, tako da tega jokanja, kako softwarsko generiranje ni v redu, res ne razumem.

Vsak uporanik naj se vpraša tole. Ti je zelo pomembno, da imaš super naključna števila? Ne? Potem ne kakat. Je zelo pomembno? Potem rešitev že obstaja.
Trdota d.o.o.

Matthai ::

strictom: aj, točno: generator naključnih števil bi bilo prav.
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

[D]emon ::

Trdi, kjer je varnost res pomembna se uporablja OTP.

Matthai ::

V praksi se OTP skoraj nikjer ne uporablja, ker je preveč kompliciran za izvedbo.
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

[D]emon ::

V praksi se OTP skoraj nikjer ne uporablja, ker je preveč kompliciran za izvedbo.


OTP se je uporabljal s strani obvescevalnih agencij do nekje sredine 80. let, primarno v navezi z Vernamovim trakom za varovanje telex komunikacij. V modernejsi obliki se pa uporablja v elektronskih razlicicah. Kjer je absolutna varnost se vedno najbolj pomembna si lahko preprican da gre za OTP. (V navezi s kako drugo sifro, n.pr. straddling checkerbox, kot je bil izveden TAPIR) Ameriske obvescevalne sluzbe so med hladno vojno prestregle prioritetne komunikacije med SZ in Kanado, enkriptirane z OTP, vendar pa so Rusi za drugo sporocilo uporabili isti kljuc kot za eno od sporocil za amerisko vlado. V navezi s tem, da so americani vedeli da sporocilo vsebuje neke britanske dokumente, so lahko le-to razbili. In to samo zato ker je bil isti kljuc uporabljen vec kot enkrat.

Moderna kriptologija iz distribucijskega problema ustvari varnostni problem, OTP pa iz varnostnega problema ustvari distribucijski problem. Je pa OTP dokazano edina absolutno varna enkripcijska metoda, seveda pod pogojem da se upostevajo stiri dolocila:

- Vedno unici liste s kljuci takoj po njihovi uporabi
- Nikoli ne uporabi istega kljuca vec kot enkrat
- Ce obstaja samo najmanjsa moznost, da je kljuc ogrozen ga smatraj ogrozenega
- Takoj obvesti uporabnike kadar pride do ogrozenosti kljuca in ga ne uporabljaj

Thomas ::

Sploh ni tako zelo kompliciran, tale OTP.

Ruska šifra, takoimenovana in to rula. Vsaj med profesionalci. Amaterji pa ... kakor kdo.
Man muss immer generalisieren - Carl Jacobi

necromncr ::

"To je popolnoma varno."

Slisi (bere) se kot: 640k bo dovolj za vsakogar.. :D

Thomas ::

Bere se tako, če se bolj za silo spoznaš. Če sa pa mau le spoznaš, ti je pa to jasno.

Sej smo imeli o tem že temo, kjer smo prediskutirali stvar.

Link.
Man muss immer generalisieren - Carl Jacobi

osrdek ::

Popolne varnosti ni.
Vsak algoritem se da razbit, če le imaš zadosti računske moči.

Beernarrd ::

citAT:
paranoja.press


Ena dobrih stvari na slo-techu so ravno tovrstni sestavki. Ne maram, da mi vsi govorijo, kako super varne so zadeve, ki to niso. Ne maram, da mi kdo prodaja standard, za katerega se že vnaprej ve da je malo "muten". Ne da pa se mi brati vseh virov o računalniški varnosti, zato so mi tovrstne paranoja.press info ravno zadosti, da me spomnijo na en razmislek več.

Skratka: long live paranoja.press

Thomas ::

> Vsak algoritem se da razbit, če le imaš zadosti računske moči.

Za razbitje Ruske šifre ni dovolj nobena računska moč. Celo neskončna bi bila premajhna.

Ti pa seveda, kakor hočeš.
Man muss immer generalisieren - Carl Jacobi

[D]emon ::

> Vsak algoritem se da razbit, če le imaš zadosti računske moči.


Ob upostevanju zgoraj navedenih stirih pravil je OTP nezlomljiv. Zakaj? Zelo preprosto ..

Ker je ključ popolnoma naključen, se s poskušanjem ne da ugotoviti kateri ključ je bil uporabljen. Če bi imeli na voljo neskončno računalniških sredstev, bi lahko preverili vse možne ključe (t.im. brute force attack). Pri tem bi ugotovili da uporaba ključa XVHEU na šifriranem tekstu QJKES rezultira v (pravilnem) TODAY. Na žalost bi ugotovili tudi, da ključ FJRAB rezultira v besedi LATER, in še huje, ključ DFPAB bi proizvedel besedo NEVER. Zato ni nikoli mogoče vedeti kateri ključ je pravi. Pravzaprav se lahko iz OTP-enkriptiranega besedila da sproducirati katerokoli željeno besedo ali frazo, dokler se le uporabi "pravi" napačni ključ; za preverjanje pravilnosti rešitev ni metod. Prav zaradi tega je OTP dokazano absolutno varen sistem.


@Thomas:

Fialka _ni_ nezlomljiva. Ima ogromen keyspace, predvsem zato ker ima 30 rotorjev (cirilica), od katerih jih je v napravi naenkrat 10. In se ti alternirano rotirajo. Ampak edina nezlomljiva enkripcijska metoda je OTP. (Sicer pa bistvo enkripcije v n.pr. vojaskih operacijah ni popolnoma prepreciti prebiranje sporocil, temvec samo omogociti, da sporocila ostanejo skrita tako dolgo, da njihova prakticna uporabnost potece.)

Zgodovina sprememb…

  • spremenilo: [D]emon ()

Matthai ::

Ne, OTP je zelo enostavno izvesti. Problem nastopi v praksi pri izmenjavi ključev. Ter pri komunikaciji med velikim številom partnerjev (tukaj je prednost PKI kriptografije!). Zato je uporaba v praksi problematična.

Uporabo OTP so si lahko privoščili ruski KGBjevci na terenu v tujini. Vojska na bojnem polju ali policija, ki patruljira po Bagdadu pa OTPja ne rabi. Jim je dovolj, če sovražnik komunikacije ne more razbiti v naslednjih nekaj mesecih. Tam je pomembno, da je stvar hitra in enostavna za uporabo.
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

gumby ::

>>Za razbitje Ruske šifre ni dovolj nobena računska moč. Celo neskončna bi bila premajhna.

das par linkov na to tematiko?
my brain hurts

[D]emon ::

@Matthai,

to je samoumevno. :) Ampak tajni agenti, diplomacija ipd. so se vedno uporabljali OTP :P In vsaj pri diplomaciji je bil problem distribucije lepo resen -- diplomatska posta.

@Thomas,

zamesal tvoj bluzitis o OTP kot "Ruski sifri" s Fialko. Ignore.

Zgodovina sprememb…

  • spremenilo: [D]emon ()

[D]emon ::

Btw, ker iz nekega cudnega razloga ne morem popravljati svojih starih postov ...

Mils Electronic (www.mils.com) se vedno prodaja hardverske resitve osnovane na OTP. :D

Thomas ::

Zakaj Ruska šifra ni zlomljiva?

Denimo, da bi bila zlomljiva. Da bi našli postopek, ki bi razbil Rusko šifro. Potem bi uporabili zadevo ne za šifriranje, pač pa bi za "pad" vzeli nek zakomprimiran file in z njim zakomprimirali nek drug, ravno tako zakomprimiran, enako dolg file. Zaradi narave Ruske šifre, bi bil rezultat enako dolg file, kot sta bila prvotna.

Postopek bi lahko ponavljali poljubno dolgo časa in bi v velikost pada stlačili poljubno mnogo date.

Če bi poznali način za razbitje Ruske šife, brez hranjenja pada seveda, bi potem podatke lahko odkomprimirali.

No, to je. Razbitje Ruske šifre bi nam odprlo vrata v neskončen kompres, ki pa ni možen. Mau kasneje bom povedal zakaj.

Bom pa jaz rekel Ruska šifra, četud to škodi Demonovemu počutju.
Man muss immer generalisieren - Carl Jacobi

[D]emon ::

Ne skodi mojemu pocutju, ampak ti delas cepca iz sebe hehe (pa brez zamere ;)). OTP niso ustvarili Rusi. End of story. :D

MrStein ::

demon, Thomas govori thomaščino, ne pa slovenščino. Ko to dojameš, dobijo njegovi posti naenkrat smisel. ;)
Teštiram če delaž - umlaut dela: ä ?

[D]emon ::

@MrStein, ocitno res .. Mogoce pa govori v sifrah hehe :D

Trdi ::

Necromancer, Demon... morda smo malce offtopic, kaj pa vem. Jaz govorim (in to sem povsem jasno povedal!) o naključnih številih, torej da ta dejanska števila dejansko potrebuješ in to povsem naključna. Govorim o povsem varnih RNG-jih. Vi pa ste na ta naključna števila v zadnjih 50 postih v tej temi povsem pozabili. Torej če rečem "to je povsem varno" s tem mislim, da so generirana števila take sorte, da jih nikoli nihče ne more predvideti ali uganiti.
Trdota d.o.o.

ender ::

Trdi: problem je samo v tem, da je za določene vrste enkripcije tak RNG povsem neuporaben.
There are only two hard things in Computer Science:
cache invalidation, naming things and off-by-one errors.

Trdi ::

Zdaj pa že res postajam malce jezen. Nisem JAZ tisti, ki sem tu offtopic. Vsi tisti, ki govorite o enkripciji brez RNG elementa, ste offtopic.

Tako da, ender, to mene čisto nič ne zanima za kaj je vse RNG neuporaben. Imaš stvari, kjer potrebuješ samo in samo in samo in samo RNG. In to sem pač jat razlagal. Ne vem, zakaj vsaka RNG tema na slo-techu zabrede samo v vode enkripcije. Dejansko je tako, saj vsak post, ki ga napišem na temo RNG-jev, vsi po vrsti interpretirate v smislu enkripcije. Čeprav sem že poudaril, da ni tako.
Trdota d.o.o.

[D]emon ::

Najverjetneje zato ker racunalniki niso sposobni generirati resnicno nakljucnih stevil? So za to prevec disciplinirani hehe :D

Thomas ::

Deterministični program ni sposoben generirati "resnično random" števil.

Računalnik, naprava, pa ima komot generatorje vsaj tako random števil, kot je recimo random žrebanje lota. So to eni že 100 krat povedali, da se dobijo posebne "random kartice". Te temeljijo na razpadanju kakšne radioaktivne snovi, na lovljenju kozmičnega radijskega šuma ipd.

Kaj pomeni, da je neka sekvenca "res random"?

Nič več in nič manj kot, da je ni možno zgenerirat s krajšim programom, kot je dolga tista sekvenca. V bitih, seveda.
Man muss immer generalisieren - Carl Jacobi

[D]emon ::

@Thomas,

takoj ko za generiranje nakljucnih stevil uporabis strojno resitev (n.pr. kartice z merjenjem suma, radioaktivnega razpada, i.pd.) je generiranje nakljucnih stevil hardversko. Pa ceprav tisto kartico goni programska oprema na eeprom cipu. ;)

CaqKa ::

naslov novice pa še kar ostaja...
generator naključnih števil vs naključni generator števil...

strictom ::

Tirnice po katerih potujejo elektroni okrog jedra so "true random"? Ali me je profesorca za kemijo nategnila?
"Violence is the last refuge of the incompetent" - Salvor Hardin

Thomas ::

Ne, ni te. Te so true random. Pomeni, noben program jih ne opiše točno.
Man muss immer generalisieren - Carl Jacobi

strictom ::

Kaj pa če bi ena zadeva preskenirala kje je elektron in virnili položaj v obliki cifre?
"Violence is the last refuge of the incompetent" - Salvor Hardin

[D]emon ::

Problem pri subatomskih delcih je da se ne da istocasno vedeti njihove pozicije in njihove energije ;>

Thomas ::

> Kaj pa če bi ena zadeva preskenirala kje je elektron in virnili položaj v obliki cifre?

Ja, to bi bil odličen random generator. Sicer bi elektron tako po "generaciji števila" šel drugam, ampak je čist vseeno.

Je pa treba rečt, da vse številke tega generatorja ne bi bile enako verjetne in bi morali mau zakomplicirat. Nič bistveno hudega.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Matthai ::

Čist za intermezzo: a bi se dalo Hijackerjev USB merilec toplote spremeniti v RNG? O tem razmišljam že nekaj časa...
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

gumby ::

odvisno, kolk je netocnost meritve...
ce meri temperaturo na dve ali vec decimalk, potem bi verjetno lahko zadnjih par bitov uporabil kot random
my brain hurts

Thomas ::

To bi bil izjemno počasen RNG, ker se tazadnji bit flipa verjetno samo na sekundo, pa še to je vprašanje. Moraš pa počakat kar za precej flipov, če ne maš prevečkrat 00000000 ali 11111111 za reultat. (Pri 8 bitnem generatorju).

Bi pa po drugi strani RNG na radioaktivni razpad lahko bil tako hiter, da ga CPU ne bi mogel dohajat.
Man muss immer generalisieren - Carl Jacobi


Vredno ogleda ...

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

Odkrita resna varnostna pomankljivost v Debianovem naključnem generatorju števil za O

Oddelek: Novice / Varnost
485389 (1979) Matthai
»

Ali bo Vista SP1 vseboval stranska vrata za NSA?

Oddelek: Novice / Ostala programska oprema
332073 (2073) cryptozaver
»

Varnost generatorjev naključnih števil

Oddelek: Novice / Varnost
483672 (3671) Thomas
»

[C] generator naključnih števil

Oddelek: Programiranje
361959 (1477) Thomas

Več podobnih tem