Factorización de claves RSA de manga corta con polinomios

¿Qué ocurre cuando los bits de una clave privada RSA están fuertemente sesgados hacia 0 en lugar de generarse aleatoriamente? Los bits de la clave pública podrían estar sesgados lo suficiente como para que detectemos estas claves generadas incorrectamente en la práctica. Junto con Hanno Böck del proyecto badkeys, encontramos cientos de claves únicas que no solo tienen esta propiedad, sino que pueden factorizarse rápidamente. También descubrimos el error que originó muchas de estas claves y analizamos datos históricos para rastrear el problema a lo largo del tiempo. Sorprendentemente, el patrón de bits 0 suele estar altamente estructurado, lo que nos permitió desarrollar una poderosa técnica criptoanalítica basada en polinomios que explota el patrón. Figura 1: Dos patrones de módulos RSA con bloques repetidos de bits 0 observados en ejemplos del mundo real. Estas claves “de manga corta”, nombradas así porque los bits 0 no cubren completamente los “limbs” de los enteros grandes, se agrupan mayormente en dos patrones. El patrón 1 sigue sin explicación, pero rastreamos el patrón 2 a una incompatibilidad de tipos en el código de enteros grandes de versiones antiguas del software de transferencia de archivos CompleteFTP. El error de CompleteFTP también generó claves DSA vulnerables de “manga corta”, y recuperamos 603 claves privadas RSA únicas y 74 claves DSA de escaneos en Internet. Si usó CompleteFTP para generar claves de host entre diciembre de 2016 y diciembre de 2023, CompleteFTP ha publicado una herramienta para comprobar si sus claves deben regenerarse.

Cómo encontramos las claves débiles
El proyecto badkeys es un servicio de código abierto que verifica claves públicas en busca de vulnerabilidades conocidas. Mientras desarrollábamos esta herramienta, Hanno recopiló un número masivo de claves reales de fuentes públicas, incluidos los registros de Transparencia de Certificados, escaneos TLS y SSH a gran escala, claves PGP y muchas otras. Al buscar en este conjunto de datos módulos RSA inesperadamente escasos, descubrimos una gran cantidad de claves en la práctica con los patrones mostrados en la Figura 1. Ambos patrones incluyen varios bloques de ceros espaciados regularmente, intercalados con datos aparentemente aleatorios. El patrón 1 aparece en los registros CT de certificados emitidos a varias organizaciones grandes, incluidas Yahoo y Verizon, y en algunos dispositivos que ejecutan software NetApp. Afortunadamente, estos certificados ya expiraron, pero aun así compartimos nuestros hallazgos con esas compañías. Queríamos averiguar qué producto podía ser responsable de generar estas claves, pero no recibimos respuesta. El patrón 2 aparece en hosts SSH que ejecutan el software CompleteFTP de EnterpriseDT. La vulnerabilidad subyacente afecta a claves RSA generadas con las versiones 10.0.0–12.0.0 (dic 2016–mar 2019) y a claves DSA generadas con v10.0.0–23.0.4 (dic 2016–dic 2023). Estas vulnerabilidades afectan a una pequeña minoría de hosts en Internet, pero la conclusión más interesante es que implementaciones criptográficas independientes fallaron de maneras similares. Más implementaciones podrían incluir los mismos errores, por lo que vale la pena adaptar algoritmos criptoanalíticos a este tipo particular de falla.

