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
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.
Muchas gracias por la aportación, es muy interesante y de mucho aporte para los que iniciamos en este mundo del desarrollo. felicidades!
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.
Buen articulo.
Llege a esta Web por un enlace en Wikipedia y la verdad esta muy buena.
Muy buen material y contenido.
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’
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
Como ingeniero inverso, sinceramente admiro éste trabajo ;).
Es genial este articulo, creo que deberias explicar un poco mas cuando lees las estructuras que encuentras en el olly.
Saludos.
Es para dejar algo a la imaginación y la investigación 🙂
MMM… podría utilizarse también redes neuronales para realizar ingeniería inversa y predecir los números mágicos 🙂
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
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.
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.
Aplicación de la Ingeniería Inversa a la Calculadora HP-75C…
http://www.fortitudine.com/~coryc/html/hp75c.shtml
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…