Mystisk fejl i tilfældighedsgenerator gør det muligt at gætte primtal i RSA-algoritmen

Det er ret grimt.

Jeg vil her henvise til Wiki: http://en.wikipedia.org/wiki/Chaos_theory http://en.wikipedia.org/wiki/Mandelbrot_set

Det er en lidt gammel disciplin.

Så vidt jeg husker, kom jeg frem til, at løsningen ligger i den matrix som tal og bogstavsystemer består af. Det begrænser mulighederne og derfor opstår gentagelserne.

Primtal optræder kun i talsystemer. Alle talsystemer er abstrakte. Binær er f.eks. ikke abstrakt. (0 / 1 ....... Er / er ikke ) Geometriske størrelser er også realstørrelse og derfor ikke abstrakte.

Jeg skal se om jeg kan komme i tanke om det, men grundlæggende er der faktisk aldrig tale om en tilfældighed. Derfor kan alt forudberegnes, det er kun et spørgsmål om den talmatrix man bruger, er tilstrækkelig stor til at få det hele med.

http://dilbert.com/strips/comic/2001-10-25/

RSA's feature that allows bad number generators to affect other keys in such a public way is problematic.

Man kan ligefrem se en ældre engelsk herre sidde i en dyb stol i sin klub og udtale ovenstående.

Martin.

:D ROFL :D

Undskyld mig, men det lyder lidt abstrakt. Kan ikke se hvad det har med generering af tilfældige data til RSA nøgler at gøre.

Her et par teorier jeg umiddelbart kan komme op med:

RSA er ret nem at implementere så det er så overraskende at mange har "forsøgt sig". Det skaber desværre muligheden for at nogen har forsøgt at lave smarte implementationer (er det mon ikke nok at ét af primtallene er tilfældige, modulus bliver jo i så fald tilfældig - så snupper jeg lige et lille primtal og bruger det som en konstant. Smart!). Det kan også være at der er tale om simple programmeringsfejl. En simpel test vil jo ikke vise at algoritmen ofte vælger de samme tal - nøglen vil jo virke fint. Endeligt kan det være at nogen bevidst har skabt svage nøgler. Enten for at få andre til at bruge nøgler der er sårbare eller som en slags "eksperiment".

Der kan ligge mange sjove "historier" bag et datasæt på mio. af enheder.

Man må vel forudsætte at der er tale om en analyse af nogenlunde videnskabelig værdi. Således at dårlige nøgler, ikke optræder som en del af undersøgelsen, men at den repræsenter et nogenlunde rimeligt udvalg. Ellers er undersøgelsen jo helt uden værdi.

Undskyld mig, men det lyder lidt abstrakt. Kan ikke se hvad det har med generering af tilfældige data til RSA nøgler at gøre.

En helt central del af det matematiske grundlag for sikkerheden er at det vitterligt er tilfældige og ikke sammenfaldende primtal.

Hvis (dvs: Når) denne betingelse ikke er opfyldt, er sikkerheden meget kraftigt reduceret.

Hvorfor der er sammenfald er et godt spørgsmål og her er implementeringer skrevet af folk der ikke helt har forstået "det med småt" en meget sandsynlig forklaring.

Efter som de vil kontakte producenter, er det muligt det er router og andet embeded med kun ringe muligheder for Entropi opsamling, hvis de genere et sæt nøgler ved opstart eller det er medfødt i firmwaren.

Er der nogen der kan forklare mig hvorfor de valgte at bruge 7 mio nøgler fra "forskellige kilder" hvorfor laver de ikke deres egne? Så kunne de også teste forskellige implementeringer?

okay måske dumt spørgsmål, men jeg er ikke ekspert i RSA kryptering og husker meget lidt fra de lektioner jeg havde på studiet...(edit: lektioner om sikkerhed :p)

men hvorfor bruger man primtal?, der findes jo færre primtal end der findes andre tal - så hvis man bare har en abnorm liste af dem, kan man vel bryde koden ?... mao: Security by obscurity

Fordi real-life nøgler er meget mere interessante

Grundlæggende set fordi det er tungt arbejde at faktorisere tal.

