Mulți designeri au susținut că schema lor de criptografie are securitate pe 80 de biți. Deci, cum se calculează timpul de atacking a acestei scheme de criptografie de securitate pe 80 de biți, cum ar fi RSA de securitate pe 80 de biți folosind un fel de procesor?
Comentarii
- RSA pe 80 de biți se poate sparge într-o clipire, folosind de ex GMP-ECM . Pentru informații despre înregistrările de factorizare RSA, consultați aceasta . Pentru informații despre securitatea pe 80 de biți, consultați aceasta . Pentru alegerea dimensiunii cheii, consultați aceasta .
- Vă mulțumim pentru răspuns. Acum iau ca exemplu securitatea pe 128 de biți. Vreau să întreb că securitatea pe 128 de biți înseamnă operațiunea de bază 2 ^ 128 pentru a ataca această schemă. Este adevărat？ Și operația de bază înseamnă multiplicare sau adunare generală? Și cum se calculează timpul concret pentru a ataca această schemă? 2 ^ 128 înmulțește timpul de efectuare a înmulțirii sau adunării generale?
- ah, deci întrebarea dvs. este: ce înseamnă securitate $ n $ -bit. ' Încerc să găsesc un Q / A despre asta. Pe scurt: înseamnă că sunt necesari $ 2 ^ n $ pași pentru a sparge sistemul, unde " pasul " este vag definit. Pentru criptarea simetrică, în general, " funcționează la fel de mult ca o criptare sau hash ". Pentru lucrări teoretice asupra criptografiei asimetrice, " pasul " tinde să fie " un singur grup ( sau operație de câmp) sau un hash ". Pentru RSA, ar putea fi 1 modul de multiplicare modular N (al cheii publice) sau 1 hash. Dar, în practică, securitatea de $ n $ -bit este adesea utilizată pentru: la fel de mult (computer) funcționează ca ruperea unui cifru simetric cu securitate de $ n $ -bit.
- A existat o întrebare despre Insecuritate pe 64 de biți . Supercomputerele precum Summit pot ajunge la 2 $ ^ {72} $ într-un an. Cu toate acestea, un grup dedicat, precum minerii Bitcoin, poate ajunge la 2 $ ^ {92} $ într-un an, astfel încât 80 de biți nu mai sunt siguri. Dacă este disponibil un atac cu mai multe ținte, chiar și AES-128 nu este sigur pentru toate țintele, vezi aici și Ce este un atac cu mai multe ținte? și aici AES-128 a fost complet rupt?
- @fgrieu Vă mulțumim pentru răspuns. De asemenea, vreau să știu că 2 ^ {128} poate fi văzut ca cicluri de ceas? După cum văd, timpul de funcționare poate fi măsurat și prin cicluri de ceas.
Răspuns
Întrebarea se reduce în mare măsură la:
Ce înseamnă $ n $ -bit securitate în practică pentru o valoare dată din $ n $ ?
TL; DR: la fel de sigur ca un bun cifru simetric cu o cheie $ n $ -bit.
Nu există o singură definiție mai precisă, chiar dacă ne limităm la atacatorii care folosesc clasic calculatoare (mai degrabă decât computere cuantice), așa cum face acest răspuns.
Un sens general acceptat este că numărul de „pași” pentru a sparge sistemul este considerat a fi $ 2 ^ n $ ; sau mai exact că probabilitatea de a sparge sistemul cu $ s $ „pași” nu este cunoscută a fi mai mare de $ s \, 2 ^ {- n} $ prin orice metodă pentru orice $ s $ . Cu toate acestea, „pașii” și „pauzele” nu sunt definite cu precizie.
În teoria criptării simetrice, „pasul” este de obicei luat ca o execuție a cifrului cu o nouă cheie. În acest fel, un cifru ideal cu o cheie de $ n $ biți are $ n $ -bit de securitate, sub căutare forță brută. Când trecem la practică, atacatorii nu sunt obligați să caute cu forța brută, iar definiția unui „pas” trebuie să devină un număr de sub-pași comparabili ca număr și cost de calcul cu sub-pașii necesari pentru unul executarea cifrului cu o nouă cheie pentru un text simplu de dimensiunea cheii . Cu această definiție, un cifru practic cu o cheie de $ n $ biți are cel mult $ n $ – securitatea biților și vizează idealul respectiv.
Când trecem la hash, definiția unui pas ar putea deveni un număr de sub-pași comparabili ca număr și cost de calcul cu sub-pașii necesari pentru hashing un mesaj nou de dimensiunea ieșirii hash .
Una dintre multele probleme cu cele de mai sus este că nu există un acord cu privire la dacă ar trebui să numărăm sau nu costul memoriei și al acceselor la memorie în costul de calcul. Lucrul sigur din perspectiva utilizatorului nu este să-l numeri, dar acest lucru poate fi de o importanță capitală pentru un atacator.
Definiția „pașilor” devine și mai tulbure atunci când vine vorba de criptografie asimetrică. ca RSA.În teorie, „pașii” ar putea fi un singur calcul în structura algebrică utilizată pentru criptosistem; ca, pentru RSA, o evaluare a multiplicării modulare $ (a, b) \ mapsto a \, b \ bmod N $ pentru întregul arbitrar $ a $ și $ b $ în $ [0, N) $ , unde $ N $ este modulul public. Dar există probleme care mută acest lucru în practică, în special pentru RSA: cel mai cunoscut atac este de a calcula modulul public $ N $ utilizând algoritm GNFS , care cost de calcul este dominat de operații care au puțină similitudine cu multiplicarea modulară și de cost practic, dominat de memorie și accesul la memorie. Ceea ce pune înapoi definiția vagă din TL; DR.
cum se calculează timpul de atacare a acestei scheme de criptografie de securitate pe 80 de biți, cum ar fi RSA de securitate pe 80 de biți utilizând un fel de procesor?
„RSA de securitate pe 80 de biți” nu trebuie înțeles ca RSA cu un public de 80 de biți modul $ N $ , care este terminal nesigur. Dacă am avea dimensiunea $ N $ , am putea estima dificultatea pe baza acelei experiențe și a experienței anterioare (vezi aceasta și linkurile sale). Dar nu, și nu există un consens cu privire la dimensiunea $ N $ pentru RSA cu securitate pe 80 de biți: 1024 de biți sunt adesea citați, dar în funcție de ipoteză , și pe care îl întrebați, este „prea mult sau prea puțin. Astfel, cel mai bun este să ignorați că vorbim despre RSA și să reveniți la: cât timp este necesar pentru a sparge un cifru simetric bun cu un 80-bit cheie.
Ceea ce ne aduce la: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequency } \ times \ text {Number-of-CPUs}} $$ unde $ n $ este nivelul de securitate în biți, $ k $ este o estimare a numărului de cicluri CPU pentru a evalua un cifru bun folosind un algoritm ultra-optimizat și $ p $ este probabilitatea reziduală de succes a unui adversar. În funcție de perspectivă, am putea lua $ k = 1 $ (care economisește examinarea detaliilor), $ k = 32 $ (deoarece acestea sunt încă mai mici decât în cele mai bune atacuri împotriva cifrelor bune care folosesc un computer de uz general) sau mult mai mult. În funcție de perspectivă, putem lua $ p = 1 $ (cel mai prudent din perspectiva unui utilizator legitim), $ p = 1/2 $ (rezultând timpul așteptat în cazul unui cifru bloc), sau un $ p $ mai mic dacă dorim o marjă de securitate¹.
De exemplu, cu $ 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} $ , primim $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , adică aproximativ 8 ani. Cu alte cuvinte, cele 1000 de procesoare noastre au o probabilitate foarte mică de succes împotriva criptelor simetrice pe 80 de biți, până când devin învechite din punct de vedere tehnic.
Pe de altă parte, 1000 de procesoare reprezintă o mică parte din procesoarele din întreaga lume și extragerea bitcoin arată în mod concludent că criptarea pe 80 de biți nu mai este suficientă împotriva adversarilor cu capacitatea de a proiecta ASIC-uri, de a le construi în cantități masive și de a susține costurile energetice pentru funcționarea lor; vezi aceasta .
¹ Termenul $ p $ în formula este cea mai prudentă din perspectiva unui utilizator legitim, dar face ca $ \ text {Time} $ să fie subestimat în multe scenarii de atac. De exemplu, în căutare coliziune, termenul corect ar fi mai mult ca $ \ sqrt p $ .