Sento sempre che C rand() non è sicuro, ma quante chiamate dovresti sapere per prevedere il valore successivo (o almeno ridurre le possibilità)? Dovrebbero essere sequenziali? Se non ci sono buone informazioni su rand () sono interessato a qualsiasi altro generatore di numeri casuali largamente usato.
Generalmente dipende dall'implementazione. Per la maggior parte, guarderai Generatori di Congruenze lineari o Registri a scorrimento feedback lineare .
Un problema comune con questi tipi di generatori è che il loro periodo è generalmente piuttosto breve e che la loro forma matematica implica una generazione deterministica. In quanto tale, puoi (generalmente) romperle in poche centinaia di chiamate o meno. I risultati sequenziali rendono più semplice l'interruzione dell'algoritmo, dal momento che è possibile creare correlazioni più forti in questo modo, ma non sono necessari.
Il più grande difetto con i generatori "nuovi" è che il seme non è sufficientemente grande. Ad esempio, se si dispone di un generatore con un seme a 32 bit e si conoscono i primi 20 valori del generatore, è banale la forza bruta. Basta generare una sequenza per ogni seme da 0 a 2 ^ 32 e confrontarlo. Puoi utilizzare l'ottimizzazione anticipata per ridurre in modo massivo il costo computazionale di questo.
Pseudo codice:
// the known values from the generator
byte[] knownValues = { 9, 55, 201, 50, 41, 111, 67, 44, 122, 66 };
for(seed = 0 to 2^32)
{
srand(seed);
bool found = true;
for(n = 0 to len(knownValues))
{
if(rand() != knownValues[n])
{
found = false;
break;
}
}
if(found == true)
{
print "Found potential seed: " + seed + "\n";
}
}
Con un RNG abbastanza veloce e alcuni hardware decenti, questo diventa sicuramente un attacco plausibile.
Ti consiglio di leggere quanto segue per una spiegazione esauriente:
Le implementazioni di rand() variano da sistema a sistema. Ho dato un'occhiata a molti di loro, e la sicurezza varia da sincea a pazzesca. Sicuramente non vuoi usare rand() per qualcosa di crittografico.
Su alcuni sistemi, un output da rand() è sufficiente per recuperare il seed e prevedere tutti gli output futuri. Su altri, hai bisogno di 2 uscite da rand() . Su alcuni sistemi, se osservi la sequenza di output da rand()&1 , scopri che ottieni sempre la sequenza 0,1,0,1,0,1, ... - in altre parole, i bit meno significativi di uscite consecutive da rand() alternate tra 0 e 1 (cioè, le uscite da rand() alternano tra dispari e pari).
Quanto è insicuro? Per quanto insicuro possiate immaginare.
Non conosco l'esatta implementazione usata per rand () quindi risponderò invece a un caso generale.
Un popolare generatore casuale non crittografico è Generatore di congressi lineari . Questo può essere previsto con meno di 10 chiamate sequenziali *.
*: Il limite superiore è probabilmente molto più basso, ma questo è stato dato come assegnazione della prima settimana in un corso introduttivo sulla crittografia che dice qualcosa su quanto siano facili da interrompere.
I CSPRNG sono un sottoinsieme di PRNG. Un PRNG deve solo essere statisticamente casuale. Un CSPRNG deve essere statisticamente casuale e resistere alla crittanalisi per determinare i valori passati o futuri anche quando si conosce una buona quantità di informazioni sui valori iniziali e / o passati.
Tutti i PRNG sono abbastanza sicuri quando hai semplicemente bisogno di un valore statisticamente casuale (come i salti delle password o gli ID utente casuali); tuttavia, un CSPRNG è necessario quando il sistema che fa uso di valori statisticamente casuali deve resistere alla crittoanalisi (uso in crittografia).
Leggi altre domande sui tag random