Échange de clés Diffie-Hellman

Voici un exemple du protocole, avec les valeurs non secrètes en bleu et les valeurs secrètes en rouge .

1. Alice et Bob conviennent publiquement d'utiliser un module p = 23 et une base g = 5 (qui est une racine primitive modulo 23).
2. Alice choisit un entier secret a = 4, puis envoie à Bob A = g ^a mod p
   • A = 5 ⁴ mod 23 = 4 (dans cet exemple, A et a ont tous deux la même valeur 4, mais ce n'est généralement pas le cas)
3. Bob choisit un entier secret b = 3, puis envoie à Alice B = g ^b mod p
   • B = 5 ³ mod 23 = 10
4. Alice calcule s = B ^a mod p
   • s =10 ⁴ mod23= 18
5. Bob calcule s = A ^b mod p
   • s =4 ³ mod23= 18
6. Alice et Bob partagent désormais un secret (le nombre 18).

Alice et Bob sont tous deux arrivés aux mêmes valeurs car, sous le mod p ,

Plus précisément,

Seuls a et b sont gardés secrets. Toutes les autres valeurs – p , g , g a  mod p et g b  mod p – sont transmises en clair. La robustesse du système réside dans le fait que le calcul de g ab mod p = g ba mod p prend un temps extrêmement long avec n'importe quel algorithme classique connu, à partir de la seule connaissance de p , g , g a  mod p et g b  mod p . Une telle fonction, facile à calculer mais difficile à inverser, est appelée fonction à sens unique . Une fois qu'Alice et Bob ont calculé le secret partagé, ils peuvent l'utiliser comme clé de chiffrement, connue d'eux seuls, pour envoyer des messages sur le même canal de communication ouvert.

Bien sûr, des valeurs beaucoup plus grandes de a , b et p seraient nécessaires pour sécuriser cet exemple, puisqu'il n'y a que 23 résultats possibles pour n modulo 23. Cependant, si p est un nombre premier d'au moins 600 chiffres, même les ordinateurs modernes les plus rapides, utilisant l'algorithme le plus rapide connu, ne peuvent pas trouver a n étant donnés uniquement g , p et g a  mod p . Ce problème est appelé le problème du logarithme discret . Le calcul de g a  mod p est connu sous le nom d'exponentiation modulaire et peut être effectué efficacement même pour de grands nombres. Notez que g n'a pas besoin d'être grand, et en pratique, il s'agit généralement d'un petit entier (comme 2, 3, ...).

Le tableau ci-dessous illustre qui sait quoi, les informations non secrètes étant en bleu et les informations secrètes en rouge . Ici, Ève joue le rôle d'une espionne : elle observe les échanges entre Alice et Bob, mais elle n'en modifie pas le contenu.

• g , base publique (racine primitive), connue d'Alice, Bob et Ève. g = 5
• p , module public (premier), connu d'Alice, Bob et Ève. p = 23
• a , la clé privée d'Alice, connue d'elle seule. a = 6
• b , la clé privée de Bob, connue de Bob seul. b = 15
• A , la clé publique d'Alice, connue d'Alice, Bob et Ève. A = g ^a mod p = 8
• B , la clé publique de Bob, connue d'Alice, de Bob et d'Ève. B = g ^b mod p = 19

s est la clé secrète partagée, connue d'Alice et de Bob, mais pas d'Ève. Il est à noter qu'il est inutile pour Ève de calculer AB , qui est égal à g ^{a + b} mod p .

Remarque : Il devrait être difficile pour Alice de trouver la clé privée de Bob, et inversement. Si ce n'est pas le cas, une personne malveillante, Ève, pourrait simplement substituer sa propre paire de clés privée/publique, insérer la clé publique de Bob dans sa clé privée, générer une fausse clé secrète partagée, puis trouver la clé privée de Bob (et l'utiliser pour trouver la clé secrète partagée). Ève pourrait choisir une paire de clés publique/privée qui lui faciliterait la tâche.

Voici une description plus générale du protocole :

1. Alice et Bob s'accordent sur un nombre naturel n et un élément générateur g dans le groupe cyclique fini G d'ordre n . (Ceci est généralement fait bien avant le reste du protocole ; g et n sont supposés être connus de tous les attaquants.) Le groupe G est écrit de manière multiplicative.
2. Alice choisit un nombre naturel aléatoire a avec 1 < a < n , et envoie l'élément g ^a de G à Bob.
3. Bob choisit un nombre naturel aléatoire b avec 1 < b < n , et envoie l'élément g ^b de G à Alice.
4. Alice calcule l'élément de G.
5. Bob calcule l'élément de G.

