Reversing the secret of the Emoji Virtual Machine

 By Luis Almaraz aka lehag
@lehag07

Descripción 

Este reto fue presentado durante el CTF de Hitcon Quals 2019 donde participé junto con mi equipo Mayas. La única descripción que nos daba el reto es la siguiente: “A simple VM that takes emojis as input! Try figure out the secret!”. En esta entrada se describe la solución que propusimos para resolver el reto.

Solución

Identificando el archivo emojivm-
d967bd1b53b927820de27960f8eec7d7833150ca.zip

1. Abrimos una terminal en donde se encuentra nuestro archivo.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$

2. Listamos los archivos del directorio actual.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$ ls -l
total 880
-rw-rw-r-- 1 lehag lehag 898690 oct 16 21:40 emojivm-d967bd1b53b927820de27960f8eec7d7833150ca.zip
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$

3. Calculamos la suma SHA1 del archivo llamado emojivm-
d967bd1b53b927820de27960f8eec7d7833150ca.zip para conocer su integridad.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$ sha1sum emojivm-
d967bd1b53b927820de27960f8eec7d7833150ca.zip
d967bd1b53b927820de27960f8eec7d7833150ca emojivm-
d967bd1b53b927820de27960f8eec7d7833150ca.zip
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$

Es la misma que la asociada con el archivo que proporciona el desafío.

4. Identificamos el tipo de archivo emojivm-d967bd1b53b927820de27960f8eec7d7833150ca.zip.
 

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$ file emojivm-
d967bd1b53b927820de27960f8eec7d7833150ca.zip
emojivm-d967bd1b53b927820de27960f8eec7d7833150ca.zip: Zip archive data, at least v1.0 to extract
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$

Es un archivo Zip.

5. Descomprimimos el archivo emojivm-d967bd1b53b927820de27960f8eec7d7833150ca.zip.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$ unzip emojivm-
d967bd1b53b927820de27960f8eec7d7833150ca.zip
Archive: emojivm-d967bd1b53b927820de27960f8eec7d7833150ca.zip
creating: emojivm_misc/
inflating: emojivm_misc/answer.txt
inflating: emojivm_misc/readme.txt
[snipped]
inflating: emojivm_reverse/chal.evm
inflating: emojivm_reverse/emojivm
inflating: emojivm_reverse/readme.txt
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$

Identificando el directorio emojivm_reverse

1. Listamos los archivos del directorio actual.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$ ls -l
total 892
-rw-rw-r-- 1 lehag lehag 898690 oct 16 21:40 emojivm-d967bd1b53b927820de27960f8eec7d7833150ca.zip
drwxr-xr-x 2 lehag lehag 4096 oct 10 16:37 emojivm_misc
drwxr-xr-x 2 lehag lehag 4096 oct 10 16:52 emojivm_pwn
drwxr-xr-x 2 lehag lehag 4096 oct 10 16:38 emojivm_reverse
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$

Obtenemos 3 directorios cuando descomprimimos el archivo emojivm-
d967bd1b53b927820de27960f8eec7d7833150ca.zip:

• emojivm_misc/
• emojivm_pwn/
• emojivm_reverse/
  

Pero para este desafío, nos centraremos en el contenido del directorio emojivm_reverse.

2. Nos cambiamos al directorio emojivm_reverse.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM$ cd emojivm_reverse/
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

3. Listamos los archivos del directorio actual.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ ls -l
total 96
-rw-r--r-- 1 lehag lehag 30483 oct 7 10:00 chal.evm
-rw-r--r-- 1 lehag lehag 59536 oct 7 10:00 emojivm
-rw-r--r-- 1 lehag lehag 21 oct 10 16:38 readme.txt
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

El desafío nos proporciona tres archivos:

• chal.evm
• emojivm
• readme.txt

Identificando el archivo readme.txt

1. Identificamos el tipo de archivo readme.txt.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ file readme.txt
readme.txt: ASCII text
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

