Mange designere hevdet at krypteringsskjemaet deres har 80-biters sikkerhet. Så hvordan beregner du tiden for å angripe dette 80-biters sikkerhetskryptografisk ordningen, for eksempel 80-biters sikkerhets-RSA ved hjelp av en slags CPU?
Kommentarer
- 80-biters RSA kan brytes på et blunk, ved å bruke f.eks GMP-ECM . For informasjon om RSA-faktoriseringsposter, se dette . For informasjon om 80-biters sikkerhet, se dette . For valg av nøkkelstørrelse, se dette .
- Takk for svaret. Nå tar jeg 128-biters sikkerhet som eksempel. Jeg vil be om at 128-biters sikkerhet betyr 2 ^ 128 grunnleggende operasjon for å angripe denne ordningen. Er dette sant？ Og betyr grunnoperasjonen generell multiplikasjon eller tillegg? Og hvordan beregner man den konkrete tiden for å angripe denne ordningen? 2 ^ 128 multipliserer tiden for generell multiplikasjon eller tillegg?
- ah så spørsmålet ditt er: hva betyr $ n $ -bit sikkerhet? Jeg ' prøver å finne en spørsmål om dette. I et nøtteskall: det betyr $ 2 ^ n $ trinn er nødvendig for å bryte systemet, der " trinn " er løst definert. For symmetrisk krypto er det generelt " like mye arbeid som en kryptering eller hash ". For teoretisk arbeid med asymmetrisk krypto, " trinn " har en tendens til å være " en gruppe ( eller felt) -operasjon eller en hash ". For RSA kan det være en modulær multiplikasjonsmodus N (av den offentlige nøkkelen) eller 1 hash. Men i praksis brukes $ n $ -bit sikkerhet ofte til: like mye (datamaskin) arbeid som å bryte en symmetrisk kryptering med $ n $ -bit sikkerhet.
- Det var et spørsmål om 64-bit usikkerhet . Superdatamaskiner som Summit kan nå $ 2 ^ {72} $ om et år. Imidlertid kan en dedikert gruppe som Bitcoin-gruvearbeidere nå $ 2 ^ {92} $ på et år, så 80-bit er ikke mer sikker. Hvis flermålsangrep tilgjengelig, selv AES-128 ikke er sikkert for alle mål, se her og Hva er et flermålangrep? og her Har AES-128 blitt fullstendig ødelagt?
- @fgrieu Takk for svaret ditt. Jeg vil også vite at kan 2 ^ {128} sees på som klokkesykluser? Som jeg ser at kjøretid også kan måles ved hjelp av klokkesykluser.
Svar
Spørsmålet koker stort sett ned til:
Hva betyr $ n $ -bit sikkerhet i praksis for en gitt verdi av $ n $ ?
TL; DR: like sikker som en god symmetrisk kryptering med en $ n $ -bit-nøkkel.
Det er ikke en eneste mer presis definisjon, selv om vi begrenser oss til angripere som bruker klassisk datamaskiner (i stedet for kvantedatamaskiner), som dette svaret gjør.
En generelt akseptert mening er at antall «trinn» for å bryte systemet antas å være $ 2 ^ n $ , eller mer presist at sannsynligheten for å bryte systemet med $ s $ «trinn» ikke er kjent for å være mer enn $ s \, 2 ^ {- n} $ ved hvilken som helst metode for hvilken som helst $ s $ . Imidlertid er «trinn» og «pause» ikke nøyaktig definert.
I teorien om symmetrisk kryptering blir «trinn» vanligvis tatt som en utførelse av krypteringen med en ny nøkkel. På denne måten har en ideell kryptering med en nøkkel på $ n $ bits $ n $ -bit sikkerhet, under brute force key search. Når vi går over til praksis, er ikke angripere bundet til brute force key search, og definisjonen av et «trinn» må bli et antall deltrinn som kan sammenlignes i antall og beregningskostnader med deltrinnene som kreves for en utførelse av kryptering med en ny nøkkel for en ren tekst på størrelse med nøkkelen . Med denne definisjonen har en praktisk kryptering med nøkkelen $ n $ bits maksimalt $ n $ – litt sikkerhet, og sikter mot det idealet.
Når vi går til hashes, kan definisjonen av et trinn bli et antall deltrinn som kan sammenlignes i antall og beregningskostnader med de nødvendige trinnene for å hashe en ny melding på størrelse med hash-utdata .
Et av mange problemer med det ovennevnte er at det ikke er enighet om om vi skal telle eller ikke kostnadene for minne og minnetilgang i beregningskostnaden. Det trygge fra en brukers perspektiv er ikke å telle det, men det kan være av største betydning for en angriper.
Definisjonen av «trinn» blir enda mer grumsete når det kommer til asymmetrisk kryptografi. som RSA.I teorien kan «trinn» være en beregning i den algebraiske strukturen som brukes for kryptosystemet; som for RSA, en evaluering av modulær multiplikasjon $ (a, b) \ mapsto a \, b \ bmod N $ for vilkårlig heltall $ a $ og $ b $ i $ [0, N) $ , der $ N $ er den offentlige modulen. Men det er problemer med å flytte dette til praksis, spesielt for RSA: det mest kjente angrepet er å faktorisere den offentlige modulen $ N $ ved hjelp av GNFS algoritme, hvilken beregningskostnad domineres av operasjoner som har liten likhet med modulær multiplikasjon, og av praktiske kostnader dominert av minne og tilgang til minne. Som setter bruk tilbake til den vage definisjonen i TL; DR.
hvordan man beregner tiden for å angripe dette 80-biters sikkerhetskryptografisk ordningen, for eksempel 80-biters sikkerhets-RSA ved hjelp av en slags CPU?
«80-biters sikkerhet RSA» skal ikke forstås som RSA med en 80-biters offentlig modul $ N $ , som er usikkert. Hvis vi hadde størrelsen $ N $ , kunne vi estimere vanskelighetsgraden basert på den og tidligere erfaring (se dette og dens lenker). Men det gjør vi ikke, og det er ingen enighet om størrelsen på $ N $ for RSA med 80-biters sikkerhet: 1024-bit siteres ofte, men avhengig av hypotesen , og hvem du spør om, det er grovt for mye eller for lite. Dermed er det beste å ignorere at vi snakker om RSA, og komme tilbake til: så lang tid som trengs for å bryte en god symmetrisk kryptering med en 80-bit nøkkel.
Som bringer oss til: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequency } \ times \ text {Number-of-CPUs}} $$ der $ n $ er sikkerhetsnivået i bits, $ k $ er en estimering av antall CPU-sykluser for å evaluere en god kryptering ved hjelp av en ultraoptimalisert algoritme, og $ p $ er den gjenværende sannsynligheten for at en motstander lykkes. Avhengig av perspektiv kan vi ta $ k = 1 $ (som sparer å undersøke detaljene), $ k = 32 $ (fordi det fortsatt er mindre enn i de beste angrepene mot gode krypter ved hjelp av en generell datamaskin), eller mye mer. Avhengig av perspektiv kan vi ta $ p = 1 $ (mest forsiktige fra et legitimt brukerperspektiv), $ p = 1/2 $ (gir forventet tid i tilfelle en blokkryptering), eller en mindre $ p $ hvis vi ønsker en sikkerhetsmargin¹.
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 si omtrent 8 år. Med andre ord, våre 1000 CPUer har bare en veldig liten sannsynlighet for suksess mot 80-biters symmetrisk krypto, til de blir teknisk foreldede.
På den annen side er 1000 CPUer en liten brøkdel av verdensomspennende prosessorer, og bitcoin-gruvedrift viser endelig at 80-biters krypto ikke lenger er nok mot motstandere med muligheten til å designe ASIC-er, bygge dem i store mengder og opprettholde energikostnadene for driften; se dette .
¹ Begrepet $ p $ i formelen er den mest forsiktige fra et legitimt brukerperspektiv, men det fører til at $ \ text {Time} $ blir undervurdert i mange angrepsscenarier. For eksempel i kollisjonssøk, vil det riktige ordet være mer som $ \ sqrt p $ .