Quand le chiffrement des données est mis à mal par des mathématiciens

En mai dernier, la conférence Eurocrypt 2014 se tenait à Copenhague. Quatre chercheurs du CNRS, de l'INRIA et du Laboratoire d'informatique de Paris 6 y présentaient leurs travaux sur un algorithme qui met à mal certains systèmes de chiffrement. Depuis, nous avons pu nous entretenir avec l'un d'entre eux : Emmanuel Thomé. Si les conséquences restent pour le moment mesurées, il s'agit néanmoins d'un nouveau coup de semonce dans le petit monde de la cryptographie.

Je chiffre et tu déchiffres, mais « ils » décryptent

Avant toute chose, il est important d'apporter quelques précisions sur les termes utilisés en cryptographie. On parle en effet de « chiffrer » un message afin de le rendre incompréhensible, puis de le « déchiffrer » lorsque l'on dispose de la clé adéquate. Si ce n'est pas le cas, il s'agit alors de le « décrypter ». De son côté, l'Agence nationale de la sécurité des systèmes d’information (ANSSI) rappelle qu'« on entend cependant souvent parler de « cryptage » qui est un anglicisme, voire de « chiffrage », mais ces mots sont incorrects », ils ne devraient donc pas être utilisés dans le cas de la cryptographie. 

Quoi qu'il en soit, le chiffrement des données occupe une place de plus en plus importante dans notre vie quotidienne, poussé en partie par le numérique qui s'installe dans tous les domaines d'activités et le besoin croissant de sécurité. Transactions bancaires, achats de produits en ligne, conversations privées entre amis, emails, échange de documents sensibles, conversations sur IP, objets connectés, ou encore stockage des données sont autant d'exemples où la cryptographie et la sécurité jouent désormais un rôle central. Et si cela est vrai pour le grand public, cela prend une plus grande ampleur pour les entreprises, les institutions et même les pays, et ce ne sont pas les révélations d'Edward Snowden qui nous inciterons à penser le contraire.

Le chiffrement RSA, l'un des plus utilisés repose sur un postulat des plus basiques

Le principe de base du chiffrement est de modifier les données afin de les rendre incompréhensibles, sauf si l'on dispose de la clé permettant de les déchiffrer. De fait, même si vos conversations ou vos données venaient à être interceptées ou volées, il ne serait pas possible de les exploiter en l'état, à moins de les décrypter, ce qui peut prendre du temps, beaucoup de temps. Dans certains cas, il est en effet question de plusieurs milliards d'années avec une méthode basique.

C'est d'ailleurs sur cet élément que l'on juge la fiabilité d'un chiffrement. Car au final, la question n'est généralement pas de savoir s'il tombera, mais plutôt quand, ou au bout de combien de temps. Il existe actuellement de nombreux algorithmes, l'un des plus connus étant certainement le RSA du nom des trois chercheurs qui l'ont mis au point : Ronald Rivest, Adi Shamir et Leonard Adleman. Il est dit asymétrique puisqu'il fonctionne avec une paire de clés : l'une privée et l'autre publique, et repose sur la factorisation des entiers et les nombres premiers.

Du RSA 2048 bits utilisé sur le site des impôts

Pour faire simple, si multiplier deux nombres premiers p et q entre eux est relativement rapide pour n'importe quel ordinateur, le factoriser – c'est-à-dire retrouver p et q à partir de leur produit – est une autre paire de manches, surtout lorsque la taille des nombres augmente. Notez que l'on parle ici d'un nombre composé de plusieurs centaines de chiffres.

Sur le papier cela ne pose pas de souci particulier, mais cela se complique dans la pratique puisqu'il n'existe (encore ?) pas d'algorithme permettant de simplifier à l'extrême cette tâche. Il faut alors chercher les nombres p et q en testant des combinaisons les unes après les autres et en vérifiant qu'il s'agit bien de nombres premiers. Problème, même avec des ordinateurs ultra-puissants, cela demande beaucoup de temps puisque la durée augmente de manière exponentielle avec la taille des nombres.

RSA-768 est tombé il y a quatre ans, mais les autres résistent encore