Factorización con polinomios
Los algoritmos criptográficos suelen necesitar enteros de cientos o miles de bits, y representan estos “enteros grandes” usando un arreglo de valores más pequeños del tamaño de la máquina, llamados limbs. Si interpretamos el patrón 1 como una secuencia de limbs de 128 bits, o de 32 bits en el patrón 2, los bloques repetidos de ceros corresponden a un único bloque de ceros en cada limb. Solo una pequeña subsección contigua del limb se rellena con bits aleatorios, y el resto del limb queda descubierto, de ahí el apodo “claves de manga corta”. Al explotar esta estructura matemática en los limbs de estos módulos, sustituimos el problema difícil de factorizar enteros por el problema fácil de factorizar polinomios. Es decir, tomamos el módulo (n) con factores desconocidos (p) y (q), lo expresamos como un polinomio (f_n(x)) con coeficientes pequeños, factorizamos (f_n(x)) en (f_p(x)) y (f_q(x)), y convertimos estos factores en (p) y (q). La técnica de conversión entre enteros y polinomios es común, incluso para la multiplicación rápida de polinomios, pero lamentablemente pocos recursos describen cómo usarla para la factorización rápida de enteros. En particular, utilizamos los dígitos de la representación en base‑(B) del entero para establecer los coeficientes del polinomio. En la representación decimal normal, esto implica reemplazar potencias de 10 por potencias de (x), y luego convertir un polinomio a entero implica reemplazar potencias de (x) por potencias de 10. Matemáticamente, la representación en base‑(B) de un entero (a = \sum_i a_i B^i) corresponde al polinomio (f_a(x) = \sum_i a_i x^i), y la evaluación del polinomio (a = f_a(B)) lo convierte de vuelta a entero. Para las claves de manga corta, la base corresponde al tamaño del limb, y los bits cero adicionales en cada limb producirán polinomios con coeficientes excepcionalmente pequeños. Figura 2: Los enteros con bloques de bits 0 pueden representarse como polinomios con coeficientes pequeños. Este método de representar enteros con polinomios es útil porque el producto de evaluaciones (f_a(B) * f_c(B)) equivale a la evaluación del producto ((f_a*f_c)(B)). Toda evaluación solo reemplaza (x) por (B), de modo que no importa si esto ocurre antes o después de la multiplicación. Lo mismo ocurre con la suma.¹ Para un módulo RSA de manga corta (n) con limbs de (w) bits, podemos usar la representación en base‑(2^w) para hallar un polinomio (f_n(x)) con coeficientes excepcionalmente pequeños. Si (f_p(x)) y (f_q(x)) también tienen coeficientes excepcionalmente pequeños, entonces (f_n(x) = f_p(x) * f_q(x)). Obsérvese que, para factores primos generados correctamente, (f_p(x)) y (f_q(x)) típicamente tendrán coeficientes de (w) bits; por eso este ataque no funciona en general. Factorizar polinomios es fácil, así que podemos factorizar (f_n(x)) para obtener (f_p(x)) y (f_q(x)), luego evaluar esos factores en (2^w) para obtener (p) y (q). Esta es la versión básica del ataque, pero intencionalmente omito una idea clave necesaria para factorizar estos módulos del mundo real. Una explicación completa está al final de este blog. Figura 3: Los polinomios de forma especial pueden factorizarse para revelar la clave privada RSA. La correspondencia entre enteros y polinomios facilita la factorización de estos módulos de forma especial, pero curiosamente también ayuda a factorizar módulos RSA genéricos. El algoritmo General Number Field Sieve (GNFS) tiene el mejor rendimiento asintótico conocido, y su primer paso consiste en definir un campo numérico seleccionando un polinomio (f_n(x)) y un punto de evaluación (m) tal que (f_n(m) = n).²

Ingeniería inversa de la vulnerabilidad de CompleteFTP
Tras aplicar esta técnica a las claves que Hanno encontró, constatamos que los factores privados son efectivamente de manga corta: los factores primos poseen grandes bloques de bits no establecidos espaciados regularmente. Los banners SSH de los hosts con el segundo patrón indican que usan el software CompleteFTP, por lo que ingenierizamos inversamente una versión de prueba para determinar qué provocó las claves vulnerables. Las claves RSA generadas dinámicamente no presentaban el patrón de manga corta³, por lo que utilizamos la herramienta ILSpy para descompilar el código .NET del binario de demostración. Después de algo de ingeniería inversa, hallamos el error que generaba las claves de manga corta. La siguiente función llena el entero grande representado por bignumLimbs con un valor aleatorio de la longitud de bits deseada. Vea si puede identificar el problema.

public void genRandomBits(int bits) {
    // Calcular el número de limbs
    int numLimbs = bits / 32;
    // Reservar espacio para la salida del RNG
    byte[] array = new byte[numLimbs];
    // Llamar al RNG del sistema
    rngProvider.GetNonZeroBytes(array);
    // Copiar a los limbs del número grande
    Array.Copy(array, 0, bignumLimbs, 0, numLimbs);
    // Establecer el bit superior para asegurar la longitud correcta
    bignumLimbs[numLimbs - 1] |= 0x80000000;
    // Guardar la longitud
    dataLength = numLimbs;
}

Figura 4: Código descompilado de la función vulnerable genRandomBits en CompleteFTP. Se eliminaron varias ramas para mayor claridad y se añadieron comentarios.

