scrypt

En cryptographie , scrypt (prononcé « ess crypt » ) est une fonction de dérivation de clés basée sur un mot de passe , créée par Colin Percival en mars 2009, initialement pour le service de sauvegarde en ligne Tarsnap . L'algorithme a été spécifiquement conçu pour rendre coûteuses les attaques matérielles personnalisées à grande échelle , en exigeant une grande quantité de mémoire. En 2016, l'algorithme scrypt a été publié par l'IETF sous la référence RFC 7914. Une version simplifiée de scrypt est utilisée comme schéma de preuve de travail par plusieurs cryptomonnaies ; elle a été implémentée pour la première fois par un programmeur anonyme du nom d'ArtForz dans Tenebrix, puis rapidement adoptée par Fairbrix et Litecoin .

Une fonction de dérivation de clé basée sur un mot de passe (KDF basée sur un mot de passe) est généralement conçue pour être gourmande en ressources de calcul, ce qui explique son temps d'exécution relativement long (de l'ordre de plusieurs centaines de millisecondes). Les utilisateurs légitimes n'ont besoin d'exécuter cette fonction qu'une seule fois par opération (par exemple, pour l'authentification), le temps requis est donc négligeable. En revanche, une attaque par force brute nécessiterait probablement d'exécuter cette opération des milliards de fois, auquel cas le temps d'exécution devient significatif et, idéalement, prohibitif.

Les fonctions de détermination de clés (KDF) basées sur les mots de passe (comme la populaire PBKDF2 de RSA Laboratories ) sont peu gourmandes en ressources, ne nécessitant ni matériel sophistiqué ni grande quantité de mémoire. Leur implémentation matérielle (sur ASIC ou FPGA , par exemple ) est donc simple et économique. Un attaquant disposant de ressources suffisantes peut ainsi lancer une attaque parallèle à grande échelle en créant des centaines, voire des milliers, d'implémentations matérielles de l'algorithme et en faisant explorer à chacune un sous-ensemble différent de l'espace des clés. Le temps nécessaire à une attaque par force brute est ainsi divisé par le nombre d'implémentations disponibles, ce qui peut le ramener à un délai raisonnable.

La fonction scrypt est conçue pour contrer de telles tentatives en augmentant les besoins en ressources de l'algorithme. Plus précisément, cet algorithme est conçu pour utiliser une grande quantité de mémoire par rapport aux autres fonctions de dérivation de clés (KDF) basées sur les mots de passe , ce qui rend la taille et le coût d'une implémentation matérielle beaucoup plus élevés et limite donc le degré de parallélisme qu'un attaquant peut exploiter, pour un budget donné.

Les importants besoins en mémoire de scrypt proviennent d'un vecteur volumineux de chaînes binaires pseudo-aléatoires générées par l'algorithme. Une fois ce vecteur généré, ses éléments sont traités dans un ordre pseudo-aléatoire et combinés pour produire la clé dérivée. Une implémentation simple nécessiterait de conserver l'intégralité du vecteur en mémoire vive afin de pouvoir y accéder à la demande.

Comme les éléments du vecteur sont générés algorithmiquement, chaque élément peut être créé à la volée selon les besoins, ne stockant qu'un seul élément en mémoire à la fois et réduisant ainsi considérablement les besoins en mémoire. Cependant, la génération de chaque élément est volontairement coûteuse en calcul, et ces éléments sont susceptibles d'être utilisés fréquemment au cours de l'exécution de la fonction. Il existe donc un compromis important en termes de vitesse d'exécution afin de minimiser les besoins en mémoire.

Ce type de compromis temps-mémoire est fréquent dans les algorithmes informatiques : on peut augmenter la vitesse au prix d'une consommation de mémoire plus importante, ou réduire la mémoire requise au prix d'un plus grand nombre d'opérations et d'un temps d'exécution plus long. L'idée derrière scrypt est de rendre délibérément ce compromis coûteux dans les deux sens. Ainsi, un attaquant pourrait utiliser une implémentation peu gourmande en ressources (et donc massivement parallélisable à moindre coût) mais très lente, ou une implémentation plus rapide mais très gourmande en mémoire et donc plus coûteuse à paralléliser.

