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 década 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 preámbulos, 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 carácter tendrá un tratamiento diferente al final del ciclo) y consiste en lo siguiente: se calcula el XOR del carácter en la posición \(i\) con el carácter en la posición \(i-1\) y con término en la posición \(i\) de la secuencia de Fibonacci, esto es: \(c_i = c_i \oplus c_{i-1} \oplus F_i\).
Ciclo de descifrado
Al llegar al 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 función que descifra el primer carácter del bloque. Para esta función, "eax" apunta al buffer descifrado (y por tanto, al primer carácter), y también vemos que apila un 8 como segundo parámetro. Este proceso de descifrado para el primer carácter 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 algún 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 código:
for i in range(16):
    print "%d -> %d" % (i, sub_173C(i, 8))
Al evaluar la transformación que realiza esta función 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 atrás hacia adelante) y el nuevo valor binario resultante se lleva nuevamente a la base original. No lo hubiera entendido solo mirando el código :)
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 = 1, 1
    for i in range(n - 1):
        a, b = b, a + b
    return a


def decode_piece(data):
    data = bytearray(data)
    for i 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 máscara "& 0xff" en mi decode_sku(), sería mas eficiente tenerla directamente en la función fibonacci(), algo como: "a, b = b, (a + b) & 0xff", sin embargo, ya no sería correcto llamar "fibonacci" a la función resultante. Como nunca calculamos valores mayores que fibonacci(1024), no creo que haga falta… Por esta misma razón tampoco incluí el decorador de memoización que se suele usar en este tipo de funciones.
A decir verdad, es mucho mas eficiente usar algo mas cercano a la versión desensamblada (actualizando los términos de la serie al mismo tiempo que se va descifrando cada carácter), 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 = 1, 1, 1
            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 función 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? Después de identificar que este proceso usa dos secuencias numéricas bien conocidas, la respuesta bien puede ser: "porque aunque innecesaria esta rutina no deja de ser bonita" :)

Comentarios

Publicar un comentario