Hvis jeg giver det et for alle praktisk formål enormt tal, flere hundrede ciffre, og fortæller dig at det er produktet af to primtal, vil det tage dig meget lang tid at finde dem, for du kan i realiteten kun prøve dig frem og da ungefähr 10% af alle tal er primtal er det mange du skal prøve, hvis produktet har 300 ciffre.

Hvis jeg giver det et for alle praktisk formål enormt tal, flere hundrede ciffre, og fortæller dig at det er produktet af to primtal, vil det tage dig meget lang tid at finde dem, for du kan i realiteten kun prøve dig frem og da ungefähr 10% af alle tal er primtal er det mange du skal prøve, hvis produktet har 300 ciffre.

jo, men der er det så at jeg ikke forstår problemet igen..

for hvis man kender tallets størrelse: 300 cifre, kan man jo lave en matrix af alle kendte primtal som er mindre en tallet og så gennemprøve alle dem som hvor produktet vil blive 300 cifre:

ek: 1.000.000 - 1 x 1000.000 - 10 x 100.000 - 100 x 10.000 - 1000 x 1.000 - 10.000 x 100 - 100.000 x 10 - 1000.000 x 1

derved kan man reducere antallet af forsøg drastisk ...

men jeg er nok ikke den første der har tænkt dette...

heh... 300 cifre er egentligt ret store tal

begynder at kunne se problemet nu :)

Det er også noget med den måde at det bag RSA virker. Hvis man ikke brugte primtal kan man ikke få RSA til at virke.

Jo, den kan faktisk godt virker bare der er mindst et primtal (det skal muligvis være større en kvadratroden af tallet) men der er ingen sikkerhed involveret.

I praksis er der ikke ret mange implementeringer der faktisk garanterer at der bruges primtal, man bruger i stedet typisk en slags sandsynlighedsbevis for at de to tal er primtal, fordi det ville tage meget lang tid at sikre at de faktisk er det.

Nu vil ethvert N>1 jo have mindst en primfaktor så der vil altid være mindst et primtal involveret ;)

Men ang. spørgsmålet "hvorfor primtal" kommer det lidt an på hvad man mener. Hvis man mener: Hvorfor kan jeg ikke bare vælge to tilfældige tal a og b og udregne n = ab i stedet for at vælge to primtal p,q og udregne n=pq? En udfordring er generering af nøglen. I nøglegenereringen skal udregnes phi(n) og hvor phi er Euler's funktion. For et n med kendt faktorisering (f.eks. n = pq) er der pæne og effektive formler for funktionen (i dette tilfæle phi(n) = (p-1)(q-1)) men det er ikke tilfældet hvis du ikke kender faktoriseringen. Så hvis du har n som n = a*b så skal du faktisk først faktorisere n (d.s. faktorisere a og b og merge faktoriseringerne) hvilket er samme sværhedsgrad som at bryde RSA.

Overskriften er vist noget misvisende. Der jo netop ikke tale om problemer i selve algoritmen men i specifikke implementeringer af algoritmen, hvilket er noget ganske andet. RSA Algoritmen siger intet om, hvordan man genererer p og q - det er blot input parametre.

Det er ikke helt let at lave noget tilfældigt i ren software, og nogle implementeringer er ret dårlige / naive på det punkt. De bedre måler på den entropi, der genereres, og fortsætter processen indtil den er tilstrækkelig høj. De bedste implementeringer er mulig i hardware, og gode HSM bokse (som dem der genererer NemID nøgleparrene) har en speciel kreds, som er designet til at udsende hvid støj, der kan bruges som seed til nøglegenerering.

Det sjove er, at de algoritmer man bruger til primtalstest (Rabin-Miller etc.) typisk også skal bruge tilfældige tal som input, så her har vi en catch 22 :-) Her er problemet imidlertid ikke så stort (et ikke-primtal slipper igennem) som ved selve nøglegeneringen (nøglen bliver svag).

Jeg har lige fået en privat email der gør opmærksom på at mange af de ramte nøgler er SSH nøgler, fordi SSHD laver sine hostkeys lige efter startup hvor der er meget begrænset mængde entropi tilgængeligt. Desuden er SSHD særligt udsat for GDC delen af angrebet, på grund af den måde OpenSSL håndterer entropi under nøglegenerering.

