La forma m\u00e1s trivial de descomponer un n\u00famero en sus factores primos consiste en comprobar si el resto de la divisi\u00f3n del n\u00famero entre un posible factor x es 0 y si lo es, dividir el n\u00famero entre x el n\u00famero de veces que sea posible anotar x como factor dicho n\u00famero de veces y seguir el proceso con el nuevo n\u00famero calculado y con x+1. Este proceso se puede optimizar porque si un n\u00famero est\u00e1 compuesto por al menos dos factores de modo que n=p\u00b7q el menor de p y q debe ser menor o igual a la ra\u00edz cuadrada de n (en cuyo caso p=q). Por lo que en vez de incrementar hasta n podemos incrementar hasta su ra\u00edz cuadrada. Si bien es probable que este algoritmo se conociera con anterioridad, este fue, por su sencillez, el que yo (re)descubr\u00ed 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).<\/p>\n
As\u00ed 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\u00fablica n, el ataque en realidad no debe procesar 2\u00b9\u00b2\u2078 claves menos como indica el art\u00edculo sino “solo” unas 2\u2074\u2074 claves menos (porque el logaritmo en base dos de la raiz de 2\u00b2\u2070\u2074\u20788 entre la de 2\u00b9\u2079\u2076\u2070 es 44). 1.75e13 o la cantidad de kil\u00f3metros que recorre la luz en 2 a\u00f1os (enorme, pero desde luego no infinito).<\/p>\n
Otra forma de comprobar la reducci\u00f3n real del espacio de claves es utilizar la f\u00f3rmula para contar primos \u03c0(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 \u03c0(2^(nbits)+2^(nbits-1))-\u03c0(2^(nbits-1)) primos posibles, suponiendo que pueda precomputar dicho listado de primos. En su art\u00edculo 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\u00f3rmula que pod\u00e9is ver en la imagen de abajo.<\/p>\n
![\"F\u00f3rmula](\"\/imagenes\/klog\/eqpi.svg\")
<\/p>\n
Si bien las cotas de esta f\u00f3rmula no son especialmente precisa, nos pueden ayudar a ver que una reducci\u00f3n del n\u00famero de bits de la clave de 2 bits (el doble de lo propuesto por el coronel) implica una reducci\u00f3n del espacio del claves entre el 76.8% y el 53.9% siendo lo m\u00e1s probable un valor cercano al 66.7% y bastante inferior al 75% que el razonamiento del Coronel Acero implica. Si aplicamos la misma f\u00f3rmula para los 128 bits de diferencia, el espacio de claves ser\u00eda de un 99.999 999 999 999 999 996% inferior que pese a ser un n\u00famero 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\u00e1s lo cual es unos 10 millones de posibilidades m\u00e1s).<\/p>\n
La realidad sin embargo es mucho m\u00e1s compleja. Si bien el algoritmo de Shor (que requiere circuitos cu\u00e1nticos espec\u00edficos) puede resolver el problema RSA tanto para 2048 como para 1960 bits en una cantidad de tiempo relativamente \u00ednfima, (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\u00f3n de bits de una clave RSA con el problema de reducci\u00f3n del espacio de claves que propone el coronel es necesario utilizar una f\u00f3rmula para calcular el n\u00famero de bits de seguridad del algoritmo.<\/p>\n
En esto, los est\u00e1ndares son algo m\u00e1s claros. La “Gu\u00eda de Seguridad CCN-STIC 807 \u201cCriptolog\u00eda de empleo en el Esquema Nacional de Seguridad\u201d, en su revisi\u00f3n 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\u00f3n: “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\u00e1n en la tabla (p\u00e1gina 121) y que os dejo en la imagen de abajo.<\/p>\n
![\"F\u00f3rmula](\"\/imagenes\/klog\/eqrsa.svg\")
<\/p>\n
Si aplicamos esa f\u00f3rmula a 1920 obtenemos aproximadamente 107 bits (con 2048 ser\u00edan 110) pero a\u00fan siguiendo la tabla podemos ver que la reducci\u00f3n en seguridad es de como mucho 5 bits o lo que es lo mismo dividir el espacio de claves original (seg\u00fan la tabla) de 5.2e33 por solo 32 a unas 1.6e32 ambos n\u00fameros enormes aunque algo inferiores a los 2\u00b9\u00b2\u2078 que se recomiendan hoy en d\u00eda. Si aplicamos la f\u00f3rmula a ambos lados el resultado es a\u00fan m\u00e1s cercano siendo la diferencia de \u00fanicamente 4.5 veces el espacio de claves.<\/p>\n
En conclusi\u00f3n podemos decir que aunque el ENS o las recomendaciones del NIST recomienden usar claves de 2048 bits (o de pasada 1024 en el p\u00e1rrafo 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.<\/p>\n
Quiero dedicar este art\u00edculo a la memoria de Dan Kaminsky, uno de los hackers que con sus increibles ataques me inspir\u00f3 a intentar ser uno de ellos. Te echaremos de menos, mentes como la tuya siempre faltan en este mundo.<\/p>\n","protected":false},"excerpt":{"rendered":"
En Febrero de 2017 se report\u00f3 la vulnerabilidad conocida como Return of Coppersmith’s Attack (ROCA) con CVE-2017-15361 y que afect\u00f3 entre otros dispositivos a una gran cantidad de DNIs electr\u00f3nicos con chip gemalto. La soluci\u00f3n aplicada en el caso de los DNIs fue revocar (impedir uso futuro) las claves afectadas y expedir nuevas claves de […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[53,52,100,50,29],"class_list":["post-514","post","type-post","status-publish","format-standard","hentry","category-seguridad","tag-cryptanalysis","tag-cryptography","tag-dni-e","tag-hacking","tag-security"],"_links":{"self":[{"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/posts\/514","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/comments?post=514"}],"version-history":[{"count":6,"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/posts\/514\/revisions"}],"predecessor-version":[{"id":521,"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/posts\/514\/revisions\/521"}],"wp:attachment":[{"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/media?parent=514"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/categories?post=514"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/klondike.es\/klog\/wp-json\/wp\/v2\/tags?post=514"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}