Es un texto ASCII.

2. Mostramos el contenido del archivo readme.txt.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ cat readme.txt
./emojivm ./chal.evm
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

Indica cómo ejecutar el programa emojivm.

Identificando el archivo chal.evm

1. Identificamos el tipo de archivo chal.evm.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ file chal.evm
chal.evm: UTF-8 Unicode text, with very long lines, with no line terminators
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

Es un texto UTF-8 Unicode.

2. Mostramos el contenido del archivo chal.evm.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ cat chal.evm
空空空 ⏬ 😅😍
⏬ 😀 ❌ ⏬ 😀 ➕🆕⏬😀⏬😍⏬😜⏬😍❌⏬😂➕⏬😜⏬😍❌⏬😂➕⏬😜⏬😍❌⏬😂➕⏬😜⏬😍❌⏬😂➕⏬😜⏬ 🆕 ⏬ 😍😜😍
⏬ 😂😜😍😂😜😍😂😜😍😂😜
⏬⏬
❌ ➕🆕⏬😀⏬😍⏬😜⏬😍❌⏬😂➕⏬😜⏬😍❌⏬😂➕⏬😜⏬😍❌⏬😂➕⏬😜⏬😍❌⏬😂➕⏬😜⏬
❌
⏬⏬ ⏬⏬⏬ ⏬⏬⏬ ⏬⏬ ⏬⏬⏬ ⏬⏬⏬ ⏬⏬ ⏬⏬⏬ ⏬⏬⏬ ⏬⏬ ⏬⏬⏬ ⏬⏬⏬ ⏬
[snipped]
😀 😀😁😀😂😀😀😜😀😄😀😀😂😀😍😀😀😁😀😀
😀 😀
😂
😀😀
😀😀😀
😀😀
⏬ ⏬⏬ ⏬⏬⏬⏬⏬
😀 ⏬⏬⏬ ⏬⏬ ⏬⏬⏬ ⏬⏬ ⏬⏬⏬ ⏬⏬⏬ ⏬⏬⏬ ⏬⏬ ⏬⏬ ⏬⏬ ⏬⏬⏬ ⏬⏬ ⏬⏬⏬
😀
⏬⏬
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

Contiene un conjunto de diferentes emojis.

Identificando el archivo emojivm

1. Identificamos el tipo de archivo emojivm. 

 

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ file emojivm
emojivm: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/l, for
GNU/Linux 3.2.0, BuildID[sha1]=48b4ebda5543d884a9be015a4c789386420f5fce, stripped
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

Es un programa de tipo ELF de 64 bits cuyos símbolos de debuggeo han sido eliminados.

Ejecutando el programa emojivm

1. Asignamos permisos de ejecución al programa emojivm.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ chmod +x emojivm
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

2. Ejecutamos el programa emojivm.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ ./emojivm chal.evm
*************************************
*
*
*
Welcome to
*
*
EmojiVM 😀😁😮       *
😁😁
⏬ 😁 *
*
The Reverse Challenge
*
*
*
*************************************
Please input the secret:

Pide un secreto.

3. Insertamos alguna cadena como entrada.

ACB123
😭
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

Imprime el emoji de cara llorando. Por lo tanto, es necesario desensamblar y depurar el programa emojivm para comprender cómo funciona.

Desensamblando y depurando el programa emojivm

1. Desensamblamos y depuramos el programa emojivm con IDA.

2. IDA presenta la función principal del programa. Espera recibir el archivo llamado chal.evm como parámetro de línea de comandos, Figura 1.

Figura 1. La función principal del
programa emojivm.

En caso de que el usuario no proporcione el archivo chal.evm, el programa imprime el mensaje "Usage: ./emojivm <source_file>" De lo contrario, el programa continúa con su ejecución, Figura 2.

Figura 2. El mensaje de cómo usar el programa emojivm.

