Des chercheurs trouvent une faille dans l’algorithme RSA

[Hinault Romaric]

Des chercheurs trouvent une faille dans l’algorithme RSA
utilisé pour chiffrer les échanges en ligne


Une équipe de chercheurs européens et américains a découvert une faille dans le système de cryptographie RSA (Rivest Shamir Adleman), très utilisé dans le commerce en ligne et pour les échanges de données sur internet.

La faiblesse se situe au niveau de la façon dont les clés publiques sont générées en utilisant l’algorithme RSA pour le chiffrement des données. Les chercheurs ont découvert qu’une petite fraction de clés publiques (27 000 sur un échantillon d’environ 7 millions) n’avait pas été générée de façon aléatoire comme il se doit. Ce qui signifie qu’il serait possible que quelqu’un puisse retrouver la clé privée qui a été utilisée pour créer des clés publiques.

Concrètement l’algorithme RSA nécessite la création d’une clé privée secrète et de clés publiques qui sont utilisées pour chiffrer les données confidentielles qui pourront être déchiffrées avec la clé privée. Pour fonctionner correctement, les clés publiques doivent être générées de façon aléatoire.

« Nous avons constaté qu’une grande majorité des clés publiques fonctionnent comme prévu » écrivent les chercheurs dans leur rapport. « Un constat plus déconcertant, est qu’un certain nombre de clés RSA que nous avons recueillies n’offrent aucune sécurité ».

Malgré le petit nombre d’utilisateurs touchés par la faille, le danger potentiel est que la confiance pour l’algorithme de sécurité RSA soit réduite, selon les chercheurs qui estiment par ailleurs que cette faille pourrait déjà être découverte par quelqu’un d’autre.

« Le manque de sophistication de nos méthodes et les conclusions font qu’il est difficile pour nous de croire que ce que nous avons présenté est nouveau, en particulier pour les organismes qui sont reconnus pour leur curiosité dans la matière » notent les chercheurs.

Les chercheurs ont décrit leur travail dans un document qui sera présenté lors de la conférence de cryptographie qui se tiendra en Californie en Aout, mais ont rendu les conclusions de leur étude publique, parce qu’ils estiment que la question est d’un intérêt immédiat pour les services utilisant RSA.
Source : Le rapport des chercheurs (au format PDF)


Et vous ?

Que pensez-vous de cette découverte ? Remet-t-elle en cause l’algorithme RSA ?

[Neko]

Ça fait 0.38%, même si c'est pas énorme, c'est pas négligeable

[transgohan]

Cela veut surtout dire que c'est pas l'algorithme qui est à remettre en question mais l'homme. La faille n'est, d'après ce que je comprend, pas dans l'algorithme mais est créée par ceux qui tentent de l'utiliser pour protéger leurs données.

Donc non elle ne remet pas en cause l'algorithme, elle remet juste en cause les compétences des informaticiens qui ont générés ces 27 000 clés.

[tomlev]

Les chercheurs ont découvert qu’une petite fraction de clés publiques (27 000 sur un échantillon d’environ 7 millions) n’avait pas été générée de façon aléatoire comme il se doit

Donc c'est pas l'algorithme RSA qui est en cause, mais la façon dont certaines personnes ont généré leurs clés... Parler de "faille" est donc un peu abusif. C'est un peu comme si j'avais utilisé "toto" comme mot de passe sur Gmail, et que mon compte avait été piraté : je ne pourrais m'en prendre qu'à moi-même, pas à la sécurité de Gmail...

[atha2]

Envoyé par tomlev

Donc c'est pas l'algorithme RSA qui est en cause, mais la façon dont certaines personnes ont généré leurs clés... Parler de "faille" est donc un peu abusif. C'est un peu comme si j'avais utilisé "toto" comme mot de passe sur Gmail, et que mon compte avait été piraté : je ne pourrais m'en prendre qu'à moi-même, pas à la sécurité de Gmail...

Sauf que Gmail te prévient que ton mot de passe n'est pas assez sécurisée
Sinon j'aime bien cette préconisation tirée du rapport

It is better to make sure that cryptographic keys are generated only after proper initialization of the source of randomness.

...

[ithel]

@atha2 et @transgohan
j'allais répondre la même chose que vous, mais après avoir lu (rapidement je l'admet) l'article, il s'avère que c'est bien un élément de l'algorithme qui pose problème: la faiblesse se situerait au niveau du calcul de la valeur du modulo (qui correspond à la multiplication des deux nombres premiers générés aléatoirement). A priori cette valeur serait parfois trop facile à décomposer.

