2007/08/07

¿Cómo analizamos un algoritmo con sólo el binario del programa?, ¿Cómo mejoramos un programa sin tener el código fuente?, ¿Cómo dividimos sin restar?, un usuario curioso siempre se siente atraído a develar los secretos tras el código y este documento es un buen punto de partida

La ingeniería inversa

El término ingeniería inversa tiene una multitud de posibles aplicaciones y es natural, como seres pensantes que somos, tener la capacidad para imaginar su significado y sus posibles alcances llanamente considerando sólo las derivaciones del término mismo.

Personalmente, me interesa de sobremanera el tema debido a los notables retos intelectuales que suele imponer la “inversión” de sistemas, procedimiento que logra fundir el trabajo en una especie de mezcla indistinta de lógica, conocimiento y esfuerzo, incluso formulando un desafío mayor, de forma posterior, que el obstáculo original que enfrentó el equipo de trabajo del proyecto en el cual nos focalizamos. Concretamente, el presente artículo intentará, al menos en su mayor parte, exponer el procedimiento de ingeniería inversa sobre un ejemplo pequeño, pero absolutamente real, para embeber al autor dentro de este extraordinario mundo.

El origen tras la ingeniería inversa

En el ambiente computacional es muy común contar con una especie de caja negra, en donde sabemos lo que ingresamos y el resultado que obtenemos pero desconocemos el procedimiento con la precisión que necesitaríamos para replicarlo.

Esta falta de documentación en los procesos es el impulso principal de toda la ingeniería inversa.

El secreto tras un programa

Muchas veces habrán visto que en este sitio utilizo implícitamente hipótesis sobre comportamientos, por ejemplo si queremos evitar un mensaje de error y no sabemos exactamente el lugar en donde trabajar del binario, simplemente buscamos en donde se carga el texto del mensaje.

Esto no es coincidencia y esa forma de abarcar los problemas tiene directa relación con el conocido método científico.

Imaginemos ahora que contamos con una aplicación que nos entrega un valor diferente para cada entrada realizada. Sin mucha dificultad podemos hacernos la idea de algo similar a la siguiente ilustración:

Ahora, esta aplicación lo único que hace es desplegar un mensaje de la siguiente forma:

¿Cómo descubrir el algoritmo tras esos resultados?

Es substancial tratar de lograr un pensamiento inductivo en donde logremos identificar el principio particular del problema, para poder llegar a extrapolarlo a una solución general.

Datos de prueba
Ingreso “0”, salida “30”
Ingreso “1”, salida “46”
Ingreso “2”, salida “65”
Ingreso “3”, salida “90”
Ingreso “4”, salida “120”
Ingreso “5”, salida “156”
…

Ya al haber observado la aplicación podríamos decidir procesar los datos que nos entrega y lograr crear un código equivalente o investigar el funcionamiento interno. Generalmente la primera forma de investigación nos servirá para abarcar problemas sencillos, no obstante nuestro objetivo siempre será estar capacitados para enfrentar el mayor desafío posible por lo que nuestro camino continuará con la investigación interna.

Paso a paso

Primero, buscamos el segmento de código involucrado en desplegar ese mensaje. Ya de forma casi mecánica simplemente buscamos una llamada a MessageBox o MessageBoxEx de la librería de sistema user32.dll.

Cualquier programador intuiría fácilmente lo que hacen las líneas superiores de esta aplicación, en especial que sprintf es parte de la librería estándar de C++. Claramente vemos también el título de la ventana en el código, estos valores son interpretados de forma inteligente por este descompilador (OllyDbg), lo que nos asiste de sobremanera a comprender el código.

Teniendo en cuenta las consideraciones anteriores la verdad es que por lógica podemos entrever que nuestra sencilla investigación ya nos dio indicios suficientes para bosquejar los pasos de la rutina, la cual comienza un poco más arriba:

Cabe destacar que se omitirán pasos intermedios de asignaciones de memoria y otros formalismos propios de ensamblador para favorecer el entendimiento del lector.

Inicialmente tenemos el valor de entrada supuestamente ya leído desde el cuadro de diálogo del programa, ahora nos enfocamos en la primera acción importante. Asumiremos el valor de entrada como una incógnita. En el siguiente trozo de código destacado, se añadió siete a la incógnita:

Es decir, por el momento tenemos una fórmula bastante sencilla que luce así:

