Un record de calcul au service de la sécurité informatique

La sécurité des systèmes d’information et de communication est l’un des enjeux technologiques majeurs de ce siècle. Au cœur de nombreux protocoles d’échanges, les clés de chiffrement assurent la sécurité des données échangées. « La confidentialité des échanges se fonde sur l’utilisation de deux clés de sécurité, explique Aurore Guillevic, chargée de recherche au sein de l’équipe CARAMBA* à Inria Nancy Grand-Est. La première, dite clé publique, permet à l’émetteur de chiffrer un message à l’attention de son destinataire ; la seconde, dite clé privée, permet à ce dernier de déchiffrer ce message. Les deux clés vont ensemble : assurer la sécurité du protocole consiste à garantir que l’on ne puisse pas trouver la clé privée à partir de la  publique. »

Sécuriser un chiffrement

« L’intégrité de la clé publique vis-à-vis d’attaques potentielles est assurée par des techniques de cryptographie utilisant des problèmes mathématiques extrêmement difficiles à résoudre », indique Emmanuel Thomé, directeur de recherche à Inria et responsable de l’équipe CARAMBA.

L’un de ces problèmes est connu sous le nom de « factorisation d’entiers ». Il s’agit de fabriquer une clé en multipliant deux nombres premiers de très grande taille. La cryptanalyse consiste, à partir du résultat de cette opération, à retrouver les deux nombres d’origine. Par exemple, 21 se décompose comme le produit de 3 et 7, deux nombres premiers. Un simple calcul mental donne dans ce cas le résultat. Pour des nombres de plus en plus grands, le calcul n’est réalisable qu’avec des ordinateurs et demande des algorithmes sophistiqués.

Un second algorithme, connu sous le nom de « logarithme discret », est également fondé sur la recherche d’une solution à une équation algébrique complexe**. Dans les deux cas, plus la clé de chiffrement est longue, plus la résolution du problème est difficile et le chiffrement robuste.

Éprouver la sûreté des clés

Les recherches de l’équipe CARAMBA consistent en particulier à développer des méthodes de « cryptanalyse » résolvant rapidement ces deux problèmes, ce qui permet d’éprouver la solidité des procédures de chiffrement ou d’en améliorer la robustesse. Les chercheurs s’appuient sur le logiciel CADO-NFS, développé à Nancy depuis 2007. Avec ses quelque 300 000 lignes de code, l’outil a nécessité le travail de nombreux experts, dont trois chercheurs de CARAMBA (Pierrick Gaudry du CNRS, Emmanuel Thomé et Paul Zimmermann, d’Inria) qui y travaillent depuis plus de dix ans. Il est conçu pour exploiter la puissance de calcul de superordinateurs, comme ceux de la plate-forme Grid'5000/SILECS ou du consortium européen PRACE***.

« Nous nous sommes intéressés aux clés de 795 bits. On peut trouver de petites clés comme celles-ci dans certaines applications embarquées, par exemple en télécommunications, car elles demandent peu de ressources de calcul », détaillent Emmanuel Thomé et Aurore Guillevic. « Avec 795 bits, on code un nombre entier de 240 chiffres, qu’il s’agit de décomposer avec l’algorithme de factorisation en deux nombres premiers de 120 chiffres. Le processus demande de manipuler une grande quantité de données (plus de 10 To****!) : 35 millions d’heures de calcul ont ainsi été nécessaires pour casser une clé de 795 bits. »

Édicter des recommandations de sécurité

Collaborant avec d’autres experts en cryptanalyse dont Nadia Heninger, de l’université de Calfornie, et Fabrice Boudot, de l’université de Limoges, l’équipe CARAMBA a ainsi établi un nouveau record de calcul et évalué l’efficacité de l’innovation apportée aux méthodes de cryptanalyse. Celle-ci a en particulier permis une accélération supplémentaire à l’amélioration constante de la puissance des processeurs (loi de Moore). Les chercheurs ont en outre montré que les deux algorithmes avaient des performances comparables, alors qu’il était admis jusqu’alors que celui du logarithme discret était plus complexe que celui de la factorisation d’entiers.

L’exercice n’est pas seulement théorique : si les moyens informatiques alloués paraissent démesurés et les compétences scientifiques pour les opérer très pointues, ils sont à la portée d’États qui peuvent développer des outils de cryptanalyse extrêmement performants.

Ces travaux contribuent entre autres à établir des recommandations en matière de cybersécurité que peuvent reprendre des agences de sécurité informatique, comme l’ANSSI***** en France. « Notre calcul montre les limites de fiabilité des clés de chiffrement et indique clairement que les clés à 795 bits ne sont pas robustes ! À ce jour, seules celles qui sont plus longues, supérieures à 2048 bits, apportent les garanties suffisantes. » Jusqu’à ce qu’un prochain record démontre le contraire ?

Emmanuel Thomé, Pierrick Gaudry, Aurore Guillevic et Paul Zimmermann

Emmanuel Thomé, Pierrick Gaudry, Aurore Guillevic et Paul Zimmermann