PRNG: la combinazione di algos non sicuri aiuta?

3

Leggendo su quanto insicuro la funzione di rand di PHP è , io ero chiedendo se aiuta a combinare le funzioni casuali. La funzione suggerita lì, openssl_random_pseudo_bytes , può anche essere crittograficamente insicura (vedi la seconda discussione). Combinare l'output da questo e rand () e forse anche mt_rand () potrebbe allungare il periodo:

function more_randomness() {
    $n = 0;
    $n += rand(0, 255);
    $n += mt_rand(0, 255);
    $n += ord(openssl_random_pseudo_bytes(1));
    return round($n / 3);
}

Se questo è completamente stupido, dimmelo. Dimmi anche come generare numeri casuali crittograficamente sicuri quando questo restituisce false:

function has_bad_prng() {
    openssl_random_pseudo_bytes(1, $is_bad);
    return $is_bad;
}
    
posta Luc 10.08.2012 - 16:03
fonte

3 risposte

7

Un PRNG può essere insicuro per diversi motivi, ma uno di questi utilizza come seme alcuni dati che possono avere solo un numero limitato di valori distinti. Ad esempio, se si usa l'ora corrente come seme, allora quel valore è noto all'attaccante, o almeno potenzialmente noto con uno sforzo non molto difficile: anche se si ha un orologio interno con precisione microsecondi e l'attaccante conosce quel clock solo fino ad una precisione di un secondo circa, quindi questo ammonta a solo un milione di valori seme possibili.

Eseguendo l'enumerazione dei possibili valori seme, l'utente malintenzionato può ricalcolare gli stessi flussi possibili di te. Puoi aggiungere centinaia di PRNG con qualsiasi algoritmo che desideri; se usano tutti l'ora corrente come seme, questo non ti salverà.

"Aggiungere" insieme diversi potrebbero aiutare se il PRNG è correttamente seminato (con distinti origini seme) e alcuni dei PRNG sono crittograficamente deboli. Ma ci sono dettagli sottili; non è facile fare bene, e di solito non vale la pena.

Se openssl_random_pseudo_bytes() restituisce "insicuro", allora c'è ben poco che puoi fare per recuperarlo. Inoltre, ciò non accade nella pratica, a meno che il tuo sistema non sia in qualche modo danneggiato. Qualsiasi server decente, che si tratti di Linux, Windows, MacOS, FreeBSD ... mantiene un PRNG crittograficamente potente seminato con eventi hardware (che è /dev/urandom , CryptGenRandom() ...) e questo è ciò che OpenSSL usa. Se questo non funziona, allora le cose si sono acuite profondamente nel tuo sistema, ed è ora di andare nel panico (cioè aumentare le eccezioni e avvisare il sysadmin).

    
risposta data 10.08.2012 - 17:47
fonte
2

Tecnicamente, si migliora la sicurezza un po ', ma senza fine utile.

I numeri casuali di solito provengono da un generatore di numeri pseudo-casuali (PRNG) che è esso stesso inseminato con un valore casuale. Lo scopo del PRNG è di allungare il seme originale per produrre un output molto lungo. I numeri casuali vengono solitamente richiamati per due motivi:

  • Per creare dati dall'aspetto casuale per un uso un po 'casuale. Forse per dare ai personaggi di un videogioco una strategia dall'aspetto casuale, magari per eseguire un algoritmo randomizzato , ecc. Il requisito generale è che i valori casuali siano ben distribuiti e superino i test statistici di base, sebbene l'uso esatto imponga esattamente quali sono i requisiti.

  • Per fornire sicurezza crittografica. Forse per generare una chiave segreta, per iniziare la ricerca di un numero primo casuale, ecc. Il requisito è che i valori casuali siano distribuiti molto bene, superino molti test statistici avanzati, abbiano uno spazio seme molto grande e non producano informazioni su altri valori nell'output o qualcosa del seme del PRNG.

