Deux chercheurs français créent un algorithme avec une backdoor

Eric Filiol et un doctorant de l’ESIEA ont développé le premier algorithme relativement similaire à l’AES. Particularité, il contient une backdoor de nature mathématique qu’il s’agit de trouver. Au-delà de ce défi, il s’agit de faire prendre conscience de la menace que représentent les algorithmes fournis par des puissances étrangères. Dans cette interview, Eric Filiol évoque également les derniers développements de GostCrypt.

Eric Filiol, Directeur du Laboratoire Confiance Numérique et Sécurité de l’ESIEA.

 

 

Propos recueillis par Philippe Richard

Vous publiez un algorithme de type AES avec une backdoor exploitable. Que recherchez-vous en développant BEA 1 ?

Éric Filiol : Il s’agit de la première concrétisation d’un travail de recherche commencé il y a quelques années. J’ai eu la chance de trouver un thésard brillant, Arnaud Bannier, qui a accepté un sujet de thèse plutôt très mathématique, mais avec des applications opérationnelles. Je n’arrivais pas, jusque-là, à en trouver un qui accepte de m’accompagner sur ce type de recherche. L’idée de départ est la suivante : les USA ont depuis les années 70s orienté voire influencé le monde vers la technologie des chiffrements par blocs (le DES puis l’AES) au détriment des chiffrements par flot (majoritairement utilisés dans le monde gouvernemental jusqu’à encore récemment). Or cette technologie de chiffrement par bloc est par nature propice pour y cacher des backdoors de nature mathématique – du fait de son extraordinaire richesse combinatoire, c’est-à-dire le nombre de ses états internes, des structures qu’ils peuvent composer et des interactions entre ces structures.

En gros, il existe deux types de backdoors (portes dérobées) de nature mathématique :

  • Une faiblesse non connue de l’auteur de l’algorithme, mais connue de l’organisme de validation, de certification et de standardisation. Le meilleur exemple est probablement celui de la cryptanalyse différentielle connue par la NSA (selon les estimations de la plupart des chercheurs) environ 20 ans avant la publication de Biham et Shamir, inventeurs de ce type d’attaque. Ce type de backdoor n’est possible que si les organismes d’évaluation ou de décision disposent d’une avance scientifique significative par rapport à la communauté scientifique ouverte. C’est à ce jour le cas pour la NSA, le GCHQ et de rares autres. Encore faut-il avoir la capacité d’agir et d’influencer les standards internationaux. C’est le cas uniquement avec le NIST et ses liens troubles avec la NSA.

  • Une faiblesse voulue et conçue par l’auteur de l’algorithme. Il n’existe aucun cas public connu. En revanche ces cas sont relativement nombreux dans le domaine étatique (rappelons que de nos jours beaucoup de pays achètent encore leurs moyens de chiffrement gouvernementaux à des puissances extérieures). On pourrait cependant considérer que le cas du générateur de clef DUAL ECC DRBG [1,2] peut rentrer dans cette catégorie.

On peut supposer voire craindre que l’AES appartient peut être à la première catégorie et le DES à la seconde. Il ne faut pas oublier que nous ne savons toujours pas si le DES contient ou non une telle backdoor et nous n’avons aucune garantie que la NSA n’en a pas découverte dans le candidat Rijndael. Or rappelons-nous que pour le DES, la NSA a profondément modifié l’algorithme Lucifer originel et qu’elle a participé très activement au processus d’évaluation technique du concours AES et donc de l’actuel standard mondial de chiffrement, sous la conduite du NIST, sans obligation de publier ses résultats.

Comme prouver l’existence éventuelle d’une backdoor est un problème extrêmement complexe et donc hors de portée avec les outils actuels (mathématique et/ou calculatoires), notre recherche consiste à prouver qu’il est possible d’en cacher une. Le but est d’attirer plus que jamais l’attention sur le risque d’utiliser des algorithmes de chiffrement fournis par d’autres. C’est un problème de souveraineté nationale. Le général de Gaulle avait imposé que les algorithmes pour les usages nationaux soient de conception française. Or depuis quelques années, nous adoptons les standards (concepts mathématiques voire les algorithmes) que les USA nous incitent (fortement) à utiliser. C’est une véritable pollution scientifique et intellectuelle.