3. El programa implementa un temporizador que finaliza la ejecución del mismo si el usuario no interactúa con él después de un minuto, Figura 3.

Figura 3. El temporizador del programa emojivm.

Es tedioso depurar el programa de esta manera, porque termina después de un minuto. Por esta razón, decidimos parchar la función renombrada aquí como setTimer con instrucciones NOP.

4. La siguiente función renombrada initEmojiValues inicializa cada valor para cada emoji que se utilizará como bytecode, Figura 4.

Figura 4. La función initEmojiValues inicializa cada valor para cada emoji.

5. La función renombrada readChalEvmFile lee el contenido del archivo chal.evm, Figura 5.

Figura 5. La función readChalEvmFile lee el
contenido del archivo chal.evm.

6. Hay una función renombrada executeEmojiBytecodes, que traduce de emoji a bytecodes en la VM (Virtual Machine), Figura 6.

Figura 6. La función executeEmojiBytecodes traduce de emoji a bytecodes.

7. Dentro de la función executeEmojiBytecodes, hay un bloque de código y una función renombrada getEmojiValueInVM que nos permite determinar el valor de cada emoji en la VM, Figura 7.

Figura 7. Cada emoji se interpretará como un bytecode en la VM.

La función anterior nos ayudó a construir la siguiente relación entre instrucciones y datos en la VM, Tabla 1.

Tabla 1. Relación entre instrucciones y datos en la VM.

Emoji	Código	Instrucción/Dato	Caso
🈳	0x1f233	NOP	1
➕	0x2795	ADD j + k	2
➖	0x2796	SUB j - k	3
❌	0x274c	MUL j * k	4
❓	0x2753	MOD j % k	5
❎	0x274e	XOR j ^ k	6
👫	0x1f46b	AND j & k	7
💀	0x1f480	LT	8
💯	0x1f4af	EQ	9
🚀	0x1f680	JMP	10
🈶	0x1f236	JNE	11
🈚	0x1f21a	JE	12
⏬	0x23ec	PUSH	13
-	-	POP	14
📤	0x1f4e4	LOAD chunk(j).at(k)	15
📥	0x1f4e5	STORE chunk(j).at(k) = l	16
🆕	0x1f195	NEW	17
-	-	DELETE	18
📄	0x1f4c4	SCANF	19
📝	0x1f4dd	PRINTF	20
-	-	WRITE (Imprime carácter a carácter hasta ‘\0’)	21
-	-	WRITE2 (Imprime un carácter en su representacion decimal)	22
🛑	0x1f6d1	EXIT	23
😀	0x1f600	0x0	-
😁	0x1f601	0x1	-
😂	0x1f602	0x2	-
🤣	0x1f923	0x3	-
😜	0x1f61c	0x4	-
😄	0x1f604	0x5	-
😅	0x1f605	0x6	-
😆	0x1f606	0x7	-
😉	0x1f609	0x8	-
😊	0x1f60a	0x9	-
😍	0x1f60d	0xa	-

La VM implementa una instrucción switch que contiene 23 casos de acuerdo con las operaciones que se ejecutarán, como se muestra en la Tabla 1. La Figura 8 muestra una visión general de los casos anteriores.

Figura 8. La VM implementa 23 casos que representan cada instrucción a ejecutar.

Generando el código ensamblador de los bytecodes emoji

1. Programamos un script para traducir los bytecodes asociados con cada emoji a instrucciones de ensamblador y comprender su flujo de ejecución en la VM.

#!/usr/bin/env python3
## Author: lehag
## Code: emoji_asm.py

