L3HCTF re double-joy 题解

基于栈的 VM 题，单纯从指令来讲并不难，只需要简单的解析一下即可分析出进行的运算，但是运算上的一些小细节加大了本题的难度。

Analysis

main 函数没有太多的内容，主要是获取输入之后传入 vm 进行运算

运算出来的结果和正确的进行逐字节的对比

进入 vm ，程序根据指令调用不同的函数，共 19 种不同的函数

根据汇编和调试很容易看出来每一个函数的作用，可以写一个简单的 python 脚本用来分析

while i < len(opcodes):
    if opcodes[i] == 0:
        print(hex(i)[2:].rjust(3, '0'), "inplace_add")
        i += 1
    elif opcodes[i] == 1:
        print(hex(i)[2:].rjust(3, '0'), "inplace_sub")
        i += 1
    elif opcodes[i] == 2:
        print(hex(i)[2:].rjust(3, '0'), "inplace_mul")
        i += 1
    elif opcodes[i] == 3:
        print(hex(i)[2:].rjust(3, '0'), "inplace_div")
        i += 1
    elif opcodes[i] == 4:
        print(hex(i)[2:].rjust(3, '0'), "inplace_mod")
        i += 1
    elif opcodes[i] == 5:
        print(hex(i)[2:].rjust(3, '0'), "inplace_and")
        i += 1
    elif opcodes[i] == 6:
        print(hex(i)[2:].rjust(3, '0'), "inplace_or")
        i += 1
    elif opcodes[i] == 7:
        print(hex(i)[2:].rjust(3, '0'), "inplace_xor")
        i += 1
    elif opcodes[i] == 8:
        print(hex(i)[2:].rjust(3, '0'), "stack[TOS1]=TOS")
        i += 1
    elif opcodes[i] == 9:
        print(hex(i)[2:].rjust(3, '0'), "TOS=stack[TOS]")
        i += 1
    elif opcodes[i] == 0xA:
        print(hex(i)[2:].rjust(3, '0'), "if TOS==0: TOS=1 else: TOS=0")
        i += 1
    elif opcodes[i] == 0xB:
        print(hex(i)[2:].rjust(3, '0'), "if TOS<0: TOS=1 else: TOS=0")
        i += 1
    elif opcodes[i] == 0xC:
        print(hex(i)[2:].rjust(3, '0'), "Inplace_swap")
        i += 1
    elif opcodes[i] == 0xD:
        print(hex(i)[2:].rjust(3, '0'), "remove_top")
        i += 1
    elif opcodes[i] == 0xE:
        tmp = (opcodes[i+1] | (opcodes[i+2] << 8) | opcodes[i+3]
               << 16 | opcodes[i+4] << 24) & 0xffffffff
        print(hex(i)[2:].rjust(3, '0'), f"push {hex(tmp)}")
        i += 5
    elif opcodes[i] == 0xF:
        tmp = (opcodes[i+1] | (opcodes[i+2] << 8) | opcodes[i+3]
               << 16 | opcodes[i+4] << 24) & 0xffffffff
        print(hex(i)[2:].rjust(3, '0'), f"jmp {hex((tmp+i+5)&0xffffffff)}")
        i += 5
    elif opcodes[i] == 0x10:
        tmp = (opcodes[i+1] | (opcodes[i+2] << 8) | opcodes[i+3]
               << 16 | opcodes[i+4] << 24) & 0xffffffff
        print(hex(i)[2:].rjust(3, '0'), f"if TOS==1: jmp {hex(i+tmp+5)}")
        i += 5
    elif opcodes[i] == 0x11:
        tmp = (opcodes[i+1] | (opcodes[i+2] << 8) | opcodes[i+3]
               << 16 | opcodes[i+4] << 24) & 0xffffffff

        print(hex(i)[2:].rjust(3, '0'), f"sub rsp,{hex(tmp)}")
        i += 5
    elif opcodes[i] == 0x12:
        tmp = (opcodes[i+1] | (opcodes[i+2] << 8) | opcodes[i+3]
               << 16 | opcodes[i+4] << 24) & 0xffffffff
        print(hex(i)[2:].rjust(3, '0'), f"return {tmp}")
        i += 5

调试的时候可以发现传入该 vm 函数的并不仅仅是指令，而是一个结构体，结构体的定义如下

该 vm 是一个基于栈的 vm，所有的数据保存在栈上。调试中发现，该程序共传入了两套 vm 指令，做题时一开始以为只有一套指令，解不出结果之后才发现后续又运行了另一套指令。

