Échange de clés Diffie-Hellman

La méthode Diffie-Hellman d’échange de clés est utilisée afin de générer un secret commun entre deux correspondants à travers un canal public potentiellement sur écoute. Publiée en 1976 par les biens nommés Whitfield Diffie et Martin Hellman, c’est la première référence connue du public à proposer l’idée d’une clé privée associée à une clé publique afin d’apporter, à terme, la confidentialité des échanges. Une application concrète de la cryptographie asymétrique était née. Bien que réputée moins performante que la cryptographie symétrique, elle ne nécessite pas l’établissement d’un canal de confiance entre les pairs pour échanger un secret commun.

L’histoire de la cryptographie asymétrique

James Henry Ellis était un mathématicien du Government Communications Headquarters (GCHQ), l’équivalent anglais de la NSA américaine. Grâce à la déclassification de documents datant des années 70, on sait qu’Ellis avait pensé au “chiffrement non secret” autrement dit au chiffrement asymétrique avant les travaux de Diffie, Hellman et Merkle. Il se serait inspiré d’une publication écrite lors de la Seconde Guerre Mondiale par les Laboratoires Bell, décrivant comment protéger une communication voix en ajoutant ou en ôtant du bruit. Seulement, il n’a pas été capable d’implémenter cette idée mathématiquement.

Par conséquent, l’histoire de la cryptographie asymétrique est somme toute assez récente. Il faut attendre 1974 pour que Ralph Merkel (les fans des blockchains reconnaîtront l’inventeur des “arbres de Merkel”) théorise son protocole appelé “Puzzles de Merkel”. Il s’agit du premier cryptosystème à clé publique jamais inventé.

Le concept des Puzzles de Merkel

Alice et Bob, nos deux compères inséparables et accros à la cryptographie, veulent communiquer à distance pour s’échanger leurs petits secrets. Alice commence par créer beaucoup de messages chiffrés par un algorithme symétrique dont la résistance est délibérement affaiblie par l’utilisation d’une clé de mauvaise qualité (par exemple 80 bits à zéro concaténés à 30 bits aléatoires). Elle aura pris soin d’identifier chaque message avec un identifiant unique ainsi qu’une clé de session aléatoire. Elle envoie l’ensemble à Bob.

Comme elle connaît Bob, elle sait qu’il sera capable de décrypter par force brute au moins un message aléatoirement sélectionné en un temps raisonnable. Bob s’exécute et une fois cette tâche terminée, il peut logiquement lire l’identifiant du message ainsi que sa clé de session. À cet instant précis, Alice et Bob ont en commun la même clé de session sans qu’Eve, la méchante de l’histoire, ne sache laquelle. En effet, Eve a vu passer les messages chiffrés sur le canal espionné mais cela ne lui donne aucun indice sur la clé de session sélectionnée par Bob.

Bob informe publiquement sa correspondante Alice de l’identifiant unique du message qu’il a réussi à décrypter. Alice est donc maintenent en mesure de faire la correspondance entre cet identifiant unique la clé de session aléatoire associée. Le tour est joué, le secret est désormais partagé !

Eve est toujours dans les parages et a tout écouté. Pour réussir son attaque, charge à elle de décrypter l’ensemble des messages envoyés par Alice. Elle y arrivera mais en un temps beaucoup plus important que Bob, au vu de la quantité de messages à traiter. Eve cherche donc ardemment l’identifiant unique parmi tous les messages chiffrés capturés ce qui lui permettra de tomber sur la clé de session aléatoire partagée entre Alice et Bob.

Par conséquent, on comprend que la clé secrète d’Alice utilisée pour le chiffrement des messages doit être suffisamment longue (mais pas trop) pour que le décryptage d’un grand nombre de messages, les pièces du Puzzle, soit pratiquement impossible en un temps raisonnable.

Complexité algorithmique des Puzzles de Merkel

