pada mi na pamet par stvari

cesto ti treba da kljuc eksportujes/importujes u neku drugu aplikaciju
mada ovo i nije neki argument...

dalje, gpg kljuc mozes da koristis i u drugim PKI sistemima, ne moraju nuzno svi da imaju isti PRNG
, bilo bi ne prakticno , pretpostalvjam
a i nebi sve platforme mogle da imaju isti prng

plitki argumenti, znam

Ma, ja samo pitam zašto pored postojećih funkcionalnosti nema još i ovo kao dodatna mogućnost.



Naravno da mogu. Druga je stvar osemenjivanje generatora, koje koristi neprenosive izvore entropije, ali ovde to nije potrebe jer je početna vrednost semena potpuno određena lozinkom.

kada kazem da nebi svuda mogli da budu isti, mislio sam recimo na embeded sisteme koji imaju drugacije arhitekture/manje mogucnosti (smart kartice recimo)
mada ne znam mnogo o PRNGovima

ne vidim neki ocigledan problem sada , zanimljivo

razmislim

srecni praznici Nedeljko, interesantne ideje !

lol, fail tek se sad setio

ako bi se za generisanje kljuca koristila lozinka kao seed za PRNG, svi koji iskoriste istu lozinku
bi imali isti par kljuceva

a to je nedopustivo

rezolucija kljuca, nista drugo.

za kljuc od 2048 bita uz dobar key generator rezolucija je 2048 bita
za kljuc bazira na lozinci rezolucija kljuca (koliko god imao bita) je broj kombinacija lozinki. Cak i da uzmes ceo unicode (2^16) i lozinku od 32 karaktera/simbola (a oba su nerealna) imas rezoluciju kljuca od 512 bita a to je daleko daleko manje od 2048 i sasvim sigurno u dometu zainteresovanih "faktora". U realnost lozinke ce biti u ASCI podskupu, 8 do 10 karaktera, znaci max 100¹⁰, realno oko 60-ak bita.

Tom lozinkom stitis kljuc od lokalne kradje ali sam PGP kljuc stiti poverljivi sadrzaj, kad napadas sadrzaj ti imas na raspolaganju samo cyphertext i javni kljuc, ako znas da je private key generisan na osnovu lozinke i PRNGa (cija implementacija mora biti javna da bi uopste bilo komunikacije), imas vektor za bruteforce napad. Da ne pominjem da je dovoljno jednom odraditi masivnu rainbow tabelu za sve lozinke sa parovima private/public key gde bi razbijanje bilo svedeno na upit u tabelu po javnom kljucu. Saltovanje bi ovde bilo tesko/nikako primenljivo.

Pa, na svakoj arhitekturi je moguće implementirati svaki algoritam. Mislio sam na upotrebu softvera istog proizvođača na raznim platformama. Znači, on svuda uvaljuje svoj PRNG i svoj algoritam generisanja ključa od lozinke.



Da, ako ti je lozinka perazdera, sva je verovatnoća da još neko ima takvu lozinku, ali ako ti je lozinka $wX2ipq8@/, budi siguran da je nema niko drugi.

@mmix

Generisanje RSA ključa je prilično skupa operacija. Generisanje jednog para traje i traje, tako da kad bi upotrebio sve računare ovoga sveta, ne bi generisao 10²⁰ parova, a nekmoli 10¹⁰⁰. Čak i sa lozinkom od 8 karaktera iz skupa malih i velikih slova i cifara možeš mirno da spavaš.

Takođe, to što je neko pocepao RSA širine 768 bita, ne znači da bi mu znanje algoritma koji generiše par ključeva na osnovu lozinke išta pomoglo. Veza između lozinke i para ključeva je malo zeznutija da bi pomoću toga vršio faktorizaciju.

da, ali to je nedovoljno , u poredjenju sa sansom da slucajno generisani kljuc imaju dva coveka
a i omogucilo bi enumeraciju kljuceva na osnovu lozinki,
napravis kljuceve za dictionary i pretrazujes javne key servere za njih, nacices neki ...
otvara dosta mogucnosti zarad male dobiti , ne svidja mi se :)

Ama, te ključeve treba generisati, a kod mene jedno generisanje traje po čitav minut.



Rezolucija ključa je takođe ograničena širinom semena korišćenog PRNG, tako da dobijaš rezoluciju ključa, koja je kudikamo manja od širine ključa.

nije, odredjena je i implementacionim karakteristikama CSPRNGa koji u osnovi uvek koristi vecu entropiju od one koja je neophodna za maksimalnu reozluciju kljuca, obicno tako sto ima izvor entropije koji radi tokom generisanja (u principu mislim da i nije bas lako ako ne i nemoguce napraviti CSPRNG bez toga jer ne vidim kako bi zadovoljio next-bit test jer bi iz state-a uvek znao sledeci bit). Slabost tvog pristupa se ogleda u identicnosti rezultata PRNGa cime on automatski pada na testu za CSPRNG.

