10. Considérations de sécurité

Considérations de sécurité

Cette section contient des considérations de sécurité supplémentaires concernant les mécanismes hash-to-curve décrits dans ce document.

10.1. Propriétés des encodages

Chaque type d'encodage (Section 3) accepte une chaîne d'octets arbitraire et l'envoie vers un point de la courbe échantillonné selon une distribution qui dépend du type d'encodage. Il est important de noter que l'utilisation d'un encodage non uniforme, ou l'évaluation directe de l'une des applications de la Section 6, produit une sortie qui se distingue aisément d'un point uniformément aléatoire. Les applications qui utilisent un encodage non uniforme DEVRAIENT analyser soigneusement les implications de sécurité de cette non-uniformité. Lorsque l'encodage requis n'est pas clair, les applications DEVRAIENT utiliser un encodage uniforme.

Les deux encodages donnés à la Section 3 peuvent produire l'élément neutre du groupe G. La probabilité que l'une ou l'autre des fonctions d'encodage produise l'élément neutre est d'environ 1/r pour une entrée aléatoire, ce qui est négligeable pour les courbes elliptiques cryptographiquement utiles. De plus, il est calculatoirement infaisable de trouver une entrée de l'une ou l'autre fonction d'encodage dont la sortie correspondante soit l'élément neutre. (Ces deux propriétés sont vérifiées lorsque les fonctions d'encodage sont instanciées avec une fonction hash_to_field respectant toutes les recommandations de la Section 5.) Les protocoles qui utilisent ces fonctions d'encodage NE DEVRAIENT PAS ajouter de cas particulier pour détecter et « corriger » l'élément neutre.

Lorsque la fonction hash_to_curve (Section 3) est instanciée avec une fonction hash_to_field indifférentiable d'un oracle aléatoire (Section 5), la fonction résultante est indifférentiable d'un oracle aléatoire ([MRH04] [BCIMRT10] [FFSTV13] [LBB19] [H20]). Dans de nombreux cas, une telle fonction peut être utilisée en toute sécurité dans des protocoles cryptographiques dont l'analyse de sécurité suppose un oracle aléatoire produisant des points uniformément aléatoires sur une courbe elliptique. Comme Ristenpart et al. le discutent dans [RSS11], toutefois, les preuves de sécurité reposant sur des oracles aléatoires ne restent pas toutes valides lorsque ces oracles sont remplacés par des fonctionnalités indifférentiables. Cette limitation devrait être prise en compte lors de l'analyse de la sécurité des protocoles reposant sur la fonction hash_to_curve.

10.2. Hachage de mots de passe

Lors du hachage de mots de passe au moyen de l'une quelconque des fonctions décrites dans ce document, un adversaire qui apprend la sortie de la fonction de hachage (ou potentiellement toute valeur intermédiaire, par exemple la sortie de hash_to_field) peut être en mesure de mener une attaque par dictionnaire. Pour atténuer de telles attaques, il est recommandé d'exécuter d'abord une fonction de dérivation de clé plus coûteuse (par exemple PBKDF2 [RFC8018], scrypt [RFC7914] ou Argon2 [RFC9106]) sur le mot de passe, puis de hacher la sortie de cette fonction vers la courbe elliptique cible. Pour assurer la résistance aux collisions, la fonction de hachage sous-jacente à la fonction de dérivation de clé devrait être choisie conformément aux recommandations énumérées à la Section 5.3.1.

10.3. Exigences de temps constant

Des implémentations en temps constant de toutes les fonctions de ce document sont FORTEMENT RECOMMANDÉES pour tous les usages, afin d'éviter les fuites d'informations par canaux auxiliaires. Il est particulièrement important d'utiliser une implémentation en temps constant lorsque les entrées d'un encodage sont des valeurs secrètes ; dans de tels cas, les implémentations en temps constant sont REQUISES pour assurer la sécurité contre les attaques temporelles (par exemple, [VR20]). Lorsque des implémentations en temps constant sont requises, toutes les opérations de base et les fonctions utilitaires doivent être implémentées en temps constant, comme discuté à la Section 4. Dans certaines applications (par exemple, les systèmes embarqués), les fuites par d'autres canaux auxiliaires (par exemple, les canaux de consommation électrique ou électromagnétiques) peuvent être pertinentes. La défense contre de telles fuites dépasse le cadre de ce document, car la nature de la fuite et la défense appropriée dépendent de l'application.

10.4. encode_to_curve : distribution de sortie et indifférentiabilité

La fonction encode_to_curve (Section 3) renvoie des points échantillonnés selon une distribution statistiquement éloignée de l'uniforme. Cette distribution est approximativement bornée comme suit : premièrement, elle inclut au moins un huitième des points de G, et deuxièmement, la probabilité des points de la distribution varie au plus d'un facteur quatre. Ces bornes sont valides lorsque encode_to_curve est instanciée avec l'une quelconque des fonctions map_to_curve de la Section 6.

Les bornes ci-dessus sont dérivées de plusieurs travaux de la littérature. Plus précisément :

Shallue et van de Woestijne [SW06] ainsi que Fouque et Tibouchi [FT12] établissent des bornes pour l'application de Shallue-van de Woestijne (Section 6.6.1).
Fouque et Tibouchi [FT10] ainsi que Tibouchi [T14] établissent des bornes pour l'application SWU simplifiée (Sections 6.6.2 et 6.6.3).
Bernstein et al. [BHKL13] établissent des bornes pour l'application Elligator 2 (Sections 6.7.1 et 6.8.2).

L'indifférentiabilité de encode_to_curve découle d'un argument similaire à celui donné par Brier et al. [BCIMRT10] ; nous esquissons brièvement cet argument comme suit. Considérons un oracle aléatoire idéal Hc() qui échantillonne selon la distribution induite par la fonction map_to_curve appelée par encode_to_curve, et supposons pour simplifier que la courbe elliptique cible a un cofacteur égal à 1 (un argument similaire s'applique aux cofacteurs différents de 1). L'indifférentiabilité est vérifiée dès lors qu'il est possible de simuler efficacement l'oracle aléatoire « interne » de encode_to_curve, à savoir hash_to_field. Le simulateur fonctionne comme suit : sur une nouvelle requête msg, le simulateur interroge Hc(msg) et reçoit un point P dans l'image de map_to_curve (si msg est identique à une requête antérieure, le simulateur renvoie simplement la valeur qu'il avait fournie en réponse à cette requête). Le simulateur calcule ensuite les préimages possibles de P sous map_to_curve, c'est-à-dire les éléments u de F tels que map_to_curve(u) == P (Tibouchi [T14] montre que cela peut être fait efficacement pour les applications de Shallue-van de Woestijne et SWU simplifiée, et Bernstein et al. montrent la même chose pour Elligator 2). Le simulateur sélectionne au hasard l'une de ces préimages et renvoie cette valeur comme sortie simulée de l'oracle aléatoire « interne ». Par hypothèse, Hc() échantillonne selon la distribution induite par map_to_curve sur un élément d'entrée uniformément aléatoire de F ; cette valeur est donc uniformément aléatoire et induit le point correct P lorsqu'elle est passée à map_to_curve.

10.5. Sécurité de hash_to_field

La fonction hash_to_field, définie à la Section 5, est indifférentiable d'un oracle aléatoire [MRH04] lorsque expand_message (Section 5.3) est modélisée comme un oracle aléatoire. Comme les preuves d'indifférentiabilité sont composables, cela reste vrai lorsque expand_message est prouvée indifférentiable d'un oracle aléatoire relativement à une primitive sous-jacente modélisée comme un oracle aléatoire. En suivant les recommandations de la Section 5.3, les deux variantes de expand_message définies dans cette section satisfont cette exigence (voir également la Section 10.6).

Nous esquissons très brièvement l'argument d'indifférentiabilité pour hash_to_field. Notons que chaque entier mod p renvoyé par hash_to_field (c'est-à-dire chaque élément de la représentation vectorielle de F) est membre d'une classe d'équivalence d'environ 2^k entiers de longueur log2(p) + k bits, tous égaux modulo p. Pour chaque entier mod p renvoyé par hash_to_field, le simulateur échantillonne au hasard un membre de cette classe d'équivalence et produit la chaîne d'octets renvoyée par I2OSP. (Notons qu'il s'agit essentiellement de l'inverse de la procédure hash_to_field.)

10.6. Sécurité de expand_message_xmd

La fonction expand_message_xmd, définie à la Section 5.3.1, est indifférentiable d'un oracle aléatoire [MRH04] lorsque l'une des conditions suivantes est vérifiée :

H est indifférentiable d'un oracle aléatoire,
H est une fonction de hachage à éponge dont la fonction interne est modélisée comme une transformation aléatoire ou une permutation aléatoire [BDPV08], ou
H est une fonction de hachage de type Merkle-Damgård dont la fonction de compression est modélisée comme un oracle aléatoire [CDMP05].

Pour les cas (1) et (2), l'indifférentiabilité de expand_message_xmd découle directement de l'indifférentiabilité de H.

Pour le cas (3), c'est-à-dire lorsque H est une fonction de hachage de type Merkle-Damgård, l'indifférentiabilité découle de [CDMP05], Théorème 5. En particulier, expand_message_xmd calcule b_0 en préfixant le message d'un bloc de zéros ainsi que d'informations auxiliaires (longueur, compteur et DST). Ensuite, chacun des blocs de sortie b_i, i >= 1 dans expand_message_xmd est le résultat de l'invocation de H sur un encodage unique et sans préfixe de b_0. Cela est vrai, premièrement parce que la longueur de l'entrée de toutes ces invocations est égale et fixée par le choix de H et de DST, et deuxièmement parce que chacune de ces entrées possède un suffixe unique (en raison de l'inclusion de l'octet compteur I2OSP(i, 1)).

La différence essentielle entre la construction discutée dans [CDMP05] et expand_message_xmd est que cette dernière hache un compteur ajouté à strxor(b_0, b_(i - 1)) ({#hashtofield-expand-xmd}, étape 10) plutôt qu'à b_0. Cette approche accroît la distance de Hamming entre les entrées des différentes invocations de H, ce qui réduit la probabilité que des non-idéalités de H affectent la distribution des valeurs b_i.

Nous notons que expand_message_xmd peut être utilisée pour instancier une fonctionnalité indifférentiable à usage général avec une sortie de longueur variable, fondée sur toute fonction de hachage satisfaisant l'un des critères ci-dessus. Les applications qui utilisent expand_message_xmd en dehors de hash_to_field devraient assurer la séparation de domaine en choisissant une valeur distincte pour DST.

10.7. Séparation de domaine pour les variantes de expand_message

Comme discuté à la Section 2.2.5, l'objectif de la séparation de domaine est de garantir que les analyses de sécurité des protocoles cryptographiques qui interrogent plusieurs oracles aléatoires indépendants restent valides même si tous ces oracles aléatoires sont instanciés à partir d'une seule fonction sous-jacente H.

Les variantes de expand_message de ce document (Section 5.3) assurent la séparation de domaine en ajoutant une étiquette de séparation de domaine DST_prime encodée sans suffixe à toutes les chaînes hachées par H, une fonction de hachage ou une fonction à sortie extensible sous-jacente. (Les autres variantes de expand_message qui suivent les recommandations de la Section 5.3.4 devraient se comporter de manière similaire, mais elles devraient être analysées au cas par cas.) Pour des raisons de sécurité, les applications qui utilisent la même fonction H en dehors de expand_message devraient imposer une séparation de domaine entre ces usages de H et expand_message, et devraient séparer l'ensemble de ces usages de ceux de H dans d'autres applications.

Cette section propose quatre méthodes pour imposer la séparation de domaine vis-à-vis des variantes de expand_message, explique comment chaque méthode réalise cette séparation, et énumère les situations dans lesquelles chacune est appropriée. Ces méthodes partagent une structure générale : le concepteur de l'application fixe une étiquette DST_ext distincte de DST_prime et enrichit les appels à H avec DST_ext. Chaque méthode enrichit les appels à H différemment, et chacune peut imposer des exigences supplémentaires sur DST_ext.

Ces méthodes peuvent être utilisées pour instancier plusieurs fonctions séparées par domaine (par exemple, H1 et H2) en sélectionnant des valeurs DST_ext distinctes pour chacune (par exemple, DST_ext1, DST_ext2).

(Séparation de domaine par suffixe uniquement.) Cette méthode est utile pour séparer par domaine les invocations de H de celles de expand_message_xmd ou expand_message_xof. Elle n'est pas appropriée pour séparer par domaine expand_message de HMAC-H [RFC2104] ; à cette fin, voir la méthode 4.

Pour instancier une fonction Hso séparée par domaine à l'aide d'un suffixe uniquement, calculer

  Hso(msg) = H(msg || DST_ext)

   DST_ext devrait être encodée sans suffixe (par exemple, en
   ajoutant un octet encodant la longueur de DST_ext) afin de rendre
   infaisable la recherche de paires (msg, DST_ext) distinctes ayant
   la même valeur de hachage.

   Cette méthode assure la séparation de domaine car toutes les
   invocations distinctes de H ont des suffixes distincts, puisque
   DST_ext est distincte de DST_prime.

2. (Séparation de domaine préfixe-suffixe.) Cette méthode peut être utilisée dans les mêmes cas que la méthode par suffixe uniquement.

   Pour instancier une fonction Hps séparée par domaine par
   préfixe-suffixe, calculer

  Hps(msg) = H(DST_ext || msg || I2OSP(0, 1))

   DST_ext devrait être encodée sans préfixe (par exemple, en
   ajoutant un préfixe d'un octet encodant la longueur de DST_ext)
   afin de rendre infaisable la recherche de paires (msg, DST_ext)
   distinctes ayant la même valeur de hachage.

   Cette méthode assure la séparation de domaine car l'ajout de
   l'octet I2OSP(0, 1) garantit que les entrées de H à l'intérieur
   de Hps sont distinctes de celles à l'intérieur de
   expand_message.  Plus précisément, l'octet final de DST_prime
   encode la longueur de DST, qui doit être non nulle (Section 3.1,
   exigence 2), et DST_prime est toujours ajoutée aux invocations de
   H à l'intérieur de expand_message.

3. (Séparation de domaine par préfixe uniquement.) Cette méthode n'est utile que pour séparer par domaine les invocations de H de celles de expand_message_xmd. Elle n'assure pas la séparation de domaine pour expand_message_xof ni pour HMAC-H.

   Pour instancier une fonction Hpo séparée par domaine à l'aide
   d'un préfixe uniquement, calculer

  Hpo(msg) = H(DST_ext || msg)

   Pour que cette méthode assure la séparation de domaine, DST_ext
   devrait avoir une longueur d'au moins b bits, où b est le nombre
   de bits produits par la fonction de hachage H.  De plus, au moins
   l'un des b premiers bits doit être non nul.  Enfin, DST_ext
   devrait être encodée sans préfixe (par exemple, en ajoutant un
   préfixe d'un octet encodant la longueur de DST_ext) afin de
   rendre infaisable la recherche de paires (msg, DST_ext)
   distinctes ayant la même valeur de hachage.

   Cette méthode assure la séparation de domaine comme suit.
   Premièrement, puisque DST_ext contient au moins un bit non nul
   parmi ses b premiers bits, elle est garantie d'être distincte de
   la valeur Z_pad (Section 5.3.1, étape 4), ce qui garantit que
   toutes les entrées de H sont distinctes de l'entrée utilisée pour
   générer b_0 dans expand_message_xmd.  Deuxièmement, puisque
   DST_ext a une longueur d'au moins b bits, elle est presque
   certainement distincte des valeurs b_0 et strxor(b_0, b_(i - 1)),
   et par conséquent toutes les entrées de H sont distinctes des
   entrées utilisées pour générer b_i, i >= 1, avec une probabilité
   élevée.

4. (Séparation de domaine XMD-HMAC.) Cette méthode est utile pour séparer par domaine les invocations de H à l'intérieur de HMAC-H (c'est-à-dire HMAC [RFC2104] instanciée avec la fonction de hachage H) de celles de expand_message_xmd. Elle s'applique également à HKDF-H (c'est-à-dire HKDF [RFC5869] instanciée avec la fonction de hachage H), comme discuté ci-dessous.

   Plus précisément, cette méthode s'applique lorsque HMAC-H est
   utilisée avec une clé non secrète pour instancier un oracle
   aléatoire fondé sur une fonction de hachage H (notons que
   expand_message_xmd peut également être utilisée à cette fin ;
   voir la Section 10.6).  Lors de l'utilisation de HMAC-H avec une
   clé secrète à forte entropie, la séparation de domaine n'est pas
   nécessaire ; voir la discussion ci-dessous.

   Pour choisir une clé HMAC non secrète DST_key qui assure la
   séparation de domaine vis-à-vis de expand_message_xmd, calculer

  DST_key_preimage = "DERIVE-HMAC-KEY-" || DST_ext || I2OSP(0, 1)
  DST_key = H(DST_key_preimage)

   Ensuite, pour instancier l'oracle aléatoire Hro au moyen de
   HMAC-H, calculer

  Hro(msg) = HMAC-H(DST_key, msg)

   L'octet nul final de DST_key_preimage garantit que cette valeur
   est distincte des entrées de H à l'intérieur de
   expand_message_xmd (car toutes ces entrées ont pour suffixe
   DST_prime, qui ne peut pas se terminer par un octet nul, comme
   discuté ci-dessus).  Cela assure la séparation de domaine car,
   avec une probabilité écrasante, toutes les entrées de H à
   l'intérieur de HMAC-H utilisant la clé DST_key ont des préfixes
   distincts des valeurs Z_pad, b_0 et strxor(b_0, b_(i - 1)) à
   l'intérieur de expand_message_xmd.

   Pour les usages de HMAC-H qui instancient un oracle aléatoire
   privé en fixant une clé secrète à forte entropie, la séparation
   de domaine vis-à-vis de expand_message_xmd n'est pas nécessaire.
   Cela s'explique par le fait que, de manière similaire au cas
   ci-dessus, toutes les entrées de H à l'intérieur de HMAC-H
   utilisant cette clé secrète ont presque certainement des préfixes
   distincts de toutes les entrées de H à l'intérieur de
   expand_message_xmd.

   Enfin, cette méthode peut être utilisée avec HKDF-H [RFC5869] en
   fixant l'entrée « salt » de HKDF-Extract à DST_key, calculée
   comme ci-dessus.  Cela assure la séparation de domaine pour
   HKDF-Extract par le même argument que pour HMAC-H utilisant
   DST_key.  De plus, en supposant que la matière de clé d'entrée
   (IKM) fournie à HKDF-Extract présente une entropie suffisamment
   élevée (disons, à la mesure du paramètre de sécurité), l'étape
   HKDF-Expand est séparée par domaine selon le même argument que
   pour HMAC-H avec une clé secrète à forte entropie (puisqu'une
   clé pseudo-aléatoire est exactement cela).

10.8. Niveaux de sécurité visés

Chaque suite cryptographique spécifie un niveau de sécurité visé (en bits) pour la courbe sous-jacente. Ce paramètre garantit que l'instanciation correspondante de hash_to_field est conservatrice et correcte. Nous soulignons que ce paramètre n'est qu'une borne supérieure du niveau de sécurité de la courbe et ne constitue ni une garantie ni une approbation de son adéquation à une application donnée. Les avancées mathématiques et cryptographiques peuvent réduire le niveau de sécurité effectif de n'importe quelle courbe.