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

De to hemmelige primtal, som bruges til en nøgle i public key-kryptering, er ikke altid helt tilfældige. Det kan gøre det lettere at bryde krypteringen.

Ægte tilfældighed har altid været en stor udfordring for kryptering, og nu har et internationalt forskerhold fundet frem til et potentielt sikkerhedsproblem i RSA-krypteringsalgoritmen, som netop skyldes et problem med at generere tilfældige tal. Det skriver New York Times.

RSA-algoritmen er den mest udbredte metode til såkaldt public key-kryptering, hvor parterne har både en privat og en offentlig nøgle.

Systemet regnes for at være sikkert, fordi den blandt andet giver mulighed for at sikre autentificering, altså at den, der har krypteret en besked, også er den, der påstår at være afsenderen.

Men algoritmen er afhængig af to elementer, som kan gøre den sårbar, når den implementeres i praksis.

For at generere en nøgle i RSA-kryptering skal man nemlig bruge to store tilfældige primtal. De to tal ganges sammen og bruges til at skabe den offentlige og private nøgle ud fra blandt andet en matematisk funktion, som først blev beskrevet af Leonhard Euler.

Den offentlige nøgle kan offentliggøres, så andre kan bruge den til at kryptere meddelelser, som kun kan åbnes ved hjælp af den tilhørende private nøgle.

Analyserede 7,1 mio. nøgler

Hele sikkerheden bygger på, at det kræver ekstremt meget regnekraft at forsøge at finde frem til, hvilke to store primtal, der er blevet brugt i nøglen. Hvis man kan gætte primtallene, kan man bryde krypteringen.

Forskerne analyserede 7,1 millioner offentlige nøgler fra forskellige kilder og var i stand til at gætte primtallene for knap 27.000 af dem, skriver New York Times.

Det skyldes tilsyneladende en fejl i den måde, primtallene udvælges på tilfældigt, som ikke i alle tilfælde er fuldstændig tilfældig. Forskerne har dog ikke været i stand til at indkredse, præcis hvor fejlen ligger, blot at den findes i flere implementeringer af krypteringsalgoritmen.

Algoritmen bruges også til at generere certifikater til websteder, og det betyder, at det i princippet kan lade sig gøre at finde frem til primtal, der er blevet brugt til at signere et sikkert websted og bruge den viden til at lave et falsk certifikat.

Da det kun er i visse tilfælde, cirka én ud af 500, kan man dog ikke rette et angreb mod en bestemt nøgle, men kan bruge metoden mod et stort sæt af nøgler.

Forskerne har offentliggjort deres resultater efter at have forsøgt at kontakte så mange af de 27.000 berørte som muligt, skriver New York Times.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (33)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
#2 Anonym

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.

  • 0
  • 6
#6 Morten Andersen

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.

  • 4
  • 0
#7 Anonym

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.

  • 0
  • 0
#8 Poul-Henning Kamp Blogger

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.

  • 4
  • 0
#11 Martin Kirk

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

  • 0
  • 2
#13 Poul-Henning Kamp Blogger

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.

  • 0
  • 0
#14 Martin Kirk

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...

  • 1
  • 1
#17 Poul-Henning Kamp Blogger

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.

  • 1
  • 0
#18 Morten Andersen

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.

  • 3
  • 0
#19 Gregers Mogensen

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.

  • 0
  • 0
#20 Gregers Mogensen

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).

  • 0
  • 0
#21 Poul-Henning Kamp Blogger

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.

  • 3
  • 0
#22 Anonym

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.

  • 0
  • 4
#24 Lars Lundin

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.

  • 0
  • 0
#25 Peter Lind Damkjær

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.

  • 2
  • 0
#26 Morten Andersen

@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.

  • 0
  • 0
#28 Morten Andersen

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!).

  • 0
  • 0
#29 Michael Zedeler

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.

  • 0
  • 0
#31 Knud Henrik Strømming

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.

  • 0
  • 0
#32 Morten Andersen

@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? :)

  • 0
  • 0
#33 Nikolaj Brinch Jørgensen
  • 0
  • 0
Log ind eller Opret konto for at kommentere