¿Basta con 1024 bits?

A continuación se transcribe, traducido libremente al castellano, un
pequeño artículo escrito por Bruce Schneier, reputado criptólogo de fama
mundial y autor de algoritmos como “blowfish” y “twofish”, uno de los
finalistas del reciente AES.
El artículo fue publicado en el boletín “Crypto-Gram”, del 15 de Abril
de 2002.

¿Basta con 1024 bits?.

El mes pasado escribí a propósito de las investigaciones de Dan
Bernstein sobre factorizaciones, y cómo dicho trabajo puede afectar al
tamaño de las claves RSA. En los últimos días se han producido
discusiones al respecto en la lista de correo BugTraq, en la que el
cypherpunk "Lucky Green" citaba este trabajo como la principal
motivación para revocar su clave PGP de 1024 bits.

Esto provoca una interesante pregunta: ¿son las claves RSA de 1024 bits
inseguras y, si es el caso, qué debe haberse al respecto?.

El récord de factorización público actual es de 512 bits, utilizando
ordenadores de propósito general. La prudencia nos obliga a que
sospechemos que instituciones como la ASN (Agencia de Seguridad Nacional
de EE.UU.) pueden superar dicho récord de forma privada, aunque no
sabemos por qué porcentaje.

En 1995 estimé que la longitud de las claves necesarias para protegernos
de diferentes adversarios: individuos, corporaciones y gobiernos
(Applied Cryptography, segunda edición, tabla 7.6, página 162). En aquel
momento sugerí que se debería migrar a claves de 1280 bits o, incluso,
1536 bits, si nos preocupaba tener a grandes corporaciones y gobiernos
como adversarios.:

 Longitud recomendada de la clave pública RSA

 Año Ind. Corp. Gob.<
 1995 768 1280 1536
 2000 1024 1280 1536
 2005 1280 1536 2048
 2010 1280 1536 2048
 2015 1536 2048 2048


Mirando estos números escritos hace siete años, creo que eran
conservadores, aunque no demasiado. La factorización, al menos entre la
comunidad académica, no ha progresado tan rápido como esperaba. Pero el
progreso matemático ocurre a ráfagas, y un descubrimiento transcendental
puede recuperar el progreso perdido. Así que si estuviese haciendo estas
recomendaciones hoy mismo, mantendría mis estimaciones del año 2000.

Hace tiempo que creo que una clave de 1024 bits puede romperse con una
máquina de mil millones de dólares. Y sigo creyendo también que una
clave RSA de 1024 bits es aproximadamente equivalente a una clave
simétrica de 80 bits (en Applied Cryptography, escribí que una clave RSA
de 768 bits es equivalente a una clave simétrica de 80 bits; eso
probablemente fue una infravaloración de las claves RSA).

Comparar claves simétricas com asimétricas es como comparar manzanas con
naranjas. Recomiendo claves simétricas de 128 bits porque trabajar con
ellas es tan rápido como con claves de 64 bits. Esto no es cierto para
las claves asimétricas. Doblar el tamaño de la clave supone,
aproximadamente, dividir la velocidad de procesamiento software por
seis. Esto puede no tener importancia para PGP, por ejemplo, pero puede
convertir aplicaciones cliente-servidor como SSL en tortugas. He visto
artículos proclamando que se necesita una clave RSA de 3072 bits para
que tenga una resistencia equivalente a una clave simétrica de 128 bits,
y claves RSA de 15.000 bits para resistir como claves simétricas de 256
bits. Este tipo de mentalidad es ridículo. Las prestaciones y los
modelos de ataque son tan diferentes que la comparación no tiene ningún
sentido.

No hay razón para el pánico y para descartar los sistemas actuales: No
creo que el anuncio de Bernstein haya cambiado nada. En la actualidad
podemos estar razonablemente contentos con nuestras claves de 1024 bits,
y los militares e instituciones lo bastante paranoicas como para
temerlas deberían haberlas actualizado hace años.

En mi opinión, la gran noticia del anuncio de Lucky Green no es que crea
que las investigaciones de Benstein sean lo bastante preocupantes como
para aconsejarle revocar sus claves de 1024 bits sino que, en el 2002,
Lucky Green todavía tiene claves RSA de 1024 bits que revocar.

Esta discusión subraya la inmensa inercia en el despliegue de claves.
Mucha gente todavía utiliza claves cortas. El mensaje de Lucky Green ha
arrojado luz sobre este fenómeno. Escribió "a la luz de esto, he
revocado todas mis claves PGP personales de 1024 bits y la gran telaraña
de confianza que dichas claves han adquirido con el tiempo". La malla de
confianza asociada a dichas claves tenía un gran valor, y restablecerla
con un nuevo conjunto de claves será difícil y llevará tiempo. Para
Green, el coste era más importante que tener claves "lo bastante
grandes".

El anuncio de Lucky Green en BugTraq
http://online.securityfocus.com/archive/1/263924

Mi ensayo sobre el artículo de Bernstein sobre factorización
http://www.counterpane.com/crypto-gram-0203.html#6

Cobertura periodística
http://zdnet.com.com/2110-1105-863643.html
http://www.infosecuritymag.com/2002/apr/news.shtml#factoringfriction

Otros ensayos sobre el artículo de Bernstein
http://www.rsasecurity.com/rsalabs/technotes/bernstein.html

Más información:

Is 1024 Bits Enough?
http://www.counterpane.com/crypto-gram-0204.html#3

Circuits for Integer Factorization: a Proposal
http://cr.yp.to/papers.html#nfscircuit