Échange de clé

Avant la découverte de la cryptographie à clé publique, aucune méthode mathématique n'était connue pour effectuer l'échange de clé, qui reposait intégralement sur une sécurité opérationnelle : la clé devait être communiquée via un canal déjà sécurisé. Pour le téléphone rouge, qui utilisait un chiffrement par masque jetable, cela impliquait le transport physique de valises diplomatiques contenant les clés (sous forme de cartes perforées) des États-Unis à la Russie, et réciproquement.

Mais le cas le plus connu est certainement celui de la machine Enigma, utilisée pendant la Seconde Guerre mondiale par les forces de l'Axe pour chiffrer les communications radio. Les clés de chiffrement, qui correspondent pour Enigma aux paramètres de branchement et au choix des rotors, étaient changés quotidiennement par l'armée allemande. Avant même la guerre, en 1932, l'espion français Hans-Thilo Schmidt parvient à obtenir les clés des mois de septembre et d'octobre de la même année. C'est notamment avec ces informations que l'équipe polonaise de Marian Rejewski est parvenue à développer une méthode de déchiffrement, automatisée dès 1938. La clé étant changée uniquement une fois par jour, tous les messages interceptés dans une même journée étaient cassés simultanément. C'est en raffinant le travail de Rejewski, et en s'appuyant sur d'autres erreurs opérationnelles des forces allemandes, qu'Alan Turing parviendra à organiser le déchiffrement des communications d'Enigma.

Le premier mécanisme d'échange de clé est du à Ralph Merkle, qui l'a décrit en 1974^[2] et publié en 1976^[3]. L'idée est de proposer une liste publique de problèmes, les « puzzles », qui nécessitent un certain effort à résoudre, et qui révèlent deux secrets une fois résolus. Pour établir une clé, on choisit au hasard l'un de ces puzzle que l'on résout. Le premier secret est transmis au propriétaire des puzzles et le renseigne sur quel puzzle on a résolu, et le second secret sert de clé cryptographique.

Un adversaire écoutant la conversation ne sait pas, a priori, quel puzzle a été sélectionné. Pour retrouver la clé choisie par les deux participants, l'adversaire doit dans le pire des cas résoudre tous les puzzles proposés. Il fait donc face à un problème de complexité quadratique.

Dans le modèle de l'oracle aléatoire, on peut montrer que la sécurité de ce protocole est effectivement quadratique en le nombre de puzzles. Cette complexité n'est pas considérée suffisante en cryptographie moderne, mais un résultat de Boaz Barak et Mohammad Mahmoody-Ghidary montre qu'il n'est pas possible de faire mieux dans ce modèle^[4].

En 1976, s'appuyant sur la construction de Merkle, Whitfield Diffie et Martin Hellman proposent d'utiliser le problème du logarithme discret dans un corps fini, un problème calculatoire considéré difficile, comme base pour construire un protocole d'échange de clé.

Le principe de fonctionnement est le suivant : pour établir une clé, Alice et Bob choisissent en secret un entier ${\displaystyle x_{A}}$ et ${\displaystyle x_{B}}$ respectivement. Alice calcule ${\displaystyle y_{A}=g^{x_{A}}}$ et Bob calcule ${\displaystyle y_{B}=g^{x_{B}}}$ , où ${\displaystyle g}$ est un générateur d'un sous-groupe assez large, négocié à l'avance. Alice envoie ${\displaystyle y_{A}}$ à Bob, et Bob envoie ${\displaystyle y_{B}}$ à Alice. Finalement, Alice calcule ${\displaystyle y_{B}^{x_{A}}}$ et Bob calcule ${\displaystyle y_{A}^{x_{B}}}$ ; ces deux quantités sont en fait égales comme le montre un calcul rapide.

Un adversaire écoutant la conversation fait face au problème suivant : étant donné ${\displaystyle g,g^{x_{A}},g^{x_{B}}}$, calculer ${\displaystyle g^{x_{A}x_{B}}}$. Ce problème est appelé problème calculatoire de Diffie-Hellman. En 2018, la meilleure méthode connue pour l'attaquer consiste à calculer des logarithmes discrets.

