Ataques a smart cards: side channel analysis (I)
Volvemos a darle un poquito al tema de las smart cards ;-). Antes de continuar, sería recomendable que quien no conozca prácticamente nada sobre smart cards lea los posts anteriores al respecto:
- Introducción
- Normas y comunicación
- Clasificación de ataques
Pese a que hay mucha información al respecto en Internet y en libros, no sé si la hay en español así que espero que siga resultando útil/interesante a la gente :-).
En este post vamos a ahondar un poco más en uno de los ataques más famosos sobre smart cards. Se trata del llamado Side Channel Analysis o SCA ( en español supongo que se traduciría como análisis de canales adyacentes o algo similar) que consiste en analizar datos procedentes de la smart card por canales alternativos.
Como ya vimos, una smart card se comunica con el exterior únicamente mediante una interfaz serie a través de uno de sus contactos. En cambio, como cualquier dispositivo electrónico, estas tarjetas 'sufren' algunos fenómenos físicos que permiten obtener información. Veamos los principales canales utilizados:
- Información temporal: realizando mediciones de lo que tardan distintas operaciones.
- Consumo: midiendo el consumo de potencia del dispositivo también es posible determinar qué está haciendo.
- Radiaciones electromagnéticas: como todos sabemos, cualquier movimiento de electrones genera un campo electromagnético, y nuestras tarjetitas no iban a ser menos.
En este primer post sobre side channel analysis vamos a ver un ejemplo de información temporal que nos puede ayudar a romper un algoritmo considerado seguro como RSA debido a una 'mala' implementación. Para ello primero (en la página extendida para no alargar mucho la portada) explicaré brevemente cómo funciona RSA, la implementación base que usaremos y luego el problema que tiene y cómo podríamos solucionarlo.
El algoritmo RSA
RSA es un algoritmo de cifrado de clave pública que basa su fortaleza en la dificultad computacional de factorizar grandes números comparada con la sencillez de realizar un producto entre esos factores.
La generación de claves RSA es como sigue:
- Elección de dos números primos de tamaño similar, p y q (y no es conveniente que estén demasiado cerca).
- Cálculo de n=p·q.
- Elección de un valor e arbitrario. Se usa mucho 65536, también conocido como F4.
- Cálculo de d tal que e·d=1 (mod phi(n) ). Aquí phi(n) es el totient de Euler, que indica la cantidad de números coprimos (es decir, sin factores comunes) con n entre 1 y n-1. En este caso, es conocido que phi(n)=(p-1)(q-1) (si alguien está interesado seguro que puede encontrar una demostración 😉 ).
A partir de aquí, la clave pública consta del módulo n y del valor del exponente público e, y la clave privada del módulo n y del exponente privado d. Ni que decir tiene que d no debe ser conocido más que por el propietario de la clave y que p y q deberían eliminarse o mantenerse en lugar seguro ;-).
El cifrado de un mensaje m en RSA se realiza como c= m^e ( mod n ), y el descifrado como m'=c^d = m^(d·e) = m (mod n) debido al teorema de Euler.
No me voy a extender más con RSA, quien esté interesado en más detalles no le resultará excesivamente complicados encontrarlos.
Implementación de la exponenciación modular con productos y cuadrados
Para explicar esto voy a hacer uso de un pequeño ejemplo ya que seguro que resulta más sencillo. Vamos a ver cómo realizaríamos el cálculo 2^17 (mod 19) de forma sencilla sin tener que recurrir a números enormes (como 2^17 😉 ).
En primer lugar, reescribimos la potencia tal que: 2^17= 2^16·2 = (2^8)^2 · 2 = ... = ((((2^2)^2)^2)^2)·2. En segundo lugar, realizamos cada cálculo intermedio módulo 19:
2^2 = 4
2^4 = (2^2)^2 = 4^2 = 16
2^8 = (((2^2)^2)^2 = 16^2 = 256 = 9
2^16 = 9^2 = 81 = 5
2^17 = 2·5 = 10
Si alguien no se fía y tiene Mathematica que ponga PowerMod[2,17,19], o en Matlab mod(2^17,19) ;-).
Viendo lo de arriba quizás no os diga nada, pero resulta que si pasas 17 a binario tienes 10001, y si se compara con lo anterior se ve que cuando el exponente tiene un 1 en binario, se hace un cuadrado y una multiplicación, y cuando tiene un 0 se hace un cuadrado solamente.
Así pues, el algoritmo sería algo como:
s=x
for i in 1 to n
s=s^2 (mod N)
if( di == 1 )
s= s*x;
end for
return(s)
Donde d=(d0,d1,d2,...,dn) es la representación binaria de d, con d0 el bit de mayor peso y siempre igual a 1.
Problema de esta implementación
Claramente, esta implementación tiene el problema de que dependiendo de si el bit de la clave es 1 o 0 se va a realizar un cuadrado o un cuadrado más una multiplicación, con lo cual habilita un análisis de tiempos. Así pues, si medimos el consumo de potencia o la radiación electromagnética y comparamos el tiempo de los distintos picos que aparecen correspondientes al cifrado RSA es posible determinar qué bits de la clave son 0 y qué bits son 1.
He estado mirando por ahí a ver si encontraba imágenes al respecto y no he encontrado nada (o no estoy en muy buenas condiciones para buscar), así que os remito a las transparencias de Erik Poll sobre el tema en la página 32 si estáis interesados.
Posibles contra medidas
Es obvio que para evitar este ataque habría que intentar que la clave no estuviera tan relacionada con el tiempo de ejecución. Una posible idea sería realizar el cálculo completo siempre y elegir el resultado en función del bit de la clave, de forma que siempre se realizaran las mismas operaciones.
Otra opción es realizar la multiplicación exponencial con grupos de bits en lugar de bit a bit, precalculando los factores de ponderación necesarios para cada resultado. De esta forma se dificulta la recuperación de la clave, aunque no sé hasta qué punto... lo que si sé es que si miras una traza de consumo realizada con esta técnica es difícil determinar cuando los dos bits eran 00, 01, 10 o 11 al menos a simple vista como en el caso expuesto.
Otra opción ante el timing analysis es lo que llaman RSA Blinding, aunque no ante este ataque en concreto. Se basa en calcular un valor aleatorio r para cada texto cifrado recibido, calcular su inversa, y realizar el descifrado como (r^e·c)^d (mod n). De esta forma se tiene r·m (mod n), y multiplicando por la inversa de r obtenemos m.
Como he dicho, esto no sirve de nada si se realiza la potencia de la forma expuesta, pero sirve como protección ante otros tipos de análisis de tiempos que funcionan incluso sin usar esta implementación.
PD: Si has llegado aquí mereces un permio 😆 Otro día más sobre SCA, concretamente Power Analysis 🙂
Leave a comment
You must be logged in to post a comment.