Mange designere hævdede, at deres kryptografiskema har 80-bit sikkerhed. Så hvordan beregner man tidspunktet for tilslutning af dette 80-bit sikkerhedskryptografisk skema, såsom 80-bit sikkerhed RSA ved hjælp af en slags CPU?
Kommentarer
- 80-bit RSA kan brydes i et blink, f.eks GMP-ECM . For oplysninger om RSA-faktoriseringsposter, se dette . For oplysninger om 80-bit sikkerhed, se dette . For valg af nøglestørrelse, se dette .
- Tak for dit svar. Nu tager jeg 128-bit sikkerhed som eksempel. Jeg vil bede om, at 128-bit sikkerhed betyder 2 ^ 128 grundlæggende operation for at angribe denne ordning. Er dette sandt？ Og betyder den grundlæggende operation generel multiplikation eller tilføjelse? Og hvordan beregner man den konkrete tid til at angribe denne ordning? 2 ^ 128 ganger gang med generel multiplikation eller tilføjelse?
- ah så dit spørgsmål er: hvad betyder $ n $ -bit sikkerhed. Jeg ' prøver at finde en Q / A om dette. I en nøddeskal: det betyder, at der er behov for $ 2 ^ n $ trin for at bryde systemet, hvor " trin " er løst defineret. For symmetrisk krypto er det generelt " så meget arbejde som en kryptering eller hash ". For teoretisk arbejde med asymmetrisk krypto har " trin " tendens til at være " en gruppe ( eller felt) handling eller en hash ". For RSA kunne det være 1 modulær multiplikationsmod N (af den offentlige nøgle) eller 1 hash. Men i praksis bruges $ n $ -bit sikkerhed ofte til: lige så meget (computer) arbejde som at bryde en symmetrisk chiffer med $ n $ -bit sikkerhed.
- Der var et spørgsmål om 64-bit usikkerhed . Supercomputere som Summit kan nå $ 2 ^ {72} $ om et år. En dedikeret gruppe som Bitcoin minearbejdere kan dog nå $ 2 ^ {92} $ om et år, så 80-bit ikke er mere sikker. Hvis multi-target angreb er tilgængeligt, er selv AES-128 ikke sikkert for alle mål, se her og Hvad er et multi-target angreb? og her Er AES-128 blevet brudt fuldstændigt?
- @fgrieu Tak for dit svar. Jeg vil også gerne vide, at kan 2 ^ {128} ses som urcyklusser? Som jeg ser, kan køretiden også måles ved hjælp af urcyklusser.
Svar
Spørgsmålet koger stort set ned til:
Hvad betyder $ n $ -sikkerhed i praksis for en given værdi af $ n $ ?
TL; DR: lige så sikker som en god symmetrisk kryptering med en $ n $ -bit nøgle.
Der er ikke en eneste mere præcis definition, selvom vi begrænser os til angribere, der bruger klassisk computere (snarere end kvantecomputere), som dette svar gør.
En generelt accepteret betydning er, at antallet af “trin” til at bryde systemet menes at være $ 2 ^ n $ ; eller mere præcist, at sandsynligheden for at bryde systemet med $ s $ “trin” ikke vides at være mere end $ s \, 2 ^ {- n} $ efter en hvilken som helst metode til enhver $ s $ . Imidlertid er “trin” og “brud” ikke præcist defineret.
I teorien om symmetrisk kryptering tages “trin” typisk som en udførelse af krypteringen med en ny nøgle. På denne måde har en ideel chiffer med en nøgle på $ n $ bits $ n $ -bit sikkerhed, under brute force-nøglesøgning. Når vi bevæger os til praksis, er angribere ikke bundet til søgning i brutalt kraftnøgle, og definitionen af et “trin” skal blive et antal deltrin, der kan sammenlignes i antal og beregningsomkostninger med de delstrin, der kræves for en udførelse af kryptering med en ny nøgle til en almindelig tekst på størrelse med nøglen . Med denne definition har en praktisk chiffer med en nøgle på $ n $ bits højst $ n $ – bit sikkerhed og sigter mod dette ideal.
Når vi går til hashes, kan definitionen af et trin blive et antal deltrin, der kan sammenlignes i antal og beregningsomkostninger med de nødvendige deltrin til hashing af en ny besked på størrelse med hashoutput .
Et af mange problemer med ovenstående er, at der ikke er enighed om, hvorvidt vi skal tælle eller ikke omkostningerne ved hukommelse og hukommelsesadgang i beregningsomkostningerne. Det sikre fra en brugers perspektiv er ikke at tælle det, men det kan være af altafgørende betydning for en angriber.
Definitionen af “trin” bliver endnu mere mørk, når det kommer til asymmetrisk kryptografi. ligesom RSA.I teorien kan “trin” være en beregning i den algebraiske struktur, der bruges til kryptosystemet; som for RSA, en evaluering af modulær multiplikation $ (a, b) \ mapsto a \, b \ bmod N $ for vilkårligt heltal $ a $ og $ b $ i $ [0, N) $ , hvor $ N $ er det offentlige modul. Men der er problemer med at flytte dette til praksis, især for RSA: det bedst kendte angreb er at faktorere det offentlige modul $ N $ ved hjælp af GNFS -algoritme, hvilken beregningsomkostning er domineret af operationer, der har ringe lighed med modulær multiplikation, og af praktiske omkostninger domineret af hukommelse og adgang til hukommelse. Hvilket sætter brugen tilbage til den vage definition i TL; DR.
hvordan man beregner tidspunktet for angreb på dette 80-bit sikkerhedskryptografisk skema, såsom 80-bit sikkerheds-RSA ved hjælp af en slags CPU?
“80-bit sikkerhed RSA” skal ikke forstås som RSA med en 80-bit offentlig modul $ N $ , som er usikker. Hvis vi havde størrelsen $ N $ , kunne vi estimere vanskeligheden ud fra den og tidligere erfaring (se dette og dens links). Men det gør vi ikke, og der er ingen enighed om størrelsen på $ N $ for RSA med 80-bit sikkerhed: 1024-bit citeres ofte, men afhængigt af hypotesen , og hvem du spørger, det er groft for meget eller for lidt. Således er det bedste at ignorere, at vi taler om RSA, og komme tilbage til: så lang tid som nødvendigt for at bryde en god symmetrisk chiffer med en 80-bit nøgle.
Hvilket bringer os til: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequency } \ times \ text {Number-of-CPUs}} $$ hvor $ n $ er sikkerhedsniveauet i bits, $ k $ er et skøn over antallet af CPU-cyklusser til evaluering af en god chiffer ved hjælp af en ultraoptimeret algoritme og $ p $ er den tilbageværende sandsynlighed for succes for en modstander. Afhængigt af perspektivet kan vi tage $ k = 1 $ (hvilket sparer undersøgelse af oplysningerne), $ k = 32 $ (fordi det stadig er mindre end i de bedste angreb mod gode cifre ved hjælp af en almindelig computer) eller meget mere. Afhængigt af perspektivet kan vi tage $ p = 1 $ (mest forsigtige set fra en legitim brugers perspektiv), $ p = 1/2 $ (giver den forventede tid i tilfælde af en blokchiffer) eller en mindre $ p $ hvis vi ønsker en sikkerhedsmargen¹.
For eksempel med $ 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} $ , vi får $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , det vil sige ca. 8 år. Med andre ord, vores 1000 CPUer har kun en meget lille sandsynlighed for succes mod 80-bit symmetrisk krypto, indtil de bliver teknisk forældede.
På den anden side er 1000 CPUer en lille brøkdel af verdensomspændende CPUer og bitcoin-minedrift viser endelig, at 80-bit krypto ikke længere er nok mod modstandere med kapaciteterne til at designe ASICer, bygge dem i store mængder og opretholde energiomkostningerne til deres drift se dette .
¹ Termen $ p $ i formlen er den mest forsigtige set fra en legitim brugers perspektiv, men det får $ \ text {Time} $ til at blive undervurderet i mange angrebsscenarier. For eksempel i kollisionssøgning ville det rigtige udtryk være mere som $ \ sqrt p $ .