为了更快做题，只是用上面写的脚本简单解析了一下这两套指令，对于虚拟机的题目，有一种处理方式是将每一个指令写成汇编指令集的形式，编译之后借助IDA等工具进行分析，好在这题的指令并不复杂，只要抓住特征很容易把算法还原出来。两套指令有相同的地方，但在运算和入栈的数据上有很大的区别。

可以很容易发现第一套指令在进行了异或操作之后，进行的是魔改版的 xtea 加密，有一个明显的特征在于进行了两次如下操作，左移 4 位，右移 5 位，异或并相加操作。

148 push 0x10
14d inplace_mul
14e push 0xd
153 TOS=stack[TOS]
154 push 0x20
159 Inplace_swap
15a inplace_div
15b inplace_xor
15c push 0xd
161 TOS=stack[TOS]
162 inplace_add

修改的地方在于 sum 的初值和 delta 不同，加密轮次也不同，秘钥、sum 和 delta 都在程序开始时入栈，很容易找。

第二套指令同样进行异或操作，但是后续进行的是魔改版的 tea 加密，特征同样也很明显，出现了两次移位，两次异或，多次相加

15a TOS=stack[TOS]
15b push 0x10
160 inplace_mul
161 push 0x0
166 push 0xe
16b inplace_add
16c TOS=stack[TOS]
16d inplace_add
16e push 0xd
173 TOS=stack[TOS]
174 push 0xb
179 TOS=stack[TOS]
17a inplace_add
17b push 0xd
180 TOS=stack[TOS]
181 push 0x20
186 Inplace_swap
187 inplace_div
188 push 0x1
18d push 0xe
192 inplace_add
193 TOS=stack[TOS]
194 inplace_add
195 inplace_xor
196 inplace_xor
197 inplace_add

sum、delta 和 key 都和第一套不同。

但是到这里题目还有很多坑没有填。

第一点就是，在一轮加密结束之后，程序会进行一次 return，与全部加密结束之后的返回值不同，返回之后程序会在 main 函数内进行下一次循环，运行另一套指令，因此两套加密是在一轮加密结束之后进行交换，轮流进行。

第二点就是，两套指令都在开头对每一个字进行了异或，都进行了一次，并且值相同（0x1010101-0xa0a0a0a），所以除了前两个字在异或之后立刻进行了一轮加密之外，后续的所有字都连续进行了两次相同的异或操作，并没有任何影响。

第三点就是与 xtea/tea 算法不同，该算法每一组字的 sum 并不重置，而是使用前一组字计算的结果继续进行，因此在解密的时候由最后一组向前进行并且将 sum 设置为全局变量是比较简单的方式。

第四点是原版 xtea/tea 基本上都是无符号数运算，但是这里的除法操作之前使用了 cdq 指令，用 EAX 的符号位填充了 EDX，很明显是一个有符号数操作。

第五点是原版 xtea/tea 使用的是右移运算，而这里用的是除法运算，这也就意味着在某些语言的处理中（比如 C），根据舍入规则的不同，有符号数的右移和除法运算的结果在最后一位上存在误差，多轮加密导致误差扩大并不断引入新的误差，因此应该使用除法的方式。

Solution

根据上述分析可以很容易复现加密的脚本和对应的解密脚本

#include <stdio.h>
#include <stdint.h>

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[8])
{
    unsigned int i;

    int32_t v0 = v[0], v1 = v[1];
    int32_t delta1 = 123456789, base1 = 987654321, sum1 = base1;
    int32_t delta2 = 0x154cbf7, base2 = 0x5eeddead, sum2 = base2;

    v0 ^= 0x1010101;
    v1 ^= 0x2020202;
    printf("%x %x\n", v0, v1);

    v0 += (((v1 << 4) ^ (v1 / 32)) + v1) ^ (sum1 + key[sum1 & 3]);
    sum1 += delta1;
    v1 += (((v0 << 4) ^ (v0 / 32)) + v0) ^ (sum1 + key[(sum1 / 0x800) & 3]);
    printf("%x %x\n", v0, v1);

    v0 ^= 0x1010101;
    v1 ^= 0x2020202;

    printf("%x %x\n", v0, v1);

    sum2 += delta2;
    v0 += ((v1 << 4) + key[4]) ^ (v1 + sum2) ^ ((v1 / 32) + key[5]);
    v1 += ((v0 << 4) + key[6]) ^ (v0 + sum2) ^ ((v0 / 32) + key[7]);
    printf("%x %x\n", v0, v1);

    for (i = 1; i < num_rounds; i++)
    {

        v0 += (((v1 << 4) ^ (v1 / 32)) + v1) ^ (sum1 + key[sum1 & 3]);
        sum1 += delta1;
        v1 += (((v0 << 4) ^ (v0 / 32)) + v0) ^ (sum1 + key[(sum1 / 0x800) & 3]);
        printf("%x %x\n", v0, v1);

        sum2 += delta2;
        v0 += ((v1 << 4) + key[4]) ^ (v1 + sum2) ^ ((v1 / 32) + key[5]);
        v1 += ((v0 << 4) + key[6]) ^ (v0 + sum2) ^ ((v0 / 32) + key[7]);
        printf("%x %x\n", v0, v1);
    }
    v[0] = v0;
    v[1] = v1;
}

