Ikasten.IO
Learning, Aprendiendo

HackIt! 2013. Level 8. RPN (y II) 1 septiembre, 2013

Warning: si no has intentando entender el intérprete RPN antes, ni te molestes en leer este post, porque te sonará a chino. Lo dejo explicado aquí para aquellos que se hayan pegado con este reto y no hayan obtenido la solución o estén totalmente atascados. Al resto de los mortales les puede explotar la cabeza (brainfuck!) si intentan comprender una mínima parte de todo lo que diga a continuación 🙂 Avisados quedáis.

Vamos a por ello, por partes. Para entender la primera sección del programa, le pondremos puntos de ruptura (bp=break point) allá donde creamos conveniente y ejecutaremos con:

Ahora veremos que si ejecutamos ésto:

El programa se para al llegar a la instrucción bp, mostrándonos el contenido de la pila.

Los 97 del principio son el código ASCII de la letra “a”. Suelo repetir esa letra en este tipo de pruebas en el que quiero ver cómo “evoluciona” el código con la entrada que le paso. Luego viene un 0, que corresponde al comando: 0Oo.oO0_ del churro de código que nos pasan. Es decir, parece que el intérprete, cuando ve una ristra de números y letras, sin espacios, interpreta los primeros dígitos como un número, hasta encontrarse con el primer carácter no numérico. En este caso, 0Oo.oO0_ = 0.
El 105, 114, 93…83 es el código ASCII del literal: _ir]2;l[l6UmIvz3]S (sin contar el _ que marca comienzo de literal).

El 0ask, se convertirá en un 0 en la pila. Lo podremos ver pulsando INTRO (ejecutar paso a paso). La siguiente instrucción, ¿?, parece que hace un simple pop (aunque luego veremos que no, que lo que hace es traer de memoria lo último que hayamos memorizado con el comando .¿? . Parece que si no hubiéramos memorizado nada es cuando hace un simple pop…luego lo veremos mejor). -1neg, empila un -1. Y llegamos a la definición de bucle, que comienza por [ y termina con ]
Las instrucciones del bucle se ejecutarán en cada ciclo, hasta que se cumpla la condición de salida. ¿Cuál es dicha condición? Si al llegar al cierre del bucle “]”, la cima de la pila tiene un 0, saldremos, si no, seguiremos ciclando.

Así que empezamos con un -1 en la pila y nos metemos en el bucle: [ 1 + @@ @ .]
Lo que hace es empilar el 1, y luego sumar (-1 + 1 = 0). A continuación, @@ duplica la cima (tendremos 0 0) Luego llega una instrucción que nos trajo de cabeza hasta que conseguimos entenderla: @. Esta instrucción hace algo como lo siguiente:

Así que en la primera vuelta, hacemos un push(pila[0]). Como en la posición 0 de la pila tenemos nuestra primera letra del posible pass, estamos haciendo push(97).

Como 97 != 0, seguimos ciclando (.] cicla haciendo antes pop). En la siguiente vuelta tenemos 0 + 1 = 1. Duplicamos el 1 con @@ (1 1) y la sentencia @ empila el segundo carácter del pass (push(pila[1])). Seguiremos haciendo ésto hasta recorrer todos los caracteres del posible password. El siguiente carácter es un 0 (el que venía de 0Oo.oO0_). Es decir, al abandonar el bucle tendremos en la cima de la pila la longitud del posible pass (tras las pruebas supimos que era 17 la longitud de dicho pass). Lo duplicamos con @@ (17 17) y luego llega el comando }:-( que desempila y guarda en memoria ese valor (17) . A continuación 17k = empilar un 17 (17 17). “+” sumar los dos valores de la cima de la pila. nos quedamos con 34. Luego, el autor del level nos volvió locos con esto: [ @@ @ ¿? + 2 / .¿? 1 – @@ @ .]
Realmente lo que está haciendo (con ese @) es capturar la posición 34 (que quedaba tras la suma de 17 y 17) y traerlo a la pila. ¿Qué hay en esa posición? Es el último carácter del literal que empilamos al principio: _ir]2;l[l6UmIvz3]S , es decir, la S (ASCII:83). Lo suma con lo que hubiera en memoria (el famoso comando ¿? Inicialmente parece que tenemos un 0 -> 83 + 0 = 83. A continuación lo divide entre 2 y lo memoriza con el comando .¿?, sacándolo de la pila (tenemos en memoria un 41.5. En la cima de la pila un 34). Restamos 1 (tenemos 33) y volvemos a repetir el proceso: push(pila[offset]) (con offset = 33 obtenemos el carácter “]” (ASCII:93) (del literal _ir]2;l[l6UmIvz3]S). Le sumamos el contenido de la memoria (el 41.5), dividimos entre 2 y guardamos el resultado, memorizándolo (67.25) y sacándolo de la pila. Seguimos así hasta la condición de salida (hasta alcanzar el 0 de 0Oo.oO0_ .

¿Qué tiene que dar? Pues si la longitud del posible pass es 17, al haberlo duplicado tenemos un 34 (lo que nos permite recorrer el literal _ir]2;l[l6UmIvz3]S hacia atrás, operando como he explicado y dando como resultado el valor 100.6990432739. Lo tendremos en memoria y lo recuperaremos con “¿?”. Luego el código empila “_d” (un 100 en ASCII), al que le suma “0.6990432739” (tenemos 100.6990432739) y resta ambos valores. Lo dicho, si la longitud del pass era 17, ahora estaremos restando 100.6990432739 – 100.6990432739 lo que dará 0. Si así fuera, saltaremos a la etiqueta “>”. Esto fue otro quebradero de cabeza. Las sentencias “=>XXXX” son JUMPS condicionales. Si el valor de la cima de la pila es 0, salta a XXXX. Si no, sigue el flujo en la siguiente instrucción. En nuestro caso es 0, por lo que saltaremos (salto =>> a la etiqueta :> ) Una etiqueta comienza con “:”, de ahí que saltemos a :>. De aquí, :> , empilamos 17, restamos a la cima – (nos quedamos con 0) y saltamos a “=>>>” (es decir, a :>>)

Aquí no me extenderé más, pero éste trozo de código:

Realmente es el quid de la cuestión. Analiza cada carácter del posible pass y le aplica esta fórmula:

Donde X es la letra del pass que estamos analizando cada vez (offset es la distancia hasta esa letra. offset 0 para la primera, offset 1 para la segunda, etc.). Cada letra X del pass, tras pasar por esa fórmula, tiene que dar los valores:

105, 114, 93, 50…. 83, es decir, los valores ASCII del famoso literal del principio
(ir]2;l[l6UmIvz3]S)