Alice et Bob possèdent désormais l'élément de groupe g ab = g ba , qui peut servir de clé secrète partagée. Le groupe G satisfait la condition requise pour une communication sécurisée tant qu'il n'existe pas d'algorithme efficace pour déterminer g ab  connaissant g , g a et g b  .

Par exemple, le protocole Diffie-Hellman à courbe elliptique est une variante qui représente un élément de G par un point sur une courbe elliptique plutôt que par un entier modulo n. Des variantes utilisant des courbes hyperelliptiques ont également été proposées. L' échange de clés par isogénie supersingulière est une variante de Diffie-Hellman conçue pour résister aux ordinateurs quantiques , mais elle a été compromise en juillet 2022.

Les clés utilisées peuvent être éphémères ou statiques (à long terme), voire mixtes (on parle alors de DH semi-statique). Ces variantes présentent des propriétés différentes et, par conséquent, des cas d'utilisation différents. On trouvera une vue d'ensemble de nombreuses variantes, ainsi que des discussions à ce sujet, dans la publication spéciale 800-56A du NIST. Liste de base :

1. Éphémère : généralement utilisé pour les accords de clés. Assure la confidentialité persistante , mais pas l’authenticité .
2. statique, statique : Génère un secret partagé à long terme. Ne garantit pas la confidentialité persistante, mais une authentification implicite. Les clés étant statiques, elles ne protègent pas contre les attaques par rejeu, par exemple .
3. Éphémère, statique : par exemple, utilisé dans le chiffrement ElGamal ou le schéma de chiffrement intégré (IES) . En cas d’échange de clés, il peut fournir une authentification unilatérale implicite (la partie éphémère peut vérifier l’authenticité de la partie statique). Aucune confidentialité persistante n’est assurée.

Il est possible d'utiliser des clés éphémères et statiques dans un seul accord de clés pour fournir plus de sécurité, comme par exemple dans NIST SP 800-56A, mais il est également possible de les combiner dans un seul échange de clés DH, qui est alors appelé triple DH (3-DH).

L'échange de clés Diffie-Hellman ne se limite pas à la négociation d'une clé partagée par deux participants seulement. Un nombre quelconque d'utilisateurs peut participer à un accord en exécutant successivement le protocole d'échange et en communiquant des données intermédiaires (qui n'ont pas besoin d'être gardées secrètes). Par exemple, Alice, Bob et Carol pourraient participer à un échange Diffie-Hellman comme suit, toutes les opérations étant considérées comme modulo p :

1. Les parties s’accordent sur les paramètres de l’algorithme p et g .
2. Les parties génèrent leurs clés privées, nommées a , b et c .
3. Alice calcule et l'envoie à Bob.
4. Bob calcule et l'envoie à Carol.
5. Carol calcule et l'utilise comme son secret.
6. Bob calcule et l'envoie à Carol.
7. Carol calcule et l'envoie à Alice.
8. Alice calcule et l'utilise comme son secret.
9. Carol calcule et l'envoie à Alice.
10. Alice calcule et l'envoie à Bob.
11. Bob calcule et l'utilise comme son secret.

Un espion a pu voir , , , , , et , mais ne peut utiliser aucune combinaison de ceux-ci pour reproduire efficacement .

Pour étendre ce mécanisme à des groupes plus importants, deux principes de base doivent être respectés :

