Ikasten.IO

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:

./RPN -fprograma.txt

Ahora veremos que si ejecutamos ésto:

"aaaaaaaaaaaaaaaaa" 0Oo.oO0_ _ir]2;l[l6UmIvz3]S
bp 0ask ¿? -1neg [ 1 + @@ @ .] @@ 
}:-( 17k + [ @@ @ ¿? + 2 / .¿? 1 - @@ @ .]
¿? _d 0.6990432739 + - =>> 1zero 0one =>o) 

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

$ ./RPN -fretocado.txt 
Bpoint alcanzado
stack:97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 97.0000000000 0.0000000000 105.0000000000 114.0000000000 93.0000000000 50.0000000000 59.0000000000 108.0000000000 91.0000000000 108.0000000000 54.0000000000 85.0000000000 109.0000000000 73.0000000000 118.0000000000 122.0000000000 51.0000000000 93.0000000000 83.0000000000 | 
37: 0ask |

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:

offset = pop();
push(pila[offset])

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:

:>>
0 .;) [ ;) @ sin 10 ;) 7con + ** @@ 1ocho % - @@ +>gen neg :gen 79O % 48$ + ;) }:-( 1Oo. ++ @ -

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

abs[sin(x) * 10 * (offset + 7)] % 79 + 48

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.

Real Pesky Numbers (RPN), así se subtitula el reto 8. La noche del sábado conseguimos terminar esta prueba – la imagen de la izquierda, con parte de la solución, es una foto realizada ese mismo día  – tras varias horas intentando descifrar cómo demonios funcionaba la aplicación que escondía el mensaje…. o más bien, cómo funcionaba el intérprete RPN proporcionado ante este galimatías de código que lo acompaña:

"your password here" 0Oo.oO0_ _ir]2;l[l6UmIvz3]S
0ask ¿? -1neg [ 1 + @@ @ .] @@ 
}:-( 17k + [ @@ @ ¿? + 2 / .¿? 1 - @@ @ .]
¿? _d 0.6990432739 + - =>> 1zero 0one =>o) 
:> 17 - =>>>
1the 0p0pE 0g0ne 12crAzy
9 _fmnqV [ @@ =><= 1 + # 
:<= ] =>o) 
:>>
0 .;) [ ;) @ sin 10 ;) 7con + ** @@ 1ocho % - @@ +>gen neg 
:gen 79O % 48$ + ;) }:-( 1Oo. ++ @ - =>asin
1one 0zero @@ 14five 11two _ebC [ @@ =><) 1infinity - # 
:<) ] =>o) 
:asin ;) 1zero + .;) ;) 17l - .]
0zero @@ 15RPN 12skill _vjikT [ @@ =>oP 2NaN - # 
:oP ]
:o)

El intérprete en cuestión estaba alojado en una aplicación para MacOSX (archivo .dmg). Suerte que este año llevamos uno 😉 Para el lector que no disponga del sistema de la manzana, el autor del reto ( thEpOpE , gracias!) nos ha proporcionado el mismo intérprete RPN compilado para Linux. ¿Te atreves a deshacer el ovillo del código anterior?

Analicemos el código. La línea 15 define la función módulo (no existente en el Basic del Spectrum). La línea 20 declara e inicializa ciertas variables que luego veremos. La línea 30 pide al usuario un password (Code). La línea 40 comprueba que la longitud del pass introducido sea al menos igual a 6 (las letras de «HackIt»). Si fuera menor, concatena el pass hasta que se cumpla la condición. En la línea 50 comienza la chicha. Iteraremos 6 veces. En cada iteración, la línea 55 del programa cambiará el contenido de la línea 60, sobre-escribiendo en memoria 3 posiciones (como si fuera el código de un virus polimórfico). ¿Cómo sabemos qué es lo que escriben esos POKE y dónde? Poniendo un STOP justo al comienzo de la línea 70 (ver figura de la izquierda).

