A.1 Cryptographie symétrique

Les mécanismes cryptographiques symétriques se caractérisent par le fait qu’ils utilisent des clés secrètes partagées par plusieurs entités, généralement deux. La sécurité d’un mécanisme symétrique repose notamment sur la connaissance exclusive de ces secrets par les entités légitimes.

Une clé secrète est généralement une suite aléatoire de bits, c’est-à-dire de 0 et de 1, de taille fixée. Cette taille de clé, notée $k$ , est déterminante pour la sécurité du système car il existe exactement $2^{k}$ valeurs de clé différentes de longueur $k$ . Les cryptosystèmes symétriques sont en général susceptibles d’être attaqués de manière générique au moyen d’une énumération de toutes les clés possibles. Une telle attaque, dite par « recherche exhaustive », ne peut cependant aboutir que si le nombre de calculs est réalisable par des moyens informatiques raisonnables. Les cryptosystèmes symétriques robustes utilisent donc une taille de clé $k$ telle que $2^{k}$ opérations soient impossibles à effectuer en un temps raisonnable.

Afin de fixer les idées sur les ordres de grandeur manipulés et sur les capacités de calcul disponibles de nos jours, quelques exemples numériques concrets sont rassemblés dans la table 2.

Ces chiffres montrent que la fonction $2^{k}$ croît extrêmement rapidement avec $k$ et que la capacité de réaliser de l’ordre de $2^{128}$ opérations de calcul en temps raisonnable semble très peu plausible de nos jours, même en disposant de moyens très importants. En outre, il apparaît en tout état de cause qu’effectuer $2^{256}$ calculs est, et restera, parfaitement hors de portée. Ce constat permet d’écarter toute menace de recherche exhaustive sur des systèmes bien dimensionnés et forme la base de toute sécurité en cryptographie. Ceci va en particulier à l’encontre de l’idée reçue selon laquelle tout mécanisme peut nécessairement être cassé par recherche exhaustive, à condition d’y mettre les moyens.

Table 2 – Ordre de grandeur de la valeur de $2^{k}$ pour le calcul

$2^{k}$	Ordre de grandeur
$2^{15}$	Opérations élémentaires nécessaires pour l’implémentation d’une primitive symétrique.
$2^{32}$	Opérations par seconde par cœur de processeur 4 GHz.
$2^{46}$	Opérations effectuables par seconde sur processeur graphique (GPU).
$2^{57}$	Opérations par an par cœur de processeur.
$2^{60}$	Opérations par seconde effectuables par les meilleurs supercalculateurs connus.
$2^{70}$	Empreintes SHA-256 calculées chaque seconde dans le monde pour pour la blockchain Bitcoin.
$2^{71}$	Opérations effectuables par an sur GPU.
$2^{76}$	Opérations par jour effectuables par les meilleurs supercalculateurs connus.
$2^{91}$	Opérations effectuables en un siècle par les meilleurs supercalculateurs connus.
$2^{96}$	Empreintes SHA-256 calculées pour la blockchain Bitcoin entre sa création en 2009 et 2025.
$2^{119}$	Opérations effectuables en 13.8 milliards d’années par les meilleurs supercalculateurs connus.
$2^{128}$	Opérations effectuables en 13.8 milliards d’années par l’ensemble des processeurs mondiaux.
$2^{256}$	Électrons dans l’univers.

A.1.1 Chiffrement symétrique

Les mécanismes de cryptographie symétrique les plus connus sont les algorithmes de chiffrement¹. Ceux-ci garantissent la confidentialité des données échangées entre deux possesseurs d’une clé secrète, même si le canal de communication employé est écouté. Le chiffrement symétrique permet également de sécuriser le stockage statique d’informations, sans intention de les transmettre.

Les problèmes majeurs que sont la génération et l’éventuel échange initial de la clé secrète entre les correspondants doivent être traités en complément du chiffrement.

De plus, l’intégrité de la donnée n’est pas garantie par le chiffrement donc rien ne permet d’exclure des possibilités d’attaques actives visant à modifier les informations transmises ou stockées. On peut ainsi concevoir des scénarios d’attaques au cours desquels un attaquant peut modifier des communications chiffrées et impacter le clair correspondant sans être détecté. Un exemple de cette attaque est détaillé en annexe A.1.2.

