Crypto Series: Differential Fault Analysis by examples
So, after more than a year without writing anything here, I was bored today and thought it would be nice to share a new piece on attacking cryptographic implementations here 🙂
Differential Fault Analysis (DFA) attacks are part of what is known as fault injection attacks. This is, they are based on forcing a cryptographic implementation to compute incorrect results and attempt to take advantage from them. With fault injection attacks (also often called active side channel attacks) one can achieve things like unauthenticated access to sensitive functionality, bypassing secure boot implementations, and basically bypassing any security checks an implementation performs.
With DFA attacks, one is able to retrieve cryptographic keys by analyzing correct/faulty output pairs and comparing them. Of course, this assumes you are able to inject faults somehow... which is often true in hardware implementations: gaming consoles, STBs, smart cards, etc. At the software level, one can achieve similar things by debugging the implementation and changing data or by patching instructions... but this is something we have been doing for a long time, haven't we? 🙂 I often say that fault injection attacks are the analog version of 'nopping' instructions out in a program, although we often do not know exactly what kind of faults we are injecting (i.e. we often miss a fault model, but we still successfully attack implementations in this way).
There are ways to protect against this kind of attack as an application programmer, but this is not the objective of this post. In the remainder of this post, I will explain two powerful DFA attacks on two modern cryptographic algorithms: RSA and (T)DES. For some information on protecting from these attacks as a programmer, take a look at these slides. If there is some interest, I will outline the most common techniques to perform fault attacks in a future post.
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 🙂