Worldlex Wiki La cryptographie basée sur le hachage est le terme générique pour les constructions de primitives cryptographiques basées sur la sécurité des fonctions de hachage . Elle présente un intérêt en tant que type de cryptographie post-quantique .
Jusqu'à présent, la cryptographie basée sur le hachage est utilisée pour construire des schémas de signatures numériques tels que le schéma de signature Merkle , des preuves à connaissance nulle et d'intégrité informatique, telles que le système de preuve zk-STARK et des preuves de plage sur des informations d'identification émises via le protocole HashWires . Les schémas de signature basés sur le hachage combinent un schéma de signature à usage unique, tel qu'une signature Lamport , avec une structure arborescente de Merkle . Étant donné qu'une clé de schéma de signature à usage unique ne peut signer qu'un seul message de manière sécurisée, il est pratique de combiner plusieurs de ces clés au sein d'une seule structure plus grande. Une structure arborescente de Merkle est utilisée à cette fin. Dans cette structure de données hiérarchique, une fonction de hachage et une concaténation sont utilisées à plusieurs reprises pour calculer les nœuds de l'arbre.
L'un des aspects à prendre en compte avec les schémas de signature basés sur le hachage est qu'ils ne peuvent signer qu'un nombre limité de messages de manière sécurisée, en raison de leur utilisation de schémas de signature à usage unique. Le National Institute of Standards and Technology (NIST) des États-Unis a précisé que les algorithmes de son concours de cryptographie post-quantique prennent en charge un minimum de 2,64 signatures en toute sécurité.
En 2022, le NIST a annoncé que SPHINCS+ serait l'un des trois algorithmes à normaliser pour les signatures numériques. Le NIST a normalisé en 2020 la cryptographie basée sur le hachage avec état basée sur le schéma de signature Merkle étendu (XMSS) et les signatures Leighton-Micali (LMS), qui sont applicables dans différentes circonstances, mais a noté que l'obligation de maintenir l'état lors de leur utilisation les rend plus difficiles à mettre en œuvre de manière à éviter toute utilisation abusive.
En 2024, le NIST a annoncé la norme de signature numérique basée sur le hachage sans état.
Histoire
Leslie Lamport a inventé les signatures basées sur le hachage en 1979. Les schémas de signature basés sur le hachage XMSS (eXtended Merkle Signature Scheme) et SPHINCS Johannes Buchmann et est basé à la fois sur le schéma fondateur de Merkle et sur le schéma de signature généralisé de Merkle (GMSS) de 2007. Une variante multi-arbre de XMSS, XMSS MT , a été décrite en 2013.
Systèmes de signature unique
Les schémas de signature basés sur le hachage utilisent des schémas de signature à usage unique comme élément de base. Une clé de signature à usage unique donnée ne peut être utilisée que pour signer un seul message de manière sécurisée. En effet, les signatures révèlent une partie de la clé de signature. La sécurité des schémas de signature à usage unique (basés sur le hachage) repose exclusivement sur la sécurité d'une fonction de hachage sous-jacente.
Les schémas de signature à usage unique les plus couramment utilisés incluent le schéma Lamport-Diffie , le schéma Winternitz et ses améliorations, comme le schéma W-OTS + . Contrairement au schéma phare de Lamport-Diffie, le schéma Winternitz et ses variantes peuvent signer plusieurs bits à la fois. Le nombre de bits à signer simultanément est déterminé par une valeur : le paramètre Winternitz. L'existence de ce paramètre permet un compromis entre taille et vitesse. Les valeurs élevées du paramètre Winternitz produisent des signatures et des clés courtes, au prix d'une signature et d'une vérification plus lentes. En pratique, une valeur typique pour ce paramètre est 16.
Dans le cas de signatures basées sur un hachage sans état, des schémas de signature à quelques reprises sont utilisés. De tels schémas permettent de réduire progressivement la sécurité dans le cas où une clé à quelques reprises est utilisée plusieurs fois. HORST est un exemple de schéma de signature à quelques reprises.
Combinaison de plusieurs paires de clés à usage unique dans un schéma de signature basé sur le hachage
L'idée centrale des schémas de signature basés sur le hachage est de combiner un plus grand nombre de paires de clés à usage unique en une seule structure pour obtenir un moyen pratique de signer plusieurs fois (mais un nombre limité de fois). Cela se fait à l'aide d'une structure arborescente de Merkle, avec des variantes possibles. Une clé publique et une clé privée sont construites à partir des nombreuses clés publiques et privées du schéma à usage unique sous-jacent. La clé publique globale est le nœud unique tout en haut de l'arbre de Merkle. Sa valeur est une sortie de la fonction de hachage sélectionnée, donc une taille de clé publique typique est de 32 octets. La validité de cette clé publique globale est liée à la validité d'une clé publique à usage unique donnée à l'aide d'une séquence de nœuds d'arbre. Cette séquence est appelée chemin d'authentification. Elle est stockée dans le cadre de la signature et permet à un vérificateur de reconstruire le chemin du nœud entre ces deux clés publiques.
La clé privée globale est généralement gérée à l'aide d'un générateur de nombres pseudo-aléatoires. Il suffit alors de stocker une valeur de départ. Les clés secrètes à usage unique sont dérivées successivement de la valeur de départ à l'aide du générateur. Avec cette approche, la clé privée globale est également très petite, par exemple généralement 32 octets.
Le problème de la traversée d'arbres est essentiel aux performances de signature. Des approches de plus en plus efficaces ont été introduites, accélérant considérablement le temps de signature.
Certains schémas de signature basés sur le hachage utilisent plusieurs couches d'arbre, offrant une signature plus rapide au prix de signatures plus volumineuses. Dans de tels schémas, seule la couche la plus basse des arbres est utilisée pour signer les messages, tandis que tous les autres arbres signent les valeurs racines des arbres inférieurs.
Le travail de Naor–Yung montre le modèle par lequel transférer une signature temporelle limitée de la famille de types Merkle dans un schéma de signature illimité (régulier).
Propriétés des schémas de signature basés sur le hachage
Les schémas de signature basés sur le hachage reposent sur des hypothèses de sécurité concernant la fonction de hachage sous-jacente, mais toute fonction de hachage répondant à ces hypothèses peut être utilisée. Par conséquent, chaque fonction de hachage adéquate génère un schéma de signature basé sur le hachage correspondant différent. Même si une fonction de hachage donnée devient non sécurisée, il suffit de la remplacer par une autre fonction sécurisée pour obtenir une instanciation sécurisée du schéma de signature basé sur le hachage considéré. Certains schémas de signature basés sur le hachage (tels que XMSS avec génération de clés pseudo-aléatoires) sont sécurisés en aval, ce qui signifie que les signatures précédentes restent valides si une clé secrète est compromise.
La minimisation des hypothèses de sécurité est une autre caractéristique des schémas de signature basés sur le hachage. En général, ces schémas ne nécessitent qu'une fonction de hachage cryptographique sécurisée (par exemple au sens de la résistance à la seconde préimage ) pour garantir la sécurité globale du schéma. Ce type d'hypothèse est nécessaire pour tout schéma de signature numérique ; cependant, d'autres schémas de signature nécessitent des hypothèses de sécurité supplémentaires , ce qui n'est pas le cas ici.
En raison de leur dépendance à un schéma de signature unique sous-jacent, les schémas de signature basés sur le hachage ne peuvent signer qu'un nombre fixe de messages de manière sécurisée. Dans le cas des schémas Merkle et XMSS, un maximum de messages peuvent être signés de manière sécurisée, avec la hauteur totale de l'arbre Merkle.
Exemples de schémas de signature basés sur le hachage
Depuis le schéma initial de Merkle, de nombreux schémas de signature basés sur le hachage avec des améliorations de performances ont été introduits. Les plus récents incluent les schémas XMSS, Leighton-Micali (LMS), SPHINCS et BPQS. La plupart des schémas de signature basés sur le hachage sont avec état , ce qui signifie que la signature nécessite la mise à jour de la clé secrète, contrairement aux schémas de signature numérique conventionnels. Pour les schémas de signature basés sur le hachage avec état, la signature nécessite de conserver l'état des clés à usage unique utilisées et de s'assurer qu'elles ne sont jamais réutilisées. Les schémas XMSS, LMS et BPQS sont avec état, tandis que le schéma SPHINCS est sans état. Les signatures SPHINCS sont plus grandes que les signatures XMSS et LMS. BPQS a été conçu spécifiquement pour les systèmes de blockchain. En plus du schéma de signature unique WOTS+, SPHINCS utilise également un schéma de signature à quelques reprises (basé sur le hachage) appelé HORST. HORST est une amélioration d'un ancien schéma de signature à quelques reprises, HORS (Hash to Obtain Random Subset).
Les schémas basés sur le hachage avec état XMSS et XMSS MT sont spécifiés dans la RFC 8391 (XMSS : eXtended Merkle Signature Scheme). Les signatures basées sur le hachage Leighton-Micali sont spécifiées dans la RFC 8554. Des améliorations pratiques ont été proposées dans la littérature pour atténuer les problèmes introduits par les schémas avec état. Les fonctions de hachage appropriées pour ces schémas incluent SHA-2 , SHA-3 et BLAKE .
Implémentations
Les schémas XMSS, GMSS et SPHINCS sont disponibles dans les API cryptographiques Java Bouncy Castle . Les schémas LMS et XMSS sont disponibles dans les API cryptographiques wolfSSL . SPHINCS est implémenté dans la boîte à outils d'analyse comparative SUPERCOP. Des implémentations de référence optimisées et non optimisées de la RFC XMSS existent. Le schéma LMS a été implémenté en Python et en C suite à son projet Internet.