Quali statistiche possono essere utilizzate per identificare i dati pseudocasuali?

Durante il concorso AES , l'ente organizzatore (il NIST) si è preso la briga di eseguire ampi test statistici sul l'output dei 15 codici a blocchi presentati, con quello che si riteneva essere il gold standard di tali test, i test duri . Non hanno trovato nulla, ovviamente. I commenti dei crittografi in quel momento erano che questi test erano un po 'ridicoli nel contesto degli algoritmi crittografici (commenti non ufficiali, ovviamente: sarebbe scortese mettere in imbarazzo l'ospite dell'evento); è stato positivo per le pubbliche relazioni che qualcuno le gestisce, ma da questo non ci si aspettava che ne valesse la pena.

Questo illustra la differenza tra casualità statistica , come è necessario ad esempio per potenziare le simulazioni di sistemi fisici e imprevedibilità , necessaria per la sicurezza. Prendi in considerazione ad esempio il seguente PRNG :

• Imposta un contatore su un seme a 128 bit.
• Per produrre i successivi 128 bit del PRNG, incrementa il contatore di 1, quindi cripta quel valore con AES e una chiave all-zero, ottenendo i 128 bit.

Questo PRNG supererà con successo tutti i test della suite Diehard; è statisticamente "perfetto" per quanto riguarda i test (la partenza dalla pura alea potrebbe essere rilevabile dopo aver generato circa 2 ⁷¹ bit, cioè più di 200 milioni di terabyte). Tuttavia, per sicurezza , è terribile, dato che è banale predire l'output futuro dopo che sono stati osservati 128 bit di output (decifrati questi 128 bit con AES e una chiave all-zero: questo ti darà il valore corrente del contatore).

Riepilogo: un PRNG crittograficamente sicuro produce un output che è indistinguibile dalla casualità; non solo con test statistici, ma anche da qualcuno che conosce esattamente l'algoritmo PRNG che è stato potenzialmente utilizzato. Se si dispone di uno strumento statistico che può mostrare che una determinata sequenza di byte proviene da un PRNG, allora si è dimostrato non solo che il PRNG non è crittograficamente sicuro, ma anche che è terribilmente cattivo. Anche l'hash di Dave è "casuale" dal punto di vista dei test di Diehard.

In parole più brevi, il tuo strumento non catturerà la casualità che è stata generata con un po 'di esperienza, ma non catturerà la maggior parte della non casualità da parte di tutti i dilettanti. Con tali strumenti, non stai prendendo di mira "non-crittografi che dovrebbero sapere meglio di usare schemi fatti in casa", ma piuttosto "scimpanzé a cui non dovrebbe essere permesso di toccare una tastiera".

Nota: i buoni steganografia strumenti crittografano i dati prima di inserirli nel supporto di trasporto, precisamente per evitare il rilevamento da uno strumento statistico. Anche la crittografia dovrebbe fornire bit indistinguibili dalla casualità.

link utilizza il seguente

• Test del chi quadrato
• Media aritmetica
• stima Monte Carlo Pi
• Coefficiente di correlazione seriale

Potresti anche aggiungere "incompressione" (questo significa anche che potresti dover identificare i file compressi per eliminarli). Il suggerimento di Dan D's Diehard ( e Dieharder ) sembra una soluzione molto approfondita. ( Modifica: Dieharder è strettamente mirato a testare i PRNG, non le istantanee del loro output, e sicuramente non adatto per campioni di dati di piccole dimensioni.)

Il tuo compito condivide alcuni dei problemi coinvolti nella statistica File Carving e nella ricerca forense di dati crittografati: più piccoli sono i dati impostare il più difficile è essere definitivo su se è "casuale".