Aller au contenu principal

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 travaille 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 : une appropriée pour les fonctions de hachage comme SHA-2 [FIPS180-4] ou SHA-3 [FIPS202], et une autre appropriée pour les fonctions à sortie extensible telles que SHAKE128 [FIPS202]. Les considérations de sécurité pour chaque variante de expand_message sont discuté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 bien intentionnées peuvent rendre silencieusement une implémentation non constante en temps. Cela signifie que toute fonction hash_to_field basée sur l'échantillonnage par rejet serait incompatible avec une implémentation en temps constant.

La fonction hash_to_field convient également pour hacher de manière sécurisée vers des scalaires. Par exemple, lors du hachage vers le corps scalaire pour 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érenciable d'un oracle aléatoire [MRH04] lorsque expand_message (section 5.3) est modélisé comme un oracle aléatoire (voir la section 10.5 pour plus de détails sur son indifférenciabilité). Garantir l'indifférenciabilité nécessite de la prudence ; pour comprendre pourquoi, considérons un nombre premier p qui est proche de 3/4 * 2^256. Réduire un entier aléatoire de 256 bits modulo ce p donne une valeur qui se trouve dans la plage [0, p / 3] avec une probabilité d'environ 1/2, ce qui signifie que cette valeur est statistiquement loin d'être uniforme dans [0, p - 1].

Pour contrôler 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é cible pour la suite en bits. La réduction 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 chaque entier de ce type, 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é k = 128 bits, L = ceil((255 + 128) / 8) = 48 octets.

Notez 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 conseils 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 l'expansion de msg en m * L octets (pour L tel que défini ci-dessus). Pour les corps d'extension où log2(p) est significativement plus petit que le niveau de sécurité k, cette approche est inefficace : elle nécessite 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 réponde aux exigences de sécurité suivantes :

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

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

  • La fonction DEVRAIT se prêter à des implémentations en ligne droite.

Par exemple, Pornin [P20] décrit une méthode de hachage vers GF(9767^19) qui répond à 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 être conforme aux exigences données dans la section 5.3. La section 3.1 traite de la méthode REQUISE pour construire DST, l'étiquette de séparation de domaine. Notez que hash_to_field peut échouer (ABORT) si expand_message échoue.

hash_to_field(msg, count)

Paramètres :

  • DST, une étiquette de séparation de domaine (voir la section 3.1).
  • F, un corps fini de caractéristique p et d'ordre q = p^m.
  • p, la caractéristique de F (voir immédiatement ci-dessus).
  • m, le degré d'extension de F, m >= 1 (voir immédiatement ci-dessus).
  • L = ceil((ceil(log2(p)) + k) / 8), où k est le paramètre de sécurité de la suite (par exemple, k = 128).
  • expand_message, une fonction qui étend une chaîne d'octets et une étiquette de séparation de domaine en une chaîne d'octets uniformément aléatoire (voir la section 5.3).

Entrée :

  • msg, une chaîne d'octets contenant le message à hacher.
  • count, le nombre d'éléments de F à produire.

Sortie :

  • (u_0, ..., u_(count - 1)), une liste d'éléments du corps.

Étapes :

  1. len_in_bytes = count * m * L
  2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
  3. pour i allant de 0 à count - 1 :
  4. pour j allant de 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. retourner (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 qui agit comme une é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) est adaptée à une utilisation avec une large gamme de fonctions de hachage, incluant SHA-2 [FIPS180-4], SHA-3 [FIPS202], BLAKE2 [RFC7693], et d'autres.

  • expand_message_xof (section 5.3.2) est adaptée à une utilisation avec des fonctions à sortie extensible (XOF), incluant les fonctions des familles SHAKE [FIPS202] ou BLAKE2X [BLAKE2X].

Ces variantes devraient suffire pour la grande majorité des cas d'utilisation, mais d'autres variantes sont possibles ; la section 5.3.4 traite des exigences.

5.3.1. expand_message_xmd​

La fonction expand_message_xmd produit une chaîne d'octets uniformément aléatoire en utilisant une fonction de hachage cryptographique H qui produit b bits. Pour la sécurité, H DOIT répondre aux exigences suivantes :

  • Le nombre de bits produits par H DOIT être b >= 2 * k, où k est le niveau de sécurité cible 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 Merkle-Damgaard comme 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 plus de détails.)

  • H PEUT être une fonction de hachage basée sur une éponge comme 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érenciabilité 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é 128 bits, b >= 256 bits et soit SHA-256 soit SHA3-256 serait un choix approprié.

La fonction de hachage H est supposée fonctionner en ingérant de manière 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'exemple, s = 1024 pour SHA-512 [FIPS180-4] et s = 576 pour SHA3-512 [FIPS202]. Pour l'exactitude, H requiert b <= s.

