Les puces ne garantissent pas la sécurité des échanges en ligne (dixit Le Monde)
fabrice.pas-de...@worldonline.fr
En dehors de la confusion entre les cartes à puces & du SSL executé
dans le processeur d'un ordinateur, j'ai un doute. C'est vraiment une
attaque efficace sur un ordinateur dans des conditions réels d'usage ?
Avec plusieurs tâches simultanées & pleins d'autres choses en même
temps ?
Goldy
J'ai pas tout compris l'article, ça parle de puce et ensuite de ssl...
J'aimerais bien aussi en savoir plus.
David MENTRE
Goldy <g...@goh.goh> writes:
D'après le peu que j'ai compris du charabia du Monde, l'attaque utilise
le module de prédiction de branchement des processeurs courants. Ce
module est utilisé pour déterminer la suite du code à charger après un
saut (càd un branchement). Jusqu'au moins au Pentium, c'était un simple
automate à quatre états (branchement non pris, possiblement non pris,
possiblement pris, branchement pris) qui transitionne d'un l'état à
l'autre suivant que le processeur se rend compte qu'il s'est trompé ou
non sur le branchement en cours. L'état en cours indique au processeur
s'il doit charger les instructions à la suite de l'instruction de saut
ou au point de saut.
Apparement, l'état de ce module est accessible à quiconque et donc à un
attaquant qui utiliserait cette information pour découvrir la clé (je
laisse les compétents expliquer comment c'est possible).
L'allusion à OpenSSL précise qu'une future version d'OpenSSL corrigerait
le problème en désactivant le module de prédiction de branchement lors
de l'utilisation des clefs : si le module n'est pas actif, plus
d'information donc plus d'attaque. Évidemment, ça aurait un impact très
négatif sur les performances du processeur.
Mais le plus simple est d'attendre la publication du papier pour en
savoir plus, non ? Ou de suivre les prochaines version d'OpenSSL ?
Amicalement,
david
--
David Mentré
Alain
fabrice.pas-de...@worldonline.fr a écrit :
la cible c'est pas les processeurs crypto des cartes à puce ?
les attaques sur les temps d'exécution sont pas nouvelles... dans les
années 70 j'avais vu des attaques contre le mot de passe basée sur le
temps de comparaison des mots de passe...
Sylvain
le début de l'article indique:
"Dans un article encore confidentiel, le chercheur et ses collègues
"décrivent la façon dont ils ont pu, en une seule tentative - soit
"quelques millisecondes -, récupérer la quasi-intégralité d'une clé
"de cryptage de 512 bits (suite d'autant de 0 ou de 1)."
j'aime assez le "article confidentiel" donc inconnu et les kms qui
viennent quand même après...
sur le fond, il est (a peu près) exact qu'avec le matériel actuel, le
simple fait de faire un calcul RSA dans une carte permets de ""lire""
(en surveillant la consommation par exemple) tous les bits 1 à 1 lorsque
qu'ils sont utilisés pour faire l'exponentiation modulaire interne.
BUT ceci n'est applicable qu'avec des chips complètement obsolètes et
déjà connus comme tels (ie troué, laissant fuir les clés, ...); les
fondeurs ont depuis un bon bout de temps mis les protections
nécessaires, les OS eux-même rajoutent une couche (par exemple en
faisant du bruit durant les opérations d'accès aux clés).
bref, ceci parait bidon.
Sylvain.
François Grieu
Monde:
http://eprint.iacr.org/2006/351
En résumé: un nouveau canal de fuite d'information entre tâches
tournant sur le *même* CPU, genre PC. Ni les cartes à puce ni les HSM
ne sont concernés.
François Grieu
root
> Mais le plus simple est d'attendre la publication du papier pour en
> savoir plus, non ? Ou de suivre les prochaines version d'OpenSSL ?
>
Ça me fait penser à ce document de D.J. Bernstein, décrivant entre autre
le problème d'attaque par timing introduit par le fait que "Skipping an
operation is faster than doing it" :
- http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
Sylvain
>
> faire un calcul RSA dans une carte [à puce] ...
le papier utilise en fait "puce" pour processeurs de PC (Intel en ligne
de mire) (merci François).
rien de neuf sous les ventilos dans ce cas, une clé soft peut de toute
façon être aisément piratée.
Sylvain.
fabrice.pas-de...@worldonline.fr
wrote:
L'attaque semble n'être possible que sur des processeur multi thread
(style HT d'Intel, T1 de Sun), par le bias de l'observation synchrone
du cache de prédiction de branchement.
D'autre part :
In the other case, one needs a very sophisticated OS expertise and a
deep thread scheduling expertise, cf. [NS]. As the above paradigm and
all its subtle implementation details heavily depend on the underlying
OS, CPU type and frequency, etc. we will not deepen further those
technical details here, and just assume the existence of a suited spy
process and a corresponding crypto process in a hardware-assisted
multi-threading environment.
dit l'auteur.
Je le trouve bien léger, parce que de là à rendre l'attaque réellement
effective dans la vraie vie, comme le prétend l'article du Monde, il
me semble qu'il y a un grand pas à franchir. Quand au condition de
l'expérience, on sait juste qu'ils ont tournés sur un Pentium 4, avec
une implémentation RSA tiré de OpenSSL, mais ultra bidouillé. Pas de
mention de l'OS utilisé.
nlevol
François Grieu a écrit :
Est-il possible que la manière la plus facile de venir à bout cette
attaque soit d'écrire le RSA sous une forme qui n'emploie pas les
branches qui sont fonction de la valeur de la clef ? Par exemple si
vous modifiez l'algorithme de la façon suivante :
result=message
for (i=(length of key -2); i>=0; i--) {
result1 = result * result
result2=result1 * Message
if (e[i]==1) result=result2 //Cette ligne doit être codée sans saut
conditionnel
else result =result1
}
Le codage les lignes « if-else» sans saut conditionnel peut être
effectué d'un certain nombre de manières, ma méthode préfère (pas
forcement le plus simple) doit employer un byte « swap ». Par
exemple, il y a deux résultats : result1 et result2, leurs adresses
sont respectivement A et B. Si vous faites un byte « swap » S=A^B (^
= XOR), alors vous pouvez employer ceci pour permuter les adresses
entre elles : (A=B^S, B=A^S).
Alors, vous devrez simplement créer un byte de décision « D » selon
lequel est 0xFF ou 0x00 si le bit de la clef est 1 ou 0 (ceci peut
être fait avec shifting et ORing). Le byte de décision est ANDed (&)
avec le byte d'échange. Le statement if-else ci-dessus devient alors :
Adresse de result = A^(S & D)
Sinon, on peut également faire une table à double entrée contenant
les adresses et employer le bit de la clef comme index (mais c'est
trop simple). Cependant, des variations de la première méthode sont
meilleures pour certaines optimisations de l'algorithme.
Dans la plupart des cas il est possible de remplacer les sauts
conditionnels avec des calculs.
Sylvain
>
> si vous modifiez l'algorithme de la façon suivante :
*l*'algo, quel algo ? (cette impl. vient d'où ?)
> Sinon, on peut également faire une table à double entrée [...]
sinon, on peut utiliser une carte HSM non ?
Sylvain.
Francois Grieu
"nlevol" <nle...@yahoo.com> écrit:
> Est-il possible que la manière la plus facile de venir à bout cette
> attaque soit d'écrire le RSA sous une forme qui n'emploie pas les
> branches qui sont fonction de la valeur de la clef ?
A mon avis oui. La ligne
if (e[i]==1) result=result2
peut effectivement s'écrire sans branchement (en C, en supposant
que e[i] est 0 ou 1)
unsigned mask = (unsigned)(e[i]) - (unsigned)1;
result = mask&result | ~mask&result2;
François Grieu
Jean-Marc Desperrier
> Sinon, on peut également faire une table à double entrée contenant
> les adresses et employer le bit de la clef comme index (mais c'est
> trop simple).
Ca, ça ressemble fortement à la méthode que Bernstein a attaqué dans le
cas de l'AES, en s'appuyant sur les variations de temps d'exécution
d'accès à un index de tableau en fonction des alignements de données et
en fonction des conflits d'accès au cache, qui se produisent quand le
modulo de l'adresse dans le tableau par la taille des lignes de cache,
est en collision avec celui d'autre données par ailleurs dans le cache.
nlevol
Francois Grieu a écrit :
> A mon avis oui. La ligne
>
> if (e[i]==1) result=result2
>
> peut effectivement s'écrire sans branchement (en C, en supposant
> que e[i] est 0 ou 1)
>
> unsigned mask = (unsigned)(e[i]) - (unsigned)1;
> result = mask&result | ~mask&result2;
D=e[i] Beau!
L'idée de le byte « swap » est cela peut être utilisé seulement
sur les adresses. L'algorithme peut être optimisé si les données
sont eues accès utilisant des pointers. L'algo optimisé devient :
result2=message
for (i=(length of key -2); i>=0; i--) {
result1 = result2 * result2
result2 = result1 * Message
D= e[i]-1 //merci
ptrResult1 = ptrResult1 ^ (S & D) //Swap if e[i] ==0
ptrResult2 = ptrResult2 ^ (S & D)
}
result = result2
nlevol
nlevol wrote:
> D=e[i] Beau!
Oopps! D=e[i]-1
Alain
Francois Grieu a écrit :
il faut faire très gaffe... les processeurs modernes sont très
intelligents, et notamment ils détectent quand un résultat n'est pas
utilisé...
si on ne connais pas l'architecture du processue, le compilateur et
l'algorithme, don dis plein de conneries...
un exemple c'est le mythe du double check locking en java, qui ne marche
pas, et pour lequel tout les tentatives de contournement échouent...
pour comprendre pourquoi il faut bien comprendre les processeurs, les
carte multi-processeurs, les compilateurs hostspot de la machine
virtuelle et le modèle d'exécution...
avec un processeur réel c'est encore pire...
dans l'article ils expliquaient que plein de solutions avaient été
testées sans succès... un système ou on équilibrait les branche de
calcul notamment...
je crois que le principe est d'utiliser la table des prédiction de
branchement associée aux lignes de code... en repassant dans une ligne
de code on dois pouvoir sentir le chemin du prédécesseur.
Francois Grieu
Alain <no...@none.org> a écrit:
> Francois Grieu a écrit :
> > Dans l'article <1164062838.4...@h48g2000cwc.googlegroups.com>,
> > La ligne
> > if (e[i]==1) result=result2
> > peut effectivement s'écrire sans branchement (en C, en supposant
> > que e[i] est 0 ou 1)
> > unsigned mask = (unsigned)(e[i]) - (unsigned)1;
> > result = mask&result | ~mask&result2;
> il faut faire très gaffe... les processeurs modernes sont très
> intelligents, et notamment ils détectent quand un résultat n'est
> pas utilisé...
Je ne demande qu'à être (légèrement) supris: quel compilateur et/ou
processeur existant sait ne pas évaluer result ou result2 dans le
morceau de code que j'ai donné ?
Bien que j'ai parlé de C, j'admet d'autres languages, y compris
Java+JIT.
François Grieu
michae...@gmail.com
>
> nlevol wrote:
> > Sinon, on peut également faire une table à double entrée contenant
> > les adresses et employer le bit de la clef comme index (mais c'est
> > trop simple).
>
> Ca, ça ressemble fortement à la méthode que Bernstein a attaqué dans le
> cas de l'AES,
En stockant la (les) paire(s) d'adresses contigument et ou il faut,
les 2 adresses possibles tiennent largement dans une ligne de
cache, donc pas de danger. Par contre, remplacer un branchement
conditionnel par un branchement indirect ne resoud pas vraiment les
choses, puisque les branchements indirects sont aussi predits, et
sont donc potentiellement vulnerables a la meme attaque.
A mon avis le plus facile pour se proteger sur PC est d'utiliser un
OS avec ASLR (Address space layout randomization), ou de l'ajouter
avec un module externe.
En tous cas puisque M.Grieu vient de se pencher sur les attaques
liees au timings, j'espere qu'il va continuer sur ce nouveau probleme
et publier ses resultats ;-)
regards,
--spath
Alain
Francois Grieu a écrit :
> Dans l'article <45637ec1$0$27376$ba4a...@news.orange.fr>,
> Alain <no...@none.org> a écrit:
>
>> Francois Grieu a écrit :
>>> Dans l'article <1164062838.4...@h48g2000cwc.googlegroups.com>,
>>> La ligne
>>> if (e[i]==1) result=result2
>>> peut effectivement s'écrire sans branchement (en C, en supposant
>>> que e[i] est 0 ou 1)
>>> unsigned mask = (unsigned)(e[i]) - (unsigned)1;
>>> result = mask&result | ~mask&result2;
>
>> il faut faire très gaffe... les processeurs modernes sont très
>> intelligents, et notamment ils détectent quand un résultat n'est
>> pas utilisé...
>
> Je ne demande qu'à être (légèrement) supris: quel compilateur et/ou
> processeur existant sait ne pas évaluer result ou result2 dans le
> morceau de code que j'ai donné ?
je pense aussi que ca marche, mais je ne jurerais de rien
dans l'article original
http://cryptome.org/sbpa/sbpa.htm
qui est plus clair, on comprend mieux l'astuce...
il y a quelques années je sais que certains travaillaient sur des
prédicteurs de valeur pour les résultats d'opération, histoire d'aller
encore plus loin que les BPA. c'est vrai que ces cherchers étaient en
avance et que les processeurs MTA et multi-coeur actuels ne sont que des
versions anciennes et réduites de leurs idées...
d'autre part si le compilo détecte que e[i]=0 ou 1, il peut faire une
optimisation en mettant un branch et en déroulant le calcul...
il y a des compilo vraiement efficace... surtout s'il tiennent compte
justement de l'exécution spéculative pour optimiser en utilisant des
branch...
> Bien que j'ai parlé de C, j'admet d'autres languages, y compris
> Java+JIT.
effectivement un JIT type hotspot pourra décider d'optimiser en faisant
des tests... une optimisation en smalltalk que j'avais vu c'était le
déroulement de test de classe...
le système observe les classe fréquentes et transforme un code du style
vtable_methode[obj.getClass()](obj)
en
if(obj instanceof Derive1) { Derive1_methode(obj) ;}
else if(obj instanceof Derive2) { Derive2_methode(obj) ;}
else vtable_methode[obj.getClass()](obj)
il peut aussi, en observant que certaines valeurs sont fréquentes
dérouler un code du style
var=x*y; en
if(x==0) var=0;
else if(y=0) var=0;
else if(x=1) var=y;
else if(y=1) var=x;
else if(x=-1) var=-y;
else if(x=2) var=y<<1;
else var=x*y;
Jean-Marc Desperrier
> En stockant la (les) paire(s) d'adresses contigument et ou il faut,
> les 2 adresses possibles tiennent largement dans une ligne de
> cache, donc pas de danger.
Effectivement la solution est de choisir l'adresse comme il faut, mais
il faut une connaissance très poussée du processeur pour trouver tout ce
qu'il faut prendre en compte (certains éléments ne sont sont pas
clairement documentés) et de telles contraintes sur l'ensemble des
éléments accédés commencent à rendre l'écriture du code sacrément
compliquée. Je pense qu'il vaut mieux lire complètement l'article de
Bernstein pour voir l'ampleur du problème :
http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
Note : Bien qu'il publie son résultat, et au moins une partie des idées,
il n'y a pas la version finale de son code dont il déclare qu'il corrige
les problèmes.
[...]
> A mon avis le plus facile pour se proteger sur PC est d'utiliser un
> OS avec ASLR (Address space layout randomization), [...]
En fait, c'est le point qui n'est pas clair pour moi dans l'attaque,
repose-t-elle ou non sur le fait de savoir exactement où se trouve dans
l'espace mémoire les instruction de sauts dans l'algorithme de calcul RSA.
Il écrit un code qui sature le cache de prédiction de branchement, il
regarde après qu'une exécution du code RSA se soit glissée au milieu de
l'exécution de son programme quelles lignes du cache ont été vidées,
mais a-t-il besoin de savoir l'adresse des instructions du RSA pour
faire correspondre à chaque ligne du cache ou peut-il le déduire du
résultat ? Le deuxième cas me semble possible, et alors ce n'est pas une
ASLR qui va suffir à se protéger.
Un peu plus complexe, mais plus efficace je crois, serait d'avoir un OS
auquel on peut dire qu'un thread est "sensible", et qu'à la fin de
chaque "time slice" où le code du thread a été exécuté, avant de
consacrer un "time slice" à un autre programme, il faut exécuter un code
particulier destiné aujourd'hui à vider le BTB mais qui pourra être
complété demain pour d'autres caches.
michae...@gmail.com
> Je pense qu'il vaut mieux lire complètement
> l'article de Bernstein pour voir l'ampleur
> du problème :
Je l'ai lu, et nulle part je n'ai vu qu'il pensait
pouvoir detecter une difference entre les temps
d'acces de deux double words dans la meme ligne de
cache. Si quelqu'un sait faire ca, ca m'interesse :)
> En fait, c'est le point qui n'est pas clair pour moi
> dans l'attaque, repose-t-elle ou non sur le fait de
> savoir exactement où se trouve dans l'espace
> mémoire les instruction de sauts dans l'algorithme
> de calcul RSA.
L'explication est dans le paragraphe 3 :
"Also a spy process is executed [...] in such a way
that all of these branches map to the same BTB set
which also stores the specific conditional branch
determined by the secret key bits of the crypto process."
Comme les entrees du BTB sont indexees d'apres l'adresse
de branchement, le process espion doit connaitre l'adresse
de la branche de l'application cryptographique a espionner de
facon a placer ses propres branches dans le meme BTB set.
Sans connaitre l'adresse on ne connait pas le set a espionner,
et ca devient impossible.
regards,
--spath
Emile
http://www.lemonde.fr/web/article/0,1-0@2-651865,36-835944,0.html?xtor=RSS-651865
et j'en ai extrait le texte suivant
>>Jean-Jacques Quisquater (Université catholique de Louvain, Belgique) rappelle que les
>>normes militaires américaines mettent en garde depuis longtemps contre les
>>attaques fondées sur l'analyse des temps de calcul. Pour lui, l'avenir est aux
>>processeurs spécialisés dans les fonctions de sécurité. "Mais on n'y viendra pas avant
>>plusieurs années", remarque-t-il.
Il va de soi que les processeurs spécialisés ne sont pas
attaquables suivant le processus d' "analyse de prédiction de branche"
(BPA). Mais de quels processeurs spécialisés s'agit-il ? Je ne pense
pas que le programme RSA mis dans un circuit intégré puisse avoir un
avenir commercial pour la grande masse des internautes. Depuis le temps
que le RSA a été inventé et que rien n'a bougé à ce point de vue,
tout porte à croire que les chiffrements effectués avec le RSA se
feront toujours en software.
La situation se présente tout différemment avec l'algorithme SED.
Le cryptosystème expérimental Classicsys démontre la faisabilité du
projet offrant toutes les garanties de confidentialité, d'intégrité,
d'authentification des correspondants, et de non répudiation. Voir le
message ci-après.
http://groups.google.com/group/fr.misc.cryptologie/browse_frm/thread/0827b554617f56c4/#
Je ne crois pas qu'il faille des années pour mener à bien la
réalisation d'un tel circuit intégré. Vu mon âge, je me ne sens
plus en mesure d'entreprendre un tel projet, mais je suis tout disposé
à céder mon savoir faire à toute personne qui serait intéressée à
la réalisation de ce projet. Vous pouvez me contacter à
emile.nos...@happymany.net (supprimer ".nospam.")
Emile
Romnulphe
> http://www.lemonde.fr/web/article/0,1-0@2-651865,36-835944,0.html?xtor=RSS-651865
En guise de rectificatif, Le Monde a publié le communiqué tardif suivant :
« Puces. La photo illustrant l'article intitulé "Les puces ne
garantissent pas la sécurité des échanges en ligne" (Le Monde daté 19-20
novembre) était celle d'une puce de carte SIM. Or l'article traitait des
puces d'ordinateur, et non pas de celles des cartes à puce, qui
disposent au contraire de contre-mesures contre ce type d'attaque. »
On va dire que c'est mieux que rien...
Francois Grieu
Romnulphe <romn...@yahou.fr.invalid> a écrit:
La photo page 7 de l'édition électronique du monde 20061119_QUO.pdf,
est celle d'un chip destinée à un boitier DIP 24 pattes, toutes connectées.
Ce n'est donc ni une carte SIM, ni un processeur affecté par le problème
auquel fait référence l'article.
> On va dire que c'est mieux que rien...
Heureusement pour Le Monde et Hervé Morin que le ridicule ne tue pas.
François Grieu
Romnulphe
> La photo page 7 de l'édition électronique du monde 20061119_QUO.pdf,
> est celle d'un chip destinée à un boitier DIP 24 pattes, toutes connectées.
> Ce n'est donc ni une carte SIM, ni un processeur affecté par le problème
> auquel fait référence l'article.
Très édifiant.
> Heureusement pour Le Monde et Hervé Morin que le ridicule ne tue pas.
Oui. Vous devriez leur écrire pour le leur dire.