sábado, 20 de agosto de 2016

Qcrack y la belleza de lo innecesario

Esta es la segunda entrada en lo que espero sea una serie dedicada a reversar QCRACK.EXE, un keygen de 1996 destinado a desbloquear software protegido con TestDrive (esto incluye a Quake y a muchos otros juegos desarrollados por id Software en la decada de los noventa).  La primera entrada es: "Quake, TestDrive y Qcrack".

Descifrando SKU.17

En la entrada anterior comente que no necesitamos realmente descifrar el archivo "SKU.17" (porque podemos extraerlo directamente en texto plano de los archivos FLOWLIB.*) y que, de hecho, es el uso de este archivo el que causa del bug de QCRACK que lo hace generar seriales incorrectos para "Final Doom".  Sin embargo, aclarar que tan compleja es esta rutina podría ayudar a confirmar (o descartar) la idea que tengo de que este keygen pudo ser el resultado de un leak.

Sin mas preambulos, asi funciona el proceso de descifrado para el archivo "SKU.17": Se descifran bloques de hasta 1024 bytes.  El proceso se realiza para todos los caracteres desde el segundo en adelante (el primer caracter tendra un tratamiento diferente al final del ciclo) y consiste en lo siguiente:  se calcula el XOR del caracter en la posicion i con el caracter en la posición (i - 1) y con termino en la posición i de la secuencia de Fibonacci, esto es: ci ⊕ ci - 1 ⊕ Fi.

Ciclo de descifrado
Al llegar a el bloque mostrado en la imagen anterior, el registro "esi" apunta al buffer que contiene el bloque de datos a descifrar, y el registro "edi" almacena el numero de bytes a descifrar.  El ciclo de descifrado esta entre 0x2600 (bonito numero) y 0x262a.

En las tres primeras lineas vemos como se inicializan las variables [ebp - 0x1b4] y [ebp - 0x1b0] que llevaran la cuenta de los terminos Fibonacci, asi como el registro ebx que funcionara como indice para el ciclo.  En 0x260c y 0x2610 se ve el doble XOR (el primero es el XOR entre el caracter previo y el numero de Fibonacci). La actualizacion de los terminos Fibonacci esta entre 0x2614 y 0x2626. Finalmente, la llamada en 0x263b (call 0x3a5c) es un "call memcpy" que va uniendo los bloques descifrados.

En la ultima linea, la llamada en 0x265c (call 0x173c) es una llamada a la funcion que descifra el primer caracter del bloque.  Para esta funcion,  "eax" apunta al buffer descifrado (y por tanto, al primer caracter), y tambien vemos que apila un 8 como segundo parametro.  Este proceso de descifrado para el primer caracter utiliza una "bit-reversal permutation" de ocho bits.

Descifrado del primer caracter
Entender esta rutina no fue facil.  Reconstruirla es bastante simple, pero entender que estaba haciendo me tomo algun tiempo.  Aqui esta una reimplemntación mas o menos literal:


def sub_173C(arg1, arg2):
    result = 0
    while arg2:
        result = arg1 & 1 | 2 * result
        arg1 >>= 1
        arg2 -= 1
    return result

No entiendo :(

En este punto tuve que atacar los datos en lugar de atacar el codigo:

for i in range(16):
    print "%d -> %d" % (i, sub_173C(i, 8))

Al evaluar la transformacion que realiza esta funcion sobre unos pocos bytes se encuentra esto:

0 -> 0
1 -> 128
2 -> 64
3 -> 192
4 -> 32
5 -> 160
6 -> 96
7 -> 224
8 -> 16
9 -> 144
10 -> 80
11 -> 208
12 -> 48
13 -> 176
14 -> 112
15 -> 240

Una busqueda de la serie "0, 128, 64, 192, 32, 160, …" nos lleva a identificar la secuencia A160638: Bit-reversed 8-bit binary numbers  :)  El argumento 1 se lee como binario (usando el padding a ceros que sea necesario para completar 8 bits), este valor invierte (se lee de atras hacia adelante) y el nuevo valor binario resultante se lleva nuevamente a la base original.  No lo hubiera entendido solo mirando el codigo :)

A continuación, la versión completa de la rutina de descifrado (incluyendo una versión de la funcion anterior mucho mas al estilo de python):


def bit_reversal(n, k):  http://stackoverflow.com/q/12681945/
    return int('{:0{width}b}'.format(n, width=k)[::-1], 2)


def fibonacci(n):  
    a, b = 11
    for i in range(n - 1):
        a, b = b, a + b
    return a


def decode_piece(data):
    data = bytearray(data)
    for in range(1, len(data)):
        data[i] ^= data[i - 1] ^ (fibonacci(i + 1) & 0xff)
    data[0] = bit_reversal(data[0], 8)
    return data


def decode_sku(sku):
    data = ''
    with open(sku, 'rb') as f:
        while True:
            piece = f.read(1024)  # block-size must be 1024 bytes
            if not piece:
                break
            data += decode_piece(piece)
    return data


# demo
print decode_sku('/dosprogs/QCRACK/SKU.17')


En la función bit_reversal() decidí usar una implementación en la que el ancho puede pasarse como un parámetro, en lugar de usar alguna de las versiones mas eficientes (que solo funcionan para ocho bits), porque en otras partes de QCRACK se usa este mismo truco con un numero de bits diferente.

Adicionalmente, la mascara "& 0xff" en mi decode_sku(), sería mas eficiente tenerla directamente en la funcion fibonacci(), algo como: "a, b = b, (a + b) & 0xff", sin embargo, ya no seria correcto llamar "fibonacci" a la funcion resultante. Como nunca calcularemos valores mas grandes que fibonacci(1024), no creo que haga falta… Por esta misma razón tampoco incluí el decorador de memoización que suelo usar en este tipo de funciones.

A decir verdad, es mucho mas eficiente usar algo mas cercano a la versión desensamblada (actualizando los terminos de la serie al mismo tiempo que se va descifrando cada caracter), aunque de esta forma se pierde legibilidad:

def decode_sku(sku):
    decoded = ''
    with open(sku, 'rb'as f:
        while True:
            piece = bytearray(f.read(1024))
            if not piece:
                break
            i, j, k = 111
            while i < len(piece):
                piece[i] ^= piece[i - 1] ^ k
                i, j, k = i + 1, k, (k + j) & 0xff
            piece[0] = int('{:08b}'.format(piece[0])[::-1], 2)
            decoded += piece
    return decoded

Comentarios

Esta rutina no habla muy bien del componente criptografico de TestDrive (¿y recuerdan el ENCRYPT.EXE que vimos antes?).  De haber encontrado una funcion criptografica compleja, funcionaría como evidencia de un leak, ahora ya debo reconsiderar mi postura sobre ese aspecto de esta historia…

En la entrada anterior me preguntaba ¿Porque alguien incluiría esta rutina innecesaria? Despues de identificar que este proceso usa dos secuencias numericas bien conocidas, la respuesta bien puede ser: "porque aunque innecesaria esta rutina no deja de ser bonita" :)

No hay comentarios:

Publicar un comentario en la entrada