Échange de clés Diffie-Hellman

L'échange de clé Diffie Hellman est un des nombreux classiques de la cryptographie moderne. Il permet à la fois d'établir un secret partagé sans nécessiter de canal de communication privé mais est également de fournir une confidentialité persistante entre sessions.

Lorsqu’on veut chiffrer ses communications, on a le choix entre deux grandes familles d’algorithmes :

  1. Asymétriques, ils utilisent deux clés, l’une est publique et permet de chiffrer, l’autre reste privée et permet de déchiffrer.
  2. Symétriques, ils utilisent la même clé pour chiffrer et déchiffrer.

L’avantage des premiers réside dans leur clé publique, qu’on peut diffuser publiquement et ainsi permettre à tout le monde de pouvoir nous envoyer des messages.

Mais dès que la performance est un critère important, ils perdent face aux seconds, bien plus efficaces mais qui nécessitent que les correspondants partagent un secrète (la clé).

pixel2013 @ pixabay
pixel2013 @ pixabay

L'échange de clé Diffie-Hellman, du nom de ses seconds inventeurs (ceux qui ont déposé le brevet en 1977 car les premiers découvreur, travaillant dans les services de communication du gouvernement britanniques, n'ont pas pu publier leur découverte), est un protocole de communication permettant de résoudre ce problème : établir un secret partagé en s’échangeant des messages via un canal de communication public.

On réparti un calcul mathématique particulier entre les participants pour qu’ils arrivent, chacun, au même résultat (deux exponentation modulaires). Tout en s'assurant qu’un observateur ne puisse pas y arriver en voyant les résultats intermédiaires (il devrait, pour celà, résoudre un logarithme discret.

Protocole d'échange de clés

Le but est donc de calculer une valeur commune sans qu'une oreille indiscrète ne puisse la deviner. Plutôt que de vous refaire la métaphore à base de peinture, je vous propose une version plus géographique...

Principe de base

Établir une clé secrète, c'est un peu comme établir un point de rendez-vous. Le but, pour Alice et Bob qui veulent pouvoir parler tranquillement, est de se retrouver au même endroit sans que Eve, qui espionne leurs communications, ne sache où ils se trouvent.

langll @ pixabay
langll @ pixabay

Pour commencer Alice et Bob se rencontrent dans un lieu public, c'est le point de départ. Ils choisissent secrètement le déplacement qu'ils veulent faire et partent chacun de leur côté. Une fois à leur point d'arrivée, ils s'envoient leur position respective, échangent de place et refont le même déplacement. Si tout va bien, ils se retrouvent au même endroit, mais pas Eve.

Pour que ce protocole fonctionne, il y a quelques petites contraintes à respecter. On considère que Eve n'est pas capable de suivre les mouvements, elle ne peut qu'écouter les communications.

  1. l'ordre des déplacements ne change pas le point d'arrivée (ils sont commutatifs) ;
  2. Eve ne peut pas calculer un déplacement en observant un point de départ et d'arrivée.

