Évaluation de la qualité des RNGs

Vérification de l’aléatoire sur les RNG

Par définition, un test fournit un moyen de réaliser des décisions quantitatives, basées sur une conjecture de départ, laquelle peut être validée ou pas. Pour cela, nous allons appeler cette hypothèse de départ la condition indexée 0 (ou hypothèse H0). Dans notre contexte des générateurs aléatoires, l’hypothèse au départ H0 sera définie comme étant « La suite analysée n’est pas aléatoire ». Une fois l’hypothèse initiale définie, nous allons maintenant quantifier les résultats des tests en utilisant comme indicateur les valeurs de probabilité aléatoire (valeur-p). L’idée de l’analyse quantitative utilisée implique d’assurer une hypothèse initiale, qui ne peut jamais être acceptée directement, mais qui peut être rejetée seulement par le test statistique. La valeur p est considérée comme la mesure à partir de laquelle les données plaident contre l’hypothèse initiale. Les seuils suivants sont généralement pris en fonction d’un niveau de confiance, exprimé comme (1-α). Ainsi pour : Évaluation de la qualité des RNGs Chapitre 6. Évaluation de la qualité des RNGs – p < α /10 : très forte présomption contre l’hypothèse, – α /10 < p ≤ α /2 : forte présomption contre l’hypothèse, – α /2 < p ≤ α : faible présomption contre l’hypothèse, – p ≥ α : pas de présomption contre l’hypothèse. Si nous revenons à notre étude, l’hypothèse initiale indique que la séquence binaire à évaluer est aléatoire, et nous allons prendre un niveau de confiance du test à 99% (α=0.01), ce qu’implique que nous pouvons tolérer de rejeter une séquence sur 100 dans l’évaluation effectuée. Un nombre de tests standardisés existe, basés sur l’analyse de certaines propriétés statistiques, telles que la distribution uniforme de valeurs et de non répétabilité, permettant de valoriser le caractère non prédictif du générateur sous étude. Nous pouvons donc citer à titre d’exemple : 1

Les Tests de Knuth

Créés par Donald Knuth [21], gouru des valeurs aléatoires au sein d’une époque où l’aléatoire n’avait pas l’importance actuelle pour les applications sécuritaires. Ces tests n’ayant pas été crées pour ces applications, ils n’offrent pas un niveau de confiance suffisant pour les applications cryptographiques. 2. Les Tests de Diehard. Crées par George Marsaglia [28], dans le but d’offrir des tests plus robustes que ceux de Knuth. Toutefois après la retraite de l’auteur, la suite de tests développée a été peu révisée et utilisée. 3. Les Tests Crypt-X. Crées par le centre de recherche en sécurité de l’information de l’Université de technologies de Queensland, et offerts comme une application commerciale pour la vérification sur systèmes de chiffrement de données et générateurs de clés. 4. Les Tests ENT. Développés par John Walker 1 , et appliqués pour l’évaluation des générateurs pseudoaléatoires. Ces outils sont de type statistique disposant d’algorithmes de compression pour des applications à grande quantité d’informations sous observation. 5. Les Tests NIST. Développés par l’Institut National de Standards et Technologie (NIST), ils sont une succession de tests ciblés sur des applications cryptographiques. Ils sont basés sur une synthèse d’algorithmes existants auxquels s’ajoutent d’autres tests basés sur de nouveaux algorithmes créés par l’équipe de sécurité informatique et d’ingénierie statistique du NIST. Cette suite de tests est devenue comme un standard bien reconnu dans le monde des tests de l’aléatoire et du cryptographique. Partant de ces constatations, nous avons donc mis en place les tests proposés par le NIST, basés sur le fait de leurs applications de type cryptographiques. 1. http ://www.fourmilab.ch/random/ 6.3. La suite NIST.

La suite NIST

Afin de répondre aux spécifications attendues, le NIST propose une batterie de tests de validation : FIPS 140-1 et FIPS 140-2. En effet, historiquement, ces deux successions de tests ont été développées comme outils de validation pour les systèmes de cryptage de type AES. Afin de prouver la puissance de ces tests, un DES a déjà été entièrement décrypté. Ainsi, nous allons dans cette partie mentionner de manière synthétique les paramètres de qualification et les tests réalisés, établis au sein d’un document détaillé [40]. Le NIST a développé des tests standardisés ayant comme but l’amélioration sur la protection de la communication de données numériques, de valeurs binaires. Ces tests sont groupés sur deux collections : les FIPS 140-1 et FIPS 140-2, appliquées pour l’évaluation des RNG, ayant comme objectif des données de grande taille.

