Génération de nombres aléatoires

Objectif du projet

Le hasard est au cœur des protocoles de sécurité : les nombres aléatoires servent à générer des clés secrètes, des nonces, des vecteurs d'initialisation ou des jetons CSRF. Si la génération est mal faite, un attaquant peut prédire les valeurs suivantes et compromettre tout le système.

Avec deux camarades, j'ai donc implémenté plusieurs algorithmes de génération de nombres aléatoires, mesuré la qualité de leur aléa et réalisé deux attaques à but pédagogique contre les générateurs vulnérables. Ces attaques sont uniquement destinées à l'apprentissage et sont interdites sur des systèmes réels.

Ma démarche

Nous avons procédé en trois temps :

1. Implémenter des générateurs de natures différentes, du plus simple au plus sûr, pour pouvoir les comparer.
2. Évaluer leur qualité avec une suite de tests statistiques.
3. Attaquer les plus faibles pour montrer concrètement ce qu'une mauvaise qualité d'aléa permet à un attaquant.

Réalisation du projet

Les générateurs implémentés

• LCG (générateur congruentiel linéaire) : simple et rapide, basé sur la formule Xn+1 = (a × Xn + c) mod m.
• Mersenne Twister (MT19937) : un générateur de très longue période (2¹⁹⁹³⁷ − 1), très utilisé en simulation.
• Blum Blum Shub : un générateur cryptographiquement sûr, fondé sur le problème de la racine carrée modulaire.
• Hash-DRBG : un générateur déterministe basé sur SHA-256, conforme à la norme NIST SP 800-90A.
• Box-Muller : une transformation qui convertit une distribution uniforme en distribution normale N(0,1).
• NRBG : un générateur qui combine plusieurs sources d'entropie (système, Mersenne Twister et BBS).

L'analyse de la qualité

J'ai écrit une suite de tests statistiques pour comparer les générateurs :

• l'entropie de Shannon, qui mesure la répartition des octets générés (valeur idéale : 8 bits) ;
• le test du χ², qui vérifie l'uniformité de la distribution ;
• le test d'autocorrélation (décalages de 1, 2, 8 et 16), qui détecte les liens entre valeurs successives ;
• le test de Kolmogorov-Smirnov, qui compare la distribution obtenue à une loi uniforme théorique.

Les résultats de tous les générateurs sont exportés dans un rapport texte.

Les attaques pédagogiques

• Sur le LCG : quand les paramètres sont connus, on remonte la séquence jusqu'à la graine initiale. Quand ils sont inconnus, on les retrouve (module par PGCD de différences, multiplicateur par inversion modulaire, incrément par substitution) à partir de quelques sorties consécutives seulement.
• Sur le Mersenne Twister : on inverse la fonction de « tempering » pour retrouver l'état interne. Avec 624 sorties consécutives, on peut reconstituer l'état complet et prédire toutes les sorties suivantes.

Ce que montrent les résultats

• Le Mersenne Twister a d'excellentes propriétés statistiques mais reste prévisible.
• BBS est très bon et sûr, mais lent.
• Le LCG est rapide mais statistiquement faible et facile à attaquer.
• Hash-DRBG offre d'excellentes propriétés cryptographiques et reste recommandé pour un usage sécurisé.

Problèmes rencontrés

• Problème : Un bon score aux tests statistiques ne garantit pas la sécurité : le Mersenne Twister les réussit bien et pourtant il est prévisible.

  Solution : Ne pas me limiter aux tests statistiques et compléter l'analyse par des attaques, pour distinguer un aléa « de bonne qualité » d'un aléa « cryptographiquement sûr ».

• Problème : Retrouver les paramètres d'un LCG quand ils sont inconnus.

  Solution : Exploiter la structure mathématique du générateur : PGCD de différences pour le module, inversion modulaire pour le multiplicateur, puis substitution pour l'incrément.

• Problème : Les générateurs sûrs, comme BBS, sont nettement plus lents que les autres.

  Solution : Accepter ce compromis entre vitesse et sécurité, et choisir le générateur selon l'usage (simulation ou cryptographie).

Ce que j'en retiens

Ce projet m'a montré qu'un générateur peut sembler aléatoire sans être sûr, et qu'il faut choisir son générateur selon l'usage : pour la cryptographie, on privilégie une solution comme Hash-DRBG ou le module secrets de Python, jamais un LCG ou un Mersenne Twister. Il m'a aussi permis de mettre en pratique des notions de mathématiques et de statistiques dans un cadre concret de sécurité informatique.

Projet réalisé avec Noah Mahé et Gatien Andrinirina.