Can you crack it? Stage 2 Solution

There has been a lot of news about the “Can you crack it?” challenge that is currently to publicise GCHQ recruiting. Here is my solution for stage 2 – the implementation of the Virtual Machine, or emulator. It’s actually pretty straight forward when you get a hold of a few of the nuances. I’ll put a list of hints here, and then present the full solution after the fold.

  1. As of stage 1 – everything is centred around the x86 architecture, this means that your instructions need to mirror the behaviour of their x86 equivalents
  2. Firmware seems to be irrelevant – don’t worry about it.
  3. There is no real trickery here – it’s just a straight forward instruction set simulator implementation
  4. The programme will finish on a HALT instruction

This is actually quite a neat little program that works by decrypting itself further programme code which it then runs and decrypts the message to get to the next stage… enjoy…

 

My implementation is in C… I don’t like javascript – it is tested using GCC on an Intel Mac. It’s a rough and ready implementation, so don’t judge me too much.

#include <stdio.h>
#include <stdlib.h>

#define MEM_LEN 768
#define FW_LEN  8

unsigned char mem[] = {
    0x31, 0x04, 0x33, 0xaa, 0x40, 0x02, 0x80, 0x03, 0x52, 0x00, 0x72, 0x01, 0x73, 0x01, 0xb2, 0x50,
    0x30, 0x14, 0xc0, 0x01, 0x80, 0x00, 0x10, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x98, 0xab, 0xd9, 0xa1, 0x9f, 0xa7, 0x83, 0x83, 0xf2, 0xb1, 0x34, 0xb6, 0xe4, 0xb7, 0xca, 0xb8,
    0xc9, 0xb8, 0x0e, 0xbd, 0x7d, 0x0f, 0xc0, 0xf1, 0xd9, 0x03, 0xc5, 0x3a, 0xc6, 0xc7, 0xc8, 0xc9,
    0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 0xd8, 0xd9,
    0xda, 0xdb, 0xa9, 0xcd, 0xdf, 0xdf, 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 0xe8, 0xe9,
    0x26, 0xeb, 0xec, 0xed, 0xee, 0xef, 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 0xf8, 0xf9,
    0x7d, 0x1f, 0x15, 0x60, 0x4d, 0x4d, 0x52, 0x7d, 0x0e, 0x27, 0x6d, 0x10, 0x6d, 0x5a, 0x06, 0x56,
    0x47, 0x14, 0x42, 0x0e, 0xb6, 0xb2, 0xb2, 0xe6, 0xeb, 0xb4, 0x83, 0x8e, 0xd7, 0xe5, 0xd4, 0xd9,
    0xc3, 0xf0, 0x80, 0x95, 0xf1, 0x82, 0x82, 0x9a, 0xbd, 0x95, 0xa4, 0x8d, 0x9a, 0x2b, 0x30, 0x69,
    0x4a, 0x69, 0x65, 0x55, 0x1c, 0x7b, 0x69, 0x1c, 0x6e, 0x04, 0x74, 0x35, 0x21, 0x26, 0x2f, 0x60,
    0x03, 0x4e, 0x37, 0x1e, 0x33, 0x54, 0x39, 0xe6, 0xba, 0xb4, 0xa2, 0xad, 0xa4, 0xc5, 0x95, 0xc8,
    0xc1, 0xe4, 0x8a, 0xec, 0xe7, 0x92, 0x8b, 0xe8, 0x81, 0xf0, 0xad, 0x98, 0xa4, 0xd0, 0xc0, 0x8d,
    0xac, 0x22, 0x52, 0x65, 0x7e, 0x27, 0x2b, 0x5a, 0x12, 0x61, 0x0a, 0x01, 0x7a, 0x6b, 0x1d, 0x67,
    0x75, 0x70, 0x6c, 0x1b, 0x11, 0x25, 0x25, 0x70, 0x7f, 0x7e, 0x67, 0x63, 0x30, 0x3c, 0x6d, 0x6a,
    0x01, 0x51, 0x59, 0x5f, 0x56, 0x13, 0x10, 0x43, 0x19, 0x18, 0xe5, 0xe0, 0xbe, 0xbf, 0xbd, 0xe9,
    0xf0, 0xf1, 0xf9, 0xfa, 0xab, 0x8f, 0xc1, 0xdf, 0xcf, 0x8d, 0xf8, 0xe7, 0xe2, 0xe9, 0x93, 0x8e,
    0xec, 0xf5, 0xc8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x37, 0x7a, 0x07, 0x11, 0x1f, 0x1d, 0x68, 0x25, 0x32, 0x77, 0x1e, 0x62, 0x23, 0x5b, 0x47, 0x55,
    0x53, 0x30, 0x11, 0x42, 0xf6, 0xf1, 0xb1, 0xe6, 0xc3, 0xcc, 0xf8, 0xc5, 0xe4, 0xcc, 0xc0, 0xd3,
    0x85, 0xfd, 0x9a, 0xe3, 0xe6, 0x81, 0xb5, 0xbb, 0xd7, 0xcd, 0x87, 0xa3, 0xd3, 0x6b, 0x36, 0x6f,
    0x6f, 0x66, 0x55, 0x30, 0x16, 0x45, 0x5e, 0x09, 0x74, 0x5c, 0x3f, 0x29, 0x2b, 0x66, 0x3d, 0x0d,
    0x02, 0x30, 0x28, 0x35, 0x15, 0x09, 0x15, 0xdd, 0xec, 0xb8, 0xe2, 0xfb, 0xd8, 0xcb, 0xd8, 0xd1,
    0x8b, 0xd5, 0x82, 0xd9, 0x9a, 0xf1, 0x92, 0xab, 0xe8, 0xa6, 0xd6, 0xd0, 0x8c, 0xaa, 0xd2, 0x94,
    0xcf, 0x45, 0x46, 0x67, 0x20, 0x7d, 0x44, 0x14, 0x6b, 0x45, 0x6d, 0x54, 0x03, 0x17, 0x60, 0x62,
    0x55, 0x5a, 0x4a, 0x66, 0x61, 0x11, 0x57, 0x68, 0x75, 0x05, 0x62, 0x36, 0x7d, 0x02, 0x10, 0x4b,
    0x08, 0x22, 0x42, 0x32, 0xba, 0xe2, 0xb9, 0xe2, 0xd6, 0xb9, 0xff, 0xc3, 0xe9, 0x8a, 0x8f, 0xc1,
    0x8f, 0xe1, 0xb8, 0xa4, 0x96, 0xf1, 0x8f, 0x81, 0xb1, 0x8d, 0x89, 0xcc, 0xd4, 0x78, 0x76, 0x61,
    0x72, 0x3e, 0x37, 0x23, 0x56, 0x73, 0x71, 0x79, 0x63, 0x7c, 0x08, 0x11, 0x20, 0x69, 0x7a, 0x14,
    0x68, 0x05, 0x21, 0x1e, 0x32, 0x27, 0x59, 0xb7, 0xcf, 0xab, 0xdd, 0xd5, 0xcc, 0x97, 0x93, 0xf2,
    0xe7, 0xc0, 0xeb, 0xff, 0xe9, 0xa3, 0xbf, 0xa1, 0xab, 0x8b, 0xbb, 0x9e, 0x9e, 0x8c, 0xa0, 0xc1,
    0x9b, 0x5a, 0x2f, 0x2f, 0x4e, 0x4e, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};

