Informatique quantique et cassage de clefs

J’ai eu la chance de pouvoir assister vendredi dernier à l’ISC, à une présentation sur l’état actuel de l’informatique quantique « dans la vraie vie ». Renaud Lifchitz, chercheur en sécurité chez Oppidia, avait eu la bonne idée de refaire, mais cette fois ci en français, la présentation qu’il avait déjà faite à la NoSuchCon. Et a mon avis, pour pouvoir comprendre un peu de quoi on parle, avoir les explications (et pouvoir poser des questions etc) en français, ça change tout :p

 

 

Vous trouverez la vidéo faite à la NSC ainsi que les slides ici. (Slides sont aussi disponibles sur slidehsare).

Et donc on en est ou ?

Les ordinateurs quantiques dans le monde existent mais se comptent sur les doigts d’une main. Google en a un, qu’il partage avec la NSA. Et il y a peu être une ou deux universités équipées. Et encore, il faut distinguer deux types d’ordinateurs quantiques. Les « vrais » et les faux.

Les vrais permettent vraiment d’implémenter n’importe quel algorithme quantique alors que les « faux » ne sont conçus que pour résoudre un type de problèmes bien particulier (recherche d’une fonction optimale ou des meilleurs solutions ou quelque chose comme ça…). Les « vrais » ordinateurs travailleraient sur 20 a 30 qbits au maximum. Mais, et la c’est intéressant, ils évoluent à peu près à la même vitesse (loi de Moore) que les ordinateurs traditionnels. En partant de cette hypothèse (qui pour le moment se vérifie donc), le chiffrement symétrique sera « menacé » dans 10 ou 15 ans. Le chiffrement asymétrique dans 25 ou 30.

MAIS, il y a un gros MAIS. Pour le chiffrement symétrique, on a déjà mathématiquement prouvé que le meilleur algorithme quantique de recherche (en racine de N) avait déjà été trouvé. Du coup, il suffira de doubler la taille de la clef (passer de l’AES 128 à de l’AES 256) et plus de problèmes. En revanche, pour le chiffrement asymétrique, qui repose sur des problèmes mathématiques comme la factorisation de grand nombre ou le logarithme discret, la le système sera complètement cassé. Augmenter la taille de la clef ne devrait pas changer grand chose. Donc, il y a vraiment un gros soucis, et des personnes essayent actuellement de trouver de nouveaux algorithmes de chiffrement qui seront capables de résister à l’informatique quantique.

Rappels sur le chiffrement symétrique/asymétrique

Le chiffrement symétrique et celui qui est utilisé pour chiffrer les communications, les disques durs etc. On « transforme » simplement la donnée pour la rendre incompréhensible, mais cette transformation est réversible si on connaît la bonne clef. Le chiffrement asymétrique, très consommateur en calcul, n’est utilisé que pour chiffrer de toute petite quantité de données. C’est le principe des signatures électronique. Surtout, il est utilisé pour réaliser les échanges de clef. Quand vous cous connectez sur un site en https, la première étape consiste à « négocier » une clef entre les deux machines. La on utilise du chiffrement asymétrique. Une fois que les deux machines se sont mises d’accord sur une clef, cette dernière est utilisée pour chiffrer symétriquement le reste de la communication. Autrement dit, et même si il existe des cas ou on fait juste du chiffrement symétrique (par exemple quand vous chiffrez votre disque dur avec un mot de passe), la plupart du temps on utilise une combinaison des deux techniques de chiffrement.

Pour le fun, la crypto c’est un peu le sujet de la majorité de mes cours actuellement. Mon dernier TP, à été de réaliser l’une des attaques décrite dans ce document. (Cryptanalyse différentielle d’un blockcipher… Le titre en jette non ?

Conclusion

Les jours de RSA sont comptés. Et les chercheurs ont 20 ou 30 ans pour trouver autre chose. Au boulot !

2 commentaires

  1. Fnux Répondre

    Salut Hoper,

    Si la crypto t’intéresse vraiment, je te passe le lien ci-dessous :

    wget http://www.as2.com/crypto/challenge.tar.bz2

    En le décompressant (tar -xjf challenge.tar.bz2) tu obtiendras deux fichiers :

    Le texte en clair : plain.txt (The Art Of War – Sun Tzu (544 BC) – ASCII US).
    Le fichier crypté : cypher.bin

    Le challenge consiste à trouver un paragraphe secret introduit dans le fichier plain.txt avant son cryptage (et donc bien évidemment non présent dans le fichier plain.txt).

    C’est, d’après les « experts » à priori d’autant plus simple et facile à casser que le fichier en clair est très long, ce qui donne justement de très grandes chances aux « analystes » de trouver où est placé ce paragraphe secret, et bien sur de lire son contenu.

    Et pour être encore plus sympatique, on précise même que le cryptage a été réalisé avec la bonne vieille (et cassée depuis longtemps) méthode RC4.

    Cependant, et c’est là que réside le chalenge, une technologie développée depuis 1997 a été appliquée par l’utilisation d’un filtre qui retire les clefs et les fuites en texte clair du fichier cypher.bin.

    Cette techno existe en fait depuis plus de 50 ans, puisque c’est ce qui était utilisé pendant la guerre froide pour protéger la ligne rouge entre Washington et Moscou, mais n’a jusqu’à ce jour jamais pu être implémentée pour être utilisée sans les bandes alors nécessaires au filtre servant au décryptage sauf par la méthode utilisée ici.

    Depuis que ce challenge existe (1997), personne n’a jamais réussi à trouver où était placé le paragraphe secret, et donc n’a jamais réussi non plus à le déchiffrer.

    Une prime de 1.000,00 Euros est promise par l’auteur de cette technologie qu’il annonce comme mathématiquement prouvée inviolable au premier qui trouvera la solution.

    Si c’est bien ton domaine d’études, alors tente le coup, même avec tes amis et même aussi tes profs.

    Mais pour info, en France, tant l’ANSSI que la DRM se sont cassé les dents dessus.

    Au fait, veux-tu que je refasse une traduction en anglais de ton dernier Kclean ?

    Bonne et heureuse année 2016.

    Cordialement.
    Fnux.

  2. hoper Répondre

    Salut fnux, et merci pour ces liens 🙂

    La crypto faisait bien parti de mes domaines d’études, mais ce n’est ni mon point fort, ni un sujet qui m’intéresse particulièrement. Au contraire, trop de maths :p
    Si je dois me spécialiser dans un domaine à l’avenir, ce sera plutôt celui de l’analyse forensic.

    Pour kclean, n’hesite pas.
    Les modifications effectuées depuis la dernière version sont vraiment mineurs, je pense qu’en fait il n’y a rien à traduire… J’aurai du mettre à jour la version anglaise dans la foulée, méa culpa.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.