Attaque temporelle

En cryptanalyse, une attaque temporelle consiste à estimer et analyser le temps mis pour effectuer certaines opérations cryptographiques dans le but de découvrir des informations secrètes. Certaines opérations peuvent prendre plus de temps que d'autres et l'étude de ces informations temporelles peut être précieuse pour le cryptanalyste. La mise en œuvre de ce genre d'attaque est intimement liée au matériel ou au logiciel attaqué.

Des attaques temporelles peuvent aussi se faire à distance, via un réseau. L'observation des délais dans un système est en général soumise à des perturbations aléatoires. Ceci est d'autant plus vrai que l'observation se fait via un réseau. La plupart des attaques temporelles demandent que l'adversaire connaisse les détails de l'implémentation. Cependant, ces attaques peuvent aussi servir à identifier les algorithmes employés et faire de l'ingénierie inverse.

Les algorithmes d'exponentiation modulaire sont coûteux, le temps d'exécution dépend linéairement du nombre de bits à '1' dans la clé. Si connaître le nombre de '1' n'est pas une information toujours suffisante pour trouver la clé, le recoupement statistique entre plusieurs chiffrements avec cette clé peut offrir de nouvelles possibilités au cryptanalyste.

En 2003, Boneh et Brumley , travaillant tous les deux à Stanford, ont démontré une attaque pratique contre des serveurs SSL. Leur cryptanalyse est basée sur des vulnérabilités découvertes dans les implémentations du théorème des restes chinois. L'attaque fut toutefois menée à travers un réseau de taille limitée mais elle montrait que ce type d'attaque était sérieuse et praticable en l'espace de quelques heures. Les implémentations furent améliorées pour limiter les corrélations entre la clé et le temps de chiffrement.

Les chiffrements par bloc sont en général moins sensibles aux attaques temporelles, la corrélation entre la clé et les opérations étant plus limitées, mais celles-ci existent quand même. La plupart reposent sur les temps mis pour accéder aux différentes tables (par exemple les S-Boxes).

En 2005, Daniel J. Bernstein a démontré qu'une attaque contre une implémentation vulnérable d'AES était possible à partir du cache des processeurs modernes des PC (AMD ou Intel)^[1]. Bernstein reproche au NIST d'avoir négligé ces problèmes lors du concours AES, il ajoute que le NIST s'est trompé en partant du principe que le temps d'accès aux tables était constant.

En 1996, Paul Kocher exhibe une faille dans une implémentation du calcul de l'exponentiation modulaire^[2]. L'algorithme consiste à calculer ${\displaystyle R=y^{x}}$ mod ${\displaystyle n}$, avec ${\displaystyle n}$ public, et ${\displaystyle y}$ obtenu par espionnage (ou une quelconque autre manière). Le but de l'attaquant est de trouver la valeur de ${\displaystyle x}$ (la clé secrète).

Pour que cette attaque se déroule correctement, la 'victime' doit calculer ${\displaystyle y^{x}}$ mod ${\displaystyle n}$ pour plusieurs valeurs de ${\displaystyle y}$, où ${\displaystyle y}$, ${\displaystyle n}$ et le temps de calcul (à un grain suffisamment fin) sont connus de l'attaquant.

Voici l'algorithme, avec ${\displaystyle w}$ le nombre de bits de longueur de ${\displaystyle x}$.

Soit ${\displaystyle s_{0}=1}$

Pour ${\displaystyle k}$ allant de ${\displaystyle 0}$ à ${\displaystyle w-1}$ faire

Si le ${\displaystyle k}$-ème bit de ${\displaystyle x}$ vaut 1

Alors ${\displaystyle R_{k}=(s_{k}\times y)}$ mod ${\displaystyle n}$

Sinon ${\displaystyle R_{k}=s_{k}}$

${\displaystyle s_{k+1}=R_{k}^{2}}$ mod ${\displaystyle n}$

FinPour

Renvoyer (${\displaystyle R_{w-1}}$)

On remarque que selon la valeur du bit, on calcule soit ${\displaystyle (s_{k}\times y)}$ mod ${\displaystyle n}$ soit rien (en fait, on effectue l'affectation ${\displaystyle R_{k}=s_{k}}$, mais en termes de temps de calcul c'est négligeable). Donc si on peut observer suffisamment finement le temps d'exécution de l'algorithme, on peut déduire la valeur du bit en fonction du temps de calcul, et ainsi recouvrer totalement le secret en procédant par itération sur les bits ${\displaystyle 0\ldots b-1}$ de l'exposant.

Cette attaque peut être contrée en modifiant l’implémentation pour que tous les calculs soient effectués d’office, quels que soient les bits de la clé :

Soit ${\displaystyle s_{0}=1}$

Pour ${\displaystyle k}$ allant de ${\displaystyle 0}$ à ${\displaystyle w-1}$ faire

Soit ${\displaystyle temp=(s_{k}\times y)}$ mod ${\displaystyle n}$

Si le ${\displaystyle k}$-ème bit de ${\displaystyle x}$ vaut 1

Alors ${\displaystyle R_{k}=temp}$

Sinon ${\displaystyle R_{k}=s_{k}}$

${\displaystyle s_{k+1}=R_{k}^{2}}$ mod ${\displaystyle n}$

FinPour

Renvoyer (${\displaystyle R_{w-1}}$)

Cette fois-ci, le temps de calcul ne dépend aucunement de la valeur de la clé (seule la source de l’affectation à ${\displaystyle R_{k}}$ change), l’attaque temporelle devient donc impossible sur ce fragment de code. Cela rend certes plus long le temps de calcul total, mais, dans le contexte qui nous intéresse, l’impératif de sécurité est incommensurablement plus important que celui de la vitesse.

• [Kocher 1996] (en) Paul Carl Kocher, « Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems », Advances in Cryptology, Springer, lecture Notes in Computer Science, vol. 1109 « CRYPTO '96, 16th Annual International Cryptology Conference »,‎ 1996, p. 104–113 (ISBN 978-3-540-61512-5, ISSN 0302-9743, DOI 10.1007/3-540-68697-5_9, lire en ligne [PDF]).

• [Bernsein 2005] (en) Daniel J. Bernstein, « Cache-timingattacks on AES » [PDF], sur cr.yp.to, 14 avril 2005.

• Portail de la cryptologie