Predicibilità di PHP array_rand

4

È generalmente noto che metodi come il metodo array_rand() in PHP non sono considerati crittograficamente sicuri. Sto cercando di capire in quali situazioni i risultati generati potrebbero essere prevedibili.

Se conosco il seme, i valori nell'array, un singolo valore generato e quante volte il metodo è stato chiamato prima che quel valore sia stato generato, so che posso facilmente calcolare tutti i valori restituiti successivamente. Posso farlo scrivendo il mio script che usa lo stesso seme e genera lo stesso numero di risultati, mettendolo quindi nello stesso stato.

Supponendo che non conosca il seme o il numero di valori precedentemente generati, quali sono le mie possibilità / quanto in basso posso ottenere la probabilità di prevedere i valori futuri.

Per definire un esempio più concreto e rendere la domanda meno teorica, supponiamo di utilizzare array_rand per generare token alfanumerici senza distinzione tra maiuscole e minuscole con una lunghezza di 12. Ciò viene ottenuto acquisendo 12 valori da un array di caratteri mediante chiamare array_rand 12 volte, rendendo così il token [A-Z\d]{12} . So di avere uno dei mille token generati consecutivamente, ma non in quale posizione è stato generato.

Posso prevedere il prossimo token (presumo che non abbia generato l'ultimo token)? Suppongo che questo non possa essere previsto con una precisione del 100%, ma quali sono le possibilità che i brute forzino tutte le possibilità per il prossimo token, e quanti sarebbero?

Supponendo che io possa convalidare se un token è valido, quanto sa che 2 gettoni consecutivi (24 valori) restringono le mie possibilità di prevedere il 3 °, ecc.

Ho visto alcune ricerche sul cracking dello stato di rand ma gli articoli in genere non hanno a che fare con intervalli vincolati / troncati.

P.S. Sto cercando di capire la prova / matematica dietro perché è insicuro, non alla ricerca di suggerimenti di approcci più sicuri.

    
posta Peter O'Callaghan 30.07.2016 - 16:12
fonte

3 risposte

1

Potresti invece costruire i tuoi dati basandoti sul% più sicuro% co_de dalla libreria OpenSSL. Ciò implica ovviamente una conversione di base per ottenere l'intervallo richiesto ma non si basa su una tabella casuale con seeding come altre funzioni (come openssl_random_pseudo_bytes() ).

Tieni presente che il valore di rand() incorporato in PHP è in realtà molto migliore del classico mt_rand() in termini di efficienza e casualità (maggiore distribuzione normale), ma è ancora presente in serie.

Entrambi i metodi, se correttamente implementati, richiederanno lo stesso sforzo alla forza bruta. La differenza principale è che una volta che la forza bruta ha avuto successo, potrebbe essere possibile per un utente malintenzionato trovare maggiori dettagli sui modelli di implementazione o trovare il seme che quindi rende più facile il prossimo attacco.

In pratica, i casi in cui realmente farà davvero la differenza sono estremamente rari, ma ci sono stati casi in cui è stato abusato. Il migliore (e unico) esempio di cui sono a conoscenza è in una slot machine del casinò di Montreal dove questo ragazzo ha trascorso settimane a cercare i modelli e alla fine l'ha fatto a causa del seme.

    
risposta data 30.07.2016 - 17:09
fonte
1

Bene, se vuoi sapere come prevedere un PRNG, google it. Scopri quale PRNG è utilizzato per array_rand e google, ad esempio "predice mersenne twister" (senza virgolette) mi fornisce due link github (nei primi 3 risultati) a persone che sono riuscite a scrivere un programma per predire il prossimo uscite basate su quelle precedenti.

Chiedete esplicitamente dopo aver predetto il PRNG quando l'output grezzo non viene fornito, ad es. quando viene utilizzato per generare caratteri casuali (che hanno solo un intervallo limitato, ad esempio 0-26 per lettere minuscole). Questo lo rende molto più difficile, ma potrei immaginare che sia ancora fatto con qualche congettura se non si ha il codice sorgente (test black box).

In un test del riquadro bianco, in cui è noto il codice sorgente, dovrebbe essere abbastanza semplice. Uno potrebbe aver bisogno di più uscite per recuperare lo stato (se parte dell'output del PRNG viene gettato via), ma dovrebbe essere un processo molto simile.

Non sono sicuro che ci sia una prova matematica, come chiedi, che dimostra che tutti i non-CSPRNG devono essere prevedibili. Penso che siano tutti prevedibili tranne quelli che sono fatti (e forse provati) per avere certe proprietà.

    
risposta data 30.07.2016 - 17:37
fonte
1

array_rand chiama mt_rand internamente . Questo è un algoritmo di twister Mersenne con una dimensione dello stato di 624 numeri. Ciò significa che se ottieni 624 output consecutivi di mt_rand , conosci l'intero stato e puoi prevedere tutti i numeri futuri.

Come si indica correttamente, è piuttosto difficile ottenere l'output di mt_rand nei casi reali, perché in genere è limitato a un intervallo. Questo non è necessariamente un problema per l'attaccante: se l'applicazione chiama mt_rand(0, 8) l'attaccante conosce solo tre bit dello stato, ma deve anche prevedere solo tre bit per predire l'output degli algoritmi.

Un altro problema pratico con il cracking dei PRNG è che l'utente malintenzionato deve richiedere token dallo stesso processo, poiché diversi processi hanno stati PRNG diversi. In genere quando ci si connette a un server la richiesta viene gestita da un processo casuale. Puoi fare fino a 100 richieste su una connessione, ma questa è ancora a corto delle 624 richieste necessarie per ottenere lo stato di mt_rand .

Nel tuo esempio chiami array_rand 12 volte, quindi l'autore dell'attacco non ottiene alcun risultato intermedio di mt_rand . Ci sono troppe combinazioni qui per la forza bruta.

Quindi questo potrebbe essere praticamente sicuro, ma sarebbe rischioso. Un'applicazione che ho esaminato ha utilizzato anche mt_rand per la generazione di token, e poi ha avuto un'altra pagina che ha chiamato mt_srand() . Ciò ha permesso di seminare il PRNG con un valore noto. Ho anche ho scritto qualcosa sul cracking dei PRNG PHP, sebbene non vada in mt_rand cracking dello stato.

    
risposta data 30.08.2016 - 10:04
fonte

Leggi altre domande sui tag