Pseudo ist eben nicht echt

Pseudozufallszahlen werden durch ein Berechnungsschema ermittelt, im Fall des hier verwendeten LCG-Algorithmus (linearer Kongruenzgenerator) handelt es sich um eine rekursiv definierte Folge X_n+1=(aX_n+c) mod m. Jeder Zufallswert X_n+1 hängt also vom vorherigen Zufallswert X_n ab. Darum wird die Folge vorhersagbar, sobald ihr Startwert bekannt ist, denn die Parameter a (Faktor) und m (Modul) sind konstant.

Die Kunst ist es, einen nicht vorhersagbaren Startwert zu finden. In PHP erledigt dies »lcg_seed()« (Listing 1). Die Funktion setzt den 64 Bit langen Startwert aus zwei gleich langen Teilwerten »s1« und »s2« zusammen. »s2« bildet die Prozess-ID des Webservers ab, deren Wertebereich in der Praxis die theoretischen 32 Bit nicht mal annähernd ausnutzt. Der Standard-Linux-Kernel begrenzt ihn in »threads.h« auf 16 Bit. Viele Systeme vergeben die PIDs sogar aufsteigend, andere reservieren einen relativ kleinen Bereich. Lässt das Zielsystem gar eine PHP-Injection zu, würde »getmypid()« die Webserver-PID sogar genau ausgeben.

Auch »s1« nutzt nicht die vollen 32 Bit aus: Listing 1 verknüpft die Unix-Epoche (t1) mit den logisch negierten Mikrosekunden (t2) per XOR, also s1=t1 XOR (NOT t2). Doch ist t2 stets kleiner 1000 000. Damit ändern sich nur die niederwertigsten 20 Bits von t2, die anderen sind stets 0 (invertiert dann 1). Somit lassen sich die oberen 12 Bits direkt aus der Systemzeit ermitteln.

Der genaue Startzeitpunkt des Prozesses ist in einem Zeitfenster von 2²⁰ Sekunden (rund 12 Tage) unerheblich. Denn praktischerweise startet Apache Instanzen nach einer bestimmten Anzahl von Anfragen neu. Das bedeutet, dass mit einer ausreichend hohen Wahrscheinlichkeit ein solcher Neustart innerhalb der letzten zwölf Tage stattfand – t2 ist also nicht mehr signifikant.

Die niederwertigen 20 Bits von »s1« verbleiben als einzige Unbekannte. Das sind ausreichend wenig Werte, um sie durch einen Brute-Force-Angriff zu ermitteln. Samy Kamkar hat dafür ein kleines Beispielprogramm [5] geschrieben und ein Patch für PHP 5.3.1 eingereicht, das dann in PHP 5.3.2 eingeflossen ist und sogar nach 5.2.13 zurückportiert wurde.

01 /* Auszug aus ext/standard/lg.cm, gekürzt um einige IFDEFs */
02
03 static void lcg_seed(TSRMLS_D)
04 {
05     struct timeval tv;
06     if (gettimeofday(&tv, NULL) == 0) {
07             LCG(s1) = tv.tv_sec ^ (~tv.tv_usec);
08     } else {
09             LCG(s1) = 1;
10     }
11     LCG(s2) = (long) getpid();
12     LCG(seeded) = 1;
13 }

Die Alternative

Tatsächlich weist die neue Version in Listing 2 eine höhere Entropie auf: Zum einen verschiebt die Zeile 7 für »s1« die gelieferten Mikrosekunden um 11 Bit nach links, was genau den Teil der Epoche maskiert, der sich am wenigsten stark ändert. Auf diese Weise schließt sich das oben abgeschätzte Zwölf-Tage-Fenster. Zum anderen fragt Zeile 14 die Systemzeit ein zweites Mal ab, um die Mikrosekunden als Verschiebungsparameter für »s2« zu gewinnen.

01 /* Auszug aus ext/standard/lg.c, gekürzt um einige IFDEFs */
02
03 static void lcg_seed(TSRMLS_D)
04 {
05     struct timeval tv;
06     if (gettimeofday(&tv, NULL) == 0) {
07             LCG(s1) = tv.tv_sec ^ (tv.tv_usec<<11);
08     } else {
09             LCG(s1) = 1;
10     }
11     LCG(s2) = (long) getpid();
12
13     /* Add entropy to s2 by calling gettimeofday() again */
14     if (gettimeofday(&tv, NULL) == 0) {
15             LCG(s2) ^= (tv.tv_usec<<11);
16     }
17     LCG(seeded) = 1;
18 }

Zugleich versuchen die PHP-Macher mit dieser Maßnahme auch die Zufälligkeit von »s2« zu erhöhen. Das erscheint allerdings wenig weise, denn der Wert wird sich zwischen den beiden kurz aufeinanderfolgenden Aufrufen nicht wesentlich ändern, vermutlich nur in den niederwertigsten 4 bis 5 Bit.

Zwar shiftet Zeile 15 diese Mikrosekunden wieder um 11 Bit nach links, der Bereich ist aber maximal 16 Bit lang, auf Standardsystemen ohne Randomisierung der Prozess-ID eher 11 bis 12 Bit. Damit wird nur das oberste Bit der PID maskiert. »s2« ist nun immerhin nicht mehr zur Hälfte mit Nullen gefüllt, ähnelt dafür aber S1 ziemlich, was theoretisch Raum für neue Abschätzungen gibt. Sinnvoller wäre es, eine andere schwer vorhersagbare Zufallsquelle für »s2« heranzuziehen, statt ein zweites Mal die Systemzeit. Auf Linux-Systemen steht mit »/dev/random« bereits ein sehr guter Zufallsdatengenerator zur Verfügung.