unsigned char firmware[] = {
    0xd2, 0xab, 0x1f, 0x05, 0xda, 0x13, 0xf1, 0x10
};

typedef struct S_CPU_STATE
{

    unsigned int ip;

    unsigned int r[4];

    unsigned int cs;
    unsigned int ds;

    unsigned int fl;
} s_cpu_state;

int stop_cpu = 0;

void dump_cpu( s_cpu_state cpu )
{
    int i;

    printf("ip        => %dn", cpu.ip);
    for (i = 0; i < 4; i++)
    {
        printf("r%d       => %dn", i, cpu.r[i]);
    }
    printf("cs        => %dn", cpu.cs);
    printf("ds        => %dn", cpu.ds);
    printf("fl        => %dnn", cpu.fl);

    for (i = 0; i < MEM_LEN; i++ )
    {
        if (i % 16 == 0)
            printf("n");

        printf("0x%02x, ", mem[i]);
    }

    for (i = 0; i < MEM_LEN; i++ )
    {
        if (i % 16 == 0)
            printf("n");

        printf("%c", mem[i]);
    }

    return;
}

int read_reg( unsigned int *v, s_cpu_state *cpu, unsigned int ix )
{
    if (ix < 4)
    {
        *v = cpu->r[ix];
        return 0;
    }
    else if (ix == 4)
    {
        *v = cpu->cs;
        return 0;
    }
    else if (ix == 5)
    {
        *v = cpu->ds;
        return 0;
    }
    else
        return 1;
}

int write_reg(s_cpu_state *cpu, unsigned int ix, unsigned int v )
{
    if (ix < 4)
    {
        cpu->r[ix] = v;
        return 0;
    }
    else if (ix == 4)
    {
        cpu->cs = v;
        return 0;
    }
    else if (ix == 5)
    {
        cpu->ds = v;
        return 0;
    }
    else
        return 1;
}

void siginthandler(int param)
{
    stop_cpu = 1;
}

