Depuis l’intégration du chiffrement par courbes elliptiques à partir d’openSSH 5.7[1] (ECDSA), j’ai cherché à comprendre les mécanismes de base de cet échange de clés. Ceci est un (très) bref resumé des informations trouvées (voir biographie).
Recommandations
L’échange de clés Diffie-Hellman basé sur les courbes elliptiques (ECDH) est devenue la méthode recommandée pour le chiffrement asymétrique ces dernières années, notamment dans la “Suite B” publiée par la NSA en 2010[2], qui exclue totalement les protocoles basés sur le RSA ou le logarithme discret (DSA).
La NSA recommande l’utilisation de ECDH avec des clés de 256 bits ou 384 bits selon le niveau de confidentialité des informations. En France, l’ANSSI recommande une taille de clé d’au moins 256 bits pour l’ECDH[3]. Étant donné son fonctionnement, le protocole ECDH nécessite des clés de taille beaucoup plus réduite que ses prédécesseurs tout en assurant le même niveau de sécurité. Il est conseillé d’utiliser des clés de 256 bits pour ECDH lorsqu’il est couplé avec AES en 128 bits, tandis que RSA nécessite une clé de 3072 bits pour assurer une sécurité équivalente[4].
Protocole de l’échange de clés
En résumé, l’échange de clé se déroule de la façon suivante :
- Accord entre A et B sur les paramètres de la courbe et un point commun P choisi au hasard sur cette courbe.
- Génération de grands nombres aléatoires K par chacun des protagonistes. Ces nombres correspondent à leur clé privée.
- A envoie Qa à B. Qa est un point sur la courbe correspondant à la multiplication du point P par la clé privée Ka de A. Qa correspond à la clé publique de A.
- B envoie également sa clé publique Qb générée à partir de P et de sa clé privée privée Kb.
- A et B peuvent maintenant calculer le secret partagé (Ka.Kb).P à partir de Kb.(Qa) et Ka.(Qb).
- La clé utilisée pour le chiffrement proprement dit de la communication (avec AES par exemple) est générée à partir d’un hash du secret partagé.
Pour plus d’explication sur les mécanismes mathématiques en jeu dans cet échange, voir cette présentation.
Sécurité
Il est couramment admis que la sécurité de cet échange repose sur le fait qu’il est facile de calculer Qa et Qb à partir de P, Ka et Kb, mais qu’il est impossible de retrouver les clés privées K à partir des éléments publics P, Qa et Qb.
En effet, aucune méthode permettant de résoudre le logarithme discret sur la courbe elliptique (donc retrouver Ka à partir de Qa et P) n’est connue publiquement à ce jour.
Au premier abord, il est parait simple de retrouver K “à la main” puisque la multiplication scalaire est réalisée très rapidement par les deux protagonistes. Cependant, le calcul du point Q repose sur des optimisations qui permettent de réduire très fortement le nombre de points intermédiaires à calculer[5] (un peu à l’image de l’exponentiation rapide[6] pour les échanges de clé reposants sur le logarithme discret). Une recherche exhaustive de K à partir de Q et P implique un calcul de chaque point Q possible et donc un temps de calcul mettant hors de portée cette solution.
D’autres méthodes ont été trouvées pour accélérer ce calcul (Shanks’ Method, Baby-step giant-step[7], Pollard’s Rho[8][9]) avec une complexité O(√(n)). Un “challenge”[10] est d’ailleurs en cours pour casser ECDH à l’aide de ces outils et donne un bon aperçu du temps et des ressources nécessaires pour un challenge sur 131 bits (estimation : 2466 Playstation 3 utilisées pendant 1 an[11]).
En pratique
Pour mes clés SSH, j’ai donc tendance à favoriser d’abord des clés ECDSA, puis RSA de grande taille, et s’il y n’y a pas d’autre solution, une paire en DSA.
ECDSA n’a pas fait l’objet pour le moment d’attaque significative[12], mais n’est pas encore disponible sur toutes les distributions (notamment Fedora, qui exclut ECDSA conformément à sa licence, puisque le protocole est encore couvert par un brevet en cours de validité).
RSA est toujours fiable, à condition d’utiliser des clés de taille supérieure à 4096 bits. Le dernier record de factorisation a été établi en 2010 sur 768 bits[13] (temps de calcul estimé à 6 mois avec 10000 stations de travail[14]).
Quant à DSA, la dernière attaque portant sur le logarithme discret avec des clés standard date de 2005 et a atteint 613 bits[15] (avec 4*16 processeurs pendant 17 jours[16]).
Les spécifications actuelles de DSA empêchent son utilisation avec une clé de plus de 1024 bits, et même si cette taille peut être considérée comme sûre, elle ne permet pas une fiabilité à très long terme de ces clés.
Il est intéressant de noter que l’ANSSI a révoqué en 2010 un des certificats racine de l’État (qui avait été émis en 2007, de type DSA 1024 bits) et continue par ailleurs à utiliser des certificats RSA de 2048 et 4096 bits[17].
Dans la documentation publiée à partir d’avril 2013, l’ANSSI ne recommande d’ailleurs plus l’utilisation de clés DSA [18].
—
[1] : http://www.openssh.com/txt/release-5.7
[2] : http://www.keylength.com/
[3] : http://www.ssi.gouv.fr/IMG/pdf/RGS_B_1.pdf
[4] : http://www.nsa.gov/business/programs/elliptic_curve.shtml
[5] : https://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/fr//pubs/archive/37376.pdf – 3.3 Point multiplication with precomputation
[6] : https://en.wikipedia.org/wiki/Exponentiation_by_squaring
[7] : https://en.wikipedia.org/wiki/Counting_points_on_elliptic_curves#Baby-step_giant-step
[8] : http://math.ucalgary.ca/~mmusson/presentations/ECC09SummerSchool.pdf
[9] : http://www.ecc-challenge.info/anon.pdf
[10] : http://www.certicom.com/index.php/the-certicom-ecc-challenge
[11] : http://www.ecc-challenge.info/
[12] : https://en.wikipedia.org/wiki/Discrete_logarithm_records#Elliptic_curves
[13] : https://www.rsa.com/rsalabs/node.asp?id=3723
[14] : http://eprint.iacr.org/2010/006.pdf
[15] : https://en.wikipedia.org/wiki/Discrete_logarithm_records#Finite_fields
[16] : https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0509&L=NMBRTHRY&P=R1490&D=0&I=-3&T=0
[17] : http://www.legifrance.gouv.fr/affichTexte.do?cidTexte=JORFTEXT000022299271&dateTexte=&categorieLien=id
[18] : http://www.ssi.gouv.fr/fr/guides-et-bonnes-pratiques/recommandations-et-guides/securite-des-reseaux/recommandations-pour-un-usage-securise-d-open-ssh.html