Som Martin Kirk er inde på, så reduceres antallet af mulighederne i matrix væsentligt, når man bruger primtal. ( hermed ikke sagt, at der ikke er andre matematiske fordele i primtal )

Det her var noget, som var meget oppe i tiden, engang i 80'erne.. Så hvorfor det kommer op nu, forstår jeg ikke rigtigt. Det er lidt som at se en gammel film.... :D

Der var dengang nationale sikkerheds agenturer som var helt oppe og ringe, det blev et politisk spørgsmål, med ballede omkring problematikken. Der var bl.a. krav fremme omkring, at man ikke måtte krypterer mere end med max 32 bit, osv.. Jeg tror oven i købet, at det holdt ved helt frem gennem 90'erne.

Det er ikke noget problem at beregne alt, det er kun et spørgsmål om man har tilstrækkelig datakraft. Det er heller ikke noget problem at beskrive et system, selv om et sådant system ikke er statisk. Så kaos og dermed muligheden for tilfældighed, findes som sådan ikke.

Det kan virke som en rent filosofisk anskuelse, men i forbindelse med RSA, er det ikke en filosofisk anskuelse.

Den alfanumeriske primtal-værdi man kan krypterer med, og fortsat have en fornuftig kommunikation i forbindelse med almindelig håndtering af PC'er, Digital Signatur, osv., er milliarder gange mindre, end den datakraft man har mulighed for at kompromitterer med. Dermed reduceres sikkerheden ganske væsentligt, da sikkerheden ligger i, at tiden for at kompromitterer vil være for stor.

For løsninger, der ligger eksternt, f.eks. i en "Sky", er der slet intet problem, der har man mulighed for at bruge alt den tid man har lyst til.

Kompleksiteten er/kan være statisk, helt uafhængig af den alfanumeriske størrelse. Det er muligt, at der er tale om nogen er kommet frem til, at der dannes et mønster som f.eks. Mandelbrot. Dermed vil der også være fornuft i at påstå, man gætter sig til at låse op for en sådan kryptering. Er der tale om, at man blot beregner sig til løsningen, er der ikke tale om gæt.

Og ja, der kan også være tale om, at man blot finder elendige løsninger. Som man tilsvarende kan beskrive har en vis statistisk spredning.

@Thomas: Hvad har du røget? ;-)

for hvis man kender tallets størrelse: 300 cifre, kan man jo lave en matrix af alle kendte primtal som er mindre en tallet og så gennemprøve alle dem som hvor produktet vil blive 300 cifre

Selvom man skulle vide (og det ved man generelt ikke) at produktet er præcis 300 cifre, så reducerer ideen kun kandidatrummet med 10% (10^301 - 10^300).

Så selv om man godt kan forestille sig en matrix af alle kandidatpar, så er det med vor tids computerkraft ikke muligt at generere den, endsige afprøve alle kandidatpar (inden universet afgår ved varmedøden, eller hvad man nu kan finde på).

For at sætte tallet 10^300 i perspektiv, så er der kun af størrelsesordenen 10^90 elementarpartikler i det observerbare univers. Tallet 10^300 er iøvrigt en omregning af 2^1024, svarende til en 1024-bits nøgle.

Blot for fuldstændighedens skyld:

Jf. primtalssætningen er antallet af primtal i mængden af tal med 300 decimale cifre væsentlig færre end 10% (det er nærmere 1 promille). Men det ændrer ikke på Poul-Henning og Lars' konklusion. Der er stadig rigtig, rigtig, rigtig mange primtal at vælge mellem.

@Peter, jeg tror Lars henviste til "tabet" af tal ved at forlange at primtallene skal vaere praecist 300 cifre lange og ikke hoejst 300 cifre og her er "tabet" rigtig 10%. I praksis regnes dog i binaert saa tabet er reelt naermere 50%, men det er stadig smaating naar udgangspunktet er 2^1024 !