En supposant que le décryptage d’un message à l’aide d’une attaque par force brute nécessite \(\small n\) étapes et qu’il y a \(\small m\) messages chiffrés à traiter, la récupération de la clé de session par Bob lui prendra \(\small O(n+m)\). Pour Eve, la complexité en temps sera de \(\small O(n*m)\). Cette complexité quadratique n’est pas considérée comme suffisamment sûre contre un attaquant. En outre, ce protocole d’échange de clé n’assure pas l’authentification des parties communicantes. Il est, dans sa construction, vulnérable aux attaques de type “man-in-the-middle”, tout comme celui de Diffie-Hellman. En effet, Eve peut très bien établir deux sessions du protocole, l’une avec Alice et l’autre avec Bob, et prétendre être la partie opposée à chacune d’entre elles. Eve créera deux clés secrètes et les utilisera pour communiquer avec eux en se faisant passer pour l’autre partie. Un exemple de cette problématique est exposé plus bas.

Whitfield Diffie et Martin Hellman

Whitfield Diffie et Martin Hellman sont deux fameux cryptologues qui ont transposé le concept des “Puzzles de Merkel” mathématiquement. Ils ont d’ailleurs collaboré avec Ralph Merkel pour arriver à construire ce qu’on appelle “l’échange de clés Diffie-Hellman”. Ci-dessous une citation d’Hellman provenant de sa publication An Overview Of Public Key Cryptography publiée en novembre 1978 dans le IEEE Communications Magazine.

Bien que ce système ait été décrit pour la première fois dans un document de Diffie et moi, il s’agit d’un système de distribution à clé publique, un concept développé par Merkle, et devrait donc s’appeler “échange de clé Diffie-Hellman-Merkel” si des noms doivent y être associés. J’espère que cette petite chaire pourrait aider à reconnaître la contribution égale de Merkle à l’invention de la cryptographie à clé publique.

Les travaux de Diffie et Hellman sur la cryptographie asymétrique leur ont valu l’obtention du Prix Turing de l’Association for Computing Machinery en 2015.

L’échange de clés Diffie-Hellman

Contrairement à ce l’on pourrait penser, dans la méthode d’échange de clés Diffie-Hellman (souvent réduit sous la forme DH), il n’y a pas à proprement parlé de communication directe de clés. On a pu le voir avec le concept des “Puzzles de Merkel”. On échange seulement des paramètres publics qui seront utilisés pour créer simultanément chez les deux interlocuteurs une même clé secrète.

L’algorithme mathématique

Passons aux choses sérieuses. Que se passe-t-il sous le capot ? Il existe différentes variantes de DH. Je n’aborderai ici que l’originale de 1976.

Alice et Bob, qui sont de retour, choisissent ensemble deux paramètres publics :

• un nombre premier vraiment grand, le modulus, noté \(\small p\),
• un nombre \(\small g\), le générateur (aussi appelé base) de telle sorte que \(\small 1 < g < p\). Notez qu’ici, \(\small g\) est une racine primitive modulo \(\small p\).

Alice choisit secrètement un entier \(\small a\), sa clé privée. Bob fait de même avec un entier \(\small b\), représentant sa propre clé privée. Alice envoie à Bob le résultat du calcul \(\small g^a\bmod p\), c’est-à-dire sa clé publique que l’on nomme \(\small pka\). Bob transmet à son tour à Alice le résultat de \(\small g^b\bmod p\), à savoir sa clé publique \(\small pkb\). Grâce à son secret \(\small a\), Alice calcule \(\small s\equiv (g^b)^a \bmod p\). Bob résout à son tour \(\small s\equiv (g^a)^b \bmod p\). Ils ont désormais chacun une clé \(\small s\) identique !

Exemple

Pour cet exemple, utilisons des nombres volontairement intelligibles. Il faut savoir qu’actuellement l’état de l’art recommande une taille pour \(\small p\) codée sur 3072 bits (Groupe Diffie-Hellman 15). Cependant, avec un tel groupe, la génération de ce modulus prendra du temps ce qui pourrait être lourd pour certains systèmes.

