Version du 24 novembre 2018 à 22:04

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).

Attaques de PRNG

On peut distinguer plusieurs types d'attaques de PRNGs:

L'attaque cryptanalytique directe correspond au fait de se baser sur une partie du flux de valeurs aléatoires fourni par un générateur afin de cerner en quoi il diffère d'un flux de valeurs parfaitement aléatoires.

L'attaque basée sur les inputs signifie que les inputs du générateur sont manipulées afin de l'attaquer. Par exemple, il est possible d'empêcher un générateur d'accumuler assez d'entropie pour qu'il puisse ne pas dévoiler d'informations sur son état actuel.

Les attaques partant d'un générateur compromis correspondent aux attaques qui utilisent la connaissance de l'état interne d'une générateur pour prédire ses prochaines valeurs ou les anciennes.

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.

Bilan

Bons points : Yarrow est un CSPRNG relativement performant et donc concrètement utilisable. Il peut être utilisé par des programmeurs non-expert en cryptographie en restant relativement sécurisé. Son niveau de sécurité dépend fondamentalement des mécanismes cryptographiques utilisés, et ces mécanismes peuvent être simplement remplacés par des choix contextuellement pertinents ou au file de l'évolution des outils cryptographiques.

Limites : Le niveau de sécurité de Yarrow est borné par le niveau de sécurité des mécanismes cryptographiques qu'il utilise : un attaquant capable de craquer son chiffrement pourra craquer le système qui utilise Yarrow. Ce modèle utilise un système d'estimation d'entropie, ce qui se révèle être un challenge au niveau de l'implémentation. A l'origine, il utilisait SHA-1 comme fonction de hachage qui est maintenant considérée comme obsolète.

Fortuna

Fortuna est une évolution du générateur pseudo-aléatoire Yarrow. Il a été crée par Bruce SCHNEIER et Niels FERGUSON, et a été publié en 2003. Il reprend plusieurs idées de Yarrow, notamment ses 3 trois composants principaux, qui sont: l'accumulateur d'entropie, la seed et un générateur de nombre.

L'accumulateur d'entropie

La principal différence entre Fortuna et Yarrow réside dans ses accumulateurs d'entropie.

Dans Yarrow, nous avions deux pools qui stockaient les bits d'entropies que générait le système. Dans Fortuna, nous avons 32 pools (numéroté de P0 à P31). Un pool étant une chaîne de bits de taille non borné. L'idée dans Fortuna est que les différentes sources d'entropies vont distribuer leurs bits d'entropie de façon circulaire entre les différentes pools. C'est à dire que prenons comme source d'entropie une saisie clavier, chaque touche va créer des bits d'entropie, les bits de la première touche iront dans la pool P0, puis ceux de la deuxième entrée iront dans P1, etc. De sorte que la 33ème entrée clavier créera des bits d'entropie stocké dans P0.

Cela permet de répartir les bits générés par les sources d'entropie afin d'avoir des suites de bits plus aléatoires