I PRNG di solito sono progettati per uno di questi requisiti e non sono uguali. I PRNG per uso occasionale tendono ad essere molto semplici, estremamente veloci e non soddisfano nessuno dei requisiti di un PRNG crittografico. È molto difficile trasformare un semplice PRNG in un PRNG crittografico; per fare ciò ci sarebbe probabilmente molto poco simile al PRNG originale lasciato nello schema PRNG finale sicuro.

Ecco alcuni problemi con la combinazione dei PRNG deboli:

  • Lunghezza del periodo. Quando combini due PRNG in modo lineare (come nell'OP), nel migliore dei casi combinerai le loro lunghezze seme. I PRNG semplici hanno in genere 32 bit o meno di lunghezza seme, che è crittograficamente molto insicuro. In genere dovresti avere almeno 128 bit di spazio seme.

  • Protezione delle sementi. La combinazione delle uscite PRNG non impedirà necessariamente che il seme venga decodificato dall'uscita PRNG. Se un attaccante può ricavare parte del seme, può ridurre drasticamente il carico di lavoro. Derivare il seme dall'output di un PRNG semplice a volte è banale in circostanze appropriate.

  • Bias di output. Combinare linearmente le uscite PRNG non nasconderà necessariamente le loro uscite difettose. Dovrebbe sicuramente migliorare il bias, ma è improbabile che siano validi come un PRNG crittografico. (In pratica, questo è probabilmente meno preoccupante, ma vale comunque la pena di essere menzionato.)

E questo presume che tu semini correttamente il PRNG. È ancora necessario eseguire manualmente la semina come qualsiasi semina predefinita utilizzata dai PRNG semplici è probabilmente basata su qualcosa di qualità molto bassa, come un timestamp.

Il semplice summery è che la combinazione di PRNG deboli offre una sicurezza migliore, ma non il livello di sicurezza che ci si dovrebbe aspettare da un PRNG crittograficamente sicuro. La soluzione è ottenere un PRNG crittografico reale e inizializzarlo con dati casuali da una buona fonte, come /dev/random o CryptGenRandom() . Oppure potresti semplicemente utilizzare l'output di quelli direttamente dal momento che sono tecnicamente PRNG stessi seminati da altri dati casuali.

Se openssl_random_pseudo_bytes imposta il flag che indica che non ha generato byte casuali sicuri, sembrerebbe che ci sia qualcosa di sbagliato nell'ambiente perché i manuali suggeriscono che ci si dovrebbe aspettare che restituisca true in condizioni normali. Controllare per vedere quale versione di PHP / OpenSSL è installata e se è possibile aggiornarla. Se non riesci a farlo funzionare, considera solo i dati casuali direttamente da /dev/random o CryptGenRandom() .

    
risposta data 10.08.2012 - 17:55
fonte
1

Se il motivo per cui le funzioni non sono sicure è perché puoi esaurire lo spazio seme dopo aver visto un numero molto piccolo di valori, allora questo approccio potrebbe dare la somma del numero di bit di sicurezza di sicurezza, assumendo che i semi fossero perfettamente casuali.

Se il problema è che hanno un breve periodo, se le funzioni hanno periodi co-prime a coppie, allora il periodo della funzione composita è il multiplo dei tre periodi, altrimenti è il multiplo comune più basso.

Nel complesso, l'aumento della sicurezza è probabilmente marginale, dato che i periodi potrebbero essere poteri di due, e che una combinazione di esaurimento dello spazio seme di uno e del periodo dell'altro sarebbe una tattica efficace. In teoria potresti avere un aumento esponenziale della sicurezza, ma è probabile che un attacco combinato possa essere trovato rapidamente. Ad esempio il seme di uno potrebbe non essere indipendente dai semi degli altri se sono basati sul tempo e le chiamate sono sequenziali.

Per rispondere alla seconda parte della tua domanda, ho visto questo link su SO per un codice che potrebbe fare ciò che vuoi.

    
risposta data 10.08.2012 - 16:38
fonte

Leggi altre domande sui tag