Les méthodes de chiffrement symétrique ou à clé secrète se divisent naturellement en deux familles, le chiffrement par bloc (« block cipher ») et le chiffrement par flot (« stream cipher »), décrites ci-dessous.

A.1.1.1 Chiffrement par bloc

Un mécanisme de chiffrement par bloc est la combinaison d’une primitive de chiffrement par bloc et d’un mode opératoire de chiffrement. Il permet de traiter les données à chiffrer, de taille quelconque, par blocs de taille fixe. On notera $n$ le nombre de bits de ces blocs de données ; typiquement, cette taille vaut 128 bits en pratique.

Une primitive de chiffrement par bloc $E$ est une fonction déterministe qui prend en entrée un bloc $m$ de $n$ bits et une clé $K$ de $k$ bits et renvoie un bloc $c = E_{K} (m)$ de $n$ bits. À clé $K$ fixée, la fonction $E_{K}$ est une permutation facilement inversible. Selon le contexte, le terme chiffrement par bloc peut désigner le mécanisme de chiffrement par bloc visant à assurer la confidentialité d’une donnée de taille arbitraire ou la primitive sous-jacente.²

L’un des exemples les plus connus de primitives de chiffrement par bloc est l’AES (Advanced Encryption Standard), sélectionné par le NIST au terme d’une compétition internationale lancée en 1997. L’AES est conçu pour traiter des blocs de 128 bits au moyen de clés de 128, 192 ou 256 bits ce qui le met hors de portée des attaques génériques.

Une primitive de chiffrement par bloc seule, ne prenant en entrée qu’un bloc de $n$ bits, ne suffit pas à définir un mécanisme de chiffrement par bloc. En effet, un mode opératoire est nécessaire pour préciser la manière dont est instrumentée la primitive de chiffrement par bloc sous-jacente pour traiter un message de taille arbitraire. La taille du message n’étant pas toujours un multiple de la taille de bloc $n$ , il convient d’utiliser une méthode de bourrage (plus communément appelé padding en anglais) pour remplir le dernier bloc de message.

Un padding usuel consiste à ajouter en suffixe du message un bit valant 1 et autant de 0 que nécessaire afin d’obtenir un nombre total de bits multiple de la taille du bloc.

Par ailleurs, afin de pallier le caractère fondamentalement déterministe de la primitive de chiffrement par bloc, il est possible et recommandé d’employer un mode opératoire probabiliste utilisant un vecteur d’initialisation (IV, pour « Initialisation Vector ») public et différent à chaque chiffrement. Cela empêche un attaquant de détecter une répétition du message en observant les chiffrés. Ce vecteur d’initialisation est généré aléatoirement ou de manière déterministiquement contrôlée lors du chiffrement et est transmis avec le chiffré pour permettre le déchiffrement.

Les deux modes opératoires de chiffrement les plus utilisés sont le mode compteur noté CTR et le mode chaîné noté CBC pour « cipher-block chaining » en anglais. Notons $m_{1}$ , $m_{2}$ , …, $m_{t}$ les $t$ blocs de message clair obtenus après padding, IV le vecteur d’initialisation et $c_{0}$ , $c_{1}$ , $c_{2}$ , …, $c_{t}$ les blocs de chiffrés où par convention $c_{0} = IV$ .

Pour CTR, le chiffré est obtenu en calculant $c_{i} = E_{K} (IV + i -1) \oplus m_{i}$ pour $i$ allant de 1 à $t$ , comme représenté figure 3. Le déchiffrement se fait de manière similaire : $m_{i} = E_{K} (IV + i -1) \oplus c_{i}$ pour $i$ allant de 1 à $t$ , avec $IV = c_{0}$ .

Figure 3 - Mode opératoire CTR.

Pour CBC, le chiffré est obtenu en calculant séquentiellement $c_{i} = E_{K} (c_{i} -1 \oplus m_{i})$ pour $i$ allant de 1 à $t$ , comme représenté figure 4. Le déchiffrement se fait en calcule $m_{i} = c_{i} -1 \oplus E_{K}^{- 1} (c_{i})$ pour $i$ allant de 1 à $t$ .

Figure 4 - Mode opératoire CBC.

