Méthode d'accord de clé Diffie-Hellman

Statut du présent mémoire

Le présent document spécifie un protocole de normalisation Internet pour la communauté Internet, et appelle à discussion et suggestions en vue de son amélioration. Prière de se reporter à l’édition en cours des "Internet Official Protocol Standards" (normes officielles du protocole Internet) (STD 1) pour connaître l’état de la normalisation et le statut du présent protocole. La distribution du présent mémo n’est pas soumise à restrictions.

Notice de copyright

Copyright (C) The Internet Society (1999). Tous droits réservés

Résumé

Le présent document normalise une variante Diffie-Hellman particulière, fondée sur le projet ANSI X9.42, développé par le groupe de travail ANSI X9F1. Diffie-Hellman est un algorithme d'accord de clés utilisé par deux parties pour se mettre d'accord sur un secret partagé. Un algorithme pour convertir le secret partagé en une quantité arbitraire de matériel de clés est fourni. Le matériel de clés résultant est utilisé comme clé de chiffrement symétrique. La variante Diffie-Hellman décrite exige que le receveur ait un certificat, mais le générateur peut avoir une paire de clés statiques (la clé publique étant placée dans un certificat) ou une paire de clés éphémères.

Table des matières

1.1   Exigences de terminologie

2.1   Accord de clés

2.1.1   Génération de ZZ

2.1.2   Génération du matériel de clé

2.1.3   Calcul de la KEK

2.1.4   Longueurs de clé pour les algorithmes courants

2.1.5   Validation de clé publique

2.1.6   Exemple 1

2.1.7   Exemple 2

2.2   Exigences de clé et de paramètres

2.2.1   Génération de paramètres de groupe

2.2.2   Validation de paramètre de groupe

2.3   Mode éphémère-statique

2.4   Mode statique-statique

1.   Introduction

Dans [DH76] Diffie et Hellman décrivent un moyen pour que deux parties se mettent d'accord sur un secret partagé d'une façon telle que le secret soit indivulgables aux espions. Ce secret peut alors être converti en matériel de clés cryptographiques pour d'autres algorithmes (symétriques). Il existe un grand nombre de variantes mineures de ce processus. Le présent document décrit une de ces variantes, fondée sur la spécification ANSI X9.42.

1.1   Exigences de terminologie

Les mots clés "DOIT", "NE DOIT PAS", "EXIGE", "DEVRA", "NE DEVRA PAS", "DEVRAIT", "NE DEVRAIT PAS", "RECOMMANDE", "PEUT", et "FACULTATIF" dans le présent document sont à interpréter comme décrit dans la RFC 2119 [RFC2119].

2.   Généralités sur la méthode

L'accord de clés Diffie-Hellman exige que l'envoyeur et le receveur d'un message aient tous deux une paire de clés. En combinant la clé privée de l'un et la clé publique de l'autre partie, les deux parties peuvent calculer le même numéro secret partagé. Ce numéro peut alors être converti en matériel de clés cryptographiques. Ce matériel de clés est normalement utilisé comme clé de chiffrement de clé (KEK, key-encryption key) pour crypter (couvrir) une clé de chiffrement du contenu (CEK, content-encryption key) qui à son tour est utilisée pour chiffrer les données du message.

2.1   Accord de clés

Le premier stade du processus d'accord de clé est de calculer un numéro secret partagé, appelé ZZ. Lorsque sont utilisées les mêmes paires de clés publique/privée du générateur et du receveur, il va résulter la même valeur ZZ. La valeur ZZ est alors convertie en une clé cryptographique symétrique partagée. Lorsque le générateur emploie une paire statique de clés privée/publique, l'introduction d'une valeur aléatoire publique assure que la clé symétrique résultante sera différente pour chaque accord de clé.

2.1.1   Génération de ZZ

X9.42 définit que le secret partagé ZZ est généré comme suit :

ZZ = g ^ (xb * xa) mod p

Noter que les parties individuelles effectuent en fait les calculs :

