Kriptografski promašaj RSA modula

Svaka enkripcija se može probiti, samo je pitanje vremena. Tako da vijest nije neobična.

Do sada se vjerovalo da algoritam generira jedinstvene nasumične brojeve koji se ne ponavljaju.

Mislim da ovo traži dodatno pojašnjenje...

Kakav to algoritam na običnom računalu može generirati jedinstvene nasumične brojeve kad znamo da je svako generiranje pseudo-slučajne naravi, jer ipak se radi o diskretnim procesima, a ne o iskorištavanju fenomena kvantne mehanike ?

Brojevi koji se ne ponavljaju? to jednostavno ne može biti istina, jer da je ključ i dužine milijun bita opet postoji određena vjerojatnost da se ponovi.

Dakle nije stvar u brojevima koji se ne ponavljaju, nego da postoji vrlo mala vjerojatnost za ponavljanjem broja, tj. da netko drugi ima isti ključ kao ti.

istina je da vijest nije toliko strašna,

zapravo radi se o određenom podskupu ključeva, a to su oni koje generiraju routeri i sl. uređaji, dok su npr. ključevi web stranica uglavnom sigurni.

Nešto nije u redu s generiranjem ključeva kod ovih, nema dovoljno entropije, tj. slučajnosti, pa je vjerojatnost ponavljanja ključeva veća nego što bi trebala biti.

sve je objašnjeno ovdje:

https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs

Zapravo vijest i jest strašna jer se i do sada znalo da se teoretski uvijek može dogoditi generiranje istih ključeva, kao što ne postoji teoretska prepreka postojanju istih otisaka prstiju različitih ljudi (iako do sada nisu otkriveni), ali postotak isth ključeva koji se u stvarnosti nalaze u uporabi je daleko veći nego je itko pretpostavljao. 

Dapače, u ovom slučaju su na 6,4 milijuna ispitanih primjera nađeno nekoliko primjera s više od tisuću identičnih ključeva. 

Ja ne znam odakle ovakva potreba za umanjivanjem važnosti ovakvog kritpografskog otkrića?

Primjerice, ako imaš one "neprovaljive" brave, vjerojatnost da će ključ neke druge takve brave od istog proizvođača pasati tvojoj bravi je daleko manja od 1%, prije je negdje oko 1:1.000.000 ili manja (ovisno o tipu/veličini ključa, broju utora i rezoluciji CNC-a koji pravi ključeve). Ovdje imaš šansu da je svaki stoti korisnik RSA ključa na Internetu (a koji je dosta veliko mjesto) ima isti javni ključ kao i ti. 

Tko misli da mu je to "dovoljno dobro" i da je RSA "siguran" ima bitno različito shvaćanje sigurnosti od mene. 

To je token, istina. Nije da baš generira RSA ključ s obzirom da je RSA ključ sastavljen od dva dijela i oba su nešto duža od 6 znamenki ;)

Ali moja poanta i dalje stoji. Slika je misleading. Ispada da je taj token nesiguran što nije istina. 

RSA je siguran. To što su neki ključevi generirani od razno raznih switcheva i routera nesigurni nema veze sa RSA algoritmom i njegovom sigurnošću. 

Ovo istraživanje je dokazalo postojanje određenog broja ključeva koji se ponavljaju. Takve ključeve je jednostavno detektirati odnosno provjeriti. Siguran sam da većina velikih izdavatelja SSL certifikata već uredno provjerava CSR-ove koji su generirani nesigurnim ključevima...

Aj hebat ga sad, nesiguran je zato što im je netko provalio u sustav i vjerojatno popalio privatne ključeve. Nema veze sa originalnim člankom niti ima veze sa RSA algoritmom kao takvim. Ali ajde, eto, nesigurni su :)

Ne, ne bavim se prodajom nečeg što ima veze sa RSA enkripcijom ali eto, igrom slučaja znam podosta o temi (RSA kao algoritmu ne RSA kao firmi o kojoj btw i nemam neko dobro mišljenje). Znam i to da je jako tendecioznmo reči da je RSA nesiguran s obzirom da se radi o matematičkom problemu a ne algoritamskom. 