Pour le mode CBC, la réutilisation de l’IV implique que les chiffrés de deux messages dont les $k$ premiers blocs sont identiques auront les mêmes $k$ premiers blocs de chiffré (en omettant $c_{0}$ qui représente l’IV), ce qui est détectable par l’attaquant. L’IV doit être aléatoire pour ne pas induire de fuite d’information. Pour le mode CTR, les valeurs des compteurs $IV + i$ pour $i$ allant de 0 à $t -1$ ne doivent pas être répétées pour des messages différents. Dans le cas contraire, cela induirait une répétition de la suite chiffrante, donc une perte de la confidentialité des données. Pour s’assurer de cela, on peut par exemple limiter les tailles de message d’entrée à maximum $2^{32} -1$ blocs et générer déterministiquement des vecteurs d’initialisation toujours différents dont les 32 bits de poids faible sont nuls.

Les modes opératoires de chiffrement disposent généralement d’une preuve de sécurité qui réduit la sécurité du mode à la sécurité de la primitive de chiffrement par bloc sous-jacente. Cette preuve de sécurité exige que certaines hypothèses, par exemple sur l’IV, soient satisfaites et donne une borne de sécurité, à savoir une estimation du nombre maximal d’appel à la primitive $E_{K}$ avant qu’une fuite d’information se produise. Les modes CTR et CBC sont ainsi prouvés jusqu’à la borne des anniversaires sous l’hypothèse de la génération aléatoire de l’IV pour CBC et de la non-répétition du compteur pour CTR. Les preuves de modes opératoires de chiffrement considèrent un attaquant passif (attaquant CPA). L’annexe A.1.3 présente brièvement les modèles de sécurité les plus utilisés en cryptographie symétrique.

A.1.1.2 Chiffrement par flot

Les mécanismes de chiffrement par flot utilisent une approche différente du chiffrement par bloc dans le sens où elles considèrent généralement le message à chiffrer comme une suite de bits combinés de manière simple (généralement un « ou-exclusif bit à bit ») avec une séquence de bits dérivée de la clé secrète (et dans la plupart des cas également d’un vecteur d’initialisation).

Les algorithmes de chiffrement par flot s’inspirent du chiffrement de Vernam, ou one-time-pad, qui est à la fois très simple, très sûr et inutilisable en pratique. Si l’on considère un message représenté sous la forme d’une suite de bits $m_{1}$ , $m_{2}$ , $m_{3}$ , … ainsi qu’une clé également vue comme une suite de bits $k_{1}$ , $k_{2}$ , $k_{3}$ , …, le chiffré du message est alors obtenu au moyen de l’opération de « ou-exclusif bit à bit », ou XOR : ci = $m_{i} \oplus k_{i}$ . Afin de déchiffrer, il suffit d’appliquer la même opération de XOR du chiffré avec la clé secrète car $c_{i} \oplus k_{i} = m_{i}$ .

Le one-time-pad est parfaitement sûr, en terme de confidentialité, si la clé est au moins de même taille que le message à chiffrer et n’est utilisée qu’une seule fois. Ceci restreint considérablement les applications envisageables à cause de la taille de la clé à partager entre émetteur et destinataire ; dans la plupart des cas, cette mise en accord de clé secrète pose un problème similaire à la transmission sécurisée du message lui-même.

L’idée générale du chiffrement par flot est d’utiliser des clés de petite taille, typiquement de l’ordre de 128 bits, et d’en dériver de manière déterministe une suite chiffrante d’allure aléatoire de même longueur que le message. Cette suite chiffrante est ensuite additionnée bit à bit avec le message pour produire le chiffré, similairement au one-time-pad. Le déchiffrement agit de la même manière, en générant la même suite chiffrante à partir de la clé secrète.

La réutilisation d’une même suite chiffrante pour deux messages différents implique une perte immédiate de confidentialité. En effet, le XOR des deux chiffrés serait alors égal au XOR des deux messages clairs. Pour pallier ce problème, l’introduction d’un vecteur d’initialisation différent à chaque chiffrement est indispensable. Ce vecteur d’initialisation est produit, aléatoirement ou déterministiquement à l’aide d’un compteur, lors du chiffrement et est transmis avec le chiffré.