A continuación, se multiplica ese valor resultante de la suma, por el mismo:

Nuevamente multiplicamos el resultado por el anterior, proporcionado tras la suma. En esta segunda vez ya podemos expresar la operación simplemente elevando al cubo la suma anterior:

Ahora le restamos diez al resultado:

El procedimiento que viene a continuación propone un mayor desafío intelectual y será abordado en el siguiente punto.

La genialidad que oculta ensamblador

Los siguientes pasos son un resumen de varias horas trabajando en el código y de comienzo puede parecer algo “místico” su funcionamiento.

La verdad es que luego de todos los pasos anteriores, un número constante es cargado al registro EAX:

Lo que hace el código es multiplicar el resultado de la salida temporal por aquel número:

La multiplicación por un número tan grande produce una especie de desbordamiento en el registro contenedor del resultado al exceder el tamaño de palabra del procesador (en este caso de 32 bits). Estos bits sobrantes, se almacenan en el registro contiguo EDX de una forma natural (los registros son contiguos en el procesador), dentro de los registros del procesador. Ahora, se desplaza un bit (se trunca el último bit) del registro EDX:

¿Qué sucedió tras aquella maraña de operaciones sin un sentido lógico aparente?

Les revelaré la respuesta dándoles la ecuación final:

Es cierto y aunque parezca increíble, lo único que se logró es dividir el resultado de las operaciones anteriores por once. Ahora se preguntarán ¿pero cómo?, en dos palabras: Números mágicos.

Números mágicos

Para dividir, lo que debemos hacer es restar cíclicamente hasta que lleguemos a cero o menos, por ejemplo para dividir 42 por 13, tendríamos que realizar la siguiente secuencia:

Así, obtenemos que la división de 42 por 13, es 3 con 3 de resto. Ahora, ¿Recuerdan el gran número que fue cargado al registro EAX?

Imaginen que tenemos un número cualquiera. En este caso usaré el número 7326, seleccionado de forma totalmente aleatoria, en decimales:

Lo multiplicamos por el número cargado en EAX, siguiendo el mismo procedimiento anterior, pero en decimales:

El resultado es bastante grande:

Expresamos el resultado en hexadecimal. Como en este caso trabajamos con un tamaño de palabra de 32 bits, tenemos que sólo 8 cifras del número en hexadecimal corresponden a esos 32 bits, FFFFFFFF en este caso sería la cifra máxima representada en hexadecimal con 32 ceros o unos, es decir, los restantes “quedarán” en el registro contiguo:

Ahora que tenemos el número que quedó en el registro de más adelante:

Siguiendo con el procedimiento, debemos truncar el último bit del resultado, primero convertimos la cifra a binario:

¿Qué obtenemos?, recordemos que al quitar el último bit lo que realmente hacemos es dividir por la base, análogamente a lo que representa añadir cifras al final, por ejemplo en decimales es simplemente multiplicar por diez, en este caso, en base dos, estamos dividiendo por dos:

Aún más evidente, en base diez:

No es que sea algo demoníaco. Es una mera coincidencia, aunque aún falta el último paso de esta pequeña demostración. ¿A cuánto corresponde el resultado, respecto del número inicial?:

Increíblemente, es la división por once del valor:

¿Sorprendente?, es increíble como una costosa operación, como lo es la división, puede ser reducida a estos niveles.

Los números mágicos son cifras especiales que permiten dividir valores de esta particular forma, hay tablas de estos números, para 32 y 64 bits y generalmente los compiladores los utilizan cuando detectan una división por una constante, de la que conozcan su número “mágico”.

Más recursos

Documento de texto completo en formato XPS (6.3 MB)

Documento de texto completo en formato XPS (2.5 MB, versión liviana)

Recursos utilizados en el documento, ejecutables, código fuente e imágenes (1.7 MB)

Conclusiones

Queda claro que el tema de la ingeniería inversa es uno de los tópicos más interesantes a los que podría afrontarse un profesional de la tecnología y en general, disfrutar el largo proceso involucrado gracias al desafío poco predecible que presenta.

Luego de meditar reiteradamente todo el presente tema aparecen controversias mayores que nos hacen pensar de si algún día será posible aplicar estas técnicas y descubrir el secreto del cerebro humano, los misteriosos efectos de la mecánica cuántica o incluso algo tan primordial como el origen de la vida.

Etiquetas: Cracking, Números mágicos