Ataque académico a tamaños de clave RSA de 768 bits

El algoritmo RSA de criptografía de clave pública se basa en una propiedad de la aritmética modular que hace casi imposible calcular la clave privada a partir de la clave pública, aunque ambas están matemáticamente vinculadas. Un componente común de las dos claves es el valor n que procede de multiplicar dos números primos p y q. Dado que la labor de la factorización de un número en sus componentes primos es crecientemente costosa conforme aumenta el tamaño del número, está claro que los avances matemáticos en técnicas de factorización harán paulatinamente menos seguros los sistemas que empleen tamaños de clave “relativamente” pequeños.

Este es el caso de la noticia que se puede encontrar en varios medios, como El Mundo:

Un grupo internacional de investigadores consiguió descomponer en sus factores primos una cifra de 232 dígitos, un récord que apunta a que relativamente pronto los códigos de seguridad habituales en Internet quedarán caducos.
Así lo informó la Universidad de Bonn, cuyo Instituto de Matemáticas participó en el proyecto.
Los códigos de seguridad habituales en Internet se basan en la dificultad para descomponer grandes cifras en sus factores primos.
“Lo que cualquier estudiante de primaria consigue sin problemas con 21=7×3 resulta casi imposible con cifras lo suficientemente grandes”, explica la universidad a través de un comunicado.
La cifra descompuesta por el grupo de investigadores tiene 768 bits, lo que equivale a decir que tiene 768 dígitos en el sistema de numeración binario que, traspasados al sistema decimal, se convierten en 232 dígitos.
Se considera que una clave de seguridad lo suficientemente segura actualmente debe tener por lo menos 1024 bits.
Para descomponer la cifra de 232 dígitos se utilizó una red de varios ordenadores, ya que según la universidad un solo ordenador normal hubiese necesitado cerca de 2.000 años para conseguirlo.
En el récord conseguido participaron, además de la Universidad de Bonn, el Departamento Federal de Seguridad en la Tecnología Informática, el Centro Wiskunde&Informatika de Holanda y la Escuela Federal Politécnica de Lausanne (Suiza), entre otras instituciones.
El ’software’ utilizado fue desarrollado en buena parte en el Instituto de Matemáticas de la Universidad de Bonn.
Según el profesor Jens Franke, la descomposición en factores primos de una clave de 1024 bits será claramente más difícil y necesitaría modificaciones importantes en el ’software’ utilizado.
Sin embargo, Franke considera que antes del final de esta década se logrará por primera vez descifrar una clave de 1024 bits.
Por ello, recomienda, para garantizar un alto nivel de seguridad a largo plazo, empezar a utilizar claves de seguridad de 2048 bits.

Otro artículo, en inglés [*], con más detalle técnico es el de Ars Technica, de John Timmer:

 Con la creciente potencia de cómputo disponible hasta para usuarios casuales, quien es consciente de la seguridad ha tenido que moverse hacia una robustez de cifrado creciente, de modo que no hallen a su información vulnerable a los ataques de fuerza bruta. El último hito por caer es 768-bit RSA; en un trabajo publicado en un servidor de criptografía, investigadores académicos han anunciado que factorizaron una de estas claves a comienzos de diciembre.

La criptografía más moderna se basa en números únicos grandes que son el producto de dos números primos. Si uno conoce los números, resulta relativamente sencillo cifrar y descifrar la información; sino, encontrar los números mediante fuerza bruta es un gran desafío computacional. Pero este reto se vuelve más sencillo cada año a medida que la velocidad de los procesadores y su eficiencia aumentan, haciendo que lo "seguro" sea un poco como un blanco móvil. El trabajo describe como fue realizado el proceso con hardware común del mercado, aunque con muchos de ellos.

El primer paso involucró  tamizar, o identificar los números enteros apropiados; eso tomó el equivalente de 1.500 años en un núcleo de un Opteron de 2,2Ghz; el resultado ocupó unos 5 TB. Estos luego fueron hallados los datos únicos y procesados en una matriz; debido a todo el trabajo anterior, usar ahora la matriz para factorizar el valor RSA solo le tomó al agrupamiento de equipos menos de mediodía. Aunque la mayor parte de la gente no va a tener acceso a este tipo de agrupamiento, estos representan un monto trivial de capacidad de computación para la muchas organizaciones. Como resultado, los autores concluyen, "El esfuerzo general es suficientemente bajo que aún la protección a corto plazo de información de poco valor, con módulo RSA de 768-bit ya no puede ser recomendada." Valores de 1024-bit sin embargo pueden ser buenos todavía por algunos años.

Dado que estos desarrollos son del alguna manera inevitables, incluso los autores suenan un poco aburridos por su informe, "No hay nada nuevo a ser informado para la etapa de la raíz cuadrada, excepto por la factorización resultante de RSA-768" escriben. "No obstante, y para que quede registro, presentamos algunos detalles." Incluso se las arreglaron para divertirse un poco en una parte haciendo referencia a un clip de Tarantino en Youtube haciendo igualmente el uso del término "bingo."

[*] Traducción nota de ArsTechnica: Raúl Batista - Segu-info
Autor: inza
Fuente: Todo es electrónico

Suscríbete a nuestro Boletín