ZZ = (yb ^ xa) mod p = (ya ^ xb) mod p

où ^ note l'exponentiation

ya est la clé publique de la partie a ; ya = g ^ xa mod p

yb est la clé publique de la partie b ; yb = g ^ xb mod p

xa est la clé privée de la partie a

xb est la clé privée de la partie b

p est un grand nombre premier

q est un grand nombre premier

g = h^{(p-1)/q} mod p, où

h est tout entier avec 1 < h < p-1 tel que h{(p-1)/q} mod p > 1 (g est d'ordre q mod p ; c'est-à-dire. g^q mod p = 1 si g!=1)

j est un grand entier tel que p = qj + 1 (Voir au paragraphe 2.2 les critères des clés et des paramètres)

Dans [CMS], le receveur de clés est identifié par le RecipientIdentifier CMS, qui pointe sur le certificat du receveur. La clé publique de l'envoyeur est identifiée en utilisant le champ OriginatorIdentifierOrKey, soit par référence au certificat de l'envoyeur, soit par inclusion en ligne d'une clé publique.

2.1.2   Génération du matériel de clé

X9.42 fournit un algorithme permettant de générer une quantité arbitraire de matériel de clés à partir de ZZ. Notre algorithme est dérivé de cet algorithme en rendant certains champs facultatifs obligatoires et en omettant certains autres.

KM = H ( ZZ || OtherInfo)

H est la fonction de résumé de message de SHA-1 [FIPS-180] ZZ est la valeur du secret partagé calculée au paragraphe 2.1.1. Les zéros en tête DOIVENT être préservés, de façon que ZZ occupe autant d'octets que p. Par exemple, si p est de 1024 bits, ZZ devrait avoir 128 octets de long. OtherInfo est le codage en DER de la structure suivante :

OtherInfo ::= SEQUENCE {

keyInfo KeySpecificInfo,

partyAInfo [0] OCTET STRING OPTIONAL,

suppPubInfo [2] OCTET STRING

}

KeySpecificInfo ::= SEQUENCE {

algorithm OBJECT IDENTIFIER,

counter OCTET STRING SIZE (4..4) }

Noter que ces définitions ASN.1 utilisent des étiquettes EXPLICITES. (En ASN.1, l'étiquetage EXPLICITE est implicite sauf si IMPLICITE est explicitement spécifié.)

algorithm est l'identifiant d'objet (OID) de l'algorithme ASN.1 de l'algorithme d'enveloppement de la CEK avec laquelle cette KEK sera utilisée. Noter que ce N'EST PAS un AlgorithmIdentifier, mais simplement l'OBJECT IDENTIFIER. Aucun paramètre n'est utilisé.

counter est un nombre de 32 bits, représenté dans l'ordre des octets du réseau. Sa valeur initiale est de 1 pour tout ZZ, c'est-à-dire la séquence d'octets 00 00 00 01 (hex), et elle est incrémentée de un chaque fois que la fonction de génération de clé ci-dessus fonctionne pour une KEK donnée.

partyAInfo est une chaîne aléatoire fournie par l'envoyeur. En CMS, elle est fournie comme paramètre dans le champ UserKeyingMaterial (codée comme OCTET STRING). S'il est fourni, partyAInfo DOIT contenir 512 bits.

suppPubInfo est la longueur de la KEK générée, en bits, représentée comme un nombre de 32 bits dans l'ordre des octets du réseau. Par exemple, pour 3DES, ce serait la séquence d'octets 00 00 00 C0.

Pour générer une KEK, on génère un ou plusieurs blocs KM (en incrémentant le compteur de façon appropriée) jusqu'à ce que suffisamment de matériel ait été généré. Les blocs KM sont concaténés de gauche à droite, c'est à dire, KM(compteur=1) || KM(compteur=2)...

Noter que la seule source d'aléa secrète dans le calcul est ZZ. Même si une chaîne plus longue que ZZ est générée, l'espace de clé effectif de la KEK est limité par la taille de ZZ, en plus de toutes considérations de niveau de sécurité imposées par les paramètres p et q. Cependant, si partyAInfo est différent pour chaque message, une KEK différente sera générée pour chaque message. Noter que partyAInfo DOIT être utilisé en mode statique-statique, mais PEUT apparaître en mode éphémère-statique.

2.1.3   Calcul de la KEK

Chaque algorithme de chiffrement de clé requiert une clé de taille spécifique (n). La KEK est générée en transposant les n octets de plus fort poids de KM dans la clé. Pour 3DES, qui exige 192 bits de matériel de clé, l'algorithme doit tourner deux fois, une fois avec une valeur de compteur de 1 (pour générer K1', K2', et les 32 premiers bits de K3') et une fois avec une valeur de compteur de 2 (pour générer les 32 derniers bits de K3). K1', K2' et K3' sont alors ajustés en parité pour générer les trois clés DES K1, K2 et K3. Pour RC2-128, qui requiert 128 bits de matériel de clé, l'algorithme fonctionne une fois, avec une valeur de compteur de 1, et les 128 bits de plus fort poids sont directement convertis en une clé RC2. De façon similaire, pour RC2-40, qui requiert 40 bits de matériel de clé, l'algorithme tourne une fois, avec une valeur de compteur de 1, et les 40 bits de plus fort poids sont utilisés comme clé.