1. Alice et Bob communiquent par canal non chiffré dans le but de choisir \(\small p\) et \(\small g\). Ils s’accordent sur les valeurs \(\small p = 281\) et \(\small g = 148\).
2. Alice choisit son entier \(\small a = 50\). Bob fait de même avec \(\small b = 33\). Ces entiers ne sont pas partagés puisqu’il s’agit de clés privées.
3. Alice calcule \(\small pka\) soit \(\small 148^{50} \equiv 245 \bmod 281\). Bob quant à lui résout \(\small 148^{33} \equiv 94 \bmod 281\) sa \(\small pkb\).
4. Ils échangent ces deux solutions, leur clé publique, toujours par canal public.
5. Alice calcule désormais \(\small 94^{50} \equiv 247 \bmod 281\) et Bob \(\small 245^{33} \equiv 247 \bmod 281\).

Alice et Bob obtiennent le même résultat soit 247 sans jamais avoir échangé ce nombre par canal public ! Ils peuvent désormais utiliser ce secret partagé comme clé de l’algorithme symétrique de leur choix.

Ces nombres sont très petits et utilisés à titre d’illustration. Un attaquant pourrait trouver facilement la clé secrète partagée en calculant \(\small 148^{a}\bmod 281 \equiv 245\) ou \(\small 148^{b} \bmod 281 \equiv 94\) par brute force. L’attaquant calculerait toutes les puissances de \(\small 148 \bmod 281\) et s’arrêterait une fois 245 ou 94 trouvé.

Un protocole vulnérable au MitM

L’histoire était trop belle. Une intruse s’est glissée dans le canal d’échange des paramètres et des clés publiques entre Alice et Bob qui communiquent sans authentification mutuelle ! La jalouse Eve est indétectable et se retrouve donc en position d’interception entre Alice et Bob. Elle est donc en possession de :

• \(\small p = 281\),
• \(\small g = 148\),
• \(\small pka\) soit \(\small 148^{a} \equiv 245 \bmod 281\) avec \(\small a\) inconnu, envoyée par Alice mais interceptée par Eve,
• \(\small pkb\) soit \(\small 148^{b} \equiv 94 \bmod 281\) avec \(\small b\) inconnu, envoyée par Bob mais interceptée par Eve.

Préparation de l’attaque

Eve génère deux clés privées \(\small ea\) et \(\small eb\) puis calcule \(\small pkea\) et \(\small pkeb\). Prenons :

• \(\small ea = 123\), clé privée pour les échanges d’Eve vers Alice,
• \(\small eb = 132\), clé privée pour les échanges d’Eve vers Bob,
• \(\small pkea = 148^{123} \bmod 281 \equiv 268 \bmod 281\), clé publique pour les échanges d’Eve vers Alice,
• \(\small pkeb = 148^{132} \bmod 281 \equiv 170 \bmod 281\), clé publique pour les échanges d’Eve vers Bob.

Détail des calculs

Eve est maintenant en capacité de calculer la clé secrète partagée avec Alice que l’on nomme \(\small ska\) tel que \(\small ska = 245^{123} \bmod 281 \equiv 253 \bmod 281\).

Eve transmet \(\small pkeb\) à Bob qui peut maintenant calculer la clé secrète \(\small skb\) commune avec Eve tel que \(\small skb = 170^{33} \bmod 281 \equiv 183 \bmod 281\).

Bob envoie à Eve, pensant être Alice, \(\small pkb\). Ainsi, Eve sait maintenant calculer de son côté \(\small skb\) tel que \(\small skb = 94^{132} \bmod 281 \equiv 183 \bmod 281\). À cet instant, Bob et Eve peuvent dialoguer avec un algorithme de chiffrement symétrique.

Eve transmet \(\small pkea\) à Alice qui peut maintenant calculer la clé secrète \(\small ska\) tel que \(\small ska = 268^{50} \bmod 281 \equiv 253 \bmod 281\). Cette valeur correspond bien à celle trouvée par Eve. Désormais Eve peut déchiffrer puis chiffrer incognito et à la volée tous les messages envoyés sur le canal de communication exploité par Alice et Bob.