Il existe d'ailleurs un concours de factorisation. RSA-768, qui est composé de 232 chiffres, est le dernier à être tombé en 2010 sous l'attaque de l'équipe CARAMEL, dont nous allons avoir l'occasion de reparler un peu plus tard.

La multiplication des deux nombres donne 12301866845301177551304949583849... puis encore 200 autres chiffres

Actuellement, on utilise couramment des clés asymétriques sur 2048 / 4096 bits ce qui devrait laisser une marge plutôt confortable, surtout dans le second cas. C'est d'ailleurs ce que recommande l'ANSII.

Une découverte qui, selon le CNRS, « secoue la cryptographie »

Dans l'histoire de la cryptographie, on a déjà vu d'autres systèmes de chiffrements tomber très rapidement, et ce, quelle que soit la clé utilisée. On se souviendra par exemple du WEP, un algorithme dérivé du RC-4, que l'on retrouvait dans le Wi-Fi au début des années 2000. Ratifié par l'IEEE 802.11, ce protocole de sécurité tombera rapidement à cause de plusieurs faiblesses dans sa conception. Quelques années plus tard, il ne faut plus que quelques minutes pour casser une clé WEP et certains logiciels comme Aircrack s'en font une spécialité. Il doit donc être éradiqué et remplacé par le WPA / WPA2. Cet exemple montre bien ce qu'une petite brèche dans un algorithme peut donner au final.

Justement, lors de la conférence Eurocrypt 2014 qui se tenait récemment à Copenhague, quatre chercheurs exposaient leurs travaux sur un nouvel algorithme (une formule mathématique) qui, selon le Centre National de la Recherche Scientifique (CNRS), « secoue la cryptographie ». Il s'agit de Pierrick Gaudry, de Razvan Barbulescu, d'Emmanuel Thomé et d'Antoine Joux. Les trois premiers font partie de l'équipe CARAMEL qui a cassé le RSA-768, tandis qu'Antoine Joux est un expert en sécurité chez CryptoExperts qui a gagné le prix Gödel en 2013. Autant dire que les quatre chercheurs n'en sont pas à leur coup d'essai et leurs travaux jouissent déjà d'une certaine réputation.

Quelles sont les implications sur les systèmes de chiffrement ?

« Secoue », le terme employé par le CNRS est fort. Mais il n'a pas été utilisé sans raison puisque leur découverte met à mal certains systèmes de chiffrement basés sur le logarithme discret et facilite grandement leur résolution. Si cela ne vous parle pas, le Loria (Laboratoire Lorrain de recherche en informatique et ses applications) donne quelques exemples concrets en expliquant que le logarithme discret « permet, entre autres, de sécuriser et fiabiliser de nombreux systèmes, comme les transactions financières via Internet ou le VPN ». Le laboratoire ne s'arrête pas là et enfonce le clou en revenant sur les travaux des quatre chercheurs : « étudié depuis plus de trois décennies, le problème semblait aussi dur que la factorisation (RSA) et cela pour n'importe quelle instance ». Le parallèle avec le RSA est intéressant, car ce dernier est largement utilisé aujourd'hui.

Si le logarithme discret n'est pas spécialement connu du grand public, en tout cas bien moins que le RSA, il reste tout de même très important. En 2012, François Morain, cryptographe au laboratoire LIX de l'école Polytechnique, expliquait sur le site des Editions Diamond que « contrairement au problème de la factorisation d’entiers qui attire beaucoup d’attention car il est lié de très près à la sécurité du cryptosystème RSA et du contenu de nos portefeuilles, celui du logarithme a reçu moins de lumière, alors qu’il est tout aussi important, sinon plus ». En effet, il indique que « les tunnels sécurisés sont souvent basés sur des protocoles proches du protocole historique de Diffie et Hellman [NDLR : qui exploite le logarithme discret]. La sécurité du tunnel repose sur la résistance de certains groupes finis aux algorithmes de calcul de logarithme discret ». 