Avec BEA-1, il s’agit d’un premier algorithme (clef de 120 bits de clef, blocs de 80 bits, 11 tours) relativement similaire à l’AES, quant aux paramètres et primitives cryptographiques employées. Il contient une backdoor (opérationnellement exploitable) d’un type assez simple. Nous espérons qu’elle sera trouvée rapidement. En revanche, la façon optimale (et donc opérationnelle) de l’exploiter, en termes de temps de calcul, du nombre de couples clair-chiffré, est peut-être plus compliquée à déterminer. Malgré la présence de cette backdoor, l’algorithme a passé avec succès les différents tests d’évaluation publics (statistiques, cryptologiques…) pour qualifier la sécurité d’un algorithme de chiffrement.

Mais, il convient de rester humble. Il s’agit d’une première étape. Plus tard, d’autres algorithmes devraient être publiés avec des backdoors de plus en plus complexes (à trouver s’entend). Nous travaillons dessus.

Quelles difficultés avez-vous rencontrées ?

À part les difficultés mathématiques inhérentes à ce type de recherche, aucune. Tout le monde semble se désintéresser de cette problématique. Plusieurs journaux internationaux ont reconnu la grande qualité de nos travaux (et leur complexité), mais ont toujours rejeté notre soumission, car ils jugeaient le sujet « borderline » (sic) sans trop savoir comment interpréter ce terme.

Ce projet a été présenté à FORmal Methods in Security Engineering (ForSE) 2017 à Porto. Le moyen d’exploiter cette porte dérobée sera présenté à Moscou lors de la conférence RusKrypto 2017. Pourquoi ces présentations ?

Cela rentre dans le cadre d’une part du processus de publication scientifique (évaluation par des pairs, partage de la connaissance). Maintenant si nous voulons alerter sur le danger d’utiliser des algorithmes fournis par d’autres, la publication reste le meilleur moyen.

Comme nous estimons que la backdoor est relativement simple à trouver, et surtout que nous avertissons que cet algorithme est inapproprié pour une utilisation réelle, il n’y a pas de contre-indication à publier et à en expliquer la méthode de cryptanalyse optimale. En revanche, plus tard, il n’est pas sûr que nous publions la partie cryptanalyse (mais nous passerons par des techniques de preuve de cryptanalyse a apport de connaissance nulle pour prouver la présence d’une backdoor exploitable).

Le choix de RusKrypto s’explique par le fait que la communauté russe est la seule qui semble s’intéresser a cette problématique, qu’elle est d’un très bon niveau mathématique et donc nous aurons des échanges scientifiques extrêmement riches et fructueux.

Comment vont réagir selon vous la NSA et d’autres agences ?

C’est à eux qu’il faudrait le demander, mais honnêtement peu me chaut. Il est clair que si l’on pouvait contribuer à ce que certains pays (dont le nôtre) s’interrogent sur le danger à utiliser des algorithmes fournis par d’autres puissances, cela serait déjà bien. Il y a des plaisirs difficiles à bouder.

À cette occasion, vous lancez un challenge ?

Oui, mais de manière plutôt informelle. L’algorithme est public depuis une semaine [3] et nous espérons que des chercheurs trouveront comment caractériser, voire exploiter la backdoor. Un prix symbolique est prévu. Le but est surtout d’avoir ce regard extérieur, mais également de contribuer à faire naître une communauté autour de cette problématique scientifique, opérationnelle et stratégique.

À propos des algorithmes, où en est Gostcrypt ? La Fédération russe a annoncé le projet d’une nouvelle norme GOST Grasshopper

Pour GostCrypt, nous avons décidé de prendre notre temps. Nous sommes en train de refondre complètement l’interface graphique (ce sera en Qt), nettoyer le code, ajouter des fonctionnalités et des innovations, documenter totalement le code source avec Doxygen, sécuriser le code… bref une grosse évolution qui, si tout va bien devrait sortir fin 2017. Le but étant immédiatement après de demander une certification CSPN (j’ai le financement). Je souhaite donc faire les choses sérieusement et avec le plus grand soin et conduire le développement actuel dans la perspective de ce CSPN…. bref une grosse évolution. Maintenant la version 1.3 de GostCrypt intègre le nouveau standard russe Grasshopper, mais sans la variabilité de clef utilisée pour la version antérieure. Cela fera partie de la prochaine version.

Je suis content que Veracrypt avance et se développe. Son auteur fait un super travail. Cela permet à GostCrypt de prendre son temps.

[1] http://www.huffingtonpost.com/2013/12/20/nsa-rsa-contract_n_4482227.html

[2] https://www.itnews.com.au/news/rsa-paid-10m-by-nsa-for-encryption-backdoor-368285

[3] https://arxiv.org/abs/1702.06475