Sécurité et problème de clefs via la prédiction de branchement

[Dandu]

http://www.lemonde.fr/web/article/0,...-835781,0.html

Ca vous parait crédible ce truc ?

apparemment, en analysant les réactions de la prédiction de branchement, ils arrivent à sortir la clefs.

Ca me semble assez fort quand même (mais je connais pas non plus le fonctionnement exact de ce truc).

[Childerik]

Tient, "l'attaque des micro-codes CPU" II le retour :D.

En fait, voilà probablement la source

[Lissyx]

Bah, vu les attaques possibles sur la consommation d'énergie des puces, c'est sûrement pas impossible.

Par contre, est ce que c'est facilement faisable pour un genre de rootkit ? Faut espérer que non, même si le monsieur parle de seulement quelques semaines avant d'avoir du code qui marche ..

[jose99m]

Les SPE du CELL et l'Itanium sont ils à l'abris ?

[The_ED]

De toute facon, il y a toujours besoin d'un programme tiers donc je ne vois pas la différence avec n'importe quel autre logiciel espion.

D'autre part, ils parlent de "faisabilité", donc c'est pour l'instant de la théorie.

J'aime beaucoup l'argument du gars de chez Intel qui serait "absent".

Beaucoup de bruit pour pas grand chose...

[Fanche]

The_ED> la différence est que là il serait impossible en rallongeant la clef de rendre le programme espion inefficace.

Lissyx> oui effectivement par exemple pour les cartes banquaires, on peut (ou on pouvait, je ne sais pas si ça a été changé) craquer le code en mesurant la consommation électrique. Ceci parce que l'électronique sur la carte est (était) synchrone. Mais avec de la logique assynchrone ce n'est pas faisable. Ce qui me fait penser que la logique assynchrone serait peut-être une solution dans la mesure ou le temps de calcul deviendrait beaucoup plus compliqué à évaluer.
Question: Intel n'a pas mis un peu de logique assynchrone dans ses procs? (je crois me souvenir d'en avoir entendu parlé mais je ne retrouve rien)

[r_one]

en fait c'est pas franchement une question de logique mais de façon de coder les algorithmes cryptographiques. Le problème est que lorsqu'on fait un tel calcul on ne va effectuer qu'un nombre limité d'opération différente (chaque opération pouvant être répétée énormément de fois). Si l'on arrive à déduire quelles sont ces opérations grâce à la consommation électrique du chip, au champ magnétique émis, à l'age du capitaine et j'en passe... alors on est capable de savoir ce qui a été calculé et donc de connaitre les clés.

Ca marche très bien avec les vielles cartes bancaires (genre 5 ou 6 ans), des boites comme gemalto (ex gemplus et axalto) ont des chercheurs qui bossent à plein temps sur ce genre d'attaque pour améliorer les chip (mais les banques ne suivent pas très vite les évolutions).

pour en revenir au sujet, l'idée des chercheurs en cryptologie est de sans cesse trouver un moyen d'inférer de l'information en exploitant le comportement du chip et des algos qui sont dessus.

[ylyad]

Simple curiosité, pour comprendre les ordres de grandeur: une des solutions proposées serait de désactiver le module de prédiction lors du traitement des clés, l'effet en étant une division par 4 de la vitesse du processeur. Euh, j'imagine que ce chiffre ne s'applique qu'au traitement des clés, non? J'ai pas l'impression que ce soit les cas qui mettent les processeurs à genoux. OK, je veux bien croire que ça aura un impact sur les perfs, mais ça va pas non plus être une régression monstrueuse, non?

PS: une explication plus détaillée serait la bienvenue parce que l'article du Monde est un peu "léger".

PPS: Via et son module de crypto a un coup d'avance, non?

[Lissyx]

Bon d'après masse de gens sur LinuxFR qui ont l'air de s'y connaître plus que moi en crypto, y'a pas mal de tirage de bourre et de blabla alors qu'en fait, bon, ...

https://linuxfr.org/2006/11/20/21654.html

[Lissyx]

Et de toute façon, on verra ce qu'il en est à la présentation de son papier, et des vraies possibilités.

