Je commence doucement à comprendre comment fonctionnent les générateurs de nombres pseudo-aléatoires (PRNG) et à voir quel est leur impact dans la sécurité informatique. En bref : la sécurité repose sur eux, trouver une faille dans le générateur revient à compromettre la sécurité !
Utilisations des PRNG
Cas où les PRNG empêchent qu'un espion puisse lire ou injecter des données dans un canal de communication (connexion réseau) :
- L'établissement d'une connexion SSL (https dans firefox) ou SSH utilise un PRNG pour générer des clés de session
- La sécurité du protocole TCP repose sur un PRNG
Cas où un PRNG sert à prouver l'identité d'une personne :
- Création d'un mot de passe (ex: programme pwgen) ou d'une clé SSH utilisés pour l'authentification
- Création d'un certificat X.509 (ex: identité d'un serveur avec https)
- Création de clés GPG (courriels)
- etc.
Attaquer la graine
La graine est un nombre de N bits utilisé pour construire l'état interne (M bits) du PRNG. N est souvent plus petit que M. Exemple : time(NULL), 32 bits voir beaucoup moins, est utilisé pour construire l'état interne de l'algorithme Mersenne Twister (20.000 bits). Il est plus facile de deviner N bits que M (32 vs 20.000 dans le cas de Mersenne Twister), c'est donc la première cible.
Obtenir la graine permet de reconstruire l'état interne initial complet.
Cas réel :
- Dans la faille OpenSSL Debian, la valeur réelle de N était 15 : ce qui donne seulement 32.768 graines différentes
- DSA-152-1 l2tpd -- missing random seed : la graine était tout simplement constante...
Une graine basée uniquement que sur time(NULL), getpid() et getppid() ne peut être utilisée dans un contexte de sécurité. Il faut utiliser de vraies sources d'entropies (ex: /dev/random sous Linux).
Reconstruire l'état interne
Si un attaquant arrive à obtenir suffisamment de bits générés par le PRNG, il pourra reconstruire l'état interne du PRNG. Dans le cas de Mersenne Twister, il suffit de 19.937 bits (ou 624 nombres de 32 bits) pour reconstruire l'état interne complet.
Pour éviter qu'un attaquant puisse reconstruire l'état interne du PRNG à partir de bits générés, on peut utiliser une fonction de hachage (ex: SHA-1) sur sa sortie. Un attaquant devra inverser la fonction SHA-1 pour obtenir l'état interne (ce qui est possible mais très coûteux).
Biais dans un générateur
Pour générer un nombre pseudo-aléatoires dans un intervalle, un mauvais PRNG va produire certaines valeurs plus fréquemment. En connaissant le biais, l'attaquant peut gagner du temps en testant ces valeurs en priorité.
Un bon PRNG donne une distribution uniforme : chaque nombre doit sortir avec une probabilité identique. Assurez-vous que le PRNG passe tous les tests statistiques connus (ex: Mersenne Twister ne passe pas tous les tests de Dieharder).
Porte dérobée dans un générateur
Il a été prouvé (lire Des Trappes dans les Clés) qu'il est possible de construire un PRNG valide (passant tous les tests statistiques) possédant une porte dérobée. Son auteur peut alors calculer les nombres générés sans pour autant connaître la graine. En pratique, l'attaquant devra toujours effectuer une recherche par force brute, mais avec un coût très inférieur au coût classique de recherche exhaustive (ex: 2^32 au lieu de 2^256).
La porte dérobée peut être introduite au niveau algorithmique (ex: On the Possibility of a Back Door in the NIST SP800-90 Dual EC PRNG) ou bien dans une implémentation.
Limiter l'effet d'une attaque dans le temps
Casser un PRNG permet de :
- Calculer les nombres précédemment générés (passé)
- Calculer les nombres qui vont être générés (futur)
L'opération de regénération de la graine, appelée reseed, limite la portée d'une attaque. Cette opération peut se faire après avoir généré N bits (ex: générer 1000 mots de passe) ou alors une fois que le pool d'entropie a atteint un certain seuil (dépend des générateurs matériels et non plus de la quantité de bits pseudo-aléatoires générés). Un pirate n'aura donc pas accès à tous les mots passe (certificats ou autre) précédents et suivants, mais seulement une partie.
Appeler reseed après chaque nombre généré est une très mauvaise idée si la graine est de mauvaise qualité. Exemple : appeler srand(time(NULL)) après chaque appel à rand() va avoir pour conséquence de générer plusieurs fois le même nombre durant la même seconde. Il est primordial d'utiliser une source ayant une excellente entropie.
Pour en savoir plus : Random number generator attack.
