[Actualizado] Determinar que tipo de compresión utiliza un programa

[GonzaFz]

EDIT2: El algoritmo resulto ser LZO.
Cualquiera que necesite informacion sobre su funcionamiento hay algo aca:
https://www.kernel.org/doc/Documentation/lzo.txt

Lastimosamente sin ingenieria inversa no se puede obtener informacion de como funciona, en ningun lado hay una especificacion oficial.


Buenas, estoy en el proceso de hacer ingenieria inversa al protocolo de red de un mmorpg.

Algunos paquetes que suelen ser muy largos se comprimen con un algoritmo que estuve analizando pero no puedo determinar cual es (el cliente solo los descomprime, nunca comprime un paquete para enviarlo, por lo tanto no tengo acceso al proceso de compresion)
Todavia sigo creyendo que es una variante del LZ77 pero no logro dar con cual, lei el funcionamiento de varias pero no encuentro un parecido a ninguna (y tampoco creo que sea viable ponerme a probar todas porque seria dificil dar con el resultado exacto).

Tambien utilice extensiones del ida pro pero no tuve buenos resultados. Se menciona Deflate y unlzx pero ninguna de las referencias es utilizada dentro del proceso de descompresión.

Voy a intentar explicar lo mas claro posible como funciona el proceso, a ver si alguno me puede dar una mano. Se que seria facil simplemente reconstruirlo tal cual me muestra el hex rays y listo, pero mas me mata la curiosidad de saber cual es y quisiera poder implementarlo al 100%


Detalles:
Por lo que pude observar del algoritmo siempre trabaja sobre el buffer de entrada y de salida. Nunca utiliza alguna tabla/string o lo que fuese externo a estos dos.
Utiliza punteros (tal como el lz77 y sus variantes) para indicar el desplazamiento hacia atrás desde la posición actual. La información que tienen los punteros esta definida a nivel de bits.
Siempre que descomprime lo hace en base a lo que fue escribiendo en el buffer de salida. Del de entrada solo va tomando los pares de bytes que representan los punteros.
Desde mi parecer la descompresión es obligatoriamente secuencial, no hay posibilidad de saber dinamicamente donde hay otro puntero, al menos sin haber analizado los punteros anteriores.
Al comienzo de la cadena comprimida siempre hay un par indicando que es lo que viene.
El factor de compresion, al menos para el unico paquete que analice (lo hice varias veces pero siempre trae la misma informacion) es de casi el 50%.

Algoritmo:
Voy a intentar explicarlo a grandes rasgos (es posible que me saltee algunas partes).
Si quieren ver el algoritmo en c sacado de hex rays lo pueden hacer aqui:
https://gist.github.com/FYGonzalo/a4118d35620d48bacea2253d5aa48e6d

Las variables las renombre yo, puede que alguna tenga un nombre que no la represente. Tambien hay algunos comentarios del codigo, igual no se si sera mas entendible leer mi "pseudocodigo" o el codigo directo del hex rays.

Mas abajo adjunto una parte del proceso de descompresión de un paquete.

Al comenzar analiza el primer byte (de ahora en mas firstByte) del buffer de entrada (de ahora en mas inputBuffer).
Si este es mayor a 0x11 (17): // Significa que hay bytes descomprimidos y se deben copiar tal como estan
   Le resta 0x11 (17) al firstByte y el resultado indica la cantidad de bytes por copiar.
   Avanza una posicion en el inputBuffer (la siguiente al firstByte) y copia lo que indica el resultado anterior.
   Dependiendo cuanto fue el resultado salta a un label donde sigue haciendo analisis del par de bytes.
Sino
LABEL 1
   Lee en una variable "secondByte" el segundo byte del inputBuffer
   Si el firstByte es menor a 0x10 (16)
       Si el firstByte es nulo
           Si el secondByte es nulo
               -----
           firstByte = secondByte + 15
       Copia una DWORD del inputBuffer al outputBuffer y avanza los punteros (de ambos buffer) 4 posiciones
       Asigna a un contador el valor de firstByte - 1
       En base al valor del contador itera copiando bytes del inputBuffer al outputBuffer (sin modificarlos)
       Vuelve a leer del inputBuffer otro par (firstByte & secondByte)
       Si el firstByte es menor a 0x10 (16)
           ------
   Mientras (1)
       Si firstByte es mayor a 0x40
           Obtiene un puntero al outputBuffer retrocediendo ((-((firstByte >> 2) & 7) - 1) - secondByte * 8) posiciones

Pausa. Aca se observa una de las situaciones en donde se opera el par en base al valor de sus bitss.
En un caso que detallo mas abajo, el par que se trabaja es (4C, 01)
El valor en bits de 4C es: 0100 1100
Aplicamos el shift de 2 posiciones: 0001 0011
Aplicamos el and 7: 0001 0011 & 0000 0111 = 0000 0011
Sumamos 1 (en realidad es resta, pero son ambos negativos asi que lo obviamos): 0000 0100.