unsigned int decode_instruction( unsigned char instr[2], s_cpu_state *cpu )
{
    unsigned char opcode = (0xE0 & instr[0]) >> 5;
    unsigned char mod = (0x10 & instr[0]) >> 4;
    unsigned int op1 = 0xF & instr[0];
    unsigned int op2 = 0xFF & instr[1];
    unsigned int ip_inc = 0;
    unsigned int v1, v2, tmp, addr;

    printf("ibuf = 0x%02x %02x => ",instr[0], instr[1]);

    /* mod 0 instructions */
    if (mod == 0)
    {
        switch (opcode)
        {
        case 0x0:
            /* jmp r1 */
            printf("jmp r[%d]n",op1);

            if (read_reg(&v1, cpu, op1))
                return 1;

            cpu->ip = (cpu->cs*16) + v1;

            printf("tjump to %dn", cpu->ip);

            ip_inc = 0; // 0 increment as we modify IP
            break;
        case 0x1:
            /* movr r1,r2 */
            printf("movr r[%d],r[%d]n", op1, op2);

            if (read_reg(&v2, cpu, op2))
                return 1;
            if (write_reg(cpu, op1, v2))
                return 1;
            printf("twrote %x to r[%d]n", v2, op1);

            ip_inc = 2;
            break;
        case 0x2:
            /* movm r1, [ds:r2] */
            printf("movm r[%d], [ds:r[%d]]n", op1, op2 );

            if (read_reg(&v2, cpu, op2))
                return 1;

            addr = (cpu->ds * 16) + v2;
            while (addr > MEM_LEN)
            {
                printf("toutside of memoryn");
                return 1;
            }
            tmp = mem[addr];

            if (write_reg(cpu, op1, tmp))
                return 1;

            printf("tfrom addr: 0x%x got val: 0x%xn", addr, tmp);

            ip_inc = 2;
            break;
        case 0x3:
            /* add r1,r2 */
            printf("add r[%d], r[%d]n", op1, op2);

            if (read_reg(&v1, cpu, op1))
                return 1;

            if (read_reg(&v2, cpu, op2))
                return 1;

            tmp = v1 + v2;

            if (write_reg(cpu, op1, tmp))
                return 1;

            printf("t 0x%x + 0x%x = 0x%x n", v1, v2, tmp);

            ip_inc = 2;
            break;
        case 0x4:
            /* xor r1,r2 */
            printf("xor r[%d], r[%d]n", op1, op2);

            if (read_reg(&v1, cpu, op1))
                return 1;

            if (read_reg(&v2, cpu, op2))
                return 1;

            tmp = v1 ^ v2;

            if (write_reg(cpu, op1, tmp))
                return 1;

            printf("t 0x%x ^ 0x%x = 0x%x n", v1, v2, tmp);
            ip_inc = 2;
            break;
        case 0x5:
            /* cmp r1, r2 */
            printf("cmp r[%d], r[%d]n", op1, op2);
            if (read_reg(&v1, cpu, op1))
                return 1;

            if (read_reg(&v2, cpu, op2))
                return 1;

            if (v1 == v2)
                cpu->fl = 0;
            else if (v1 < v2)
                cpu->fl = 0xff;
            else if (v1 > v2)
                cpu->fl = 0x1;

            printf("tv1 = %d, v2 = %d, fl is now 0x%xn", v1, v2, cpu->fl);

            ip_inc = 2;
            break;
        case 0x6:
            /* jmpe r1 */
            printf("jmpe r[%d]n", op1);
            if (cpu->fl == 0)
            {
                if (read_reg(&v1, cpu, op1))
                    return 1;

                cpu->ip = (cpu->cs*16) + v1;
                printf("tjump to %dn", cpu->ip);

                ip_inc = 0; // jump, no increment
            }
            else
            {
                printf("tNOPn");
                ip_inc = 1; // jump, nop
            }

            break;
        case 0x7:
            /* halt */
            printf("haltn");
            return 1;
        default:
            return 1;
        }
    }
    else if (mod == 1)
    {
        switch (opcode)
        {
        case 0x0:
            /* jmp r2:r1 */
            printf("jmp %d:r[%d]n", op2, op1);

            if (read_reg(&v1, cpu, op1))
                return 1;

            tmp = (op2*16) + v1;

            cpu->cs = op2;
            cpu->ip = tmp;

            printf("tjump to %dn", cpu->ip);

            ip_inc = 0;
            break;
        case 0x1:
            /* movr rx, imm */
            printf("movr r[%d], 0x%xn", op1, op2);

            if (write_reg(cpu, op1, op2))
                return 1;

            printf("twrote 0x%x to r[%d]n", op2, op1);

            ip_inc = 2;
            break;
        case 0x2:
            /* movm [ds:rs], r2 */
            printf("movm [ds:r[%d]], r[%d]n", op1, op2);

            if (read_reg(&v1, cpu, op1))
                return 1;
            if (read_reg(&v2, cpu, op2))
                return 1;

            addr = (cpu->ds * 16) + v1;

            while (addr > MEM_LEN)
            {
                printf("toutside of memoryn");
                return 1;
            }

            mem[addr] = v2;

            printf("twrote 0x%x to mem[%d]n", v2, addr);

            ip_inc = 2;
            break;
        case 0x3:
            /* add r1, imm */
            printf("add r[%d], 0x%xn", op1, op2);

            if (read_reg(&v1, cpu, op1))
                return 1;

            tmp = v1 + op2;

            if (write_reg(cpu, op1, tmp))
                return 1;

            printf("t 0x%x + 0x%x = 0x%x n", v1, op2, tmp);

            ip_inc = 2;
            break;
        case 0x4:
            /* xor r1, imm */
            printf("xor r[%d], 0x%xn", op1, op2);

            if (read_reg(&v1, cpu, op1))
                return 1;

            tmp = v1 ^ op2;

            if (write_reg(cpu, op1, tmp))
                return 1;

            printf("t 0x%x ^ 0x%x = 0x%x n", v1, op2, tmp);

            ip_inc = 2;
            break;
        case 0x5:
            /* cmp r1, imm */
            printf("cmp r[%d], 0x%xn",op1, op2);

            if (read_reg(&v1, cpu, op1))
                return 1;

            if (v1 == op2)
                cpu->fl = 0;
            else if (v1 < op2)
                cpu->fl = 0xff;
            else if (v1 > op2)
                cpu->fl = 0x1;

            printf("tv1 = %d, op2 = %d, fl is now 0x%xn", v1, op2, cpu->fl);

            ip_inc = 2;
            break;
        case 0x6:
            /* jmpe r2:r1 */
            printf("jmpe 0x%x:r[%d]n",op2, op1);
            if (cpu->fl == 0)
            {
                if (read_reg(&v1, cpu, op1))
                    return 1;

                cpu->cs = op2;
                cpu->ip = (op2 * 16) + v1;
                printf("tjump to %dn", cpu->ip);

                ip_inc = 0; // jump, no increment
            }
            else
            {
                printf("tNOPn");
                ip_inc = 2; // jump, nop
            }
            break;
        case 0x7:
            /* halt */
            printf("haltn");
            return 1;
        default:
            return 1;
        }
    } else return 1;

    cpu->ip += ip_inc;
    return 0;
}

