Compréhension approfondie de la sécurité des nombres aléatoires mt_rand() en php

mt_rand() utilise l'algorithme mersennetwister pour renvoyer des entiers aléatoires. Tout le monde le sait, mais l'article suivant vous présente principalement les informations pertinentes sur la sécurité des nombres aléatoires mt_rand() en PHP. Vous avez besoin que vos amis puissent s'y référer. Apprenons avec l'éditeur ci-dessous.

Avant-propos

J'ai découvert de nombreuses vulnérabilités de sécurité liées à mt_rand() il y a quelque temps. Ils ont fondamentalement mal compris l'utilisation des nombres aléatoires. provoqué. Ici, je voudrais mentionner un autre piège du manuel du site officiel de PHP. Jetez un œil à l'introduction de mt_rand() : version chinoise ^cn version anglaise ^en Vous pouvez voir que la version anglaise a un avertissement d'avertissement jaune supplémentaire

This function does not generate cryptographically secure values, and should not be used for cryptographic purposes. If you need a cryptographically secure value, consider using random_int(), random_bytes(), or openssl_random_pseudo_bytes() instead.

De nombreux développeurs nationaux ont probablement lu la version chinoise de l'introduction et ont utilisé mt_rand() dans le programme pour générer des jetons de sécurité, des clés de cryptage et de déchiffrement de base, etc., provoquant de graves problèmes de sécurité.

Nombre pseudo-aléatoire

mt_rand() n'est pas une véritable fonction de génération de nombres aléatoires. En fait, la plupart des langages de programmation le les fonctions de nombres aléatoires génèrent toutes des nombres pseudo-aléatoires. La différence entre les vrais nombres aléatoires et les nombres pseudo-aléatoires ne sera pas expliquée ici. Il vous suffit de comprendre brièvement un peu

Le pseudo-aléatoire est généré par une fonction déterminable (congruence linéaire couramment utilisée) via une graine. (horloge couramment utilisée) de nombres pseudo-aléatoires. Cela signifie que si vous connaissez la graine, ou le nombre aléatoire qui a été généré, il est possible d'obtenir des informations sur la prochaine séquence de nombres aléatoires (prévisibilité).

Supposons simplement que la fonction qui génère des nombres aléatoires en interne dans mt_rand() est :

où seed est la graine du nombre aléatoire, et i est le nombre de fois que cette fonction de nombre aléatoire est appelée. Lorsque l’on connaît les deux valeurs de i et rand en même temps, on peut facilement calculer la valeur de seed. Par exemple, rand=21 et i=2 sont remplacés dans la fonction 21=seed+(2*10) pour obtenir seed=1. N'est-ce pas très simple ? Après avoir obtenu la graine, nous pouvons calculer la valeur du rand lorsque i est n'importe quelle valeur. rand = seed+(i*10)

Amorçage automatique de PHP

De la section précédente, nous savons déjà que chaque fois que mt_rand() est appelé, il sera basé sur seed et current Appelé plusieurs fois i pour calculer un nombre pseudo-aléatoire. Et la graine est automatiquement générée :

Remarque : Depuis PHP 4.2.0, il n'est plus nécessaire d'utiliser srand() ou mt_srand() pour amorcer le générateur de nombres aléatoires, car cela est désormais effectué automatiquement par le système. .

Alors la question se pose : quand le système termine-t-il automatiquement l'amorçage ? Si mt_rand() est automatiquement amorcé à chaque fois, alors cela ne sert à rien de casser la graine. Le manuel ne donne pas d'informations détaillées sur ce point. J'ai cherché partout sur Internet et je n'ai trouvé aucune réponse fiable, j'ai donc dû parcourir le code source ^mtrand :

PHPAPI void php_mt_srand(uint32_t seed)
{
 /* Seed the generator with a simple uint32 */
 php_mt_initialize(seed, BG(state));
 php_mt_reload();

 /* Seed only once */
 BG(mt_rand_is_seeded) = 1; 
}
/* }}} */

/* {{{ php_mt_rand
 */
