Pensé que esta era una pregunta y un problema bastante interesante, así que intenté implementar los ataques por mi cuenta, pero contra algo que no sea "verdadero" o "falso".
Para simplificar las cosas, utilicé una página estática como archivo y le inyecté contenido al final. El secreto del objetivo se veía así:
<input type="hidden" name="secret" value="7253b8f45f322b411ce39b12c6e9a84c" />
Utilicé la fuente de una página de MSDN como un ejemplo para construir. La fuente de la página de destino completa que utilicé se puede encontrar aquí ; el secreto está en la línea 33. Un factor importante aquí es que el contenido de la página incluye muchas otras cadenas hexadecimales, lo que imita un escenario de ataque potencialmente más difícil.
Para atacar esto, usé un método bastante ingenuo:
- Agregue
<input type="hidden" name="secret" value=" al final de la página, luego agregue nuestras estimaciones anteriores (si las hay), luego agregue 0000 a ffff en secuencia y busque el resultado más pequeño cuando esté comprimido.
- Para la cadena hexadecimal de 4 caracteres que produjo el resultado más pequeño, agregue los primeros tres caracteres a nuestra estimación. Eliminar el último carácter es importante ya que hay bastante incertidumbre en el último carácter, y si lo hace mal, tiende a generar repetidamente el último carácter para todas las estimaciones restantes (por ejemplo,
7251 en el primero generaría 1111 en todas las suposiciones posteriores).
- Repita los pasos 1 y 2 hasta que queden < 4 caracteres para adivinar. Ejecute las restantes combinaciones posibles, en cada caso agregando
" /> a la cadena adjunta para completar la etiqueta.
Escribí una implementación completa con paralelismo en C #, que puede encontrar aquí .
Aquí están los resultados para 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!
Esto tardó solo un par de minutos en ejecutarse y descubre correctamente el secreto.
Ahora intentemos nuevamente con Brotli, usando el modo de compresión "más rápido", con la misma configuración para el ataque:
................................
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!
No tan bien. La segunda conjetura sale mal y esto arroja todo el algoritmo. Quizás debamos ser un poco más cautelosos y solo aceptar 2/4 caracteres por bloque en lugar de 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!
¡Y allí podemos ver que funciona de nuevo! Así que resulta que no es imposible atacar a Brotli de esta manera.
La parte clave que explica por qué falló su ataque es el diccionario predefinido:
A diferencia de la mayoría de los algoritmos de compresión de propósito general, Brotli utiliza un diccionario predefinido de 120 kilobytes, además del diccionario que se rellena dinámicamente ("ventana deslizante"). El diccionario predefinido contiene más de 13000 palabras comunes, frases y otras subcadenas derivadas de un gran cuerpo de texto y documentos HTML
(de Brotli - Wikipedia )
Entonces, ¿aparecen "verdad" y "falso" en este diccionario? ¡Sí! Encontré una copia textual del diccionario aquí y puede encontrar verdadero y falso en las líneas 6829 y 1204 respectivamente.
La razón por la que mi ataque funciona y el tuyo no es porque estoy buscando algo que no está en el diccionario. Para un solo token como "verdadero" o "falso", usar el índice del diccionario es mucho más eficiente que tratar de plegar los caracteres con otra instancia en el flujo mediante la codificación a distancia.
Pero, ¿por qué me resultó más difícil realizar un ataque de oráculo de compresión con éxito utilizando Brotli que con GZip? No parece haber muchas cadenas hexadecimales en el diccionario. Creo que esto es simplemente porque el sistema de compresión Brotli es más complejo que GZip. GZip usa una combinación de codificación LZ77 y Huffman, que tiene un fuerte enfoque en la eliminación de duplicados, lo que funciona muy bien para un ataque oráculo de compresión. Brotli, por otro lado, tiene más trucos bajo la manga, lo que lleva a una mayor probabilidad de que se utilicen otros mecanismos de compresión en lugar de la eliminación de duplicados durante los primeros bloques cuando el duplicado no es muy largo. Una forma de mejorar el ataque para Brotli sería forzar con fuerza bruta un conjunto más largo de valores en el primer bloque (por ejemplo, 6 o incluso 8 caracteres) para intentar obtener una eliminación por duplicado. Esto es mucho más lento, pero probablemente obligaría a un oráculo de compresión confiable fuera del compresor Brotli.