int main (void)
{
    unsigned char instr_buf[2] = {0,0};
    int i;

    s_cpu_state cpu;

    /* initialise CPU state */
    cpu.ip = 0x0;

    cpu.r[0] = 0x00;
    cpu.r[1] = 0x00;
    cpu.r[2] = 0x00;
    cpu.r[3] = 0x00;

    cpu.cs = 0;
    cpu.ds = 0x10;

    cpu.fl = 0;

    signal(SIGINT, siginthandler);

    while (cpu.ip+1 < MEM_LEN  && stop_cpu == 0)
    {
        instr_buf[0] = mem[cpu.ip];
        instr_buf[1] = mem[cpu.ip+1];

        printf("@ 0x%x -> ", cpu.ip);
        if (decode_instruction( instr_buf, &cpu ))
        {
            printf("error! Dumping...n");
            dump_cpu( cpu );

            exit(1);
        }
        printf("n");

    }

    if (stop_cpu)
    {
        printf("Interrupted... dumping - n");
        dump_cpu(cpu);
        exit(0);
    }

    printf("left the bounds of memory!!n");
    exit(0);

    return 0;
}
This entry was posted in Howto, Misc. and tagged , , , , , , , , . Bookmark the permalink.

6 Responses to Can you crack it? Stage 2 Solution

  1. Andrew says:

    I did my own (Java) implementation of the algorithm and, after running, the memory contained an instruction to fetch a .exe file – which in turn relies on cygwin being installed to run. Did you have the same experience?

  2. The Silly Scientist says:

    Yes that is the correct solution – it’s the next stage in the challenge.

    I’ll write up how I solved that shortly…

  3. Mark m says:

    I did the same. It’s a very interesting challenge. I’ve also done stage 3, but I’ve got a question about the vm. It seems to be that there is quite a lot of the data in mem that is unused? Did you find a use for it or is it just noise? Is there a second message? What about the two instructions after the second block of code? What about the cc ? Am I just too curious?

    • The Silly Scientist says:

      @Mark m –
      Yes, it’s a bit of a mystery that – the program never writes past memory address 498, I tried setting an entry point to 512 (the third ‘section’ as laid out in the js file), but it is an invalid instruction – so who knows. Possibly a decoy- I wonder if they will post any ‘official’ solutions after the deadline they have runs out.

  4. Pingback: Spy Agencies Turn to the Web In Search For Codebreakers » OWNI.eu, News, Augmented

  5. Pingback: JamesBondAuction.co.uk – James Bond 007 » Archive » Hiring James Bond 00.7 … ‘illegal’ hackers need not apply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.