# Étirement de clé

En cryptographie, l'étirement de clé (en anglais, key stretching) est une technique utilisée pour augmenter la résistance d'une clé faible, généralement un mot de passe ou une phrase secrète. L'étirement de clé augmente la résistance d'une clé à une attaque par force brute en augmentant le temps nécessaire pour tester chaque clé possible. Les mots de passe ou les phrases secrètes créés par les humains sont souvent assez courts ou prévisibles, ce qui facilite leur cassage. L'étirement de clé rend ces attaques plus difficiles.
Les techniques d'étirement fonctionnent généralement de la façon suivante. La clé initiale est entrée dans un algorithme qui produit une clé améliorée. La clé améliorée doit être de taille suffisante pour qu'il soit impossible de la découvrir au moyen d'une attaque par force brute (par exemple, elle doit avoir au moins 128 bits). L'algorithme d'étirement doit être sécurisé, c'est-à-dire qu'il ne doit pas y avoir de moyens connus de calculer la clé améliorée avec un algorithme requérant moins de temps de processeur.
L'attaquant qui veut découvrir une clé étirée a deux options : soit essayer toutes les combinaisons possibles de la clé étirée (impossible si la clé est assez longue), soit essayer toutes les combinaisons possibles de caractères de la clé initiale en les étirant puis en les testant. Dans cette seconde approche, si la clé initiale est un mot de passe, l'attaquant procédera habituellement de la façon suivante : tout d'abord, il essayera chaque mot d'une liste de mots de passe communs, puis chaque mot du dictionnaire, et finalement toutes les combinaisons possibles de caractères du mot de passe. L'étirement des clés n'empêche pas cette approche, mais l'attaquant devra y consacrer beaucoup de temps, car il doit étirer chaque mot de passe possible et l'étirement est conçu pour prendre un temps significatif.
Si l'attaquant utilise la même classe de matériel que l'utilisateur, chaque tentative prendra le même temps que l'utilisateur a pris pour étirer la clé (ce temps est habituellement de l'ordre d'une seconde). Même si l'attaquant dispose de ressources informatiques beaucoup plus grandes, l'étirement de clé le ralentira énormément, car l'ordinateur de l'utilisateur n'a qu'à calculer la fonction d'étirement une fois pour traiter un mot de passe alors que l'attaquant doit la calculer pour chaque tentative de l'attaque.
Il existe plusieurs façons d'effectuer l'étirement de clé. Par exemple, une fonction de hachage cryptographique ou un chiffrement par bloc peuvent être appliqués de manière répétée. Dans les applications où la clé est utilisée pour un chiffrement par bloc, la key schedule dans le chiffrement peut être programmée de sorte qu'elle prenne un certain temps à s'effectuer pour ralentir le processus et rendre le cassage de la clé extrêmement long.
Une technique connexe, le salage, protège contre les compromis temps-mémoire et est souvent utilisée en conjonction avec l'étirement de clé.

## Étirement de clé à base de hachage

De nombreuses bibliothèques fournissent des fonctions d'étirement de clé (par exemple, voir Crypt (C) (en)). PBKDF2 est destiné à générer une clé de chiffrement à partir d'un mot de passe, il n'est pas destiné à l'authentification par mot de passe. PBKDF2 peut être utilisé pour ces deux buts si le nombre de bits de sortie est inférieur ou égal au nombre de bits de l'algorithme de hachage interne utilisé dans PBKDF2 qui est habituellement SHA-1 (160 bits) ou s'il est utilisé comme clé de chiffrement pour chiffrer des données statiques.

## Quelques exemples

