Nelle notizie, ci sono diversi articoli ( qui , qui , e il punto di vista tecnico ) che hanno a che fare con un punto debole di un generatore di numeri casuali.
La domanda è in qualche modo duplice. Quali sintomi mostrano gli RNG deboli? Ciò significa, ad esempio, che diversi semi diversi danno lo stesso risultato? O mi manca quello che intendono per "debole"?
E, Come si passa dall'individuare un RNG debole per decifrare completamente il traffico crittografato?
Quando generi una chiave privata, lo fai con una fonte di casualità. Se tale fonte di casualità può emettere N diversi flussi di bit, allora, al massimo, si può ottenere N una chiave privata diversa. Qui è dove ci piace parlare di entropy , che è una misura di quanto è grande N . Quando si dice che la fonte della casualità offre "100 bit di entropia", significa che (approssimativamente) N = 2 100 .
L'utente malintenzionato vorrà ottenere la tua chiave privata. Se sa che usi una sorgente debole con un N basso (ad esempio, solo 40 bit di entropia), allora può, sulla propria macchina, enumerare tutti i possibili output dalla sorgente casuale e risolvere la chiave privata corrispondente.
Ad esempio, supponiamo di aver usato un seme PRNG con l'ora corrente, espresso in microsecondi. Questo è l'ora conosciuta dalla tua macchina. L'attaccante presume che la tua macchina sia ragionevolmente ben impostata con l'ora corrente, diciamo entro 10 secondi. Quindi, dal punto di vista dell'attaccante, il seme per il tuo PRNG è noto in un intervallo di 10 secondi; dal momento che il PRNG usa il tempo in microsecondi, questo lo lascia con N = 10000000 possibili semi. L'attaccante poi dice a se stesso: "SE quel tipo ha usato il valore di seme x , POI il suo codice ha prodotto il valore della chiave privata K x ; vediamo se questo corrisponde alla sua chiave pubblica ... No. Quindi non ha usato x . Proviamo ancora con x + 1 (e così via). "
Quindi un PRNG debole è mortale in tali situazioni.
Come puoi rilevare un PRNG debole? Beh, il più delle volte non puoi. Un PRNG molto povero può sembrare povero dall'inizio; ad esempio, se generi due chiavi private e ottieni il doppio della stessa, allora probabilmente c'è qualcosa di sbagliato ... ma, come mostra l'esempio "time as seed", questo non è sempre facile da rilevare: il tempo scorre continuamente, quindi tu mai riutilizzare un seme. Eppure questo è debole. Perché la debolezza deriva da quanto sia difficile indovinare lo stato interno della sorgente casuale, che non è lo stesso di essere statisticamente di parte.
Una grande distorsione statistica è rilevabile ed è un'evidente debolezza; ma un PRNG può essere debole senza essere rilevabile come tale.
Se sei un cattivo e vuoi fare un PRNG debole non rilevabile , allora puoi prendere una buona cifra di blocco (ad esempio, AES ), scegliere un valore chiave K e crittografare i valori successivi di un contatore, partendo da 0. Questo produrrà un flusso molto lungo di byte pseudocasuali che nessuno sarà in grado di dimostrare in modo non casuale, proprio perché AES è bravo nella crittografia delle cose. Ma tu, in quanto cattivo, conosci K , quindi puoi facilmente prevedere l'intero stream da solo.
L'unico modo affidabile per rilevare un PRNG debole è di esaminare il metodo esatto con cui funziona il PRNG, fino ai minimi dettagli: quali eventi fisici raccolgono, perché questi eventi possono essere considerati " casuale ", come sono mescolati insieme con algoritmi crittografici per produrre byte pseudocasuali. Non puoi farlo con un hardware RNG opaco, da qui l'attuale serie di voci.
I RNG deboli sono, per definizione, difficili da rilevare (in un flusso casuale tutte le sequenze sono ugualmente probabili, quindi richiederebbe un flusso infinito per dimostrare non casualità), ma una buona definizione è se è possibile (apparentemente) prevedere in modo attendibile la prossima cifra nel flusso casuale è migliore di "caso". Di nuovo, questo è dimostrabile solo se si dispone di un flusso infinito, ma per l'interruzione di crypto, questo non è importante quanto assumere un RNG debole dall'osservazione e utilizzare l'assunto per interrompere effettivamente la crittografia (cioè usando la propria ipotesi di come Lo schema casuale (pseudo) generato è un modo migliore per dimostrare un RNG debole rispetto all'aspettativa di generare un flusso infinito e testarlo per la distribuzione).
Una volta determinato / indovinato come prevedere il pattern in un flusso casuale, se quel flusso è stato usato per generare chiavi, o un time pad, si ha un modo di utilizzare la distribuzione prevista come un modo per ridurre la ricerca spazio per (segreto) indovinare la chiave o cercare la distribuzione in un codice di trasposizione ecc. Per i time pad, è particolarmente un problema in quanto si ha un modo per invertire il pad (che è banale se si conosce una quantità significativa della chiave) .
Tutti gli algoritmi crittografici sono suscettibili di scarsa casualità a un diverso grado di corso e talvolta 'pseudo' è sufficiente.
Leggi altre domande sui tag random cryptography encryption