La procédure suivante implémente expand_message_xmd.

expand_message_xmd(msg, DST, len_in_bytes)

Paramètres :

  • H, une fonction de hachage (voir les exigences ci-dessus).
  • b_in_bytes, b / 8 pour b la taille de sortie de H en bits. Par exemple, pour b = 256, b_in_bytes = 32.
  • s_in_bytes, la taille du bloc d'entrée de H, mesurée en octets (voir la discussion ci-dessus). Par exemple, pour SHA-256, s_in_bytes = 64.

Entrée :

  • msg, une chaîne d'octets.
  • DST, une chaîne d'octets d'au plus 255 octets. Voir ci-dessous pour plus d'informations sur l'utilisation de DST plus longs.
  • len_in_bytes, la longueur de la sortie demandée en octets, ne dépassant pas le moindre de (255 * b_in_bytes) ou 2^16-1.

Sortie :

  • uniform_bytes, une chaîne d'octets.

Étapes :

  1. ell = ceil(len_in_bytes / b_in_bytes)
  2. ABORT si ell > 255 ou len_in_bytes > 65535 ou 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. pour i allant de 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. retourner substr(uniform_bytes, 0, len_in_bytes)

Notez que la chaîne Z_pad (étape 6) est préfixée à msg avant de calculer b_0 (étape 7). Ceci est nécessaire pour la sécurité lorsque H est un hachage Merkle-Damgaard, par exemple SHA-2 (voir la section 10.6). Le hachage de ces données supplémentaires signifie que le coût de calcul de b_0 est plus élevé que le 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 possible, cependant, d'éviter entièrement ce surcoût en profitant du fait que Z_pad ne dépend que de H, et non des arguments de expand_message_xmd. Pour ce faire, précalculez d'abord et enregistrez l'état interne de H après avoir ingéré Z_pad. Ensuite, lors du calcul de b_0, initialisez H en utilisant l'état enregistré. D'autres détails 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 en utilisant une fonction à sortie extensible (XOF) H. Pour la sécurité, H DOIT répondre 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érenciabilité d'un oracle aléatoire a été prouvée sous une hypothèse cryptographique raisonnable.

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

La procédure suivante implémente expand_message_xof.

expand_message_xof(msg, DST, len_in_bytes)

Paramètres :

  • H(m, d), une fonction à sortie extensible qui traite le message d'entrée m et renvoie d octets.

Entrée :

  • msg, une chaîne d'octets.
  • DST, une chaîne d'octets d'au plus 255 octets. Voir ci-dessous pour plus d'informations sur l'utilisation de DST plus longs.
  • len_in_bytes, la longueur de la sortie demandée en octets.

Sortie :

  • uniform_bytes, une chaîne d'octets.

Étapes :

  1. ABORT si len_in_bytes > 65535 ou 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. retourner uniform_bytes

5.3.3. Utilisation de DST plus longs que 255 octets​

Les variantes expand_message définies dans cette section acceptent des étiquettes de séparation de domaine d'au plus 255 octets. Si les applications nécessitent une étiquette de séparation de domaine de plus de 255 octets, par exemple en raison des 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é cible en bits.

5.3.4. Définition d'autres variantes de expand_message​

Lors de la définition d'une nouvelle variante 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érenciabilité d'un oracle aléatoire sous une hypothèse appropriée sur les primitives cryptographiques sous-jacentes ; voir la section 10.5 pour plus d'informations.

En outre, les variantes expand_message :

  • DOIVENT donner une résistance aux collisions proportionnée au niveau de sécurité de la courbe elliptique cible.

  • DOIVENT être construites sur des primitives conçues pour être utilisées dans des applications nécessitant un caractère aléatoire cryptographique. À titre d'exemple, un chiffrement par flux sécurisé est une primitive appropriée, tandis qu'un générateur de nombres pseudo-aléatoires 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, longueur) distinctes. Satisfaire cette exigence est subtil. À titre d'exemple simplifié, le hachage msg || DST ne fonctionne pas, car dans ce cas, des paires (msg, DST) distinctes dont les concaténations sont égales renverront la même sortie (par exemple, ("AB", "CDEF") et ("ABC", "DEF")). Les variantes définies dans ce document utilisent un encodage sans suffixe de DST pour é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 sont séparées par domaine des invocations à l'extérieur de expand_message. Par exemple, si la variante expand_message utilise une fonction de hachage H, un encodage de DST DOIT être ajouté soit comme préfixe, soit comme suffixe de l'entrée de chaque invocation de H. L'ajout de DST en tant que suffixe est l'approche RECOMMANDÉE.

  • DEVRAIENT lire msg exactement une fois, pour des raisons d'efficacité lorsque msg est long.

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

Dernière mise à jour le