[MiaowZedong]

Envoyé par ithel

@atha2 et @transgohan
j'allais répondre la même chose que vous, mais après avoir lu (rapidement je l'admet) l'article, il s'avère que c'est bien un élément de l'algorithme qui pose problème: la faiblesse se situerait au niveau du calcul de la valeur du modulo (qui correspond à la multiplication des deux nombres premiers générés aléatoirement). A priori cette valeur serait parfois trop facile à décomposer.

Non, ce n'est pas l'algorithme qui est remis en cause, mais bien la façon dont les clés sont generées. Certains facteurs premiers possibles sont trop utilisés dans la vraie vie, alors qu'en théorie chaque clé doit être complétement unique.

De toute façon, on savait déjà que les nombres aléatoires sont trop importants pour être generés au hasard

[atha2]

Envoyé par ithel

@atha2 et @transgohan
j'allais répondre la même chose que vous, mais après avoir lu (rapidement je l'admet) l'article, il s'avère que c'est bien un élément de l'algorithme qui pose problème: la faiblesse se situerait au niveau du calcul de la valeur du modulo (qui correspond à la multiplication des deux nombres premiers générés aléatoirement). A priori cette valeur serait parfois trop facile à décomposer.

Oui mais il faut bien générer le modulo (P et Q) et c'est là apparemment où est le problème (cf citation du rapport dans mon précédent poste).
De ce que j'ai compris de l'article (après l'avoir lu rapidement aussi, j’avoue), l'algo vérifie que la valeur de P et Q est assez grande mais dans un contexte local, il ne peut pas savoir que leurs valeurs n'est pas si aléatoire que ça.

Envoyé par tomlev

Donc c'est pas l'algorithme RSA qui est en cause, mais la façon dont certaines personnes ont généré leurs clés... Parler de "faille" est donc un peu abusif. C'est un peu comme si j'avais utilisé "toto" comme mot de passe sur Gmail, et que mon compte avait été piraté : je ne pourrais m'en prendre qu'à moi-même, pas à la sécurité de Gmail...

Oui la faille n'est pas dans RSA lui même mais dans le système de certification basé sur RSA en place. Il faudrait régénérer tout les certificats.

[Petrolevb]

Pas certain que ça soit réellement les utilisateurs : une des failles de l'algorithme pourrait être au moment de vérifier si les deux nombres sont bien premiers, je ne sais pas si c'est réellement une vérification ou alors simplement un algorithme avec des probabilités (=> même infiniment faible, cela reste non nul...)

Après faudrait aussi tester avec 10M de clefs générées réellement par eux... (mais bon ca peut prendre un peu de temps )

[rambc]

Bonjour.
je vais compléter le message de Petrolevb ci-dessus.

L'algorithme RSA nécessite d'avoir deux grands nombres premiers P et Q pour former un nombre N = PQ. Le but du jeu est de rendre concrètement impossible la factorisation de N : par exemple, si P = 2, le cryptage est cassé.

Le problème de la détermination de P et Q n'est pas simple. On ne va pas utiliser un algorithme déterministe car ce dernier devra s'exécuter en un temps raisonnable, or si on utilise un tel algorithme, quelqu'un de malvaillant pourrait aussi s'en servir de façon brutale pour essayer de factoriser N. Voir au passage le test de primalité AKS.

Du coup, on cherche de très grands nombres premiers, et c'est à ce stade que l'on fait appel à des algorithmes probabilistes de recherche de nombres premiers. Ce type d'algorithme doit être efficace, c'est à dire concrètement rapide à utiliser, et sûr, c'est à dire produire peu de faux nombres premiers, et c'est peut-être là que les chercheurs ont trouvé des failles. Voir au passage le test de primalité de Miller-Rabin.

En espérant avoir été clair...

[shenron666]

Envoyé par Hinault Romaric

« Nous avons constaté qu’une grande majorité des clés publiques fonctionnent comme prévu » écrivent les chercheurs dans leur rapport. « Un constat plus déconcertant, est qu’un certain nombre de clés RSA que nous avons recueillies n’offrent aucune sécurité ».

dire "un certain nombre de clés RSA [...] n’offrent aucune sécurité" est assez exagéré
ce n'est pas donné à tout le monde d'exploiter ce genre de faille

[vohufr]

Ca me rappelle lorsque il y a quelques années, ils ont dû dévalider toutes les clefs ssh lors d'une mise à jour...