Veel ontwerpers beweerden dat hun cryptografieschema 80-bits beveiliging heeft. Dus hoe bereken je de tijd die nodig is om dit 80-bits beveiligingscryptografieschema te gebruiken, zoals 80-bits RSA-beveiliging met een soort CPU?
Opmerkingen
- 80-bit RSA is in een oogwenk breekbaar, met bijv GMP-ECM . Zie this voor informatie over RSA-factorisatierecords. Zie this voor informatie over 80-bits beveiliging. Zie this voor de keuze van de sleutelgrootte.
- Bedankt voor uw antwoord. Nu neem ik 128-bits beveiliging als voorbeeld. Ik wil vragen dat 128-bits beveiliging 2 ^ 128 basisbewerkingen betekent om dit schema aan te vallen. Is dit waar？ En betekent de basisbewerking algemene vermenigvuldiging of optelling? En hoe bereken je de concrete tijd om dit plan aan te vallen? 2 ^ 128 vermenigvuldigt de tijd van algemene vermenigvuldiging of optelling?
- ah dus uw vraag is: wat betekent $ n $ -bit beveiliging. Ik ' m probeer hier een Q / A over te vinden. In een notendop: het betekent dat $ 2 ^ n $ stappen nodig zijn om het systeem te breken, waarbij " stap " losjes gedefinieerd is. Voor symmetrische crypto is het in het algemeen " evenveel werk als een codering of hash ". Voor theoretisch werk aan asymmetrische crypto, " stap " is " één groep ( of veld) bewerking of een hash ". Voor RSA kan dat 1 modulaire vermenigvuldigingsmod N (van de openbare sleutel) of 1 hash zijn. Maar in de praktijk wordt $ n $ -bit beveiliging vaak gebruikt voor: evenveel (computer) werk als het breken van een symmetrisch cijfer met $ n $ -bit beveiliging.
- Er was een vraag over 64-bits onveiligheid . Supercomputers zoals Summit kunnen in een jaar tijd oplopen tot $ 2 ^ {72} $. Een toegewijde groep zoals Bitcoin-mijnwerkers kan echter $ 2 ^ {92} $ in een jaar bereiken, dus 80-bit is niet veiliger. Als een aanval met meerdere doelen beschikbaar is, is zelfs AES-128 niet voor alle doelen beveiligd, kijk dan hier en Wat is een aanval met meerdere doelen? en hier Is AES-128 volledig defect?
- @fgrieu Bedankt voor je antwoord. Ik wil ook weten dat 2 ^ {128} kan worden gezien als klokcycli? Zoals ik zie, kan de looptijd ook worden gemeten door klokcycli.
Antwoord
De vraag komt grotendeels neer naar:
Wat betekent $ n $ -bit beveiliging in de praktijk voor een bepaalde waarde van $ n $ ?
TL; DR: zo veilig als een goed symmetrisch cijfer met een $ n $ -bit-sleutel.
Er is geen enkele nauwkeurigere definitie, zelfs als we ons beperken tot aanvallers die klassieke computers (in plaats van kwantumcomputers), zoals dit antwoord doet.
Een algemeen aanvaarde betekenis is dat het aantal “stappen” om het systeem te doorbreken wordt verondersteld te zijn $ 2 ^ n $ ; of beter gezegd dat de kans om het systeem te breken met $ s $ “steps” niet groter is dan $ s \, 2 ^ {- n} $ met elke methode voor elke $ s $ . “Stappen” en “breken” zijn echter niet precies gedefinieerd.
In de theorie van symmetrische versleuteling wordt “stap” doorgaans genomen als één uitvoering van de code met een nieuwe sleutel. Op deze manier heeft een ideaal cijfer met een sleutel van $ n $ bits $ n $ -bit beveiliging, onder brute force key search. Wanneer we overgaan tot oefenen, zijn aanvallers niet gebonden aan brute force key-zoekopdrachten, en de definitie van een stap moet een aantal substappen worden die qua aantal en rekenkosten vergelijkbaar zijn met de substappen die nodig zijn voor één uitvoering van het cijfer met een nieuwe sleutel voor een leesbare tekst ter grootte van de sleutel . Met deze definitie heeft een praktisch cijfer met de sleutel $ n $ bits maximaal $ n $ – bit-beveiliging, en streeft naar dat ideaal.
Wanneer we naar hashes gaan, kan de definitie van een stap een aantal substappen worden die qua aantal en rekenkosten vergelijkbaar zijn met de vereiste substappen voor het hashen van een nieuw bericht de grootte van de hash-uitvoer .
Een van de vele problemen met het bovenstaande is dat er geen overeenstemming is over of we de kosten van geheugen- en geheugentoegang moeten tellen of niet in de rekenkosten. Het veilige vanuit het perspectief van een gebruiker is om het niet te tellen, maar dat kan van het grootste belang zijn voor een aanvaller.
De definitie van “stappen” wordt nog duisterder als het gaat om asymmetrische cryptografie zoals RSA.In theorie kunnen “stappen” één berekening zijn in de algebraïsche structuur die wordt gebruikt voor het cryptosysteem; zoals, voor RSA, één evaluatie van modulaire vermenigvuldiging $ (a, b) \ mapsto a \, b \ bmod N $ voor willekeurig geheel getal $ a $ en $ b $ in $ [0, N) $ , waarbij $ N $ de openbare modulus is. Maar er zijn problemen om dit in de praktijk te brengen, met name voor RSA: de bekendste aanval is om de openbare modulus $ N $ te ontbinden met de GNFS -algoritme, waarvan de rekenkosten worden gedomineerd door bewerkingen die weinig gelijkenis vertonen met modulaire vermenigvuldiging, en waarvan de praktische kosten worden gedomineerd door geheugen en toegang tot geheugen. Dat maakt gebruik van de vage definitie in de TL; DR.
hoe de tijd van aanval op dit 80-bits cryptografieschema wordt berekend, zoals 80-bits RSA-beveiliging met een soort CPU?
“80-bits RSA-beveiliging” moet niet worden opgevat als RSA met een 80-bits openbare modulus $ N $ , wat terminaal onveilig is. Als we de grootte hadden van $ N $ , zouden we de moeilijkheid kunnen schatten op basis van dat en eerdere ervaringen (zie dit en zijn links). Maar dat doen we niet, en er is geen consensus over de grootte van $ N $ voor RSA met 80-bits beveiliging: 1024-bits wordt vaak genoemd, maar hangt af van de hypothese , en aan wie je het vraagt, dat is grofweg te veel of te weinig. Het is dus het beste om te negeren dat we het over RSA hebben, en terug te gaan naar: zoveel tijd als nodig is om een goed symmetrisch cijfer te breken met een 80-bits key.
Dat brengt ons bij: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequentie } \ times \ text {Number-of-CPUs}} $$ waarbij $ n $ het beveiligingsniveau in bits is, $ k $ is een schatting van het aantal CPU-cycli om een goede code te evalueren met behulp van een uiterst geoptimaliseerd algoritme, en $ p $ is de resterende kans op succes van een tegenstander. Afhankelijk van het perspectief kunnen we $ k = 1 $ nemen (wat het onderzoek van de details scheelt), $ k = 32 $ (omdat dat nog steeds minder is dan bij de beste aanvallen op goede cijfers met een computer voor algemeen gebruik), of veel meer. Afhankelijk van het perspectief, kunnen we $ p = 1 $ nemen (zeer voorzichtig vanuit het perspectief van een legitieme gebruiker), $ p = 1/2 $ (wat de verwachte tijd oplevert in het geval van een blokcijfer), of een kleinere $ p $ als we een veiligheidsmarge willen¹.
Bijvoorbeeld met $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ approx2 ^ {- 10} $ , $ \ text {Frequency} = 4 \ text {GHz} \ approx2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {Number-of-CPUs} = 1000 \ approx2 ^ {10} $ , we krijgen $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , dat is ongeveer 8 jaar. Met andere woorden, onze 1000 CPUs hebben slechts een zeer kleine kans op succes tegen 80-bit symmetrische crypto, totdat ze technisch verouderd raken.
Aan de andere kant is 1000 CPUs maar een fractie van wereldwijde CPUs en bitcoin mining toont onomstotelijk aan dat 80-bit crypto niet langer voldoende is tegen tegenstanders met de mogelijkheid om ASICs te ontwerpen, ze in enorme hoeveelheden te bouwen en de energiekosten voor hun werking te dragen; zie dit .
¹ De $ p $ term in de formule is het meest voorzichtig vanuit het perspectief van een legitieme gebruiker, maar hierdoor wordt $ \ text {Time} $ in veel aanvalsscenarios onderschat. botsing zoeken, zou de juiste term meer zijn als $ \ sqrt p $ .