5. Hachage vers un corps fini

La fonction hash_to_field hache une chaîne d'octets msg de longueur arbitraire en un ou plusieurs éléments d'un corps F. Cette fonction procède en deux étapes : elle hache d'abord la chaîne d'octets d'entrée pour produire une chaîne d'octets uniformément aléatoire, puis interprète cette chaîne d'octets comme un ou plusieurs éléments de F.

Pour la première étape, hash_to_field appelle une fonction auxiliaire expand_message. Ce document définit deux variantes de expand_message : l'une adaptée aux fonctions de hachage telles que SHA-2 [FIPS180-4] ou SHA-3 [FIPS202], et l'autre adaptée aux fonctions à sortie extensible telles que SHAKE128 [FIPS202]. Les considérations de sécurité propres à chaque variante de expand_message sont abordées ci-dessous (Sections 5.3.1 et 5.3.2).

Les implémenteurs NE DOIVENT PAS utiliser l'échantillonnage par rejet pour générer un élément uniformément aléatoire de F, afin de garantir que la fonction hash_to_field se prête à une implémentation en temps constant. La raison en est que les procédures d'échantillonnage par rejet sont difficiles à implémenter en temps constant, et que des « optimisations » ultérieures, même bien intentionnées, peuvent silencieusement rendre une implémentation non constante en temps. Cela signifie que toute fonction hash_to_field fondée sur l'échantillonnage par rejet serait incompatible avec une implémentation en temps constant.

La fonction hash_to_field convient également au hachage sécurisé vers des scalaires. Par exemple, pour hacher vers le corps des scalaires d'un (sous-)groupe de courbe elliptique d'ordre premier r, il suffit d'instancier hash_to_field avec le corps cible GF(r).

La fonction hash_to_field est conçue pour être indifférentiable d'un oracle aléatoire [MRH04] lorsque expand_message (Section 5.3) est modélisée comme un oracle aléatoire (voir la Section 10.5 pour les détails sur son indifférentiabilité). Garantir l'indifférentiabilité demande de la prudence ; pour comprendre pourquoi, considérons un nombre premier p proche de 3/4 * 2^256. Réduire un entier aléatoire de 256 bits modulo ce p produit une valeur qui se situe dans l'intervalle [0, p / 3] avec une probabilité d'environ 1/2, ce qui signifie que cette valeur est statistiquement loin d'être uniforme sur [0, p - 1].

Pour maîtriser le biais, hash_to_field utilise à la place des entiers aléatoires dont la longueur est d'au moins ceil(log2(p)) + k bits, où k est le niveau de sécurité visé pour la suite, en bits. Réduire de tels entiers mod p donne un biais d'au plus 2^-k pour tout p ; ce biais est approprié lorsqu'on vise une sécurité de k bits. Pour chacun de ces entiers, hash_to_field utilise expand_message pour obtenir L octets uniformes, où

L = ceil((ceil(log2(p)) + k) / 8)

Ces octets uniformes sont ensuite interprétés comme un entier via OS2IP. Par exemple, pour un nombre premier p de 255 bits et une sécurité de k = 128 bits, L = ceil((255 + 128) / 8) = 48 octets.

Notons que k est une borne supérieure du niveau de sécurité pour la courbe correspondante. Voir la Section 10.8 pour plus de détails et la Section 8.9 pour des recommandations sur le choix de k pour une courbe donnée.

5.1. Considérations d'efficacité dans les corps d'extension

La fonction hash_to_field décrite dans cette section est inefficace pour certains corps d'extension. Plus précisément, lors du hachage vers un élément du corps d'extension GF(p^m), hash_to_field nécessite d'étendre msg en m * L octets (pour L tel que défini ci-dessus). Pour les corps d'extension où log2(p) est nettement inférieur au niveau de sécurité k, cette approche est inefficace : elle exige que expand_message produise environ m * log2(p) + m * k bits, alors que m * log2(p) + k octets suffisent pour générer un élément de GF(p^m) avec un biais d'au plus 2^-k. Dans de tels cas, les applications PEUVENT utiliser une fonction hash_to_field alternative, à condition qu'elle satisfasse aux exigences de sécurité suivantes :