Certains chiffrements par flot peuvent être construits à partir de primitives de chiffrement par bloc. Le mode CTR (Counter) et le mode OFB (Output Feedback) en sont deux exemples caractéristiques. Lorsqu’ils sont instanciés avec une primitive de chiffrement par bloc, ils peuvent être considérés à la fois comme des mécanismes de chiffrement par bloc et par flot.

A.1.2 Intégrité cryptographique

Les chiffrements vus dans les sections précédentes ne fournissent que la propriété de confidentialité des données. Cela n’empêche pas un attaquant d’altérer les données chiffrées et d’induire ainsi une modification du clair sans être détecté. Des mécanismes cryptographiques complémentaires sont donc nécessaires pour garantir la détection d’une telle altération. Ces mécanismes fournissent la propriété d’intégrité de la donnée et peuvent être utilisés indépendamment de l’emploi d’un chiffrement.

Pour illustrer la nécessité de l’intégrité en complément du chiffrement, nous prenons l’exemple de données chiffrées avec un chiffrement par flot. Si un attaquant désire inverser un bit de message clair, il lui suffit d’inverser le bit de chiffré correspondant, et ce sans connaître la suite chiffrante. À titre d’exemple, imaginons le chiffrement du montant d’une transaction financière ; le positionnement du montant à payer dans le message se situe en général à une position fixe et connue. L’attaquant peut alors inverser un bit de cette somme et ainsi transformer un faible montant en une somme très importante, comme si l’on transformait, en notation décimale, 0000017 euros en 1000017 euros.

Plus précisément, la principale technique permettant d’assurer l’intégrité des données consiste à calculer un code d’authentification de message (appelé MAC pour « Message Authentication Code »³), aussi appelé motif d’intégrité, à partir des données dont on veut garantir l’intégrité et d’une clé secrète symétrique. Ce motif d’intégrité est ensuite concaténé à la donnée transmise. Le récepteur calcule de son côté le MAC de la donnée reçue à l’aide de la clé symétrique et le compare au MAC reçu. L’égalité de ces MAC garantit l’intégrité de la donnée puisqu’un attaquant, ignorant la clé symétrique, est incapable de produire un MAC valide de la donnée altérée. Pour cela, il est nécessaire que le MAC soit de longueur suffisante, typiquement d’au moins 96 bits.

Un MAC peut être construit à partir d’un mode opératoire d’intégrité reposant sur la sécurité d’une primitive de chiffrement par bloc sous-jacente, et éventuellement à partir d’un problème mathématique théorique, par exemple une évaluation polynomiale dans un corps fini.

Un exemple de MAC est le mode CBC-MAC surchiffré. Le MAC est alors calculé en appliquant le mode de chiffrement CBC (décrit figure 4) au message, sans utiliser de vecteur d’initialisation (IV), et en ne conservant comme valeur de MAC que le dernier bloc de chiffré, surchiffré avec une clé $K'$ , différente de celle utilisée dans la chaîne CBC. Graphiquement, on obtient la représentation symbolique de la figure 5. Toute modification, même minime, du message à protéger engendre un résultat totalement différent du MAC.

Figure 5 - Mode opératoire CBC-MAC surchiffré

Un autre MAC très utilisé est GMAC (Galois MAC) opérant sur des corps finis de grande taille (128 bits). GMAC interprète le message comme un polynôme et l’évalue en la clé, puis chiffre ce résultat à l’aide d’une primitive de chiffrement par bloc pour obtenir le motif d’intégrité. Il est prouvé que la sécurité de GMAC repose sur la robustesse de la primitive de chiffrement par bloc.

Notons enfin qu’un MAC valide ne permet que de garantir l’intégrité d’un message. Si l’on souhaite assurer l’intégrité d’un ensemble de messages formant une communication, il convient de prendre en compte des mesures contre le rejeu ou la suppression de certains messages accompagnés de MAC valides.

L’utilisation conjointe d’un algorithme de chiffrement et d’un mécanisme ’intégrité est appelée chiffrement intègre ou plus communément chiffrement authentifié, depuis l’anglais Authenticated Encryption. Pour ce faire, il est possible d’utiliser deux mécanismes indépendants ou un seul mécanisme intégrant les deux propriétés de sécurité. Dans ce second cas, les mécanismes utilisés sont souvent basés sur un mode opératoire de chiffrement authentifié instancié avec une primitive de chiffrement par bloc.

