3. DSA et ECDSA déterministes

(EC)DSA déterministe est le processus de génération d'une signature (EC)DSA sur un message d'entrée m en utilisant le processus standard de génération de signature (EC)DSA (discuté dans la section précédente), sauf que la valeur k, au lieu d'être générée aléatoirement, est obtenue par le processus décrit dans cette section.

Nous utilisons les notations décrites dans la section 2.

3.1. Blocs de construction

3.1.1. HMAC

HMAC [RFC2104] est une construction d'un code d'authentification de message utilisant une fonction de hachage et une clé secrète. Ici, nous utilisons HMAC avec la même fonction de hachage H que celle utilisée pour traiter le message d'entrée avant la génération ou la vérification de signature.

Nous désignons le processus d'application de HMAC avec la clé K sur les données V par:

HMAC_K(V)

qui retourne une séquence de bits de longueur hlen (la longueur de sortie de la fonction de hachage sous-jacente H).

3.2. Génération de k

Étant donné le message d'entrée m, le processus suivant est appliqué:

a. Traiter m par la fonction de hachage H, produisant:

h1 = H(m)

(h1 est une séquence de hlen bits).

b. Définir:

V = 0x01 0x01 0x01 ... 0x01

de sorte que la longueur de V, en bits, soit égale à 8*ceil(hlen/8). Par exemple, sur un système basé sur les octets, si H est SHA-256, alors V est défini comme une séquence de 32 octets de valeur 1. Notez que dans cette étape et toutes les étapes suivantes, nous utilisons la même fonction H que celle utilisée à l'étape 'a' pour traiter le message d'entrée; ce choix sera discuté plus en détail dans la section 3.6.

c. Définir:

K = 0x00 0x00 0x00 ... 0x00

de sorte que la longueur de K, en bits, soit égale à 8*ceil(hlen/8).

d. Définir:

K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))

où '||' désigne la concaténation. En d'autres termes, nous calculons HMAC avec la clé K, sur la concaténation des éléments suivants, dans l'ordre: la valeur actuelle de V, une séquence de huit bits de valeur 0, l'encodage de la clé privée (EC)DSA x, et le message haché (éventuellement tronqué et étendu comme spécifié par la transformation bits2octets). Le résultat HMAC est la nouvelle valeur de K. Notez que la clé privée x est dans la plage [1, q-1], donc une entrée appropriée pour int2octets, produisant rlen bits de sortie, c'est-à-dire un nombre intégral d'octets (rlen est un multiple de 8).

e. Définir:

V = HMAC_K(V)

f. Définir:

K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))

Notez que "l'octet interne" est 0x01 cette fois.

g. Définir:

V = HMAC_K(V)

h. Appliquer l'algorithme suivant jusqu'à ce qu'une valeur appropriée soit trouvée pour k:

Définir T comme la séquence vide. La longueur de T (en bits) est désignée tlen; ainsi, à ce point, tlen = 0.
Tant que tlen < qlen, faire ce qui suit:

V = HMAC_K(V)

T = T || V
Calculer:

k = bits2int(T)

