Vorhersage der Ausgabe von PHP's rand ()

Ich habe in zahlreichen Quellen gelesen, dass die Ausgabe von rand () von PHP als PRNG vorhersehbar ist, und ich akzeptiere das meistens als Tatsache, einfach weil ich es an so vielen Orten gesehen habe.

Ich bin an einem Proof-of-Concept interessiert: Wie würde ich die Ausgabe von rand () vorhersagen? Beim Lesen dieses Artikels habe ich verstanden, dass die Zufallszahl eine Zahl ist, die von einer Liste zurückgegeben wird, die mit einem Zeiger (dem Startwert) beginnt - aber ich kann mir nicht vorstellen, wie dies vorhersehbar ist.

Könnte jemand vernünftigerweise herausfinden, welche zufällige # zu einem bestimmten Zeitpunkt innerhalb weniger tausend Vermutungen über rand () generiert wurde? oder sogar 10.000 Vermutungen? Wie?

Dies ist darauf zurückzuführen, dass ich eine Authentifizierungsbibliothek gesehen habe, die rand () verwendet, um ein Token für Benutzer zu erstellen, die Kennwörter verloren haben, und ich nahm an, dass dies eine potenzielle Sicherheitslücke darstellt. Ich habe seitdem die Methode durch eine Mischung aus Hashing openssl_random_pseudo_bytes(), dem ursprünglichen Hashing- Passwort und Microtime ersetzt. Nachdem ich dies getan hatte, stellte ich fest, dass ich keine Ahnung hätte, wie ich das Token erraten könnte, selbst wenn ich wüsste, dass es ein md5 von rand () ist.

Die Fähigkeit, den nächsten Wert zu erraten, randhängt davon ab, zu bestimmen, womit srandaufgerufen wurde. Insbesondere das Säen srandmit einer vorbestimmten Anzahl führt zu einer vorhersehbaren Ausgabe ! Über die interaktive PHP-Eingabeaufforderung:

[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 > 

Dies ist nicht nur ein Zufall. Die meisten PHP-Versionen ^* auf den meisten Plattformen ^** erzeugen srandbei 1024 die Sequenz 97, 97, 39, 77, 93 .

Um es klar auszudrücken, dies ist kein Problem mit PHP, dies ist ein Problem mit der Implementierung von sich randselbst. Dasselbe Problem tritt in anderen Sprachen auf, die dieselbe (oder eine ähnliche) Implementierung verwenden, einschließlich Perl.

Der Trick ist, dass jede vernünftige Version von PHP srandeinen "unbekannten" Wert hat. Oh, aber es ist nicht wirklich unbekannt. Von ext/standard/php_rand.h:

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

Also ist es ein bisschen Mathe mit time(), der PID und dem Ergebnis von php_combined_lcg, das in definiert ist ext/standard/lcg.c. Ich werde nicht hierher kommen, da meine Augen glasig wurden und ich beschloss, die Jagd einzustellen.

Ein bisschen googeln zeigt, dass andere Bereiche von PHP nicht die besten Eigenschaften für die Zufallsgenerierung haben , und fordert dazu auf php_combined_lcg, hier hervorzuheben , insbesondere diese Art der Analyse:

Diese Funktion ( gettimeofday) gibt uns nicht nur einen präzisen Server-Zeitstempel auf einem Silbertablett zurück, sondern erhöht auch die LCG-Ausgabe, wenn wir "mehr Entropie" (von PHPs uniqid) anfordern .

Ja dasuniqid . Es scheint, dass der Wert von das php_combined_lcgist, was wir sehen, wenn wir die resultierenden hexadezimalen Ziffern betrachten, nachdem wir uniqiddas zweite Argument auf einen wahren Wert gesetzt haben.

Wo waren wir jetzt?

Oh ja. srand.

Wenn der Code, aus dem Sie zufällige Werte vorhersagen möchten, nicht aufgerufen wird srand, müssen Sie den von bereitgestellten Wert ermitteln php_combined_lcg, den Sie (indirekt?) Durch einen Aufruf von abrufen können uniqid. Mit diesem Wert in der Hand ist es möglich , den Rest des Werts - time(), die PID und etwas Mathematik - brachial zu erzwingen . Bei dem verknüpften Sicherheitsproblem geht es um das Unterbrechen von Sitzungen, aber die gleiche Technik würde hier funktionieren. Wieder aus dem Artikel:

Hier ist eine Zusammenfassung der oben beschriebenen Angriffsschritte:

• Warten Sie, bis der Server neu gestartet wurde
• Holen Sie sich einen eindeutigen Wert
• Brute Force das RNG-Saatgut aus diesem
• Fragen Sie den Online-Status ab, um zu warten, bis das Ziel angezeigt wird
• Verschachteln Sie Statusabfragen mit eindeutigen Abfragen, um die aktuelle Serverzeit und den aktuellen RNG-Wert zu verfolgen
• Brute Force-Sitzungs-ID für den Server unter Verwendung der Zeit und des RNG-Wertintervalls, die bei der Abfrage festgelegt wurden

Ersetzen Sie einfach den letzten Schritt nach Bedarf.

(Dieses Sicherheitsproblem wurde in einer früheren PHP-Version (5.3.2) gemeldet als derzeit (5.3.6). Daher ist es möglich, dass sich das Verhalten von uniqidund / oder php_combined_lcggeändert hat, sodass diese spezielle Technik möglicherweise nicht mehr funktioniert. YMMV.)

Auf der anderen Seite, wenn der Code , den Sie Produkt sind versuchen Anrufe srandmanuell , dann , wenn sie nicht verwenden etwas oft besser als das Ergebnis php_combined_lcg, sind Sie wahrscheinlich eine viel haben , gehen leichte Zeit zu raten , den Wert und Säen Sie Ihre lokalen Generator mit der richtigen Nummer. Die meisten Leute, die manuell anrufen srandwürden , würden auch nicht erkennen, wie schrecklich eine Idee ist, und werden daher wahrscheinlich keine besseren Werte verwenden.

Es ist erwähnenswert, dass mt_randdas gleiche Problem auch betroffen ist. Das Säen mt_srandmit einem bekannten Wert führt auch zu vorhersehbaren Ergebnissen. Es openssl_random_pseudo_bytesist wahrscheinlich sicherer, Ihre Entropie zu begründen .

tl; dr: Um die besten Ergebnisse zu erzielen , sollten Sie den PHP-Zufallszahlengenerator nicht verwenden. Um Himmels willen, sollten Sie ihn nicht uniqidden Benutzern aussetzen . Wenn Sie eine oder beide dieser Methoden anwenden, sind Ihre Zufallszahlen möglicherweise besser zu erraten.

Update für PHP 7:

PHP 7.0 führt random_bytesund random_intals Kernfunktionen ein. Sie verwenden die CSPRNG-Implementierung des zugrunde liegenden Systems, wodurch sie frei von den Problemen sind, die ein Start-Zufallszahlengenerator hat. Sie sind praktisch ähnlich openssl_random_pseudo_bytes, nur ohne dass eine Erweiterung installiert werden muss. Für PHP5 ist eine Polyfill verfügbar .

*: Der Suhosin-Sicherheitspatch ändert das Verhalten von randund mt_randso, dass sie bei jedem Anruf neu generiert werden . Suhosin wird von Dritten bereitgestellt. Einige Linux-Distributionen enthalten es standardmäßig in ihren offiziellen PHP-Paketen, während andere es als Option festlegen und andere es vollständig ignorieren.

**: Abhängig von der Plattform und den verwendeten zugrunde liegenden Bibliotheksaufrufen werden andere Sequenzen generiert als hier dokumentiert. Die Ergebnisse sollten jedoch weiterhin wiederholbar sein, es sei denn, der Suhosin-Patch wird verwendet.

Um visuell zu veranschaulichen, wie nicht zufällig die rand()Funktion ist, ist hier ein Bild, in dem alle Pixel aus "zufälligen" roten, grünen und blauen Werten bestehen:

Normalerweise sollten die Bilder kein Muster enthalten.

Ich habe versucht, srand()mit verschiedenen Werten aufzurufen . Es ändert nichts daran, wie vorhersehbar diese Funktion ist.

Beachten Sie, dass beide nicht kryptografisch sicher sind und vorhersehbare Ergebnisse liefern.

Die Ausgabe von PHPs rand () ist vorhersehbar als PRNG

Es ist ein linearer Kongruenzgenerator . Das bedeutet Sie haben eine Funktion , die effektiv ist: NEW_NUMBER = (A * OLD_NUMBER + B) MOD C. Wenn Sie NEW_NUMBER gegen OLD_NUMBER ein Diagramm erstellen, werden diagonale Linien angezeigt. Einige der Hinweise in der RAND-Dokumentation von PHP enthalten Beispiele dafür.

Dies ist darauf zurückzuführen, dass ich eine Authentifizierungsbibliothek gesehen habe, die rand () verwendet, um ein Token für Benutzer zu erstellen, die Kennwörter verloren haben. Ich nahm an, dass dies eine potenzielle Sicherheitslücke darstellt.

Auf einem Windows-Computer beträgt der Maximalwert von RAND 2 ^ 15. Dies gibt dem Angreifer nur 32.768 Überprüfungsmöglichkeiten.

Könnte jemand vernünftigerweise herausfinden, welche zufällige # zu einem bestimmten Zeitpunkt innerhalb weniger tausend Vermutungen über rand () generiert wurde? oder sogar 10.000 Vermutungen? Wie?

Obwohl dieser Artikel nicht genau der ist, den Sie suchen, zeigt er, wie einige Forscher eine vorhandene Implementierung eines Zufallszahlengenerators nutzten, um mit Texas Holdem Geld zu verdienen. Es gibt 52! Mögliche gemischte Decks, aber die Implementierung verwendete einen 32-Bit-Zufallszahlengenerator (das ist die maximale Anzahl von mt_getrandmax auf einem Windows-Computer) und setzte die Zeit in Millisekunden seit Mitternacht fest. Dies reduzierte die Anzahl möglicher gemischter Decks von ungefähr 2 ^ 226 auf ungefähr 2 ^ 27, was es möglich machte, in Echtzeit zu suchen und zu wissen, welches Deck behandelt wurde.

Nachdem ich dies getan hatte, stellte ich fest, dass ich keine Ahnung hätte, wie ich das Token erraten könnte, selbst wenn ich wüsste, dass es ein md5 von rand () ist.

Ich würde empfehlen, etwas aus der SHA-2- Familie zu verwenden, da die Regierung md5 als defekt ansieht. Einige Leute verwenden Google, um MD5-Hashes zu entschlüsseln, weil sie so häufig sind. Hasch einfach etwas und wirf dann den Hash in eine Google-Suche - im Grunde ist Google zu einem riesigen Regenbogentisch geworden .

Es ist wirklich genauer zu sagen, dass bei einer zufällig generierten Zahl die nächste relativ vorhersehbar ist. Es gibt nur so viele Zahlen, wie es sein kann. Das heißt aber nicht, dass Sie es erraten könnten, sondern eher, dass Sie ein Programm schreiben könnten, das es ziemlich schnell tut.