Rev 300: Ensartador

By Mexihacks Team

Descripcion:

Recuerdo que la materia de Ensamblador en la universidad soliamos llamarla Ensartador, espero este reto no sea algo similar.
Existe una funcion matematica, implementala y arrojara un numero el cual sera la flag.


Resolucion:


1. El archivo que nos dan es de tipo ASCII.

user@blackbox:~/Hackdef/RE/3. Ensartador$ file Ensartador.asm

Ensartador.asm: ASCII text

user@blackbox:~/Hackdef/RE/3. Ensartador$

2. Al abrir el código anterior se observa un ascii art rifado, referente al logo anterior del HackDef:

2.1 Al abrir el código anterior se observa que el código embebido es de tipo MIPS.

# Can U reverse it?
# R U a h4ck3r or n00b5?
[snipped]
.text
.globl main
main:
la $a0, eid_in
li $v0, 4
syscall
la $a0, new_eid
li $v0, 4
syscall
[snipped]
.data
eid_in: .asciiz "run program! LOL ..."
eid_out: .asciiz "HAPPY EID: flag{"
eid_end: .asciiz "}"
eid_num: .word 200
leet_eid: .word 20191337
new_eid: .asciiz "\n"

3. Ejecutamos el código anterior con el entorno llamado spim.

user@blackbox:~/Hackdef/RE/3. Ensartador$ spim -f Ensartador.asm

SPIM Version 8.0 of January 8, 2010
Copyright 1990-2010, James R. Larus.
All Rights Reserved.
See the file README for a full copyright notice.
Loaded: /usr/lib/spim/exceptions.s
spim: (parser) syntax error on line 8 of file Ensartador.asm
.,,
^
The following symbols are undefined:
main
Instruction references undefined symbol at 0x00400014
[0x00400014] 0x0c000000 jal 0x00000000 [main] ; 188: jal main
user@blackbox:~/Hackdef/RE/3. Ensartador$

Tiene errores de sintaxis, corregimos la sintaxis, al eliminar el encabezado de abajo:

# Can U reverse it?
# R U a h4ck3r or n00b5?
# Y0u kn0w i'm alw4ys h4ppy exc3pt 0n3 d4y, 1t w4s l4st y34r wh3n s0m30n3 f0und my fl4g!
# This year you w1ll n3v3r g3t my flag ... but y0u c4n g3t it despues que termine el CTF!
[snipped]
**,*,,**,/,.*, .*,...,*....,,,*,.*/,**... ,, .*, ./,**... .*,*..*,,*,...**.,*. ...,*,*,.**,*,**,,*
**,*,,**,*/**, ... .*,,,.,*,,,.,,.**,//,**,,. .,, .**,*/,**,,, */* *,,, ** .*. .. .,,,*,*. **,*,**,**
**,*, ,*,**, ./// .*. .*,,,.**/**,** *//. .**/**,** ***. *,,,. ** .*. .*// .** .*. **.*,*,.,*

4. Guardamos cambios.
5. Ejecutamos la nueva versión del programa.

user@blackbox:~/Hackdef/RE/3. Ensartador$ spim -f 2_Ensartador.asm
SPIM Version 8.0 of January 8, 2010
Copyright 1990-2010, James R. Larus.
All Rights Reserved.
See the file README for a full copyright notice.
Loaded: /usr/lib/spim/exceptions.s
run program! LOL ...

Al parecer ya no tiene errores de sintaxis, pero no termina, pareciera caer en un ciclo infinito.

6. Cuando se revisó su código fuente, se visualizó que es la implementación clásica del algoritmo recursivo de Fibonacci, los siguientes son los valores de inicio:

eid_in: .asciiz "run program! LOL ..."
eid_out: .asciiz "HAPPY EID: flag{"
eid_end: .asciiz "}"
eid_num: .word 200
leet_eid: .word 20191337
new_eid: .asciiz "\n"

El código referente a la función recursiva del algoritmo es el siguiente:

bif:
addi $sp, $sp, -12
sw $ra, 0($sp)
sw $s0, 4($sp)
sw $s1, 8($sp)
add $s0, $a0, $zero
addi $t1, $zero, 1
beq $s0, $zero, return0
beq $s0, $t1, return1
addi $a0, $s0, -1
jal bif
add $s1, $zero, $v0
addi $a0, $s0, -2
jal bif
lw $a0, leet_eid
move $t2, $a0
div $v0, $t2
mfhi $v0
add $v0, $v0, $s1 # final value is return value from n-2 recursion of fibonacci...
exitbif:
lw $ra, 0($sp)
lw $s0, 4($sp)
lw $s1, 8($sp)
addi $sp, $sp, 12
jr $ra
return1:
li $v0,1
j exitbif
return0:
li $v0,0
j exitbif

Al ser recursivo, su tiempo de ejecución es mayor que en su versión iterativa, fue por eso que al ejecutarlo el programa parecer caer en un ciclo infinito, sin embargo, esto no es así.

Si se presta atención a las siguientes líneas de código:

lw $a0, leet_eid
move $t2, $a0
div $v0, $t2
mfhi $v0

La instruccion mfhi mueve el resultado de la division a $v0, aunque no es recomendable ese orden de instrucciones en arquitectura MIPS, el emulador SPIM no se queja al respecto :-)

Es notorio que el algoritmo tiene una pequeña modificación en el resultado que retorna, en pseudocódigo tenemos que las líneas anteriores corresponden a hacer las siguientes operaciones:

v0 = bif(s0 - 1);
s1 = v0;
v0 = bif(s0 - 2);
t2 = 20191337;
v0 = v0 % t2;
v0 = v0 + s1;
return v0;

Al resultado de cada recursividad de la función llamada bif se le aplica un módulo igual a t2, t2 corresponde al valor constante de 20191337.

7. Dicho lo anterior, se programó el siguiente script que implementa la función de Fibonacci, pero en su forma iterativa, para tener una ejecución más rápida comparada con su versión recursiva, pero se le hizo la modificación considerando la operación del módulo.

def f(n):
a, b = 0, 1
for i in range(0, n):
a, b = b, a%20191337 + b
return a
n = 200
print(f(n))

8. Ejecutar el script anterior, se obtiene la flag!!!!!!!!

user@blackbox:~/Hackdef/RE/3. Ensartador$ python3 fib.py
1675618669
user@blackbox:~/Hackdef/RE/3. Ensartador$