Tester et valider les implémentations de RNG

Les tests des générateurs de nombres aléatoires se heurtent à une difficulté fondamentale : les séquences véritablement aléatoires et les séquences pseudo-aléatoires produites par un bon PRNG semblent identiques pour les tests statistiques. Aucun test portant sur une longueur finie ne peut prouver qu'une séquence est aléatoire ; les statistiques peuvent seulement détecter un caractère non aléatoire avec un certain degré de confiance. Les tests vérifient qu'un RNG ne présente pas de biais ou de motifs évidents, mais ils ne peuvent pas prouver sa sécurité cryptographique. Les tests des RNG cryptographiques poursuivent deux objectifs distincts : (1) la qualité statistique — vérifier que la distribution de la sortie semble uniforme et indépendante ; (2) la robustesse cryptographique — vérifier que l'algorithme DRBG est correctement implémenté et que ses garanties de sécurité tiennent. Ces objectifs nécessitent des méthodes de test différentes.

NIST SP 800-22 fournit 15 tests statistiques pour évaluer des séquences de bits. Ces tests comprennent : le test de fréquence (à un bit) — la proportion de 1 doit être proche de 0,5 ; le test de fréquence par blocs — la fréquence des 1 dans chaque bloc de m bits ; le test des séries — le nombre de séries ininterrompues de bits identiques ; le test de la plus longue série — la longueur de la plus longue série de 1 ; le test du rang de matrices binaires — le rang de matrices binaires formées à partir de la séquence ; le test spectral (DFT) — la détection de motifs périodiques ; la recherche de motifs chevauchants — le comptage des occurrences de motifs précis ; le test statistique universel de Maurer — compresser la séquence et mesurer de combien elle raccourcit. Chaque test produit une valeur p ; p < 0.01 suggère un caractère non aléatoire. Les tests s'effectuent sur 1 million à 1 milliard de bits.

