On nous parle d'un "article encore confidentiel". Et si c'est confidentiel, c'est que ça doit être une véritable bombe cette découverte ! Sauf que trois coups de Googling plus tard, on le tient. "On the Power of Simple Branch Prediction Analysis" par Onur Aciicmez, Cetin Kaya Koc et Jean-Pierre Seifert est en fait disponible en intégralité sur le très confidentiel site de l'IACR... Au moins, c'est bien pour nous, on va pouvoir vérifier si l'apocalypse numérique est bien pour demain et s'il va falloir envisager une réorientation professionelle très prochainement.

Première observation, évidente puisque même le journaliste l'a vue : ça parle de "Branch Prediction analysis" (BPA), technique connue visant à étudier les prédictions faites par le cache d'un processeur sur les branchements (if - then - else) du code qu'il exécute pour essayer d'en déduire d'abord ce qu'il est en train de faire et ensuite les valeurs qu'il manipule. Ça ne vous rappelle rien ? Et si je vous dit Hyper-Threading, ça vous aide plus ? L'article de Colin Percival se base sur l'étude du cache. Pour faire à peu près la même chose. Pourquoi tant de foin cette fois-ci ? L'optimisation proposée serait-elle si révolutionnaire ?

Seconde observation, qui semble avoir complètement échappé à notre reporter : l'exploitation est complètement locale. Ceci qui tend à sérieusement limiter le contexte d'exploitation qui, on le sent bien venir, est déjà tendu. Ce point a-t-il été volontairement omis ? On est en droit de se poser la question, dans la mesure où on se rend bien compte que l'effet d'annonce de l'article en prendrait un coup. Il est tout de même un peu surprenant que des gens aussi compétents que Jacques Stern ou Jean-Jacques Quisquater ne l'aient pas mentionné. Pour autant, ce ne serait pas la première fois qu'un journaliste omettrait un "détail" pour mieux emballer son sujet, d'autant que c'est soufflé à demi-mot par la mention d'un programme espion. Mais si effectivement la technique est aussi efficace qu'annoncé, à savoir récupérer une clé de 512 bits du premier coup, ça laisse entrevoir des perspectives très intéressantes pour les keyloggers et autres backdoors, et on lui pardonnerait volontiers l'écart.

Un système multi-tâche, comme son nom l'indique, traite plusieurs tâches en même temps, alors que le processeur, cœur du système, ne peut exécuter qu'une seule opération à la fois. Du coup, si vous exécutez des calculs mathématiques, genre, au hasard, des multiplications, tout autre programme essayant de faire la même chose s'en trouvera légèrement ralenti. L'observation fine du temps d'exécution vous renseignera donc sur les autres occupations du processeur. C'est un principe vieux comme le monde, ou du moins comme les systèmes d'exploitation multi-tâche. Dans le cas de la BPA, un peu plus compliqué, on va s'attacher à étudier l'efficacité du prédicteur de branchement pour les calculs effectués en parallèle par le système, mais grosso modo, l'idée de base reste la même : introduire un peu de concurrence pour perturber le système et observer le résultat. Or une bonne observation repose sur la capacité de l'attaquant à exécuter du code en parallèle sur la machine d'une part et d'autre part à effectuer des mesures de temps précises. Et là, ça commence à devenir plus compliqué, parce qu'à moins d'être physiquement devant la machine avec un chronomètre, on va avoir du mal, même beaucoup de mal. Différence entre le temps réel et le temps processus, concurrence d'accès à l'horloge système, problèmes de précision, bref, pleins d'excellentes raisons qui rendent la tâche hardue. Mais bon, si ça marche du premier coup...

Les auteurs attaquent donc l'implémentation RSA de OpenSSL, la célèbre bibliothèque cryptographique libre utilisée à peu près partout, même chez pleins de gens qui s'en défendent[1] pour récupérer une clé de 512 bits. Hummm. 512 bits seulement ? C'est un peu court jeune homme... Aussi loin que je me souvienne, j'ai toujours entendu dire que 512 bits, c'était trop court et qu'il fallait utiliser au minimum 1024 bits et aujourd'hui du 2048 bits. Ça doit donc bien faire une dizaine d'années qu'on le sait, même si les certificats de cette taille sont restés très longtemps sur le marché[2]. Mais pourquoi diable seulement 512 bits et pas 1024 alors que la longueur de clé ne devrait pas être un facteur décisif ? La question rest entière et laisse planer un sérieux doute sur la montée à l'échelle de la technique. Toujours est-il qu'une chose est sûre : le OpenSSL utilisé pour les expérimentations n'est pas la version standard fournie avec l'Ubuntu de Mme Chombier :