Si cette valeur de k est dans la plage [1,q-1], et est appropriée pour DSA ou ECDSA (c'est-à-dire qu'elle résulte en une valeur r qui n'est pas 0; voir la section 3.4), alors la génération de k est terminée. La valeur obtenue de k est utilisée dans DSA ou ECDSA. Sinon, calculer:

K = HMAC_K(V || 0x00)

V = HMAC_K(V)

et boucler (essayer de générer un nouveau T, et ainsi de suite).

Veuillez noter que lorsque k est généré à partir de T, le résultat de bits2int est comparé à q, pas réduit modulo q. Si la valeur n'est pas entre 1 et q-1, le processus boucle. Effectuer une simple réduction modulaire induirait des biais qui seraient préjudiciables à la sécurité de la signature.

3.3. Description alternative de la génération de k

Le processus décrit dans la section précédente est en fait dérivé du générateur de nombres pseudoaléatoires "HMAC_DRBG", décrit dans [SP800-90A] et l'Annexe D de [X9.62]. En utilisant la terminologie de [SP800-90A], la génération de k peut être décrite comme suit:

a. Instancier HMAC_DRBG en utilisant HMAC paramétré avec la même fonction de hachage H que celle utilisée pour traiter le message qui doit être signé. Les paramètres d'instanciation sont:

requested_instantiation_security_strength : Définir ce paramètre à toute valeur que l'implémentation HMAC_DRBG acceptera, lors de l'utilisation de H comme fonction de hachage de base.

prediction_resistance_flag : Définir ce paramètre à "false".

personalization_string : Définir ce paramètre à "Null" (la séquence de bits vide).

entropy_input : Utiliser int2octets(x) comme chaîne d'entropie.

nonce : Utiliser bits2octets(H(m)) comme nonce.

Notez que les deux derniers paramètres ne sont pas des paramètres de la fonction d'instanciation HMAC_DRBG en soi; au lieu de cela, ces valeurs sont demandées à la fonction interne Get_entropy_input pendant l'instanciation. Pour (EC)DSA déterministe, nous voulons que HMAC_DRBG s'exécute avec la chaîne d'entropie et le nonce que nous spécifions, sans accéder à une source d'entropie réelle.

b. Générer une valeur candidate pour k en demandant qlen bits à HMAC_DRBG et en convertissant les bits résultants en un entier avec la transformation bits2int. Répéter cette étape jusqu'à ce qu'une valeur soit obtenue, qui est non nulle, inférieure à q, et appropriée pour (EC)DSA (voir la section 3.4).

Notez que nous instancions une nouvelle instance HMAC_DRBG pour chaque processus de génération de signature. Il n'y a pas de "chaîne de personnalisation" et pas d'"entrée additionnelle" lors de la génération de bits. La fonction de réensemencement de HMAC_DRBG n'est jamais invoquée, ni de manière externe ni en conséquence du traitement interne HMAC_DRBG.

Comme montré ci-dessus, nous utilisons l'encodage de la clé privée comme "chaîne d'entropie" et le message haché (tronqué et étendu par bits2octets) comme "nonce". Dans HMAC_DRBG, la chaîne d'entropie et le nonce sont simplement concaténés dans la graine initiale; par conséquent, la division entre "entropie" et "nonce" est assez arbitraire. L'utilisation de qlen bits pour chacun devrait être compatible avec la plupart des exigences d'entrée de l'implémentation HMAC_DRBG.

3.4. Notes d'utilisation

Avec DSA ou ECDSA, la valeur k est utilisée pour calculer la première moitié de la signature, appelée r (voir la section 2.4). Les normes DSA et ECDSA imposent que, si r est zéro, alors un nouveau k DEVRAIT être sélectionné. Dans cette situation, ce document spécifie que la valeur k est "inappropriée", et le processus de génération DOIT continuer à boucler.

Cette occurrence est extrêmement improbable. En fait, cela nécessiterait un effort computationnel considérable (similaire à casser la résistance à la préimage de la fonction de hachage) pour trouver une clé privée et un message qui conduisent à une valeur zéro pour r; toucher un tel cas par pur hasard est donc jugé improbable, et un attaquant ne peut pas le forcer avec des messages soigneusement conçus. En pratique, un tel chemin de code ne sera pas déclenché et peut donc être implémenté avec peu d'optimisation.

3.5. Justification

Le processus décrit dans les sections précédentes imite le processus de génération "Approuvé" de k décrit dans l'Annexe D de [X9.62], avec le générateur de nombres pseudoaléatoires "HMAC_DRBG". La principale différence est que nous utilisons la concaténation de la clé privée x et du message haché H(m) comme graine du générateur de nombres pseudoaléatoires (PRNG). Si l'on utilise un "niveau de sécurité" de n bits, alors HMAC_DRBG DEVRAIT être utilisé avec une entropie de graine d'au moins n+64 bits; cependant, la clé x DEVRAIT également avoir été générée avec autant d'entropie, et la longueur de x est qlen, qui est au moins égale à 2*n et donc supérieure à n+64 (DSA et ECDSA, tels que spécifiés par les normes, exigent qlen >= 160). On peut alors argumenter que ECDSA déterministe remplit les exigences d'entropie de l'Annexe D de [X9.62].

Nous utilisons bits2octets(H(m)) au lieu de H(m) afin de faciliter l'intégration. En effet, de nombreux systèmes de signature existants délèguent le hachage du message; le moteur de signature (qui a accès à la clé privée) reçoit uniquement H(m). Dans certaines applications, où la bande passante des données est contrainte, seuls les premiers qlen bits de H(m) sont transférés au moteur de signature, sur la base que la transformation bits2int ignorera les bits suivants de toute façon. Possiblement, dans certains systèmes, le H(m) tronqué pourrait être réduit de manière externe modulo q, puisque c'est la première chose que (EC)DSA effectue sur le message haché. Avec la définition de bits2octets, (EC)DSA déterministe peut être appliqué avec la même entrée.

3.6. Variantes

De nombreuses parties de la spécification de (EC)DSA déterministe sont assez arbitraires. Il est possible de définir des variantes qui ne sont PAS "(EC)DSA déterministe" mais qui peuvent néanmoins être utiles dans certains contextes:

Il est possible d'utiliser H(m) directement, au lieu de bits2octets(H(m)), comme partie de l'entrée HMAC. Comme expliqué dans la section 3.5, nous utilisons bits2octets(H(m)) afin de faciliter l'intégration dans les systèmes qui utilisent déjà un moteur de signature (EC)DSA en lui envoyant une valeur de hachage déjà tronquée. L'utilisation du H(m) complet n'introduit aucune vulnérabilité.
Des données supplémentaires peuvent être ajoutées à l'entrée de HMAC, concaténées après bits2octets(H(m)):

K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k')

Un cas d'utilisation peut être un protocole qui nécessite un algorithme de signature non déterministe sur un système qui n'a pas accès à une source aléatoire de haute qualité. Il suffit que les données supplémentaires k' ne se répètent pas (par exemple, un compteur de signatures ou une horloge monotone) pour garantir que les signatures "d'apparence aléatoire" sont indiscernables, d'un point de vue cryptographique, des signatures (EC)DSA ordinaires. Dans la terminologie [SP800-90A], k' est l'"entrée additionnelle" qui peut être définie comme paramètre lors de la génération de bits pseudoaléatoires. Cette variante peut être considérée comme un "renforcement" de la randomité de la source des données supplémentaires k'.
Au lieu d'utiliser x (la clé privée) comme entrée à HMAC, il est possible d'utiliser des données secrètes supplémentaires, stockées avec la clé privée avec les mêmes mesures de sécurité. L'entropie de ces données supplémentaires DOIT être d'au moins n bits, de préférence n+64 bits ou plus, où n est le niveau de sécurité cible. Avoir des données secrètes supplémentaires peut aider à prouver formellement la sécurité de la dérandomisation, mais cela implique un coût de stockage supplémentaire et une incompatibilité avec les clés privées (EC)DSA déjà générées.
De même, la clé privée pourrait être une valeur z, à partir de laquelle x (la "clé privée" au sens (EC)DSA ordinaire) et une autre valeur x', à utiliser comme entrée à HMAC dans la génération de k, seraient dérivées par une fonction pseudoaléatoire (PRF) appropriée (telle que HMAC_DRBG). Cela maintiendrait les exigences de stockage de clé privée au minimum tout en fournissant une sécurité plus facilement prouvable, mais cela impacterait la génération de clé privée et ne serait pas compatible avec les paires de clés déjà générées.
Dans ce document, nous utilisons la même fonction de hachage H pour traiter le message d'entrée et comme paramètre à HMAC. Deux fonctions de hachage distinctes pourraient être utilisées, à condition que les deux soient adéquatement sécurisées. La sécurité globale sera limitée par la plus faible des deux fonctions de hachage, c'est-à-dire celle avec la plus petite sortie. L'utilisation d'une fonction de hachage spécifique et constante pour HMAC peut être utile pour les implémentations contraintes qui acceptent des messages hachés de manière externe, quel que soit la fonction de hachage utilisée pour cela, mais qui n'ont des ressources que pour implémenter une seule fonction de hachage pour HMAC.

Le principal inconvénient de toute variante est qu'elle cesse d'être vérifiable par rapport aux vecteurs de test publiés dans ce document.