Hay una discrepancia entre el tamaño de los limbs y el tamaño de la salida del RNG. Cada limb requiere 32 bits de material aleatorio, pero Array.Copy convierte implícitamente cada elemento de 8 bits de la salida del RNG en su propio elemento de los limbs del entero grande. La estructura repetitiva en las claves de manga corta se debe a que el problema afecta a cada limb, y los bits cero aparecen porque se copia un valor demasiado pequeño a cada limb. Esto coincide exactamente con el patrón de las claves criptoanalizadas. También descubrimos por qué nuestras pruebas dinámicas no generaron claves rotas: la función genRandomBits estaba compilada pero inaccesible en la versión más reciente. Las versiones antiguas utilizaban código de generación de claves escrito a medida que llamaba a esta función vulnerable, que más tarde fue refactorizada para usar las API criptográficas estándar de .NET. Ingenierizamos inversamente una versión anterior de CompleteFTP para buscar otras llamadas a genRandomBits y hallamos que la generación de claves DSA también estaba afectada. La clave privada DSA de 160 bits (x) se generaba previamente con esta función, y la clave pública y los parámetros incluyen un generador (g) y el objetivo (y = g^x). La clave privada es fácilmente recuperable, y una vez que supimos qué buscar, encontramos claves DSA vulnerables en la práctica también.⁴ Desde la versión v12.1.0, CompleteFTP genera claves RSA usando RSACryptoServiceProvider de .NET, y desde la v23.1.0 genera claves DSA usando la API DSA.Create.

Cómo se difundió la vulnerabilidad y cómo se contenió
La decisión de refactorizar el código de generación de claves para usar bibliotecas estándar redujo significativamente el alcance del impacto. Esto se refleja en los datos. La profesora Nadia Heninger dispone de una gran colección de escaneos SSH históricos y contemporáneos que utilizamos para encontrar firmas RSA SSH rotas, así que comprobé si incluían hosts con CompleteFTP. Típicamente había cientos de hosts con CompleteFTP en cada escaneo IPv4‑wide, y al alinear los escaneos históricos con la historia de versiones, la tendencia es clara. Figura 5: Con el tiempo, menos hosts con CompleteFTP ejecutan el software vulnerable, pero una fracción significativa sigue usando claves vulnerables. A partir de la introducción de la vulnerabilidad RSA en diciembre de 2016, hubo un aumento constante en el número de hosts con claves vulnerables, y una vez que el código RSA reescrito se lanzó en marzo de 2019, esta tendencia se detuvo inmediatamente. Sin embargo, aunque el número de hosts que ejecutan una versión afectada ha disminuido de forma constante desde entonces, la proporción de claves afectadas se ha estabilizado, coherente con clientes que actualizan su software regularmente pero generan sus claves solo una vez. El equipo de EnterpriseDT respondió rápidamente durante todo el proceso de divulgación. Para ayudar a estos usuarios, EnterpriseDT lanzó la v26.1.0 de CompleteFTP el 8 de mayo 2026; esta actualización verifica automáticamente si el sistema está usando una clave RSA o DSA vulnerable y alerta al usuario si la clave necesita regenerarse. También publicaron una herramienta independiente que hace lo mismo. Además, el sitio web de badkeys y su herramienta independiente ahora soportan la detección de claves RSA de manga corta vulnerables. En total, recuperamos claves privadas para 603 claves públicas RSA únicas y 74 claves DSA generadas por versiones vulnerables de CompleteFTP, y 26 claves RSA con el patrón de manga corta no identificado. Nuestras fuentes de datos están fuertemente sesgadas hacia claves RSA SSH, por lo que estos números no reflejan la prevalencia real.

Búsqueda de más claves de manga corta
Desafortunadamente, no disponemos de más información sobre el patrón de manga corta 1, ni sabemos si esa vulnerabilidad se extiende a otros tipos de claves. Es común que los algoritmos criptoanalíticos exploten el conocimiento de bloques irregularmente espaciados de bits conocidos (incluyendo ECDSA⁵ y RSA⁶), pero el espaciado regular de la fuga de manga corta añade nueva estructura, y pueden existir variantes poderosas de dichos algoritmos que exploten esta propiedad. Si este tipo de fuga aparece en dos implementaciones independientes de RSA, es probable que existan aún más ejemplos de claves de manga corta en la naturaleza. En este caso, el impacto de las vulnerabilidades es afortunadamente limitado, pero ilustra el poder de la investigación práctica. El proceso de usar vulnerabilidades conocidas para inspirar algoritmos más capaces y usar esos algoritmos para descubrir nuevas vulnerabilidades genera un bucle de retroalimentación potente en criptoanálisis. Nos ayuda a comprender cómo fallan los sistemas criptográficos reales en la práctica, y solo al observar cómo se rompen los sistemas aprendemos a hacerlos más seguros.

Agradecimientos
Gracias a Nadia Heninger por presentarme a Hanno y por permitir que usemos los escaneos SSH para este proyecto. esos escaneos consisten en datos históricos de Censys y de la Universidad de Michigan suministrados por Zakir Durumeric, y datos contemporáneos y scripts de análisis de Kevin He y George Sullivan.

