La fragilité inattendue du chiffrement symétrique dans le monde postquantique

Une première version de cet article est parue dans la revue La Recherche, n°541, en novembre 2018.

Systèmes symétriques contre systèmes asymétriques : ces deux piliers de la cryptographie ne sont pas affectés de la même façon par l’arrivée de l’ordinateur quantique, qui devient plus tangible chaque jour. Résolvant certains problèmes bien plus rapidement qu’un ordinateur classique, un ordinateur quantique compromettrait la sécurité de la majeure partie de la cryptographie asymétrique — c’est-à-dire à clé publique. D’où la recherche de systèmes asymétriques de ce type, aiguillonnée par la compétition lancée par le NIST.

La cryptographie symétrique paraissait à première vue à l’abri de cette catastrophe annoncée. En effet, il y a quelques années seulement, on estimait que la seule menace sérieuse de l’informatique quantique contre la cryptographie symétrique était celle d’une attaque à l’aide de l’algorithme quantique de Grover, découvert en 1996. Et on pensait qu’on pouvait s’en prémunir facilement en doublant la taille des clés secrètes utilisées pour le chiffrement et le déchiffrement. Nous avons montré que les choses n’étaient pas si simples et que manipuler les messages avec un ordinateur quantique présentait un risque de sécurité.

En cryptographie symétrique, la même clé est utilisée pour le chiffrement et le déchiffrement — d’où son qualificatif de « symétrique ». L’avantage est la mise au point de systèmes efficaces : le standard ABS, standard symétrique recommandé depuis 2002, permet de chiffrer plusieurs gigaoctets par seconde sur un processeur récent, alors que les standards de cryptographie asymétrique atteignent moins d’un mégaoctet par seconde — une vitesse mille fois moins élevée. En pratique, on utilise souvent des systèmes hybrides, où la cryptographie asymétrique sert seulement à échanger une clé secrète, qui est ensuite utilisée avec un algorithme de chiffrement symétrique. La cryptographie symétrique sécurise nos communications au quotidien : la téléphonie mobile ou le Wi-Fi, les transactions sur le Web, les cartes de transport ou les clés de voiture électroniques.

Standards publics

Fondamentalement, dans un système symétrique, on essaie de construire des fonctions qui mélangent le message de façon pseudo-aléatoire. Comme on ne peut pas prouver mathématiquement la sécurité de ces fonctions, cette dernière repose sur la cryptanalyse : tous les standards sont publics et la communauté cryptographique cherche continuellement des faiblesses dans les systèmes utilisés. Dès lors que les cryptanalystes décèlent une propriété non aléatoire, ils peuvent s’en emparer pour aller plus loin et casser le système. C’est ainsi que, durant la Première Guerre mondiale, tirant profit de similarités dans les messages chiffrés par les Allemands, le Français Georges Painvin a pu décrypter une grande partie des messages. De même, le mathématicien polonais Marian Rejewski mit à profit le fait que certains mots étaient doublés dans le message pour comprendre le fonctionnement d’Enigma, la fameuse machine de codage symétrique utilisée durant la Seconde Guerre mondiale. Dès que l’on trouve une propriété non aléatoire — parfois des choses plus subtiles qu’une régularité —, on considère qu’un système est faible. Après plusieurs années de recherches, on aura une bonne confiance dans le système si les meilleures analyses connues ne mettent pas en danger sa sécurité.

Comment fonctionne un système de cryptographie symétrique ? Prenons l’exemple du chiffrement par blocs, où le message à transmettre est séparé en blocs de petite taille. Le message est d’abord découpé en blocs typiquement constitués de 128 bits (16 octets). L’idée naïve qui consiste à traiter chaque bloc indépendamment ne fonctionne pas car, dès que l’on se retrouve avec deux blocs égaux, les deux chiffrés (le produit de la transformation par le système cryptographique) seront également égaux. C’est ce que l’on appelle une « collision ». Les cryptographes élaborent donc un mode opératoire (voir dessin ci-dessous), qui est la manière dont les blocs sont traités pour gérer les messages plus longs que 128 bits. En résumé, un système cryptographique symétrique, c’est à la fois une série de transformations complexes sur un bloc (pour l’AES, chaque bloc est chiffré par quatre transformations répétées dix fois ; ces itérations sont ce que l’on appelle des « tours »), et un mode opératoire qui dit comment les blocs sont reconstruits.

Principe d’un mode opératoire. Le message M est découpé en blocs (m₁, …, m₄), et on procède au chiffrement (E) sur le bloc m₁, puis on ajoute le deuxième bloc m₂ et on recommence. Le message chiffré est la concaténation de c₁ c₂ c₃ c₄. Illustration © La Recherche

Puissance de calcul

