En Febrero de 2017 se reportó la vulnerabilidad conocida como Return of Coppersmith’s Attack (ROCA) con CVE-2017-15361 y que afectó entre otros dispositivos a una gran cantidad de DNIs electrónicos con chip gemalto. La solución aplicada en el caso de los DNIs fue revocar (impedir uso futuro) las claves afectadas y expedir nuevas claves de 1920bits que, según los autores del ataque y el Centro Criptológico Nacional, no están afectadas por dicha vulnerabilidad.
Han salido artículos recientemente con afirmaciones algo alarmistas sobre la reducción de la clave en 128-bits. La realidad es que se estima que el factor de trabajo de un ataque contra dichas claves se reduce como mucho en 32 (es decir, si atacar una clave de 2048-bits requiriera 32 ordenadores funcionando un año, las de 1920 bits requieren 1 ordenador funcionando un año o 32 funcionando unos 12 días). Puede parecer mucho pero teniendo en cuenta lo enormes que son los factores de seguridad con los que se trabaja en realidad no es un valor muy significativo. En el caso de que aparezcan ordenadores cuánticos lo bastante potentes, los factores de seguridad se reducirían tanto que la diferencia en la cantidad de tiempo necesario para atacar a cualquiera de los dos algoritmos sería ínfima.
En este artículo os voy a explicar mejor las matemáticas que hay tras mis afirmaciones.
Para entender un poco mejor el contexto de mis afirmaciones os recomiendo leer primero el artículo sobra la vulnerabilidad ROCA del Coronel Fernando Acero Martín. Si bien sus afirmaciones acerca de las claves de 1920 bits son desacertadas, el problema que describe donde se suplanta la identidad del firmante (o se invalidan las firmas hechas con claves afectadas) es muy serio y debe ser tenido en cuenta.
La forma más trivial de descomponer un número en sus factores primos consiste en comprobar si el resto de la división del número entre un posible factor x es 0 y si lo es, dividir el número entre x el número de veces que sea posible anotar x como factor dicho número de veces y seguir el proceso con el nuevo número calculado y con x+1. Este proceso se puede optimizar porque si un número está compuesto por al menos dos factores de modo que n=p·q el menor de p y q debe ser menor o igual a la raíz cuadrada de n (en cuyo caso p=q). Por lo que en vez de incrementar hasta n podemos incrementar hasta su raíz cuadrada. Si bien es probable que este algoritmo se conociera con anterioridad, este fue, por su sencillez, el que yo (re)descubrí en mi adolescencia cuando intentaba atacar este problema inspirado por mis profesores de instituto (a los que quiero mandar un saludo y mi agradecimiento si leen esto).
Así pues, como las claves RSA se componen de al menos dos factores: p y q ambos de la mitad de bits que la clave pública n, el ataque en realidad no debe procesar 2¹²⁸ claves menos como indica el artículo sino “solo” unas 2⁴⁴ claves menos (porque el logaritmo en base dos de la raiz de 2²⁰⁴⁸8 entre la de 2¹⁹⁶⁰ es 44). 1.75e13 o la cantidad de kilómetros que recorre la luz en 2 años (enorme, pero desde luego no infinito).
Otra forma de comprobar la reducción real del espacio de claves es utilizar la fórmula para contar primos π(x). Dado que las claves RSA se componen generalmente de dos primos de la mita de bits, a un atacante preparado, le basta con calcular los restos de las divisiones con esos π(2^(nbits)+2^(nbits-1))-π(2^(nbits-1)) primos posibles, suponiendo que pueda precomputar dicho listado de primos. En su artículo de 1962 “Approximate formulas for some functions of prime numbers” Rosser y Schoenfeld proponen la siguiente inecualidad que ofrece una cota superior e inferior de dicha fórmula que podéis ver en la imagen de abajo.
Si bien las cotas de esta fórmula no son especialmente precisa, nos pueden ayudar a ver que una reducción del número de bits de la clave de 2 bits (el doble de lo propuesto por el coronel) implica una reducción del espacio del claves entre el 76.8% y el 53.9% siendo lo más probable un valor cercano al 66.7% y bastante inferior al 75% que el razonamiento del Coronel Acero implica. Si aplicamos la misma fórmula para los 128 bits de diferencia, el espacio de claves sería de un 99.999 999 999 999 999 996% inferior que pese a ser un número enorme queda muy lejos del 99.999 999 999 999 999 999 999 999 6% propuesto por el Coronel (fijaos que el segundo porcentaje tiene siete nueves más lo cual es unos 10 millones de posibilidades más).
La realidad sin embargo es mucho más compleja. Si bien el algoritmo de Shor (que requiere circuitos cuánticos específicos) puede resolver el problema RSA tanto para 2048 como para 1960 bits en una cantidad de tiempo relativamente ínfima, (y con las que no tiene mucho sentido comparar tiempos), el mejor algoritmo conocido en ordenadores normales conocido como General Number Field Sieve o GNFS puede resolver el problema en un tiempo inferior a 2^nbits. Por ello, para poder comparar el problema de la reducción de bits de una clave RSA con el problema de reducción del espacio de claves que propone el coronel es necesario utilizar una fórmula para calcular el número de bits de seguridad del algoritmo.
En esto, los estándares son algo más claros. La “Guía de Seguridad CCN-STIC 807 “Criptología de empleo en el Esquema Nacional de Seguridad”, en su revisión de 2017” en el Cuadro D.1 establece equivalencias con niveles de seguridad en bits. Este cuadro esta extraido del del “NIST Special Publication 800-57”. Dicho del NIST indica que esta tabla proviene de otra publicación: “Implementation Guidance for FIPS 140-2 and the Cryptographic Module Validation Program” https://csrc.nist.gov/csrc/media/projects/cryptographic-module-validation-program/documents/fips140-2/fips1402ig.pdf que provee la formula para calcular la equivalencia para los elementos que no están en la tabla (página 121) y que os dejo en la imagen de abajo.
Si aplicamos esa fórmula a 1920 obtenemos aproximadamente 107 bits (con 2048 serían 110) pero aún siguiendo la tabla podemos ver que la reducción en seguridad es de como mucho 5 bits o lo que es lo mismo dividir el espacio de claves original (según la tabla) de 5.2e33 por solo 32 a unas 1.6e32 ambos números enormes aunque algo inferiores a los 2¹²⁸ que se recomiendan hoy en día. Si aplicamos la fórmula a ambos lados el resultado es aún más cercano siendo la diferencia de únicamente 4.5 veces el espacio de claves.
En conclusión podemos decir que aunque el ENS o las recomendaciones del NIST recomienden usar claves de 2048 bits (o de pasada 1024 en el párrafo 492), el uso de claves de 1920 bits no reduce por si mismo la seguridad del sistema RSA de forma lo bastante significativa para suponer un problema en si mismo.
Quiero dedicar este artículo a la memoria de Dan Kaminsky, uno de los hackers que con sus increibles ataques me inspiró a intentar ser uno de ellos. Te echaremos de menos, mentes como la tuya siempre faltan en este mundo.