Erwin.Ried.cl / Documentos / Cracking /
Ingeniería inversa y los números mágicos

¿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 (22/08/2007 10:51 PM)


1. 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.


2. 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.


3. 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.



4. 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.


5. 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.


6. 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".


7. 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)



8. 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.

Haga clic sobre una de las estrellas para calificar este artículo.

Opiniones y comentarios (Escribir un nuevo comentario)
Muchas gracias por la aportación, es muy interesante y de mucho aporte para los que iniciamos en este mundo del desarrollo. felicidades!
Escrito por Horacio (12/10/2010 12:22 PM)
Muy interesantes comentarios, me sentí muy identificado con los contenidos ya que desde hace algunos años intento predecir los números de los próximos sorteos de melate, chispazo (con 2 primeros lugares) y ultimamente sorteo tris, utilizando metodologías basadas en fenómenos de sincronicidad y coincidencias significativas con aplicación de ingeniería inversa.
Escrito por Carlos Ruíz (23/09/2010 06:09 PM)
Buen articulo. Llege a esta Web por un enlace en Wikipedia y la verdad esta muy buena. Muy buen material y contenido.
Escrito por SpeeDinG (01/08/2010 03:07 PM)
Muy bueno tu artículo Erwin. Siempre he sido un admirador del assembler y la ingeniería reversa. Un caso espectacular es cómo la empresa AMD logró crear su propio CPU analizando un chip de Intel que por aquellos años era un monopolio. "Simplemente", tomó uno de ellos lo rebanó en pequeñas lonjas y analizó cada una de las capas de silicio para ver qué es lo que podría hacer cada una de ellas, y ya sabemos lo grande y fuerte competidora que es para Intel la empresa AMD. ¡Admirable'
Escrito por Jorg Spicel (04/10/2009 12:24 PM)
Muy cierto, lo curioso es que el producto nunca infringía patentes ni licencias de Intel pues lo que hizo AMD fue sólo aprender el funcionamiento del procesador. Lamentablemente por temas de calor y batería tengo que preferir productos de Intel para aparatos móviles, pero para mi computador de escritorio AMD siempre está presente
Escrito por Erwin Ried (05/10/2009 03:09 PM)
Como ingeniero inverso, sinceramente admiro éste trabajo ;).
Escrito por Shaddy (19/11/2008 04:00 AM)
Es genial este articulo, creo que deberias explicar un poco mas cuando lees las estructuras que encuentras en el olly. Saludos.
Escrito por jackl007 (04/01/2008 06:54 PM)
Es para dejar algo a la imaginación y la investigación :-)
Escrito por Erwin Ried (04/01/2008 09:24 PM)
MMM... podría utilizarse también redes neuronales para realizar ingeniería inversa y predecir los números mágicos :)
Escrito por Jesus Concha (17/12/2007 02:44 AM)
Pablo Elcholo te comento que en la serie Animatrix (de los creadores de Matrix) en concreto en los capitulos de El Segundo Renacimiento ya se ve ese futuro que anbunciaba Isamov, veanse los capitulos son muy ilustrativos. Gonzalo - http://internetizado.blogspot.com
Escrito por Gonzalo (23/09/2007 02:17 AM)
muy buen articulo Esto me viene a la mente un articulo de Isaac Asimov Hasta que punto el cerebro humano mantendra la hegemoneidad de su poder??? sera hasta que nosotros mismos contruyamos un computador capaz de construir uno mas complejo que el anterior y asi sucesivamante hasta que replique la complejidad del cerebro humano y asi tendremos que hacernos aun lado humildemente y dejar las cosas a alguien que sepa llevarlas mejor. Y si no vendra el supercomputador y nos hara a un lado de a malas.
Escrito por Pablo Elcholo (18/08/2007 10:46 PM)
http://www.fortitudine.com/~coryc/html/hp75c.shtml http://www.pmonta.com/calculators/hp-35/ Par de ejemplos de aplicación de la ingeniería inversa en calculadoras HP... Muy buen artículo Erwin... La ingeniería inversa tiene mucho futuro y es cada día más necesaria.
Escrito por s3basmagr1 (16/08/2007 09:47 PM)
Aplicación de la Ingeniería Inversa a la Calculadora HP-75C... http://www.fortitudine.com/~coryc/html/hp75c.shtml
Escrito por sebasmagri (13/08/2007 11:04 PM)
Realmente los usos de la ingeniería inversa pueden afectar todos los aspectos de nuestras vidas... que herramienta tan poderosa para labores de inteligencia por ejemplo. La mente humana no tiene límites y creo que la ciencia en este siglo seguirá buscando nuevas aplicaciones para esta disciplina...
Escrito por sebasmagri (12/08/2007 10:09 PM)

Copyright © 2013 por Erwin Ried.