random.choice non random

Question

Sto usando Python 2.5 su Linux, in più processi FCGI paralleli. Io uso

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

per generare cookie distinti. Supponendo che l'RNG sia estratto da/dev/urandom, e che la sequenza di numeri casuali provenga dal twister di Mersenne, mi aspetto che ci sia praticamente zero possibilità di collisione.

Tuttavia, vedo collisioni regolari, anche se solo pochi utenti (< 100) hanno effettuato l'accesso in qualsiasi momento.

Perché i numeri casuali non sono più casuali?

Answer 1

Non dovrebbe generare duplicati.

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 

Le possibilità di duplicati sono significative con chars = "ab"; 126 duplicati in 1000000 iterazioni. Non esiste con 62.

Detto questo, questo non è un buon modo per generare cookie, perché i cookie di sessione devono essere imprevedibili, per evitare gli attacchi che implicano il furto di cookie di sessione di altre persone. Il Mersenne Twister non è progettato per generare numeri casuali sicuri. Questo è quello che faccio:

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

... che dovrebbe essere molto sicuro (vale a dire, difficile prendere una serie di cd cookies di sessione e indovinate altri cookie di sessione esistenti da loro).

Answer 2

Per evitare il problema, è possibile utilizzare una sequenza di cookie, che sono garantiti per essere diversi (è possibile, ad esempio, utilizzare un set). Ogni volta che dai un cookie a qualcuno, lo prendi dalla sequenza e ne aggiungi un altro. Un'altra opzione è generare un UUID e usarlo come cookie.

Un altro modo per evitare il problema potrebbe essere quello di tenere una chiave privata e utilizzare un checksum (ad esempio MD5) della chiave privata, con un valore contatore collegato ad esso. La probabilità di collisioni sarà quindi molto bassa. Per essere più sicuri, aggiungi altre variabili al checksum, come l'ora corrente, l'indirizzo IP dell'utente, ...

Le librerie per generare i cookie esistono. Qualsiasi implementazione WSGI probabilmente contiene un generatore di cookie.

Se ti interessa solo il modo in cui le stringhe sono casuali, puoi generare un file con, ad esempio, un milione di cookie ed eseguire controlli di casualità su quel file. Questo, tuttavia, non è quello che raccomanderei.

Answer 3

Questo non è sicuramente un normale scenario di collisione:

• 32 caratteri con 62 opzioni per carattere è equivalente a 190 bit (log2 (62) * 32)
• Secondo il paradosso del compleanno, si dovrebbe ricevere una collisione in modo naturale una volta ogni 2 ** 95 cookie, il che significa che non è mai

Potrebbe essere un problema di concorrenza?

• Se è così, utilizzare diversi random.Random istanze per ogni thread
• Impossibile salvare questi casi nella memoria thread-local (threading.local())
• su Linux, Python dovrebbe sementi di loro utilizzando os.urandom() - non ora del sistema - in modo da dovrebbe ottenere flussi diversi per ogni thread.

Answer 4

ho dovuto cancellare la mia risposta originale, che ha suggerito che generatore non è seminato da /dev/urandom, fin dalla sua source (per Python 3.x) dice chiaramente che si tratta di:

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 

pertanto umilmente accetta che ci siano misteri nel mondo che potrei non essere in grado di decifrare.

Answer 5

1. Non so come i processi fcgi vengono generati, ma è possibile che sia utilizzando fork() dopo l'interprete Python è iniziata (e il modulo a caso è stato importato da qualcosa), e quindi in modo efficace semina due processi 'random._inst s dalla stessa origine?

2. Forse mettere un po 'di debug per verificare che sia correttamente seed da urandom, e non tornare al seme meno rigoroso basato sul tempo?

eta re commento: amico! Quello sono io perplesso poi; se l'RNG ha sempre stati diversi all'avvio, non riesco a vedere come potresti ottenere collisioni. Strano. Dovrei mettere un sacco di registrazioni statali per indagare sui casi particolari che provocano collisioni, immagino, che suona come un sacco di lavoro che scava tra i registri. Potrebbe essere (1a) che il server FCGI di solito non si batta, ma occasionalmente lo fa (forse sotto carico, o qualcosa del genere)?

Oppure (3) alcuni problemi di livello superiore come un proxy HTTP danneggiato che passa lo stesso Set-Cookie a più client?