La conclusion que saque de esta operacion (y de otras donde se repite) es que en el firstByte, cuando es mayor o igual a 0x40, hay 3 bitss que indican parte del desplazamiento.
En este caso seria: 0100 1100
Pero como luego se le suma 1 sabemos que el primer termino, de la operacion compleja indicada en la ultima linea de codigo mas arriba, dara como resultado un valor entre 1 y 8 (no mas ni menos).

Luego simplemente se suma (nuevamente, es una resta pero al ser todos negativos lo obviamos) el valor del secondByte (sin importar cual fuere) multiplicado por 8.
Es decir que al final vamos a retroceder en el outputBuffer la cantidad resultante de esta suma.

           Avanza el inputBuffer posicionandose en el byte siguiente al par que estamos analizando
           Determinamos la cantidad de bytes por copiar* aplicando ((firstByte >> 5) - 1)        

Nuevamente nos detenemos aqui.
Recordemos que el firstByte actualmente tiene el valor 4C que en binario es: 0100 1100.
Aplicamos el shift 5 posiciones a la derecha: 0000 0010
Le restamos 1: 0000 0010 - 0000 0001.

La conclusión de este segmento es que los 3 bitss de mayor peso del firstByte (siempre que este sea mayor a 0x40) indican una cantidad de bytes por copiar*.
*En realidad no indica la cantidad total de bytes por copiar. Obligatoriamente al llegar a este punto se copian al menos 2 bytes (lo veran en las siguientes lineas de codigo), pero indica la cantidad de bytes, luego de haber copiado 2 obligatorios, que se deben copiar.

           Copiamos dos bytes obligatorios del outputBuffer (basados en el puntero que obtuvimos anteriormente hace 4 lineas de codigo)
           Luego copiamos tantos bytes del outputBuffer como indique la operacion anterior.
           Luego saltamos a otro label donde aplicamos una and entre el firstByte y 3. El resultado indica la cantidad de bytes (planos) del inputBuffer por copiar. En caso de que sea 0, volvemos al Label 1, sino continuamos en el while.

Nuevamente se opera a nivel de bits.
Al aplicar la operacion and entre el valor de firstByte y 3 (0000 0011) lo que hacemos es analizar los dos bits de menor peso del firstByte.
Es decir que ahora como conclusión entendemos que significa completamente el firstByte cuando es mayor o igual a 0x40:
0100 1100: Indican parte de la cantidad de bytes a copiar del "diccionario" (recordemos que se le resta 1) y obligatoriamente se copiaban 2
0100 1100: Indican parte del desplazamiento hacia atras en el outputBuffer donde se encuentra la cadena descomprimida (recordemos que se le suma 1 y luego 8 * secondByte)
0100 1100: Indican la cantidad de bytes planos del outputBuffer que debemos copiar luego de haber copiado los "descomprimidos".

       Si el firstByte es menor a 0x20 (32)
           Break (sale del while y creo que termina con algunas operaciones)
       (Si el firstByte es menor que 0x40 pero mayor o igual a 0x16 - Condicion no especificada pero se llega a este punto debido a esa situacion)

En este caso se da una situacion particular. Es como si se invirtieran la responsabilidad de los bytes del par y ahora el segundo byte (secondByte) indica los desplazamientos hacia atras en el outputBuffer y el firstByte los bytes por copiar.

           Se obtiene una "cantidadCopiar" haciendo firstByte & 0x1F

Aqui nuevamente se vuelve a trabajar a nivel de bitss.
Un caso que analice en el cual se entraba a este punto es con el par (2A, C8).
Como dijimos anteriormente cuando el firstByte es menor a 0x40 pero mayor o igual a 0x20 se invierten las responsabilidades.
Sabemos que 2A es: 0010 1010
Y 1F: 0001 1111

Asi que al aplicar la operacion and entre ambos lo que estamos haciendo es recuperar los 5 bitss de menor peso del firstByte.
El resultado sera 0000 1010

           Si cantidadCopiar es nula
               Si secondByte es cero
                   -----
               cantidadCopiar += secondByte + 31 (decimal)
           Obtenemos un puntero al outputBuffer con un retroceso desde la posicion actual determinado por ((secondByte >> 2) + 1)

Nuevamente se trabaja con bitss.
Recordemos, secondByte es C8: 1100 1000
Aplicamos el shift: 0011 0010 (50 decimal)
Restamos 1: 0011 0001 (49 decimal)

           Avanzamos el inputBuffer 2 posiciones (nos saltamos un byte despues del par que estamos analizando)
           --- Se aplica una operacion rara dada una condicion que nunca vi que fuese verdadera bajo el inputBuffer de prueba que estoy analizando ----
           Copiamos una DWORD de la posicion que indica el puntero que definimos unas lineas atras (del outputBuffer) y lo pegamos en la posicion actual del outputBuffer. Es decir, copiamos una DWORD "descifrada" del outputBuffer a la posicion actual del outputBuffer (basicamente buscamos en el diccionario la palabra y la pegamos)
           Avanzamos 4 posiciones (por el DWORD) en los punteros a ambos buffers.
           Disminuimos la cantidadCopiar en 2
           Hacemos un bucle copiando la cantidad de bytes que indique "cantidadCopiar"

           Nuevamente (como el caso de mayor o igual a 0x40): (Basicamente es un label que no lo puse como tal)
           Aplicamos un and entre el byte que indica el offset (ahora es el secondByte, en el caso anterior habia sido firstByte) y 3. El resultado indica la cantidad de bytes "planos" restantes por copiar del inputBuffer al outputBuffer.