TestU01 (L'Ecuyer et Simard, 2007) est une batterie complète de tests statistiques largement utilisée par la communauté des RNG. SmallCrush : 10 tests, environ 35 secondes, pour des vérifications rapides. Crush : 144 tests, environ 2 heures. BigCrush : 160 tests, environ 24 heures. Les tests BigCrush détectent des corrélations subtiles que NIST SP 800-22 ne détecte pas. Les DRBG cryptographiques bien conçus, comme HMAC_DRBG et CTR_DRBG, réussissent BigCrush sans difficulté : leur sortie est calculatoirement indiscernable d'une sortie aléatoire pour des algorithmes en temps polynomial. Les PRNG non cryptographiques, comme Mersenne Twister et les générateurs congruentiels linéaires, échouent à certains tests BigCrush. Un échec à BigCrush indique fortement que le RNG ne devrait pas être utilisé à des fins cryptographiques.

SP 800-90B et 90A définissent des tests de bon fonctionnement que les DRBG doivent exécuter en continu pendant leur fonctionnement. Test continu du RNG (CRNGT) : chaque bloc produit est comparé au bloc précédent ; s'ils sont égaux (RNG bloqué), le DRBG doit passer dans un état d'erreur et cesser de produire des données. Test de comptage des répétitions : si des échantillons consécutifs présentent la même valeur un nombre de fois supérieur à ce qui est attendu statistiquement compte tenu de l'estimation d'entropie, le test échoue. Test de proportion adaptative : si la valeur la plus fréquente apparaît dans une fenêtre plus souvent qu'un seuil donné, le test échoue. Ces tests de bon fonctionnement détectent les défaillances des sources d'entropie, comme un capteur bloqué ou une défaillance matérielle du HWRNG, avant qu'elles ne compromettent à leur insu la génération de clés cryptographiques.

PractRand est un outil moderne de test des RNG conçu pour une évaluation en ligne, ou en flux, qui analyse la séquence au fur et à mesure de sa génération au lieu d'exiger une longueur prédéterminée. Il applique notamment des tests d'écart, des tests de distribution des bits et des tests spectraux avec une précision adaptative. PractRand est particulièrement efficace pour détecter les RNG qui produisent de bonnes séquences courtes, mais révèlent des motifs sur des milliards de bits. Les DRBG cryptographiques produisent une sortie que PractRand ne peut pas distinguer de l'aléatoire, quelle que soit sa longueur ; il s'agit de la définition opérationnelle de l'indiscernabilité calculatoire. PractRand sert également à évaluer des sources d'entropie, en testant la sortie de /dev/urandom et la sortie de RDRAND, afin de détecter des défaillances matérielles ou des biais systématiques.

Le Programme de validation des algorithmes cryptographiques (CAVP) fournit des vecteurs de test officiels pour les DRBG de SP 800-90A. Les tests CAVP consistent à soumettre une implémentation au système de tests automatisé de NIST avec des vecteurs de test à réponse connue (KAT) : à partir d'une entrée d'entropie, d'un nonce, d'une chaîne de personnalisation et d'une entrée supplémentaire donnés, l'implémentation doit produire exactement les bits de sortie attendus. Le CAVP ne teste pas les propriétés statistiques ; il teste la correction algorithmique. La certification FIPS 140-3 exige la validation CAVP de tous les algorithmes cryptographiques utilisés dans le périmètre du module. Les vecteurs de test CAVP sont accessibles au public sur le serveur ACVP de NIST et sont intégrés aux suites de tests d'OpenSSL, de mbedTLS et de BoringSSL.

Avant de pouvoir initialiser un DRBG de manière sécurisée, sa source d'entropie doit être validée. SP 800-90B définit : (1) l'estimation de l'entropie — mesurer l'entropie réelle par bit au moyen de tests statistiques, notamment l'estimation de la min-entropie ; (2) les tests au démarrage — vérifier que la source d'entropie produit une sortie valide avant sa première utilisation ; (3) les tests à la demande — tests facultatifs déclenchés par l'application ; (4) les tests de bon fonctionnement de la source de bruit — détecter la dégradation du matériel. Sources d'entropie courantes et entropie estimée par bit : RDRAND/RDSEED du CPU (environ 1 bit par bit, matériel certifié) ; /dev/urandom (combine plusieurs sources, avec une estimation prudente de l'entropie) ; TRNG à oscillateur en anneau (0,5 à 0,9 bit par bit selon la conception) ; bruit de l'ADC (0,1 à 0,5 bit par bit). La validation selon SP 800-90B exige des tests en laboratoire avec du matériel spécialisé.

Les environnements virtuels introduisent des difficultés particulières pour les tests des RNG. Les VM peuvent être confrontées à des conditions de faible entropie au démarrage (aucun événement matériel) ou après la restauration d’un instantané (réinitialisation de l’état). Les conteneurs Docker partagent le RNG du noyau hôte — un conteneur ne peut pas tester directement la qualité de l’entropie sous-jacente. Tests pour les déploiements sur VM : (1) Mesurer le temps nécessaire à la fin de la lecture de /dev/random — de longues attentes indiquent une entropie insuffisante. (2) Rechercher les UUID ou clés dupliqués générés en parallèle par des instances de VM (un mode de défaillance réel documenté dans des déploiements en nuage). (3) Vérifier que VIRTIO-RNG (virtio_rng.ko) est chargé dans les VM — cela fournit une injection d’entropie de l’hôte vers l’invité. (4) Auditer la séquence de démarrage de l’application : la génération de clés a-t-elle lieu avant que suffisamment d’entropie soit disponible ?

Les tests de sûreté en cas de duplication de processus empêchent une vulnérabilité subtile : lorsqu’un processus se duplique, le processus parent et le processus enfant partagent le même état du DRBG, ce qui les amène à générer des séquences identiques. Détection : lancer N processus enfants, générer un UUID dans chacun et vérifier que tous les UUID sont uniques. Si deux UUID correspondent, le RNG n’est pas sûr en cas de duplication. OpenSSL a corrigé un bogue de sûreté lors d’une duplication en 2020 (CVE-2020-1971 ne concernait pas directement le DRBG, mais le schéma est similaire). OpenSSL utilise actuellement une mise à jour de graine fondée sur le PID : si le PID a changé depuis le dernier appel (ce qui indique une duplication), le DRBG est automatiquement réensemencé. Pour vérifier cela : exécutez le test avant et après une duplication, puis confirmez que le réensemencement a eu lieu en vérifiant que les sorties sont distinctes.

Une liste de contrôle pratique pour auditer les implémentations de RNG : (1) Le RNG est-il initialisé à partir de l’OS (getrandom, BCryptGenRandom), plutôt qu’à partir de graines fondées sur l’heure ? (2) Le type de DRBG est-il un mécanisme approuvé par NIST SP 800-90A (Hash, HMAC, CTR) ? (3) La longueur de la graine est-elle suffisante pour le niveau de sécurité revendiqué ? (4) Le réensemencement est-il déclenché périodiquement ou après un nombre fixe d’appels à la génération ? (5) L’implémentation gère-t-elle la sûreté en cas de duplication (réensemencement après duplication) ? (6) Les tests de santé sont-ils activés et arrêtent-ils le système en cas d’échec ? (7) L’état est-il remis à zéro à l’arrêt ? (8) Les vecteurs de test CAVP sont-ils exécutés dans l’intégration et le déploiement continus ? (9) Les estimations d’entropie sont-elles documentées et validées ? (10) Pour les exigences FIPS : le module est-il certifié FIPS 140-3 ?

Les défaillances historiques des RNG montrent l’importance de l’enjeu. Debian OpenSSL (2006-2008) : un correctif a accidentellement supprimé deux lignes de code de collecte d’entropie, réduisant le réservoir de graines à un espace de PID de 15 bits — seulement 32 767 clés SSH possibles ont été générées pour l’ensemble des utilisateurs de Debian. Toutes les clés d’hôte SSH et les clés utilisateur générées par Debian ont dû être remplacées. Portefeuilles Bitcoin Android (2013) : SecureRandom utilisait un ensemencement au niveau de Java qui échouait sur certains appareils, ce qui provoquait des valeurs k dupliquées dans les signatures ECDSA — révélant directement les clés privées. Sony PS3 (2010) : utilisait un nonce constant dans la signature du micrologiciel ECDSA, ce qui permettait d’extraire la clé privée à partir de deux signatures (le même k pour des messages différents révèle la clé par une simple manipulation algébrique).

Lequel des tests suivants détecte qu’un DRBG pourrait produire une sortie bloquée (la même valeur de façon répétée) ?

Les tests statistiques (NIST SP 800-22, TestU01 BigCrush, PractRand) vérifient la qualité de la sortie, mais ne peuvent pas prouver la sécurité cryptographique. Les tests à réponse connue CAVP vérifient la correction algorithmique des implémentations de SP 800-90A. Les tests de source d’entropie de SP 800-90B (estimation de la min-entropie, tests de santé) valident l’entrée de la graine. Le test continu du RNG (CRNGT) détecte en temps réel une sortie bloquée. Les déploiements sur VM et en conteneurs nécessitent une injection d’entropie (VIRTIO-RNG) et des vérifications de l’entropie au démarrage. Les tests de sûreté en cas de duplication vérifient que les processus enfants n’héritent pas de l’état du DRBG. Les défaillances réelles (Debian, Android) montrent que les bogues de RNG entraînent directement la compromission de clés cryptographiques. Les listes de contrôle d’audit formalisent ces vérifications pour les déploiements en production.