La résolution du logarithme discret dans un groupe générique d'ordre premier ${\displaystyle p}$ requiert un effort ${\displaystyle O({\sqrt {p}})}$, c'est-à-dire que l'adversaire fait face à un problème exponentiellement plus difficile que les utilisateurs du protocole. Dans les sous-groupes multiplicatifs des corps finis, utilisés initialement par Diffie et Hellman, il existe en fait des algorithmes plus efficaces, notamment des variantes du crible du corps de nombre généralisé. En 1984, Neal Koblitz et Victor S. Miller proposent d'utiliser plutôt le groupe des points rationnels d'une courbe elliptique. Pour des courbes bien choisies, aucune attaque classique plus efficace que les attaques génériques n'est connue.

En pratique, ce n'est pas le résultat direct du protocole de Diffie-Hellman qui est utilisé comme clé : on l'utilise plutôt comme source d'entropie, fournie à une fonction de dérivation de clé.

Le protocole de Diffie-Hellman, tel que décrit ci-dessus, ne garantit que la sécurité contre une adversaire passif, capable d'écouter la conversation mais pas d'interférer avec elle. Si l'adversaire est capable d'intercepter les communications, alors il est possible de monter une attaque de l'homme du milieu. Pour cela, il suffit à l'adversaire de se faire passer pour Alice auprès de Bob, et pour Bob auprès d'Alice. Il établira avec chacun une clé, et pourra ainsi déchiffrer les messages envoyés par Alice (et, s'il le souhaite, les transmettre à Bob, potentiellement après les avoir modifié).

Pour se prémunir d'un tel scénario, un protocole d'échange doit être authentifié. On peut pour cela utiliser un schéma de signature, et s'assurer que chaque message envoyé est signé par son auteur et vérifié par son destinataire. Pour des raisons de performance, seule une signature portant sur l'intégralité de la conversation peut être produite : c'est l'approche retenue par TLS. Cependant cette simplification fragilise l'échange de clé en pratique, puisqu'un attaquant possède jusqu'à la fin de la conversation pour forger une signature : c'est un des composants de l'attaque Logjam.

Pour pouvoir vérifier la validité d'une signature numérique, le destinataire doit avoir connaissance de la clé de vérification correspondante. Il s'agit d'une clé publique de long terme, qui peut être certifiée pour en garantir la provenance. Un échange de clé authentifié s'appuie donc sur la disponibilité d'une infrastructure de clé publique. La sécurité de la signature numérique utilisée peut reposer sur d'autres hypothèses que le problème de Diffie-Hellman, comme la difficulté de factoriser de grands entiers pour RSA.

La quantité ${\displaystyle y_{A}}$ (ou ${\displaystyle y_{B}}$) utilisée peut ainsi être calculée à chaque session avec un nouveau ${\displaystyle x_{A}}$ (resp. ${\displaystyle x_{B}}$). L'utilisation d'une clé de session « éphémère » offre la garantie suivante : si une clé de session est découverte par l'adversaire, ce dernier ne possède aucune information à propos des sessions passées ou futures. On dit qu'un tel mécanisme garantit parfaitement la confidentialité persistante.

En revanche, la clé de long terme utilisée pour la signature des messages, si elle est découverte par l'adversaire, lui permet d'usurper l'identité d'un des participants. Pour certains schémas de signature, notamment les signatures de Schnorr et ses variantes DSA, ECDSA, EdDSA, des faiblesses du générateur de nombre aléatoire sont susceptibles de révéler la clé secrète. En 2004, l'algorithme Dual EC DRBG a été standardisé par le NIST, comme générateur de nombres pseudo-aléatoire destinés à une utilisation notamment pour la signature numérique. En 2013, les révélations d'Edward Snowden confirment qu'il s'agit d'une tentative d'affaiblissement de la cryptographie (dans le cadre du programme Bullrun de la NSA), permettant à ses auteurs de prédire la génération de nombres aléatoires au moyen d'une porte dérobée. Dual EC DRBG a été retiré en 2014 de la liste officielle du NIST.

Plutôt qu'un protocole dans lequel les deux partis obtiennent une clé, il est possible que l'un des partis décide une clé, qu'il transmet à l'autre. Pour que cette transmission soit sûre, la clé envoyée est chiffrée : on parle d'encapsulation de clé.

