Ho pensato che questa fosse una domanda e un problema piuttosto interessanti, quindi ho provato a implementare gli attacchi da solo, ma contro qualcosa di diverso da "vero" o "falso".
Per semplificare le cose ho usato una pagina statica come file e ho inserito del contenuto al suo interno alla fine. Il segreto bersaglio assomigliava a questo:
<input type="hidden" name="secret" value="7253b8f45f322b411ce39b12c6e9a84c" />
Ho usato l'origine di una pagina MSDN come esempio per costruire intorno. La sorgente completa della pagina di destinazione che ho utilizzato può essere trovata qui ; il segreto è sulla linea 33. Un fattore importante qui è che il contenuto della pagina include molte altre stringhe esadecimali, che imitano uno scenario di attacco potenzialmente più difficile.
Per attaccare questo, ho usato un metodo abbastanza ingenuo:
- Aggiungi
<input type="hidden" name="secret" value=" alla fine della pagina, quindi aggiungi le nostre ipotesi precedenti (se presenti), quindi aggiungi 0000 a ffff in sequenza e cerca il risultato più piccolo quando è compresso.
- Per la stringa esadecimale a 4 caratteri che ha prodotto il risultato più piccolo, aggiungi i primi tre caratteri a nostra discrezione. Eliminare l'ultimo personaggio è importante in quanto c'è un po 'di incertezza nell'ultimo carattere, e se ha torto si tende a generare ripetutamente l'ultimo carattere per tutte le ipotesi rimanenti (ad esempio
7251 sul primo genererebbe 1111 su tutte le supposizioni successive).
- Passa ai passaggi 1 e 2 finché non rimangono 4 caratteri da indovinare. Esegui le rimanenti combinazioni possibili, aggiungendo in ogni caso
" /> alla stringa aggiunta per completare il tag.
Ho scritto un'implementazione completa con parallelismo in C #, che puoi trovare qui .
Ecco i risultati di GZip:
................................
Guessed f45a
Secret: 7253b8f45
................................
Guessed f322
Secret: 7253b8f45f32
................................
Guessed 2b41
Secret: 7253b8f45f322b4
................................
Guessed 11ca
Secret: 7253b8f45f322b411c
................................
Guessed e39a
Secret: 7253b8f45f322b411ce39
................................
Guessed b12a
Secret: 7253b8f45f322b411ce39b12
................................
Guessed c6e9
Secret: 7253b8f45f322b411ce39b12c6e
................................
Guessed 9a84
Secret: 7253b8f45f322b411ce39b12c6e9a8
Reached last block.
Guessed 4c
Secret: 7253b8f45f322b411ce39b12c6e9a84c
Done!
Ci sono voluti solo un paio di minuti per eseguire correttamente il segreto.
Ora proviamo ancora con Brotli, usando la modalità di compressione "più veloce", con la stessa configurazione per l'attacco:
................................
Guessed 7253
Secret: 725
................................
Guessed 3b77
Secret: 7253b7
................................
Guessed 4aa7
Secret: 7253b74aa
................................
Guessed 47aa
Secret: 7253b74aa47a
................................
Guessed 0aaa
Secret: 7253b74aa47a0aa
................................
Guessed 0aaa
Secret: 7253b74aa47a0aa0aa
................................
Guessed 3a0a
Secret: 7253b74aa47a0aa0aa3a0
................................
Guessed 0aaa
Secret: 7253b74aa47a0aa0aa3a00aa
................................
Guessed 4aaa
Secret: 7253b74aa47a0aa0aa3a00aa4aa
................................
Guessed 2aaa
Secret: 7253b74aa47a0aa0aa3a00aa4aa2aa
Reached last block.
Guessed 7a
Secret: 7253b74aa47a0aa0aa3a00aa4aa2aa7a
Done!
Non così buono. La seconda ipotesi va storta e questo elimina l'intero algoritmo. Quindi forse dobbiamo essere un po 'più cauti e accettare solo 2/4 caratteri per blocco anziché 3/4.
................................
Guessed 411c
Secret: 7253b8f45f322b41
................................
Guessed 1c77
Secret: 7253b8f45f322b411c
................................
Guessed e377
Secret: 7253b8f45f322b411ce3
................................
Guessed 9b12
Secret: 7253b8f45f322b411ce39b
................................
Guessed 1277
Secret: 7253b8f45f322b411ce39b12
................................
Guessed c677
Secret: 7253b8f45f322b411ce39b12c6
................................
Guessed e977
Secret: 7253b8f45f322b411ce39b12c6e9
................................
Guessed a84c
Secret: 7253b8f45f322b411ce39b12c6e9a8
Reached last block.
Guessed 4c
Secret: 7253b8f45f322b411ce39b12c6e9a84c
Done!
E lì possiamo vederlo funzionare di nuovo! Quindi risulta che non è impossibile attaccare Brotli in questo modo.
La parte chiave che spiega il motivo per cui l'attacco non è riuscito è il dizionario predefinito:
Unlike most general purpose compression algorithms, Brotli uses a pre-defined 120 kilobyte dictionary, in addition to the dynamically populated ("sliding window") dictionary. The pre-defined dictionary contains over 13000 common words, phrases and other substrings derived from a large corpus of text and HTML documents
(da Brotli - Wikipedia )
Quindi "vero" e "falso" appaiono in questo dizionario? Sì! Ho trovato una copia testuale del dizionario qui e puoi trovare true e false sulle righe 6829 e 1204 rispettivamente.
Il motivo per cui il mio attacco funziona e il tuo no non è che sto cercando qualcosa che non sia nel dizionario. Per un singolo token come "true" o "false", l'utilizzo dell'indice del dizionario è molto più efficiente rispetto al tentativo di piegare i caratteri insieme a un'altra istanza nello stream utilizzando la codifica della distanza.
Ma perché è stato più difficile per me eseguire un oracle di compressione riuscito usando Brotli piuttosto che con GZip? Non sembrano esserci molte stringhe esadecimali nel dizionario. Credo che questo sia semplicemente perché il sistema di compressione Brotli è più complesso di GZip. GZip usa una combinazione di LZ77 e codifica di Huffman, che ha una strong attenzione all'eliminazione dei duplicati, che funziona perfettamente per un attacco di oracolo di compressione. Brotli, d'altra parte, ha più asso nella manica, portando ad una maggiore probabilità di utilizzo di altri meccanismi di compressione invece dell'eliminazione duplicata durante i primi blocchi quando il duplicato non è molto lungo. Un modo per migliorare l'attacco per Brotli sarebbe quello di forzare la forza bruta su un insieme più lungo di valori nel primo blocco (ad esempio 6 o anche 8 caratteri) per cercare di ottenere un'eliminazione duplicata. Questo è molto più lento ma probabilmente forzerebbe un oracle di compressione affidabile dal compressore Brotli.