• La fonction DOIT produire un ou plusieurs éléments de corps uniformément aléatoires, à un biais d'au plus 2^-k près.

• La fonction NE DOIT PAS utiliser l'échantillonnage par rejet.

• La fonction DEVRAIT se prêter à des implémentations en ligne droite (straight-line).

Par exemple, Pornin [P20] décrit une méthode de hachage vers GF(9767^19) qui satisfait ces exigences tout en utilisant moins de bits de sortie de expand_message que ne le ferait hash_to_field pour ce corps.

5.2. Implémentation de hash_to_field

La procédure suivante implémente hash_to_field.

Le paramètre expand_message de cette fonction DOIT se conformer aux exigences données à la Section 5.3. La Section 3.1 décrit la méthode REQUISE pour construire DST, l'étiquette de séparation de domaine. Notons que hash_to_field peut échouer (ABORT) si expand_message échoue.

hash_to_field(msg, count)

Parameters:
- DST, a domain separation tag (see Section 3.1).
- F, a finite field of characteristic p and order q = p^m.
- p, the characteristic of F (see immediately above).
- m, the extension degree of F, m >= 1 (see immediately above).
- L = ceil((ceil(log2(p)) + k) / 8), where k is the security
  parameter of the suite (e.g., k = 128).
- expand_message, a function that expands a byte string and
  domain separation tag into a uniformly random byte string
  (see Section 5.3).

Input:
- msg, a byte string containing the message to hash.
- count, the number of elements of F to output.

Output:
- (u_0, ..., u_(count - 1)), a list of field elements.

Steps:
1. len_in_bytes = count * m * L
2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
3. for i in (0, ..., count - 1):
4.   for j in (0, ..., m - 1):
5.     elm_offset = L * (j + i * m)
6.     tv = substr(uniform_bytes, elm_offset, L)
7.     e_j = OS2IP(tv) mod p
8.   u_i = (e_0, ..., e_(m - 1))
9. return (u_0, ..., u_(count - 1))

5.3. expand_message

expand_message est une fonction qui génère une chaîne d'octets uniformément aléatoire. Elle prend trois arguments :

1. msg, une chaîne d'octets contenant le message à hacher,

2. DST, une chaîne d'octets jouant le rôle d'étiquette de séparation de domaine, et

3. len_in_bytes, le nombre d'octets à générer.

Ce document définit les deux variantes suivantes de expand_message :

• expand_message_xmd (Section 5.3.1) convient à une large gamme de fonctions de hachage, notamment SHA-2 [FIPS180-4], SHA-3 [FIPS202], BLAKE2 [RFC7693] et d'autres.

• expand_message_xof (Section 5.3.2) convient aux fonctions à sortie extensible (XOF), notamment aux fonctions des familles SHAKE [FIPS202] ou BLAKE2X [BLAKE2X].

Ces variantes devraient suffire pour la grande majorité des cas d'usage, mais d'autres variantes sont possibles ; la Section 5.3.4 en expose les exigences.

5.3.1. expand_message_xmd

La fonction expand_message_xmd produit une chaîne d'octets uniformément aléatoire au moyen d'une fonction de hachage cryptographique H qui produit b bits en sortie. Pour des raisons de sécurité, H DOIT satisfaire aux exigences suivantes :

• Le nombre de bits produits par H DOIT vérifier b >= 2 * k, où k est le niveau de sécurité visé en bits, et b DOIT être divisible par 8. La première exigence garantit une résistance aux collisions de k bits ; la seconde garantit l'uniformité de la sortie de expand_message_xmd.

• H PEUT être une fonction de hachage de type Merkle-Damgård telle que SHA-2. Dans ce cas, la sécurité est assurée lorsque la fonction de compression sous-jacente est modélisée comme un oracle aléatoire [CDMP05]. (Voir la Section 10.6 pour une discussion.)

• H PEUT être une fonction de hachage à éponge telle que SHA-3 ou BLAKE2. Dans ce cas, la sécurité est assurée lorsque la fonction interne est modélisée comme une transformation aléatoire ou comme une permutation aléatoire [BDPV08].

