Peut-on casser une clé de cryptage en quelques millisecondes ?

La compréhension de la méthode nécessite de savoir ce qu'est, dans un processeur, l'unité de prédiction de branche (ou de branchement, ou encore de saut) et ce qu'on entend par attaque de type side channel.

L'unité de prédiction de branche

Voyons d'abord ce qu'est cette unité de prédiction de branche car c'est la cible de l'attaque qui a été publiée. Chaque instruction d'un programme informatique nécessite plusieurs cycles de l'horloge du processeur pour être traitée. Pendant longtemps ceci a fortement ralenti leur vitessevitesse de traitement car on était obligé d'attendre que l'exécution d'une instruction soit terminée avant que le processeur puisse lire et commencer à exécuter l'instruction suivante. Puis on s'est rendu compte qu'une modification de la structure des processeurs permettait de pallier largement ce problème en y introduisant une unité nouvelle appelée pipeline.

Le principe est le suivant : un pipeline est constitué d'une suite de registres (de cases en quelque sorte) que l'instruction parcourt au fur et à mesure de son exécution. Dès qu'une étape de cette exécution est franchie la première « case » devient disponible pour accueillir une deuxième instruction, puis lors de l'étape suivante, une troisième instruction, etc. Les instructions successives progressent donc dans le pipeline à la queue le leu au cours de leur exécution ce qui permet théoriquement d'atteindre rapidement une vitesse d'exécution de une instruction par cycle d'horloge (et même plus dans les processeurs modernes).

Tout le problème est en fait de savoir quelle va être l'instruction suivante à faire entrer dans le pipeline. En effet les programmes sont littéralement truffés de séries d'instructions qui s'exécutent en boucle et de branchements conditionnels.

Une boucle est par exemple du type :

• exécuter une série d'instructions de façon répétitive tant que telle condition n'est pas remplie.

Un branchement conditionnel est du type :

• si telle condition est remplie, aller vers telle partie du programme, sinon aller vers telle autre.

Autrement dit, à part quelques sections de programmes limitées où les instructions s'exécutent bien dans l'ordre de leur écriture, dans la majorité des cas l'instruction qui suit celle de rang n n'est pas l'instruction de rang n+1 mais une instruction qui peut se situer des centaines ou des milliers d'instructions après... ou avant dans le programme. Or pour savoir quelle est l'instruction suivante il faudrait que l'instruction en cours ait été complètement traitée et qu'on connaisse son résultat, ce qui n'est pas possible puisqu'elle est encore au début du pipeline.

Une telle situation devrait ruiner l'intérêt du principe du pipeline si une solution n'avait pas été trouvée. Le processeur contient en effet une unité de prédiction de branchement dont le rôle est d'évaluer quelle est l'instruction suivante la plus probable. Cette unité utilise divers mécanismes et, en particulier, un cache (branch target bufferbuffer) dans lequel est enregistré le comportement des séquences récentes exécutées par le programme. Comme une partie considérable du déroulement de la plupart des programmes consiste à exécuter de manière hautement répétitive les mêmes séquences d'instructions, l'unité de prédiction permet d'anticiper la bonne instruction dans un nombre satisfaisant de cas. Bien entendu il y a un certain nombre de fausses prédictions : dans ce cas la seule solution est de vider le pipeline et de recommencer. La longueur d'un pipeline détermine le nombre d'instructions qui peuvent être traitées simultanément, donc son efficacité. Inversement une fausse prédiction est bien plus catastrophique en terme d'efficacité sur un pipeline long (20 « cases » dans le cas du Pentium 4) que sur un pipeline court.

Qu'appelle-t-on attaque de type « side channel » ?

Tout le monde sait plus ou moins qu'une attaque de piratage classique va chercher à accéder à des données en exploitant une faille du système informatique. Ce peut être une négligence dans la sécurisation de l'ordinateur ou une vulnérabilité due à un défaut du système d'exploitation ou d'un programme fonctionnant sur l'ordinateur. Mais il y a des situations où il est impossible d'accéder aux données elles-mêmes pour des raisons diverses. Une attaque par side channel va donc chercher à espionner le comportement matériel de l'ordinateur pour essayer d'en tirer des informations sur les données qu'il manipule. C'est ainsi par exemple qu'il a été possible de capter à distance le rayonnement électromagnétique émis par un écran pour reconstituer les données qu'il affichait. En entrant plus avant dans le fonctionnement d'un ordinateur, par exemple avec un programme espion, il est possible de tirer des informations sur les données traitées par un processeur en surveillant les temps d'exécution de certaines séries d'instructions ou les variations de consommation électrique.

