Dans les coulisses de TLS (1.3): zoom sur l'algorithme X25519

La majorité des communications sur Internet est désormais sécurisée grâce au protocole TLS (Transport Layer Security), en particulier via le HTTPS, qui n’est rien d’autre que du HTTP encapsulé dans du TLS. En 2021, la quasi-totalité des serveurs et clients web supportent le TLS 1.2, les versions précédentes ne devant plus être utilisées car elles comportent des failles de sécurité. La version 1.3 du TLS, publiée en 2018, apporte de nombreuses améliorations et est à ce jour l’état de l’art en matière de sécurité.

Le rôle de TLS est d’assurer:

• l’authenticité du serveur, autrement dit la garantie que le site www.mabanque.com appartient bien à Mabanque et non à la mafia nord-coréenne,
• la confidentialité des échanges entre le client et le serveur,
• l’intégrité des données, c’est-à-dire l’assurance que les données reçues par le client sont bien celles qui ont été envoyées par le serveur, et vice versa.

La confidentialité repose sur le chiffrement des messages par un algorithme de chiffrement symétrique (à clé secrète), généralement de type AES 128 ou 256 bits. La clé étant secrète, elle doit être connue du client et du serveur (et personne d’autre !), ce qui nous amène au sujet de cet article: l’algorithme X25519.

Lorsqu’un client (par exemple un navigateur web) se connecte à un serveur TLS, il effectue d’abord ce qu’on appelle la poignée de mains (handshake) qui est un échange de messages servant entre autres à partager la fameuse clé secrète entre le client et le serveur. Avant TLS 1.3, divers algorithmes pouvaient être utilisés pour l’échange de clé, mais pour simplifier le protocole et améliorer la sécurité, seul l’algorithme X25519 est maintenant utilisé.

Cet algorithme est de la famille ECDH (Elliptic-Curve Diffie-Hellman), et est crucial pour la sécurité d’Internet, car toute attaque réussie sur l’algorithme impliquerait de pouvoir espionner n’importe quelle conversation chiffrée avec TLS !

Avant d’expliquer le fonctionnement de X25519, il faut d’abord revenir sur l’algorithme de Diffie-Hellman (DH) classique, qui était utilisé dans les vieilles versions de TLS. Le DH est assez magique car à la fois très simple et très efficace. Il repose sur le problème du “logarithme discret”, qui est relativement simple à comprendre mais difficile à résoudre. Pour commencer, il faut choisir un nombre premier p très (très) grand, et un petit nombre g “qui convient” (je passe les détails pour l’instant), appelé le générateur. La suite de l’algorithme consiste à effectuer des calculs “modulo p”, autrement dit:

• On utilise uniquement des entiers compris entre 0 et p-1
• Si le résultat d’un calcul sort de l’intervalle [0, p-1], on se ramène à cet intervalle en prenant le reste de la division par p

Par exemple si on prend p=11, on ne travaillera qu’avec les nombres de 0 à 10, et les calculs se font comme ceci:

• \(2 + 10 = 12 = 1\) (car 1 est le reste de 12 divisé par 11)
• \(5 * 5 = 25 = 3\) (car 3 est le reste de 25 divisé par 11)
• \(2 - 5 = -3 = 8\)
• \(3 * 4 = 12 = 1\)
• \(3^4 = 81 = 4\)
• etc.

Au passage puisque 3 * 4 = 1, alors par définition 4 est l’inverse de 3 et donc 1 / 3 = 4 !

Ce mode de calcul s’appelle l’arithmétique dans \(\mathbb{Z}/p\mathbb{Z}\), et demande un peu de pratique mais on s’y habitue assez vite. Pour la suite, nous aurons besoin de calculer les puissances du nombre g (modulo p). Si on prend par exemple g = 3, on obtient:

• \(3^1 = 3\)
• \(3^2 = 9\)
• \(3^3 = 5\)
• \(3^4 = 4\)
• \(3^5 = 1\)
• \(3^6 = 3\)
• \(3^7 = 9\)
• \(3^8 = 5\)
• \(3^9 = 4\)
• \(3^{10} = 1\)

On voit que dans ce cas on retombe sur le nombre g au bout de 5 itérations, et donc l’ensemble des puissances de 3 contient 5 éléments différents. En fait on peut montrer que dans le cas général, le nombre de puissances de g différentes (ce nombre est appelé “l’ordre de g” et sera noté q) est forcément un diviseur de p-1, et donc si p=11, q vaut 1, 2, 5 ou 10.

Ceci étant dit, l’algorithme de Diffie-Hellman est le suivant:

• Alice choisit un nombre secret a et calcule \(A = g^a\). Le nombre a est appelé la clé privée d’Alice et A sa clé publique. Attention le calcul se fait toujours modulo p !
• De même Bob choisit un nombre b et calcule \(B = g^b\)
• Alice envoie à Bob sa clé publique (A), et Bob envoie à Alice sa clé publique (B)
• Alice calcule \(S = B^a = (g^b)^a = g^{ab}\)
• Bob calcule \(S’ = A^b = (g^a)^b = g^{ab}\)
• Comme S = S’, Alice et Bob connaissent tous les deux ce nombre et peuvent donc l’utiliser comme clé secrète.

Toute la magie de l’algorithme tient au fait que l’échange des clés publiques A et B peut se faire via une communication en clair (non chiffrée), et pourtant le nombre S ne peut être connu que par Alice et Bob ! En effet même si un attaquant connaît les nombres A et B, il est lui est impossible de retrouver la clé secrète a (et donc de calculer \(B^a\)) à partir de A, car il n’existe pas de méthode efficace pour retrouver a en connaissant \(g^a\), opération appelée logarithme discret. Mais attention, il ne faut pas choisir g n’importe comment: l’ordre de g (c’est-à-dire le nombre de puissances de g différentes) doit être un nombre premier (et très grand) sinon il peut exister une attaque qui permettrait à un “homme du milieu” interceptant la communication de deviner plus (voire très) facilement la valeur de S.

Avec p=11 et g=3, on peut facilement fabriquer une table qui donne directement a à partir de A, mais en pratique on choisit un nombre premier de 2048 bits (!) voire plus, pour obtenir une sécurité satisfaisante. Ceci oblige à utiliser des clés très lourdes (2048 bits également) et explique que l’algorithme de DH classique est de moins en moins utilisé.

L’algorithme X25519 est aussi de type Diffie-Hellman, mais utilise l’arithmétique sur courbe elliptique (d’où le nom Elliptic-Curve Diffie-Hellman), beaucoup plus sophistiquée mais aussi plus efficace d’un point de vue cryptographique que le simple calcul de puissances utilisé dans le DH classique. Le nom assez mystérieux de cet algorithme sera expliqué à la fin de l’article, patience donc !

Pour comprendre la méthode, prenons d’abord un exemple simple: la courbe d’équation \(y^2 = x^3 + 1\) (avec x et y réels pour l’instant), qui est un exemple de courbe elliptique. Il est possible de définir une opération d’addition sur l’ensemble des points de cette courbe, de la façon suivante: pour additionner 2 points P et Q, on trace une droite passant par P et Q et on note R le 3eme point d’intersection de cette droite avec la courbe. Alors par définition le point P+Q est le point opposé de R (noté -R), qui est le 2eme point d’intersection entre la courbe et la droite verticale passant par R:

Il y a 2 cas particuliers:

• Si P = Q, alors il faut prendre comme droite la tangente à la courbe au point P
• Si P = -Q, alors la droite passant par P et Q est verticale, et il n’y a pas de 3ème point d’intersection avec la courbe. Dans ce cas la somme P+Q est égale à un point fictif noté O, appelé le point “à l’infini” (à ne pas confondre donc avec l’origine du repère !)