• Sinon, H DOIT être une fonction de hachage dont l'indifférentiabilité d'un oracle aléatoire [MRH04] a été prouvée sous une hypothèse cryptographique raisonnable.

SHA-2 [FIPS180-4] et SHA-3 [FIPS202] sont des choix typiques et RECOMMANDÉS. À titre d'exemple, pour le niveau de sécurité de 128 bits, b >= 256 bits, et SHA-256 ou SHA3-256 constituerait un choix approprié.

On suppose que la fonction de hachage H fonctionne en ingérant de façon répétée des blocs de données de longueur fixe. La longueur en bits de ces blocs est appelée taille de bloc d'entrée (s). À titre d'exemples, s = 1024 pour SHA-512 [FIPS180-4] et s = 576 pour SHA3-512 [FIPS202]. Pour la correction, H requiert b <= s.

La procédure suivante implémente expand_message_xmd.

expand_message_xmd(msg, DST, len_in_bytes)

Parameters:
- H, a hash function (see requirements above).
- b_in_bytes, b / 8 for b the output size of H in bits.
  For example, for b = 256, b_in_bytes = 32.
- s_in_bytes, the input block size of H, measured in bytes (see
  discussion above). For example, for SHA-256, s_in_bytes = 64.

Input:
- msg, a byte string.
- DST, a byte string of at most 255 bytes.
  See below for information on using longer DSTs.
- len_in_bytes, the length of the requested output in bytes,
  not greater than the lesser of (255 * b_in_bytes) or 2^16-1.

Output:
- uniform_bytes, a byte string.

Steps:
1.  ell = ceil(len_in_bytes / b_in_bytes)
2.  ABORT if ell > 255 or len_in_bytes > 65535 or len(DST) > 255
3.  DST_prime = DST || I2OSP(len(DST), 1)
4.  Z_pad = I2OSP(0, s_in_bytes)
5.  l_i_b_str = I2OSP(len_in_bytes, 2)
6.  msg_prime = Z_pad || msg || l_i_b_str || I2OSP(0, 1) || DST_prime
7.  b_0 = H(msg_prime)
8.  b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
9.  for i in (2, ..., ell):
10.    b_i = H(strxor(b_0, b_(i - 1)) || I2OSP(i, 1) || DST_prime)
11. uniform_bytes = b_1 || ... || b_ell
12. return substr(uniform_bytes, 0, len_in_bytes)

Notons que la chaîne Z_pad (étape 6) est préfixée à msg avant le calcul de b_0 (étape 7). Cela est nécessaire pour la sécurité lorsque H est un hachage de type Merkle-Damgård, par exemple SHA-2 (voir la Section 10.6). Le hachage de ces données supplémentaires implique que le coût du calcul de b_0 est supérieur au coût du simple calcul de H(msg). Dans la plupart des contextes, ce surcoût est négligeable, car le coût d'évaluation de H est bien inférieur aux autres coûts impliqués dans le hachage vers une courbe.

Il est toutefois possible d'éviter entièrement ce surcoût en tirant parti du fait que Z_pad ne dépend que de H, et non des arguments de expand_message_xmd. Pour ce faire, il convient d'abord de précalculer et de sauvegarder l'état interne de H après ingestion de Z_pad. Ensuite, lors du calcul de b_0, on initialise H à partir de l'état sauvegardé. Les détails supplémentaires dépendent de l'implémentation et dépassent le cadre de ce document.

5.3.2. expand_message_xof

La fonction expand_message_xof produit une chaîne d'octets uniformément aléatoire au moyen d'une fonction à sortie extensible (XOF) H. Pour des raisons de sécurité, H DOIT satisfaire aux critères suivants :

• La résistance aux collisions de H DOIT être d'au moins k bits.

• H DOIT être une XOF dont l'indifférentiabilité d'un oracle aléatoire a été prouvée sous une hypothèse cryptographique raisonnable.