La cible de l'attaque

Jean-Pierre Seifert a choisi de s'attaquer à une clé RSA telle qu'elle est implémentée dans Open SSLSSL (une solution couramment utilisée), fonctionnant sur un ordinateur équipé d'un processeur IntelIntel Pentium 4. Il n'est pas possible d'accéder directement aux données permettant de retrouver la clé de chiffrement car les processus et les espaces de mémoire qu'ils utilisent sont soigneusement cloisonnés. Il reste des possibilités d'attaque par side channel.

Les concepteurs des logiciels de sécurité savent parfaitement qu'il est possible de tirer des informations sur les données manipulées en exploitant les temps d'exécution des calculs portant sur la clé de chiffrement. Aussi on utilise des algorithmes dont le temps d'exécution est très peu affecté par la nature des données traitées, ou contenant des instructions fictives qui ne changent rien au résultat, mais qui ont pour rôle de modifier arbitrairement les temps de calcul. De plus, comme le calcul s'exécute dans un ordinateur en même temps qu'une multitude de tâches plus ou moins simultanées, les informations sur les duréesdurées qu'on peut recueillir sont fortement « bruitées » par l'impact de tous les traitements exécutés par le processeur. Pour tirer des informations de l'observation des temps de calcul il faudrait exécuter des milliers de mesures et traiter les résultats par des méthodes statistiques pour extraire des informations significatives du bruit de fond. C'est pourquoi il est assez facile de se protéger contre ce type d'attaque.

