mboost-dp1
Flickr - bongo vongo
Læs mere her om hvorfor problemets omfang er overdrevet.
Der er tale om mange embeddede enheder, som ikke har entropi nok, når de genererer det første primtal. Ingen websites af nogen særlig betydning ser ud til at være berørt.
Der er ikke tale om nogen svaghed i RSA. Så længe man vælger sine primtal tilfældigt er RSA stadig ikke brudt.
At de var i stand til at samle alle SSL certifikater og SSH nøgler og rent faktisk finde gengangere blandt primtallene er en lidt imponerende præstation.
I princippet er den metode ganske oplagt. Det som er imponerende er at de var i stand til at gennemføre beregningerne på tallene. Som udgangspunkt skulle man have udregnet GCD på hvert par af moduli. Og med millioner af offentlige nøgler er der mange måder at vælge et par af nøgler.
Men de fandt en genvej til at gennemføre udregningerne. Denne genvej involverede at multiplicere samtlige moduli med hinanden, og betød at de havde en mellemregning med mange millioner cifre.
Selv med genvejen ser det stadigvæk ud til at algoritmen må være kvadratisk i antal nøgler. At køre en kvadratisk algoritme med ti millioner nøgler er stadigvæk imponerende. Nå må jeg hellere kigge på artiklen for at se om de fandt en måde at eliminere den kvadratiske del af algoritmen.
At RSA ikke er sikker, hvis primtallene ikke er tilfældige er der ikke noget overraskende i. Ingen kryptering er sikker, hvis nøglen ikke er tilfældig.
DSA er faktisk endnu mere sårbar. Det kom frem dengang Debian lavede fadæsen med at fjerne alt entropi fra deres tilfældigtalsgenerator. En DSA nøgle som er genereret med gode tilfældige tal vil blive kompromitteret, hvis man blot bruger den med dårlige tilfældige tal. Så svag er RSA trods alt ikke.
Der er tale om mange embeddede enheder, som ikke har entropi nok, når de genererer det første primtal. Ingen websites af nogen særlig betydning ser ud til at være berørt.
Der er ikke tale om nogen svaghed i RSA. Så længe man vælger sine primtal tilfældigt er RSA stadig ikke brudt.
At de var i stand til at samle alle SSL certifikater og SSH nøgler og rent faktisk finde gengangere blandt primtallene er en lidt imponerende præstation.
I princippet er den metode ganske oplagt. Det som er imponerende er at de var i stand til at gennemføre beregningerne på tallene. Som udgangspunkt skulle man have udregnet GCD på hvert par af moduli. Og med millioner af offentlige nøgler er der mange måder at vælge et par af nøgler.
Men de fandt en genvej til at gennemføre udregningerne. Denne genvej involverede at multiplicere samtlige moduli med hinanden, og betød at de havde en mellemregning med mange millioner cifre.
Selv med genvejen ser det stadigvæk ud til at algoritmen må være kvadratisk i antal nøgler. At køre en kvadratisk algoritme med ti millioner nøgler er stadigvæk imponerende. Nå må jeg hellere kigge på artiklen for at se om de fandt en måde at eliminere den kvadratiske del af algoritmen.
At RSA ikke er sikker, hvis primtallene ikke er tilfældige er der ikke noget overraskende i. Ingen kryptering er sikker, hvis nøglen ikke er tilfældig.
DSA er faktisk endnu mere sårbar. Det kom frem dengang Debian lavede fadæsen med at fjerne alt entropi fra deres tilfældigtalsgenerator. En DSA nøgle som er genereret med gode tilfældige tal vil blive kompromitteret, hvis man blot bruger den med dårlige tilfældige tal. Så svag er RSA trods alt ikke.
#1
Præcis, der er intet nyt i at RSA sikkerhed kommer netop fra tilfældigheden og størrelsen af primtallende.
Derfor bør det heller ikke være svært at regne ud, at hvis tilfældigheden ikke er i orden vil sikkerheden bag RSA blive brudt.
Præcis, der er intet nyt i at RSA sikkerhed kommer netop fra tilfældigheden og størrelsen af primtallende.
Derfor bør det heller ikke være svært at regne ud, at hvis tilfældigheden ikke er i orden vil sikkerheden bag RSA blive brudt.
Det kunne jeg ikke finde i artiklen. Men de har heller ikke offentliggjort alle detaljer endnu, for at det ikke skal være for nemt at reproducere før de fleste sårbare systemer er blevet patchet.kasperd (1) skrev:Nå må jeg hellere kigge på artiklen for at se om de fandt en måde at eliminere den kvadratiske del af algoritmen.
Måske kommer svaret på om de kunne eliminere den kvadratiske del i en endelig udgave af artiklen.
Jeg overvejede om de kunne vinde noget ved at bruge Montgomery algoritmen. Men det ser ikke ud til at ret mange af beregningerne kan genbruges, da de afhænger af det specifikke modulus.
Artiklen nævner dog et punkt hvor RSA er mere sårbar end andre algoritmer.kasperd (1) skrev:DSA er faktisk endnu mere sårbar.
Med alle algoritmer er det nemt at søge efter identiske offentlige nøgler. Men hvis to legitime sites ved et uheld har identiske nøgler skal man stadig bruge den hemmelige nøgle fra et af de to sites for at kunne gennemføre et angreb.
Der hvor RSA er mere sårbar er i tilfældet hvor første primtal ikke er særligt tilfældigt, men andet primtal er mere tilfældigt.
I dette tilfælde er kollisionerne sværere at finde. Men når først man har fundet dem kan de hemmelige nøgler udregnes fra de to offentlige RSA nøgler.
Dog mener jeg stadigvæk at DSA må siges at være mere sårbar end RSA, fordi jeg synes at risikoen for at lække nøglen hver gang den bruges er et større problem. Og selvom DSA ikke umiddelbart tillader at man kombinerer to svage offentlige nøgler for at beregne den hemmelige nøgle, så er det stadig et problem hvis de svage nøgler genereres i første omgang.
Nyheden er ikke at RSA er svag hvis man bruger dårlige tilfældige tal. Nyheden er hvor tit der bruges dårlige tilfældige tal, samt at nogen har fundet en forholdsvis effektiv metode til at finde genbrugte primtal._alligned_malloc (2) skrev:Derfor bør det heller ikke være svært at regne ud, at hvis tilfældigheden ikke er i orden vil sikkerheden bag RSA blive brudt.
På baggrund af uddybelserne i ovenstående kommentarer kan vi nok konkludere at der er tale om en "EB overskrift".
M.R. (5) skrev:Igang med at skrive SRP (studieretningsprojekt) om hvorfor RSA netop er sikkert, og så kommer jeg ind på newz.dk dagen før aflevering: "RSA HAR EN STOR SVAGHED" arghhhhhhhhhhh!!!!, stress!!..
Læser artiklen, ohh nvm!
Kære ven. Hvis du skriver et studieretningsprojekt med konklusionen givet på forhånd, så har du ikke forstået hvad SRP går ud på. :-)
Tag det her som en mulighed for at føje lidt ekstra på, hvor du skriver et præmissen for din rapport muligvis kan være ændret, efter at en amerikansk kryptolog har fundet en svaghed, men at denne svaghed er offentliggjort ved udgangen af projektskrivningsforløbet og derfor ikke er inddraget i rapporten eller dens konklusion.
Til nr. 8 og 9 :
Vil I være så venlige at redegøre for hvordan SSL
laver key-exchange ?
Det er korrekt at der er nogen der ikke fatter en skid af noget som helst . Det er IKKE 'nr7' !!
https://www.google.dk/search?q=RSA+cracked&btn...
Nr.1 siger :
"Så længe man vælger sine primtal tilfældigt er RSA stadig ikke brudt" Hvordan 'vælger man' noget 'tilfældigt' ??
Forestil dig i øvrigt at du har en 64-bit krypterings-nøgle bestående af 'tilfældigt generet data' ..
Men de sidste 16 bits er alle 'NUL' ....
Hvor 'tilfældig' er den nøgle egentlig ?
Ikke mere 'tilfældig' end at alle 48 bits ER beregnet !
(Hvor mange 'tilfældige' primtal findes der i øvrigt ??)
Du har HELLER ikke fattet en skid af hvor alvorligt det her er .
Vil I være så venlige at redegøre for hvordan SSL
laver key-exchange ?
Det er korrekt at der er nogen der ikke fatter en skid af noget som helst . Det er IKKE 'nr7' !!
https://www.google.dk/search?q=RSA+cracked&btn...
Nr.1 siger :
"Så længe man vælger sine primtal tilfældigt er RSA stadig ikke brudt" Hvordan 'vælger man' noget 'tilfældigt' ??
Forestil dig i øvrigt at du har en 64-bit krypterings-nøgle bestående af 'tilfældigt generet data' ..
Men de sidste 16 bits er alle 'NUL' ....
Hvor 'tilfældig' er den nøgle egentlig ?
Ikke mere 'tilfældig' end at alle 48 bits ER beregnet !
(Hvor mange 'tilfældige' primtal findes der i øvrigt ??)
Du har HELLER ikke fattet en skid af hvor alvorligt det her er .
Adi Shamir ('S' i RSA) var i øvrigt involveret i udviklingen af GSM-krypto . Og det er vist almen viden at den 'krypto' burde dømmes for falsk markeds-føring ..
http://www.wired.com/politics/law/news/1999/12/329...
RSA har i årtier udviklet mere end tvivlsom kryptografi .
Måske er det derfor den Amerikanske Regering er så glade for dem ??
http://www.wired.com/politics/law/news/1999/12/329...
RSA har i årtier udviklet mere end tvivlsom kryptografi .
Måske er det derfor den Amerikanske Regering er så glade for dem ??
#12 + 13
Man vælger noget tilfældigt ved at vælge noget der ikke er deterministisk bestemt forinden. En (kryptografisk) PRNG med god entropi er for praktiske formåls skyld ikke-deterministisk.
Din 64-bit nøgle med 16 nuller til sidst er tilfældig hvis og kun hvis en PRNG har genereret den bit sekvens. Det er fløjtende ligegyldigt at de sidste 16 bits er 0, hvis det er umuligt at forudse hvornår PRNG'en genererer 16 nuller i træk.
Et tilfældigt primtal finder du eksempelvis ved at få en PRNG til at generere 128 tilfældige bytes. Betragt dem som et enormt stort positivt tal. Er tallet lige så læg 1 til. Undersøg probabilistisk om tallet er et primtal; hvis ikke læg 2 til. Rince and repeat.
Primtalssætningen giver et overslag på antallet af primtal med eksempelvis 290 til 300 cifre. Der er mange...
Jeg tænker på et (probabilistisk genereret) primtal på 300 cifre. Ved du hvilket det er? Hvis ikke er det vel hemmeligt.
Man vælger noget tilfældigt ved at vælge noget der ikke er deterministisk bestemt forinden. En (kryptografisk) PRNG med god entropi er for praktiske formåls skyld ikke-deterministisk.
Din 64-bit nøgle med 16 nuller til sidst er tilfældig hvis og kun hvis en PRNG har genereret den bit sekvens. Det er fløjtende ligegyldigt at de sidste 16 bits er 0, hvis det er umuligt at forudse hvornår PRNG'en genererer 16 nuller i træk.
Et tilfældigt primtal finder du eksempelvis ved at få en PRNG til at generere 128 tilfældige bytes. Betragt dem som et enormt stort positivt tal. Er tallet lige så læg 1 til. Undersøg probabilistisk om tallet er et primtal; hvis ikke læg 2 til. Rince and repeat.
Primtalssætningen giver et overslag på antallet af primtal med eksempelvis 290 til 300 cifre. Der er mange...
Jeg tænker på et (probabilistisk genereret) primtal på 300 cifre. Ved du hvilket det er? Hvis ikke er det vel hemmeligt.
RobertL (12) skrev:Du har HELLER ikke fattet en skid af hvor alvorligt det her er .
Hvad er det du ikke forstår ved at "sikkerhedsbristen" i virkeligheden skyldes lav entropi under nøglegenereringen?
Der er ikke fundet nogle fejl eller svagheder i RSA, blot en retorisk ulempe ved tilfældigt genererede nøgler... som ikke er tilfældige.
RobertL (14) skrev:Adi Shamir ('S' i RSA) var i øvrigt involveret i udviklingen af GSM-krypto . Og det er vist almen viden at den 'krypto' burde dømmes for falsk markeds-føring ..
http://www.wired.com/politics/law/news/1999/12/329...
RSA har i årtier udviklet mere end tvivlsom kryptografi .
Måske er det derfor den Amerikanske Regering er så glade for dem ??
1) Du henviser til en fuldstændig irrelevant nyhed om GSM fra 1999.
2) RSA er en algoritme, ikke et firma, din nar.
3) Obvious troll is obvious.
tachylatus (18) skrev:3) Obvious troll is obvious.
successful troll is successful ^^
men ja, mage til retard
tachylatus (18) skrev:2) RSA er en algoritme, ikke et firma, din nar.
Tal pænt, din nar.
http://en.wikipedia.org/wiki/RSA_(algorithm) skrev:The RSA algorithm was publicly described in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames, listed in the same order as on the paper.
RSA er både navnet på en krypteringsalgoritme og et firma. De tre personer som opfandt algoritmen grundlagde firmaet fire år senere. Forbogstaverne af de tre personers efternavne er blevet brugt til både navnet på algoritmen og navnet på firmaet.tachylatus (18) skrev:RSA er en algoritme, ikke et firma
Artiklen handler om algoritmen, nærmere bestemt dårlige implementationer af algoritmen. Artiklen har intet med firmaet at gøre.
Artiklen har heller intet at gøre med alle de andre ting RSA kan stå for, og som ikke er relateret til kryptologi.
Jeg mente nok at sikkerhed idag er bygget op omkring primtal. Og hvis der så blev fundet en mere præcis formel på at udregne dem, så vil det så vidt jeg kan forstå, betyde at man får problemer med at lave denne form for automatisk kryptering. Da de fleste nuværende krypterings metoder benytter sig af at det ikke er nemt at lave en primtals ligning i en formel som gør det simpelt at bryde en type sikkerhed.
Der er lavet "formler" til primtal, men de er alle noget jeg ser rimelig meget som Pi og dens genveje, som ikke udregner den korrekt, men blot kommer tæt på. De bedste primtals formler tester vidst bare stort set alle tal om de er primtalt. Ikke helt optimalt.
Der er lavet "formler" til primtal, men de er alle noget jeg ser rimelig meget som Pi og dens genveje, som ikke udregner den korrekt, men blot kommer tæt på. De bedste primtals formler tester vidst bare stort set alle tal om de er primtalt. Ikke helt optimalt.
#23
RSA bygger på, at det er let at multiplicere men svært at faktorisere. Det gælder principielt set for alle tal, men med primtal åbnes der op for nogle matematiske fiksfakserier der muliggør kryptering.
Det er tungt at faktorisere - selv hvis du har en O(1) funktion, der beregner primtal #n.
RSA bygger på, at det er let at multiplicere men svært at faktorisere. Det gælder principielt set for alle tal, men med primtal åbnes der op for nogle matematiske fiksfakserier der muliggør kryptering.
Det er tungt at faktorisere - selv hvis du har en O(1) funktion, der beregner primtal #n.
RSA er den eneste jeg kan komme i tanke om, som bruger hemmelige primtal. Hvis man kunne finde en genvej til at faktorisere, så ville RSA være brudt. Men hvis der f.eks. blev fundet en effektiv metode til at udregne det n'te primtal ville det ikke kunne bruges til at bryde RSA. Men en sådan algoritme kunne potentielt bruges til at generere RSA nøgler hurtigere.kblood (23) skrev:Da de fleste nuværende krypterings metoder benytter sig af at det ikke er nemt at lave en primtals ligning i en formel som gør det simpelt at bryde en type sikkerhed.
Mange andre public key systemer er baseret på diskrete logaritmer. Diskrete logaritmer kan f.eks. bruges over Z mod p for et vilkårligt primtal. For at bruge denne type legeme til kryptografi skal man bruge et stort primtal, men det behøver ikke være hemmeligt. Man kunne i princippet blive enige om et enkelt primtal, og så kunne alle bruge det samme primtal til deres nøgler. Diskrete logaritmer kan også bruges over elliptiske kurver og dermed kan mange af algoritmerne man tidligere har brugt over Z mod p overføres til elliptiske kurver. Men jeg må indrømme, at jeg har ikke sat mig ind i præcist hvordan elliptiske kurver hænger sammen.
Lad mig lige præcisere det en anelse.Pally (25) skrev:RSA bygger på, at det er let at multiplicere men svært at faktorisere. Det gælder principielt set for alle tal, men med primtal åbnes der op for nogle matematiske fiksfakserier der muliggør kryptering.
Det er ikke svært at faktorisere et primtal, det er faktisk meget let. Det er svært at faktorisere et sammensat tal, hvis to af de primtal der indgår som faktorer er store. Det er derfor RSA bruger produktet af to primtal. Hvis man ser på alle tal med et givent antal cifre, så er dem som er sværest at faktorisere netop dem som er produktet af to primtal med samme antal cifre.
RSA kunne stadigvæk kryptere og dekryptere selvom modulus ikke var et produkt af to primtal.
Jeg kunne lave en RSA nøgle med et enkelt primtal eller tre primtal, og når først nøglen er lavet ville software der arbejder med nøglen ikke opdage, at den ikke var lavet med et forkert antal primtal. Både signatur algoritmer og krypteringsalgoritmer baseret på RSA ville virke.
Hvis man kigger på den hemmelige nøgle ville man selvfølgelig kunne se at den ikke var lavet vha. to primtal.
Der er fundet en algoritme som i polynomiel tid kan afgøre om et tal er et primtal eller et sammensat tal. Men den algoritme kan ikke bruges til at faktorisere et sammensat tal.
Hvis jeg lavede en RSA nøgle med kun et enkelt primtal ville hvem som helst kunne se på den offentlige nøgle og se at mit n var et primtal. Og så ville den nøgle være brudt. Så en RSA nøgle med kun et enkelt primtal ville kunne brydes på kortere tid end det tog at lave nøglen.
Hvis jeg lavede en RSA nøgle med tre primtal ville der mig bekendt ikke være nogen simpel algoritme til at se forskel på denne offentlige nøgle og en ægte RSA offentlig nøgle.
Men tre primtal er ikke optimalt sikkerhedsmæssigt. I stedet for at tage tre primtal kunne jeg have taget to primtal med lidt flere cifre. Det ville give et sammensat tal som var mindre end det jeg ville have fået ud af de tre primtal, men som stadig er sværere at faktorisere fordi primfaktorerne er større.
Beviset for at man med RSA kan opløfte til den offentlige eksponent og derefter opløfte til den hemmelige eksponent og nå tilbage til det tal man startede med består af to dele.
Den første del beviser at det gælder for primiske restklasser. Den anden del beviser at det gælder, hvis input er et multiplum af det ene primtal.
Den første del af beviset gælder uanset hvilket n man bruger. Om det var et produkt af et, to eller tre primtal gør ingen forskel.
Den anden del af beviset gælder kun for tilfældet med to primtal. Men denne del af beviset er i praksis ligegyldig. Chancen for at man tilfældigvis kommer til at bruge et input, som ikke er i en primisk restklasse er det samme som chancen for at gætte en af primfaktorerne.
tachylatus (17) skrev:Hvad er det du ikke forstår ved at "sikkerhedsbristen" i virkeligheden skyldes lav entropi under nøglegenereringen?
Der er ikke fundet nogle fejl eller svagheder i RSA, blot en retorisk ulempe ved tilfældigt genererede nøgler... som ikke er tilfældige.
JEG har forstået hvad det betyder :
Nemlig at 'RSA' har sørget for at deres RNG slet ikke er så tilfældig som det ser ud til !
Og DET er der absolut INTET nyt i, de har gjort det før !
Men jeg er jo bare en 'troll', der i modsætning til alle jer andre, ikke fatter hvad 'RSA' betyder ..
tachylatus (18) skrev:RobertL (14) skrev:Adi Shamir ('S' i RSA) var i øvrigt involveret i udviklingen af GSM-krypto . Og det er vist almen viden at den 'krypto' burde dømmes for falsk markeds-føring ..
http://www.wired.com/politics/law/news/1999/12/329...
RSA har i årtier udviklet mere end tvivlsom kryptografi .
Måske er det derfor den Amerikanske Regering er så glade for dem ??
1) Du henviser til en fuldstændig irrelevant nyhed om GSM fra 1999.
2) RSA er en algoritme, ikke et firma, din nar.
3) Obvious troll is obvious.
Hvordan er det 'irrelevant' at Adi Shamir, 'S' i 'RSA',
tidligere har udviklet en algoritme hvor nøglen HELLER IKKE var så tilfældig som de prøvede at bilde os ind ??
RobertL (28) skrev:
Nemlig at 'RSA' har sørget for at deres RNG slet ikke er så tilfældig som det ser ud til !
Og DET er der absolut INTET nyt i, de har gjort det før !
RSA har ikke "sørget" for noget som helst. RSA er et firma, som specialiserer sig i sikkerhedssoftware, startet af de samme personer som udviklede RSA algoritmen.
De to ting har ikke andet med hinanden at gøre. Dette er højst sandsynligt et problem hos et tredje-parts software bibliotek.
RobertL (29) skrev:
Hvordan er det 'irrelevant' at Adi Shamir, 'S' i 'RSA',
tidligere har udviklet en algoritme hvor nøglen HELLER IKKE var så tilfældig som de prøvede at bilde os ind ??
Fordi GSM ike har noget med RSA algoritmen at gøre? Fordi det at han dengang lavede en svag algoritme, ikke betyder at der er noget grundlæggende galt med RSA.
RobertL (14) skrev:Adi Shamir ('S' i RSA) var i øvrigt involveret i udviklingen af GSM-krypto . Og det er vist almen viden at den 'krypto' burde dømmes for falsk markeds-føring ..
http://www.wired.com/politics/law/news/1999/12/329...
Hvor har du det fra at Shamir var med til at udvikle GSM kryptering (btw, vi snakker vel om A5/1?). Det eneste jeg har kunne finde om Shamir og GSM var at han med til at skrive en artikel som hed: "Real Time Cryptanalysis of A5/1 on a PC".
http://www.wired.com/politics/law/news/1999/12/329...
http://cryptome.info/0001/a51-bsw/a51-bsw.htm
https://www.schneier.com/blog/archives/2012/02/lousy_random_nu.html skrev:The cause of this is almost certainly a lousy random number generator used to create those public keys in the first place. This shouldn't come as a surprise
@#31 : Du har helt ret, Shamir var del af teamet der dechifrerede
A5/1 i real-time ..
Det ændrer dog ikke ved at der er en hel del der tyder på at RSA har et problem . I betragtning af at 7.1 millioner nøgler er en forsvindende lille del af key-space for en 1024-2048 bit RSA-nøgle
er 0.38% alarmerende højt .
Se fex
http://arstechnica.com/security/news/2010/01/768-b...
Det er næppe et software bibliotek, der er årsagen. Der er tale om embedede enheder, som ikke har den nødvendige entropi når de booter første gang og genererer deres nøgle.T-Hawk (30) skrev:Dette er højst sandsynligt et problem hos et tredje-parts software bibliotek.
Hvis software biblioteket fik tilfældige bits fra /dev/random (eller tilsvarende), så ville opstarten gå i stå og hænge indtil entropi af en eller anden vej blev tilgængelig.
Dette er noget som producenterne ikke kan tolerere, så hvis biblioteket gjorde som beskrevet, så ville producenten af hardwaren sandsynligvis få den til at læse fra /dev/urandom i stedet.
I sidste ende hænger problemet på hardwareproducenterne. De er nødt til enten at ændre deres design således at det ikke er nøvendigt at generere en nøgle ved første opstart, eller sikre at tilfældige bits er tilgængelige ved første opstart.
Der er flere måder at løse det på. De kunne sætte en hardwaretilfældigtalsgenerator i. Eller de kunne arrangere en mulighed for at gemme entropi fra boot til boot (på samme måde som nogle Linux distributioner gør), så skal de blot sikre at den gemte entropi er tilfældig fra fabrikkens side.
Der er intet som kan gøres i software for at løse problemet uden at disse hardwareproducenter tager del i at løse problemet. Og softwaren kan såmænd allerede nok til at hardwareproducenterne blot skal gøre deres del af opgaven.
Opret dig som bruger i dag
Det er gratis, og du binder dig ikke til noget.
Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.
- Forside
- ⟨
- Forum
- ⟨
- Nyheder
Gå til bund