Les mécanismes de chiffrement authentifié les plus utilisés sont AES-GCM (AES-Galois Counter Mode) et AES-CCM (AES-Counter with CBC-MAC), standardisés par le NIST.

A.1.3 Modèles de sécurité

Les mécanismes cryptographiques sont souvent complexes et leur sécurité est difficile à appréhender a priori. Les propriétés de confidentialité et d’intégrité sont générales et recouvrent un éventail nuancé de notions de sécurité dépendantes des capacités estimées de l’attaquant. La cryptographie moderne formalise ces notions à travers différents modèles de sécurité définissant la portée d’une attaque et les capacités de l’attaquant considéré. Il devient alors possible de prouver la sécurité des mécanismes dans un certain modèle à partir de certaines propriétés, plus simples, des primitives cryptographiques sous-jacentes. Il convient néanmoins de vérifier la pertinence du modèle de sécurité avec le contexte envisagé.

Une propriété naturellement attendue d’un algorithme de chiffrement est que le chiffré ne donne aucune information sur le clair à un attaquant qui ne dispose pas de la clé secrète. Néanmoins, la taille du clair est une information particulièrement complexe à protéger tout en gardant une efficacité pratique. La plupart des modèles de sécurité accepte donc que l’attaquant puisse déduire la taille du clair à partir de celle du chiffré.

Un modèle de sécurité est défini par un problème de décision et un oracle auquel a accès l’attaquant. Le problème de décision le plus commun est le problème d’indistinguabilité (IND) défini comme suit. L’attaquant propose deux messages différents $M_{0}$ et $M_{1}$ de son choix (de même taille) et obtient le chiffré $C$ de l’un des deux. Il doit alors déterminer lequel des deux messages a été chiffré avec probabilité significativement supérieure à $1/2$ . S’il n’en est pas capable, cela indique que la vue d’un chiffré ne contient pas d’information exploitable sur le clair associé.

L’oracle définit formellement la capacité de l’attaquant en lui octroyant la capacité de chiffrer et déchiffrer des messages avec plus ou moins de liberté. Par exemple, dans le modèle IND-CPA, l’oracle CPA autorise uniquement à l’attaquant de chiffrer un ensemble de messages de son choix. Certaines variantes de cet oracle autorisent le chiffrement de messages qui peuvent dépendre de précédentes réponses de l’oracle, on parle alors d’oracle adaptatif. Le modèle IND-CCA définit quant à lui un oracle qui permet aussi de déchiffrer des données (différentes de C). Le modèle utilisant sa version adaptative, IND-CCA2, est considéré comme offrant le niveau de sécurité le plus élevé parmi les chiffrements. Certains modèles de sécurité permettent aussi de formaliser les propriétés de sécurité liées à l’intégrité (par exemple INT-CTXT), ce qui permet de formaliser la sécurité de chiffrements authentifiés.

Une propriété des chiffrements déterministes (par exemple des modes opératoires de chiffrement sans IV) est que deux chiffrements du même message génèrent des chiffrés identiques, dévoilant potentiellement de l’information à l’attaquant. Dans le modèle IND-CPA, l’attaquant peut demander à l’oracle le chiffré de $M_{0}$ ou $M_{1}$ , et vérifier lequel des deux est égal à $C$ , répondant ainsi correctement au problème décisionnel de l’indistinguabilité. Ainsi, un tel chiffrement déterministe ne peut pas être prouvé dans le modèle IND-CPA, et nécessite un autre modèle plus faible, apportant une sécurité moindre.

Les modèles de sécurité utilisés en cryptographie moderne les plus conservateurs, tels que IND-CCA2 ou des conjonctions de modèles de confidentialité et d’intégrité, permettent de capturer l’ensemble des moyens d’attaquants quelque soit le contexte d’utilisation des mécanismes cryptographiques. Évaluer la sécurité de mécanismes dans de tels modèles permet de minimiser les risques de faille de sécurité lors de leur emplois au sein de constructions plus complexes et plus généralement de s’assurer qu’aucune attaque liée à la conception de ce mécanisme n’existe. Enfin, la cryptographie moderne propose des mécanismes cryptographiques permettant d’atteindre de tels niveaux de sécurité sans réduire fortement les performances ; il serait par conséquent dommage de se priver de l’emploi de ces mécanismes.