U osvnovi nije vazno koliko traje generisanje jednog para kljuceva, problem je sto kljuc od 2048 ili vise bita svodis na defacto kljuc od 60-ak bitova (100¹⁰ nije 10¹⁰⁰ vec 10²⁰). Mislim da generisanje kljuca sa racunarske strane traje veoma kratko, duzina keygen procesa je verovatno (al nemoj me drzati za rec jer implementacija CSPRNG ipak nije moja specijalnost) posledica skupljanja podataka sa sistemskih izvora entropije sto nije nesto sto se moze ubrzati. Tvoj algoritam to ne sme da ima i samim tim implementacija moze da se "skrati" ako uvedes vestacke pauze. Cak i ako ubacis neki stretching u pricu tako da proces generisanja kljuca zaista potraje neko vreme (a da ne bude potpuni smor za korisnika) implementacija je javna, rainbow tabela sa 2^60 mogucih kombinacija ce biti napravljena pre ili kasnije.

Ne znam kako bih ti jos objasnio to, jedini izvor entropije je tebi lozinka, sve sto napravis ne moze biti bolje od toga.

BBS algoritam jeste kriptografski siguran, ali je spor, a ovde je baš to potrebno. Ima osobinu da se iz sekvence generisanih bitova ne može predvideti sledeći bit, odnosno da je to teško koliko i faktorizacija celih brojeva.



Da li bi mogao ovo da pojasniš?



Ovo si izvalio i ostao živ. Hajde uozbilji se. Ma, da, sad ćeš na osnovu činjenice da je početna vrednost semena iz skupa od 2⁶⁰ vrednosti da faktorišeš broj reda veličine 2¹⁰²⁴ kao da je reda veličine 2⁶⁰. Kako da ne.

Ako generisanje jednom para traje T vremena, onda za generisanje N parova treba NxT vremena. Prosto ko pasulj. Ako je NxT dovoljno veliko, bezbedan si. Ovde su i N i T veliki.

T možeš uvek dovoljno da povećaš. Recimo, da ne prihvataš prvi generisani par ključeva, nego stoti. Takav ti je algoritam. Ili da imaš brojač poziva generatora pseudoslučajnih brojeva, pa da generišeš parove ključeva dok broj poziva ne pređe milion, pa tek onda da prihvatiš poslednji generisani par ključeva.

Da, ali u nekom trenutku ce T da postane katastrofalno neupotrebljivo za primenu. Mozes ti da stavis svaki milioniti par kljuceva (to sam podrazumevao pod stretching) ali je problem sto ce tek tvoj unuk moci nesto da kriptuje kljucem za koji si ti uneo lozinku danas. Nije primenljivo u praksi, da bi bilo prihvatljivo T mora da bude dovoljno malo. A N ti je vec malo, tj relativno malo u odnosu na zaista random keyset.

I ne vidim sta sam izvalio, previse si se udubio u matematiku i ne vidis drvo od sume.

Neka je A skup svih jednoznacnih vrednosti koji odgovaraju svim mogucim lozinkama, dakle A ima appx 2⁶⁰ elemenata. Neka je f keygen koji za svako x iz A generise kljuc kx sirine n bitova (n>60) i neka je KX skup svih kx. Bez obzira koliko je n card(A) = card(KX). Ako popises sve (x, kx) parove IMAS ono sto NIKAKO ne bi smeo da imas, f^-1.

CSPNG mora da prodje tzv next-bit test. Ako imas prethodni niz bitova i znas ili ispravno pretpostavis state RNGa next-bit test kaze da sansa da pogodis sledeci broj mora biti tacno 50%. U tvom slucaju to ne prolazi jer za istu lozinku na dva sistema moras da dobijes iste kljuceve, dakle ako nemam aktivan izvor entropije (a ne smem da ga imam da bi kljuc bio isti) za isti seed znam kako ce izgledati nizovi. BBS algoritam koji pominjes se bazira na dovoljno velikim p i q, sto je seed za algoritam koji moraju biti generisani na oba sistema identicno, sto znaci da je sva informacija/entropija za taj seed sadrzana u lozinci. Samim tim ti nemas dovoljno informacija da jednoznacno generises dovoljno razlicitih velikih (p,q) parova. Cela sigurnost BBSa se bazira na tome da su p i q random izabrani veliki prime brojevi. Tebi nisu random, bazirani su na lozinci.

Pa, tako gledano, f^-1 uvek imaš. Treba "samo" da popišeš parove, kojih u ovom slučaju ima "samo" 2⁶⁰. E, sad popis se radi brzinom od 10⁵ parova u sekundi. Za to ti je potrebno tričavih par stotina hiljada godina.

