La génération aléatoire de clés RSA ne laisse pas assez de place au hasard

L’algorithme utilisé pour générer des certificats X.509 ou encore des clés de chiffrement PHP n’est pas aussi sûr que l’on pouvait l’imaginer jusqu’ici. La découverte en a été faite par des chercheurs en cryptographie. Ceux-ci indiquent avoir procédé à une «vérification de l’état sanitaire de clés publiques trouvées sur Internet», avec pour objectif de «tester la validité de l’assertion selon laquelle un choix aléatoire différent est fait à chaque fois que des clés sont générées ». Une opération qui a échoué : «la vaste majorité des clés publiques fonctionne comme prévu» mais «deux modulos RSA pour mille n’offrent aucune sécurité ». Pourquoi ? Notamment parce qu’il y a des duplicatas, bien involontaires, certes, mais dont l’existence même pose problème. 

Concrètement, les chercheurs aboutissent à la conclusion «qu’il y a plus de duplicatas» que ce que les études précédentes avaient pu laisser penser : «sur 6,4 millions de modulos RSA distincts, 71504 (1,1 %) apparaissent plus d’une fois, et même des milliers de fois pour certains.» Pire, ils assurent avoir trouvé 12934 modulos RSA n’offrant aucune sécurité : «les clés privées [correspondantes] sont accessibles à n’importe qui prendrait la peine de reproduire notre travail », assurent-ils. Et d’estimer ainsi que, au mieux, l’algorithme RSA 1024 bits offre une sécurité de 99,8 %. Pour ces chercheurs, le chiffrement basé sur un secret unique - et non pas sur un couple clé privé/clé publique - et sur l’algorithme Diffie-Hellman serait finalement plus sûr.

Pour l’expert Bruce Schneier, c’est un «excellent travail» qu’on fait là les chercheurs. Mais pour lui, l’algorithme RSA ou le principe du chiffrement asymétrique ne sont pas remis en cause par cette étude : le problème vient «presque certainement du générateur de nombres aléatoires» utilisé pour la création de ces clés publiques. Et «cela ne devrait surprendre personne. L’un des points les plus difficiles de la cryptographie est la génération de nombres aléatoires ». Et d’ajouter que «la capacité à produire quelque chose d’aléatoire n’est pas une exigence fonctionnelle et à moins que vous ne la testiez spécifiquement - et que vous sachiez comment la tester - vous penserez probablement que votre système cryptographique fonctionne correctement ».

En fait, pour les chercheurs, c’est environ 0,003 % des clés RSA publiques qui est potentiellement vulnérable, « ce qui ne semble pas inacceptable ». Pour Bruce Schneier, il y a effectivement un risque mais il est difficile à quantifier. Et la nature aléatoire - encore - de la menace fait «qu’il est difficile de savoir comment monétiser» la faille. Ce qui tend à réduire la menace concrète. Toutefois, il s’interroge sur l’éventualité de générateurs de nombres aléatoires «volontairement affaiblis. Les suspects les plus évidents sont les services de renseignement nationaux comme la NSA. Je n’ai aucune preuve mais si je devais affaiblir des systèmes de chiffrement, je commencerais par les générateurs de nombres aléatoires.»