Reversing RISC-based Virtual Machine

by Miguel Angel G @M23Gzz

 agradecimientos especiales @ZEr0Luis

 

El siguiente reto fue presentado durante el redpwnCTF

r1sc 55 solves / 487 points
"Look, Mum, no opcodes!"


TD;LR: Consiste en una VM muy particular, que implementa 3 instrucciones (ret, subleq y int3). Una vez que logramos entender cómo implementaba la VM dichas instrucciones el reto consistió en entender la lógica del programa. Se nos ocurrió poner breakpoints cuando el programa realizaba la lectura de nuestra input, y al hacerlo descubrimos que los 48 caracteres que conforman el input se dividen en palabras de 8 bytes, dichos bytes son interpretados como un entero sin signo, se realizan dos sustracciones a ese  valor y el resultado se compara contra un valor especifico, de esta comparación se determina si la flag es correcta o incorrecta, dicho valor era para todos los casos  0xfffffffffffffffe y la comparación correcta ocurre cuando el valor obtenido de la sustracción es mayor, dejándonos una sola posibilidad 0xffffffffffffffff. Finalmente solo fue cuestión de obtener los valores que se restaban a cada palabra de 8 bytes de nuestro input de 48 bytes en tiempo de ejecución, y resolver la ecuación.

El nombre del archivo en conjunto con la descripción ya nos daban algunas pistas sobre el reto. r1sc hace referencia a la arquitectura RISC la cual se caracteriza por tener un instruction set reducido, mientras que a la vez nos advierte "Look, Mum no opcodes!" de alguna manera logran implementar dicha arquitectura de una manera no convencional sin el uso de "opcodes".

Al ejecutar el binario, solicita un código de acceso, el cuál al ser correcto desplegará el texto “Access authorized.” de no serlo "Access denied." ver Figura 1





Figura 1 - Ejecución del binario

El flujo del programa es siguiente:
  1. Lee input de usuario
  2. Ejecuta una sub-rutina
  3. Se compara una localidad de memoria contra 0 (Se infiere que dicha localidad es modificada en el paso 2)
  4. Si es igual a 0 “Access authorized.” de lo contrario "Access denied."

Solo quedaba analizar la subrutina del paso 2 para poder entender cómo obtener la flag.

En la figura 2 nos muestra el desensamblado de dicha rutina.

  
Figura 2 - Código desensamblado en GDB.

Vemos que los valores los toma con base en el registro RBP dicho registro se carga con una dirección estática en la función principal (offset 0x2038)

También notamos que la función es recursiva (offset 0x10b7)

Deducimos que es ahí donde se implementa la vm.

 Con el fin de replicar las instrucciones dadas por el binario, se extrae la sección señalada por el RBP almacenado en el binario y se guardo en un binario aparte que contiene todas las instrucciones de la VM, esto se realizo con la ayuda de HxD.

Reubicando la dirección 0x0000555555557038 señalada en la ejecución, sería equivalente a la dirección 00003038 dentro del binario, la cual fue extraída del binario original y colocada en otro diferente que se denominó como “r1sc_rom”.


Figura 3 - Localización de la entrada en el binario

Al introducir la entrada “aaaaaaaaaaaa” se puede identificar la dirección donde comienza el uso del input introducido por el usuario siendo 0x555555557050 como se aprecia en las siguientes imágenes, siendo 61 el código hexadecimal del carácter a.

Figura 4 - Entrada al binario

Figura 5 - Ubicación de la entrada en el binario

Al reubicar la dirección en el binario “r1sc_rom” se manipulará directamente el input modificando el contenido hexadecimal del binario que se encuentre en el rango de 00000018 a 00000048 que comprendería los 6 bytes que constituye el input.

Figura 6 - Binario r1sc_rom

Desmenuzando la lógica:
1. RBP + RSI * 8 conforman la direccion efectiva de la instrucción actual

2. Solo se cuentan con 3 instrucciones:
  •     ret -> termina la ejecución del programa
  •     int3 -> Debugger
  •     subleq -> subtract and branch if less than or equal to zero

3. El registro RSI puede considerarse el program counter (PC)

4. Después de cada instrucción incrementa el PC en 3

5. Cada instrucción ocupa 24 bytes de memoria, conformando 3 argumentos de 8 bytes cada uno:  
arg1, arg2, arg3

6. el registro RBP contiene el inicio del espacio de memoria  para la VM dicho espacio es RAM y ROM.

7. Cada localidad de memoria tiene un tamaño de 8 bytes de ahí que  [rsi] = rbp * rsi * 8

La primera instrucción es la siguiente

[0] 09 00 00 00 00 00 00 00
[1] 09 00 00 00 00 00 00 00
[2] 10 00 00 00 00 00 00 00

decodificada en little-endian tiene la siguiente estructura
 
9, 9, 10

La ejecucion es determinada no por el valor de los argumentos (De ahí la pista "Look Mum, no opcodes") sino por el resultado de la resta de los valores de memoria a los que apunta arg1 y arg2 , el  valor de arg3 y en conjunto con el valor del PC (registro RSI)

si pc == 1:
    fin del programa

si [arg2] > [arg1]:
    pc = pc + 3

si no:
    si arg3 == 2:
        int3

    si arg3 == 0:
        pc = pc + 3

    si arg3 != 0:
        pc = arg3

[arg2] = [arg2] - [arg1]
Nota: [argn] denota el operador de indirección para el valor argn ej.[3] = rbp + 3 * 8 = rbp + 24

Antes de dar inicio a la ejecucion del programa se nos pide introducir un input de hasta 48 bytes, el cual se va almacenar en el mismo espacio de memoria del programa, específicamente de las localidades