Apéndice
Esta sección final está destinada a quienes desean implementar el ataque o demostrar que el ataque funciona. Dejé fuera detalles clave del post principal, pero las siguientes preguntas guiadas le ayudarán a cerrar esa brecha. Primero, aquí están los módulos completos para que los factorice. Son generados sintéticamente, pero siguen el mismo patrón que las claves en la práctica. Los factores de (n_2) se generaron llamando a genRandomBits(1024) en un bucle hasta que el resultado fue primo.

n_1=0xc889f7ef523b08e400000000000000014d2ee8284c7a03c000000000000000012c16eeaeab96ddc8000000000000000201036d671407a06600000000000000022f743377005a840d0000000000000001e8e3c0efdd8054ba000000000000000306ee98c677dfdf190000000000000002de525d2b1011ceae0000000000000424455c59eec3a0654500000000000003f8d762d68bcbe8cc3a00000000000000d31291f9aaa7e9a7d60000000000000337a82a59342aadff570000000000000295c495b3690a69b66c00000000000000d9c5e55654e9b14cba000000000000040f0f0f7d3bfdce03d6000000000000026b89ac77db000000000000000000036a77
n_2=0x40000049000014ac8000900e00010ec58000b17b8001e0720001be890002169f80029cd5000349190003cd4480037c8c000397660003b28300041021000418cb00058a210004c2708004924980053b8780051cbd8005ebe80006bb27800765e6800651478007f62300073949800860950008614d800863988008d103800884c100099a260009a6d90009578f0007e84300080db800072e59000724f10007c0ec0006ec6600062231000605930005ca4c000566cc0005da92000574dd00040bf1000457dc0004cfbe0004c5640003fe6d0003ada60002de110002cbb30002d5a6000243840001cdf40001a8a9000151be000113f4000101070000acdf000029e5

Si computa (f_{n_2}(x)) usando (B=2^{32}), algunos de los coeficientes son grandes. ¿Por qué? ¿Es cierto que todos los coeficientes de (f_p(x)) y (f_q(x)) son pequeños? ¿Existe un desplazamiento de bits (p \ll i) tal que (f_{2^i p}(x)) tenga coeficientes pequeños? Este es el truco clave necesario para convertir valores arbitrarios de manga corta en polinomios con coeficientes pequeños. Si (f_{2^i p}(x)) y (f_{2^j q}(x)) tienen coeficientes pequeños, ¿puede aún calcular (f_{2^i p}(x)*f_{2^j q}(x)) a partir de información pública? ¿Puede aún recuperar (p) y (q)? Si esta técnica de factorización de polinomios funcionara para cualquier (p) y (q), RSA quedaría roto. ¿Por qué la propiedad de manga corta es importante y por qué este método de factorización no funciona en general? ¿Cuáles son los límites? La propiedad de manga corta nos permite construir el producto (f_{2^i p}(x)*f_{2^j q}(x)), pero a menos que (f_{2^i p}(x)) y (f_{2^j q}(x)) sean irreducibles, la factorización podría dividirlo en más de dos términos. Demuestre que siempre existe una manera eficiente de recuperar (p) y (q) a partir de la factorización del polinomio. En términos matemáticos, la aplicación de evaluación es un homomorfismo de anillos.

↩︎ Más precisamente, las implementaciones modernas de factorización usan una generalización de esta técnica. Buscan un par de polinomios (f_0, f_1) donde (f_1) es lineal y (\text{Resultant}(f_0, f_1)) es un múltiplo pequeño de (n). En el caso especial donde (f_1) es mónico, entonces (\text{Resultant}(f_0, x - m) = n \Leftrightarrow f_0(m) = n).

↩︎ La generación de claves RSA de CompleteFTP en Linux tenía un problema separado donde el exponente privado se fijó a 65537 y el exponente público era grande. Lo divulgamos y el problema se solucionó en la v26.0.2. La versión Linux de la herramienta ofrece diferentes funcionalidades y es menos popular que la de Windows. Según datos de licencias de EnterpriseDT, creen que ningún usuario de producción está afectado por este asunto. Nuestros escaneos corroboran esta afirmación, ya que no encontramos claves en la práctica con esta propiedad.

↩︎ El intercambio de claves Diffie‑Hellman también usó la función vulnerable, pero con un exponente de 2048 bits. No es vulnerable, y creemos que los intercambios DH que usaron esta función siguen siendo criptográficamente seguros.

↩︎ Extended Hidden Number Problem and Its Cryptanalytic Applications de Hlaváč y Rosa considera el problema de nonces (EC)DSA con múltiples bloques de bits desconocidos en ubicaciones arbitrarias.

↩︎ Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits de Herrmann y May examina la factorización RSA cuando uno de los factores tiene múltiples bloques contiguos de bits desconocidos.