random.choice nicht zufällig

Question

Ich benutze Python 2.5 unter Linux, in mehreren parallelen FCGI-Prozessen. Ich verwende

chars = string.ascii_letters + string.digits 
    cookie = ''.join([random.choice(chars) for x in range(32)]) 

, um unterschiedliche Cookies zu generieren. Unter der Annahme, dass der RNG aus/dev/urandom ausgesät wird und dass die Sequenz der Zufallszahlen vom Mersenne Twister kommt, würde ich erwarten, dass es praktisch keine Kollisionswahrscheinlichkeit gibt.

Allerdings sehe ich regelmäßige Kollisionen, obwohl nur wenige (< 100) Benutzer zu jeder Zeit angemeldet sind.

Warum sind die Zufallszahlen nicht zufälliger?

Answer 1

Es sollte keine Duplikate erzeugen.

import random 
chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" 
def gen(): 
    return ''.join([random.choice(chars) for x in range(32)]) 

test = [gen() for i in range(100000)] 
print len(test), len(set(test)) # 100000 100000 

Die Wahrscheinlichkeit von Duplikaten ist signifikant mit chars = "ab"; 126 Duplikate in 1000000 Iterationen. Es ist nicht existent mit 62.

Das ist, das ist nicht eine gute Möglichkeit, Cookies zu erstellen, da Sitzungscookies unvorhersehbar sein müssen, um Angriffe zu vermeiden, die Session-Cookies anderer Leute zu stehlen. Der Mersenne Twister ist nicht zum Erzeugen sicherer Zufallszahlen vorgesehen. Das ist, was ich tue:

import os, hashlib 
def gen(): 
    return hashlib.sha1(os.urandom(512)).hexdigest() 

test = [gen() for i in range(100000)] 
print len(test), len(set(test)) 

..., die sehr sicher sein sollten (was heißt, schwierig, eine Reihe von Session-Cookies zu nehmen und erraten, andere bestehende Session-Cookies von ihnen).

Answer 2

Um das Problem zu vermeiden, können Sie eine Folge von Cookies verwenden, die garantiert unterschiedlich sind (Sie können z. B. ein Set verwenden). Jedes Mal, wenn du jemandem einen Keks gibst, nimmst du ihn aus der Sequenz und fügst ihm einen weiteren hinzu. Eine weitere Möglichkeit besteht darin, eine UUID zu generieren und diese als Cookie zu verwenden. Eine andere Möglichkeit, das Problem zu vermeiden, könnte darin bestehen, einen privaten Schlüssel zu halten und eine (z. B. MD5) Prüfsumme des privaten Schlüssels mit einem Zählerwert zu verwenden, der damit verbunden ist. Die Wahrscheinlichkeit für Kollisionen ist dann sehr gering. Um sicherer zu sein, fügen Sie der Prüfsumme weitere Variablen hinzu, wie die aktuelle Uhrzeit, die IP-Adresse des Benutzers, ...

Bibliotheken zum Generieren von Cookies existieren. Jede WSGI-Implementierung enthält wahrscheinlich einen Cookie-Generator.

Wenn Sie nur daran interessiert sind, wie zufällig Ihre Strings sind, könnten Sie eine Datei mit, sagen wir, einer Million Cookies generieren und Zufälligkeitsüberprüfungen für diese Datei durchführen. Dies ist jedoch nicht, was ich empfehlen würde.

Answer 3

Dies ist definitiv keine normale Kollision Szenario:

• 32 Zeichen mit 62 Optionen pro Zeichen auf 190 Bits entspricht (log2 (62) * 32)
• Nach dem Geburtstagsparadoxon, sollten Sie eine Kollision natürlich einmal alle 2 ** 95 Cookies, was bedeutet nie

Könnte dies ein Nebenläufigkeitsproblem sein?

• Wenn ja, verwenden unterschiedliche random.Random Instanzen für jeden Thread
• Kann diese Instanzen in Thread-lokalen Speicher speichern (threading.local())
• Unter Linux, Python sollte sie os.urandom() mit Saatgut - nicht Systemzeit -, so dass Sie sollte für jeden Thread unterschiedliche Streams erhalten.

Answer 4

Ich hatte meine ursprüngliche Antwort zu löschen, die vorgeschlagen, dass Generator nicht aus /dev/urandom ausgesät wird, seine seit source (für Python 3.x) deutlich sagt, dass es ist:

def seed(self, a=None): 
    """Initialize internal state from hashable object. 

    None or no argument seeds from current time or from an operating 
    system specific randomness source if available. 

    If a is not None or an int or long, hash(a) is used instead. 
    """ 

    if a is None: 
     try: 
      a = int(_hexlify(_urandom(16)), 16) 
     except NotImplementedError: 
      import time 
      a = int(time.time() * 256) # use fractional seconds 

    super().seed(a) 
    self.gauss_next = None 

ich daher demütig akzeptiere, dass es Geheimnisse in der Welt gibt, die ich nicht entziffern kann.

Answer 5

1. Ich weiß nicht, wie Sie Ihre FCGI Prozesse hervorgebracht werden, aber ist es möglich, dass es mit fork() nach der Python-Interpreter (und das statistische Modul wurde durch etwas importiert) daher effektiv, hat begonnen Seeding zwei Prozesse 'random._inst s aus der gleichen Quelle?

2. Vielleicht Debuggen, um zu überprüfen, ob es korrekt aus dem Urzustand kommt und nicht auf den weniger rigorosen, zeitbasierten Seed zurückfällt?

eta re kommentieren: Mann! Das bin ich dann ratlos; Wenn der RNG beim Start immer einen anderen Status hat, kann ich nicht sehen, wie Sie möglicherweise Kollisionen bekommen. Seltsam. Ich würde viel State Logging einlegen müssen, um die speziellen Fälle zu untersuchen, die zu Kollisionen führen, denke ich, was sich anhört wie eine Menge Arbeit, die durch Logs läuft. Könnte es sein (1a) der FCGI-Server normalerweise nicht fork, aber gelegentlich (vielleicht unter Last oder etwas)?

Oder (3) ein höheres Problem wie ein defekter HTTP-Proxy, der denselben Set-Cookie an mehrere Clients weitergibt?