Entrées de la fonction scrypt  : Cet algorithme utilise les paramètres suivants : Phrase secrète :  Chaîne d’octets contenant les caractères à hacher. Sel :  Chaîne d’octets contenant des caractères aléatoires qui modifie le hachage pour se protéger contre les attaques par table arc-en-ciel. Facteur de coût (N) : Paramètre entier représentant  le coût CPU/mémoire – Doit être une puissance de 2 (ex. : 1024). Facteur de taille de bloc (r) :  Paramètre entier représentant la taille des blocs, qui ajuste la taille et les performances de lecture séquentielle de la mémoire (8 est couramment utilisé). Facteur de parallélisation (p) : Paramètre entier représentant  le niveau de parallélisation (1 à 2<sup> 32 </sup> – 1 * hLen/MFlen) . Longueur de clé souhaitée (dkLen) :  Longueur de clé souhaitée en octets. (Longueur de sortie prévue en octets de la clé dérivée ; Un entier positif tel que dkLen ≤ (2 <sup>32 </sup> − 1) * hLen. hLen : Entier. La longueur en octets de la fonction de hachage (32 pour SHA256). MFlen : Entier. La longueur en octets de la sortie de la fonction de mélange ( SMix ci-dessous). Définie comme r * 128 dans la RFC 7914. Sortie : DerivedKey : Tableau d’octets, DesiredKeyLen longÉtape 1. Générer un bloc de sel coûteux BlockSize ← 128*BlockSizeFactor  // Longueur (en octets) de la sortie de la fonction de mélange SMix (par exemple 128*8 = 1024 octets)Utilisez PBKDF2 pour générer 128 * BlockSizeFactor * p octets de données initiales (par exemple, 128 * 8 * 3 = 3072 octets). Traitez le résultat comme un tableau de p éléments, chaque entrée représentant la taille du bloc en octets (par exemple, 3 éléments de 1024 octets chacun). [B 0 ...B p−1 ] ← PBKDF2 HMAC-SHA256 ( Phrase secrète , Sel , 1, BlockSize * ParallélisationFactor) Mélanger chaque bloc B fois en utilisant la fonction ROMix (chaque bloc peut être mélangé en parallèle) pour i ← 0 à p-1 faire B i ← ROMix(B i , CostFactor) Tous les éléments de B constituent notre nouveau sel « cher » : selCher ← B 0 ∥B 1 ∥B 2 ∥ ... ∥B p-1 // où ∥ désigne la concaténationÉtape 2. Utilisez PBKDF2 pour générer le nombre d'octets souhaité, mais en utilisant le sel coûteux que nous venons de générer, renvoyez PBKDF2 HMAC-SHA256 (Passphrase, expensiveSalt, 1, DesiredKeyLen) ;

Où PBKDF2(P, S, c, dkLen)la notation est définie dans la RFC 2898, où c est un nombre d'itérations.

Cette notation est utilisée par la RFC 7914 pour spécifier une utilisation de PBKDF2 avec c = 1.

Fonction ROMix(Bloc, Itérations) Créer des copies itératives de X X ← Bloc pour i ← 0 à Itérations−1 faire V i ← X X ← BlockMix(X) pour i ← 0 à Itérations−1 faire j ← Intégrer(X) modulo Itérations X ← BlockMix(X xor V j ) retourner X 

Où RFC 7914 définit Integerify(X)comme le résultat de l'interprétation des 64 derniers octets de X comme un entier petit-boutiste A ₁ .

Étant donné que le nombre d'itérations est égal à 2 à la puissance N, seuls les premiersCeiling(N / 8) octets parmi les 64 derniers octets de X, interprétés comme un entier petit-boutiste A ₂ , sont réellement nécessaires pour calculer . Integerify(X) mod Iterations = A1 mod Iterations = A2 mod Iterations

Fonction BlockMix(B) : Le bloc B est composé de blocs de 128 octets (ce qui équivaut à 2r blocs de 64 octets). r ← Longueur (B) / 128 ; Considérez B comme un tableau de 2r blocs de 64 octets [B 0 ...B 2r-1 ] ← B X ← B 2r−1 pour i ← 0 à 2r−1 faire X ← Salsa20/8(X xor B i ) // Salsa20/8 hache de 64 octets vers 64 octets Y i ← X retour ← Y 0 ∥Y 2 ∥...∥Y 2r−2 ∥ Y 1 ∥Y 3 ∥...∥Y 2r−1

Où Salsa20/8 est la version à 8 manches de Salsa20 .

Scrypt est utilisé dans de nombreuses cryptomonnaies comme algorithme de preuve de travail (plus précisément, comme fonction de hachage dans l' algorithme de preuve de travail Hashcash ). Il a été implémenté pour la première fois dans Tenebrix (lancé en septembre 2011) et a servi de base à Litecoin et Dogecoin , qui ont également adopté son algorithme Scrypt. Le minage des cryptomonnaies utilisant Scrypt est souvent effectué sur des processeurs graphiques ( GPU ), car ces derniers offrent généralement une puissance de calcul nettement supérieure (pour certains algorithmes) à celle des processeurs (CPU). Cette situation a entraîné une pénurie de GPU haut de gamme en raison de la hausse du prix de ces cryptomonnaies en novembre et décembre 2013.

L'utilitaire scrypt a été écrit en mai 2009 par Colin Percival comme démonstration de la fonction de dérivation de clé scrypt. Il est disponible dans la plupart des distributions Linux et BSD .