Prédire la sortie de rand () de PHP

J'ai lu dans de nombreuses sources que la sortie de rand () de PHP est prévisible car c'est un PRNG, et j'accepte principalement cela comme un fait simplement parce que je l'ai vu dans tant d'endroits.

Je suis intéressé par une preuve de concept: comment pourrais-je prévoir la sortie de rand ()? En lisant cet article, je comprends que le nombre aléatoire est un nombre renvoyé d'une liste commençant à un pointeur (la graine) - mais je ne peux pas imaginer comment cela est prévisible.

Quelqu'un pourrait-il raisonnablement comprendre quel # aléatoire a été généré via rand () à un moment donné dans quelques milliers de suppositions? ou même 10 000 suppositions? Comment?

Cela vient parce que j'ai vu une bibliothèque d'authentification qui utilise rand () pour produire un jeton pour les utilisateurs qui ont perdu des mots de passe, et j'ai supposé que c'était une faille de sécurité potentielle. J'ai depuis remplacé la méthode par le hachage d'un mélange de openssl_random_pseudo_bytes(), le mot de passe haché d'origine et le microtime. Après avoir fait cela, j'ai réalisé que si j'étais à l'extérieur, je n'aurais aucune idée de comment deviner le jeton même en sachant qu'il s'agissait d'un md5 de rand ().

La capacité de deviner la valeur suivante randest liée à la capacité de déterminer ce qui a srandété appelé. En particulier, l' ensemencement srandavec un nombre prédéterminé entraîne une sortie prévisible ! Depuis l'invite interactive PHP:

[charles@charles-workstation ~]$ php -a
Interactive shell

php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > srand(1024);
php > echo rand(1, 100);
97
php > echo rand(1, 100);
97
php > echo rand(1, 100);
39
php > echo rand(1, 100);
77
php > echo rand(1, 100);
93
php > 

Ce n'est pas seulement un coup de chance. La plupart des versions PHP ^* sur la plupart des plates-formes ^** généreront la séquence 97, 97, 39, 77, 93 srandavec 1024.

Pour être clair, ce n'est pas un problème avec PHP, c'est un problème avec l'implémentation de randlui - même. Le même problème apparaît dans d'autres langues qui utilisent la même implémentation (ou une implémentation similaire), y compris Perl.

L'astuce est que toute version saine de PHP aura pré-ensemencé srandavec une valeur "inconnue". Oh, mais ce n'est pas vraiment inconnu. De ext/standard/php_rand.h:

#define GENERATE_SEED() (((long) (time(0) * getpid())) ^ ((long) (1000000.0 * php_combined_lcg(TSRMLS_C))))

Donc, c'est un peu de calcul avec time(), le PID et le résultat de php_combined_lcg, qui est défini dans ext/standard/lcg.c. Je ne vais pas c & p ici, car, bien, mes yeux brillaient et j'ai décidé d'arrêter de chasser.

Un peu de recherche sur Google montre que d' autres domaines de PHP n'ont pas les meilleures propriétés de génération d'aléatoire , et appelle à php_combined_lcgse démarquer ici, en particulier ce morceau d'analyse:

Non seulement cette fonction ( gettimeofday) nous rend un horodatage précis du serveur sur un plateau d'argent, mais elle ajoute également une sortie LCG si nous demandons "plus d'entropie" (de PHP uniqid).

Ouais çauniqid . Il semble que la valeur de php_combined_lcgsoit ce que nous voyons lorsque nous regardons les chiffres hexadécimaux résultants après l'appel uniqidavec le deuxième argument défini sur une valeur vraie.

Maintenant, où en étions-nous?

Oh oui. srand.

Donc, si le code à partir duquel vous essayez de prédire des valeurs aléatoires n'appelle passrand , vous devrez déterminer la valeur fournie par php_combined_lcg, que vous pouvez obtenir (indirectement?) Via un appel à uniqid. Avec cette valeur en main, il est possible de forcer brutalement le reste de la valeur - time(), le PID et quelques calculs. Le problème de sécurité lié concerne la rupture des sessions, mais la même technique fonctionnerait ici. Encore une fois, à partir de l'article:

Voici un résumé des étapes d'attaque décrites ci-dessus:

• attendez que le serveur redémarre
• récupérer une valeur uniqid
• force brute la graine RNG de cette
• interroger l'état en ligne pour attendre que la cible apparaisse
• entrelacer les sondages d'état avec les sondages uniqid pour garder une trace de l'heure actuelle du serveur et de la valeur RNG
• ID de session de force brute sur le serveur à l'aide de l'intervalle de temps et de valeur RNG établi lors de l'interrogation

Remplacez simplement cette dernière étape si nécessaire.

(Ce problème de sécurité a été signalé dans une version PHP antérieure (5.3.2) que nous avons actuellement (5.3.6), il est donc possible que le comportement de uniqidet / ou php_combined_lcgait changé, donc cette technique spécifique pourrait ne plus fonctionner. YMMV.)