Basta con resolver esa ecuación para cada X y fin de la prueba… bueno, casí, porque por ejemplo, para la primera letra del pass, abs[sin(x) ….] = 105 no tiene una única solución. De hecho, hay 3 posibles soluciones. Lo mismo ocurre para otras cuantas letras (fijaros en la foto que publiqué de la primera parte de la solución de este nivel). Lo que nos dejó probando varias soluciones hasta alcanzar la buena. Cuando la lees te das cuenta de que tiene sentido al leerla en hAx0r, pero … no fuimos los únicos, @navarparty también se divirtió probando un rato 🙂

Aunque parezca mentira, nos gustó este puzle mental 🙂 pero metimos horas por un tubo para resolverlo. Algún año estaría bien que los autores de los retos del año anterior nos contaran cómo demonios se les ocurrió, así como el proceso de creación que llevaron a cabo hasta obtener este tipo de levels de artesanía pura.

  • thEpOpE dice:

    Los niveles sería una buena cosa poder tener una mesa redonda al año siguiente para poderlos comentar, sobre todo porque imaginamos un modo de ataque, pero después cada grupo los enfoca de formas muy distintas.

    Siempre he querido hacer niveles con “cosas” que me he encontrado en la realidad, y un nivel basado en RPN me vino a la inspiración después de haber analizado una calculadora programada en .net para WinCE, cuyo algoritmo de protección era sencillamente la evaluación de una expresión RPN. Además he querido siempre en los niveles que he programado, que todos los miembros del grupo puedan “aprender” algo más… En el de #7, el de Basic de Spectrum, que no por ser basic un lenguaje interpretado y viejo, deja de tener opciones de protección interesantes. ¿Y si trasladamos esto a python? :p

    Respecto a este nivel de RPN, todo surge como un evaluador sencillo de RPN; hasta que voy pensando en utilizarlo para calculos más complejos (pila en coma flotante, uso de variables, gestión de la pila, saltos condicionales, y bucles). Y voilá… resultó este engendro. Con el tiempo añadí varias cositas que ayudan a la ofuscación, como es el intérprete de los números… deja de evaluar el número en el momento en que encuentra algo que no es un dígito válido, pero el número se usa. Una cosa que salió casi por casualidad es el poder usar etiquetas y nombres de variables extraños, lo cual era muy simpático para el resultado final. Una variable llamada “¿?” mola 😉 y una etiqueta :o) ni qué decir (¡!).

    Originalmente era una prueba de windows. Pero el lenguaje que usé para programarlo me permitía, sin modificar una sola línea, compilarlo para linux, para MacOS, y para Amiga…. y pensé en hacerlo en MacOS y consola (lo tuve que hacer en un virtual box, y chequearlo unos días antes en un MacOS real). Para que el foco de la protección se centrara en entender el RPN, añadí un modo debug en la linea de comandos, y lo mismo el poder ejecutar sentencias, sin necesidad de pasarlas por archivos externos.

    Lo que no he entendido es cómo llegásteis a saber que se podían poner “bp”. Es algo que introduje al programar el debugger en linea de comandos.

    A marcan le comenté que tenía un txt que había ido haciendo a medida que iba programando el RPN, y que estaría bien dárselo a la gente al terminar la hackit. A quienes estáis en la lista de correo os lo hice llegar. Creo que este año mi objetivo en los dos niveles se alcanzó: “el hecho de tener el código fuente no hace más fáciles las cosas”. Creo que esto ha sido la tónica general en casi todos los niveles este año. De hecho en el último, marcan se superó 😉

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *