1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
Titre: RFC 8032: Edwards-curve Digital Signature Algorithm (EdDSA)
Auteur:
Date: Wed 25 Jan 2017 01:00:00 +0100
Lien: https://www.bortzmeyer.org/8032.html
Ce RFC est la description IETF de l'algorithme de signature cryptographique
EdDSA. EdDSA est en fait une famille, il prend un certain nombre de paramètres,
comme la courbe elliptique Edwards utilisée et ce RFC décrit son utilisation
avec les courbes Edwards25519 et Edwards448.
EdDSA n'avait apparemment été décrit auparavant que dans des publications
scientifiques, ce RFC sert à la fois à avoir une référence IETF, et également à
décrire EdDSA dans des termes plus familiers aux programmeurs. Pourquoi faire
de l'EdDSA, d'ailleurs ? Parce que cet algorithme (ou plutôt cette famille
d'algorithmes) a plusieurs avantages, notamment :
* Rapide,
* Ne nécessite pas un nombre aléatoire différent par signature (un problème
qui a souvent frappé les mises en œuvres de DSA, par exemple avec la Sony
Playstation[1]),
* Clés et signatures de taille réduite.
Un site Web sur EdDSA[2] a été créé par ses auteurs. La référence officielle
d'EdDSA est l'article « High-speed high-security signatures[3] » de D.
Bernstein, N. Duif, T. Lange, P. Schwabe, P., et B. Yang. Une extension à
d'autres courbes est décrite dans « EdDSA for more curves[4] ». Sur les courbes
elles-mêmes, on peut consulter le RFC 7748.
La section 3 du RFC décrit l'algorithme générique d'EdDSA. Comme il laisse
ouvert pas moins de onze paramètres, on voit qu'on peut créer une vaste famille
d'algorithmes se réclamant d'EdDSA. Mais, évidemment, toutes les combinaisons
possibles pour ces onze paramètres ne sont pas sérieuses du point de vue de la
sécurité cryptographique, et notre RFC ne décrira que cinq algorithmes
spécifiques, dont ed25519 et ed448. L'algorithme générique est surtout utile
pour la culture générale.
C'est parce que EdDSA est un algorithme générique (au contraire de ECDSA) que
les programmes qui l'utilisent ne donnent pas son nom mais celui de
l'algorithme spécifique. Ainsi, OpenSSH vous permet de générer des clés Ed25519
(ssh-keygen -t ed25519) mais pas de clés EdDSA (ce qui ne voudrait rien dire).
La section 4 du RFC décrit en détail un des paramètres importants de EdDSA : le
choix de la fonction prehash. Celle-ci peut être l'identité (on parle alors de
Pure EdDSA) ou bien une fonction de condensation cryptographique (on parle
alors de Hash EdDSA).
La section 5, elle, spécifie EdDSA avec les autres paramètres, décrivant
notamment Ed25519 et Ed448. Ainsi, Ed25519 est EdDSA avec la courbe
Edwards25519, et une fonction prehash qui est l'identité. (Pour les autres
paramètres, voir le RFC.) L'algorithme Ed25519ph est presque identique sauf que
sa fonction prehash est SHA-512.
Comme tout algorithme de cryptographie, il faut évidemment beaucoup de soin
quand on le programme. La section 8 du RFC contient de nombreux avertissements
indispensables pour le programmeur. Un exemple typique est la qualité du
générateur aléatoire. EdDSA n'utilise pas un nombre aléatoire par signature (la
plaie de DSA), et est déterministe. La sécurité de la signature ne dépend donc
pas d'un bon ou d'un mauvais générateur aléatoire. (Rappelons qu'il est très
difficile de faire un bon générateur aléatoire, et que beaucoup de programmes
de cryptographie ont eu des failles de sécurité sérieuses à cause d'un mauvais
générateur.) Par contre, la génération des clés, elle, dépend de la qualité du
générateur aléatoire (RFC 4086).
Il existe désormais pas mal de mises en œuvre d'EdDSA, par exemple dans OpenSSH
cité plus haut. Sinon, les annexes A et B du RFC contiennent une mise en œuvre
en Python d'EdDSA. Attention, elle est conçue pour illustrer l'algorithme, pas
forcément pour être utilisée en production. Par exemple, elle n'offre aucune
protection contre les attaques exploitant la différence de temps de calcul
selon les valeurs de la clé privée (cf. la section 8.1). J'ai extrait ces deux
fichiers, la bibliothèque eddsalib.py[5] et le programme de test eddsa-test.py[6]
(ils nécessitent Python 3). Le programme de test prend comme entrée un fichier
composé de plusieurs vecteurs de test, chacun comprenant quatre champs, séparés
par des deux-points, clé secrète, clé publique, message et signature. La
section 7 du RFC contient des vecteurs de test pour de nombreux cas. Par
exemple, le test 2 de la section 7.1 du RFC s'écrit
4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb:3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c:72:92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00
et l'exécution du programme de test affiche juste le numéro de ligne quand tout
va bien :
% python3 eddsa-test.py <> vector2.txt
1
On peut aussi utiliser des tests plus détaillés comme ce fichier de vecteurs de
test[7] :
% python3 eddsa-test.py <> sign.input
1
2
3
...
1024
Si on change le message, la signature ne correspond évidemment plus et le
programme de test indique une assertion erronée :
% python3 eddsa-test.py <> vector2-modified.txt
1
Traceback (most recent call last):
File "eddsa-test.py", line 30, in <>module>
assert signature == Ed25519.sign(privkey, pubkey, msg)
AssertionError
Liens:
[1]: http://arstechnica.com/gaming/2010/12/ps3-hacked-through-poor-implementation-of-cryptography/ (lien)
[2]: http://ed25519.cr.yp.to/ (lien)
[3]: http://ed25519.cr.yp.to/ed25519-20110926.pdf (lien)
[4]: http://ed25519.cr.yp.to/eddsa-20150704.pdf (lien)
[5]: http://www.bortzmeyer.org/files/eddsalib.py (lien)
[6]: http://www.bortzmeyer.org/files/eddsa-test.py (lien)
[7]: http://ed25519.cr.yp.to/python/sign.input (lien)
|