A.1.4 Fonctions de hachages et fonctions à sortie extensible

Certaines primitives cryptographiques ne sont pas paramétrées par des clés. Ces primitives sont néanmoins souvent classées parmi les primitives symétriques dans la mesure où leurs caractéristiques principales empruntent beaucoup aux primitives à clé secrète.

La plus importante de ces primitives est la fonction de hachage dont le but est de transformer, de manière déterministe, une suite de bits de longueur quelconque, en une empreinte, ou haché, de taille fixe. Une fonction de hachage cryptographique doit être non inversible, c’est-à-dire qu’il ne soit pas possible étant donné une empreinte de trouver un message dont l’image par la fonction de hachage est égale à celle-ci : on dit que la fonction de hachage est résistante aux préimages. En outre, on demande souvent qu’il ne soit pas possible de trouver deux messages distincts ayant une même empreinte. On parle alors de résistance aux collisions.

Il est à noter qu’une fonction de hachage étant une fonction d’un ensemble de taille potentiellement infinie vers un ensemble de taille finie, il existe une infinité de telles collisions. On demande cependant qu’il ne soit pas possible de calculer pratiquement, en temps raisonnable, une telle collision.

L’attaque générique pour trouver des collisions exploite le paradoxe des anniversaires : si l’on note $n$ le nombre de bits de l’empreinte, pour trouver une collision, il suffit de calculer de l’ordre de $2^{n /2}$ hachés de messages aléatoires avant que deux de ces messages ne fournissent la même empreinte. Les fonctions de hachage sont essentiellement dimensionnées en prenant en compte cette attaque générique.

Il existe d’autres propriétés de sécurité des fonctions de hachage. Par exemple, à partir d’un message et de son empreinte, il doit être impossible de trouver en pratique un autre message qui donne la même empreinte : on parle alors de résistante aux secondes préimages. De telles propriétés découlent souvent de la résistance aux préimages ou de la résistance aux collisions.

Une des nombreuses applications des fonctions de hachage apparaît dans les mécanismes de signature numérique afin de réduire le message de longueur quelconque à une simple empreinte de petite taille fixée. Elles sont également utilisées comme primitive de base dans certains MAC (par exemple HMAC).

On appelle fonction à sortie extensible ou XOF (de l’anglais « eXtendable Output Function ») une fonction sans clé $XH$ qui à un message binaire $M$ de taille arbitraire et à un entier $ℓ \geq 0$ associe une empreinte $XH (M, ℓ)$ de longueur $ℓ$ bits. Lorsque $ℓ < ℓ^{'}$ , $XH (M, ℓ)$ doit être égal pour tout $M$ au préfixe de $XH (M, ℓ^{'})$ constitué de ses $ℓ$ premiers bits.

Généralement, une XOF est définie à niveau de sécurité fixé $λ$ . Définir des propriétés de sécurité exhaustives et précises de XOF est une tâche ardue, mais il est tout de même possible de définir certaines propriétés requises par les XOF. Pour tout intervalle d’entiers de taille $λ$ , la XOF restreinte aux bits de sortie à position dans cet intervalle doit se comporter comme une fonction de hachage avec taille de sortie $λ$ pour laquelle il n’existe pas de meilleure attaque que les attaques génériques. De plus, à message inconnu d’entropie suffisamment grande, la XOF se comporte comme un mécanisme de chiffrement par flot instancié avec une clé de taille suffisamment grande. Cela revient à dire que la sortie de la XOF doit ressembler à une séquence aléatoire et ne doit posséder aucune structure exploitable.

Le seul terme admis en français est celui de chiffrement ; les termes « cryptage » et « chiffrage » sont incorrects. L’opération inverse du chiffrement est le déchiffrement. ↩
La primitive de chiffrement par bloc est une brique élémentaire pouvant être utilisée dans d’autres constructions cryptographiques, comme des fonctions de hachage ou des MAC. ↩
Le terme MAC peut faire référence à l’algorithme permettant de calculer le motif d’intégrité et au motif d’intégrité lui-même. ↩

Keyboard shortcuts