Si un rootkit générique peut exister pour feinter facilement des clefs, oui.

Sinon, il restera à mon sens plus facile de piquer les certificats.

[PeGGaaSuSS]

Bon d'après masse de gens sur LinuxFR qui ont l'air de s'y connaître plus que moi en crypto, y'a pas mal de tirage de bourre et de blabla alors qu'en fait, bon, ...

https://linuxfr.org/2006/11/20/21654.html

Tu peut citer les parties interessantes, parceque j'ai commencé a lire et a part le blabla anti-TCPA, j'ai un peu la flemme de trier...
Je suis d'accord avec le dernier commentaire

[Fanche]

Tu peut citer les parties interessantes, parceque j'ai commencé a lire et a part le blabla anti-TCPA, j'ai un peu la flemme de trier...

flemmard!

[Lissyx]

Bah grosso modo, beaucoup de bruit pour rien, les conditions sont spéciales, et c'est loin d'être trivial à mettre en place visiblement.

Et en plus ça permet de justifier des trucs assez louches

[Lissyx]

Encore masse à lire.
http://it.slashdot.org/article.pl?sid=06/11/18/2030247
Faudrait que je me bouffe le rapport original. Je suis sûr que ça a rien à voir avec ce qui est passé dans Le Monde

[fofo]

De toute facon, il y a toujours besoin d'un programme tiers donc je ne vois pas la différence avec n'importe quel autre logiciel espion.

D'autre part, ils parlent de "faisabilité", donc c'est pour l'instant de la théorie.

J'aime beaucoup l'argument du gars de chez Intel qui serait "absent".

Beaucoup de bruit pour pas grand chose...

Tout à fait à partir du moment ou on peut exécuter du code sur une machine il suffit d'aller chercher simplement sur le disque la clé privée en question... :???: (genre ~/.ssh/rsa.private ou part là sous windows : ~\Application Data\Microsoft\SystemCertificates)

et ça doit prendre quelques millisecondes aussi :D

c'est completement con comme truc...

a partir du moment ou on peut pas récupérer la clé à distance ça n'a aucun intéret cette affaire.





Sinon la prédiction de branchement c'est ce qui permet d'occuper le CPU pendant qu'il attend le résultat d'un test.

Le proc fonctionne en étages : (*)
- Le premier interprete le type d'intruction (calcul, chrgement mémoire, saut...) pour l'envoyer dans la bonne partie du proc.
- Le second vérifie quel sont les données nécessaire à l'instruction,
- Le troisième récupert les données dans les registres,
- ...

Ainsi pendant que l'instruction C est en cours d'interpretation pour savoir à quoi elle sert, l'instruction B est dans le deuxième étage, l'instruction A dans le 3ème...

Un prescot a jusqu'a 40 étages de pipeline.

Donc si l'instuction est test un conditionnel, le premier étage qui décripte l'instruction ne sait pas encore la valeur du test (vrai ou faux) vu que celui là ne sera connu que dans 39 cycles d'horloges correspondant au 39 étages du pipe-line que lles instructions précédente doivent encore traverser.

Donc à priori une fois qu'une instruction de ce type entre dans le pipeline, on ne sait pas encore qu'elle sera la prochaine instruction à être évaluée.
Plusieurs solutions :
1) Attendre la fin des 39 cycles d'horloges pour connaitre la prochaine instruction à évaluer,
2) Utiliser une prédiction de branchement :
- On prédit la valeur de la condition :
- On exécute le code qui correspond,
- Passé 39 cycles d'horoges, on connait la vrai valeur de la conditon :
- C'était celle qu'on avait prédit => Cool on a gagner 39 cycles d'horloges,
- Raté c'était l'autre branche => De toute façon c'est pas pire que d'attendre 39 cycles le résultat...


Après il y'a plusieurs méthodes pour prédire les valeurs :
- Toujours Vrai / Toujours Faux (~50% de chances)
- La même valeur que la dernière condition testé (~65% de chances) : ça marche trés bien pour les boucles
- Se baser sur des statistques en fonction des instructions...