La question est maintenant de savoir s'il faut ou non avoir « peur » pour la confidentialité de nos données et des transactions sur internet. Va-t-on se retrouver prochainement dans la même situation que pour le système de chiffrement WEP, mais avec des conséquences bien plus importantes ? Pour avoir plus de détails sur les tenants et les aboutissants de cette histoire, nous avons pu nous entretenir avec Emmanuel Thomé, chercheur à l'INRIA, mais également l'un des quatre mathématiciens à l'origine de cette découverte.

Emmanuel Thomé, chercheur au CNRS, répond à nos questions sur « son » algorithme

Tout d'abord, il est important de rappeler que ce n'est pas la première fois que les travaux de ce quatuor sont rendus publics. En effet, cette avancée majeure date du début de l'année dernière et leur travail avait alors déjà été mis en ligne. Nous avons donc tout d'abord commencé par interroger Emmanuel Thomé sur l'évolution de ces travaux durant l'année passée, afin de savoir quels avaient été les changements apportés entre la première publication début 2013 et la présentation qui s'est déroulée à Copenhague.

Le chercheur nous précise que ce temps a été mis à profit afin de remettre en ordre la présentation de l'algorithme, mais aussi afin de valider certains points. Il n'y a pas eu de nouvelle « révolution » durant ce laps de temps. 

Là où il est question de logarithme discret et de corps mathématiques

Il ajoute qu'il ne s'agit toujours que d'un travail théorique et nous précise aussi que le passage à la pratique n'est pas obligatoire et qu'il n'a pas toujours lieu dans ce genre de cas. De toute façon, il faut bien avouer que dans le petit monde de la sécurité informatique, connaître une méthode permettant de casser un code suffit à le faire tomber en disgrâce. Car le danger, même potentiel, pourrait avoir des impacts trop importants pour être négligé.

Emmanuel Thomé nous a ensuite précisé que l'algorithme mis au point par son équipe ne fonctionne pour le moment que sur un champ d'action restreint : le logarithme discret sur des corps de petite caractéristique. Pour faire simple, un corps mathématique est un ensemble comprenant plusieurs éléments, suivants certaines règles. On peut par exemple citer les nombres rationnels, les réels, les complexes, etc. D'autres types de corps, utilisés en cryptographie ont un nombre fini d'éléments. Ce nombre est toujours une puissance d'un nombre premier, et ce nombre premier est appelé la caractéristique. Par exemple un corps à 2^160 éléments est de caractéristique 2

De son côté, le logarithme discret est une formule mathématique, proche du logarithme « traditionnel », mais que l'on utilise dans d'autres des groupes mathématiques que les nombres réels. À titre d'exemple, le logarithme de 100 en base 10 est 2 (10^2 = 100). On appelle sa réciproque, la fonction exponentielle. On peut ainsi passer de l'un à l'autre grâce à des calculs mathématiques, ce qui est utilisé comme base pour certains systèmes de chiffrement.

Une évolution possible vers d'autres systèmes de chiffrement, y compris le RSA

Bien évidemment, la question du passage à d'autres corps mathématiques est envisagée, mais il reste encore d'importantes barrières à franchir pour que cela puisse fonctionner. En tout état de cause, ce n'est pas le cas actuellement. Sur de grands corps mathématiques, on retrouve des systèmes de chiffrement comme Diffie-Hellman et El Gamal, ce dernier étant d'ailleurs présent dans certaines versions de GnuPG et de PGP.

Il ne sont donc pas touchés par l'algorithme des quatre chercheurs pour le moment. Mais pour Thomé, il n'est pas illogique de penser qu'il pourrait aussi s'attaquer au chiffrement RSA, même si c'est loin d'être le cas actuellement.

De toute façon, on peut en faire ce qu'on veut, tous les messages finiront par devenir des 0 et des 1

Une évolution pas simple, certains chiffrements offrent moins de « prises » que d'autres

