Mon blog

Ce nouveau RFC est la description de deux courbes elliptiques largement utilisées mais qui n'avaient pas fait l'objet d'une description formelle complète : curve25519 et curve448. Maintenant que c'est fait, elles pourront être utilisées dans des normes Internet utilisant la cryptographie comme TLS ou DNSSEC.

La cryptographie sur les courbes elliptiques est une alternative aux algorithmes traditionnels fondés sur la décomposition en facteurs premiers, comme le classique RSA. Il est toujours bon de ne pas mettre tous ses œufs dans le même panier, car on ne sait jamais quelle sera la prochaine victime de la cryptanalyse (d'où le RFC 7696, sur l'importance de ne pas être prisonnier d'un seul algorithme). Grâce aux courbes elliptiques, si RSA est cassé complètement, on aura une solution de rechange. En outre, la cryptographie sur les courbes elliptiques a des propriétés intéressantes, comme des clés de taille plus petite. Dans les deux cas, RSA ou courbes elliptiques, je n'y connais pas grand'chose donc n'espérez pas des explications plus pointues.

Le schéma général de la cryptographie sur courbes elliptiques est décrit dans le RFC 6090 (voir aussi le cours « SEC 1: Elliptic Curve Cryptography »). Ce schéma permet l'utilisation d'une infinité de courbes elliptiques mais attention, toutes n'ont pas les propriétés requises. La plus connue est la courbe P-256 normalisée par le NIST. Comme il y a de très bonnes raisons de se méfier du NIST (leur rôle dans l'affaiblissement délibéré de Dual EC DRBG, cf. l'article de Schneier et celui de Greenemeier), et comme les raisons des choix des paramètres de P-256 n'ont jamais été rendues publiques, beaucoup de gens se méfient de P-256 (voir une bonne discussion sur StackExchange). Il est donc important, là encore, d'avoir plusieurs fers au feu, et de disposer d'autres courbes.

Les deux courbes décrites dans ce RFC sont curve25519 et curve448. Elles sont de la famille des courbes de Montgomery (et donc ont une équivalence avec une courbe d'Edwards).

Il n'est pas facile de faire des maths dans un RFC, avec leur format actuel. La section 3 décrit la notation utilisée dans le RFC, mais je ne vais pas reproduire les équations ici (je suis complètement ignorant de MathML et ce blog ne le gère pas). Des formules comme (section 4.1) :

     (u, v) = ((1+y)/(1-y), sqrt(-486664)*u/x)
     (x, y) = (sqrt(-486664)*u/v, (u-1)/(u+1))
    

sont nettement moins jolies dans le texte brut des RFC.

La section 4 du RFC décrit les deux courbes. Curve25519 doit son nom au fait qu'un des nombres premiers utilisés pour la génération des paramètres de la courbe est 2^255-19. Sa description originale est dans l'article de Bernstein « Curve25519 -- new Diffie-Hellman speed records », et son équivalent en courbe d'Edwards, ed25519 dans « High-speed high-security signatures ».

L'autre courbe, curve448, utilise le nombre premier 2^448-2^224-1. La courbe d'Edwards équivalente est nommée Goldilocks et est décrite dans « Ed448-Goldilocks, a new elliptic curve ».

La section 5 du RFC présente les fonctions X25519 et X448, utilisées pour faire du Diffie-Hellman avec ces courbes. Des vecteurs de test sont également fournis, si vous voulez vérifier votre implémentation (rappel au passage : il y a plein de pièges quand on programme de la crypto.)

En parlant de Diffie-Hellman, la section 6 est la description de l'utilisation de ces deux courbes pour un échange de clés ECDH, utilisant les deux fonctions de la section précédente.

Quelle est la sécurité de ces deux courbes (section 7) ? Le niveau de sécurité de curve25519 lors d'une attaque par force brute est d'un peu moins de 128 bits. Une attaque par force brute est normalement l'essai de toutes les clés possibles. Toutefois, le terme est souvent utilisé en cryptographie (avec un abus de langage) pour désigner des méthodes où on fait beaucoup d'essais, sans forcément tester toutes les clés (comme l'algorithme rho). D'autre part, le RFC rappelle qu'il n'est pas facile de comparer des algorithmes de cryptographie, surtout entre algorithmes symétriques et asymétriques, cf. l'article de Bernstein « Understanding brute force ».)

curve448 est normalement « meilleure », avec 224 bits de sécurité (mais plus lente : on n'a rien sans rien). Le RFC note que, pour des ordinateurs quantiques (si on en a un jour...), les deux courbes seront aussi faciles à casser l'une que l'autre. En attendant, curve25519 est parfaitement suffisant.

Notez que, si vous aimez la cryptographie quantique et les discussions sans fin, la NSA a publié en août 2015 un texte qui a stupéfié beaucoup de monde car il affirmait que, vu l'arrivée supposée proche des calculateurs quantiques, il n'était pas recommandé de faire des efforts pour migrer depuis RSA vers les courbes elliptiques. Certains en ont déduit que la NSA avait déjà des calculateurs quantiques et savaient donc que les courbes elliptiques étaient cassées ou proches de l'être, d'autres ont supposé que, si la NSA essayait de décourager les utilisateurs de se servir des courbes elliptiques, c'était au contraire une raison supplémentaire pour migrer vers ces courbes au plus vite. La polémique et l'état des informations disponibles sont très bien expliqués dans l'article « A riddle wrapped in an enigma ».

L'annexe A du RFC décrit comment les paramètres de ces deux courbes ont été générés. Des courbes comme la P-256 du NIST ou comme la courbe elliptique souveraine FRP256 de l'ANSSI ont été très critiquées car les différentes constantes utilisées sont juste annoncées, sans explication. Il n'y a pas besoin d'être excessivement paranoïaque, ou d'avoir lu les documents publiés par Snowden, pour se demander « Pourquoi ces valeurs plutôt que d'autres ? Ne serait-ce pas parce que ces constantes ont des propriétés qui facilitent leur décryptage par la NSA ou un organisme similaire ? ». Il y a consensus aujourd'hui pour dire qu'on ne doit utiliser que des courbes pour lesquelles le choix des paramètres a été fait « objectivement », selon une méthodologie expliquée et vérifiable. C'est ce que fait l'annexe A.

Notez que les paramètres des deux courbes de ces RFC n'ont pas été choisis complètement « objectivement ». Ils ont fait l'objet d'« optimisations », notamment pour des raisons de performance. Si on veut une courbe générée entièrement par un algorithme objectif et publiquement vérifiable, il faudra se tourner (elle est très récente) vers des courbes « publiquement vérifiables » comme la « courbe d'un million de dollars », qui proclame être « a procedure, more than a curve ».

Maintenant que ces courbes font l'objet d'une documentation complète, il sera plus facile de les utiliser depuis un protocole IETF (ceci dit, elles sont déjà dans au moins une norme, voir RFC 7479). Plusieurs travaux sont en cours pour cela ; il y avait un Internet-Draft pour permettre curve25519 dans TLS, draft-ietf-tls-curve25519 mais il a été remplacé par le plus général RFC 8422. Un autre Internet-Draft traite le cas de DNSSEC, draft-sury-dnskey-ed25519.

Notez que les deux courbes de ce RFC sont décrites selon un formalisme qui ne permet pas de les utiliser telles quelles dans un algorithme comme ECDSA (explications sur StackOverflow). Mais on peut avec EdDSA.

OpenSSH dispose de curve25519 depuis la version 6.5. (« Add support for key exchange using elliptic-curve Diffie Hellman in Daniel Bernstein's Curve25519. This key exchange method is the default when both the client and server support it. [...] Add support for Ed25519 as a public key type. Ed25519 is a elliptic curve signature scheme that offers better security than ECDSA and DSA and good performance. It may be used for both user and host keys. »). Dans les sources d'OpenSSH, ce sont les fichiers ayant 25519 dans leur nom :

/tmp/openssh-7.1p2 %   ls *25519*
ed25519.c  fe25519.c  fe25519.h  ge25519_base.data  ge25519.c  ge25519.h  kexc25519.c  kexc25519c.c  kexc25519s.c  sc25519.c  sc25519.h  smult_curve25519_ref.c  ssh-ed25519.c

Pour générer des clés utilisant cette courbe, on utilise le classique ssh-keygen :

% ssh-keygen -t ed25519
Generating public/private ed25519 key pair.
...
Your identification has been saved in /home/stephane/.ssh/id_ed25519.
Your public key has been saved in /home/stephane/.ssh/id_ed25519.pub.
...      
    

Par contre, ces courbes ne sont pas encore dans OpenSSL (voir la discussion #309). Autrement, on trouve des mises en œuvre de curve25519 à plein d'endroits : https://github.com/msotoodeh/curve25519, https://code.google.com/p/curve25519-donna/ et bien sûr http://cr.yp.to/ecdh.html et https://nacl.cr.yp.to/.

Merci à Patrick Mevzek pour son exploration d'OpenSSH et OpenSSL, à Émilien Gaspar pour les discussions et à Manuel Pégourié-Gonnard pour des corrections, notamment sur la force brute.