rbp + 0x018 a rbp + 0x048 (o [3] a [8] inclusive)

dando como resultado 6 palabras de 64 bits cada una como entrada de usuario

Para encontrar la flag, lo que se hizo fue encontrar los lugares donde arg1 o arg2 entraran dentro del rango donde se encontraba almacenada la entrada del usuario.

Al encontrar los segmentos del programa que tenían interacción con el input se encontro lo siguiente 

(para el caso de la localidad [5]):

PC    arg1    arg2   arg3    [arg1]              [arg2]
154   11      5      0        023a367c34e563f0   7463757274736e69
238   273     5      0        72293ef63f8e0a7a   72293ef63f8e0a79
253   15      5      277      fffffffffffffffe   ffffffffffffffff


Como podemos observar en el fragmento anterior en la instruccion [154] se observa que arg1 = 11 y arg2 = 5 arg2 en este caso apunta a la direccion con offset rbp + 0x028 que conforma parte del input, en dicha instruccion se resta nuestro input contra el valor 0x23a367c34e563f0 y posteriormente en la direccion [238] se vuelve a restar  pero ahora con el valor de 0x72293ef63f8e0a7a, para finalmente hacer la comparacion en la direccion [253] contra el  valor de 0xfffffffffffffffe, el resultado de las restas ocurridas en [154] y [238] debe ser mayor o 0xfffffffffffffffe de tal manera que el pc se incrementara en 3, de lo contrario se realiza un salto a 277.

PC    arg1    arg2    arg3    [arg1]                [arg2]
277    9        9        0        0                    0
280    9        9        0        0                    0
283    9        9        0        0                    0
286    9        9        0        0                    0
289    9        9        0        0                    0
292    9        9        1        0                    0

Como se puede observar, si la ejecucion cae en la direccion de memoria [277] se inicia la secuencia de salida del programa. Mientras que si se cumple la condicion se obtiene lo siguiente:

PC    arg1    arg2    arg3    [arg1]                [arg2]
253    15     7       280     fffffffffffffffe    -24311deb30242b22

Ahora se compara contra las localidades rbp + 0x38 que de igual manera conforma parte del input, este patrón es el mismo para las 6 palabras que conforma el input.

De lo anterior podemos deducir lo siguiente:

xi - d1i - d2i > fffffffffffffffe
xi - d1i - d2i = ffffffffffffffff

xi = d1i + d2i + ffffffffffffffff

donde xi contien 8 bytes del input original
Para cada una de las 6 palabras de 8 bytes que conforman nuestro input.

Resolviendo la ecuacion

xi = d1i + d21 - 1

[3] - d9cd4ab6a2d747 - 73899430b0be9520 > fffffffffffffffe
[3] = 7463617B67616C66

[4] - 16069317e428ca9 - 5dd2f647ee29d4cd > fffffffffffffffe
[4] = 5F335F796C6C6175

[5] - 23a367c34e563f0 - 72293ef63f8e0a7a > fffffffffffffffe
[5] = 7463757274736E69

[6] - 39a9fadb327f099 - 71d8bf8cc0467ed1 > fffffffffffffffe
[6] = 75735F3A736E6F69

[7]- 5d4d629e80d5489 - 5f9d8902895817da > fffffffffffffffe
[7] = 65725F2C71656C62

[8] - 96f75d79b354522 - 73c3fe96ce29e753 > fffffffffffffffe
[8] = 7D33746E695F2C74

[3] = tca{galf
[4] = _3_yllau
[5] = tcurtsni
[6] = us_:snoi
[7] = er_,qelb
[8] = }3tni_,t

finalmente para obtener la flag le hacemos el inverso a los numeros que obtuvimos

flag{actually_3_instructions:_subleq,_ret,_int3}
Se implementó el siguiente código en Python3 para resolver este reto, se trata de la misma implementación de la vm pero ahora en python, se utiliza en conjunto con el archivo r1sc_rom que extrajimos del binario original:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import struct

 

def vm(opcode, rom = []):

    jump = 0

    arg1 = rom[opcode]

    arg2 = rom[opcode + 1]

    arg3 = rom[opcode + 2]

   

    if(arg1 < 9) or (arg2<9):

        print(rom[3:9])

        print(opcode,arg1,arg2,arg3,"    ", "%x"%rom[arg1], "%x"%rom[arg2])

   

    if(opcode == 1):

        return None

    if (rom[arg2] > rom[arg1]) or (jump != 0):

           opcode = opcode + 3

 

    else:

        if arg3 == 2:

            print("debugging")

            return None

 

        if arg3 == 0:

            opcode = opcode + 3

 

        if arg3 != 0:

            opcode = arg3

    rom[arg2] = rom[arg2] - rom[arg1]

 

    if(arg1 < 9) or (arg2<9):

        print(rom[3:9])

        print(opcode,arg1,arg2,arg3,"    ", "%x"%rom[arg1], "%x"%rom[arg2])

    return opcode, rom

   

 

def gen_rom(f):

    with open(f,'rb') as fd:

        buff = fd.read()

        r_iter = struct.iter_unpack('<Q',buff)

        rom = [i[0] for i in r_iter]

        return rom

    return None

 

def main():

    rom = gen_rom('r1sc_rom')

    if rom is None:

        return

    opcode, rom = vm(0, rom)

    counter = 0

    while opcode is not None:

        try:

            opcode, rom = vm(opcode, rom)

            counter += 1

        except Exception as e:

            break

    print(counter)

 

if __name__ == "__main__":


    main()



Go Mayas!.

Comentarios

Publicar un comentario