Otra vez trabajamos a nivel de bits.
Al aplicar el and al secondByte (0xC8) lo que estamos haciendo es recuperar los 2 bitss de menor peso.

Recapitulando ahora conocemos toda la informacion que trae el secondByte:
0011 0010: Indican el desplazamiento hacia atras en el outputBuffer (recordemos que se le resta 1)
0011 0010 Indican la cantidad de bytes "planos" que deben copiarse del inputBuffer al outputBuffer, luego de haber copiado los del diccionario indicados por el puntero.

           En caso de que este resultado sea mayor que 0, copiamos los bytes que indican y seguimos dentro del while.
           En caso contrario (sea igual a 0), volvemos al LABEL 1.

Ya cuando se sale de todo este bucle (unicamente por el Break de que firstByte < 0x20) se hacen operaciones para finalizar, se copian los bytes restantes y algun que otro detalle.
Se devuelve la longitud del buffer de salida.

Descompresion de un paquete real:
Lo pueden ver aqui, hay imagenes y una explicacion del proceso hasta cierto punto (no lo cargo al post porque se haria mucho mas largo de lo que ya es).
http://imgur.com/a/kuQkl




Y eso es todo lo que pude obtener, la verdad es que hay algunos detalles mas del algoritmo pero no llegue a analizarlos porque mi principal objetivo es determinar que estandar de compresion (si es que es un estandar) es el utilizado.

Espero no haberlos aburrido, y que me puedan dar una mano, me costo mucho trabajo hacer la ingenieria inversa y luego un poco mas redactar todo el post y juntar las pruebas.

Saludos.

[MCKSys Argentina]

Hola!

Si estuviera en tu lugar probaría con zlib. Si no funciona, con un script de python para saber si no está usando gzip.

Si ninguno de los 2 parece reconocerlo, vas a tener que seguir reverseando hasta dar con el algoritmo (es muy raro que no usen un algoritmo de compresión standard).

Saludos!

[GonzaFz]

Mira, probe la compresion GZip de .Net y por lo que llegue a leer, a fondo es simplemente la misma que la de Deflate (implementada en .Net) pero con algunos agregados mas como checksum y otros detalles.

GZip me lanza un error de numeros magicos.
Deflate encuentra errores en el bloque.

Tambien probe una libreria de ZLib (DotNetZip) y tampoco me descomprime.

Intente hacerlo a la inversa, poniendo la cadena descomprimida y comprimiendo para analizar si arroja un resultado similar pero no, en todos estos casos en la cadena comprimida resultante no hay ninguna cadena literal (como si las hay en el algoritmo que estoy usando, si se ven las imagenes, en el paquete comprimido hay fechas, nombres, etc).


EDIT:
Como nadie me supo decir (tambien pregunte en otro foro pero no me respondieron) decidi implementarlo yo mismo.
Lastimosamente, ademas de que todavia el codigo no esta listo (me falta mucho pero esta encaminado), no se si voy a liberarlo o no asi que todavia no lo voy a compartir. Si algun dia lo libero voy a actualizar este tema y dejar el link para que puedan ver por si necesitan hacer algo similar.
(No lo libero por no perjudicar a los desarrolladores del juego, hacerlo daria facilidad a cualquier oportunista de aprovecharse de todo lo que logre hasta ahora, y mi objetivo no es perjudicar al juego).

De todas formas mi idea fue implementarlo al estilo como .net implementa DeflateStream y GZipStream, para que sea facil luego utilizarlo en cualquier situacion (ademas de elegante y aprender como los grandes escriben codigo).
En el repositorio de github de dotnet: https://github.com/dotnet/corefx/blob/master/src/System.IO.Compression/src/System/IO/Compression/DeflateZLib/DeflateStream.cs

Luego de ahi pueden ir sacando que otras clases se necesitan.

Pero yo no me base en eso, utilice otro similar, de una libreria opensource (SharpZipLib) que implementa de manera muy similar, aunque quizas mas simple.
https://github.com/icsharpcode/SharpZipLib/blob/master/ICSharpCode.SharpZipLib.Shared/Zip/Compression/Streams/InflaterInputStream.cs

Ese seria el stream para descomprimir, y luego en el mismo directorio esta el DeflaterInputStream que es el stream a comprimir. Lo mismo, de ahi van sacando las otras clases que necesitan.


Cualquier duda me consultan, creo que mi reproduccion del algoritmo de descompresion fue un exito, ahora me faltaria desarrollar el de compresion.

Saludos.