Ključevi nisu generirani RSA algoritmom jer RSA algoritam nema apsolutno nikakve veze sa generiranjem ključeva. RSA algoritam se bazira na već izgeneriranim ključevima. Algoritam generiranja tog ključa može biti bugovit što se i pokazalo u ovom slučaju. Logika iza svega je da je poprilično jednostavno detektirati takve ključeve i eliminirati ih. Nije ovo prvi puta da se pokazalo da je neki random number generator manjkav. Tvrditi da je RSA samim time nesiguran je u najmanju ruku tendeciozno ako ne i senzacionalistički. 

No dobro, možemo ovako dovjeka. Zapravo je povod mojeg komentara bio to što je članak napisan jutarnjolistovski. I baš mi je žao zbog toga... Kada kolegama kažem da još uvijek posječujem BOL smiju mi se. A iskreno, dolazim ovdje više manje zato da saznam kada se desi neka promjena u cjeniku T-Com-a. Na žalost, izvor kvalitetnih IT novina tražim negdje drugdje.

To istraživanje nije jutarnjolistovsko. Članak na BOL-u je. Slika je samo točka na i.

Cijelu priču možeš protumačiti kako želiš ali budi siguran da nisam ništa "bubnuo".

Možda je teško primiti kritiku? ;)

 Drago, kako možeš čitatelju site za koji radiš napisati da piše budalaštine, ima glupe komentare i sl? Malo se skuliraj i prihvati kritiku. Čini se da je čitatelj upućeniji u problematiku od tamo nekog (da i ja malo tebe vrijeđam) umišljenog novinara. Jesi li ti pročitao izvorni stručni rad koji si linkao ili si kao i obično c/p nečiju vijest u google translator i nakeljio prvu sliku koju ti je google izbacio? Čovjek ti pokušava objasniti razliku između algoritma koji generira ključeve i algoritma koji ih koristi. Očigledno ti je to teško shvatiti.

Ovaj site sve više liči ne na jutarnji nego na 24h. Senzacionalistički naslovi (pogotovo ovi nedavni u rimi), glasine, tužakanje, uveli ste i polugole komade... I onda kad vam to netko dobronamjerno kaže u lice, vrijeđate ga, brišete mu postove i na kraju banate.

P.S.

Baš me zanima koliko će dugo ovaj post ostati na forumu. Vi možete vrijeđati ali vas se ne smije ni kritizirati.

Daj da pogodim - ti znaš osnove RSA enkripcije? Da znaš osnove onda bi znao da RSA algoritam zapravo nema veze sa generiranjem ključeva, već samo za postizanje neprobojnosti postavlja uvjete koje ključevi moraju zadovoljiti.

U ovom konkretnom slučaju radi se o lošoj implementaciji algoritma koji generira ključeve koji zadovoljavaju te uvjete u konkretni uređaj, što nema direktne veze ni sa RSA algoritmom ni sa implementacijom RSA algoritma.

Primjerice DSA je po tom pitanju još osjetljiviji jer se kod DSA algoritma prilikom svakog potpisivanja generira random broj, a nalaženje dva potpisa sa istim random brojem može otkriti privatni ključ (nešto slično se dogodilo Sony-u da PS3).

  Prvi korak:

Choose two distinct prime numbers p and q.
For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test.

Ako na osnovu ove rečenice možeš smatrati da je generiranje ključeva integralni dio algoritma onda se i izjava "Korak 1: pronađi privatni ključ; Korak 2: upotrijebi ga" može smatrati probijanjem bilo kojeg algoritma.

Upravo odabir dva broja koja zadovoljavaju te uvjete je ono za što je potreban dobar random generator.

Slažem se da u praksi nije bitno koji dio procesa je kriv ukoliko postoji sigurnosni problem, ali to onda nije problem samo RSA algoritma već svoj onih kojima se sigurnost temelji na random brojevima (a tu je kao što sam i napisao DSA još osjetljiviji)!