Se déplacer à la boussole sur de courtes distances respecte la première contrainte (sur de très longues distances, la courbure de la Terre ne garanti plus l'associativité de ces déplacements) mais pas la seconde. Vous arriverez au même endroit, mais pour Eve, les calculs sont faciles.

Pour respecter la deuxième contrainte, il faut un déplacement que Eve ne puisse pas inverser. Prenons, par exemple, une suite de mouvements aléatoires (avant, arrière, droite, gauche) et jouons là dans un labyrinthe, quitte à butter sur les murs. En observant le point de départ et d'arriver, Eve ne peut pas déduire la suite de mouvements.

Le problème, cette fois, c'est que rien ne garanti qu'Alice et Bob arrivent au même endroit dans le labyrinthe.

Il faut donc un espace et une opération qui soit associatif et difficile à inverser. Le hasard faisant bien les choses, c'est justement les caractéristiques du problème du logarithme discret, sujet d'un précédent article.

Définition formelle

Alice et Bob vont donc utiliser un groupe fini et un générateur. Le groupe fini est l'espace dans lequel ils vont se déplacer, le générateur est leur point de départ, le calcul de l'exponentiation est la façon de se déplacer et les exposants secrets sont les déplacements d'Alice et Bob.

Le protocole d'échange de clé se déroule comme suit :

  1. Alice et Bob se mettent d'accord publiquement sur un groupe \((G, \times)\) et un générateur \(g\) ;
  2. Ils choisissent chacun un nombre aléatoire (leur clé secrète), \(a\) pour Alice et \(b\) pour Bob, ce sera leur déplacement ;
  3. Ils calculent leur première destination (leur clé publique) et se l'envoie l'un l'autre ; Alice envoie donc \(g^a\) à Bob et reçoit \(g^b\) en retour ;
  4. Ils calculent leur destination finale en appliquant de nouveau leur exposant ; Alice calcule \(g^{b^a}\) et Bob calcule \(g^{a^b}\).

Première contrainte. L'équivalence des points d'arrivée est due à l'associativité de l'opération :

\[ g^{a^b} = g^{ab} = g^{ba} = g^{b^a}\]

Deuxième contrainte. La sécurité de cet algorithme est basée sur le fait que Eve, connaissant \(g\), \(g^a\) et \(g^b\), n'est pas capable de calculer \(g^{ab}\). Cette propriété est connue sous le nom de Problème de Diffie-Hellman et, en l'état des connaissances actuelles, semble être aussi difficile que celui du logarithme discret.

On parle de protocole d'échange de clés car les couples \((a, g^a)\) et \((b, g^b)\) sont les paires de clés privées et publiques d'Alice et Bob. Ces clés permettent de calculer le secret partagé et si vous poussez jusqu'à ElGamal, de chiffrer des messages.

Sécurité

Ce protocole, utilisé seul, n'a aucune utilité et sert donc en conjonction avec d'autres protocoles qui comblent ses lacunes (signature) et bénéficient de ses atouts (confidentialité persistante).

Bru-nO @ pixabay

Besoin de signature

Si Eve est en mesure d'intercepter et modifier les communications, ce qui est le cas de certains moyens de communications, la sécurité du protocole tombe.

Si Eve s’intercale entre Alice et Bob, elle peut, elle aussi, choisir un nombre \(e\) et envoyer \(g^e\) de chaque côté. Aucun des deux ne sachant qu’il s’agit de Eve, chaque moitié de communication sera sécurisée par une clé secrète : \(g^{ae}\) entre Alice et Eve et \(g^{be}\) entre Bob et Eve.

Pour éviter ce risque, les communications sont donc signées par Alice et Bob via des clés publiques préalablement échangées ou certifiées par un tiers de confiance.

Confidentialité persistante

On peut alors se demander l'utilité de ce protocole... Quel est l'intérêt d'utiliser un protocole d'échange de clés puisqu'il nécessite un système de chiffrement/signature asymétriques ? Autant utiliser un protocole à clé publique directement !?

D'accord, mais que ce passerait-il si Eve stockait toutes les communications entre Alice et Bob et prenait son temps pour casser la clé privée de Bob ? Une fois la clé cassée (ou volée, tous les coups sont permis), l'ensemble des communications passée et future serait alors compromis.

La confidentialité persistante (ou forward secrecy en anglais) correspond à ce besoin de protéger les communications passées et l'échange de clé Diffie-Hellman apporte cette propriétés aux échanges entre Alice et Bob :

Avec cette variante, même si Eve dispose de la clé privée ayant permis de signer les communications, elle doit quand même casser la clé partagée pour savoir de quoi ils parlent.

Et si en plus, Alice et Bob utilisent des nombres différents à chaque session (on parle alors de clés éphémères), Eve devra casser chaque clé individuellement.

Utilisation dans SSL/TLS

Lorsqu'un client et un serveur mettent en place une connexion sécurisée par SSL/TLS, celle-ci est chiffrée via un algorithme symétrique et nécessite donc que le client et le serveur se mettent d'accord sur la clé à utiliser.

Sans rentrer dans les détails des messages échangés (i.e. RFC-5246), l'établissement d'une connexion suit les étapes suivantes :

  1. Hello Le client et le serveur se mettent d'accord sur les algorithmes qu'ils vont utiliser pour les opérations cryptographiques, les fameuses « cipher suites ».
  2. Certificates Le serveur envoie son certificat et peut demander au client de lui en envoyer un également. Chaque partie vérifie l'authenticité des certificats via leurs tiers de confiance (les fameuses CA).
  3. Key Exchange Messages Le serveur envoie les données nécessaires pour l'échange de clé, le client le fera de même également ensuite.

En fonction des algorithmes choisis dans les messages Hello, l'échange de clé se fait différemment :

RSA Dans ce mode, le client génère une clé partagée et l'envoie au serveur, après l'avoir chiffrée avec la clé privée du serveur. Casser la clé du serveur permet de déchiffrer toutes les communications.

DH - fixed Dans ce mode, le certificat (du client et/ou du serveur) contient déjà les paramètres et clés publiques. Les messages d'échange de clés sont donc vides (puisque la donnée est dans le certificat), les parties calculent le secret partagé grâce au contenu des certificats. Il faut alors casser la clé partagée mais une fois fait, toues les communications suivantes seront lisibles.

DHE - ephemeral Dans ce mode, l’échange de clé est rejoué (avec des nombres différents) à chaque session via les messages Key exchange messages. Il faut donc casser individuellement chaque clé pour chaque session.

Bien que la communication soit initiée par le client, c'est le serveur qui envoie le premier message pour l'échange de clé (et donc fixe le groupe et le générateur). Ceci parce que, culturellement, c'est l'entreprise qui héberge le serveur qui prend la responsabilité de la sécurité des communications.

Les algorithmes ECDH et ECDHE pour l'échange de clés sont également des échanges de clé Diffie-Hellman mais utilisent les courbes elliptiques (d'où la mention EC) comme groupe pour leurs opérations. Le protocole est identique, seul les éléments et l'opération changent.

Et après

On pourrait presque parler de protocole de rêve. Il est simple à implémenter, nécessite peut d'opérations, peut se dérouler publiquement tout en fournissant la confidentialité persistante à toutes vos sessions.

Vous connaissez maintenant son fonctionnement, les raisons de sa sécurité, ses limitations et surtout comment il peut être utilisé pour disposer de communications sûres.