def fromEmojiBytecodesToASM(data):
    k  = 0;
    for i in range(0, len(data)):
        if(hex(ord(data[i])) == '0x1f233'):
            print("{:08x} NOP".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x2795'):
            print("{:08x} ADD j + k".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x2796'):
            print("{:08x} SUB j - k".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x274c'):
            print("{:08x} MUL j * k".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x2753'):
            print("{:08x} MOD j % k".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x274e'):
            print("{:08x} XOR j ^ k".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f46b'):
            print("{:08x} AND j & k".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f480'):
            print("{:08x} LT".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f4af'):
            print("{:08x} EQ".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f680'):
            print("{:08x} JMP".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f236'):
            print("{:08x} JNE".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f21a'):
            print("{:08x} JE".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x23ec'):
            print("{:08x} PUSH".format(k), end=" ");
            k += 2;
        elif(hex(ord(data[i])) == '0x1f4e4'):
            print("{:08x} LOAD chunk(j).at(k)".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f4e5'):
            print("{:08x} STORE chunk(j).at(k) = l".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f195'):
            print("{:08x} NEW".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f4c4'):
            print("{:08x} SCANF".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f4dd'):
            print("{:08x} PRINTF".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f6d1'):
            print("{:08x} EXIT".format(k));
            k += 1;
        elif(hex(ord(data[i])) == '0x1f600'):
            print("0x0");
        elif(hex(ord(data[i])) == '0x1f601'):
            print("0x1");
        elif(hex(ord(data[i])) == '0x1f602'):
            print("0x2");
        elif(hex(ord(data[i])) == '0x1f923'):
            print("0x3");
        elif(hex(ord(data[i])) == '0x1f61c'):
            print("0x4");
        elif(hex(ord(data[i])) == '0x1f604'):
            print("0x5");
        elif(hex(ord(data[i])) == '0x1f605'):
            print("0x6");
        elif(hex(ord(data[i])) == '0x1f606'):
            print("0x7");
        elif(hex(ord(data[i])) == '0x1f609'):
            print("0x8");
        elif(hex(ord(data[i])) == '0x1f60a'):
            print("0x9");
        elif(hex(ord(data[i])) == '0x1f60d'):
            print("0xA");
with open("chal.evm", 'r') as fd:
  data = fd.read();

fromEmojiBytecodesToASM(data);

2. Ejecutamos el script anterior y obtenemos las instrucciones en ensamblador de los bytecodes emoji.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ python3 emoji_asm.py
00000000 NOP
00000001 NOP
00000002 NOP
00000003 PUSH 0x6
00000005 PUSH 0xA
[snipped]
00002275 STORE chunk(j).at(k) = l
00002276 PUSH 0x0
00002278 PRINTF
00002279 EXIT
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

El proceso de validación

1. Una vez que entendemos el código ensamblador y después de depurar la ejecución del programa, se observa que la VM ejecuta 4 pasos para validar el secreto de entrada:

• Longitud del secreto
• Formato del secreto
• Serie de operaciones realizadas
• Valores finales

Longitud del secreto

1. Primero, el programa llamado emojivm cuenta la cantidad de caracteres que ingresamos, comparando cada carácter del secreto hasta que llega al caracter ‘\ n’ o ‘\ 0’, Figura 9.

Figura 9. El programa cuenta el número de caracteres del secreto.

Si el conteo no es igual a 0x18 (24), el programa imprime el emoji de cara llorando y finaliza su ejecución. De lo contrario, el programa continúa con su ejecución, Figura 10.

Figura 10. Si el conteo no es igual a 0x18, el
el programa termina su ejecución.

Formato del secreto

1. La segunda validación corresponde al formato del secreto. El programa inicia un contador de 0x0 a 0x18, Figura 11.

Figura 11. El programa inicia un contador de 0x0 a 0x18.

2. Luego, verifica que cada valor de secret[i%5] sea igual a “-”, esperando una entrada con el siguiente formato: XXXX-XXXX-XXXX-XXXX-XXXX, Figura 12. Si lo anterior no se cumple, el programa imprime el emoji de cara llorando y finaliza su ejecución, Figura 10. De lo contrario, el programa continúa con su ejecución.

Figura 12. Cada valor de secret[i%5] tiene que ser igual a "-".

Serie de operaciones realizadas

1. Nuevamente, el programa inicia un contador de 0x0 a 0x18, Figura 11. Realiza algunas operaciones utilizando los casos 2, 3, 5, 6, 7, 8, 9, 10, 11 y 12 correspondientes a las operaciones: ADD, SUB, MOD, XOR, AND, LT, EQ, JMP, JNE y JE, principalmente. Toma algunas posiciones del secreto para operar con otros valores constantes y formar un arreglo renombrado aquí como result. Obtenemos las siguientes operaciones:

for i in range(24):
  if(i % 4 == 0):
    result[i] = secret[i] + 0x1e;
  if(i % 4 == 1):
    result[i] = (secret[i] - 0x8) ^ 0x7;
  if(i % 4 == 2):
    result[i] = ((secret[i] + 0x2c) ^ 0x44) - 0x4;
  else:
    result[i] = (secret[i] ^ 0x65)^(0xac & 0x14);

Comparación final

1. Una vez que el programa calculó los valores anteriores, inicia un nuevo contador de 0x0 a 0x18, Figura 11, y compara cada resultado final anterior con los siguientes valores:

final = [0x8e, 0x63, 0xcd, 0x12, 0x4b, 0x58, 0x15, 0x17, 0x51, 0x22, 0xd9, 0x04, 0x51, 0x2c, 0x19, 0x15,
0x86, 0x2c, 0xd1, 0x4c, 0x84, 0x2e, 0x20, 0x06];

Utiliza la siguiente instruccion, Figura 13:

Figura 13. La comparación entre los valores del arreglo llamado result y los valores del arreglo llamado final.

Si los valores anteriores no coinciden, el programa imprime el emoji de cara llorando y finaliza su ejecución, Figura 10. De lo contrario, el programa continúa con su ejecución.

Encontrando el secreto correcto

1. Para encontrar el secreto correcto, desarrollamos un script invirtiendo cada operación previa.

#!/usr/bin/env python3
## Author: lehag
## Code: reverse_secret.py

final = [0x8e, 0x63, 0xcd, 0x12, 0x4b, 0x58, 0x15, 0x17, 0x51, 0x22, 0xd9, 0x04, 0x51, 0x2c, 0x19, 0x15, 0x86, 0x2c, 0xd1, 0x4c, 0x84, 0x2e, 0x20, 0x06];
secret = [None]*24;

for i in range(0, 24):
    if(i % 4 == 0):
        secret[i] = chr(final[i] - 0x1E);
    elif(i % 4 == 1):
        secret[i] = chr((final[i] ^ 0x7) + 0x8);
    elif(i % 4 == 2):
        secret[i] = chr(((final[i] + 0x4) ^ 0x44) - 0x2C);
    else:
        secret[i] = chr((final[i] ^ 0x65) ^ (0xAC & 0x14));

print(''.join(secret));  ## plis-g1v3-me33-th3e-f14g

2. Ejecutamos el script anterior y obtenemos el secreto correcto.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ python3 reverse_secret.py
plis-g1v3-me33-th3e-f14g
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

3. Luego, ejecutamos el programa llamado emojivm con el secreto correcto y obtenemos el flag.

lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$ ./emojivm_patched chal.evm
*************************************
*
*
*
Welcome to
*
*
EmojiVM 😀😁😮       *
😁😁
😁
⏬ *
*
The Reverse Challenge
*
*
*
*************************************
Please input the secret: plis-g1v3-me33-th3e-f14g
😍
hitcon{R3vers3_Da_3moj1}
lehag@blackbox:~/Hitcon/2019/Quals/RE/EmojiVM/emojivm_reverse$

Flag

hitcon{R3vers3_Da_3moj1}

Agradecimientos

A Bryan Enrique, compañero de Mayas, por aportar ideas durante la solucion del reto.

Go Mayas!