Prvo bi sebe trebao obrazovati pa tek onda druge. Uporno tupiš jedno te isto iako ti drugi ukazuju da si u krivu.

Usput, bio sam supendiran jer sam ušao u konflikt s moderatorom ili nekim od vas umišljenih bugovaca. No davno je bilo a nisam zlopamtilo.

Svi skupa cijepidlacite oko sitnice. Istina, forumasi iznad mene su u pravu - cinjenica je da sam RSA algoritam nije pogodjen, pogodjen je proces implementacije RSA algoritma radi redundantih kljuceva. Ali za potrebe BUG foruma, sasvim je svejedno da li ce to biti nazvano greskom u RSA algoritmu, greskom u RSA enkripciji,greskom u implementaciji kljuceva ili nekako deseto. Za prosjecnog citatelja*, clanak je jasan i informativan. Za strucnjake... pa, oni i onako vjerojatno ne prate RSA bugtraq na bug forumu :)

A sto se tice pseudo-slucajnog kljuca, ja sam zadovoljan njima. Onog dana kad masina izbaci pravi slucajni kljuc, terminatori ce prohodati zemljom, a AI zlobno cerekati :)

EDIT - pod "prosjecnim citateljem" nisam mislio nista omalovazavajuce, nego citatelja koji se ne bavi profesionalno kriptografijom.

Povlacis me za jezik. Da, slika je simbolicna (kao i vecina slika vezanih uz vijesti na BOLu. Tesko je konkretnom slikom simbolizirati apstraktan pojam). Da, postoji par omanjih gresaka u clanku (vise na semantickoj razini). U osnovi se slazem sa tobom, ali i dalje mislim da je netko tko se ne bavi previse doticnom problematikom iz clanka shvatio osnovni problem o kojem je rijec, i zato stojim iza toga da clanak ima informativnu vrijednost. Bojim se da je sve ostalo offtopicarenje za ovu temu.

U pravu si - naslov je strašno "bombastičan" - "Kriptografski promašaj RSA modula". Ono - smrzneš se kad ga pročitaš. Ovo će se vjerojatno na novinarstvu kasnije uzimati kao primjer bombastičnog naslova. A ispod toga slika nekog tokena. Kako sada pogoditi o čemu se u tekstu radi samo gledanjem slikice i čitanjem naslova? Da, to zna biti problem onima kojima bi iz naslova i otvorne slike pogađali o čemu se radi... I da "volim koristiti izraz RSA jer zvučim bitno i veliko". RSA je sigurno naslov koji ti odmah doda 100.000 junika po stranici. Koji bi izraz trebao koristiti kada govorim o RSA algoritmu? Riječ "senzacionalizam" i "RSA" u jednoj rečenici - ovo se događa valjda jednom u 1000 godina. Tebe je fakat lako fascinirati, međutim u novinarski senzacionalizam se razumiješ ko Marica u kriv klinac.

Je li i naslov originalnog članka "Ron was wrong, Whit is right" senzacionalistički? Ako je zašto je, ako nije zašto nije?

Ti tvrdiš da RSA algoritam nije kompromitiran, iako su ključevi koje generira nesigurniji nego je itko ikada prije znao. Krivica za to je na generatoru slučajnih brojeva (koji je, usput, krucijalni preduvjet funkcioniranja RSA algoritma), a dupliće bi hvatao po Netu i onda ih valjda poništavao na neku foru ili tko zna što. Da se vratimo na rad:

"As was the case with the Debian OpenSSL vulnerability, we believe that publication is preferable to attempts to cover up weaknesses. There is a risk, but people desiring to exploit the current situation will have to redo our work, both the data collection and the calculation, as we have put our data under custody. We hope that people who know how to do the computation quickly will show good judgment." Meni ovo zvuči kao molba da se ne iskorištava propust, a ne kao zaključak da je tako nešto teško učiniti. Čudno ... ali, idemo dalje...