Méthodologie utilisée

La suite statistique NIST fait appel à 15 tests statistiques qui doivent être réalisés en suivant une démarche, qui consiste à trouver la variation χ 2 (x) d’un paramètre d’intérêt calculé à partir de la séquence binaire sous étude. La suite contient 15 tests : 1. Le test de fréquence globale (monobit) 2. Le test de fréquence par blocs 3. Le test de répétition globale 4. Le test de répétition par blocs 5. Le test de rang de la matrice binaire 6. Le test spectral 7. Le test de non chevauchement de séquences 8. Le test de chevauchement de séquences 9. Le test universel de Maurer 10. Le test de la complexité linéaire 11. Le test Série 12. Le test de l’entropie approximée 13. Les sommes cumulatives 14. L’excursion aléatoire 15. Le variant sur l’excursion aléatoire. Nous allons maintenant étudier le principe des fonctions statistiques en mettant en avant les deux méthodes possibles de validation du caractère aléatoire du signal. Chapitre 6. Évaluation de la qualité des RNGs 6.3.2 Fonctions statistiques utilisées. Les deux méthodes de validation du caractère aléatoire du signal, reposent sur la quantification des fonctions d’erreur erf(x) et sa complémentaire erfc(x) mais également sur l’analyse du paramètre χ 2 . Ainsi, – Lorsque l’analyse de la totalité de la séquence est sous étude, la densité de probabilité d’une suite de valeurs observées est caractérisée par une loi normale définie par : f(x) = 1 σ √ 2π e − (x−µ) 2 2σ (6.1) dont σ et µ, correspondent à la variance et moyenne, respectivement. Une distribution normale standard possède σ = 1 et µ = 0. Ainsi, la fonction de distribution cumulative (cdf) d’une distribution normale, prend la forme : φ(x) = 1 σ √ 2π Z x −∞ e − −t 2 2 dt (6.2) La fonction d’erreur, erf(x), indique la probabilité d’avoir une variable aléatoire avec une distribution normale, de moyenne nulle et variance 1/2. erf(x) = 1 √ π Z x −x e −t 2 dt (6.3) La fonction complémentaire est : erfc(x) = 2 √ π Z ∞ −x e −t 2 dt (6.4) Les deux fonctions, φ et erf peuvent alors être approximées en utilisant la relation : φ(x) = 1 2 [1 + erf( x √ 2 )] (6.5) – La seconde méthode consiste en l’analyse du terme χ 2 en utilisant plusieurs degrés de liberté et en décomposant la séquence d’entrée en blocs. Si nous avons comme hypothèse que les données sont aléatoires, un sous bloc de données sera aussi aléatoire. Ainsi, l’analyse permet d’identifier la présence de patrons ou combinaisons particulières identifiables comme non aléatoires. La fonction Γ est une extension de la fonction factoriel (n!), étendue sur des valeurs réelles positives : Γ(z) = Z ∞ 0 t z−1 e −t dt = (z − 1)! (6.6) Nous pouvons exprimer la fonction gamma en terme de deux fonctions complémentaires : Γ(z) = γ(z, x) + Γ(z, x) (6.7) 6.4. Description des tests. avec Γ(z, x) la fonction gamma incomplète supérieure et γ(a, x) l’inférieure. Γ(z, x) = Z ∞ x t z−1 e −t dt (6.8) Nous allons utiliser deux expressions normalisés : la fonction gamma inférieure incomplète normalisée, P(z,x) : P(z, x) = γ(z, x) Γ(z, x) (6.9) et la fonction gamma supérieur incomplète normalisée, Q(z,x) : Q(z, x) = 1 − P(z, x) = Γ(z, x) Γ(z) = 1 Γ(z) Z ∞ 0 t z−1 e z−1 dt (6.10) 6.3.3 Obtention des valeurs-p. L’obtention des valeurs-p dépend du type de test, dans lequel s’observe une caractéristique en particulier de la distribution de données de la séquence. Nous allons donc dans la partie suivante étudier les différents tests et l’extraction de la valeurs-p.