Názory k článku ENT - Program pro testování sekvencí pseudonáhodných čísel

takze tento clanok je rovnako nahodny ako rand() ? :))) To ma potom rand() poriadne sklamal. To fakt uz radsej mozem do mojho programu krmit newsfeed z root (tecka) cz :)))

Tusim v modernich Intelech je nejaky generator nahodnych cislic odvisly od zahrivani CPU a podobnych blbosti - pouzij ten :D Mozna i nekdo napsal do linuxu podporu.

Existuje, funguje, je podporovany. Zde je recenze http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf a tady podpurne utility http://sourceforge.net/projects/gkernel. Podpora je primo v kernelu (modul i810_rng ve 2.4 a hw_random ve 2.6).

Nepouziva se primo, ale pres specialniho demona se vystup z hw generatoru cpe do /dev/random jako zdroj entropie.

Jedina nevyhoda je, ze je trosku pomalejsi.

Entropy = 7.999390 bits per byte.

Optimum compression would reduce the size
of this 312690 byte file by 0 percent.

Chi square distribution for 312690 samples is 264.33, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.6724 (127.5 = random).
Monte Carlo value for Pi is 3.138060059 (error 0.11 percent).
Serial correlation coefficient is -0.000603 (totally uncorrelated = 0.0).

Staci shitova integrovana zvukovka s pripojenym mikrofonem a cat /dev/dsp udela stejnou praci ;-)

s timhle jsem si zkousel hrat, mam tu jeste nekde zdrojaky. nefunguje to spolehlive. z te zvukovky se musi brat malo bitu a pote je trochu prechroustat md5, aby se dala ta data pouzit. a to je pomale a narocne a zere to vykon procesoru. a na to, abych si do te zvukovky zapojil sumovou diodu jsem trochu moc liny. :-)

kdyztak sumitka se delala pro egg project, http://noosphere.princeton.edu/

ehm, preco by mal byt ten clanok rovnako nahodny ako rand() ? dava vam rand() take vysledky?

autor pise "Článek na 99,99 % není náhodný shluk písmen, což mě potěšilo...:-)"

Jasně že dává. Já už root.cz normálně ani nečtu, stačí mi rand() z mého stroje. Je to mnohem lepší počteníčko a bez slov typu "podezředlá"!

velice pekne :-)

Nemate nekdo nakou serii dat z online casina ?
Bylo by docela zajimave project to ENTem.
Tipuju ze vetsina programatoru je lina a pouziva klasickej rand() a to by se melo projevit na mene nahodnych vysledcich. Otazka ovsem je jestli by se dalo pouzit na predikci vysledku.

Tady bych si dovolil tipnout ze tam ani moc rand() nebude. Nikdy jsem teda on-line kasino nehral, ale myslim ze cisla budou tezce ovlivnovana dle aktualnich sazek, podobne jako je to u vyhernich automatu.

Nerozumiem preco sa autor stazuje ze mu chyba test suvislosti susednych cisel a odstavec nadtym je o tomto teste. Alebo som nieco nepochopil?

chybicka: v predposlednom odstavci je namiesto ENT, ELF.

Diky za nalezeni chyb. Ze pisu o chybejicim testu serialni korelace, to je kazdopadne chyba, za niz se omlouvam. Moc nechybelo a misto ENTa tam byl HOBIT :-)

Udelal uz nekdy nekdo realny exploit ci zneuziti cehokoli jen na zaklade toho ze nahodne cislo nebylo dostatecne nahodne? nebo jde spis o bouri ve sklenici vody protoze i to nejmin nahodny je furt tezky na bruteforce uhodnuti...?

O exploitech na nekvalitní rand() nevím, ale
třeba simulace Monte Carlo mohou nekvalitním
generátorem trpět.

No, uz jednou takhle nekdop udelal exploit na casino ... nejake casino aby dokazalo jak "je jejich software ferovy" tak zverejnilo kus zdrojaku, kde bylo videt, jak se nahodne cislo generuje.
Jenze melo to jednu chybku - byl to 32bitovy pseudonahodny jednoduchy generator (standardni random() v delphi). Dalsi problem byl v tom, se se seedoval pred kazdym rozdanim karet a zdrojem seedu je tam pocet milisekund od zacatku dne .... cimz se pocet moznych random hodnot seedu zuzil pry asi na 200000 (je tu nejaka odlisnost v casu mezi serverem a klientem a tak, uz si nepamatuju kolik seedu to bylo, ale raqdove o dost min nez 2^32 ...)

For byl v tom, ze podle prvnich peti liznutych karet slo zjistit ktery z tech 200000 seedu na serveru je a jakych dalsich 5 karet mi server da, takze clovek pak vedel ktery karty si ma vymenit a jestli vyhraje - kdyz jo, tak zvednu sazku ....

Ale je fakt, ze tam byl ten bug se seedem, bez nej by bylo treba prohledavat 2^32 hodnot, coz by bylo o dost horsi .... vicemene nepouzitelny...