D'un autre côté, si le code que vous essayez de produire du produit appelle srandmanuellement , à moins qu'ils n'utilisent quelque chose de bien meilleur que le résultat php_combined_lcg, vous aurez probablement beaucoup plus de facilité à deviner la valeur et à amorcer votre local générateur avec le bon numéro. La plupart des gens qui appelleraient manuellement srandne réaliseraient pas non plus à quel point cette idée est horrible, et ne sont donc pas susceptibles d'utiliser de meilleures valeurs.

Il convient de noter qu'il mt_randest également touché par le même problème. L'ensemencement mt_srandavec une valeur connue produira également des résultats prévisibles. Baser votre entropie sur openssl_random_pseudo_bytesest probablement un pari plus sûr.

tl; dr: pour de meilleurs résultats, n'amorcez pas le générateur de nombres aléatoires PHP et, pour l'amour du ciel, ne l'exposez pas uniqidaux utilisateurs. Si vous effectuez l'une de ces actions ou les deux, vous risquez de deviner vos nombres aléatoires.

Mise à jour pour PHP 7:

PHP 7.0 présente random_byteset en random_inttant que fonctions principales. Ils utilisent l'implémentation CSPRNG du système sous-jacent, ce qui les libère des problèmes rencontrés par un générateur de nombres aléatoires. Ils sont effectivement similaires à openssl_random_pseudo_bytes, uniquement sans avoir besoin d'installer une extension. Un polyfill est disponible pour PHP5 .

*: Le correctif de sécurité Suhosin modifie le comportement de randet de mt_randtelle sorte qu'ils se ré- amorcent toujours à chaque appel. Suhosin est fourni par un tiers. Certaines distributions Linux l'incluent par défaut dans leurs packages PHP officiels, tandis que d'autres en font une option, et d'autres l'ignorent complètement.

**: En fonction de la plate-forme et des appels de bibliothèque sous-jacents utilisés, des séquences différentes seront générées que celles décrites ici, mais les résultats devraient toujours être reproductibles à moins que le patch Suhosin soit utilisé.

Pour illustrer visuellement à quel point la rand()fonction est non aléatoire , voici une image où tous les pixels sont constitués de valeurs "aléatoires" rouges, vertes et bleues:

Il ne devrait normalement pas y avoir de motif dans les images.

J'ai essayé d'appeler srand()avec différentes valeurs, cela ne change pas la prévisibilité de cette fonction.

Notez que les deux ne sont pas sécurisés cryptographiquement et produisent des résultats prévisibles.

la sortie de rand () de PHP est prévisible car c'est un PRNG

C'est un générateur de congruence linéaire . Cela signifie que vous avez une fonction qui est efficace: NEW_NUMBER = (A * OLD_NUMBER + B) MOD C. Si vous affichez NEW_NUMBER par rapport à OLD_NUMBER, vous commencerez à voir des lignes diagonales. Certaines notes sur la documentation RAND de PHP donnent des exemples de la façon de procéder.

Cela vient parce que j'ai vu une bibliothèque d'authentification qui utilise rand () pour produire un jeton pour les utilisateurs qui ont perdu des mots de passe, et j'ai supposé que c'était une faille de sécurité potentielle.

Sur une machine Windows, la valeur maximale de RAND est de 2 ^ 15. Cela ne donne à l'attaquant que 32 768 possibilités de vérification.

Quelqu'un pourrait-il raisonnablement comprendre quel # aléatoire a été généré via rand () à un moment donné dans quelques milliers de suppositions? ou même 10 000 suppositions? Comment?

Bien que cet article ne soit pas exactement celui que vous recherchez, il montre comment certains chercheurs ont pris une implémentation existante d'un générateur de nombres aléatoires et l'ont utilisé pour gagner de l'argent sur le Texas Holdem. Il y en a 52! decks mélangés possibles, mais l'implémentation a utilisé un générateur de nombres aléatoires 32 bits (qui est le nombre maximum de mt_getrandmax sur une machine Windows), et l'a semé avec le temps en millisecondes depuis minuit. Cela a réduit le nombre de decks mélangés possibles d'environ 2 ^ 226 à environ 2 ^ 27, ce qui permet de rechercher en temps réel et de savoir quel deck a été traité.

Après avoir fait cela, j'ai réalisé que si j'étais à l'extérieur, je n'aurais aucune idée de comment deviner le jeton même en sachant qu'il s'agissait d'un md5 de rand ().

Je recommanderais d'utiliser quelque chose dans la famille SHA-2 car les autorités considèrent que md5 est cassé. Certaines personnes utilisent Google pour décrypter les hachages md5 car ils sont si courants. Il suffit de hacher quelque chose, puis de lancer le hachage dans une recherche Google - en gros, Google est devenu une table arc-en-ciel géante .

Il est vraiment plus précis de dire que, étant donné un nombre généré de manière aléatoire, le suivant est relativement prévisible. Il ne peut y en avoir que beaucoup. Mais cela ne signifie pas que vous pourriez le deviner, plus que vous pourriez écrire un programme qui le fait, assez rapidement.