Pa, jesu random, jer su zasnovani na nepoznatoj lozinci. To ti je isto. Možeš ti u svrhu inicijalizacije BBS-a da koristiš Mersenne twister. Njega ćeš inicijalizovati lozinkom. On će generisati p i q za BBS, koje nećeš moći da pogodiš, a dalje se koristi BBS. Obzirom da RSA parove generiše BBS, ti nemaš nikakve informacije o p i q koje je generisao Mersenne twister za BBS, jer je taj deo odavno uništen. Stoga predvidljivost Mersenne twister-ovih bitova na osnovu prethodnih ne igra nikakvu ulogu.

Odakle ti ta brzina uopste? Uostalom, nek je i tacno, opet je 100,000 godina na jednom kompu isto sto i 1 godina na 100,000 nodova supercompa. ;)

Cela poenta krekovanja je da od javnog kljuca dodjes do privatnog. U punoj RSA implementaciji f^-1 nije izracunljivo (jos uvek) i ne postoji baza (priv, pub) iz koje bi je izvukao jer ONA ima 2^2048 elemenata koje ne mozes sracunati u doglednom periodu. 2^60 parova(x, pub) je izvodljvio kako god da ga izmentenes. iz pub izvuces x, iz x sracunas priv, kraj price.

I nema veze kako muljas lozinku da dodjes do p i q ili random stream-a. bruteforce to resava. Sve sto ti mozes je da produzis T, a kao sto rekosmo T ima krajnju gornju granicu upotrebljivosti.

Pa, ako je T=1s na kućnom računaru (zbog upotrebljivosti nećemo terati korisnika da čeka duže od 1s u proseku), onda je T=10^-5s na superkompu, tj. superkompu treba više stotina hiljada godina da razbije takav ključ grubom silom preko isprobavanja lozinki. Kapiš sad?

Ah, da, 350k godina. Mada, morao bi da osmislis (pbss,qbss) = g(lozinka) tako da g jednoznacno, inace ces imati koliziju.

Kad tako pogledas zasto onda sad koristimo 2kbit rsa kljuceve? nek obradis i milijardu iteracija u sekundi na desktopu trebace ti 10^600 godina, ukupna kumulativna moc na ovom svetu nece moci da brutuje za iole podnosljiviji period, ne? Cemu onda to?

Pa, isti algoritam sa istim ulazom daje uvek isti izlaz. Nema kolizije.

To nije kolizija

kolizija je da postoji neka transformacija da za neko x iz A postoji y = c(x) iz A tako da je keygen(x) = keygen(c(x))

npr lozinke peramika i #22soko12 da generisu isti par (p,q) i samim tim iste kljuceve. postojanje c() drasticno smanjuje broj neophodnih iteracija pri krekovanju.

Ne smanjuje se značajno ako je c dovoljno "divlja" funkcija, a broj dopustivih semena (ovde su to parovi prostih brojeva neke širine, mada se neće sva takva semena moći generisati) mnogo veći od broja mogućih lozinki. Pri x!=y je verovatnoća od g(x)=g(y) zanemarljiva, ako je uopšte veča od nule, tako da će broj semena koja se mogu generisati biti za malo manji od broja mogućih lozinki. Poenta je da skup parova ključeva koji se mogu generisati nije mnogo manji od broja mogućih lozinki.

Sve to stoji, ali su se i najveci crypto mozgovi zeznuli kod crypto hasheva (a g() i jeste neka vrsta digesta) i za md5 i za sha1. Dovoljno je da c svuce complexity sa 60 na 40 bita i vec je neupotrebljiv.

Pa, ništa, zna se tačno koliki je period Mersenne twister-a za koju širinu semena.

Eto ti zabave za praznike

Pazi, realno posle svega ovoga mislim da bi mogao da napravis veoma dobar akademski rad na ovu temu, mozda cak i da ga objavis negde. Uz jak password policy i dobar jednoznacan BSS(p,q) = g(pass) mozda bi mogao i da napravis prakticno primenljiv sistem.


Mada, sad nesto listam temu i razmisljam. Posto je tebi jedini izvor entropije lozinka, zasto gubiti vreme sa BSS kad on nema svoj izvor entropije i deterministican je za isti seed (samim tim je i random rsa p,q deterministican). Ako vec mozes da iskoristis Mersenne Twister da generises dva velika prime-a kojim bi pokrenuo BSS, zasto odmah ne iskoristis ta dva prime-a za RSA? BSS ti ne donosi nista u tom pogledu sem uspoiravanja, zar ne (a ako je do stretcha tu je n-ti kljuc). Ili sam nesto prevideo?

Prevideo si da Mersenne twister u svom osnovnom obliku nije primenljiv na kriptografiju jer je na osnovu fiksnog broja generisanih bitova moguće rekonstruisati seme i samim tim rekonstruisati ceo postupak od početka do kraja. Dakle, pomoću javnog ključa bi tajni bio efikasno izračunljiv. BSS nema tu slabost.