Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Fault injection: Ataque a RSA-CRT

Después de mucho tiempo en el letargo, volvemos a la carga con un ejemplo de inyección de fallos en el algoritmo RSA empleando el Teorema Chino del Resto ( Chinese Remainder Theorem ). Este teorema permite que si tenemos un par de ecuaciones tal que

Con p y q primos, se pueda calcular x ( mod p·q ) a partir de ellos y dos resultados auxiliares.

Por ello, el algoritmo RSA se puede dividir de una potencia modular con un módulo enorme a dos operaciones modulares de módulos de tamaño aproximadamente la mitad del primero. Con esto se consigue una mejora de rendimiento, lo cual es fundamental en aplicaciones con recursos limitados como smart cards. Además, los resultados auxuliares pueden ser precalculados, con lo cual se pueden cargar en la tarjeta al mismo tiempo que la clave y reducir la carga.

Sin embargo, en estos entornos es posible inyectar fallos tal y como expliqué en esta entrada. ¿Y qué tiene esto que ver con las implementaciones de RSA usando el CRT? Como vamos a ver, mucho 🙂

En primer lugar, supongamos que realizamos una firma mediante RSA-CRT en un dispositivo embebido. Entonces, el dispositivo calcula mediante el cálculo de y , y realiza la combinación apropiada para obtener . Esto se hace mediante la fórmula , donde a y b son los resultados antes mencionados que se calculan mediante las siguientes fórmulas:

a= 0 (mod p), a=1 (mod q)

b=1 (mod p), b=0 (mod q)

Así pues, supongamos que ahora realizamos un ataque mediante glitching e introducimos un fallo en el cálculo de , de forma que ya no cumple . Entonces, obviamente el resultado es incorrecto, pero... ¿podemos aprovecharlo?

Poniendo todas las ecuaciones que tenemos juntas, vemos que la diferencia entre el valor correcto c, y el valor en el que hemos inducido nuestro fallo, c', cumple lo siguiente:

Por tanto, si calculamos el máximo común divisor de c-c' y n=p·q, este caso nos daría el valor de q ya que es el único factor común entre ambos, pues c-c' es múltiplo de q pero no de p. Este cálculo se puede hacer de forma eficiente mediante el algoritmo de Euclides.

Así pues, mediante un poco de matemáticas y una inyección de un fallo en un resultado resulta muy sencillo obtener la clave RSA. Esto deja clara la necesidad de proteger los dispositivos embebidos ante este tipo de ataques.

Este ejemplo ha sido sacado de las notas de Henk Van Tilburg para Cryptography 1 .