2.1.4   Longueurs de clé pour les algorithmes courants

Certains algorithmes de chiffrement de clé courants ont des KEK des longueurs suivantes.

3DES à 3 clés   192 bits

RC2-128   128 bits

RC2-40   40 bits

Les longueurs de clé effectives de RC2 sont égales aux longueurs des clés réelles de RC2.

2.1.5   Validation de clé publique

L'algorithme suivant PEUT être utilisé pour valider une clé publique y reçue.

1.   Vérifier que y est dans l'intervalle [2, p-1]. S'il ne l'est pas, la clé est invalide.

2.   Calculer y^q mod p. Si le résultat == 1, la clé est valide. Autrement, la clé est invalide.

Le principal objet de la validation de clé publique est de prévenir des attaques de petit sous-groupe [LAW98] sur la paire de clés de l'envoyeur. Si le mode éphémère-statique est utilisé, cette vérification peut n'être pas nécessaire. Voir aussi [P1363] pour des informations complémentaires sur la validation de clé publique.

Noter que cette procédure peut être soumise à des brevets en cours.

2.1.6   Exemple 1

ZZ est constitué des 20 octets 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13

L'algorithme d'enveloppe de clé est le 3DES-EDE.

Aucune partyAInfo n'est utilisée.

Par conséquent, l'entrée à la première invocation de SHA-1 est :

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 ; ZZ

30 1d

   30 13

   06 0b 2a 86 48 86 f7 0d 01 09 10 03 06   ; OID d'enveloppe 3DES

   04 04

   00 00 00 01   ; Compteur

   a2 06

   04 04

   00 00 00 c0   ; longueur de clé

Et le résultat se compose des vingt octets : a0 96 61 39 23 76 f7 04 4d 90 52 a3 97 88 32 46 b6 7f 5f 1e

L'entrée à la seconde invocation de SHA-1 est :

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 ; ZZ

30 1d

30 13

06 0b 2a 86 48 86 f7 0d 01 09 10 03 06   ; OID d'enveloppe 3DES

04 04

00 00 00 02   ; Compteur

a2 06

04 04

00 00 00 c0   ; longueur de clé

Et le résultat sont les 20 octets : f6 3e b5 fb 5f 56 d9 b6 a8 34 03 91 c2 d3 45 34 93 2e 11 30

Par conséquent,

K1' = a0 96 61 39 23 76 f7 04

K2' = 4d 90 52 a3 97 88 32 46

K3' = b6 7f 5f 1e f6 3e b5 fb

Note : La parité de ces clés n'a pas été ajustée.

2.1.7   Exemple 2

ZZ sont les 20 octets 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13