Lorsqu’on ne connaît pas de faiblesse à un système, la meilleure attaque possible consiste à tester toutes les clés. Pour l’AES, on utilise typiquement des clés de 128 bits (la même longueur que celle des blocs), de sorte qu’il y a 2¹²⁸ clés possibles (environ 10³⁸). Même avec toute la capacité de calcul disponible sur Terre, tester toutes les clés de manière exhaustive prendrait plusieurs milliers de fois l’âge de l’Univers… L’AES paraît donc offrir une bonne confiance, ce qui n’est pas le cas des standards anciens. Le système de chiffrement DES (pour Data Encryption Standard), utilisé jusqu’au début des années 2000, utilise des clés de 56 bits ; il y a donc 2⁵⁶ clés possibles, soit quelques dizaines de billiards (7 x 10¹⁶ environ). Avec la puissance de calcul actuelle, une machine dédiée peut tester toutes les clés en moins d’une journée. À l’inverse, RC4, algorithme de chiffrement par flot utilisé pour les pages Web, a été cassé en raison de faiblesses dans la structure de l’algorithme, même si la clé est assez grande. En effet, le flux aléatoire généré par l’algorithme est légèrement biaisé en faveur de certaines séquences d’octets, ce qui peut être mis à profit dans des attaques en pratique.

Que peut faire l’ordinateur quantique contre les systèmes symétriques ? La menace la mieux connue est l’algorithme quantique de Grover. Ce dernier permet de rechercher parmi 2ⁿ clés, avec seulement 2^{n / 2} opérations. Avec cette accélération quadratique de la recherche exhaustive, pour retrouver une clé de 128 bits, un ordinateur quantique aurait besoin de seulement 2⁶⁴ opérations. Or un ordinateur classique est aujourd’hui capable de faire 2⁶⁴ opérations en un temps raisonnable (lire ci-dessous). Ce calcul serait aussi potentiellement réalisable avec un ordinateur quantique suffisamment gros et rapide. Des résultats récents montrent que la taille de bloc est aussi un paramètre sensible pour les attaques quantiques. En particulier, des algorithmes quantiques ont été proposés pour trouver des collisions plus rapidement qu’avec un ordinateur classique, ce qui peut être exploité pour attaquer certains modes opératoires. Plus précisément, un algorithme quantique peut trouver une collision sur 128 bits avec 2⁵¹ opérations, alors qu’un algorithme classique en nécessite 2⁶⁴. De surcroît, ce type d’algorithme permet de concevoir des versions « quantifiées » des attaques classiques qui exploitent des faiblesses dans les algorithmes cryptographiques.

Doubler la taille de clé

Toutefois, ces attaques quantiques ne sont pas inquiétantes en pratique, car on peut s’en protéger facilement : pour l’attaque de Grover, le nombre d’étapes double à chaque fois qu’on ajoute 2 bits à la clé. Ainsi, avec une clé de 256 bits de long, on retrouve une sécurité suffisante, puisque l’attaque de Grover requiert alors 2¹²⁸ opérations. De façon générale, on estime que l’on peut restaurer la sécurité contre les algorithmes quantiques en doublant la taille de clé et en augmentant la taille de bloc. C’est d’ailleurs l’une des forces d’AES, qui fonctionne aussi avec des clés de 256 bits — c’était l’un des critères pour la standardisation.

Une superposition quantique permet de travailler avec des bits quantiques (qubits) qui sont des « mélanges » de tous les états entre 0 et 1.  Illustration © La Recherche

Récemment, nous avons découvert des attaques quantiques qui nécessitent bien moins d’opérations. Elles supposent que l’attaquant peut chiffrer des messages avec des superpositions quantiques (voir dessin à droite ci-contre).

C’est une hypothèse forte, qui demande que l’ordinateur quantique soit utilisé non seulement par l’attaquant, mais aussi par l’utilisateur légitime du chiffrement. Dans ce cas, l’algorithme quantique de Simon permet de résoudre un problème de recherche très particulier avec seulement n opérations, alors qu’un algorithme classique pour le même problème demande 2ⁿ¹² opérations.

Avec notre collègue Anthony Leverrier, d’Inria Paris, et Marc Kaplan, de Télécom ParisTech, nous avons montré que l’on peut utiliser cet algorithme pour attaquer des modes opératoires ou pour accélérer certains types d’attaques, comme les attaques par glissement — une attaque où l’on s’arrange pour que le bloc d’entrée d’un tour corresponde au bloc d’entrée d’un autre tour. Avec une taille de bloc de 128 bits, ces attaques demandent seulement 128 opérations sur des messages en superposition quantique, alors qu’il faudrait 2⁶⁴ messages dans le cas classique. Ainsi, certains systèmes de cryptographie symétrique n’offrent aucune sécurité si l’on autorise des messages en superposition quantique. Ces attaques ne présentent pas de danger immédiat, mais permettent de mieux cerner l’impact potentiel de l’ordinateur quantique.