Avec cette définition, on peut donc choisir un point G sur la courbe, et calculer les “multiples” de ce point, c’est à dire les points:

• 2G = G + G
• 3G = 2G + G
• 4G = 3G + G
• etc.

Mais quel rapport avec l’algorithme de Diffie-Hellman ? Et bien, grâce à la multiplication sur notre courbe elliptique, on peut appliquer exactement le même principe:

• Alice choisit un nombre entier a (la clé privée), calcule le point aG, et l’envoie à Bob,
• Bob choisit un nombre b, calcule le point bG, et l’envoie à Alice,
• Alice peuvent donc chacun de leur côté calculer le point S = abG = baG, qui sera la clé secrète.

Comme en pratique les ordinateurs ne peuvent pas (réellement) travailler avec des nombres réels, les “courbes” elliptiques utilisées en cryptographie ne sont pas à coordonnées réelles, mais à coordonnées entières. Plus précisément, tout comme pour l’algorithme de Diffie-Hellman classique, on travaille dans l’ensemble des entiers modulo p (\(\mathbb{Z}/p\mathbb{Z}\)), où p est un nombre premier.

Si on prend p=11 pour simplifier, la “courbe” d’équation \(y^2 = x^3 + 1\) contient 12 points: les 11 points bleus sur la figure suivante, ainsi que le point O (à l’infini) qui n’est pas représenté:

A noter que pour représenter un point de la courbe (autre que O), il suffit de connaître la coordonnée x et de savoir si y est pair ou impair (on parle de coordonnées compressées).

Pour calculer la somme de 2 points de la courbe, on utilise exactement la même méthode qu’avec les nombres réels, mais avec quelques subtilités:

• La “droite” passant par P et Q peut “faire le tour” du plan car on travaille modulo 11 et donc 11 est équivalent à 0 (l’espace est en fait la surface d’un tore)
• Pour calculer P + P, on fait comme si on travaillait avec des nombres réels pour calculer la pente de la “tangente” au point P (dans cet exemple un simple calcul de dérivée montre que la tangente a pour pente \(3x^2 / 2y\))

Si on part du point G de coordonnées (2, 3), on peut ainsi calculer les points 2G, 3G, etc:

Ici on trouve que 6G = O, et donc la boucle est bouclée (7G = G, 8G = 2G, etc.). Comme précédemment, on dit que G est d’ordre 6 car l’ensemble des multiples de G contient 6 éléments, et 6 est bien un diviseur de 12 (le nombre total de points sur la courbe). Rappelons que pour des raisons de sécurité on cherche un point G d’ordre premier, et donc il serait préférable d’utiliser le point 2G, qui est d’ordre 3 (évidemment dans cet exemple simplifié, ça ne fait pas une grande différence; dans la vraie vie on veut que l’ordre de G soit premier et très grand).

Il est maintenant temps de mettre fin au suspense et de découvrir l’ensemble utilisé dans l’algorithme X25519 ! Cet algorithme utilise la courbe elliptique d’équation:

\(y^2 = x^3 + 486662 x^2 + x\) (modulo p), où \(p = 2^{255} - 19\) (d’où le nom 25519 !)

Le générateur utilisé est le point G de coordonnées x=9 et y impair (y est un nombre à 77 chiffres !).

L’ordre de G est un nombre premier légèrement supérieur à \(2^{252}\), et donne le nombre de clés privées possibles. On dit que cet algorithme offre une protection de 128 bits car une attaque en force brute nécessiterait environ \(2^{128}\) essais pour retrouver k en connaissant kG. Par comparaison, l’algorithme de Diffie-Hellman classique nécessite une clé de 3072 bits pour obtenir un niveau de sécurité équivalent.

A ce jour l’algorithme X25519 offre un très bon compromis entre sécurité et rapidité, et couplé avec le chiffrement symétrique AES-256-GCM, est le pilier de la sécurité d’Internet.