Category: Reverse Engineering

You can download the Stack VM-Reverse Engineering Challenge, along with all the challenges for the 2016 Greek Qualifier CTF of European Cybersecurity Challenge, in this link. More details on the Greek ECSC 2016 Qualifier CTF event can be found here.

Points: 90

Challenge designer: Ailianos Panos

Description: > You have been given an executable that, given a correct input, it decrypts and prints a flag. However, our junior coder made some mistakes on the implementation. As a result the decryption does not work correctly. Your goal is to identify the encryption algorithm and fix the mistakes in order to output the correct flag.
The key is 0123456789ABCDEF

Write-up

The crypt.exe implements a stack based Virtual Machine that emulates the Tiny Encryption Algorithm (TEA). The algorithm was compiled with a custom made “assembly” language. The code is the following:

MOVREGREG, EBP,ESP,
MOVREGPTR, EAX,EBP,//MESSSAGE
PUSHIMM,1,

MOVREGREG,EDX,EBP,
SUBREGIMM,EDX,4, //KEY
MOVREGPTR,EDX,EDX,

MOVREGPTR,EAX,EBP,
MOVREGPTR,ESI,EAX,
ADDREGIMM,EAX,4,
MOVREGPTR,EDI,EAX,

MOVREGIMM,ECX,0xC6,
SHRL,ECX,0x18,
MOVREGIMM,EAX,0xEF,
SHRL,EAX,0x10,
ORREGREG,ECX,EAX,
MOVREGIMM,EAX,0x37,
SHRL,EAX,8,
ORREGREG,ECX,EAX,
ORREGIMM,ECX,0x20,

MOVREGREG,EBX,ESI,
SHRL,EBX,4,

PUSHREG,EDX,
ADDREGIMM,EDX,8,
MOVREGPTR,EDX,EDX,
ADDREGREG,EBX,EDX,
POPREG,EDX,

MOVREGREG,EAX,ECX,
ADDREGREG,EAX,ESI,
XORREGREG, EBX,EAX,
MOVREGREG,EAX,ESI,
SHRR,EAX,4, //PURPOSELY WRONG SHOULD BE 5

PUSHREG, EDX,
ADDREGIMM,EDX,12,
MOVREGPTR,EDX,EDX,
ADDREGREG,EAX,EDX,
POPREG,EDX,
XORREGREG,EBX,EAX,

SUBREGREG,EDI,EBX,

MOVREGREG,EBX,EDI,
SHRL,EBX,4,
PUSHREG,EDX,
MOVREGPTR,EDX,EDX,
ADDREGREG,EBX,EDX,
POPREG,EDX,
MOVREGREG,EAX,EDI,
ADDREGREG,EAX,ECX,
XORREGREG,EBX,EAX,

MOVREGREG,EAX,EDI,
SHRR,EAX,4,  //PURPOSELY WRONG SHOULD BE 5

PUSHREG,EDX,
ADDREGIMM,EDX,4,
MOVREGPTR,EDX,EDX,
ADDREGREG,EAX,EDX,
POPREG,EDX,

XORREGREG,EBX,EAX,
SUBREGREG,ESI,EBX,

PUSHREG,ECX,
MOVREGIMM,ECX,0x9E,
SHRL,ECX,0x18,
MOVREGIMM,EAX,0x37,
SHRL,EAX,0x10,
ORREGREG,ECX,EAX,
MOVREGIMM,EAX,0x79,
SHRL,EAX,0x8,
ORREGREG,ECX,EAX,
ORREGIMM,ECX,0xB9,
MOVREGREG,EAX,ECX,
POPREG,ECX,
SUBREGREG,ECX,EAX,

POPREG,EAX,
ADDREGIMM,EAX,1,
CMPREGIMM,EAX,0x20,

PUSHREG,EAX,
JLE,0x38,

LEAVE,

The “assembly” has different opcodes than the x86 CPU but it implements the same approach. It has almost the same registers (EAX,EBP,ESP etc) and the commands have the same approach. The goal is to reverse the binary, identify the existence of the Virtual Machine, and then understand the code. The TEA implementation has the following error;

SHRR,EAX,4

should be

SHRR,EAX,5

Once the player identifies the TEA algorithm two things can be done. Either patch the executable in order to change 0x4 to 0x5 or recreate a TEA implementation in another environment.

A python script was created that implements TEA decryption algorithm. The script decrypts only one block of cipher text and is implemented only for this scenario. It is not a full TEA decryption script.

import sys
import struct
import binascii
from ctypes import *

def decipher(v, k):
    y=c_uint32(v[0])
    z=c_uint32(v[1])
    sum=c_uint32(0xC6EF3720)
    delta=0x9E3779B9
    n=32
    w=[0,0]

    while(n>0):
        z.value -= ( y.value << 4 ) + k[2] ^ y.value + sum.value ^ ( y.value >> 5 ) + k[3]
        y.value -= ( z.value << 4 ) + k[0] ^ z.value + sum.value ^ ( z.value >> 5 ) + k[1]
        sum.value -= delta
        n -= 1

    w[0]=y.value
    w[1]=z.value
    return w

if len(sys.argv)<3:
    print "Missing arguments"
    exit

print "Key:" + sys.argv[1]
print "Cipher file:" + sys.argv[2]
k = struct.unpack("<4L",sys.argv[1])
v = struct.unpack("<2L",binascii.unhexlify(sys.argv[2]))

out = decipher(v,k)
print "FLAG is "+struct.pack("<L",out[0])+struct.pack("<L",out[1])

The crypt.exe binary contains the following ciphertext bytes in hex format a38090be7f3de428.

The script can be run as follows:

❯❯❯ python decrypt.py 0123456789ABCDEF a38090be7f3de428
Key:0123456789ABCDEF
Cipher file:a38090be7f3de428
FLAG is y0d4fl4g

The flag is: > y0d4fl4g