L'algorithme d'enveloppe de clé est l'enveloppe de clé RC2-128, et on a donc besoin de 128 bits (16 octets) de matériel de clé.

Le partyAInfo utilisé sont les 64 octets    01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01

01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01

01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01

01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01

Par conséquent, l'entrée pour SHA-1 est :

00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 ; ZZ

30 61

30 13

06 0b 2a 86 48 86 f7 0d 01 09 10 03 07   ; OID d'enveloppe RC2

04 04

00 00 00 01   ; Compteur

a0 42

04 40

01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01   ; partyAInfo

01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01

01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01

01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01

a2 06

04 04

00 00 00 80   ; longueur de clé

Et le résultat sont les 20 octets : 48 95 0c 46 e0 53 00 75 40 3c ce 72 88 96 04 e0 3e 7b 5d e9

Par conséquent,

K = 48 95 0c 46 e0 53 00 75 40 3c ce 72 88 96 04 e0

2.2   Exigences de clé et de paramètres

X9.42 exige que les paramètres de groupe soient de la forme p = jq + 1 où q est grand nombre premier de longueur m et j ≥ 2. Un algorithme pour générer des nombres premiers de cette forme (dérivé des algorithmes de FIPS PUB 186-1[FIPS-186] et [X942]se trouve dans l'appendice A.

X9.42 exige que la clé privée x soit dans l'intervalle [2, (q - 2)]. x devrait être généré de façon aléatoire dans cet intervalle. y est alors calculé à l'aide de g^x mod p. Pour ce conformer au présent mémoire, m DOIT être ≥ 160 bits, (par conséquent, q DOIT être au moins long de 160 bits). Lorsqu'on doit utiliser des chiffrements symétriques plus forts que DES, un m plus grand est conseillé. p doit au minimum avoir 512 bits de long.

2.2.1   Génération de paramètres de groupe

Les agents DEVRAIENT générer des paramètres de domaine (g, p, q) en utilisant l'algorithme suivant, dérivé de [FIPS-186] et [X942]. Lorsque cet algorithme est utilisé, on peut vérifier que la procédure de génération est correcte par une troisième partie de l'algorithme du paragraphe 2.2.2.

2.2.1.1   Génération de p, q

Cet algorithme génère une paire p, q où q est de longueur m et p est de longueur L.

1.   Régler m' = m/160 où / représente la division entière avec arrondi à la valeur supérieure. C'est à dire 200/160 = 2.

2.   Régler L'= L/160

3.   Régler N'= L/1024

4.   Choisir une chaîne binaire arbitraire GERME telle que la longueur de GERME ≥ m

5.   Régler U = 0

6.   Pour i = 0 à m' - 1

U = U + (SHA1[GERME + i] OUX SHA1[(GERME + m' + i)) * 2^(160 * i)

Noter que pour m = 160, cela se réduit à l'algorithme de [FIPS-186]

U = SHA1[GERME] OUX SHA1[(GERME+1) mod 2^160 ].

5.   Former q à partir de U en calculant U mod (2^m) et en réglant le bit de plus fort poids (le bit 2^(m-1)) et le bit de moindre poids à 1. En termes d'opérations booléennes, q = U OU 2^(m-1) OU 1. Noter que 2^(m-1) < q < 2^m

6.   Utiliser un algorithme de nombre premier robuste pour vérifier si q est premier.

7.   Si q n'est pas premier, passer alors à 4.

8.   Régler compteur = 0

9.   Régler R = germe + 2*m' + (L' * compteur)

10.   Régler V = 0

12.   Pour i = 0 à L'-1 faire V = V + SHA1(R + i) * 2^(160 * i)

13.   Régler W = V mod 2^L

14.   Régler X = W OR 2^(L-1)

Noter que 0 ≤ W < 2^(L-1) et donc X ≥ 2^(L-1)

15.   Régler p = X - (X mod (2*q)) + 1

16.   Si p > 2^(L-1) utiliser un essai de nombre premier robuste pour vérifier que p est premier. Autrement, aller à 18.

17.   Si p est premier sortir p, q, germe, compteur et arrêter.

18.   Régler compteur = compteur + 1

19.   Si compteur < (4096 * N) passer alors à 8.

20.   Sortir "échec"

Note : Un essai robuste de nombre premier est celui où la probabilité qu'un nombre non premier réussisse l'essai est d'au plus 2^-80. [FIPS-186] fournit un algorithme convenable, ainsi que [X942].

2.2.1.2   Génération de g

Ce paragraphe donne un algorithme (dérivé de [FIPS-186]) pour générer g.

1.   Soit j = (p - 1)/q.

2.   Régler h = tout entier, où 1 < h < p - 1 et h diffère de toute valeur essayée précédemment.

3.   Régler g = h^j mod p

4.   Si g = 1 aller à l'étape 2

2.2.2   Validation de paramètre de groupe

L'ASN.1 pour les clés DH dans [PKIX] inclut des éléments j et des paramètres de validation qui PEUVENT être utilisés par le receveur d'une clé pour vérifier que les paramètres de groupe ont été générés correctement. Deux vérifications sont possibles :

1.   Vérifier que p = qj + 1. Cela démontre que les paramètres satisfont au critère de paramètre de X9.42.

2.   Vérifier que lorsque la procédure de génération de p,q de l'Appendice 2 de [FIPS-186] est suivie avec le germe 'germe', p est trouvé lorsque 'compteur' = pgenCounter.

Cela démontre que les paramètres ont été choisis de façon aléatoire et n'ont pas une forme particulière.

La fourniture des informations de validation dans leurs certificats par les agents est une affaire local entre agents et CA.

2.3   Mode éphémère-statique

Dans le mode éphémère-statique, le receveur a une paire de clés statique (et certifiée) amis l'envoyeur génère une nouvelle paire de clés pour chaque message et l'envoie en utilisant la production originatorKey. Si la clé de l'envoyeur est fraîchement générée pour chaque message, le secret partagé ZZ sera différent de façon similaire pour chaque message et partyAInfo PEUT être omis, car il sert simplement à découpler plusieurs KEK générées par le même ensemble de clés appariées. Si cependant, la même clé éphémère d'envoyeur est utilisée pour plusieurs messages (par exemple, elle est mise en mémoire cache au titre de l'optimisation des performances) un partyAInfo distinct DOIT être utilisé pour chaque message. Toutes les mises en œuvre de la présente norme DOIVENT mettre en œuvre le mode éphémère-statique.

Afin de résister aux attaques de petit sous-groupe, le receveur devrait effectuer la vérification décrite au paragraphe 2.1.5. Si un adversaire ne peut pas déterminer le succès ou l'échec d'une opération de déchiffrement du receveur, le receveur PEUT choisir d'omettre cette vérification. Voir aussi dans [LL97] une méthode de génération de clés qui n'est pas soumise à l'attaque de petit sous-groupe.

2.4   Mode statique-statique

Dans le mode statique-statique, l'envoyeur et le receveur ont tous deux une paire de clés statique (et certifiée). Comme les clés de l'envoyeur et du receveur sont donc les mêmes pour chaque message, ZZ sera le même pour chaque message. Et donc, partyAInfo DOIT être utilisé (et être différent pour chaque message) afin de s'assurer que des messages différents utilisent des KEK différentes. Les mises en œuvre PEUVENT mettre en œuvre le mode statique-statique.

Afin d'empêcher les attaques de petit groupe, le générateur et le receveur DEVRAIENT tous deux effectuer soit l'étape de validation décrit au paragraphe 2.1.5, soit vérifier que le CA a correctement vérifié la validité de la clé. Voir aussi dans [LL97] une méthode de génération de clés qui n'est pas sujette à l'attaque de petit groupe.

Remerciements

La méthode d'accord de clé décrite dans le présent document se fonde sur des travaux effectués par le groupe de travail ANSI X9F1. L'auteur tient à les remercier pour leur assistance.

L'auteur tient aussi à remercier Stephen Henson, Paul Hoffman, Russ Housley, Burt Kaliski, Brian Korver, John Linn, Jim Schaad, Mark Schertler, Peter Yee, et Robert Zuccherato pour leurs avis éclairés et leur relecture.

Références

[CMS]   R. Housley, "Syntaxe de message cryptographique", RFC 2630, juin 1999.

[FIPS-46-1]   Federal Information Processing Standards Publication (FIPS PUB) 46-1, Data Encryption Standard, Reaffirmed 1988 January 22 (supersedes FIPS PUB 46, 15 janvier 1977).

[FIPS-81]   Federal Information Processing Standards Publication (FIPS PUB) 81, DES Modes of Operation, 2 décembre 1980.

[FIPS-180]   Federal Information Processing Standards Publication (FIPS PUB) 180-1, "Secure Hash Standard", 17 avril 1995.

[FIPS-186]   Federal Information Processing Standards Publication (FIPS PUB) 186, "Digital Signature Standard", 19 mai 1994.

[P1363]   "Standard Specifications for Public Key Cryptography", IEEE P1363 working group draft, 1998, Annex D.

[PKIX]   R. Housley, W. Ford, W. Polk et D. Solo, "Internet X.509 Public Key Infrastructure Certificate and CRL Profile", RFC 2459, janvier 1999.

[LAW98]   L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone, "An efficient protocol for authenticated key agreement", Technical report CORR 98-05, University of Waterloo, 1998.

[LL97]   C.H. Lim and P.J. Lee, "A key recovery attack on discrete log-based schemes using a prime order subgroup", B.S. Kaliski, Jr., editor, Advances in Cryptology - Crypto '97, Lecture Notes in Computer Science, vol. 1295, 1997, Springer-Verlag, pp. 249-263.

[RFC2119]   S. Bradner, "Mots clés à utiliser dans les RFC pour indiquer les niveaux d'exigence", BCP 14, RFC 2119, mars 1997.

[X942]   "Agreement Of Symmetric Keys Using Diffie-Hellman and MQV Algorithms", ANSI draft, 1998.

Considérations pour la sécurité

Toute la sécurité de ce système est fournie par le secret du matériel de clé privée. Si les clés privées de l'envoyeur ou du receveur sont divulguées, tous les messages envoyés ou reçus en utilisant cette clé sont compromis. De même, la perte de la clé privée résulte en l'incapacité de lire les messages envoyés en utilisant cette clé.

Les clés statiques Diffie-Hellman sont vulnérables aux attaques de petit sous-groupe [LAW98]. En pratique, ce problème survient des deux côtés en mode statique-statique et pour le receveur durant le mode éphémère-statique. Les paragraphes 2.3 et 2.4 décrivent les pratiques appropriées pour se protéger contre cette attaque. Autrement, il est possible de générer des clés de telle façon qu'elles soient résistantes à cette attaque. Voir [LL97]

Le niveau de sécurité fourni par ces méthodes dépend de plusieurs facteurs. Il dépend de la longueur de la clé symétrique (normalement, un niveau de sécurité 2^l si la longueur est de l bit) de la taille du nombre premier q (un niveau de sécurité 2^{m/2}) et de la taille du nombre premier p (où le niveau de sécurité croît comme une fonction sous exponentielle de la taille en bits). Un bon principe de conception est d'avoir un système équilibré, où les trois niveaux de sécurité sont approximativement les mêmes. Si beaucoup de clés sont dérivées d'une paire donnée de nombres premiers p et q, il peut être prudent d'avoir de plus hauts niveaux pour les nombres premiers. Dans tous les cas, la sécurité globale est limitée au plus faible des trois niveaux.

Adresse de l'auteur

Eric Rescorla

RTFM Inc.

30 Newell Road, #16

East Palo Alto, CA 94303

mél : ekr@rtfm.com

Déclaration de copyright

Remerciement

Le financement de la fonction d’édition des RFC est actuellement fourni par Internet Society.