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

Date :
Mis à jour le 02/03/2020
Pendant plus de 18 mois, des chercheurs et chercheuses en informatique ont mobilisé la puissance de calcul de superordinateurs afin de tester des algorithmes de cryptographie, établissant un nouveau record de cryptanalyse. Un tour de force numérique qui permet d’éprouver la robustesse de certaines clés de chiffrement. Décryptage avec Emmanuel Thomé et Aurore Guillevic, experts du domaine à Inria Nancy Grand-Est.

 

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
Photo Cécile Pierrot
Emmanuel Thomé, Pierrick Gaudry, Aurore Guillevic et Paul Zimmermann
Emmanuel Thomé, Pierrick Gaudry, Aurore Guillevic et Paul Zimmermann


 

 

* CARAMBA (Cryptology, arithmetic : algebraic methods for better algorithms) regroupe une quinzaine de chercheurs et chercheuses d’Inria Nancy et de l’université de Lorraine.

** Il s’agit de trouver la fonction inverse au calcul d’une exponentielle pour certains nombres entiers.

*** PRACE (Partnership for Advanced Computing in Europe) est une association internationale mettant à disposition des chercheurs et ingénieurs de ses pays membres des ressources de calcul « haute performance ».

**** 1 To pour 1012 octets (ou 1 million de millions d’octets). 10 To représentent l’équivalent de dix millions de photographies numériques à 3 millions de pixels.

***** ANSSI : Agence nationale de la sécurité des systèmes d'information.