• En commençant par une clé « vide » composée uniquement de g , le secret est créé en élevant la valeur actuelle à l'exposant privé de chaque participant une fois, dans n'importe quel ordre (la première exponentiation de ce type donne la propre clé publique du participant).
• Toute valeur intermédiaire (ayant reçu jusqu'à N − 1 exposants, où N est le nombre de participants au groupe) peut être divulguée publiquement, mais la valeur finale (après application des N exposants) constitue le secret partagé et ne doit donc jamais être divulguée publiquement. Ainsi, chaque utilisateur doit obtenir sa copie du secret en appliquant sa propre clé privée en dernier (sinon, le dernier contributeur ne pourrait pas communiquer la clé finale à son destinataire, car il aurait transformé cette clé en secret même que le groupe souhaite protéger).

Ces principes laissent la porte ouverte à diverses options quant à l'ordre de contribution des participants aux clés. La solution la plus simple et la plus évidente consiste à disposer les N participants en cercle et à faire tourner les N clés sur ce cercle, jusqu'à ce que chaque clé ait été complétée par l'ensemble des N participants (en terminant par son propriétaire) et que chaque participant ait contribué à N clés (en terminant par la sienne). Toutefois, cette méthode exige que chaque participant effectue N exponentiations modulaires.

En choisissant un ordre plus approprié et en s'appuyant sur le fait que les clés peuvent être dupliquées, il est possible de réduire le nombre d'exponentiations modulaires effectuées par chaque participant à en utilisant une approche de type diviser pour régner , donnée ici pour huit participants :

1. Les participants A, B, C et D effectuent chacun une exponentiation, donnant ; cette valeur est envoyée à E, F, G et H. En retour, les participants A, B, C et D reçoivent .
2. Les participants A et B effectuent chacun une exponentiation, donnant , qu'ils envoient à C et D, tandis que C et D font de même, donnant , qu'ils envoient à A et B.
3. Le participant A effectue une exponentiation, donnant , qu'il envoie à B ; de même, B envoie à A. C et D font de même.
4. Le participant A effectue une dernière exponentiation, donnant le secret = , tandis que B fait de même pour obtenir = ; de même, C et D font de même.
5. Les participants E à H effectuent simultanément les mêmes opérations en utilisant comme point de départ.

Une fois cette opération terminée, tous les participants posséderont le secret , mais chaque participant n'aura effectué que quatre exponentiations modulaires, au lieu des huit qu'implique un simple arrangement circulaire.

Le protocole est considéré comme sûr contre l'écoute clandestine si G et g sont correctement choisis. En particulier, l'ordre du groupe G doit être élevé, surtout si ce même groupe est utilisé pour un trafic important. L'espion doit résoudre le problème de Diffie-Hellman pour obtenir g = ^ab . Ceci est actuellement considéré comme difficile pour les groupes dont l'ordre est suffisamment élevé. Un algorithme efficace pour résoudre le problème du logarithme discret permettrait de calculer facilement a ou b et de résoudre le problème de Diffie-Hellman, rendant ainsi ce protocole et de nombreux autres systèmes de chiffrement à clé publique vulnérables. Les corps de faible caractéristique peuvent être moins sûrs.

L' ordre de G doit posséder un grand facteur premier pour empêcher l'utilisation de l' algorithme de Pohlig-Hellman afin d'obtenir a ou b . C'est pourquoi un nombre premier de Sophie Germain q est parfois utilisé pour calculer , appelé nombre premier sûr , car l'ordre de G n'est alors divisible que par 2 et q . Parfois, g est choisi pour générer le sous-groupe d'ordre q de G , plutôt que G lui-même , de sorte que le symbole de Legendre de g a ne révèle jamais le bit de poids faible de a . IKEv2 est un protocole utilisant un tel choix .

Le générateur g est souvent un petit entier tel que 2. En raison de l' autoréductibilité aléatoire du problème du logarithme discret, un petit g est tout aussi sûr que n'importe quel autre générateur du même groupe.

Si Alice et Bob utilisent des générateurs de nombres aléatoires dont les résultats ne sont pas totalement aléatoires et peuvent être prédits dans une certaine mesure, il est alors beaucoup plus facile d'écouter aux portes.

Dans sa description originale, l'échange Diffie-Hellman ne garantit pas à lui seul l'authentification des parties communicantes et peut être vulnérable à une attaque de l'homme du milieu . Mallory (une attaquante active exécutant une telle attaque) peut établir deux échanges de clés distincts, l'un avec Alice et l'autre avec Bob, se faisant ainsi passer pour Alice auprès de Bob, et inversement. Cela lui permet de déchiffrer, puis de rechiffrer, les messages échangés. Il est important de noter que Mallory doit être présente au milieu de la communication dès le début et y rester, déchiffrant et rechiffrant activement les messages à chaque communication entre Alice et Bob. Si elle intervient après la génération des clés et le début de la conversation chiffrée entre Alice et Bob, l'attaque échoue. En cas d'absence, sa présence est révélée à Alice et Bob. Ils sauront alors que toutes leurs conversations privées ont été interceptées et décodées par une personne présente sur le canal. Dans la plupart des cas, cela ne leur permettra pas d'obtenir la clé privée de Mallory, même si elle a utilisé la même clé pour les deux échanges.

Pour prévenir ce type d'attaque, il est généralement nécessaire d'utiliser une méthode d'authentification entre les parties communicantes. Des variantes de l'échange de clés Diffie-Hellman, comme le protocole STS , peuvent être utilisées à cette fin.