Rileva l'uso del PRNG dall'output

5

Domanda: esiste un modo per rilevare l'utilizzo di un PRNG rigorosamente osservando l'output fornito da un'applicazione?

Background: Durante un controllo di un algoritmo di generazione di chiavi che sapevo era basato sull'LCG, ho notato che il sequencer di Burp valutava l'entropia dei tasti come strong, il che è falso in quanto sono prevedibili. Ho quindi alimentato lo stesso test con interi grezzi generati dal modulo casuale basato su Mersenne Twister di Python per vedere di nuovo l'entropia valutata di nuovo.

Il fallimento di questo strumento mi ha fatto meravigliare se ci sono strumenti / approcci disponibili per rilevare effettivamente l'uso di PRNG dall'output.

    
posta 0x90 09.01.2013 - 03:15
fonte

1 risposta

8

Se il PRNG è crittograficamente strong , quindi, per definizione, il suo output non può essere distinto da byte casuali. Questo è l'esperimento mentale con il quale si suppone che un PRNG sia testato: due caselle nere vengono date all'attaccante, una che implementa il PRNG, l'altra produce byte veramente casuali (quella contiene uno gnomo che lancia i dadi molto veloce ). Gli obiettivi degli attaccanti sono di trovare quale casella contiene il PRNG, con un tasso di successo migliore della pura fortuna (cioè il 50%).

I PRNG che sono NON crittograficamente forti, come Mersenne Twister, possono essere riconosciuti come tali da un utente malintenzionato che li colpisce specificatamente . Ma non necessariamente con uno strumento di analisi statistica generico.

Per fare un'analogia, esistono PRNG che sono forti contro gli eserciti di crittografi che conoscono il codice sorgente completo del PRNG e hanno accesso a migliaia di computer di grandi dimensioni. Ci sono anche PRNG che possono essere dichiarati non casuali da una marmotta che brandisce un abaco. E ci sono PRN che sono nel mezzo: i semplici strumenti generici non li cattureranno, ma ciò non significa che non possano essere catturati, ma solo che ci vorrà un po 'più di sforzo.

(Matematicamente, non è noto se il PRNG crittograficamente strong possa realmente esistere - questa è tutta la differenza tra un algoritmo che non può essere infranto e un algoritmo che non sappiamo come rompere. Un corollario è che lo facciamo Non so se può esistere uno strumento di analisi implementabile che riconosca in modo affidabile tutto il PRNG non strong. In questo momento , abbiamo PRNG che è crittograficamente debole, ma statisticamente molto buono, così che strumenti di analisi come Burp il sequencer non troverà nulla di non casuale in essi.)

    
risposta data 09.01.2013 - 04:17
fonte

Leggi altre domande sui tag