10 REM PoliMorph
15 DEF FN m(a,b) = a- (INT (a/b)*b) : REM a Mod b
20 LET pos1=00053: LET pos2=00069: LET pos3=24000: LET x1=181: LET x2=42: LET x3=45
30 LET n$="HackIt": INPUT "Code:";c$: LET x$=""
40 IF LEN c$< LEN n$ THEN LET c$=c$+c$: GOTO 40 
50 FOR g=1 TO LEN n$ 
55 POKE pos1,x1: POKE pos2,x2: POKE pos3,x3 
60 LET cod = INT (98*ATN (g/ LEN n$)) + CODE c$(g)/0 + g 
70 LET x1=x1+1: IF x1>183 THEN LET x1=181
80 LET x2=x2+1: IF x2>47 THEN LET x2=42
90 LET x3=x3+2: IF x3>45 THEN LET x3=43
110 LET x$=x$ + CHR$ (32 + FN m(cod, 95))
120 NEXT g: PRINT "Decoded:";x$
130 IF n$ <> x$ THEN PRINT "Wrooonnggg!": FOR g=pos1-11 TO pos3+2: POKE g,48+ INT (RND*10): NEXT g: STOP
140 PRINT "Right!, here goes the rest..."

Vemos que tras la ejecución, la línea 60 ha cambiado:

Antes:
60 LET cod = INT (98*ATN (g/ LEN n$)) + CODE c$(g)/0 + g
Ahora, tras los POKE(pos_memoria, valor):
60 LET cod = INT (98*ASN (g/ LEN n$)) + CODE c$(g)*0 - g

¿Por qué? Las posiciones de memoria las calculó pacientemente el autor de la prueba (thEpOpE). ¿Y el valor? Podemos ayudarnos de esta tabla de mnemónicos. Por ejemplo, el primer POKE(00053, 181) cambia la posición 00053 (donde teníamos un ATN -arcotangente-) por el operador ASN -arcoseno-, dado que al código 181 le corresponde el operador ASN según la tabla indicada. La división por 0 (ilegal), ha cambiado a multiplicación por 0 (legal) con POKE(00069, 42). El «+ g» ha cambiado a «- g» con el POKE(24000, 45). El 45 corresponde al operador «-«. Lo que no tengo claro es cómo demonios la dirección 24000 corresponde a esa sección del código (seguro que thEpOpE nos ilumina en los comentarios 🙂

Los valores 181, 42 y 45 corresponden a las variables x1, x2 y x3 definidas en la línea 20. En cada vuelta del bucle, x1, x2 y x3 cambiarán, por lo que los POKE modificarán la línea 60 en cada vuelta. La tabla enlazada nos ayudará a conocer qué hace en cada vuelta. Esa línea 60 va modificando cada letra de nuestro password (dejándola en la variable cod). En la línea 110 se calcula el carácter asociado al código ASCII de 32 + cod módulo 95. Esto nos dará un carácter imprimible entre ASCII(32) y ASCII (32+94). Ese carácter, en cada vuelta, debe coincidir con las letras del string «HackIt». ¡Un level muy trabajado!.

Algunos comentarios finales. Me ha gustado el efecto de bombardear la memoria y cambiar el código en caso de introducir un pass incorrecto (línea 130). También nos dejó ojipláticos al comienzo la división por cero de la línea 60. Cuando vimos los POKE de la 55 supusimos que corregiría ese bug intencionado. También nos costó encontrar un emulador que cargara el código en BASIC. No sé si fue un efecto buscado o no…

Finalmente, el level tenía un bug no intencionado. La clave final aparece en los strings del binario… nos dimos cuenta tras pasar horas y horas con la prueba, encontrar la solución de forma ortodoxa y recordar que ese string lo habíamos visto antes en algún sitio O:-)

Y con esto, llegamos al level 8, donde nos espera un interesante intérprete RPN del mismo autor…