we changed the window size from 5 to 1, removed the CRT mode,
and added the dummy reduction step.

En français de tous les jours, ça veut dire que la vitesse de calcul en a pris un sacré coup dans l'aile. Pourquoi ? Parce que quand ça calcule à vitesse normale, ça ne marche pas ? Vitesse rabaissée, longueur de clé discutable...

Mais c'est un peu plus loin qu'on va tomber sur le détail qui tue. Vous vous souvenez de ce qu'a écrit le journaliste : 512 bits ou presque en un seul coup. C'est exactement ce qui est écrit dans le résumé qui introduit l'article. C'est l'argument massue du papier. Et bien non, ce n'est pas le cas. On peut en effet lire en page 12 :

To validate this heuristic, we performed then ten different
"random" SBPA attacks on the same 512 bit key, from
which we show in Figure 8 only 4 very different ones.

En gros, il se trouve que sur un système multi-tâche, on a pleins de processus qui tournent en même temps et qui viennent polluer les mesures qui montrent alors de écarts importants. Les auteurs vont alors poser l'hypothèse que s'ils font pleins de mesures à des moments différents, quelques unes vont se montrer exactes, sinon nettement plus précises que les autres. L'idée va donc consister à lancer de nombreuses mesures, prier un grand coup et chercher celle qui est plus précise que les autres si elle est là :

And indeed, the following experimental result, also being
among those ten measurements, clearly shows that there
is one exceptionally clear one, which directly reveals 508
out of 512 secret key bits.

Alors oui, une seule mesure nous donnera l'essentiel de la clé. Sauf qu'il aura fallu en faire quelques dizaines pour l'isoler et qu'elle est qualifié d'exceptionnelle. Je n'ai effectivement pas lu l'article en détail, je vous le concède, mais c'est loin du one shot. On a pris la meilleure itération entre dix et on n'a toujours pas la clé, même si 508 bits sur 512, je vous accorde également que ça fait mal. Et puis c'est bien joli d'annoncer que la figure 9 est exceptionnellement claire, mais qu'est-ce qui nous prouve que d'abord on en aura toujours une du même accabi toutes les dix itérations et ensuite qu'on est capable de l'isoler aussi précisément[3] ? En gros, ça laisse quelques questions en suspens :

  • Est-ce que le ratio est toujours d'une mesure bonne pour dix mauvaises ?
  • Qu'est-ce qui caractérise une bonne mesure, par rapport à une mauvaise ?
  • Est-ce que cette mesure est la seule qui a l'air bonne ?
  • Si ce n'est pas le cas, comment différencier les faux positifs ?
  • Enfin, si on a 508 bits sur 512, comment est-ce qu'on sait lesquels sont bons ?

En outre, cela complique sérieusement l'exploitation pratique : quand vous faites du commerce électronique, vous ne passez votre temps à chiffrer en RSA avec la même clé. Quand vous déclarez vos impôts, vous ne signez pas vingt fois de suite votre envoi. Il se pourrait donc bien que votre programme malicieux ait un peu de mal à réunir tous les éléments nécessaires, et c'est bien là que la bât blesse.

Évidemment, le journaliste, lui, il n'a pas vu tout cela. Il a vu que ça parlait de mettre à mal de la cryptographie et en a aussitôt déduit la fin du chiffrement à clé public sur Internet. Et son "petit logiciel taupe [qui] pourrait [...] écouter la puce en toute discrétion, et renvoyer la clé à des hackers" n'est pas encore sur le pas de votre disque dur. Mais ne me faites cependant pas dire ce que je n'ai pas écrit. Cet article propose une amélioration intéressante des techniques de BPA connues qui mérite d'être approfondie et prise en compte. Mais cette amélioration n'est manifestement pas à la hauteur de ce qui est annoncé en introduction et est loin de révolutionner le monde de la cryptographie, qui a compris depuis longtemps que seul un environnement d'exécution isolé et protégé pouvait fournir à des opérations cryptographiques un niveau de sécurité élevé. C'est le principe même des processeurs cryptographiques et des cartes à puce, et ce n'est pas pour rien que les standards de sécurité forts en imposent l'utilisation.

Quand à ce qu'on en lit dans la presse, ça frise la tempête dans un dé à coudre. Comme d'habitude seront tentées de dire les mauvaises langues...

Notes

[1] Observez le nombre de gens qui patchent après l'annonce d'une faille OpenSSL, c'est très intéressant...

[2] Même qu'il doit encore y en avoir en circulation...

[3] L'attaquant, contrairement à nos chercheurs, ne connait pas la clé qu'il cherche, lui...