int32_t delta1 = 123456789, base1 = 987654321, sum1 = delta1 * 0x14 * 5 + base1;
int32_t delta2 = 0x154cbf7, base2 = 0x5eeddead, sum2 = delta2 * 0x14 * 5 + base2;

void decipher(unsigned int num_rounds, uint32_t v[2], int32_t const key[8])
{
    unsigned int i;
    int32_t v0 = v[0], v1 = v[1];

    for (i = 1; i < num_rounds; i++)
    {
        v1 -= ((v0 << 4) + key[6]) ^ (v0 + sum2) ^ ((v0 / 32) + key[7]);
        v0 -= ((v1 << 4) + key[4]) ^ (v1 + sum2) ^ ((v1 / 32) + key[5]);
        sum2 -= delta2;

        v1 -= (((v0 << 4) ^ (v0 / 32)) + v0) ^ (sum1 + key[(sum1 / 0x800) & 3]);
        sum1 -= delta1;
        v0 -= (((v1 << 4) ^ (v1 / 32)) + v1) ^ (sum1 + key[sum1 & 3]);
    }

    v1 -= ((v0 << 4) + key[6]) ^ (v0 + sum2) ^ ((v0 / 32) + key[7]);
    v0 -= ((v1 << 4) + key[4]) ^ (v1 + sum2) ^ ((v1 / 32) + key[5]);
    sum2 -= delta2;

    v0 ^= 0x1010101;
    v1 ^= 0x2020202;

    v1 -= (((v0 << 4) ^ (v0 / 32)) + v0) ^ (sum1 + key[(sum1 / 0x800) & 3]);
    sum1 -= delta1;
    v0 -= (((v1 << 4) ^ (v1 / 32)) + v1) ^ (sum1 + key[sum1 & 3]);

    v0 ^= 0x1010101;
    v1 ^= 0x2020202;

    v[0] = v0;
    v[1] = v1;
}

void decipher2(unsigned int num_rounds, uint32_t v[2], int32_t const key[8])
{
    unsigned int i;
    int32_t v0 = v[0], v1 = v[1];
    for (i = 0; i < num_rounds; i++)
    {
        v1 -= ((v0 << 4) + key[6]) ^ (v0 + sum2) ^ ((v0 / 32) + key[7]);
        v0 -= ((v1 << 4) + key[4]) ^ (v1 + sum2) ^ ((v1 / 32) + key[5]);
        sum2 -= delta2;

        v1 -= (((v0 << 4) ^ (v0 / 32)) + v0) ^ (sum1 + key[(sum1 / 0x800) & 3]);
        sum1 -= delta1;
        v0 -= (((v1 << 4) ^ (v1 / 32)) + v1) ^ (sum1 + key[sum1 & 3]);
    }

    v[0] = v0;
    v[1] = v1;
}

int main()
{
    uint32_t v[10] = {
        0xAEE0FAE8, 0xFC3E4101, 0x167CAD92, 0x51EA6CBE, 0x242A0100, 0x01511A1B, 0x514D6694, 0x2F5FBFEB,
        0x46D36398, 0x79EEE3F0};
    int32_t const k[8] = {0x0000494C, 0x00006F76, 0x00006520, 0x00004355, 0x00005354, 0x00004F4D, 0x00002074, 0x00006561};
    unsigned int r = 0x14;
    for (int i = 8; i >= 2; i -= 2)
    {
        uint32_t tmp_v[] = {v[i], v[i + 1]};
        decipher2(r, tmp_v, k);
        v[i] = tmp_v[0];
        v[i + 1] = tmp_v[1];
    }

    decipher(r, v, k);
    for (auto i : v)
    {
        while (i != 0)
        {
            printf("%c", i & 0xff);
            i >>= 8;
        }
    }
    return 0;
}

Analysis

Solution

目录