Nederlander vindt lek in RSA-algoritme
Een groep onderzoekers, waaronder een Nederlandse wiskundige, heeft een probleem in het RSA-algoritme ontdekt. Het gaat om de manier waarop publieke sleutels worden gegenereerd. Van de 7 miljoen gegenereerde sleutels die de onderzoekers onderzochten, bleken er 27.000 niet willekeurig te zijn gegenereerd zoals had gemoeten. Hierdoor zou iemand het geheime priemgetal kunnen achterhalen dat gebruikt wordt voor het maken van de publieke sleutel.
Het onderzoek werd uitgevoerd door cryptoloog James Hughes en de Nederlandse wiskundige Arjen Lenstra. De onderzoekers zijn van plan hun onderzoek tijdens een conferentie in augustus te presenteren. De onderzoekers wilden met hun onderzoek controleren of de sleutels inderdaad willekeurig worden gegenereerd, zoals altijd werd aangenomen.
"We ontdekten dat de meeste publieke sleutels werken zoals bedoeld. Een meer verontrustende ontdekking was dat twee op de duizend RSA moduli geen veiligheid boden", zo schrijven de onderzoekers in hun rapport.
Database
De publieke sleutels zijn inmiddels uit een publiek toegankelijke database verwijderd, om te voorkomen dat iemand de kwetsbaarheid zou misbruiken, zo meldt de New York Times. Ook zouden er maatregelen genomen om de van het internet gehaalde publieke sleutels te beschermen.
Volgens de onderzoekers zullen websites aanpassingen moeten doorvoeren om de integriteit van hun veiligheidssystemen te garanderen. Het RSA-algoritme wordt voor allerlei gevoelige online transacties en communicatie gebruikt.
De onderzoekers merken op dat het mogelijk is dat de kwetsbaarheid ook door iemand anders is ontdekt. De gebruikte methoden zijn allesbehalve complex, waardoor de onderzoekers niet geloven dat wat ze presenteren nieuw is. Met name als het gaat om inlichtingendiensten en andere groepen die in encryptie geinteresseerd zijn, aldus het rapport. Het zou mogelijk ook nieuw licht schijnen op de beslissing van het National Institute of Standards and Technology (NIST) in 1991 om DSA als digitale handtekening te gebruiken, in plaats van RSA.
Reacties (24)
Hiermee te maken? http://www.h-online.com/newsticker/news/item/Debian-package-of-OpenSSL-generates-weak-keys-735183.html
Verder zat in de jaren negentig een patent op RSA. Dat was in PGP een reden over te stappen op DH/DSS. Ondertussen is het patent op RSA verlopen en gebruikt PGP ook weer vrolijk RSA/RSA als default.
Tegenwoordig worden afzonderlijke sleutelparen gebruikt voor encryptie en ondertekening zodat de encryptie sleutel kan worden vervangen terwijl de (langere) ondertekeningssleutel hetzelfde blijft. Tenminste, zo begrijp ik het. Ook kan DSS maximaal 1024 bits zijn terwijl in PGP RSA 4096 bits mag zijn voor ondertekening.
Verder zat in de jaren negentig een patent op RSA. Dat was in PGP een reden over te stappen op DH/DSS. Ondertussen is het patent op RSA verlopen en gebruikt PGP ook weer vrolijk RSA/RSA als default.
Tegenwoordig worden afzonderlijke sleutelparen gebruikt voor encryptie en ondertekening zodat de encryptie sleutel kan worden vervangen terwijl de (langere) ondertekeningssleutel hetzelfde blijft. Tenminste, zo begrijp ik het. Ook kan DSS maximaal 1024 bits zijn terwijl in PGP RSA 4096 bits mag zijn voor ondertekening.
15-02-2012, 13:15 door
RichieB
Uitgebreide details worden gegeven in dit artikel: https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs
Ach, ze gaan er van uit dat de publiek toegankelijke database door niemand
is gecopieerd.
is gecopieerd.
15-02-2012, 13:34 door
[Account Verwijderd]
[Verwijderd]
Door pe0mot: Ongelofelijk en stom.
Heel erg lang geleden heel veel embedded geprogrammeerd en het was inderdaad een uitdaging om een random seed te vinden.
Tegenwoordig mag dat toch geen probleem meer zijn door variabelen als IP, ethernet mac, tijd, serial, etc.
Heel erg lang geleden heel veel embedded geprogrammeerd en het was inderdaad een uitdaging om een random seed te vinden.
Tegenwoordig mag dat toch geen probleem meer zijn door variabelen als IP, ethernet mac, tijd, serial, etc.
Grappig dat je zegt dat het een uitdaging was, en dan vier van de vijf 'sources' voor een random seed die je als moderne oplossing noemt op dezelfde computer totaal niet of zelden (ip) veranderen.
Iemand die twee keys op dezelfde computer genereert met ip/mac/serial als seed heeft inderdaad een probleem, ook tegenwoordig.
15-02-2012, 14:12 door
[Account Verwijderd]
[Verwijderd]
Volgens mij is er niets mis met het RSA-algoritme (de wiskunde), maar gaat het mis bij sommige implementaties (het (computer-)systeem)
15-02-2012, 17:44 door
Erik van Straten
Zelfs als je random algoritme perfect is bestaat de kans op collissions.
Als je een database vult met publiekelijk bekende public keys en eigenaars (bijv. https hostnames of PGP keys), en vervolgens willekeurige keypairs gaat genereren tot je een match hebt op een public key in je database, kun je de bijbehorende identiteit spoofen.
De kans dat je een identiteit naar keuze kunt spoofen is natuurlijk een stuk kleiner (totdat iemand public key rainbow tables maakt, maar bij 1024 bit keys heb je daar wel een flinke schijf voor nodig, om maar niet te spreken van 2048 bit keys ;)
Terzijde, een ingetrokken certificaat betekent overigens geen garantie dat een keypair niet meer gebruikt wordt (dit los van bovenstaande toevallige collisions). Bijv. Diginotar heeft destijds verschillende root certificaten uitgegeven met dezelfde public key erin, maar niet al die certificaten zijn geblacklist door de webbrowserfabrikanten. Een fout in revocation is dus dat certificaten worden gerevoked in plaats van public keys.
Als je een database vult met publiekelijk bekende public keys en eigenaars (bijv. https hostnames of PGP keys), en vervolgens willekeurige keypairs gaat genereren tot je een match hebt op een public key in je database, kun je de bijbehorende identiteit spoofen.
De kans dat je een identiteit naar keuze kunt spoofen is natuurlijk een stuk kleiner (totdat iemand public key rainbow tables maakt, maar bij 1024 bit keys heb je daar wel een flinke schijf voor nodig, om maar niet te spreken van 2048 bit keys ;)
Terzijde, een ingetrokken certificaat betekent overigens geen garantie dat een keypair niet meer gebruikt wordt (dit los van bovenstaande toevallige collisions). Bijv. Diginotar heeft destijds verschillende root certificaten uitgegeven met dezelfde public key erin, maar niet al die certificaten zijn geblacklist door de webbrowserfabrikanten. Een fout in revocation is dus dat certificaten worden gerevoked in plaats van public keys.
15-02-2012, 20:55 door
Dev_Null
So what else is new in cryptoland? Alle "gecentraliseerde" en publiekelijk openbare cryptomethodes zijn gebackdoord voor gebruik door Big Brother.
Door pe0mot:
Het gaat over een probleem dat verschillende embedded devices het zelfde certificaat afgeven.
Oftewel alle routers van XYZ hebben standaard dezelfde encryptiesleutel (omdat ze dezelfde seed gebruiken).
Door Anoniem:
Twee keer hetzelfde certificaat door het zelfde device was niet het probleem in dit artikel.Door pe0mot: Tegenwoordig mag dat toch geen probleem meer zijn door variabelen als IP, ethernet mac, tijd, serial, etc.
Iemand die twee keys op dezelfde computer genereert met ip/mac/serial als seed heeft inderdaad een probleem, ook tegenwoordig.Het gaat over een probleem dat verschillende embedded devices het zelfde certificaat afgeven.
Oftewel alle routers van XYZ hebben standaard dezelfde encryptiesleutel (omdat ze dezelfde seed gebruiken).
In de gelinkte preprint van Lenstra et.al. is er weinig over de bron/oorzaak van de slechte keys.
In het blog van Nadia Heninger et.al die blijkbaar ongeveer hetzelfde onderzoek gedaan hebben (maar net ff later met publiceren) wordt als hoofdbron van slechte keys die ze vonden een aantal soorten devices genoemd.
Hoe dan ook is het een serieus probleem als je secret key slecht gegenereerd is en dan te factoriseren valt.
Meerdere keys op een device genereren zou overigens best kunnen voorkomen :
een _heel_ veilig , want embedded, stand alone, device zonder netwerk. Alleen aangezet om een key te genereren, die dan op een usb stick (of papier) eruit gaat.
-> zelfde mac
-> zelfde (of geen) ip
-> zelfde serial
-> zelfde of vrijwel zelfde tijd (want aangezet; embedded devices starten dan vaak met begin of epoch; geen netwerk dus geen ntp).
Anyway, echte random events samplen op een computer is best lastig, en het blijkt hier in elk geval dat een aantal soorten apparatuur dat verkeerd doen.
En de door jou voorgestelde seed bronnen zijn eigenlijk van erg lage kwaliteit, met maar een _heel_ beperkte hoeveelheid entropie, die bovendien niet of weinig verandert als het device meer random getallen moet leveren.
Van de 16M mogelijkheden voor de eerste drie bytes van een mac adres zijn er maar een paar duizend in gebruik (want vendor ID). Orde 10-12 bits informatie, van de 24 bits.
IP adres levert ook behoorlijk minder dan 32 bits entropie (met name een scheve kans op een private adres)
De tijd, hooguit in 10-msec resolutie is natuurlijk ook geen platte kansverdeling over de bitlengte, maar piekt rondom "nu". Bij de key staat nogal vaak het moment van genereren erbij .
Je wilt twee random getallen van elk 512 bits genereren, dan moet je niet met een seed pool van op z'n best een paar tientallen bits aan entropie werken en denken dat je keys wel goed gaan.
Door Erik van Straten: Zelfs als je random algoritme perfect is bestaat de kans op collissions.
Als je een database vult met publiekelijk bekende public keys en eigenaars (bijv. https hostnames of PGP keys), en vervolgens willekeurige keypairs gaat genereren tot je een match hebt op een public key in je database, kun je de bijbehorende identiteit spoofen.
De kans dat je een identiteit naar keuze kunt spoofen is natuurlijk een stuk kleiner (totdat iemand public key rainbow tables maakt, maar bij 1024 bit keys heb je daar wel een flinke schijf voor nodig, om maar niet te spreken van 2048 bit keys ;)
Terzijde, een ingetrokken certificaat betekent overigens geen garantie dat een keypair niet meer gebruikt wordt (dit los van bovenstaande toevallige collisions). Bijv. Diginotar heeft destijds verschillende root certificaten uitgegeven met dezelfde public key erin, maar niet al die certificaten zijn geblacklist door de webbrowserfabrikanten. Een fout in revocation is dus dat certificaten worden gerevoked in plaats van public keys.
Als je een database vult met publiekelijk bekende public keys en eigenaars (bijv. https hostnames of PGP keys), en vervolgens willekeurige keypairs gaat genereren tot je een match hebt op een public key in je database, kun je de bijbehorende identiteit spoofen.
De kans dat je een identiteit naar keuze kunt spoofen is natuurlijk een stuk kleiner (totdat iemand public key rainbow tables maakt, maar bij 1024 bit keys heb je daar wel een flinke schijf voor nodig, om maar niet te spreken van 2048 bit keys ;)
Terzijde, een ingetrokken certificaat betekent overigens geen garantie dat een keypair niet meer gebruikt wordt (dit los van bovenstaande toevallige collisions). Bijv. Diginotar heeft destijds verschillende root certificaten uitgegeven met dezelfde public key erin, maar niet al die certificaten zijn geblacklist door de webbrowserfabrikanten. Een fout in revocation is dus dat certificaten worden gerevoked in plaats van public keys.
Klok en klepel verhaal.
De kans op collisions bij random getallen van 512 bit hoort ongeveer 1/(2^256) te zijn (birthday paradox).
(RSA 1024 vereist twee priemgetallen van 512 bit).
Mits de random generator goed was, natuurlijk.
1/2^256 is op alle praktische manieren "nul" .
Het gaat ook niet over collisions op key-id, of collision in de hash functie.
Hier blijken verschillende keys een priemgetal gemeenschappelijk te hebben !
Dat is geen collision in de betekenis zoals die normaal by cryptografie gebruikt wordt.
Waarbij dus beide keys te ontbinden zijn, en daarmee volkomen gekraakt.
Anders gezegd, het paper van Lenstra et.al presenteert "12720 1024-bit RSA keys ontbonden te hebben".
Dat, terwijl het ontbinden van één 1024 bit RSA key (die wel correct gegenereerd is) voorlopig nog buiten bereik ligt.
16-02-2012, 07:30 door
Overcome
Door Anoniem: Volgens mij is er niets mis met het RSA-algoritme (de wiskunde), maar gaat het mis bij sommige implementaties (het (computer-)systeem)
Inderdaad. Het is een zwaar misleidende titel. Kijk maar naar de abstract van het originele artikel:
We performed a sanity check of public keys collected on the web. Our main goal was to test the validity of the assumption that different random choices are made each time keys are generated. We found that the vast majority of public keys work as intended. A more disconcerting finding is that two out of every one thousand RSA moduli that we collected offer no security. Our conclusion is that the validity of the assumption is questionable and that generating keys
in the real world for "multiple-secrets" cryptosystems such as RSA is significantly riskier than for "single-secret" ones such as ElGamal or (EC)DSA which are based on Diffe-Hellman.
Het artikel gaat over "computational and randomness properties of actual public keys". Oftewel, het RSA algoritme staat nog als een huis. De implementatie van het algoritme kan mis lopen wanneer de juiste "random choices" niet worden gemaakt bij het genereren van de sleutels. Dat maakt het RSA algoritme zelf nog niet zwakker, alleen de implementaties waar het genereren van random getallen fout gaat.
Dit heeft niks met het RSA algoritme te maken maar met de gebruikte libraries voor keygenerating , trouwens... RSA wordt al lange tijd een tweede keuze na DSA
17-02-2012, 01:52 door
Erik van Straten
Door Anoniem:
(RSA 1024 vereist twee priemgetallen van 512 bit).
Mits de random generator goed was, natuurlijk.
1/2^256 is op alle praktische manieren "nul" .
Inderdaad, volgens het birthday problem is de kans ongeveer 50% dat van 23 willekeurig gekozen mensen er twee op dezelfde dag jarig zijn. Ik schrijf dan ook nergens hoe groot de kans is dat in een verzameling van n public keys er twee hetzelfde zijn, wat ik probeer aan te geven dat zo'n collision wel eens eerder zou kunnen optreden dan je denkt. Je hebt gelijk dat ik er op had moeten wijzen dat die kans dan nog steeds astronomisch klein is. Mits, inderdaad, de randomness degelijk is.Door Erik van Straten: Zelfs als je random algoritme perfect is bestaat de kans op collissions.
De kans op collisions bij random getallen van 512 bit hoort ongeveer 1/(2^256) te zijn (birthday paradox).(RSA 1024 vereist twee priemgetallen van 512 bit).
Mits de random generator goed was, natuurlijk.
1/2^256 is op alle praktische manieren "nul" .
Terug naar die randomness (waar de publicatie van Lenstra et al over gaat), daar had ik al eerder enkele nare gevoelens bij (ik heb het artikel nog onvoldoende goed gelezen, maar zag zo snel geen verklaring voor de oorzaak van de, in een aantal gevallen, gevonden slechte randomness):
(1) In http://en.wikipedia.org/wiki/RSA_%28algorithm%29 staat:
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
Dat vet gemaakte aspect lijkt mij tegenstrijdig met het eerste (en griezelig implementatie-afhankelijk), en tast de randomness aan;* For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length
(2) Als ik naar de modulus (dat is p * q) van RSA public keys kijk, bijv. die van root certificates in web browsers, dan zie ik dat de eerste (en naar ik aanneem hoogste) byte altijd 0x80 of hoger is [*]. Om dat voor elkaar te krijgen moeten p en q allebei flink groot zijn. Ook dat tast denk ik de randomness aan.
M.a.w. p en q moeten allebei "ongeveer" even groot zijn en ze moeten groot zijn.
Wat is jouw mening hierover? Zou dit een (deel van) een verklaring voor de bevindingen van Lenstra et al kunnen zijn?
[*] Firefox toont, onder het kopje "public key", netjes los van elkaar de modulus (een reeks hexadecimale getallen) en de exponent (meestal 65537 decimaal). MSIE (feitelijk de Windows certificate store, die je in kunt zien door certmgr.msc te starten) toont slechts een reeks hexadecimale getallen die begint met bijv. 30 82 01 0a 02 82 01 01 00 ad 3d ... en eindigt met bijv. 02 03 01 00 01; in dat geval begint de modulus met "ad" (de 10e byte). Op het einde zijn 02 03 zogenaamde ASN.1 "tag" en lengte bytes; hexadecimaal 01 00 01 is decimaal 65537 (de exponent).
Door Erik van Straten:
Terug naar die randomness (waar de publicatie van Lenstra et al over gaat), daar had ik al eerder enkele nare gevoelens bij (ik heb het artikel nog onvoldoende goed gelezen, maar zag zo snel geen verklaring voor de oorzaak van de, in een aantal gevallen, gevonden slechte randomness):
Door Anoniem:
(RSA 1024 vereist twee priemgetallen van 512 bit).
Mits de random generator goed was, natuurlijk.
1/2^256 is op alle praktische manieren "nul" .
Inderdaad, volgens het birthday problem is de kans ongeveer 50% dat van 23 willekeurig gekozen mensen er twee op dezelfde dag jarig zijn. Ik schrijf dan ook nergens hoe groot de kans is dat in een verzameling van n public keys er twee hetzelfde zijn, wat ik probeer aan te geven dat zo'n collision wel eens eerder zou kunnen optreden dan je denkt. Je hebt gelijk dat ik er op had moeten wijzen dat die kans dan nog steeds astronomisch klein is. Mits, inderdaad, de randomness degelijk is.Door Erik van Straten: Zelfs als je random algoritme perfect is bestaat de kans op collissions.
De kans op collisions bij random getallen van 512 bit hoort ongeveer 1/(2^256) te zijn (birthday paradox).(RSA 1024 vereist twee priemgetallen van 512 bit).
Mits de random generator goed was, natuurlijk.
1/2^256 is op alle praktische manieren "nul" .
Terug naar die randomness (waar de publicatie van Lenstra et al over gaat), daar had ik al eerder enkele nare gevoelens bij (ik heb het artikel nog onvoldoende goed gelezen, maar zag zo snel geen verklaring voor de oorzaak van de, in een aantal gevallen, gevonden slechte randomness):
(ben de anoniem die op jou reageerde, en ook wo 13:43 / wo 22:19)
In het paper van Lenstra et.al wordt ook niets gezegd over de oorzaak,of over het type devices die slechte keys genereren.
De bloglink van Nadia Heninger die ongeveer hetzelfde onderzoek gedaan heeft zegt dat in hun geval de bron telkens een 'embedded' device (zoals een router of vpn appliance was).
Je gaat dan bijna denken dat de suggestie van pe0mot om mac of serial of klok of ip als random seed te gebruiken of dergelijke bronnen met veel te weinig entropie inderdaad ergens gebruikt is.
De followup posts daar vertellen al een hoop meer :
https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs
(1) In http://en.wikipedia.org/wiki/RSA_%28algorithm%29 staat:
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
Dat vet gemaakte aspect lijkt mij tegenstrijdig met het eerste (en griezelig implementatie-afhankelijk), en tast de randomness aan;* For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length
Nee hoor. Denk even aan een wat kleiner voorbeeld :
Neem twee willekeurige getallen van vier decimale cijfers , eerste cijfer >=1 . Tussen 1000 en 9999 zitten heel veel cijfers.
Er zijn _enorm_ veel priemgetallen van 512 bit lengte. (512 bit lengte is circa 154 decimale cijfers).
Zorgen dat een vijver van getallen van 154 cijfers niet groot genoeg is omdat je wel eens dezelfde zou kunnen pikken (of ze 'in een rainbow table zetten' ) zijn niet terecht.
Priemgetallen (waar het hier om gaat) zijn ook niet zeldzaam, er zijn ongeveer x/ln(x) priemgetallen <= x .
_Echt_ meer dan genoeg om , gegeven een rng met voldoende entropie gewoon nooit dezelfde tegen te komen.
(2) Als ik naar de modulus (dat is p * q) van RSA public keys kijk, bijv. die van root certificates in web browsers, dan zie ik dat de eerste (en naar ik aanneem hoogste) byte altijd 0x80 of hoger is [*]. Om dat voor elkaar te krijgen moeten p en q allebei flink groot zijn. Ook dat tast denk ik de randomness aan.
M.a.w. p en q moeten allebei "ongeveer" even groot zijn en ze moeten groot zijn.
Wat is jouw mening hierover? Zou dit een (deel van) een verklaring voor de bevindingen van Lenstra et al kunnen zijn?
De eerste (msb) en laatste (lsb) bit van beide priemgetallen zijn altijd 1 ;-)
Dat is niet de oorzaak van de zwakke keys.
17-02-2012, 11:28 door
Erik van Straten
Door Anoniem: Er zijn _enorm_ veel priemgetallen van 512 bit lengte. (512 bit lengte is circa 154 decimale cijfers).
Zorgen dat een vijver van getallen van 154 cijfers niet groot genoeg is omdat je wel eens dezelfde zou kunnen pikken (of ze 'in een rainbow table zetten' ) zijn niet terecht.
Priemgetallen (waar het hier om gaat) zijn ook niet zeldzaam, er zijn ongeveer x/ln(x) priemgetallen <= x .
_Echt_ meer dan genoeg om , gegeven een rng met voldoende entropie gewoon nooit dezelfde tegen te komen.
Dank voor jouw antwoord!Zorgen dat een vijver van getallen van 154 cijfers niet groot genoeg is omdat je wel eens dezelfde zou kunnen pikken (of ze 'in een rainbow table zetten' ) zijn niet terecht.
Priemgetallen (waar het hier om gaat) zijn ook niet zeldzaam, er zijn ongeveer x/ln(x) priemgetallen <= x .
_Echt_ meer dan genoeg om , gegeven een rng met voldoende entropie gewoon nooit dezelfde tegen te komen.
Echter als je stong primes gaat gebruiken (http://en.wikipedia.org/wiki/Strong_prime) zijn dat er ook weer ineens minder.
Door Anoniem: De eerste (msb) en laatste (lsb) bit van beide priemgetallen zijn altijd 1 ;-)
Dat is niet de oorzaak van de zwakke keys.
lsb (b=bit) altijd 1 - vanzelfsprekend, maar msb natuurlijk niet.Dat is niet de oorzaak van de zwakke keys.
Als ik het decimale priemgetal 3 in 512 bits opschrijf, zijn dat 510 nullen gevolgd door twee enen. Daarnaast, om in een 1024 bit groot restultaat van p * q (de modulus) een msb = 1 te krijgen, terwijl p en q in 512 bits passen (nb. ik weet niet of dat een vereiste is), moet er in p en/of q meer gebeuren dan alleen msb = 1.
Hoewel je in theorie een vijver hebt van 154 decimale cijfers, zijn er verschillende redenen waardoor die vijver in de praktijk kleiner is. Wellicht is die vijver, ondanks de beperkingen, nog steeds zo groot dat, gegeven een RNG met voldoende entropie, de kans op een collision verwaarloosbaar is, maar dat soort aannames worden te vaak gedaan in de cryptografie en blijken later onjuist. Ik ben liever voorzichtig.
Door Erik van Straten:
Echter als je stong primes gaat gebruiken (http://en.wikipedia.org/wiki/Strong_prime) zijn dat er ook weer ineens minder.
Door Anoniem: Er zijn _enorm_ veel priemgetallen van 512 bit lengte. (512 bit lengte is circa 154 decimale cijfers).
Zorgen dat een vijver van getallen van 154 cijfers niet groot genoeg is omdat je wel eens dezelfde zou kunnen pikken (of ze 'in een rainbow table zetten' ) zijn niet terecht.
Priemgetallen (waar het hier om gaat) zijn ook niet zeldzaam, er zijn ongeveer x/ln(x) priemgetallen <= x .
_Echt_ meer dan genoeg om , gegeven een rng met voldoende entropie gewoon nooit dezelfde tegen te komen.
Dank voor jouw antwoord!Zorgen dat een vijver van getallen van 154 cijfers niet groot genoeg is omdat je wel eens dezelfde zou kunnen pikken (of ze 'in een rainbow table zetten' ) zijn niet terecht.
Priemgetallen (waar het hier om gaat) zijn ook niet zeldzaam, er zijn ongeveer x/ln(x) priemgetallen <= x .
_Echt_ meer dan genoeg om , gegeven een rng met voldoende entropie gewoon nooit dezelfde tegen te komen.
Echter als je stong primes gaat gebruiken (http://en.wikipedia.org/wiki/Strong_prime) zijn dat er ook weer ineens minder.
Niet zo heel veel minder, en er is geen valide argument om "Strong Primes", ondanks hun spannende naam, te gebruiken.
De wiki link naar een paper van Ron Rivest (R uit RSA) en Bob Silverman verwijst daar ook naar. Bob Silverman is ook een bekend getaltheoreticus, en post nog wel eens 'pubkeybreaker' over dit en aanverwante onderwerpen.
Door Anoniem: De eerste (msb) en laatste (lsb) bit van beide priemgetallen zijn altijd 1 ;-)
Dat is niet de oorzaak van de zwakke keys.
lsb (b=bit) altijd 1 - vanzelfsprekend, maar msb natuurlijk niet.Dat is niet de oorzaak van de zwakke keys.
Als ik het decimale priemgetal 3 in 512 bits opschrijf, zijn dat 510 nullen gevolgd door twee enen. Daarnaast, om in een 1024 bit groot restultaat van p * q (de modulus) een msb = 1 te krijgen, terwijl p en q in 512 bits passen (nb. ik weet niet of dat een vereiste is), moet er in p en/of q meer gebeuren dan alleen msb = 1.
Als je geen fixed-length veld gebruikt, kun je de lengte van getallen niet uitdrukken door (willekeurig) voorloopnullen mee te nemen, vandaar dat ik zeg MSB=1 .
Als je trouwens wel met fixed-length werkt, is "lengte van het getal" inclusief voorloopnullen ook gewoon zinloos .
"getal onder de tien van vier cijfers " : 0003
Hoeveel kilometer heeft jouw auto gelopen "getal van zeven cijfers" .
Op die fiets praat ik ook graag over mijn salaris als een getal van 12 cijfers.
Met een willekeurig aantal voorloopnullen is de "lengte" van een getal betekenisloos.
De nerd definitie dan maar, een binair getal waarvan de 2log 512 is.
Hoewel je in theorie een vijver hebt van 154 decimale cijfers, zijn er verschillende redenen waardoor die vijver in de praktijk kleiner is. Wellicht is die vijver, ondanks de beperkingen, nog steeds zo groot dat, gegeven een RNG met voldoende entropie, de kans op een collision verwaarloosbaar is, maar dat soort aannames worden te vaak gedaan in de cryptografie en blijken later onjuist. Ik ben liever voorzichtig.
Nee, daar worden geen _aannames_ gedaan, daar wordt naar de wiskunde gekeken, in plaats van een huis en tuin en keuken "gevoel".
Als er nou één vak is waar de uitspraken en noodzakelijke randvoorwaarden strak gedefinieerd zijn is het wel de wiskunde en (zeker) getaltheorie.
Als je niet voldoet aan die randvoorwaarden (zoals het genereren van een echt random groot getal) , dan kun je niet steunen op bewijzen die daaruit volgen; No shit sherlock.
De (impliciete) aanname die bij een product gedaan wordt wat betreft de competentie van de implementator daarintegen ...
Het is mij altijd een bron van verbazing, en zo af en toe ergernis, hoe lang er (vaak juist security mensen) geneuzeld wordt over crypto keylengtes en zeer hypothetische brute-force aanvallen en hoe weinig over implementatie, bugs en alle manieren waarop in de praktijk werkelijk aanvallers binnen komen.
Ik vrees dat dat is omdat, ongeveer als enige, keylengtes een mooi kwantificeerbaar niveau van veiligheid geven, en dat er over de rest geen harde uitspraken te doen zijn.
19-02-2012, 17:10 door
Erik van Straten
Door Anoniem: Als je geen fixed-length veld gebruikt, kun je de lengte van getallen niet uitdrukken door (willekeurig) voorloopnullen mee te nemen, vandaar dat ik zeg MSB=1 .
Jouw stelling is dus dat van elk binair getal (ongelijk nul) waarvan alle voorloopnullen zijn verwijderd, het most significant bit 1 is?Ja duh...
Als je trouwens wel met fixed-length werkt, is "lengte van het getal" inclusief voorloopnullen ook gewoon zinloos .
Dat hangt helemaal van de context af. Voor de getalrepresentatie boeit het inderdaad niet, maar je hebt zelf de term "vijver" geïntroduceerd. De kans dat twee afzonderlijk gegenereerde random getallen de waarde 1 opleveren is aanzienlijk anders als de vijver 1 bit of 512 bit groot is. Je kunt van het resultaat 1 pas zeggen hoe random het (mogelijk) was als je erbij vertelt hoe groot de vijver was waar de random generator uit mocht kiezen.Ik ga nog even terug naar een eerder antwoord van je:
Door Anoniem op 15-02-2012 om 22:32: Anders gezegd, het paper van Lenstra et.al presenteert "12720 1024-bit RSA keys ontbonden te hebben".
Dat, terwijl het ontbinden van één 1024 bit RSA key (die wel correct gegenereerd is) voorlopig nog buiten bereik ligt.
Dacht het niet, we schrijven ruim 2 jaar na het factoriseren van 768 bit (zie http://eprint.iacr.org/2010/006.pdf): Dat, terwijl het ontbinden van één 1024 bit RSA key (die wel correct gegenereerd is) voorlopig nog buiten bereik ligt.
By Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K.Lenstra, Emmanuel Thomé, Joppe W.Bos, Pierrick Gaudry, Alexander Kruppa, Peter L.Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, and Paul Zimmermann: Factorization of a 768-bit RSA modulus version 1.4, February 18, 2010
1 Introduction
On December 12, 2009, we factored the 768-bit, 232-digit number RSA-768 by the number field sieve (NFS, [20]). The number RSA-768 was taken from the now obsolete RSA Challenge list [38] as a representative 768-bit RSA modulus (cf. [37]). This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one.
Because the first factorization of a 512-bit RSA modulus was reported only a decade ago (cf. [7]) it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours or the one in [7]. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.
1 Introduction
On December 12, 2009, we factored the 768-bit, 232-digit number RSA-768 by the number field sieve (NFS, [20]). The number RSA-768 was taken from the now obsolete RSA Challenge list [38] as a representative 768-bit RSA modulus (cf. [37]). This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one.
Because the first factorization of a 512-bit RSA modulus was reported only a decade ago (cf. [7]) it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours or the one in [7]. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.
Door Anoniem: Het is mij altijd een bron van verbazing, en zo af en toe ergernis, hoe lang er (vaak juist security mensen) geneuzeld wordt over crypto keylengtes en zeer hypothetische brute-force aanvallen en hoe weinig over implementatie, bugs en alle manieren waarop in de praktijk werkelijk aanvallers binnen komen.
Ik vrees dat dat is omdat, ongeveer als enige, keylengtes een mooi kwantificeerbaar niveau van veiligheid geven, en dat er over de rest geen harde uitspraken te doen zijn.
Kan zijn, maar van jou heb ik geen verklaring gezien waarom de hoogste byte van 1024 bit RSA moduli altijd >= 0x80 lijkt te zijn, en strong primes winpel je weg. Allemaal mooi en aardig, maar stel dat we te maken hebben met een perfecte PRNG, hoe groot is dan de vijver waar deze bij het genereren van een maximaal 512 bit groot priemgetal in de praktijk uit kan vissen?Ik vrees dat dat is omdat, ongeveer als enige, keylengtes een mooi kwantificeerbaar niveau van veiligheid geven, en dat er over de rest geen harde uitspraken te doen zijn.
Door Erik van Straten:
Ja duh...
Door Anoniem: Als je geen fixed-length veld gebruikt, kun je de lengte van getallen niet uitdrukken door (willekeurig) voorloopnullen mee te nemen, vandaar dat ik zeg MSB=1 .
Jouw stelling is dus dat van elk binair getal (ongelijk nul) waarvan alle voorloopnullen zijn verwijderd, het most significant bit 1 is?Ja duh...
Wel, net zo duh als dat de LSB van een priemgetal 1 is, daarom stond er ook een smiley achter beide beweringen...
Als je trouwens wel met fixed-length werkt, is "lengte van het getal" inclusief voorloopnullen ook gewoon zinloos .
Dat hangt helemaal van de context af. Voor de getalrepresentatie boeit het inderdaad niet, maar je hebt zelf de term "vijver" geïntroduceerd. De kans dat twee afzonderlijk gegenereerde random getallen de waarde 1 opleveren is aanzienlijk anders als de vijver 1 bit of 512 bit groot is. Je kunt van het resultaat 1 pas zeggen hoe random het (mogelijk) was als je erbij vertelt hoe groot de vijver was waar de random generator uit mocht kiezen.De context hier was en is RSA encryptie en wiskunde, daar heeft "lengte van een getal" echt maar één betekenis.
De term "vijver om uit te vissen" heb ik gebruikt voor het aantal priemgetallen met een lengte van 512 bits.
(zie onder voor hoeveel, aka hoe groot die vijver is)
Ik ga nog even terug naar een eerder antwoord van je:
Door Anoniem op 15-02-2012 om 22:32: Anders gezegd, het paper van Lenstra et.al presenteert "12720 1024-bit RSA keys ontbonden te hebben".
Dat, terwijl het ontbinden van één 1024 bit RSA key (die wel correct gegenereerd is) voorlopig nog buiten bereik ligt.
Dacht het niet, we schrijven ruim 2 jaar na het factoriseren van 768 bit (zie http://eprint.iacr.org/2010/006.pdf): Dat, terwijl het ontbinden van één 1024 bit RSA key (die wel correct gegenereerd is) voorlopig nog buiten bereik ligt.
By Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen K.Lenstra, Emmanuel Thomé, Joppe W.Bos, Pierrick Gaudry, Alexander Kruppa, Peter L.Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, and Paul Zimmermann: Factorization of a 768-bit RSA modulus version 1.4, February 18, 2010
1 Introduction
On December 12, 2009, we factored the 768-bit, 232-digit number RSA-768 by the number field sieve (NFS, [20]). The number RSA-768 was taken from the now obsolete RSA Challenge list [38] as a representative 768-bit RSA modulus (cf. [37]). This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one.
Because the first factorization of a 512-bit RSA modulus was reported only a decade ago (cf. [7]) it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours or the one in [7]. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.
1 Introduction
On December 12, 2009, we factored the 768-bit, 232-digit number RSA-768 by the number field sieve (NFS, [20]). The number RSA-768 was taken from the now obsolete RSA Challenge list [38] as a representative 768-bit RSA modulus (cf. [37]). This result is a record for factoring general integers. Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one.
Because the first factorization of a 512-bit RSA modulus was reported only a decade ago (cf. [7]) it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours or the one in [7]. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.
We zitten er nog steeds vrij ruim vanaf.
Het is aardig speculeren hoever je komt met N jaren werk en budgetten van het formaat "Irak oorlog" (allemaal ingezet op het ontbinden van één enkele sleutel), maar het RSA-1024 is nog wel even buiten bereik.
De al eerder genoemde Bob Silverman heeft er wel eens in enig detail over gepost, en in welke mate _alle_ resources (niet alleen cpu cycles) groeien met een groter getal. Zoals geheugen van individuele computers in de parallele stap, en nauw gekoppeld geheugen op de computer die de laatste stap van een factorisatie (matrix oplossen) moet doen.
Nog een paar racks vol met GPU kaarten helpen daaraan niet zo veel.
Vanuit theoretisch perspectief is dat "slechts" een constante factor, maar het maakt in het uitvoeren veel verschil.
Dit is een gebied wat ik met enige belangstelling volg, (RSA-768 had ik zien langskomen destijds) en waar ik nog geen startend RSA-1024 project ken.
Vanuit het perspectief "misschien ergens in komend decennium iets wat een jaar of meer continue werk vergt voor een enkele key" is "12,720 RSA keys ontbonden" dan andere koek, en nogal duidelijk dat er ergens een shortcut was.
Door Anoniem: Het is mij altijd een bron van verbazing, en zo af en toe ergernis, hoe lang er (vaak juist security mensen) geneuzeld wordt over crypto keylengtes en zeer hypothetische brute-force aanvallen en hoe weinig over implementatie, bugs en alle manieren waarop in de praktijk werkelijk aanvallers binnen komen.
Ik vrees dat dat is omdat, ongeveer als enige, keylengtes een mooi kwantificeerbaar niveau van veiligheid geven, en dat er over de rest geen harde uitspraken te doen zijn.
Kan zijn, maar van jou heb ik geen verklaring gezien waarom de hoogste byte van 1024 bit RSA moduli altijd >= 0x80 lijkt te zijn, en strong primes winpel je weg. Allemaal mooi en aardig, maar stel dat we te maken hebben met een perfecte PRNG, hoe groot is dan de vijver waar deze bij het genereren van een maximaal 512 bit groot priemgetal in de praktijk uit kan vissen?Ik vrees dat dat is omdat, ongeveer als enige, keylengtes een mooi kwantificeerbaar niveau van veiligheid geven, en dat er over de rest geen harde uitspraken te doen zijn.
Ik heb niet in detail gekeken naar het opslagformaat wat gebruikt wordt voor de modulus, maar ga gewoon nogmaals uit van msb=1 ?.
Verscholen achter de brede rug van Rivest en Silverman (et.al) wuif ik inderdaad strong primes als niet nuttig weg ja.
Zelfs _als_ je je zou beperken tot strong primes zijn ze overigens niet zo zeldzaam dat je keuze enorm beperkt wordt.
Hoeveel priemgetallen van (precies) 512 bits (ja, msb=1) er zijn had ik, in zekere zin, al aangegeven.
Ik schreef (vrijdag 10:30) dat er x/ln(x) priemgetallen zijn <= x.
Dat is het Prime Number Theorem, overigens.
Vul daar x=2^512 in, vul x=2^511 in, en trek van elkaar af.
Dat levert het formaat getal waarbij "collision (cq duplicaat) op goed geluk" gewoon van de kaart is gevallen en vervangen door bewust on onbewust slechte RNG.
20-02-2012, 20:31 door
Erik van Straten
@Anoniem 19-2-2012 23:33: opnieuw dank voor jouw bijdragen, je helpt me scherp te blijven! Ik stel voor om de discussie hier te sluiten, ik geloof niet dat we het eens gaan worden...
Door Erik van Straten: @Anoniem 19-2-2012 23:33: opnieuw dank voor jouw bijdragen, je helpt me scherp te blijven! Ik stel voor om de discussie hier te sluiten, ik geloof niet dat we het eens gaan worden...
Is prima.
Ter afsluiting een lees linkje : http://primes.utm.edu/howmany.shtml
Afgezien van het subonderwerp hier (hoeveel priemgetallen) gewoon is de site van Chris Caldwell gewoon boeiend over priemgetallen en aanverwante getaltheorie. Sommige erg moeilijk, sommige al eeuwen een open vraag, andere, en elk geval achteraf, eigenlijk " das gewoon logisch ".
22-02-2012, 12:35 door
Erik van Straten
Door Anoniem: Ter afsluiting een lees linkje : http://primes.utm.edu/howmany.shtml
Leuk leesvoer, dan je wel!Reageren
Deze posting is gelocked. Reageren is niet meer mogelijk.
Specialiseer je in Forensisch ICT
Online informatieavond 19 november
Wil jij je specialiseren in digitaal forensisch onderzoek? Je kennis verbreden en tech-nische vaardigheden ontwikkelen? Ontdek de cursus- en opleidingsmogelijkheden van Hogeschool Leiden:
- Bachelor Informatica Forensisch ICT (deeltijd)
- Master Digital Forensics (vol- en deeltijd)
- Module Mobile Forensics
- Module Data Analytics
Interesse? Meld je aan!
Chief Information Security Officer
Utrecht heeft jou nodig! Als Chief Information Security Officer speel jij een cruciale rol in de bescherming van de digitale informatie van de gemeente Utrecht. Als geen ander weet jij welke dreigingen er zijn en kun je deze vertalen naar risico's die de gemeente en haar inwoners lopen. Solliciteer nu!
Cybersecurity Trainer / Streamer
Toe aan een nieuwe nieuwe job waarmee je het verschil maakt? In de Certified Secure trainingen laat je deelnemers zien hoe actuele kwetsbaarheden structureel verholpen worden. Ook werk je actief mee aan de ontwikkeling van onze gamified security challenges. Bij het maken van challenges kom je telkens nieuwe technieken tegen, van Flutter tot GraphQL, van Elastic Search tot Kubernetes.