Napr. nmap dokaze vyuzit predikovatelne generovanie IPID na blind zombie scan (option -sI). Najjednoduchsie je, ked sa IPID zvacsuje postupne pricitanim nejakej konstanty, napr. 1000 - (broken) little-endian incremental (toto typicky robia Win95, Win98). Keby sa na to pouzil linearny kongruencny generator (LCG), ako je napr. funkcia rand(), tak by sa z dvoch ziskanych hodnot IPID dali vypocitat dalsie, takze by to neposkytovalo o nic vacsiu bezpecnost nez pricitanie konstanty.

Pri SSL/TLS by pouzitie predikovatelneho generatora ako napr. LCG umoznovalo odpocuvat a desifrovat spojenie.

kdyby...kdyby...

ptal jsem se jestli to jde zneuzit, zda se ze ne, tudiz mi generovani vic nahodnych nez normalne nahodnych cisel pripadne jako ztrata casu.

ja chapu ze kazdy chce mit to nej (prodam kilo entropie z me disertace) ale neni lepsi spokojit se s tim co je?

Jie

O exploitech nevím, ale při numerických simulacích je špatný generátor katastrofa, nehledě na to, že periodu klasického rand()u vyčerpáte, než stačíte říct f*ck, takže nedostáváte náhodná čísla, ale dokola pořád tutéž posloupnost.

No teraz som si neni isty, ci rozumiem otazke..."viac nahodne nez normalne nahodne" = ?

Inak s tym nmapom to naozaj funguje, staci si na nete najst nejaky vhodny zombie stroj (cf. http://www.insecure.org/nmap/idlescan.html).

Nahodnost sa skuma kvoli tomu, aby sa nepouzili blbe generatory na nevhodnych miestach, potom by sme uz nemali "kdyby", ale riadny pruser ;-)

Len maly priklad: V praci http://eprint.iacr.org/2003/052.pdf sa popisuje utok na SSL/TLS pomocou postrannych kanalov zalozenych na tom, ze sifrovanie RSA rozlicnymi klucmi v urcitych implementaciach trva rozlicne dlhu dobu a teda je mozne invertovat RSA. Tato praca nema sice malo spolocne s (pseudo)nahodnymi generatormi (PRNG), ale pouzitie zleho generatoru ma podobny dopad: ak sa da nejak z postrannych kanalov uhadnut interny stav PRNG, utocnik uz vie generovat rovnake pseudonahodne postupnosti a rekonstruovat vsetky operacie, kde takto vygenerovane hodnoty vstupuju. Nemusi byt ani schopny uhadnut interny stav, ak dokaze napr. z casti postupnosti vypocitat, ze dalsie vygenerovane cislo bude lezat v nejakom hodne obmedzenom rozsahu.

Inak povedane, ak utocnik dokaze aspon z casti predpovedat vystup PRNG, dokaze obmedzit prehladavany priestor. Ak ho dokaze obmedzit dostatocne, tak zrazu brute-force v obmedzenom priestore moze za nejaky rozumny cas dat vysledok (napr. tajnu hodnotu, kluc, atd.).

Jo, ja :-). Bylo to tak, ze na jednom webu zverejnovali data, ale jen cast a oproti registraci. Kdyz se clovek zaregistroval (zadal mail a heslo), vytvorili mu ucet s ID a heslem a dali mu vedet na mail (ten zadany). To ID bylo generovano "nahodne". Ja jsem si nechal zaregistrovat tri maily a z tech tri ID jsem byl schopny urcit dalsi a dalsi. Takze jsem si pak z jejich WEB formulare nechal zaregistrovat jednu mailovou adresu a nasledne X neexistujicich adres (kde X >> 100 :-)). Na tu prvni existujici mi prislo ID a ja jsem z toho byl schopen urcit i ty dalsi, takze jsem nepotreboval, aby mi doslo tech X mailu (samozrejme nikam nedosly, protoze jsem si ty adresy vymyslel, ale ucty s danym heslem uz byly vytvoreny a ja jsem byl schopen odvodit prislusna ID).
Je to legracka, samozrejme jsem si mohl zaregistrovat X mailovych adres, ale tohle bylo (pri danem poctu registraci) mnohem rychlejsi a vyhodnejsi :-).
Btw. slo o dokumentaci, kterou poskytovali v omezene mire! Clovek si mohl vybrat dokumenty, ktere chtel, ale mohl si stahnout pouze urcity pocet dokumentu. No a ja jsem chtel vsechny :-).

Skusal som to na Linuxe (2.4.18, glibc 2.3.4) aj na pod Cygwinom a vsade som dostal uplne iny vysledok ako je popisovany v clanku (oba testy 500000 resp 500001 bytov):

-pod Linuxom (500000 krat rand()%256, niektore implementacie rand() maju dolne bity menej nahodne, ale podla manualu v zmienenej glibc by to malo vyjst rovnako ked sa beru horne a dolne bity):
Entropy = 7.999610 bits per byte.

Optimum compression would reduce the size
of this 500000 byte file by 0 percent.

