Longitud de la clau

En criptografia, la mida de la clau o la longitud de la clau es refereix al nombre de bits d'una clau utilitzada per un algoritme criptogràfic (com ara un xifratge).
La longitud de la clau defineix el límit superior de la seguretat d'un algoritme (és a dir, una mesura logarítmica de l'atac més ràpid conegut contra un algoritme), perquè la seguretat de tots els algoritmes pot ser violada per atacs de força bruta. Idealment, el límit inferior de la seguretat d'un algoritme és, per disseny, igual a la longitud de la clau (és a dir, el disseny de l'algoritme no resta valor al grau de seguretat inherent a la longitud de la clau).
La majoria dels algoritmes de clau simètrica estan dissenyats per tenir una seguretat igual a la longitud de la seva clau. No obstant això, després del disseny, es podria descobrir un nou atac. Per exemple, Triple DES va ser dissenyat per tenir una clau de 168 bits, però ara es coneix un atac de complexitat 2112 (és a dir, Triple DES ara només té 112 bits de seguretat, i dels 168 bits de la clau l'atac n'ha fet "ineficaços" per a la seguretat). No obstant això, sempre que la seguretat (entesa com "la quantitat d'esforç que caldria per obtenir accés") sigui suficient per a una aplicació concreta, no importa si la longitud de la clau i la seguretat coincideixen. Això és important per als algoritmes de clau asimètrica, perquè no es coneix cap algoritme d'aquest tipus que satisfaci aquesta propietat; la criptografia de corba el·líptica és la que s'hi acosta més amb una seguretat efectiva d'aproximadament la meitat de la longitud de la seva clau.
Importància
Les claus s'utilitzen per controlar el funcionament d'un xifratge, de manera que només la clau correcta pugui convertir el text xifrat (text xifrat) en text sense format. Tots els xifratges d'ús comú es basen en algoritmes coneguts públicament o són de codi obert, de manera que només la dificultat d'obtenir la clau determina la seguretat del sistema, sempre que no hi hagi cap atac analític (és a dir, una "debilitat estructural" en els algoritmes o protocols utilitzats) i assumint que la clau no està disponible d'una altra manera (com ara mitjançant robatori, extorsió o compromís de sistemes informàtics). La idea àmpliament acceptada que la seguretat del sistema hauria de dependre només de la clau ha estat formulada explícitament per Auguste Kerckhoffs (a la dècada de 1880) i Claude Shannon (a la dècada de 1940); les afirmacions es coneixen com a principi de Kerckhoffs i màxima de Shannon, respectivament.
Per tant, una clau hauria de ser prou gran com perquè un atac de força bruta (possible contra qualsevol algorisme de xifratge) sigui inviable – és a dir, que trigaria massa temps i/o requeriria massa memòria per executar-se. El treball de Shannon sobre la teoria de la informació va demostrar que per aconseguir l'anomenat "secret perfecte", la longitud de la clau ha de ser com a mínim tan gran com el missatge i només s'ha d'utilitzar una vegada (aquest algorisme s'anomena "one-time pad"). A la llum d'això, i de la dificultat pràctica de gestionar claus tan llargues, la pràctica criptogràfica moderna ha descartat la noció de secret perfecte com a requisit per al xifratge, i en canvi se centra en la seguretat computacional, sota la qual els requisits computacionals de trencar un text xifrat han de ser inviables per a un atacant.
Mida de la clau i sistema de xifratge
Els sistemes de xifratge sovint s'agrupen en famílies. Les famílies comunes inclouen sistemes simètrics (per exemple, AES) i sistemes asimètrics (per exemple, RSA i criptografia de corba el·líptica [ECC]). Es poden agrupar segons l'algoritme central utilitzat (per exemple, xifratges ECC i Feistel). Com que cadascun d'aquests té un nivell diferent de complexitat criptogràfica, és habitual tenir diferents mides de clau per al mateix nivell de seguretat, depenent de l'algoritme utilitzat. Per exemple, la seguretat disponible amb una clau de 1024 bits utilitzant RSA asimètric es considera aproximadament igual en seguretat a una clau de 80 bits en un algorisme simètric.[1]
El grau real de seguretat aconseguit al llarg del temps varia a mesura que es disposa de més potència computacional i mètodes analítics matemàtics més potents. Per aquest motiu, els criptòlegs tendeixen a buscar indicadors que un algoritme o una longitud de clau mostren signes de vulnerabilitat potencial, per passar a mides de clau més llargues o algoritmes més difícils. Per exemple, A Maig 2007 , es va factoritzar un enter de 1039 bits amb el sedàs especial de camp numèric utilitzant 400 ordinadors durant 11 mesos. El nombre factoritzat tenia una forma especial; el sedàs del camp de nombres especials no es pot utilitzar en claus RSA. El càlcul és aproximadament equivalent a trencar una clau RSA de 700 bits. Tanmateix, això podria ser un avís previ que les claus RSA de 1024 bits utilitzades en el comerç en línia segur haurien de quedar obsoletes, ja que podrien arribar a ser fràgils en un futur previsible. El professor de criptografia Arjen Lenstra va observar que "l'última vegada, vam trigar nou anys a generalitzar d'un nombre especial a un nombre no especial, difícil de factoritzar" i quan se li va preguntar si les claus RSA de 1024 bits eren mortes, va dir: "La resposta a aquesta pregunta és un sí incondicional".[2]
L'atac Logjam del 2015 va revelar perills addicionals en l'ús de l'intercanvi de claus Diffie-Hellman quan només s'utilitzen un o uns quants mòduls primers comuns de 1024 bits o més petits. Aquesta pràctica, força comuna en aquell moment, permetia que es compromessin grans quantitats de comunicacions a costa d'atacar un petit nombre de nombres primers.[3]
Atac de força bruta
Fins i tot si un xifratge simètric és actualment indestructible explotant les debilitats estructurals del seu algorisme, pot ser possible executar tot l'espai de claus en el que es coneix com a atac de força bruta. Com que les claus simètriques més llargues requereixen exponencialment més feina per a la cerca per força bruta, una clau simètrica prou llarga fa que aquesta línia d'atac sigui poc pràctica.
Amb una clau de longitud n bits, hi ha 2n claus possibles. Aquest nombre creix molt ràpidament a mesura que n augmenta. El gran nombre d'operacions ( 2128) necessàries per provar totes les claus de 128 bits possibles es considera àmpliament fora de l'abast de les tècniques convencionals de computació digital en un futur previsible. Tanmateix, un ordinador quàntic capaç d'executar l'algoritme de Grover podria cercar les possibles claus de manera més eficient. Si un ordinador quàntic de la mida adequada pogués reduir una clau de 128 bits a una seguretat de 64 bits, aproximadament l'equivalent a DES. Aquesta és una de les raons per les quals AES admet longituds de clau de 256 bits o més.
Longituds de clau de l'algoritme simètric
El xifratge Lucifer d'IBM va ser seleccionat el 1974 com a base del que es convertiria en l'Estàndard de Xifratge de Dades. La longitud de la clau de Lucifer es va reduir de 128 bits a 56 bits, cosa que la NSA i el NIST van argumentar que era suficient per a la protecció no governamental en aquell moment. L'NSA té importants recursos informàtics i un gran pressupost; alguns criptògrafs, com ara Whitfield Diffie i Martin Hellman, es van queixar que això feia que el xifratge fos tan feble que els ordinadors de l'NSA podrien desxifrar una clau DES en un dia mitjançant la computació paral·lela per força bruta. L'NSA va qüestionar això, afirmant que l'ús de DES per força bruta els portaria "uns 91 anys".[4]
No obstant això, a finals dels anys 90, va quedar clar que el DES es podia desxifrar en pocs dies amb maquinari fet a mida, com el que podia comprar una gran corporació o un govern.[5] El llibre Cracking DES (O'Reilly and Associates) explica l'èxit del 1998 per trencar un DES de 56 bits mitjançant un atac de força bruta muntat per un grup de ciberdrets amb recursos limitats; vegeu EFF DES cracker. Fins i tot abans d'aquella demostració, 56 bits es considerava una longitud insuficient per a claus d'algoritme simètriques d'ús general. Per això, DES va ser substituït en la majoria d'aplicacions de seguretat per Triple DES, que té 112 bits de seguretat quan s'utilitzen claus de 168 bits (clau triple).[6]
L'estàndard avançat de xifratge publicat el 2001 utilitza mides de clau de 128, 192 o 256 bits. Molts observadors consideren que 128 bits són suficients en el futur previsible per a algoritmes simètrics de la qualitat d'AES fins que els ordinadors quàntics estiguin disponibles. Tanmateix, a partir del 2015, l'Agència de Seguretat Nacional dels Estats Units ha publicat directrius que planegen canviar a algoritmes resistents a la computació quàntica i ara requereix claus AES de 256 bits per a dades classificades fins a Top Secret.[7]
El 2003, l'Institut Nacional d'Estàndards i Tecnologia dels EUA (NIST) va proposar l'eliminació gradual de les claus de 80 bits abans del 2015. El 2005, les claus de 80 bits només estaven permeses fins al 2010.[8]
Des del 2015, les directrius del NIST diuen que "l'ús de claus que proporcionen menys de 112 bits de força de seguretat per a la concordança de claus ara no està permès". Els algoritmes de xifratge simètric aprovats pel NIST inclouen Triple DES de tres claus i AES. Les aprovacions per a Triple DES de dues claus i Skipjack es van retirar el 2015; l'algoritme Skipjack de la NSA utilitzat en el seu programa Fortezza utilitza claus de 80 bits.[9]
Longituds de clau d'algoritme asimètric
L'eficàcia dels criptosistemes de clau pública depèn de la intractabilitat (computacional i teòrica) de certs problemes matemàtics com la factorització entera. Aquests problemes requereixen molt de temps per resoldre'ls, però normalment són més ràpids que intentar totes les claus possibles per la força bruta. Per tant, les claus asimètriques han de ser més llargues per a una resistència equivalent a l'atac que les claus d'algoritme simètriques. Es considera que els mètodes més comuns són febles contra ordinadors quàntics prou potents en el futur.
Des del 2015, el NIST recomana un mínim de claus de 2048 bits per a RSA,[10] una actualització de la recomanació àmpliament acceptada d'un mínim de 1024 bits des d'almenys el 2002.[11]
Les claus RSA de 1024 bits són equivalents en força a les claus simètriques de 80 bits, les claus RSA de 2048 bits a les claus simètriques de 112 bits, les claus RSA de 3072 bits a les claus simètriques de 128 bits i les claus RSA de 15360 bits a les claus simètriques de 256 bits.[12] El 2003, RSA Security va afirmar que era probable que les claus de 1024 bits es poguessin desxifrar en algun moment entre el 2006 i el 2010, mentre que les claus de 2048 bits són suficients fins al 2030.[13] A 2020 La clau RSA més gran que es coneix públicament que ha estat piratejada és la RSA-250 amb 829 bits.[14]
L'algoritme Diffie-Hellman de camp finit té aproximadament la mateixa força de clau que RSA per a les mateixes mides de clau. El factor de treball per trencar Diffie-Hellman es basa en el problema del logaritme discret, que està relacionat amb el problema de factorització entera en què es basa la força de RSA. Per tant, una clau Diffie-Hellman de 2048 bits té aproximadament la mateixa força que una clau RSA de 2048 bits.
La criptografia de corba el·líptica (ECC) és un conjunt alternatiu d'algoritmes asimètrics que són equivalentment segurs amb claus més curtes, i només requereixen aproximadament el doble de bits que l'algoritme simètric equivalent. Una clau Diffie-Hellman de corba el·líptica (ECDH) de 256 bits té aproximadament el mateix factor de seguretat que una clau AES de 128 bits.[15] Un missatge xifrat amb un algorisme de clau el·líptica utilitzant una clau de 109 bits de longitud va ser desxifrat el 2004.[16]
L'NSA havia recomanat anteriorment ECC de 256 bits per protegir informació classificada fins al nivell SECRET i 384 bits per a TOP SECRET;[17] El 2015 va anunciar plans per fer la transició a algoritmes resistents als atacs quàntics el 2024 i, fins aleshores, recomana 384 bits per a tota la informació classificada.[18]
Efecte dels atacs de computació quàntica en la força de les claus
Els dos atacs de computació quàntica més coneguts es basen en l'algoritme de Shor i l'algoritme de Grover. Dels dos, el de Shor ofereix el risc més gran per als sistemes de seguretat actuals.
Es conjectura àmpliament que les derivades de l'algoritme de Shor són efectives contra tots els algoritmes de clau pública convencionals, incloent RSA, Diffie-Hellman i la criptografia de corba el·líptica. Segons el professor Gilles Brassard, expert en computació quàntica: "El temps necessari per factoritzar un enter RSA és del mateix ordre que el temps necessari per utilitzar aquest mateix enter com a mòdul per a un únic xifratge RSA. En altres paraules, no es triga més a trencar RSA en un ordinador quàntic (fins a una constant multiplicativa) que a utilitzar-lo legítimament en un ordinador clàssic". El consens general és que aquests algoritmes de clau pública no són segurs a qualsevol mida de clau si hi ha ordinadors quàntics prou grans capaços d'executar l'algoritme de Shor disponibles. La implicació d'aquest atac és que totes les dades xifrades amb sistemes de seguretat basats en estàndards actuals, com ara l'omnipresent SSL utilitzat per protegir el comerç electrònic i la banca per Internet i l'SSH utilitzat per protegir l'accés a sistemes informàtics sensibles, estan en risc. Les dades xifrades protegides mitjançant algoritmes de clau pública es poden arxivar i es poden trencar més endavant, cosa que es coneix comunament com a desxifratge retroactiu/retrospectiu o "recollir ara, desxifrar més tard".
Es conjectura àmpliament que els xifratges simètrics convencionals (com ara AES o Twofish) i les funcions hash resistents a les col·lisions (com ara SHA) ofereixen una major seguretat contra els atacs coneguts de computació quàntica. Es considera que són els més vulnerables a l'algoritme de Grover. Bennett, Bernstein, Brassard i Vazirani van demostrar el 1996 que una cerca de claus per força bruta en un ordinador quàntic no pot ser més ràpida que aproximadament 2 n /2 invocacions de l'algoritme criptogràfic subjacent, en comparació amb aproximadament 2 n en el cas clàssic. Així, en presència de grans ordinadors quàntics, una clau de n bits pot proporcionar almenys n /2 bits de seguretat. La força bruta quàntica es pot derrotar fàcilment duplicant la longitud de la clau, cosa que té un cost computacional addicional reduït en l'ús habitual. Això implica que es requereix una clau simètrica de com a mínim 256 bits per aconseguir una qualificació de seguretat de 128 bits contra un ordinador quàntic. Com s'ha esmentat anteriorment, l'NSA va anunciar el 2015 que té previst fer la transició a algoritmes resistents a les deteccions quàntiques.[19]
En una secció de preguntes freqüents sobre computació quàntica del 2016, la NSA va afirmar:
"Un ordinador quàntic prou gran, si es construeix, seria capaç de soscavar tots els algoritmes de clau pública àmpliament desplegats utilitzats per a l'establiment de claus i les signatures digitals. […] Generalment s'accepta que les tècniques de computació quàntica són molt menys efectives contra els algoritmes simètrics que contra els algoritmes de clau pública actualment àmpliament utilitzats. Si bé la criptografia de clau pública requereix canvis en el disseny fonamental per protegir contra un possible ordinador quàntic futur, es creu que els algoritmes de clau simètrica són segurs sempre que s'utilitzi una mida de clau prou gran. […] Els algoritmes de clau pública (RSA, Diffie-Hellman, [corba el·líptica Diffie-Hellman] ECDH i [Algorisme de signatura digital de corba el·líptica] ECDSA) són tots vulnerables a l'atac d'un ordinador quàntic prou gran. […] Si bé s'han proposat diversos algoritmes de clau pública resistents a la computació quàntica interessants externs a la NSA, el NIST no ha estandarditzat res, i la NSA no especifica cap estàndard comercial resistent a la computació quàntica en aquest moment. La NSA espera que el NIST tingui un paper principal en l'esforç per desenvolupar un conjunt estandarditzat i àmpliament acceptat d'algoritmes resistents a la computació quàntica." […] Donat el nivell d'interès a la comunitat criptogràfica, esperem que hi hagi algoritmes resistents a les eines quàntiques àmpliament disponibles durant la propera dècada. […] Els algoritmes AES-256 i SHA-384 són simètrics i es creu que estan a salvo dels atacs d'un gran ordinador quàntic."
En un comunicat de premsa del 2022, l'NSA va notificar:
"Un ordinador quàntic criptoanalíticament rellevant (CRQC) tindria el potencial de trencar els sistemes de clau pública (de vegades anomenats criptografia asimètrica) que s'utilitzen avui dia. Donades les activitats estrangeres en la computació quàntica, ara és el moment de planificar, preparar i pressupostar una transició a algoritmes QR [resistents als sistemes quàntics] per assegurar una protecció sostinguda dels [Sistemes de Seguretat Nacional] NSS i els actius relacionats en cas que un CRQC esdevingui una realitat assolible."
Des del setembre del 2022, l'NSA ha estat fent la transició del Commercial National Security Algorithm Suite (ara anomenat CNSA 1.0), llançat originalment el gener del 2016, al Commercial National Security Algorithm Suite 2.0 (CNSA 2.0), ambdós resumits a continuació:[20]
CNSA 2.0
| Algoritme | Funció | Paràmetres |
|---|---|---|
| Estàndard de xifratge avançat (AES) | Xifratge de blocs simètric per a la protecció de la informació | Claus de 256 bits |
| CRISTALLS-Kyber | Algoritme asimètric per a l'establiment de claus | Nivell V |
| CRISTALLS-Diliti | Algoritme asimètric per a signatures digitals | Nivell V |
| Algoritme de hash segur (SHA) | Algoritme per calcular una representació condensada d'informació | SHA-384 o SHA-512 |
| Signatura de Leighton-Micali (LMS) | Algoritme asimètric per a la signatura digital de firmware i programari | Tots els paràmetres aprovats. SHA256/192 recomanat. |
| Esquema de signatures Xtended Merkle (XMSS) | Algoritme asimètric per a la signatura digital de firmware i programari | Tots els paràmetres aprovats |
CNSA 1.0
| Algoritme | Funció | Paràmetres |
|---|---|---|
| Estàndard de xifratge avançat (AES) | Xifratge de blocs simètric per a la protecció de la informació | Claus de 256 bits |
| Intercanvi de claus Diffie-Hellman de corba el·líptica (ECDH) | Algoritme asimètric per a l'establiment de claus | Corba P-384 |
| Algoritme de signatura digital de corba el·líptica (ECDSA) | Algoritme asimètric per a signatures digitals | Corba P-384 |
| Algoritme de hash segur (SHA) | Algoritme per calcular una representació condensada d'informació | SHA-384 |
| Intercanvi de claus Diffie-Hellman (DH) | Algoritme asimètric per a l'establiment de claus | Mòdul mínim de 3072 bits |
| [Rivest-Shamir-Adleman] RSA | Algoritme asimètric per a l'establiment de claus | Mòdul mínim de 3072 bits |
| [Rivest-Shamir-Adleman] RSA | Algoritme asimètric per a signatures digitals | Mòdul mínim de 3072 bits |
Referències
- ↑ Barker, Elaine. «Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, NIST SP-800-131A Rev 2» (en anglès). Nvlpubs.nist.gov, 01-03-2019. [Consulta: 11 febrer 2023].
- ↑ Cheng, Jacqui. «Researchers: 307-digit key crack endangers 1024-bit RSA» (en anglès). Ars Technica, 23-05-2007. [Consulta: 24 setembre 2016].
- ↑ «Weak Diffie-Hellman and the Logjam Attack» (en anglès). weakdh.org, 20-05-2015.
- ↑ «DES Stanford-NBS-NSA meeting recording & transcript» (en anglès). Toad.com. Arxivat de l'original el 2012-05-03. [Consulta: 24 setembre 2016].
- ↑ Blaze, Matt. «Minimal key lengths for symmetric ciphers to provide adequate commercial security» (en anglès). Fortify, 01-01-1996. [Consulta: 14 octubre 2011].
- ↑ Barker, Elaine. «Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, NIST SP-800-131A Rev 2» (en anglès). Nvlpubs.nist.gov, 01-03-2019. [Consulta: 11 febrer 2023].
- ↑ «NSA Suite B Cryptography» (en anglès). National Security Agency, 15-01-2009. Arxivat de l'original el 2009-02-07. [Consulta: 24 setembre 2016].
- ↑ Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles NIST Special Publication, 01-08-2005. DOI: 10.6028/NIST.SP.800-57p1 [Consulta: 8 gener 2019].
- ↑ Barker, Elaine. «Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, NIST SP-800-131A Rev 2» (en anglès). Nvlpubs.nist.gov, 01-03-2019. [Consulta: 11 febrer 2023].
- ↑ Barker, Elaine; Dang, Quynh NIST Special Publication, 22-01-2015, p. 12. DOI: 10.6028/NIST.SP.800-57pt3r1 [Consulta: 24 novembre 2017].
- ↑ «A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths» (en anglès). RSA Laboratories. Arxivat de l'original el 2017-01-13. [Consulta: 24 setembre 2016].
- ↑ Barker, Elaine NIST Special Publication, 5-2020, p. 53. DOI: 10.6028/NIST.SP.800-57pt1r5.
- ↑ Kaliski, Burt. «TWIRL and RSA Key Size» (en anglès). RSA Laboratories, 06-05-2003. Arxivat de l'original el 2017-04-17. [Consulta: 24 novembre 2017].
- ↑ Zimmermann, Paul. «Factorization of RSA-250» (en anglès). Cado-nfs-discuss, 28-02-2020. Arxivat de l'original el 2020-02-28. [Consulta: 12 juliol 2020].
- ↑ Barker, Elaine; Dang, Quynh NIST Special Publication, 22-01-2015, p. 12. DOI: 10.6028/NIST.SP.800-57pt3r1 [Consulta: 24 novembre 2017].
- ↑ «Certicom Announces Elliptic Curve Cryptography Challenge Winner» (en anglès). BlackBerry Limited, 27-04-2004. Arxivat de l'original el 2016-09-27. [Consulta: 24 setembre 2016].
- ↑ «NSA Suite B Cryptography» (en anglès). National Security Agency, 15-01-2009. Arxivat de l'original el 2009-02-07. [Consulta: 24 setembre 2016].
- ↑ «Commercial National Security Algorithm Suite» (en anglès). National Security Agency, 09-08-2015. Arxivat de l'original el 2022-02-18. [Consulta: 12 juliol 2020].
- ↑ «NSA Suite B Cryptography» (en anglès). National Security Agency, 15-01-2009. Arxivat de l'original el 2009-02-07. [Consulta: 24 setembre 2016].
- ↑ «Announcing the Commercial National Security Algorithm Suite 2.0, U/OO/194427-22, PP-22-1338, Ver. 1.0» (en anglès). media.defense.gov. National Security Agency, 01-09-2022. Arxivat de l'original el November 21, 2022. [Consulta: 14 abril 2024].