L'hashing di un PRNG lo rende crittograficamente sicuro?

10

L'hashing del risultato di un normale generatore di numeri casuali produce un PRNG crittograficamente sicuro?

Ad esempio, sha1(rand()) sarebbe effettivamente un PRNG sicuro?

Supponendo che non lo faccia, come faresti ad attaccarlo?

Modifica: supponiamo che per attacco intendo determinare il valore successivo che genererà dopo aver visto una serie di valori che ha prodotto.

Nota: dovrei notare che non sto scegliendo di implementare un PRNG in questo modo. Sono davvero interessato ad analizzare le proprietà di questo perché ho visto costrutti simili nel codice. Non mi sembra una buona idea, ma sto facendo fatica a pensare al modo migliore per attaccarlo.

    
posta Colin Newell 08.06.2013 - 22:34
fonte

4 risposte

7

L'hashing dell'output di un RNG è tipicamente un componente di un RNG crittograficamente sicuro, ma non è magico. Non può rendere improvvisamente sicuro un RNG schifoso.

Un componente chiave in un RNG crittograficamente sicuro è l'assoluta imprevedibilità. Se puoi prevedere l'output, puoi usare quella previsione come parte del tuo attacco. L'esecuzione dell'output tramite un hash non modifica la prevedibilità.

Supponiamo, ad esempio, che il mio super generoso generatore di numeri casuali si alternhi tra la restituzione dei numeri 4 e 7. Puoi obiettare che il mio RNG è orribile e avresti ragione. Ma diciamo che ora si esegue l'output tramite SHA1. Quindi si alterna tra restituire SHA1 (4) e SHA1 (7). Ancora non casuale. Quindi la risposta è NO.

Ma gli hash sono utili per gli RNG crittografici

D'altra parte, diciamo che hai una vera fonte di entropia (es. un contatore geiger puntato su un blocco di plutonio ) che genera risultati casuali ma nel nostro caso distorti. A causa del nostro apparato di campionamento, il flusso di uscita è del 57% 1 e del 43% 0. È casuale che non sia assolutamente possibile prevedere i risultati, ma se indovini "1", avrai ragione più spesso.

Possiamo neutralizzare questo errore eseguendo l'output attraverso un hash crittografico. Una delle proprietà di un hash crittografico è che l'output NON è influenzato in modo intrinseco, indipendentemente dall'input. Ovviamente dobbiamo raccogliere blocchi di input di input abbastanza lunghi da evitare di raddoppiare lo stesso valore due volte. Ma l'output finale avrà un numero approssimativamente uguale di 1 e 0, il che rende la nostra crittografia più sicura.

    
risposta data 09.06.2013 - 08:32
fonte
6

L'hashing non ha alcun effetto per aumentare la sicurezza di un PRNG come rand() . Infatti, se l'uscita del PRNG è maggiore dell'uscita della funzione di hashing, ne diminuirà la sicurezza.

sha(rand()) è, fondamentalmente, sicurezza per oscurità. Supponi che rendendo l'output PRNG visualizzato più casuale lo renderà più sicuro, il che non è corretto. Non affronterò l'argomento dei generatori di numeri pseudo casuali crittografati (CSPRNGs) , poiché non sto bene- esperto in materia. Devi solo sapere che se un% arbitrario rand() non è sicuro, non importa come si modifica l'output, esso rimarrà insicuro e potrebbe addirittura renderlo meno sicuro.

Ora, se stai parlando di PHP / C's rand() , allora è importante sapere che è lontano dall'essere un PRNG crittograficamente sicuro.

Poiché CodiciInChaos ha detto , il il maggior problema con rand() è la fonte del seme. Esaminando php-src/ext/standard/php_rand.h , puoi vedere chiaramente come è il seme generato

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

php_combined_lcg() si riduce a un generatore lineare congruenziale (LLG) , e quelli, LLGs, non sono raccomandati per essere usato per scopi di crittografia.

L'attacco

Il valore restituito da php_combined_lcg() è identico al valore restituito da uniqid() che potrebbe essere trapelato attraverso nomi di file generati, password generate, token mal implementati, ecc. Una volta che l'attaccante acquisisce quel valore, il resto è semplice. I valori di time() e getpid() sono ragionevolmente forzabili.

    
risposta data 09.06.2013 - 02:49
fonte
2

Parte 1

No, questo non è sicuro, non sarebbe semanticamente sicuro (perché Random () non è sicuro)

Direi che non sarebbe sicuro perché una funzione hash riduce l'entropia del suo input. In altre parole, una funzione di hash di solito ha meno di una mappatura 1: 1 dei risultati da inserire, e ha una maggiore possibilità di scontrarsi con gli input precedenti rispetto a quanto fa l'input raw stesso.

In questo caso, l'input non casuale sarà semplicemente "più lungo" con più bit, ma non lo renderà più casuale, che è la base della maggior parte delle esigenze di crittografia. (Pensa a One Time Pad)

Una soluzione migliore:

Alimenta l'input non casuale in un "HKDF". Un HKDF consente di derivare molte chiavi da una chiave, con l'ipotesi che la chiave di origine / PRF non sia necessariamente casuale. L'HKDF usa il paradigma "Estrai poi espandi" che aggiunge casualità usando un "sale" non segreto che è casuale. Esempio HMAC(salt, yourKey)

Un altro approccio è quello di alimentare quell'input non casuale in un codice di flusso come AES o 3DES e usarlo come una volta sola (o qualsiasi altra cosa tu voglia usare per)

Come lo attaccheresti?

Devo sapere come viene usato. L'attacco è lo stesso dell'attacco a caso () con il ritardo di hashing aggiunto in seguito. La versione semplificata di questo attacco è sapere che l'area che hai bisogno di forza bruta è molto più piccola di 2 ^ 51 e che è probabilmente non trascurabile.

In un esempio di codice di flusso, significa che SHA1 causerà una collisione in meno di 281,5 terabyte è crittografato e la funzione rand () lo riduce ulteriormente. (se qualcuno sa come calcolare questo apprezzerei le informazioni)

Parte 2

Concentrati solo sull'aspetto "hashing" che non ha la relazione con un PRNG come sospetti:

Le collisioni sono cattive perché permettono all'attaccante di fare molte cose, come implementare un messaggio scelto, una falsificazione esistenziale o una serie di altri attacchi, a seconda di dove usi l'output dell'hash risultante.

In termini di hashing, è più probabile che si verifichi una collisione nelle operazioni 2 ^ n / 2 (all'incirca la radice quadrata della dimensione dello spazio di output).

Name       Size    Attack Operations
SHA-1       160    2^80               (Insecure, don't use)
SHA-256     256    2^128 
SHA-512     512    2^256
Whirlpool   512    2^256              (AES based and slowest)

Quanto sopra elencato è la migliore resistenza di collisione possibile (in teoria) basata esclusivamente sul numero di bit nell'output.

Tieni presente che la sicurezza realistica di un hash sarà probabilmente meno sicura del massimo teorico. Prendiamo ad esempio SHA-1, il collision finder più conosciuto richiede solo 2 ^ 51 valutazioni hash e il caso teorico migliore è 2 ^ 80)

    
risposta data 09.06.2013 - 00:13
fonte
-1

Ciò dipende completamente dai requisiti di sicurezza dell'applicazione, dal generatore di numeri casuali e dalla funzione di hash. Il fatto è che potrebbe essere sicuro, ma rispondere a questa domanda richiederebbe un'attenta ricerca. "Sicuro" non significa sempre la stessa cosa in ogni contesto. In che modo un utente malintenzionato tenta di sfruttare il generatore di numeri casuali compromesso? Quando i ricercatori di sicurezza sviluppano strumenti come CSPRNG cercano di soddisfare determinati requisiti che possono renderlo uno strumento sicuro per un'ampia varietà di applicazioni.

Detto questo, in genere è una cattiva idea creare le proprie soluzioni di sicurezza, specialmente quando sono basate su buone idee, perché il diavolo si trova nei dettagli e un bug sottile è molto più pericoloso di un ovvio.

Ti suggerisco di passare un po 'di tempo a leggere come funziona l'HMAC. A prima vista, l'hash (messaggio | secretkey) sembra essere un modo efficace per creare un codice di autenticazione del messaggio. Tuttavia, a causa di alcune debolezze inevitabili delle funzioni hash, tra le altre ragioni, gli esperti di sicurezza hanno deciso che l'hashing dell'input e / o della chiave più volte e l'introduzione di pad in mezzo possono creare un codice di autenticazione più sicuro.

Se hai bisogno di un po 'di tempo per capire perché gli HMAC sono fatti come sono, potrebbe aiutarti ad apprezzare perché i CSPRNG raccomandati siano probabilmente migliori di quello che puoi fare da soli.

Detto questo, sembra che quello che vuoi fare sia tagliare degli angoli. Invece di chiedere, come posso fare un CSPRNG mezzo ass? Potresti chiedere se il tuo generatore di numeri casuali ha davvero bisogno di essere crittograficamente sicuro.

Se hai davvero bisogno di quel livello di sicurezza, dovresti farlo bene. Se non ne hai bisogno, andare a metà strada serve solo a darti un falso senso di sicurezza e rende difficile analizzare e prevedere i tuoi punti deboli di sicurezza.

Se sono un hacker, un bug o debolezza ben nascosto (qualcosa di simile al cuore), sarà infinitamente più prezioso di qualcosa di ovvio, che verrà riconosciuto e corretto non appena diventerà abbastanza importante da meritare attenzione.

Direi che è uno dei motivi più importanti per non inventare il proprio quando si tratta di sicurezza.

Se sei interessato a ricercare in modo più approfondito il potenziale di sicurezza del tuo schema proposto, questo potrebbe essere un punto di partenza. È una domanda correlata nello scambio di stack di crittografia:

link

    
risposta data 25.04.2014 - 18:59
fonte

Leggi altre domande sui tag