Chi square distribution for 500000 samples is 270.02, and randomly
would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bytes is 127.4948 (127.5 = random).
Monte Carlo value for Pi is 3.134604538 (error 0.22 percent).
Serial correlation coefficient is -0.000333 (totally uncorrelated = 0.0).

-pod Cygwin (500001 krat perlom print pack("C", int(rand()*256))):
Entropy = 7.999630 bits per byte.

Optimum compression would reduce the size
of this 500001 byte file by 0 percent.

Chi square distribution for 500001 samples is 256.14, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.5045 (127.5 = random).
Monte Carlo value for Pi is 3.137628551 (error 0.13 percent).
Serial correlation coefficient is -0.000694 (totally uncorrelated = 0.0).

Pokial viem, implementacia rand() je linearny kongruencny generator (LCG). V pravdepodobnosti a statistike som sice celkom lavy, ale ak sa dobre pamatam, tak hodnoty vygenerovane LCG sa rozdelenim blizia uniformnemu rozdeleniu a v tomto zmysle by mali mat celkom dobre statisticke vlastnosti, v skutocnosti jediny problem LCG je, ze su z niekolkych hodnot predikovatelne, teda nie su vhodne ako kryptograficke RNG.

Stala sa teda niekedy zasadna zmena implementacie rand() v glibc alebo preco som dostal ine vysledky?

Pozn. pre autora: mozno by sa hodilo este zmienit diehard testy, celkom by ma zaujimal nejaky podrobnejsi popis...

Linearni kongruencni generator je dost primitivni a dobre statisticke vlastnosti nema. Glibc pouziva jiny algoritmus (viz man rand, man random).

Viem, ze LCG je uplne primitivny. V Googli som nasiel, ze ANSI C rand() je LCG. Pozrel som sa podrobnejsie do manualu random, ale neviem nikde najst co je to "additive feedback random number generator". Je to nieco podobne ako non-linear feedback shift register?

Co znamena "mat dobre statisticke vlastnosti"? Napr. predikovatelnost generatora je dost blba vlastnost pri pouziti v kryptografickych aplikaciach, ale v inych vadit nemusi (napr. v grafike). Je aspon pravda, ze hodnoty vygenerovane LCG sa blizia k uniformnemu rozdeleniu?

Některé statistické vlasnosti se mohou projevit docela dobře i v grafice -- např. korelační: Kreslíte náhodné body v prostoru vyšší dimenze než 1 (rovina, 3d bod, bod + hodnota, bod + normála, bod + vektor, etc.) a zjistíte, že nejsou rozložené rovnoměrně (jak byste čekal), tvoří nějaké nadplochy a pod.

Uniformní LCG jsou z toho, jak fungují.

Misto spojeni "rand() funkce" bych doporucil "funkce rand()". Ale jinak clanek informacne nabity a skvely :).

O zadnem generatoru (pseudo)nahodnych cisel se nemuze rict, ze generuje realizace uniformniho rozdeleni jen proto, ze tak proste funguje. (viz Yeti)

Obecne generator produkuje vysledne hodnoty, u kterych hypoteticky predpokladame nahodnost, tj. - laicky receno - shodnost s uniformnim rozdelenim. Takovouto hypotezu muzeme pak otestovat "jakymkoli vhodnym" testem. Uspech generatoru u daneho testu sice jeste nezarucuje kvalitu, ale cim vice testy generator projde bez ztraty kyticky tim lepe.

O ENTu slysim prvne, ale dle mych zdroju je nejznamejsi baterii testu asi Marsaglia Diehard - viz http://stat.fsu.edu/pub/diehard/.

Jinak pokud bych se ja mel spolehnout na kvalitu vyslednych (pseudo)nahodnych cisel, doporucujil bych prostredi R (www.r-project.org), ktere si pro vlastni potrebu programuji sami statistici. V helpu k .Random.seed se da mimojine najit seznam prislusne literatury a zminka o nekolika vhodnych generatorech. R standardne pouziva Mersenne-Twister s uctyhodnou periodou 2^19937 - 1.

• Text neni tak docela originalni a autor neuvadi odkud cerpa. Pokud se podivate treba na http://www.fourmilab.ch/random/ tak bude hned jasnejsi, kde se v textu vzaly ty z hlediska cestiny trochu zvlastni kousky. Ale aspon to autor hezky preusporadal a trochu doplnil.
• Vzhledem k zamereni ROOTa by byvalo asi bylo na miste testnout soubor s rand() funkci na Linuxu. Coz autor zjevne neudelal a doslovne prevzal text:

  Applying this test to the output of various pseudorandom sequence generators is interesting. The low-order 8 bits returned by the standard Unix rand() function, for example, yields: Chi square distribution for 500000 samples is 0.01, and randomly would exceed this value 99.99 percent of the times.

  Podrobnosti k tematu viz kapitolu o random number generatorech v ,,Numerical recipes'' (Google). Mimo jine je tam popsana i ta stara implementace rand() -- a je to docela zabavne cteni.

• Neni tu literatura, odkazy a sirsi kontext.