PHPAPI uint32_t php_mt_rand(void)
{
 /* Pull a 32-bit integer from the generator state
 Every other access function simply transforms the numbers extracted here */

 register uint32_t s1;

 if (UNEXPECTED(!BG(mt_rand_is_seeded))) {
 php_mt_srand(GENERATE_SEED());
 }

 if (BG(left) == 0) {
 php_mt_reload();
 }
 --BG(left);

 s1 = *BG(next)++;
 s1 ^= (s1 >> 11);
 s1 ^= (s1 << 7) & 0x9d2c5680U;
 s1 ^= (s1 << 15) & 0xefc60000U;
 return ( s1 ^ (s1 >> 18) );
}

Vous pouvez voir qu'à chaque fois mt_rand( ) est appelé, il sera d'abord vérifié s'il a été semé. S'il a été semé, générez directement des nombres aléatoires, sinon appelez php_mt_srand pour semer. C'est-à-dire que lors de chaque processus php cgi, seul le premier appel à mt_rand() sera automatiquement généré. Ensuite, des nombres aléatoires seront générés sur la base de cette première graine semée. Parmi les différents modes de fonctionnement de php, à l'exception du CGI (chaque requête démarre un processus cgi et le ferme une fois la requête terminée. Les variables d'environnement php.ini doivent être relues à chaque fois, ce qui entraîne une faible efficacité, et cela ne devrait pas être le cas. beaucoup utilisé maintenant), en gros, après qu'un processus a traité la demande, le serveur de veille attend le suivant et il ne sera pas recyclé tant que plusieurs demandes ne seront pas traitées (il sera également recyclé après l'expiration du délai).

Écrivez un script pour le tester

<?php
//pid.php
echo getmypid();

<?php
//test.php
$old_pid = file_get_contents(&#39;http://localhost/pid.php&#39;);
$i=1;
while(true){
 $i++;
 $pid = file_get_contents(&#39;http://localhost/pid.php&#39;);
 if($pid!=$old_pid){
 echo $i;
 break;
 }
}

Résultat du test : (windows+phpstudy)

Apache 1000 requêtes

nginx 500 requêtes

Bien sûr, ce test ne fait que confirmer le nombre de requêtes qu'Apache et nginx peuvent traiter en un seul processus. Vérifions simplement la conclusion. maintenant à propos de l'ensemencement automatique :

<?php
//pid1.php
if(isset($_GET[&#39;rand&#39;])){
 echo mt_rand();
}else{
 echo getmypid();
}

<?php
//pid2.php
echo mt_rand();

<?php
//test.php
$old_pid = file_get_contents(&#39;http://localhost/pid1.php&#39;);
echo "old_pid:{$old_pid}\r\n";
while(true){
 $pid = file_get_contents(&#39;http://localhost/pid1.php&#39;);
 if($pid!=$old_pid){
 echo "new_pid:{$pid}\r\n";
 for($i=0;$i<20;$i++){
  $random = mt_rand(1,2);
  echo file_get_contents("http://localhost/pid".$random.".php?rand=1")." ";
 }

 break;
 }
}

Jugé par pid , lorsqu'un nouveau processus Au début, obtenez aléatoirement la sortie de mt_rand() sur l'une des deux pages :

old_pid:972 new_pid:7752 1513334371 2014450250 1319669412 499559587 117728762 1465174656 1671827592 1703046841 464496438 1974338231 46646067 981271768 1070717272 571887250 922467166 606646473 134605134 857256637 1971727275 2104203195

Prenez le premier nombre aléatoire 1513334371 pour exploser la graine :

smldhz@vm:~/php_mt_seed-3.2$ ./php_mt_seed 1513334371 Found 0, trying 704643072 - 738197503, speed 28562751 seeds per second seed = 735487048 Found 1, trying 1308622848 - 1342177279, speed 28824291 seeds per second seed = 1337331453 Found 2, trying 3254779904 - 3288334335, speed 28811010 seeds per second seed = 3283082581 Found 3, trying 4261412864 - 4294967295, speed 28677071 seeds per second Found 3

3 graines possibles éclatées, le nombre est très petit et testées manuellement une par une :

<?php
mt_srand(735487048);//手工播种
for($i=0;$i<21;$i++){
 echo mt_rand()." ";
}

Sortie :

Les 20 premiers chiffres sont exactement les mêmes que ceux obtenus par le script ci-dessus. La graine confirmée est 1513334371. Avec la graine, nous pouvons calculer le nombre aléatoire généré en appelant mt_rand() un certain nombre de fois. Par exemple, j'ai généré 21 chiffres dans ce script, et le dernier chiffre est 1515656265. Si vous n'avez pas visité le site après avoir exécuté le script tout à l'heure, vous pouvez voir le même 1515656265 en ouvrant http://localhost/pid2.php.

Nous arrivons donc à la conclusion :

L'amorçage automatique de php se produit lorsque mt_rand() est appelé pour la première fois dans le processus php cgi. Quelle que soit la page visitée, tant que la demande est traitée par le même processus, ils partageront la même graine initialement semée automatiquement.

php_mt_seed

Nous savons déjà que la génération de nombres aléatoires dépend d'une fonction spécifique, qui a été supposée être rand = seed+(i*10)  ci-dessus. Pour une fonction aussi simple, on peut bien sûr calculer directement (oralement) une solution (un groupe), mais la fonction réellement utilisée par mt_rand() est assez complexe et ne peut être inversée. Une méthode de craquage efficace consiste à énumérer de manière exhaustive toutes les graines, à générer une séquence de nombres aléatoires basée sur la graine, puis à la comparer avec une séquence de nombres aléatoires connue pour vérifier si la graine est correcte. php_mt_seed^phpmtseed est un tel outil. Il est très rapide et ne prend que quelques minutes pour exécuter la graine 2^32 bits. Il peut directement exploser les graines possibles en fonction de la sortie d'un seul mt_rand() (exemple ci-dessus). Bien sûr, il peut également exploser les graines qui limitent la sortie MIN MAX comme mt_rand(1,100) (utile dans les exemples ci-dessous).

Problèmes de sécurité

Cela dit, pourquoi les nombres aléatoires sont-ils dangereux ? En fait, il n'y a rien de mal avec la fonction elle-même, et le responsable indique également clairement que les nombres aléatoires générés ne doivent pas être utilisés à des fins de cryptage de sécurité (bien que le manuel de la version chinoise ne l'écrive pas). Le problème est que le développeur ne réalise pas qu’il ne s’agit pas d’un nombre véritablement aléatoire. Nous savons déjà que des graines peuvent être extraites d'une séquence connue de nombres aléatoires. C'est-à-dire que tant qu'il y a un nombre aléatoire de sortie ou sa valeur dérivée (valeur aléatoire réversible) dans n'importe quelle page, alors le nombre aléatoire dans n'importe quelle autre page ne sera plus un « nombre aléatoire ». Les exemples courants de génération de nombres aléatoires incluent les codes de vérification, les noms de fichiers aléatoires, etc. Des nombres aléatoires courants sont utilisés pour la vérification de la sécurité, comme la récupération des valeurs de vérification du mot de passe, telles que les clés de cryptage, etc. Un scénario d'attaque idéal :

En pleine nuit, en attendant qu'Apache (nginx) reprenne tous les processus PHP (pour s'assurer que la prochaine visite sera ré-amorcée), visitez une fois la page de codes de vérification, inversez le nombre aléatoire en fonction des caractères du code de vérification, puis explosez les graines de nombres aléatoires en fonction de nombres aléatoires. Visitez ensuite la page de récupération de mot de passe, et le lien de récupération de mot de passe généré est basé sur des nombres aléatoires. Nous pouvons facilement calculer ce lien et récupérer le mot de passe de l'administrateur...XXOO

Instance

PHPCMS MT_RAND SEED CRACK mène à la clé d'authentification fuite. Yu Niu écrit mieux que moi, il suffit de lire le sien

La fuite de clé d'authentification Discuz x3.2 est en fait similaire. Le patch officiel a été publié et ceux qui sont intéressés peuvent l'analyser eux-mêmes.

Résumé

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!