Au sujet des 0.2% des clés RSA faibles

Le
Kevin Denis
Bonjour,

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
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Mehdi Tibouchi
Le #24283011
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
Le #24284031
Le 27-02-2012, Mehdi Tibouchi
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
Le #24284061
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
Le #24285901
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.
Mehdi Tibouchi
Le #24287221
Jean-Marc Desperrier wrote in message

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) :

http://www.comms.engg.susx.ac.uk/fft/crypto/ECCFut.pdf

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
Le #24297951
Mehdi Tibouchi a écrit :
Il est par exemple mentionné
dans cet exposé de Don Johnson en 1999 (voir en page 13) :

http://www.comms.engg.susx.ac.uk/fft/crypto/ECCFut.pdf

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
Le #24307351
Jean-Marc Desperrier wrote in message

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é ».
Publicité
Poster une réponse
Anonyme