Ioevrigt er det ikke korrekt som Lars skriver, at man ikke kan vaere sikker paa produktet er paa praecis 300 cifre. Nu regner man jo i praksis med binaere tal og en RSA 2048-bit noegle vil, ifoelge de fleste standarder, vaere dannet som produktet af to primtal paa praecis 1024 bit (d.s. med den oeverste, bit nr. 1023 hvis man starter fra 0 som mindst betydende, sat til 1) saaledes at produktet (modulus) faar en laengde paa 2047-2048 bit. Saa derfor kender man bitlaengden af primtallene helt praecist... men det er en ringe hjaelp da der stadig er over 2^1014 primtal af denne stoerrelse.

@Morten,

Point taken. Jeg havde stirret mig blind på Poul-Hennings "ungefähr 10%" fra indlægget d. 15/2 kl. 14.35.

OK ja det er jeg enig er forkert :)

Lige for fuldstændighedens skyld vil jeg lige nævne, at man ikke skal stirre sig blind på selve udfaldsrummet, f.eks. at der er 2^1014 primtal at tage af (af størrelsen 1024 bit). Der er i praksis langt nemmere måde at knække RSA på end den udtømmende søgning. Takket være sådanne algoritmer, især GNFS, er det lykkedes at knække RSA 768-bit (d.s. hvor hvert primtal er af størrelsen 384 bit). RSA-1024 bit må forventes brudt indenfor en dekade og nok snarere før end senere. Man bør ikke bruge mindre end RSA 1536 bit og det bedste er nok 2048-bit. Bemærk at de omtalte algoritmer fortsat kører i eksponentiel tid i bit-størrelsen, men det er eksponentiel tid med en konstant (et pænt stykke under 1) i eksponenten... en konstant der bliver med at blive mindre efterhånden som algoritmerne bliver bedre... og således udhuler sikkerheden.

Udtømmende søgning er praktisk umuligt allerede langt inden 128 bit, hvilket er grunden til at f.eks. AES-128 kan regnes for sikker (men jeg ville selv være mere komfortabel ved 256-bit!).

Tilbage i 1998 deltog jeg i et projekt hvor en af vores udviklere opdagede at måden man brugte OpenSSL på, slet ikke sikrede at der blev brugt entropi nok til generering af nøglepar. Han sendte en patch, men problemet var vist noget mere dybtliggende - der manglede en effektiv metode til at generere store mængder entropi hurtigt.

Et kuriosum - antallet af 'lovlige' skakspil er 10^120 - antallet af skak-positioner er 10^40. Vi skal altså have antallet af elementarpartikler fra 10^30 universer for at en partikel svarer til et spil.

Karsten

PS: fra skak.com

Men hvorfor skal denne generering af tilfældige tal foregå lokalt? Kunne man ikke forestille sig en cloud-baseret service, hvor man anmoder om et tilfældigt tal? Behørigt sikret o.s.v. Så kunne det bagvedliggende system benytte diverse state-of-the-art-systemer, á la systemer baseret på radioaktivt henfald, kosmisk stråling, termisk støj o.l. Det kunne evt. bygges ind i DNS- eller NTP-protokollen, som jo i forvejen er kritiske i forhold til PKI-systemer. Eller i (en særlig udgave af) SSL-protokollen, hvor der jo i forvejen udveksles tilfældige data for at autentificere enhederne mod hinanden.

@Knud: Problemet bliver her at få overført tilfældigheden hen til den maskine hvor det faktisk skal bruges. Det skal naturligvis ske sikkert (så det ikke kan opsnappes, ændres osv. undervejs) ellers ryger hele idéen. Hvordan vil du gøre det? Kryptografisk? Måske Diffie-Hellmann.... så skal klienten bare lige generere en tilfældig eksponent... kan du se problemet? :)

Det er ikke helt let at lave noget tilfældigt i ren software, og nogle implementeringer er ret dårlige / naive på det punkt. De bedre måler på den entropi, der genereres, og fortsætter processen indtil den er tilstrækkelig høj. De bedste implementeringer er mulig i hardware, og gode HSM bokse (som dem der genererer NemID nøgleparrene) har en speciel kreds, som er designet til at udsende hvid støj, der kan bruges som seed til nøglegenerering.

Mange nyere chipsets kan lave tilfældige tal (seeding fra temperaturvariationer og alt muligt andet gejl).