Mais le cloisonnement évoqué ci-dessus n'est pas parfait : en effet il existe quelques ressources qui sont partagées par tous les processus qui utilisent le microprocesseurmicroprocesseur, et c'est le cas de l'unité de prédiction de branche. L'attaque inventée par l'équipe de Jean-Pierre Seifert cible le cache de cette unité. Précisons bien que ce cache ne contient aucune donnée manipulée dans le calcul cryptographique. Par contre c'est lui qui enregistre les informations sur les branchements effectués durant les calculs et qui serviront pour les prédictions ultérieures (ce sont ce qu'on appelle des méta-données). Comme cette unité de prédiction est partagée par tous les processus n'importe quel programme espion peut interférer avec les informations stockées, quel que soit le niveau de privilège attribué au programme espion ou au programme de cryptographiecryptographie ! Ce cache constitue donc un point faible non protégé.

Principe de l'attaque

Un programme espion fonctionne en continu de manière cyclique en exécutant toujours les mêmes branches de son algorithme. S'il est convenablement conçu il va donc remplir le cache de l'unité de prédiction avec des adresses de branchement qui seront valables pour le cycle suivant du programme (la prédiction sera toujours juste). Si l'ordinateur exécute alors l'algorithme de cryptage il va avoir recours à l'unité de prédiction et il modifiera éventuellement le contenu de son cache.

Le principe de l'algorithme RSAalgorithme RSA est le suivant : il prend successivement tous les bits de la clé ; si le bit est 0 il fait une simple élévation au carré de la donnée traitée ; si le bit est 1 il fait une élévation au carré suivie d'une multiplication. Selon la valeur du bit le branchement ne sera donc pas le même et cette information s'enregistrera dans le cache. Le processus espion tournant en parallèle détectera que certaines information de branchement auront été modifiées dans le cache en fonction de la valeur du bit car, comme elles ne correspondent pas à celles du processus espion il y aura alors une fausse prédiction pour une de ses étapes et celle-ci sera allongée par la nécessité de vider le pipeline.

L'article n'entre pas dans les détails mais le principe est que selon que le bit de la clé est 0 ou 1 le programme espion sera ralenti ou non. La mesure du temps d'exécution du programme espion permet donc de connaître la valeur du bit de la clé qui vient d'être traité. Bien entendu d'autres processus pourront interférer et brouiller cette détection. Mais une analyse précise de la structure de l'unité de prédiction de branche a permis à Jean-Pierre Seifert et ses collaborateurs de réaliser un programme espion capable de discriminer très efficacement les informations utiles du bruit de fond. Certes beaucoup de tentatives d'espionnage seront encore brouillées mais si une tentative tombe pendant une période favorablement il sera possible en une seule lecture (donc en quelques millisecondes) de récupérer la valeur de la plupart des bits de la clé alors qu'auparavant il fallait traiter statistiquement des milliers de tentatives toutes très fortement brouillées.

Les auteurs de l'article annoncent que sur 10 tentatives indépendantes portant sur la même clé l'une d'entre elle a permis de lire d'un seul coup 508 des 512 bits de la clé.

Importance et limites de la technique

Le plus important dans une publication scientifique est parfois ce qu'elle ne dit pas. Dans le cas présent il est légitime de s'étonner du fait que l'article ne mentionne qu'une expérience faite de 10 tentatives dont une s'est révélée efficace, sans avoir permis toutefois de casser complètement la clé. Or on s'attendrait normalement à trouver un tableau montrant le résultat de nombreuses expériences avec le pourcentage de succès en fonction du nombre de bits récupérés. Le fait que l'article soit muet sur ce point laisse penser que seul un résultat exceptionnellement bon est cité, à côté d'une multitude d'échecs passés sous silence.

Il faut noter aussi qu'on utilise plus souvent des clés de 1024 bits pour lesquelles le pourcentage de bonne récupération des bits est probablement très inférieur. Enfin, même pour une clé de 512 bits les auteurs ont dû affaiblir certaines caractéristiques de l'algorithme de cryptage afin d'obtenir ce résultat partiel.

Ce type d'attaque nécessite de connaître de façon précise l'algorithme de cryptage (et ce qui a été mis au point pour l'implémentation de RSA dans Open SSL nécessite certainement des modifications notables pour d'autres implémentations). De même le programme espion est étroitement dépendant de la structure de l'unité de prédiction de branche et il est probable qu'un programme espion mis au point pour le Pentium 4 devrait être modifié pour un processeur AMD, sans parler du fait que rien n'est dit sur les dual coresdual cores qui vont se généraliser.

Toutefois si ceci tempère considérablement le sensationnalisme de certains articles parlant de cet exploit, il ne faut pas sous-estimer la menace potentielle que cette voie d'attaque pourrait représenter à l'avenir, d'autant qu'elle pourrait concerner d'autres algorithmes utilisés dans les programmes de cryptographie, qui reposent également sur des branchements différents selon la valeur traitée. Cette technique est en effet totalement insensible à toutes les méthodes classique de masquage utilisées dans les programmes de cryptographie et au niveau de privilège accordé au programme espion et au programme de cryptographie.

Comme protection on avance la possibilité de désactiver l'unité de prédiction durant les traitements cryptographiques, mais ceci ferait chuter fortement la vitesse de traitement. D'autres estiment que les traitements cryptographiques devraient être assurés par un processeur spécialisé différent de celui qui traite les autres processus, mais ceci ne peut être envisagé que dans un avenir lointain. D'autres enfin disent que la structure des processeurs devraient être radicalement modifiée, mais on voit mal comment.

On peut toutefois rassurer tous ceux qui utilisent les paiements sécurisés en ligne : ces opérations sont généralement assurées par un serveurserveur distinct du ou des serveurs plus généralistes (par exemple le serveur web) de la société, et on voit mal comment il serait possible d'y installer un programme espion à moins d'une grossière négligence de l'administrateur du réseau. Enfin, pour tous les autres usages (militaires ou autres) de la cryptographie, il est bien évident que les ordinateurs chargés de ce type de tâches sont particulièrement protégés contre tout type d'intrusion !

En aucun cas ce type d'attaque ne peut trouver la clé d'un document crypté qui tomberait entre des mains hostiles : le programme espion peut simplement essayer de trouver la clé qui est en train d'être utilisée sur un ordinateur qui aurait été infecté préalablement.