Le pire algo de prédiction (aléatoire) aura une prédiction ~50%, ça veut donc dire q'un saut conditionnel sur deux sera correctement prédit, et donc en moyenne on traitera ce branchement en la moitié du temps nécessaire à l'instruction pour traverser tout le pipeline (donc 20 cycles au lieu de 40).

Les meilleurs algos de prédiction montent à ~95-98% ça devient donc trés interressant et étant donné que les tests conditionnel sont trés fréquent (IF(){}, WHILE(){}, SWITCH(){}, FOR(){}...) c'est donc globalement un gros gain de performances.



(*) Désolé les puristes c'est une explication très théorique mais l'esprit est là...


Edit : De la lecture http://en.wikipedia.org/wiki/Branch_prediction

[Neo_13]

- Raté c'était l'autre branche => De toute façon c'est pas pire que d'attendre 39 cycles le résultat...

Pas exactement... a partir du moment ou on sait qu'on s'est planté, on attend 39cycles pour vider le pipeline (soit 79 en tout) et recommencer !

si on prédit bien, on gagne 39 cycles...
si on prédit mal, on perd 79 cycles...

Le voilà, le soucis de la prédiction... il faut au moins 67% de prédiction juste pour gagner quelque chose. Le score final est bien plus élevé... Notamment parce que les boucles sont faites pour boucler... ie, on en sort peu par rapport au nombre de passage.

[fefe]

L'article est la : http://eprint.iacr.org/2006/351.pdf (Edit: Meme lien que Childerik, je confirme juste que c'est ce qui a lance l'article).

[jihef]

En parlant de prédiction voici un article qui explique deux-trois trucs : http://www.onversity.net/cgi-bin/pro...bgteob&P=a0206

[fefe]

C'est la 4 eme attaque utilisant des meta informations pour casser RSA. Celle-ci est de meilleure qualite car elle ne necessite pas de multiples runs mais pose tout de meme un certains nombre de problemes.

Tout d'abord c'est une proof of concept, open SSL a ete modifie, et simplifie afin de pouvoir mener l'experience, une version complete complexifie de maniere significative l'attaque, sans l'empecher.
Ensuite cela fait partie des attaques qui necessitent l'execution d'un autre thread sur la meme machine, a priori un utilisateur malicieux sur votre machine a beaucoup d'autres options beaucoup plus simples pour voir ce qui se passe.

Finalement des modifications software assez limitees ont bloque les precedentes attaques du meme type et ce, en quelques jours donc l'article du Monde est effectivement un peu alarmiste.

Le probleme vient effectivement de la maniere de coder RSA, qui permet d'obtenir des informations sur la cle a partir du timing de l'execution. Les ressources partagees des microprocesseurs sont exploitees les unes apres les autres pour essayer d'obtenir ces informations de timing par effet de bord (ca a commence avec les caches on en est aux BT.
Pour les solutions:
1. soit on fait attention a ne pas reveler d'infos sur la cle en partant du principe que quelqu'un peut chronometrer toutes nos operations
2. soit on empeche le chronometrage de ces operations

La solution 2 est celle qui m'interresse personellement meme si la 1. est la plus simple, rapide et moins couteuse a mettre en oeuvre.
-on empeche l'utilisateur de faire tourner un thread espion (mais il y en aura toujours pour etre infectes par un virus quelconque)
-on force la granularite de partage de ressource a etre suffisament importante que le temps que l'on cherche a mesurer est negligeable devant cette granularite
-on donne la possiblite aux systemes d'exploitation de bloquer les mesures (precises) de temps quand une operation donnee est en cours.

Les 2 derniers necessitent bien entendu des modifications dans le hard.

[fefe]

En parlant de prédiction voici un article qui explique deux-trois trucs : http://www.onversity.net/cgi-bin/pro...bgteob&P=a0206

:whistle:

[Franck@x86]