Un mécanisme d'encapsulation de clé peut utiliser tout chiffrement à clé publique, par exemple RSA : Alice publie sa clé publique, Bob choisit une donnée aléatoire qu'il chiffre avec la clé d'Alice. Cette donnée sera utilisée pour dériver une clé par les deux partis.

Un cas extrême d'encapsulation consiste à utiliser un chiffrement symétrique pour envoyer une clé, ce qui requiert que les deux partis se soient préalablement coordonnés sur un secret. Ce secret peut être par exemple un mot de passe : on parle d'échange de clé authentifié par mot de passe (PAKE), dont les premières versions ont été proposées en 1992^[5],[6], qui furent rapidement cassées. Les premières constructions dotées d'une preuve de sécurité sont obtenues en 2000^[7],[8], dans le modèle de l'oracle aléatoire. Les premières preuves dans le modèle standard datent de 2001^[9],[10].

En 2002, Antoine Joux montre comment utiliser les accouplements de Weil sur courbes elliptiques pour effectuer, en un tour, un échange de clé à trois partis^[11]. Le protocole de Diffie-Hellman, s'il était utilisé, nécessiterait l'établissement d'un canal sécurité entre chaque paire.

En 2003, Dan Boneh et Alice Silverberg proposent de généraliser cette construction, afin d'échanger une clé entre un nombre arbitraire de participants, au moyen d'une application multilinéaire cryptographique^[12]. Il s'agit d'un algorithme effectivement calculable ${\displaystyle e:G_{1}\times \cdots \times G_{n}\rightarrow G_{T}}$ satisfaisant notamment que pour tous entiers ${\displaystyle a_{1},\dotsc ,a_{n}}$et tous ${\displaystyle g_{i}\in G_{i}}$ , on a ${\displaystyle e(g_{1}^{a_{1}},\ldots ,g_{n}^{a_{n}})=e(g_{1},\ldots ,g_{n})^{\prod _{i=1}^{n}a_{i}}}$, qui vérifie une extension des propriétés de sécurité des couplages. Il faut attendre 2013 pour voir apparaître les premiers candidats^[13],[14], qui ont depuis été cassés^{[15],[16],[17],[18]}.

La construction d'un protocole efficace d'échange de clé multipartite, et la conception d'une application multilinéaire cryptographique, sont en 2018 des questions de recherche encore ouvertes.

Le problème du logarithme discret, sur lequel s'appuie le protocole de Diffie-Hellman, peut être résolu efficacement sur un ordinateur quantique au moyen de l'algorithme de Shor. Par ailleurs, la signature utilisée pour authentifier une session est également à risque.

Plusieurs protocoles de remplacement ont donc été proposés, qui ne souffrent pas de telles faiblesses. Parmi les propositions, on compte notamment l'algorithme de Jao-De Feo^[19], reposant sur les isogénies de courbes elliptiques supersingulières, et l'algorithme New Hope^[20], reposant sur les problèmes de court vecteurs dans les réseaux euclidiens. New Hope a été implémenté et utilisé de manière expérimentale dans le navigateur Google Chrome en 2016^[21].

Sans lien avec la section précédente, il a été proposé d'utiliser, au lieu de garanties mathématiques et informatiques, les propriétés de la physique pour assurer la sécurité de l'échange de clé. Plus spécifiquement, l'observation des propriétés statistiques d'un flux de particules intriquées, associée au théorème de non clonage permet de détecter un adversaire qui écoute, et de « jeter » une partie des bits ainsi révélés en corrigeant le bruit (ce qui corrige également les erreurs inhérente aux mesures). Cette étape de réconciliation aboutit à une séquence de bits communs aux deux partis souhaitant échanger une clé. Une étape supplémentaire d'amplification est nécessaire pour pouvoir dériver de la séquence commune une clé.

Plusieurs de ces protocoles ont été implémentés et validés expérimentalement, sur des distances couvrant plusieurs centaines de kilomètres^[22].

Toutefois, l'échange de clé quantique pose un certain nombre de défis technologiques et opérationnels, qui limitent pour l'instant son déploiement : en particulier, un canal de communication spécifique doit être établi entre les participants. Par exemple, pour les protocoles BB84, B92^[23] ou SARG04^[24], il faut pouvoir assurer le transport de photons à basse énergie en conservant leur polarisation en dépit des phénomènes de décohérence sur toute la longueur du canal.

• Portail de la cryptologie