"Generation of a regular RSA modulus consists of finding two random prime numbers. This must be done in such a way that these primes were not selected by anyone else before. The probability not to regenerate a prime is commensurate with the security level if NIST's recommendation is followed to use a random seed of bit-length twice the intended security level. Clearly, this recommendation is not always followed.".

 Oh, noes - netko se ne drži preporuke, ali ni to nije bitno jer nema veze s RSA algoritmom per se. Okej, ali da vidimo što dalje kažu:

"Irrespective of the way primes are selected (additive/sieving methods or methods using fresh random bits for each attempted prime selection), a variety of obvious scenarios is conceivable where poor initial seeding may lead to mishaps, with duplicate keys a consequence if no "fresh" local entropy is used at all. If the latter is used, the outcome may be worse: for instance, a not-properly-random first choice may be prime right away (the probability that this happens is inversely proportional to the length of the prime, and thus non-negligible) and miss its chance to profit from local entropy to become unique. But local entropy may lead to a second prime that is unique, and thus a vulnerable modulus."

Pa znači li to da je zapravo vrlo teško dobiti zaista nasumični prim par? Zar to onda ne ugrožava i čitav besprijekorni RSA algoritam? Ali NE! Algoritam je okej, jedino činjenica da nema dobrih generatora za stvarno slučajan prim broj, već se ovi ponavljaju u 0,2% slučajeva.

Prihvaćam da samo generiranje tih brojeva nije dio algoritma već samo uvjet za njegovo funkcioniranje. Međutim - činjenica ostaje da je taj osnovni uvjet, makar bio van algoritma, čini algoritam ranjivim. Ali ne - faktički PRONAĐENE postojeće gomile duplića (ključeva) i problem s generiranjem prim brojeva su "totalno odvojene stvari".

RSA je okej. Zato jer tebi ide na jetra slika, morao si pročitati naslov tri puta i ego ti ne da da priznaš da si se provalio prvi puta i sada nastavljaš u istom tonu.

Ako ništa, uvijek možeš nakon stila i forme (jutarnjolistaški i bombastični) članka tražiti tipfelere u diskusiji.

Drago, vidim ironiju. Što si očekivao, da se neću spustiti na tvoj nivo?

 ...a dupliće bi hvatao po Netu i onda ih valjda poništavao na neku foru ili tko zna što...

Da, tko zna što. Ti očito ne. CRL. Go google it.

Ali suština problema se vidi iz tvog zaključka na ovaj citat iz teksta:

"Irrespective of the way primes are selected (additive/sieving methods or methods using fresh random bits for each attempted prime selection), a variety of obvious scenarios is conceivable where poor initial seeding may lead to mishaps, with duplicate keys a consequence if no "fresh" local entropy is used at all."

Ti se pitaš znaći li to da je zapravo vrlo teško dobiti zaista nasumičan prim par i zaključuješ da je to tako. Nije mi jasno kako ne vidiš da ovaj citat govori upravo suprotno i zapravo je suština problema opisana samo u toj jednoj rečenici. Poor inital seeding. Nije uopće teško dobiti skroz slučajni broj. Problem je u implementaciji algoritma za generiranje slučajnih brojeva odnosno vrlo specifično, problem je u seedanju koji se na nekim uređajima radi vrlo aljkavo. 

Ovo za krajnjeg korisnika nije od neke velike važnosti. Više je bitno administratorima i proizvođačima uređaja koji koriste takve algoritme. Osim toga, ovdje se radi o 1024 bitnim ključevima. Već neko vrijeme se oni ne preporučuju za SSL certifikate a za EV SSL certifikate je 2048 bitni i veći ključ obavezan. Čak i certifikat za BOL ima 2048 bitni javni ključ. Ali zašto ja to tebi govorim? Ti zasigurno to već znaš. Bitno da se piše o tome da je RSA modul kompromitiran i da se bliži kraj svemira.

Zašto iskrivljuješ činjenice? Ovo je retoričko pitanje, nemoj odgovarati. Imam par teorija ali vjerojatno bih potaknuo daljnju prepisku o ovoj za prosječnog posjetitelja BOLa apsolutno nevažnoj temi.