LOAD «» . Ése es el mantra que recuerdo haber repetido cientos de veces en 1986. El nivel 7 del HackIt! de este año me hizo recordar algunos comandos más… pero para comenzar a recordar, lo primero que hay que hacer es instalar un emulador del viejo Spectrum en nuestros flamantes portátiles. Fuse-SDL es uno de ellos, disponible desde apt-get en Ubuntu. Desde aquí, pulsando F1 accederemos a un menú desde el que poder cargar el fichero que nos pasan: image.dsk. Elegimos a continuación la opción +3 BASIC.

Para ver el contenido del disco, tecleamos:

cat

En este caso, únicamente veremos un fichero de nombre HACKME.BAS. Por cierto, lo del disco fue una innovación que trajo tío Sinclair con la versión +3. Yo no llegué a disfrutarla, pasé directamente del casete a discos de 5-1/4. ¡Menudo adelanto! 🙂  En fin… batallitas.

Ahora hay varias vías. La primera que probamos es a cargar el código con:

LOAD "HACKME.BAS"

Esto cargará en memoria y ejecutará el programa en Basic HACKME.BAS. Es importante el último punto: ejecutará directamente, antes de mostrarnos el código fuente. La ejecución nos pide que introduzcamos un código (vamos a llamarle «password»). Internamente el programa hace algunas operaciones y nos devuelve otro string calculado a partir de nuestro password (¿cómo lo ha calculado? ése es el quid de la cuestión), junto a un mensaje del estilo «Wrooong!».

Pulsando ENTER tras el mensaje «Wrooong!» pasamos a ver el código fuente… y aquí empieza la diversión. El programa lleva por título «PoliMorph» y vemos, entre otras cosas, que en caso de introducir un password incorrecto, ejecuta la instrucción POKE (escritura en memoria) justo apuntando al propio código en BASIC, sobreescribiendo con números al azar multitud de posiciones (lo que provoca que perdamos el código original). Lo de Polimorph no era broma…

Así que un primer paso es obtener el código de HACKME.BAS _antes_de su ejecución. Bien, esto fue fácil, basta con usar el comando MERGE «HACKME.BAS» (en lugar de LOAD). El comando MERGE carga el código en memoria pero no lo autoejecuta. Y aquí aparece esta pequeña obra de arte, con más comandos POKE haciendo de las suyas.  El lector más despierto seguro que verá algo muy extraño en la línea 60 (¿una división por 0?):

10 REM PoliMorph
15 DEF FN m(a,b) = a- (INT (a/b)*b) : REM a Mod b
20 LET pos1=00053: LET pos2=00069: LET pos3=24000: LET x1=181: LET x2=42: LET x3=45
30 LET n$="HackIt": INPUT "Code:";c$: LET x$=""
40 IF LEN c$ < LEN n$ THEN LET c$=c$+c$: GOTO 40  
50 FOR g=1 TO LEN n$ 55 POKE pos1,x1: POKE pos2,x2: POKE pos3,x3  
60 LET cod = INT (98*ATN (g/ LEN n$) + CODE c$(g)/0 + g  
70 LET x1=x1+1: IF x1>183 THEN LET x1=181
80 LET x2=x2+1: IF x2>47 THEN LET x2=42
90 LET x3=x3+2: IF x3>45 THEN LET x3=43
110 LET x$=x$ + CHR$ (32 + FN m(cod, 95))
120 NEXT g: PRINT "Decoded:";x$
130 IF n$ <> x$ THEN PRINT "Wrooonnggg!": FOR g=pos1-11 TO pos3+2: POKE g,48+ INT (RND*10): NEXT g: STOP
140 PRINT "Right!, here goes the rest..."

El código es bastante legible… salvo la línea 55 y esa división por 0 en la 60… ¿Te animas a descifrar cuál es el funcionamiento exacto?

Otro detalle más: probamos con otros emuladores de Spectrum con soporte para archivos .DSK sin éxito. Por alguna razón sólo fuse-sdl fue capaz de leer el código de HACKME.BAS.