Il nous précise tout de même que dans la pratique les choses ne sont néanmoins pas simples. En effet, en faisant une analogie avec un alpiniste qui tente de grimper une paroi qui n'a jamais été franchie, l'algorithme sur le logarithme discret dans les corps de petites caractéristiques proposait déjà quelques points d'accroches afin de commencer l'ascension, ce qui n'est pas toujours le cas. Par exemple, les algorithmes basés sur le logarithme discret dans le groupe des courbes elliptiques offrent bien moins de prises dès le départ et s'attaquer à ce code est donc bien plus difficile.

Pour autant, il tient à se montrer rassurant et à préciser que ce n'est pas encore demain qu'un site comme Amazon par exemple tombera sous les coups de son algorithme. Mais dans le monde de la cryptographie qui, pour rappel, repose sur des calculs mathématiques et sur le temps nécessaire à les mener à bien, l'impact est important. Encore une fois, la question n'est pas de savoir si un code tombera, mais quand.

Quid de la sécurité des codes actuels ? Tout n'est finalement que question de temps...

Ces travaux ont des répercussions sur d'autres expérimentations en cours, notamment en ce qui concerne le chiffrement par couplages qui était en cours de développement par plusieurs laboratoires de recherche et qui prennent donc de plein fouet ce nouvel algorithme. Emmanuel Thomé précise que la plupart des travaux sur les couplages en petite caractéristique ont été stoppés net.

Nous avons alors abordé un sujet plus vaste sur la cryptographie et la résistance des codes dans le temps. En effet, lorsque l'on crée un code cryptographique, un des éléments de base est de déterminer la durée pendant laquelle on souhaite qu'il soit fiable et donc qu'il résiste aux attaques. 

Le chercheur du CNRS nous a cité deux exemples. Tout d'abord, les passeports qui ont une durée de validité de 10 ans. Il ne faut donc pas que le chiffrement puisse être cassé durant ce laps de temps, finalement assez court. D'un autre côté, le stockage de documents chiffrés avec une clé asymétrique et là, la situation est bien différente. Notre interlocuteur ne prendrait en effet pas de paris sur la sécurité d'un tel chiffrement pendant une durée d'un siècle par exemple, ce qui peut paraître relativement long, mais finalement assez court selon les points de vues et les documents concernés. D'autant plus que la puissance de calcul dans le monde de l'informatique ne cesse de croitre et qu'il est de plus en plus facile d'accéder à de gros « clusters ».

... et cela dépend grandement de la taille de votre clé de chiffrement

Quel que soit l'algorithme utilisé, il est donc bien important de bien dimensionner sa clé. Dans le cas du RSA par exemple, on a pu remarquer qu'une clé sur 768 bits était cassable et il vaut donc mieux aller largement plus haut. Néanmoins, pour d'autres systèmes de chiffrement, une clé de 128 bits peut être largement suffisante, cela dépend en fait des corps mathématiques sur lesquels elles s'appliquent.

Afin de donner quelques idées, l'ANSSI (Agence nationale de la sécurité des systèmes d’information) indique des règles ainsi que des recommandations sur la taille minimale des clés que l'on doit utiliser. On les trouve au sein de ce document : le référentiel général de sécurité (v 2.0 du 26 avril 2012). Certains diront que les niveaux sont trop faibles afin que l'agence puisse, si besoin casser les codes, mais dans tous les cas il s'agit d'une base de travail intéressante.

En voici deux exemples :

• Clé symétrique (DES par exemple) : 100 bits jusqu'en 2020, 128 bits ensuite
• Clé asymétrique (RSA par exemple) : 2048 bits jusqu'en 2030, 3072 bits ensuite

L'agence précise par contre un point important concernant les clés asymétriques : « la taille des modules RSA est un sujet souvent très polémique. L’usage courant fait que l’utilisation de modules de 1024 bits est en général considérée comme suffisante pour garantir une sécurité pratique, même si les analyses effectuées par les plus grands spécialistes du domaine s’accordent sur l’idée que de tels modules n’apportent pas une sécurité suffisante, ou tout du moins comparable à celle que l’on exige des autres mécanismes cryptographiques ».

En effet, même si une clé sur 1024 bits n'a pas été factorisée pour le moment, le principe de précaution veut que l'on passe au minimum au cran du dessus. De plus, les révélations faites par Edward Snowden sur les agissements de la NSA laissent penser que l'agence américaine dispose d'une capacité de calcul phénoménale, la prudence doit donc être de mise suivant le degré de sécurité recherché. Puis, il devient assez facile d'utiliser des clés de 2048 ou de 4096 bits, donc pourquoi s'en priver ?

Crédit image : référentiel de l'ANSSI, page 47

Du côté de PGP, l'outil de chiffrement créé par Phil Zimmermann et récupéré par Symantec, on est un peu plus prudent et on prend comme base de travail une étude des Dr Lenstra et Verheul : « selon leurs calculs, une clé sur 2048 bits devrait [NDLR : notez l'emploi du conditionnel par les scientifiques] protéger vos secrets jusqu'en 2020, même contre des adversaires bien informés et disposant de nombreuses ressources (la NSA par exemple). Contre les adversaires de moindre importance comme les multinationales, vos secrets devraient être protégés beaucoup plus longtemps d'une attaque par force brute, même avec une clé de seulement 1024 bits ». Cette dernière hypothèse semble tout de même bien légère et on ne saurait que vous conseiller de passer au 2048 bits, voire tout simplement au 4096 bits pour être tranquille.

Pour rappel, il n'existe aucune limitation en France en ce qui concerne la taille d'une clé de chiffrement, au moins pour les particuliers, et ce depuis 2004. Libre à vous d'en choisir une aussi longue que vous le souhaitez, mais attention avec la taille le temps de traitement des données augmente aussi.

Un chiffrement totalement inviolable existe, du moins en théorie

Sachez enfin qu'il existe au moins un code totalement inviolable, mais à condition de respecter strictement certaines règles : le chiffre de Vernam (ou masque jetable). C'est le cas d'une permutation aléatoire de l'alphabet, qui serait réellement aléatoire, ce qui est tout sauf simple, avec une clé de chiffrement qui soit au moins aussi longue que le message à chiffrer.

En effet, avec ce système de chiffrement, il est impossible de savoir si un mot de huit lettres donnera éclatées, vagirons, macramés, japonnés... et l'on pourrait prendre les 38341 mots trouvés par ici comme exemple. Seule solution pour le savoir : connaitre la clé. Notez au passage qu'il serait totalement inutile de tenter une analyse séquentielle sur le texte chiffré afin de déterminer la lettre la plus utilisée, qui est généralement le e, car la permutation change de manière aléatoire à chaque fois.

L'histoire raconte qu'il s'agirait du procédé utilisé entre le Kremlin (Russie) et la Maison Blanche (États-Unis) pour sécuriser le fameux « téléphone rouge ». Dans cette situation, il reste tout de même un problème de taille : faire transiter les clés qui doivent absolument rester secrètes puisqu'il suffit que quelqu'un les intercepte pour qu'il accède ensuite à toutes les correspondances chiffrés.

Doit-on devenir totalement paranoïaque ? Non, enfin pas plus que d'habitude 

Quoi qu'il en soit, la question principale était la suivante : faut-il avoir peur des systèmes de chiffrement actuels et de l'annonce des quatre chercheurs ? En effet, pour la plupart des utilisateurs il n'est pas toujours évident de faire la part des choses.

Mais n'ayez pas trop d'inquiétude dans l'immédiat, car la réponse est non... du moins pour le moment. Le coup de semonce évoqué ici ne remet pas en cause la sécurité des sites qui utilisent souvent d'autres systèmes de chiffrement que le logarithme discret sur les corps de petites caractéristiques. De plus, la relève est déjà en route avec la cryptographie quantique, que ce soit pour l'échange de clés ou le chiffrement des messages, mais il s'agit là d'un tout autre sujet.

De plus, comme nous avons pu le voir avec Heartbleed, les problèmes de sécurité ont bien plus de chances de venir d'une faille d'un des protocoles, et nous ne parlerons même pas de la crédulité des utilisateurs et donc de la première des faiblesses : celle située entre la chaise et le clavier.

• Lire l'article de Pierrick Gaudry, de Razvan Barbulescu, d'Emmanuel Thomé et d'Antoine Joux