je suppose que vous avez lu: http://eprint.iacr.org/2012/064 , ou
< https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs >
Je ne suis pas sûr de bien comprendre le problème.
J'ai appris que la solidité de RSA repose sur le fait qu'il est très
difficile de factoriser un très grand nombre composé de deux très
grands nombres premiers. Bien.
Les auteurs du papier ci dessus ont téléchargés un très grand nombre
de clés publiques RSA et ont effectués des PGCD entre chacune des
paires possibles. Si on trouve un PGCD différent de 1, alors cela
signifie que les deux nombres ont un facteur en commun, et de fait, on
retrouve les diviseurs de chacune des deux clés.
Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions
on retrouve a et b, puis découle les clés privées de A et B.
RSA serait donc "affaibli" dans certains cas lorsque des clés partagent
des facteurs communs.
Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A
et B. Pourquoi ce moyen serait il plus rapide que de calculer les
facteurs premiers de A et B?
La seconde chose qui m'étonne concerne l'explication de la faiblesse. Il
est indiqué qu'un mauvais générateur aléatoire créerait ses clés comme
cela:
prng.seed(seed)
p = prng.generate_random_prime()
q = prng.generate_random_prime()
N = p*q
Avec l'explication suivante:
Si le (seed) est mauvais, alors on peut connaître N et tous les
équipements utilisant cette méthode auraient le même 'N'.
Certes, mais faut il encore que le seed soit mauvais partout, et de la
même manière sur tous les équipements employant la méthode.
La seconde méthode, utilisée pour augmenter la sécurité est la
suivante:
prng.seed(seed)
p = prng.generate_random_prime()
prng.add_randomness(bits)
q = prng.generate_random_prime()
N = p*q
Avec l'explication:
Si le seed est mauvais, alors p est identique entre tous les équipements
employant cet algo, et q change. Si on a plusieurs clés d'un équipement,
on calcule le PGCD de ces clés et on retrouve chacun des 'p' et 'q'.
Encore une fois, il faut que le seed soit tout le temps mauvais de la
même manière. L'article continue en indiquant:
"OpenSSL's RSA key generation functions this way: each time random bits
are produced from the entropy pool to generate the primes p and q, the
current time in seconds is added to the entropy pool. Many, but not all,
of the vulnerable keys were generated by OpenSSL and OpenSSH, which
calls OpenSSL's RSA key generation code."
On parle donc bien de la seconde manière dont est générée le 'q'
puisque add_randomness(seconds) est utilisé, mais d'où viendrait
le faible prng.seed(seed) faible?
De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé
publique ssh en différents endroits, et la clé publique de mon
serveur est accessible. Cela signifie qu'au moins plusieurs
personnes en ont deux, et peuvent donc faire le PGCD afin de
retrouver mes clés privées?
Merci pour toute remarque, précisions sur ce sujet.
--
Kevin
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Mehdi Tibouchi
Kevin Denis wrote in message :
Les auteurs du papier ci dessus ont téléchargés un très grand nombre de clés publiques RSA et ont effectués des PGCD entre chacune des paires possibles. Si on trouve un PGCD différent de 1, alors cela signifie que les deux nombres ont un facteur en commun, et de fait, on retrouve les diviseurs de chacune des deux clés. Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions on retrouve a et b, puis découle les clés privées de A et B. RSA serait donc "affaibli" dans certains cas lorsque des clés partagent des facteurs communs.
Pas juste « affaibli », complètement cassé.
Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A et B. Pourquoi ce moyen serait il plus rapide que de calculer les facteurs premiers de A et B?
On connaît depuis fort longtemps un algorithme rapide pour le calcul des PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le PGCD de deux entiers de n bits en temps quasi-linéaire en n.
En revanche, on ne connaît pas d'algorithme efficace pour la factorisation. Le meilleur dont on dispose actuellement a une complexité en quelque chose comme exp(n^{1/3}).
Certes, mais faut il encore que le seed soit mauvais partout, et de la même manière sur tous les équipements employant la méthode.
Non, il suffit que le seed soit le même juste deux fois pour que les clefs produites soient identiques.
De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé publique ssh en différents endroits, et la clé publique de mon serveur est accessible. Cela signifie qu'au moins plusieurs personnes en ont deux, et peuvent donc faire le PGCD afin de retrouver mes clés privées?
L'attaque ne dit pas que deux clefs RSA ont toujours un facteur commun, heureusement ! Elle dit juste qu'il y a dans la nature des sources d'aléa faibles qui aboutissent occasionnellement à des facteurs communs.
Il se peut que l'une de vos clefs ait un facteur commun avec une autre clef RSA quelque part, mais ce n'est vraisemblable que si elle a été générée sur un système dont le générateur aléatoire n'ait pas eu assez d'entropie. Il semblerait d'après le billet de Heninger que cela concerne principalement des systèmes embarqués.
-- M. Tibouchi.
Kevin Denis wrote in message
<slrnjkkfsb.e3d.kevin@slackwall.local.tux>:
Les auteurs du papier ci dessus ont téléchargés un très grand nombre
de clés publiques RSA et ont effectués des PGCD entre chacune des
paires possibles. Si on trouve un PGCD différent de 1, alors cela
signifie que les deux nombres ont un facteur en commun, et de fait, on
retrouve les diviseurs de chacune des deux clés.
Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions
on retrouve a et b, puis découle les clés privées de A et B.
RSA serait donc "affaibli" dans certains cas lorsque des clés partagent
des facteurs communs.
Pas juste « affaibli », complètement cassé.
Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A
et B. Pourquoi ce moyen serait il plus rapide que de calculer les
facteurs premiers de A et B?
On connaît depuis fort longtemps un algorithme rapide pour le calcul des
PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le
PGCD de deux entiers de n bits en temps quasi-linéaire en n.
En revanche, on ne connaît pas d'algorithme efficace pour la
factorisation. Le meilleur dont on dispose actuellement a une complexité
en quelque chose comme exp(n^{1/3}).
Certes, mais faut il encore que le seed soit mauvais partout, et de la
même manière sur tous les équipements employant la méthode.
Non, il suffit que le seed soit le même juste deux fois pour que les
clefs produites soient identiques.
De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé
publique ssh en différents endroits, et la clé publique de mon
serveur est accessible. Cela signifie qu'au moins plusieurs
personnes en ont deux, et peuvent donc faire le PGCD afin de
retrouver mes clés privées?
L'attaque ne dit pas que deux clefs RSA ont toujours un facteur commun,
heureusement ! Elle dit juste qu'il y a dans la nature des sources d'aléa
faibles qui aboutissent occasionnellement à des facteurs communs.
Il se peut que l'une de vos clefs ait un facteur commun avec une autre
clef RSA quelque part, mais ce n'est vraisemblable que si elle a été
générée sur un système dont le générateur aléatoire n'ait pas eu assez
d'entropie. Il semblerait d'après le billet de Heninger que cela concerne
principalement des systèmes embarqués.
Les auteurs du papier ci dessus ont téléchargés un très grand nombre de clés publiques RSA et ont effectués des PGCD entre chacune des paires possibles. Si on trouve un PGCD différent de 1, alors cela signifie que les deux nombres ont un facteur en commun, et de fait, on retrouve les diviseurs de chacune des deux clés. Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions on retrouve a et b, puis découle les clés privées de A et B. RSA serait donc "affaibli" dans certains cas lorsque des clés partagent des facteurs communs.
Pas juste « affaibli », complètement cassé.
Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A et B. Pourquoi ce moyen serait il plus rapide que de calculer les facteurs premiers de A et B?
On connaît depuis fort longtemps un algorithme rapide pour le calcul des PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le PGCD de deux entiers de n bits en temps quasi-linéaire en n.
En revanche, on ne connaît pas d'algorithme efficace pour la factorisation. Le meilleur dont on dispose actuellement a une complexité en quelque chose comme exp(n^{1/3}).
Certes, mais faut il encore que le seed soit mauvais partout, et de la même manière sur tous les équipements employant la méthode.
Non, il suffit que le seed soit le même juste deux fois pour que les clefs produites soient identiques.
De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé publique ssh en différents endroits, et la clé publique de mon serveur est accessible. Cela signifie qu'au moins plusieurs personnes en ont deux, et peuvent donc faire le PGCD afin de retrouver mes clés privées?
L'attaque ne dit pas que deux clefs RSA ont toujours un facteur commun, heureusement ! Elle dit juste qu'il y a dans la nature des sources d'aléa faibles qui aboutissent occasionnellement à des facteurs communs.
Il se peut que l'une de vos clefs ait un facteur commun avec une autre clef RSA quelque part, mais ce n'est vraisemblable que si elle a été générée sur un système dont le générateur aléatoire n'ait pas eu assez d'entropie. Il semblerait d'après le billet de Heninger que cela concerne principalement des systèmes embarqués.
-- M. Tibouchi.
Kevin Denis
Le 27-02-2012, Mehdi Tibouchi a écrit :
Les auteurs du papier ci dessus ont téléchargés un très grand nombre de clés publiques RSA et ont effectués des PGCD entre chacune des paires possibles. Si on trouve un PGCD différent de 1, alors cela signifie que les deux nombres ont un facteur en commun, et de fait, on retrouve les diviseurs de chacune des deux clés. Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions on retrouve a et b, puis découle les clés privées de A et B. RSA serait donc "affaibli" dans certains cas lorsque des clés partagent des facteurs communs.
Pas juste « affaibli », complètement cassé.
Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A et B. Pourquoi ce moyen serait il plus rapide que de calculer les facteurs premiers de A et B?
On connaît depuis fort longtemps un algorithme rapide pour le calcul des PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le PGCD de deux entiers de n bits en temps quasi-linéaire en n.
bon, wikipedions la division d'Euclide.
En revanche, on ne connaît pas d'algorithme efficace pour la factorisation. Le meilleur dont on dispose actuellement a une complexité en quelque chose comme exp(n^{1/3}).
D'ou la solidité de RSA si je comprends bien.
Certes, mais faut il encore que le seed soit mauvais partout, et de la même manière sur tous les équipements employant la méthode.
Non, il suffit que le seed soit le même juste deux fois pour que les clefs produites soient identiques.
De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé publique ssh en différents endroits, et la clé publique de mon serveur est accessible. Cela signifie qu'au moins plusieurs personnes en ont deux, et peuvent donc faire le PGCD afin de retrouver mes clés privées?
L'attaque ne dit pas que deux clefs RSA ont toujours un facteur commun, heureusement ! Elle dit juste qu'il y a dans la nature des sources d'aléa faibles qui aboutissent occasionnellement à des facteurs communs.
C'est plus l'exemple fourni qui semble sous entendre cela. Le calcul de 'p' prend de l'aléa, puis en rajoute avant de calculer 'q' dans le cas d'openSSL, et donc d'openssh. Mais j'ai peut être mal compris l'exemple.
Il se peut que l'une de vos clefs ait un facteur commun avec une autre clef RSA quelque part, mais ce n'est vraisemblable que si elle a été générée sur un système dont le générateur aléatoire n'ait pas eu assez d'entropie. Il semblerait d'après le billet de Heninger que cela concerne principalement des systèmes embarqués.
Donc si on résume: certains systèmes embarqués ont des générateurs aléatoires faibles. Si leur générateur d'aléa est faible, alors la crypto (au sens large) basée dessus est faible, comme par exemple la génération de clés RSA. Dans ce cas, quelle est la nouveauté de l'article? (vraie question) -- Kevin
Le 27-02-2012, Mehdi Tibouchi <medtib@alussinan.org> a écrit :
Les auteurs du papier ci dessus ont téléchargés un très grand nombre
de clés publiques RSA et ont effectués des PGCD entre chacune des
paires possibles. Si on trouve un PGCD différent de 1, alors cela
signifie que les deux nombres ont un facteur en commun, et de fait, on
retrouve les diviseurs de chacune des deux clés.
Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions
on retrouve a et b, puis découle les clés privées de A et B.
RSA serait donc "affaibli" dans certains cas lorsque des clés partagent
des facteurs communs.
Pas juste « affaibli », complètement cassé.
Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A
et B. Pourquoi ce moyen serait il plus rapide que de calculer les
facteurs premiers de A et B?
On connaît depuis fort longtemps un algorithme rapide pour le calcul des
PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le
PGCD de deux entiers de n bits en temps quasi-linéaire en n.
bon, wikipedions la division d'Euclide.
En revanche, on ne connaît pas d'algorithme efficace pour la
factorisation. Le meilleur dont on dispose actuellement a une complexité
en quelque chose comme exp(n^{1/3}).
D'ou la solidité de RSA si je comprends bien.
Certes, mais faut il encore que le seed soit mauvais partout, et de la
même manière sur tous les équipements employant la méthode.
Non, il suffit que le seed soit le même juste deux fois pour que les
clefs produites soient identiques.
De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé
publique ssh en différents endroits, et la clé publique de mon
serveur est accessible. Cela signifie qu'au moins plusieurs
personnes en ont deux, et peuvent donc faire le PGCD afin de
retrouver mes clés privées?
L'attaque ne dit pas que deux clefs RSA ont toujours un facteur commun,
heureusement ! Elle dit juste qu'il y a dans la nature des sources d'aléa
faibles qui aboutissent occasionnellement à des facteurs communs.
C'est plus l'exemple fourni qui semble sous entendre cela. Le calcul
de 'p' prend de l'aléa, puis en rajoute avant de calculer 'q' dans le cas
d'openSSL, et donc d'openssh. Mais j'ai peut être mal compris l'exemple.
Il se peut que l'une de vos clefs ait un facteur commun avec une autre
clef RSA quelque part, mais ce n'est vraisemblable que si elle a été
générée sur un système dont le générateur aléatoire n'ait pas eu assez
d'entropie. Il semblerait d'après le billet de Heninger que cela concerne
principalement des systèmes embarqués.
Donc si on résume: certains systèmes embarqués ont des générateurs
aléatoires faibles. Si leur générateur d'aléa est faible, alors la
crypto (au sens large) basée dessus est faible, comme par exemple la
génération de clés RSA.
Dans ce cas, quelle est la nouveauté de l'article? (vraie question)
--
Kevin
Les auteurs du papier ci dessus ont téléchargés un très grand nombre de clés publiques RSA et ont effectués des PGCD entre chacune des paires possibles. Si on trouve un PGCD différent de 1, alors cela signifie que les deux nombres ont un facteur en commun, et de fait, on retrouve les diviseurs de chacune des deux clés. Si la clé A = Pxa et B = Pxb alors le PGCD vaut P, et avec deux divisions on retrouve a et b, puis découle les clés privées de A et B. RSA serait donc "affaibli" dans certains cas lorsque des clés partagent des facteurs communs.
Pas juste « affaibli », complètement cassé.
Quelque chose m'échappe, c'est la manière de calculet un PGCD entre A et B. Pourquoi ce moyen serait il plus rapide que de calculer les facteurs premiers de A et B?
On connaît depuis fort longtemps un algorithme rapide pour le calcul des PGCD : l'algorithme d'Euclide. Implémenté correctement, il fournit le PGCD de deux entiers de n bits en temps quasi-linéaire en n.
bon, wikipedions la division d'Euclide.
En revanche, on ne connaît pas d'algorithme efficace pour la factorisation. Le meilleur dont on dispose actuellement a une complexité en quelque chose comme exp(n^{1/3}).
D'ou la solidité de RSA si je comprends bien.
Certes, mais faut il encore que le seed soit mauvais partout, et de la même manière sur tous les équipements employant la méthode.
Non, il suffit que le seed soit le même juste deux fois pour que les clefs produites soient identiques.
De manière très pragmatique, ça m'ennuie. Car j'ai diffusé ma clé publique ssh en différents endroits, et la clé publique de mon serveur est accessible. Cela signifie qu'au moins plusieurs personnes en ont deux, et peuvent donc faire le PGCD afin de retrouver mes clés privées?
L'attaque ne dit pas que deux clefs RSA ont toujours un facteur commun, heureusement ! Elle dit juste qu'il y a dans la nature des sources d'aléa faibles qui aboutissent occasionnellement à des facteurs communs.
C'est plus l'exemple fourni qui semble sous entendre cela. Le calcul de 'p' prend de l'aléa, puis en rajoute avant de calculer 'q' dans le cas d'openSSL, et donc d'openssh. Mais j'ai peut être mal compris l'exemple.
Il se peut que l'une de vos clefs ait un facteur commun avec une autre clef RSA quelque part, mais ce n'est vraisemblable que si elle a été générée sur un système dont le générateur aléatoire n'ait pas eu assez d'entropie. Il semblerait d'après le billet de Heninger que cela concerne principalement des systèmes embarqués.
Donc si on résume: certains systèmes embarqués ont des générateurs aléatoires faibles. Si leur générateur d'aléa est faible, alors la crypto (au sens large) basée dessus est faible, comme par exemple la génération de clés RSA. Dans ce cas, quelle est la nouveauté de l'article? (vraie question) -- Kevin
Tanguy Ortolo
Si j'ai tout bien compris, ça ne devrait pas introduire de faiblesse supplémentaire. Certes, étant donné deux clefs partageant un même facteur, il est facile de les factoriser et donc de les casser.
Mais cette possibilité ne rend pas compte de la difficulté, en amont de cette étape, de trouver pour une clef donnée une seconde clef partageant un facteur.
De la même façon, on pourrait remarquer qu'étant donnés une clef et un nombre premier divisant celle-ci, il est très facile de la factoriser. Certes, mais pour ça il faut déjà trouver le nombre premier en question, et c'est là toute la difficulté. :-)
En prenant le point de vue d'Alice, qui a publié sa clef publique, si quelqu'un parmi les milliers d'utilisateurs de clefs RSA a publié une clef partageant un facteur avec la sienne, elle n'a pas de chance. Mais la probabilité en est très faible, c'est du même ordre que si quelqu'un a publié un nombre premier composant la clef d'Alice.
-- Tanguy Ortolo
Si j'ai tout bien compris, ça ne devrait pas introduire de faiblesse
supplémentaire. Certes, étant donné deux clefs partageant un même
facteur, il est facile de les factoriser et donc de les casser.
Mais cette possibilité ne rend pas compte de la difficulté, en amont de
cette étape, de trouver pour une clef donnée une seconde clef partageant
un facteur.
De la même façon, on pourrait remarquer qu'étant donnés une clef et un
nombre premier divisant celle-ci, il est très facile de la factoriser.
Certes, mais pour ça il faut déjà trouver le nombre premier en question,
et c'est là toute la difficulté. :-)
En prenant le point de vue d'Alice, qui a publié sa clef publique, si
quelqu'un parmi les milliers d'utilisateurs de clefs RSA a publié une
clef partageant un facteur avec la sienne, elle n'a pas de chance. Mais
la probabilité en est très faible, c'est du même ordre que si quelqu'un
a publié un nombre premier composant la clef d'Alice.
Si j'ai tout bien compris, ça ne devrait pas introduire de faiblesse supplémentaire. Certes, étant donné deux clefs partageant un même facteur, il est facile de les factoriser et donc de les casser.
Mais cette possibilité ne rend pas compte de la difficulté, en amont de cette étape, de trouver pour une clef donnée une seconde clef partageant un facteur.
De la même façon, on pourrait remarquer qu'étant donnés une clef et un nombre premier divisant celle-ci, il est très facile de la factoriser. Certes, mais pour ça il faut déjà trouver le nombre premier en question, et c'est là toute la difficulté. :-)
En prenant le point de vue d'Alice, qui a publié sa clef publique, si quelqu'un parmi les milliers d'utilisateurs de clefs RSA a publié une clef partageant un facteur avec la sienne, elle n'a pas de chance. Mais la probabilité en est très faible, c'est du même ordre que si quelqu'un a publié un nombre premier composant la clef d'Alice.
-- Tanguy Ortolo
Jean-Marc Desperrier
Kevin Denis a écrit :
Donc si on résume: certains systèmes embarqués ont des générateurs aléatoires faibles. Si leur générateur d'aléa est faible, alors la crypto (au sens large) basée dessus est faible, comme par exemple la génération de clés RSA. Dans ce cas, quelle est la nouveauté de l'article? (vraie question)
Deux point sont nouveaux en gros, sans être révolutionnaires : - jusqu'à présent la catégorie de clés faibles qu'on avait en tête était celle avec à la fois la clé publique identique, donc p *et* q identiques (faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique faible), le papier met en avant cette seconde catégorie quand seulement p ou bien seulement q est identique. - la seconde catégorie est quelque part encore plus pourrie que la première :-)
En effet quand on a 2 clé publique identique, on ne sait pas instantanément si c'est vraiment un mauvais générateur ou si c'est quelqu'un qui a réutilisé 2 fois la même clé. Même quand c'est à peu près évident que c'est dû à un mauvais générateur aléatoire, A peut attaquer B et réciproquement, mais un tiers C auquel ni A ni B ne transmet la clé privé doit retrouver de quel générateur il s'agit, quel soft, sous quelles conditions, pour recréer la même collision et casser la clé. Suivant le cas, c'est très facile ou quand même un peu moins.
Avec cette nouvelle catégorie, c'est automatiquement instantané pour C de récupérer les clés privées de A et de B quand elles partagent un facteur commun, et on est sur à 100% que c'est un problème de générateur et pas une copie de clé privée. Du coup, ça a permis d'identifier un problème avec les générateurs d'un certain nombre de VPN/routeur, ce qui est un point positif.
Kevin Denis a écrit :
Donc si on résume: certains systèmes embarqués ont des générateurs
aléatoires faibles. Si leur générateur d'aléa est faible, alors la
crypto (au sens large) basée dessus est faible, comme par exemple la
génération de clés RSA.
Dans ce cas, quelle est la nouveauté de l'article? (vraie question)
Deux point sont nouveaux en gros, sans être révolutionnaires :
- jusqu'à présent la catégorie de clés faibles qu'on avait en tête était
celle avec à la fois la clé publique identique, donc p *et* q identiques
(faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique
faible), le papier met en avant cette seconde catégorie quand seulement
p ou bien seulement q est identique.
- la seconde catégorie est quelque part encore plus pourrie que la
première :-)
En effet quand on a 2 clé publique identique, on ne sait pas
instantanément si c'est vraiment un mauvais générateur ou si c'est
quelqu'un qui a réutilisé 2 fois la même clé. Même quand c'est à peu
près évident que c'est dû à un mauvais générateur aléatoire, A peut
attaquer B et réciproquement, mais un tiers C auquel ni A ni B ne
transmet la clé privé doit retrouver de quel générateur il s'agit, quel
soft, sous quelles conditions, pour recréer la même collision et casser
la clé. Suivant le cas, c'est très facile ou quand même un peu moins.
Avec cette nouvelle catégorie, c'est automatiquement instantané pour C
de récupérer les clés privées de A et de B quand elles partagent un
facteur commun, et on est sur à 100% que c'est un problème de générateur
et pas une copie de clé privée.
Du coup, ça a permis d'identifier un problème avec les générateurs d'un
certain nombre de VPN/routeur, ce qui est un point positif.
Donc si on résume: certains systèmes embarqués ont des générateurs aléatoires faibles. Si leur générateur d'aléa est faible, alors la crypto (au sens large) basée dessus est faible, comme par exemple la génération de clés RSA. Dans ce cas, quelle est la nouveauté de l'article? (vraie question)
Deux point sont nouveaux en gros, sans être révolutionnaires : - jusqu'à présent la catégorie de clés faibles qu'on avait en tête était celle avec à la fois la clé publique identique, donc p *et* q identiques (faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique faible), le papier met en avant cette seconde catégorie quand seulement p ou bien seulement q est identique. - la seconde catégorie est quelque part encore plus pourrie que la première :-)
En effet quand on a 2 clé publique identique, on ne sait pas instantanément si c'est vraiment un mauvais générateur ou si c'est quelqu'un qui a réutilisé 2 fois la même clé. Même quand c'est à peu près évident que c'est dû à un mauvais générateur aléatoire, A peut attaquer B et réciproquement, mais un tiers C auquel ni A ni B ne transmet la clé privé doit retrouver de quel générateur il s'agit, quel soft, sous quelles conditions, pour recréer la même collision et casser la clé. Suivant le cas, c'est très facile ou quand même un peu moins.
Avec cette nouvelle catégorie, c'est automatiquement instantané pour C de récupérer les clés privées de A et de B quand elles partagent un facteur commun, et on est sur à 100% que c'est un problème de générateur et pas une copie de clé privée. Du coup, ça a permis d'identifier un problème avec les générateurs d'un certain nombre de VPN/routeur, ce qui est un point positif.
Mehdi Tibouchi
Jean-Marc Desperrier wrote in message <jiis0b$odq$:
Deux point sont nouveaux en gros, sans être révolutionnaires : - jusqu'à présent la catégorie de clés faibles qu'on avait en tête était celle avec à la fois la clé publique identique, donc p *et* q identiques (faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique faible), le papier met en avant cette seconde catégorie quand seulement p ou bien seulement q est identique. - la seconde catégorie est quelque part encore plus pourrie que la première :-)
Même ce point n'est pas nouveau en fait. Il est par exemple mentionné dans cet exposé de Don Johnson en 1999 (voir en page 13) :
Mais je suppose qu'il y a une différence entre savoir qu'une vulnérabilité est possible en principe, et constater empiriquement qu'elle existe et est exploitable en pratique.
C'est comme la différence entre les nombreux papiers qui pointent les faiblesses de (EC)DSA lorsque l'aléa k n'est pas tiré uniformément au hasard d'une part, et le fait de retrouver la clef secrète des PlayStation 3 d'autre part.
Cela dit, je ne me prononce pas sur la pertinence ou non d'aller faire la publicité d'un résultat comme celui-là jusque dans les colonnes du New York Times.
-- M. Tibouchi.
Jean-Marc Desperrier wrote in message
<jiis0b$odq$1@writer.imaginet.fr>:
Deux point sont nouveaux en gros, sans être révolutionnaires :
- jusqu'à présent la catégorie de clés faibles qu'on avait en tête était
celle avec à la fois la clé publique identique, donc p *et* q identiques
(faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique
faible), le papier met en avant cette seconde catégorie quand seulement
p ou bien seulement q est identique.
- la seconde catégorie est quelque part encore plus pourrie que la
première :-)
Même ce point n'est pas nouveau en fait. Il est par exemple mentionné
dans cet exposé de Don Johnson en 1999 (voir en page 13) :
Mais je suppose qu'il y a une différence entre savoir qu'une
vulnérabilité est possible en principe, et constater empiriquement
qu'elle existe et est exploitable en pratique.
C'est comme la différence entre les nombreux papiers qui pointent les
faiblesses de (EC)DSA lorsque l'aléa k n'est pas tiré uniformément au
hasard d'une part, et le fait de retrouver la clef secrète des
PlayStation 3 d'autre part.
Cela dit, je ne me prononce pas sur la pertinence ou non d'aller faire la
publicité d'un résultat comme celui-là jusque dans les colonnes du New
York Times.
Jean-Marc Desperrier wrote in message <jiis0b$odq$:
Deux point sont nouveaux en gros, sans être révolutionnaires : - jusqu'à présent la catégorie de clés faibles qu'on avait en tête était celle avec à la fois la clé publique identique, donc p *et* q identiques (faille OpenSSL/Debian, qui a donné lieu à une liste de clé publique faible), le papier met en avant cette seconde catégorie quand seulement p ou bien seulement q est identique. - la seconde catégorie est quelque part encore plus pourrie que la première :-)
Même ce point n'est pas nouveau en fait. Il est par exemple mentionné dans cet exposé de Don Johnson en 1999 (voir en page 13) :
Mais je suppose qu'il y a une différence entre savoir qu'une vulnérabilité est possible en principe, et constater empiriquement qu'elle existe et est exploitable en pratique.
C'est comme la différence entre les nombreux papiers qui pointent les faiblesses de (EC)DSA lorsque l'aléa k n'est pas tiré uniformément au hasard d'une part, et le fait de retrouver la clef secrète des PlayStation 3 d'autre part.
Cela dit, je ne me prononce pas sur la pertinence ou non d'aller faire la publicité d'un résultat comme celui-là jusque dans les colonnes du New York Times.
-- M. Tibouchi.
Jean-Marc Desperrier
Mehdi Tibouchi a écrit :
Il est par exemple mentionné dans cet exposé de Don Johnson en 1999 (voir en page 13) :
Mais je suppose qu'il y a une différence entre savoir qu'une vulnérabilité est possible en principe, et constater empiriquement qu'elle existe et est exploitable en pratique.
Merci pour cette référence, elle est très intéressante.
Cependant je vois un deuxième point qui fait une grosse différence sur le "exploitable en pratique" : Le papier décrit une méthode pas performante du tout en terme de complexité algorithmique, et du coup pour illustrer prend un cas où on a relativement peu de clé à tester et un espoir important de trouver une collision.
Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça donne envie de tester même quand on ne crois pas trop que ça va réussir.
Ceci dit l'algo optimisé est plutôt évident, il est bien possible qu'il avait été publié avant si on fouille les archives.
Mehdi Tibouchi a écrit :
Il est par exemple mentionné
dans cet exposé de Don Johnson en 1999 (voir en page 13) :
Mais je suppose qu'il y a une différence entre savoir qu'une
vulnérabilité est possible en principe, et constater empiriquement
qu'elle existe et est exploitable en pratique.
Merci pour cette référence, elle est très intéressante.
Cependant je vois un deuxième point qui fait une grosse différence sur
le "exploitable en pratique" : Le papier décrit une méthode pas
performante du tout en terme de complexité algorithmique, et du coup
pour illustrer prend un cas où on a relativement peu de clé à tester et
un espoir important de trouver une collision.
Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça
donne envie de tester même quand on ne crois pas trop que ça va réussir.
Ceci dit l'algo optimisé est plutôt évident, il est bien possible qu'il
avait été publié avant si on fouille les archives.
Mais je suppose qu'il y a une différence entre savoir qu'une vulnérabilité est possible en principe, et constater empiriquement qu'elle existe et est exploitable en pratique.
Merci pour cette référence, elle est très intéressante.
Cependant je vois un deuxième point qui fait une grosse différence sur le "exploitable en pratique" : Le papier décrit une méthode pas performante du tout en terme de complexité algorithmique, et du coup pour illustrer prend un cas où on a relativement peu de clé à tester et un espoir important de trouver une collision.
Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça donne envie de tester même quand on ne crois pas trop que ça va réussir.
Ceci dit l'algo optimisé est plutôt évident, il est bien possible qu'il avait été publié avant si on fouille les archives.
Mehdi Tibouchi
Jean-Marc Desperrier wrote in message <jj2e1t$t7v$:
Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça donne envie de tester même quand on ne crois pas trop que ça va réussir.
Le papier de Lenstra et al. prend spécifiquement soin de ne pas mentionner l'algo quasi-linéaire utilisé, et les auteurs considèrent qu'il est évident pour le spécialiste (« sapienti sat », écrivent-ils), donc on peut difficilement parler de « nouvel algo publié ».
Jean-Marc Desperrier wrote in message
<jj2e1t$t7v$1@writer.imaginet.fr>:
Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça
donne envie de tester même quand on ne crois pas trop que ça va réussir.
Le papier de Lenstra et al. prend spécifiquement soin de ne pas
mentionner l'algo quasi-linéaire utilisé, et les auteurs considèrent
qu'il est évident pour le spécialiste (« sapienti sat », écrivent-ils),
donc on peut difficilement parler de « nouvel algo publié ».
Jean-Marc Desperrier wrote in message <jj2e1t$t7v$:
Alors qu'avec le nouvel algo publié, c'est hyper efficace, et ça, ça donne envie de tester même quand on ne crois pas trop que ça va réussir.
Le papier de Lenstra et al. prend spécifiquement soin de ne pas mentionner l'algo quasi-linéaire utilisé, et les auteurs considèrent qu'il est évident pour le spécialiste (« sapienti sat », écrivent-ils), donc on peut difficilement parler de « nouvel algo publié ».