Donc à priori une fois qu'une instruction de ce type entre dans le pipeline, on ne sait pas encore qu'elle sera la prochaine instruction à être évaluée.
Plusieurs solutions :
1) Attendre la fin des 39 cycles d'horloges pour connaitre la prochaine instruction à évaluer,
2) Utiliser une prédiction de branchement :
- On prédit la valeur de la condition :
- On exécute le code qui correspond,
- Passé 39 cycles d'horoges, on connait la vrai valeur de la conditon :
- C'était celle qu'on avait prédit => Cool on a gagner 39 cycles d'horloges,
- Raté c'était l'autre branche => De toute façon c'est pas pire que d'attendre 39 cycles le résultat...

tu oublies :
3) Exécuter toutes les branches (ce que fait l'instruction cmov si je ne me trompe pas)

[Franck@x86]

:whistle:

On écrit "prédicateur" (et non "prédicteur") ! :D

[fefe]

cmov te permet de selectionner le resultat qui t'interesse apres avoir execute les multiples branches et mis leur resultats dans des registres/ zones memoire differents. C'est la solution simple pour eliminer les aleas de branchement data dependants.
cmov n'est pas aussi rapide qu'un branchement bien predit, mais son utilisation est rentable pour la performance lorsque les 2 branches de code sont assez courtes et le taux de bonnes prediction assez mauvais. Dans le cas present executer toutes les branches reduirait la performance de maniere significative (plus que d'attendre le calcul de la destination du branchements <=> desactiver la prediction de branchement).

Je suis quasi certain que dans les jours qui viennent quelqu'un aura une solution software au probleme .

[johnnyholzeisen]

Si je ne me trompe pas, c'est pas l'Itanium qui exécute constamment les 2 cas à chaque branchement (lorsque le compilateur n'a pas su faire autrement...)

[fefe]

L'itanium avec les registres condition permet d'effectuer l'equivalent du cmov (selection d'un resultat en fonction d une condition) gratuitement.
L'itanium dispose de plus d'unites d'execution en parallele que la plupart des autres micro-processeurs ce qui permet d'utiliser ce type de technique a moindre cout que dans un x-86.

De la a dire que c'est constamment, il y a une difference, mais effectivement l'itanium utilise cette technique beaucoup plus que la plupart des autres microprocesseurs (l'idee de condition associee a chaque opearation dans un microprocesseur ne date pas d'itanium, c'est une des caracteristiques des architectures ARM par exemple).

[Stéphane.P]

Un article de FuturaScience qui remet les choses à plat :
C'est ici

[fefe]

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.

Ceci est faux, ceci est insensible a toutes les methodes etudiees dans l'article. Ce qui ne veut pas dire que d'autres methodes connues ou en developpement ne protegent pas de l'attaque (j'en connais au moins une qui ne devrait pas tarder a etre publiee et ne cause pas de perte de performance).
L'analyse faite dans l'article ne cherche pas a resoudre le probleme, mais plus a l'observer.

[fetide]

Pas exactement... a partir du moment ou on sait qu'on s'est planté, on attend 39cycles pour vider le pipeline (soit 79 en tout) et recommencer !

si on prédit bien, on gagne 39 cycles...
si on prédit mal, on perd 79 cycles...

Le voilà, le soucis de la prédiction... il faut au moins 67% de prédiction juste pour gagner quelque chose. Le score final est bien plus élevé... Notamment parce que les boucles sont faites pour boucler... ie, on en sort peu par rapport au nombre de passage.

Salut,
en fait il a bien raison, à partir du moment où l'on sait que le branchement est mal prédit (donc au cycle 39 sur les 40 étages) il ne reste plus qu'une seule instruction valide dans le pipe.
On attend un cycle pour la traiter et on flush le pipeline après, soit un ou deux cycles à attendre pas 79. Après le flush on reprend tranquillement le cours normale des instructions, on ne perd rien à faire de la prédiction de branchement.

En parlant de prédiction de branchement voici un lien vers le deuxième championnat du monde de la discipline : http://camino.rutgers.edu/cbp2/ .
Les résultats ne sont pas encore publiés mais c'est un francais qui à gagner dans les deux catégorie

[Fanche]

Up: un petit article du monde en parle, ils auraient une solution!
lemonde
mais bon ils en disent rien et ont pas l'air très optimistes avec leur solution...