CSPRNG

Les générateurs pseudo-aléatoires (PRNG) sont énormément utilisés en cryptographie, que ce soit pour générer des clés utilisées par des algorithmes de chiffrement symétriques, des salts pour perturber les logiciels de prédiction, des vecteurs d'initialisation utiles lors de l'utilisation de chiffrements par bloc en chaine, etc ...

Les cryptographes développent des algorithmes en se basant sur l'idée qu'on peut effectivement générer des nombres de manière imprévisible. Mais peut-on vraiment soutenir la robustesse d'un algorithme de chiffrement qui se base sur des nombres qu'un attaquant saurait deviner à l'avance ? Autrement dit, à quel point un algorithme peut être sécurisé, s'il est possible pour un attaquant de compromettre le générateur qu'il utilise ? Il apparait alors évidemment qu'un générateur se doit d'être lui aussi robuste et sécurisé.

Nous nous intéressons donc ici à certains modèles de générateurs pseudo-aléatoires crypto-sécurisés (CSPRNG).

Yarrow

Yarrow désigne une famille de PRNG conçue par Bruce Schneier, John Kelsey et Niels Ferguson en 1999, dont le nom fait référence à d'anciens rites de divination.

Le modèle Yarrow se divise en 3 composants principaux : un accumulateur d'entropie, un mécanisme de reseed et un générateur à proprement parler (+ problème des anniversaires).

Accumulateur d'entropie

Yarrow comporte 2 boîtes (pool) dédiées à stocker les bits aléatoires issus de sources d'entropie. Typiquement, ces bits proviennent du système d'exploitation de la machine et du materiel en lui même (exemples : timing exacts de pression des touches, trajectoire du pointeur, ...). Pour les remplir, il va donc être question d'estimer la quantité d'entropie présente dans un apport. Cela dit, elles possèdent chacune une fonction d'estimation d'entropie qui lui est propre. L'une est qualifiée de rapide car la fonction d'estimation qui l'accompagne est plutôt optimiste quant à la quantité d'entropie qu'elle récupère dans un apport. L'autre est plus lente car plus conservatrice en entropie. Ces pool contiennent des données hashées, ce qui leur permet de perturber un attaquant qui voudrait obtenir de l'information dessus en contrôlant certaines sources d'entropie.

Reseed

Le reseed est l'action d'utiliser l'entropie stockée par les pool afin de modifier la clé privée du générateur. Ce mécanisme doit faire un compromis entre 2 approches. D'une part, il est préférable de reseed souvent afin d'empêcher un générateur compromis à un moment donné de divulguer trop d'informations. Mais d'autre part, on n'a pas toujours une quantité d'entropie suffisante pour être sûr qu'un attaquant ne puisse pas deviner quelles pourraient être les prochaines valeurs générées. C'est pourquoi utiliser trop souvent ce qu'on a accumulé peut mener à une faiblesse du système. C'est ici que l'idée d'avoir 2 pool rentre en jeu : la pool rapide permet d'effectuer des reseed assez régulièrement, et la pool lente permet de garder un taux "d'imprévisibilité" assez élevé.

Générateur

Pour générer des nombres pseudo aléatoires, Yarrow utilise un compteur qui sera incrémenté à chaque fois que l'on aura besoin d'une nouvelle valeur, puis encrypte ce compteur à l'aide d'un mécanisme de chiffrement par bloc qui utilise la clé du générateur. Le problème ici est que selon le problème des anniversaires, un générateur parfaitement aléatoire finira par produire des valeurs qu'il a déjà produite. L'utilisation d'un compteur comme mécanisme de génération empêche de reproduire ce phénomène, ce qui va à l'encontre du principe de génération d'une suite de valeur que l'on ne pourrait dissocier d'une suite de valeurs parfaitement aléatoires. C'est pourquoi il existe un mécanisme de "porte"/"gate" qui va régulièrement rechanger la clé (d'une autre manière que par un reseed) afin de permettre au générateur de renvoyer à l'occasion, des valeurs déjà produites.

Bons points :

Limites :

Sources et Liens utiles

les CSPRNG

Entropie

Article Yarrow (1999)

Wiki Yarrow

Article Fortuna (2003)

Wiki Fortuna

Généralisation de Fortuna (2014)

Wiki Attaques sur les PRNG

Article sur les attaques

Bonus