Análisis de fallas en la firma de rsa sendero de bits blog Bitcoin para iniciar sesión

Esta primavera y verano, como pasante en Trail of Bits, investigué ataques de fallas de modelado en firmas RSA. Observé una optimización de la firma de RSA que utiliza el Teorema de Remanencia chino (CRT) y las fallas de cálculo inducidas que revelan llaves privadas. Analicé los ataques de fallas en un nivel bajo en lugar de en un contexto matemático. Después de analizar tanto un programa de juguete como la implementación mbed TLS de RSA, identifiqué bits en la memoria que filtran claves privadas cuando se vuelcan. El proceso de firma con RSA-CRT

Normalmente, un RSA firma la operación usaría este algoritmo: s = m d (mod n). Aquí, s representa la firma, el mensaje, el exponente privado yn la clave pública. Este algoritmo es efectivo, pero cuando los números involucrados aumentan al tamaño necesario para la seguridad, el cálculo comienza a tomar un tiempo extremadamente largo. Por esta razón, muchas bibliotecas de criptografía usan el El resto chino Teorema (CRT) para acelerar el descifrado y la firma. El CRT divide el cálculo grande único en dos más pequeños antes de unir sus resultados.

Luego calculamos dos firmas parciales, cada una utilizando uno de estos dos números; la primera firma parcial, s1, es igual a m dp (mod p), mientras que la segunda, s2, es igual a m dq (mod q). Se calculan las inversas de p (mod q) y q (mod p), y finalmente, las dos firmas parciales se combinan para formar la firma final, s, con s = (s1 * q * qInv) + (s2 * p * pInv) (mod n). El ataque de falla

Comencé escribiendo un simple programa de juguete en C para llevar a cabo la firma de RSA usando el Teorema del resto chino. Este programa no incluyó relleno ni controles, utilizando libros de texto RSA para firmar números bastante pequeños. Usé un depurador para modificar manualmente una de las firmas parciales y producir una firma final con fallas. Escribí un programa en Python para usar esta firma fallada para calcular las claves privadas y descifrar con éxito otro mensaje cifrado. Traté de alterar los datos en diferentes etapas del proceso de firma para ver si aún podía extraer las claves privadas. Cuando me sentía cómodo llevando a cabo estos ataques de fallas a mano, comencé a automatizar el proceso. Volteando los bits con Manticore

Utilicé Ninja binario para ver el desmontaje de mi programa e identificar las ubicaciones de memoria de los datos que me interesaban. Cuando intentaba resolver las claves privadas, sabía dónde buscar. Luego, instalé y aprendí a usar Manticore, el binario análisis herramienta desarrollada por Trail of Bits con la que iba a realizar los ataques de fallas.

Escribí una secuencia de comandos de Manticore que iteraría a través de cada byte de memoria consecutivos, alteré una instrucción volteando un bit en ese byte y ejecuté el programa de firma de RSA. Para cada ejecución que no dio como resultado un bloqueo o un tiempo de espera, utilicé la salida para tratar de extraer las claves privadas. Los comprobé con las claves correctas al intentar descifrar otro mensaje correctamente. Con todos estos datos, generé un archivo CSV de los resultados intermedios y finales de cada lanzamiento de bits, incluido el firmas parciales, las claves privadas, y si las claves privadas eran precisas.

Este tipo de automatización ofrece una aceleración masiva en el desarrollo de exploits para vulnerabilidades como esta, ya que una vez que simplemente describes la vulnerabilidad a Manticore, obtienes una lista completa de formas de explotarla. Esto es particularmente útil si puede introducir algún error impreciso (por ejemplo, al utilizar Rowhammer), ya que puede encontrar grupos de bits que, al voltear, filtran una clave privada. Faulting mbed TLS

Una vez que tuve el archivo de resultados de lanzamiento de bits para mi programa de juguete, busqué una biblioteca criptográfica real para atacar. Me decidí por mbed TLS, una implementación que se usa principalmente en sistemas integrados. Debido a que era mucho más complejo que el programa que había escrito, pasé un tiempo mirando el código fuente TLS de mbed para tratar de comprender el proceso de firma de RSA antes de compilarlo y observar el binario desmontado usando Ninja binario.

Una diferencia clave entre mbed TLS y mi programa de juguete era que las firmas que utilizaban mbed TLS estaban rellenas. los ataques de fallas Intentaba modelar y solo se aplica al relleno determinista, en el que un mensaje dado siempre dará como resultado el mismo valor acolchado, y no esquemas probabilísticos. Aunque mbed TLS puede implementar una variedad de diferentes esquemas de relleno, analicé la firma de RSA usando PKCS # 1 v1.5, una alternativa determinista al esquema de relleno de PSS más complejo y aleatorizado. De nuevo, utilicé un depurador para ubicar los datos objetivo. Cuando supe de qué ubicaciones de memoria estaría leyendo, empecé a fallar en una de las firmas parciales y produje una firma incorrecta.

Pronto me di cuenta, sin embargo, de que había algunos controles de tiempo de ejecución para prevenir un ataque de falla del tipo que estaba tratando de realizar. En particular, dos de las comprobaciones, si fallan, detendrían la ejecución y mostrarían un mensaje de error sin crear la firma. Usé el depurador para omitir los cheques y producir la firma fallada que estaba buscando.

Tal como lo hice con el programa de juguetes, comencé a tratar de automatizar los ataques de fallas e identificar las volteadas de bits que filtrarían las claves privadas. Para acelerar el proceso, escribí un guión GDB en lugar de usar Manticore. Encontré pequeños cambios que me permitirían eludir ambos controles que normalmente evitarían la creación de una firma con fallas. Usé GDB para alterar ambas instrucciones de memoria. En un proceso idéntico al programa de juguete, también volqué un bit en una dirección de memoria determinada. Luego usé Python para recorrer cada byte de memoria, invocar este script e intentar extraer las claves privadas, comprobando nuevamente si eran correctas al intentar descifrar un mensaje conocido. Recopilé las claves privadas resueltas y escribí los resultados en un archivo CSV de todos los cambios de bits.

banner