La famille de XOF SHAKE [FIPS202] est un choix typique et RECOMMANDÉ. À titre d'exemple, pour une sécurité de 128 bits, SHAKE128 constituerait un choix approprié.

La procédure suivante implémente expand_message_xof.

expand_message_xof(msg, DST, len_in_bytes)

Parameters:
- H(m, d), an extendable-output function that processes
  input message m and returns d bytes.

Input:
- msg, a byte string.
- DST, a byte string of at most 255 bytes.
  See below for information on using longer DSTs.
- len_in_bytes, the length of the requested output in bytes.

Output:
- uniform_bytes, a byte string.

Steps:
1. ABORT if len_in_bytes > 65535 or len(DST) > 255
2. DST_prime = DST || I2OSP(len(DST), 1)
3. msg_prime = msg || I2OSP(len_in_bytes, 2) || DST_prime
4. uniform_bytes = H(msg_prime, len_in_bytes)
5. return uniform_bytes

5.3.3. Utilisation de DST de plus de 255 octets

Les variantes de expand_message définies dans cette section acceptent des étiquettes de séparation de domaine d'au plus 255 octets. Si des applications requièrent une étiquette de séparation de domaine de plus de 255 octets, par exemple en raison d'exigences imposées par un protocole appelant, les implémenteurs DOIVENT calculer une étiquette de séparation de domaine courte par hachage, comme suit :

• Pour expand_message_xmd utilisant la fonction de hachage H, DST est calculée comme

DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST)

• Pour expand_message_xof utilisant la fonction à sortie extensible H, DST est calculée comme

DST = H("H2C-OVERSIZE-DST-" || a_very_long_DST, ceil(2 * k / 8))

Ici, a_very_long_DST est la DST dont la longueur est supérieure à 255 octets, « H2C-OVERSIZE-DST- » est un littéral de chaîne ASCII de 17 octets, et k est le niveau de sécurité visé en bits.

5.3.4. Définition d'autres variantes de expand_message

Lors de la définition d'une nouvelle variante de expand_message, la considération la plus importante est que hash_to_field modélise expand_message comme un oracle aléatoire. Ainsi, les implémenteurs DEVRAIENT prouver l'indifférentiabilité d'un oracle aléatoire sous une hypothèse appropriée concernant les primitives cryptographiques sous-jacentes ; voir la Section 10.5 pour plus d'informations.

En outre, les variantes de expand_message :

• DOIVENT offrir une résistance aux collisions à la mesure du niveau de sécurité de la courbe elliptique cible.

• DOIVENT être construites sur des primitives conçues pour un usage dans des applications requérant de l'aléa cryptographique. À titre d'exemples, un chiffrement par flot sûr est une primitive appropriée, tandis qu'un générateur de nombres pseudo-aléatoires de type Mersenne Twister [MT98] ne l'est pas.

• NE DOIVENT PAS utiliser l'échantillonnage par rejet.

• DOIVENT donner des valeurs indépendantes pour des entrées (msg, DST, length) distinctes. Satisfaire cette exigence est subtil. Comme exemple simplifié, hacher msg || DST ne convient pas, car dans ce cas des paires (msg, DST) distinctes dont les concaténations sont égales renverraient la même sortie (par exemple, ("AB", "CDEF") et ("ABC", "DEF")). Les variantes définies dans ce document utilisent un encodage sans suffixe (suffix-free) de DST afin d'éviter ce problème.

• DOIVENT utiliser l'étiquette de séparation de domaine DST pour garantir que les invocations de primitives cryptographiques à l'intérieur de expand_message soient séparées par domaine des invocations extérieures à expand_message. Par exemple, si la variante de expand_message utilise une fonction de hachage H, un encodage de DST DOIT être ajouté soit en préfixe, soit en suffixe de l'entrée de chaque invocation de H. L'ajout de DST en suffixe est l'approche RECOMMANDÉE.

• DEVRAIENT lire msg exactement une fois, par souci d'efficacité lorsque msg est long.

En outre, chaque variante de expand_message DOIT spécifier une EXP_TAG unique qui identifie cette variante dans un identifiant de suite (Suite ID). Voir la Section 8.10 pour plus d'informations.