Difetto nella crittografia tramite flusso di numeri pseudocasuali (dalla documentazione PGP)

Un PRNG che è "buono" (con forti garanzie di casualità statistica, ad esempio, oltre ad avere un lungo periodo) non dice nulla sulla sua sicurezza. Vedi per es. discussione in questo thread .

Il thread discute la differenza tra:

• one time pad (infrangibili in linea di principio a patto che non siano né trapelati né riutilizzati, ma di solito non praticabili)
• codice di flusso (che può essere reso sicuro se necessario e può essere abbastanza pratico)
• PRNG (che non sono stati progettati per essere crittograficamente protetti) usati come codici di flusso (tipicamente facilmente interrotti)

Quello che Phil avrebbe dovuto usare era una cifratura del flusso, non solo un vecchio PRNG. MT (e precedenti PRNG) non sono adatti per l'uso come codice di streaming. Salsa20 / ChaCha (di Dan Bernstein) e ISAAC sono due codici di flusso specifici. ISAAC è utilizzato da shred . Salsa20 fa parte del programma UE eSTREAM / ECRYPT . Certo, Phil può essere perdonato per non aver usato un codice stream: RC4 (che è considerato rotto - la sua debolezza è parte di ciò che rende insicuro il WEP - ma che è la base per ISAAC) è stato inventato solo nel 1987.

Le debolezze crittografiche dei PRNG normali (inclusi MT e Wichmann-Hill) hanno portato a vulnerabilità, ad es. Attacchi con numero di sequenza TCP. A volte tali vulnerabilità vengono indirizzate usando un diverso tipo di CSPRNG, che raccoglie l'entropia "mentre va" (ad esempio, dal jitter del mouse / temporizzazione). Per essere idonei all'uso come codice di flusso, i CSPRNG devono disporre di tutta l'entropia di input disponibile all'inizio, piuttosto che raccoglierla nel modo corretto. Vedi le pagine di Wikipedia su CSPRNGs e su / dev / [u] casuale .

Non ho idea di quale sia il metodo utilizzato da Phil Zimmerman per la sua crittografia, quindi non posso dire nulla al riguardo.

Tuttavia, Mersenne-Twister può essere inserito in un cifrario di flusso "sicuro", ad esempio CryptMT . CryptMT è stato successivamente rotto, tuttavia: Distinguishing Attack on CryptMT . Leggendo quella carta probabilmente ti viene un'idea abbastanza precisa su come attaccare Mersenne-Twister e il suo tipo.

In realtà, ho fatto qualche altra indagine. Prima di tutto, il documento che ho citato è stato successivamente redatto dagli autori, vedi la discussione qui , e era contro CryptMTv1, non CryptMTv3 che è la versione corrente. Non ci sono attacchi noti contro CryptMTv3. Il più vicino a un attacco che ho trovato è sulla sicurezza di Stream Cipher CryptMT v3 , che dice esplicitamente:

However, we have not found any non-randomness about the keystream output.

Inoltre, il report finale di eSTREAM per CryptMT dice:

CryptMT v3. The cipher CryptMT has a very unusual design which delivers very reasonable performance. While there have been no negative cryptanalytic results against the cipher in the last phase of eSTREAM, we are somewhat concerned that the security of the cipher, in particular the non-linear filter component, might not yet be as well-understood as some of the other finalists. We anticipate that elements of CryptMT will continue to be of interest to the cryptographic community, and we hope that the full advantages of the approach embodied in CryptMT v3 can be evaluated. However, we are currently not sufficiently confident in the design and security of this algorithm for us to include it in the final portfolio.

Quasi un merito negativo!

Inoltre, osservando la "prestazione molto ragionevole" menzionata sopra in eBASH , sembra che CryptMTv3 offre prestazioni sorprendenti per i messaggi lunghi (ad esempio, 1,82 cicli per byte per i messaggi lunghi), spesso solo ottimizzato da Salsa20 / 8, dove Salsa20 / 8 è già stato interrotto (a malapena, e Salsa20 / 12 è ancora molto sicuro).

Quindi direi che CryptMT è sicuramente un contendente nei flussi di codice anche se non è stato ancora analizzato abbastanza!

Qualsiasi semplice cifrario XOR / PRNG in cui la chiave viene utilizzata per inizializzare il PRNG è vulnerabile a un attacco in testo normale con complessità 1:

1. Cripta un testo in chiaro almeno fino al testo cifrato sconosciuto.
2. XOR il testo in chiaro noto con il suo testo cifrato. Questo ti dà il keytream .
3. XOR il keystream con il testo cifrato sconosciuto: questo ti dà il testo in chiaro originale.

Se riesci a crittografare un testo in chiaro composto da tutti gli "0", puoi saltare il passaggio 2: l'output del processo di crittografia è il keystream.

Non importa quale PRNG stai utilizzando: tutto da RANDU a Fortuna è vulnerabile a questo tipo di attacco per il recupero di chiavi tradizionali.

Si noti che ci sono cifrari che usano "XOR il testo in chiaro con il keystream" come nucleo della loro operazione. Tuttavia, prendono precauzioni per prevenire questo attacco: one-time pad non riutilizzano mai la password, i codici di flusso richiedono chiavi a uso singolo o valori monouso denominati nonces e feedback di output e modalità di funzionamento a blocchi di cifratura usa sia la chiave che un secondo valore monouso chiamato vettore di inizializzazione per garantire che l'RNG non venga mai seminato lo stesso due volte.

Penso che il modo migliore per affrontare questa questione come laico crittografico sia quello di allontanarsi dalla crittografia moderna e considerare invece i codici classici, carta e matita. In questo caso, probabilmente il miglior esempio da considerare è la chiave in esecuzione :

In classical cryptography, the running key cipher is a type of polyalphabetic substitution cipher in which a text, typically from a book, is used to provide a very long keystream.

Fondamentalmente, un tale codice prende un testo in chiaro e un testo di lingua naturale altrettanto lungo (ad esempio, un passaggio da un romanzo) e crittografa ogni lettera del testo in chiaro spostandola di una quantità che dipende dalla corrispondente lettera di keystream.

Tali codici sono facilmente infrangibili:

[I]f (as usual) the running key is a block of text in a natural language, security actually becomes fairly poor, since that text will have non-random characteristics which can be used to aid cryptanalysis. As a result, the entropy per character of both plaintext and running key is low, and the combining operation is easily inverted.

To attack the cipher, a cryptanalyst runs guessed probable plaintexts along the ciphertext, subtracting them out from each possible position. When the result is a chunk of something intelligible, there is a high probability that the guessed plain text is correct for that position (as either actual plaintext, or part of the running key). The 'chunk of something intelligible' can then often be extended at either end, thus providing even more probable plaintext - which can in turn be extended, and so on. Eventually it is likely that the source of the running key will be identified, and the jig is up.

La ragione per cui tali attacchi funzionano è perché:

1. L'utente malintenzionato normalmente ha alcune informazioni parziali sul testo in chiaro. Nella crittografia classica questo sarebbe il probabile linguaggio e argomenti in chiaro (che implicano le frequenze di lettere e parole e le dipendenze tra lettere e parole consecutive). Nella crittografia moderna, questo sarebbe il protocollo di comunicazione che viene crittografato (ad esempio, HTTP su SSL), i punti finali della connessione (ad es. Google), ecc.
2. Un linguaggio dei tasti in linguaggio naturale ha schemi tali che, date alcune lettere dal keystream, devi indovinare le prossime lettere con probabilità molto alta. Ora la cosa fondamentale da osservare è che i PRNG non crittografici hanno anche questa proprietà e quindi ammettono attacchi simili.

Questa serie di blog descrive come rompere semplici RNG congruenziali lineari e il Mersenne Twister. Per java.util.Random RNG, se hai due% di output consecutivi di% co_de dal PRNG, è sufficiente ricostruire il suo stato e prevedere il resto del flusso pseudocasuale (sia in avanti che all'indietro). Pertanto, se hai usato quel PRNG per generare il tuo keystream, un utente malintenzionato che conosce o indovina otto byte consecutivi del testo cifrato può quindi applicare una variante dell'attacco di cifratura in esecuzione e le tecniche di cracking PRNG della serie blog per decifrare il resto del messaggio.

Parte 3 della serie di blog descrive come puoi prevedere in modo simile l'output di un Mersenne Twister se riesci a ottenere 624 parole in uscita consecutive. Quindi è più difficile del generatore di congruenza lineare, ma è ancora vulnerabile.