Les exemples suivants supposent qu'un ordinateur personnel peut faire environ 65 000 hachages SHA-1 en une seconde en utilisant du code compilé. Ainsi, un programme qui utilise un algorithme d'étirement de clé incluant 65 000 hachages retardera l'utilisateur durant environ une seconde pour chaque étirement.
Le test d'un mot de passe ou d'une phrase secrète nécessite généralement une opération de hachage. Donc, si l'étirement de clé a été utilisé, l'attaquant doit calculer une clé étirée pour chaque clé qu'il teste, ce qui signifie qu'il doit effectuer 65 000 hachages pour chaque test. Cela augmente la charge de travail de l'attaquant d'un facteur de 65 000, soit environ 2$^{16}$. Cela signifie que la clé étirée ajoute environ 16 bits supplémentaires dans la force de la clé.
La loi de Moore indique que la vitesse des ordinateurs double à peu près toutes les 1,5 année. Cela signifie que, toutes les 1,5 année, il est possible de casser un mot de passe d'un bit de plus. Conséquemment, les 16 bits supplémentaires de sécurité fournis par l'étirement de clé permettent de repousser le cassage de la clé d'environ 16 × 1.5 = 24 années.
La loi de Moore signifie également que le nombre d'itérations de hachage de la fonction d'étirement doit être doublé toutes les 1,5 année pour maintenir le même niveau de sécurité. Pour éviter cette modification annuelle, les clés sont conçues pour être plus sécuritaires que nécessaire pour assurer leur sécurité dans le temps. En particulier, un système qui nécessite des clés étirées constantes dans le temps ne peut pas mettre à jour facilement le nombre d'itérations utilisées dans l'étirement des clés. Dans ce cas, le concepteur du système doit prendre en considération le temps de vie du système pour choisir un nombre d'itérations suffisant pour assurer la sécurité du système durant toute sa vie.
Les fonctions de hachage basées sur la saturation du processeur (CPU-bound) sont toujours vulnérables aux implémentations matérielles. De telles implémentations de SHA-1 existent et utilisent seulement 5000 fonctions logiques (gates) et 400 cycles d'horloge. Avec des circuits logiques programmables (FPGA) de plusieurs millions de fonctions logiques coûtant moins de 100 $, un attaquant peut construire un casseur de mots de passe entièrement déroulé pour environ 5 000 $. Une telle machine, cadencée à 100 MHz, peut faire environ 300 000 itérations de hachage par seconde. Un attaquant peut choisir le compromis qui lui convient entre le prix et la vitesse de son casseur, par exemple, il peut remplacer la machine précédente par une machine de 2 500 $ qui peut effectuer 150 000 itérations de hachage par seconde. L'étirement de clé est efficace pour ralentir un casseur matériel : un casseur de 5 000 $ attaquant un hachage SHA-1 standard à une vitesse de 300 000 itérations par seconde ne testerait que 300 000/2$^{16}$ = 4,6 mots de passe par seconde.
Pour se défendre contre une attaque par matériel personnalisé, des fonctions cryptographiques liées à la saturation de la mémoire vive ont été développées. Elles accèdent à de grandes quantités de mémoire d'une manière imprévisible, de sorte que les caches sont inefficaces. Comme de grandes quantités de mémoire vive à faible latence sont coûteuses, un attaquant potentiel est considérablement dissuadé.
Une faiblesse existe dans les algorithmes d'étirement de clé basés sur le hachage qui utilisent une fonction de hachage itérative. Cette attaque est connue comme une attaque d'état transférable (transferable state attack). L'attaque implique le transfert de l'état du hachage précédent dans les hachages itérés directement dans la prochaine itération. Cette méthode peut diminuer le temps nécessaire pour étirer la clé de 80 à 90 %. Cette attaque a été mise en œuvre pour SHA-256.

## Histoire

La première fonction d'étirement de clé délibérément lente (la fonction CRYPT) a été décrite en 1978 par Robert Morris pour chiffrer des mots de passe Unix. Pour cette fonction, il a utilisé 25 itérations, un sel de 12 bits et une variante de DES comme sous-fonction (la fonction DES elle-même n'a pas été utilisée pour ne pas permettre des attaques utilisant des équipements spécifiquement conçus pour casser des chiffrements DES). Les mots de passe étaient limités à un maximum de huit caractères ASCII. Alors que la fonction représentait un grand progrès pour son temps, CRYPT(3) est maintenant considéré comme insuffisant. Le nombre d'itérations, conçu pour l'ère PDP-11, est trop faible, 12 bits de sel est un inconvénient, mais n'arrête pas les attaques par dictionnaire précalculées, et la limite de 8 caractères empêche l'utilisation de mots de passe et de phrases secrètes forts.
Les fonctions modernes d'étirement de clé basées sur des mots de passe, telles que PBKDF2, utilisent un hachage cryptographique tel que MD5 ou SHA1, un sel plus long (par exemple, 64 bits) et un nombre d'itérations élevé (dizaines ou centaines de milliers).
En 2009, un algorithme de renforcement des clés à haute intensité de mémoire, scrypt, a été introduit dans le but de contrer l'utilisation de matériel personnalisé et hautement parallèle pour casser des clés$^,$.
En 2013, le Password Hashing Competition a été organisé afin de sélectionner une norme d'étirement de clé améliorée qui résisterait aux attaques des processeurs graphiques et du matériel personnalisé. Le gagnant, Argon2, a été annoncé le 1er juillet 2015.

## Quelques systèmes utilisant l'étirement de clé

* Certains logiciels de chiffrement de disque (mais pas tous)
* Les gestionnaires de mots de passe open source KeePass, KeePassX et Password Safe (en)
* Les logiciels de chiffrement PGP et GPG
* Les protocoles de chiffrement Wi-Fi WPA et WPA2 en mode personnel