2020KCTF KeyMe设计说明和破解思路

Author： iyzyi
发布时间：January 10, 2021
1536views
No comments
7221字数
Categories： REVERSE

（数学学的太差了，没控制好多解问题，这锅我背了，呜呜呜呜~）

看雪的神仙师傅太多了，菜鸡自认为做不出题来，所以只能转向防守方出个题了。

之前提交题目的时候正好碰上考试，设计说明写得有些简略，我再补充一下吧。

设计说明

用户名长度1~254，注册码长度448，注册码字符集为0-9a-f

将user取md5后，前8字节、后8字节分别再次md5，分别作为第一、二部分进行验证。

由于验证逻辑是f'(serial) == user，所以md5碰撞并不会导致多解（理论上存在多个user对于同一个serial的可能，但是不会存在一个user对于多个serial的情况）

将serial从hex字符串转换成byte数组，长度224，前32字节作为第一部分验证的输入，后192字节作为第二部分验证的输入。

然后分两部分进行验证。

1.1 qixi-vm

一个超小的vm。

涉及的小算法我之前在看雪发过：https://bbs.pediy.com/thread-261646.htm。在上文的基础上多加了一个&运算。这个小算法没多大难度，但是编译出来的汇编指令是很臃肿的，嵌套了15层的话，指令大概有几十万条。指令膨胀的特性用来配合vm真的是再合适不过了。

编译后只涉及了六种汇编指令，mov, shr, shl, and, xor, add，所以我把这六种指令设计成了一个小vm，太低级了，甚至可能都不配被称之为vm。

指令格式如下：

uint16_t xor_data[] = {0x0123, 0x4567, 0x89ab, 0xcdef, 0x0f1e, 0x2d3c, 0x4b5a, 0x6978};
int pointer = 0;
uint32_t reg[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

struct VmCmd{
    uint32_t and_param;        //&运算的参数
    uint8_t rubbish_size;    //垃圾指令大小 
    uint8_t xor_index;         //异或的索引
    uint8_t reg_byte;        //(dst<<4) + src
    uint8_t dst;            //目的操作数 
    uint8_t src;            //源操作数 
    uint8_t op_byte;        //六种指令 
    uint8_t other_op_param; //其他运算的参数
};

uint32_t encrypt_vm(uint32_t plain){
    
    reg[15] = plain;         // [ebp+plain]
    
    while(pointer < (sizeof(vm_data) / sizeof(vm_data[0]))) {
        VmCmd vcmd;
        vcmd.and_param = *(uint32_t*)(vm_data + pointer);
        vcmd.rubbish_size = (((vcmd.and_param >> 16) & 1) << 1) + ((vcmd.and_param >> 7) & 1);
        vcmd.xor_index = (((vcmd.and_param >> 27) & 1) << 2) + (((vcmd.and_param >> 19) & 1) << 1) + ((vcmd.and_param >> 8) & 1);
        vcmd.reg_byte = *(vm_data + pointer + 4) ^ ((xor_data[vcmd.xor_index] >> 8) & 0xff);
        vcmd.dst = (vcmd.reg_byte >> 4) & 0xf;
        vcmd.src = (vcmd.reg_byte) & 0xf;
        vcmd.op_byte = *(vm_data + pointer + 4 + 1 + vcmd.rubbish_size) ^ (xor_data[vcmd.xor_index] & 0xff);
        vcmd.other_op_param = *(vm_data + pointer + 4 + 1 + vcmd.rubbish_size + 1);
        uint16_t new_data = ((*(vm_data + pointer + 4)) << 8) + (*(vm_data + pointer + 4 + 1 + vcmd.rubbish_size));
        for (int i = 0; i < 7; i++){
            xor_data[i] = xor_data[i+1];
        }
        xor_data[7] = new_data;
        pointer += 4 + 1 + vcmd.rubbish_size + 1 + 1;

        if (vcmd.op_byte & 64){                //and
            reg[vcmd.dst] &= vcmd.and_param;
        } else if (vcmd.op_byte & 32){        //shr
            reg[vcmd.dst] >>= vcmd.other_op_param;
        } else if (vcmd.op_byte & 16){        //shl
            reg[vcmd.dst] <<= vcmd.other_op_param;
        } else if (vcmd.op_byte & 8){        //xor
            reg[vcmd.dst] ^= reg[vcmd.src];
        } else if (vcmd.op_byte & 4){        //mov
            reg[vcmd.dst] = reg[vcmd.src];
        } else if (vcmd.op_byte & 2){        //add
            reg[vcmd.dst] += reg[vcmd.src];
        }
    }
    
    return reg[14];        //eax
}

由于vm指令的设计问题，只适用于所涉及的变量不多于16个的汇编代码。因为源操作数和目标操作数分别只有4个bit来标识。

一个字段可能会有多个含义。比如and_param既可以是&运算的参数，又可以从中提取两个bit表示填充的垃圾指令的长度。

为了增加（一点点）难度，我还把vm的字节码改了4个字节。vm_data中的第1122145处开始的4个byte数据应该175 179 150 244 ，为了迷惑师傅们，我改成了111 112 113 114，然后使用TLS回调改回正确的字节码0xf496b3af。这个数据是最后一个&运算的参数。而且由于字节码是实时异或更新的，所以此后的十几条指令都是错的。

1.2 aes256_shellcode

上一步的输出转为这一步的输入。

这一步是调用了微软的crypto api，算法是aes256 cbc， iv=0000000000000000，key是sha256(1_L0V3_BXS_F0REVER!)

看起来简单，但我是写了个shellcode的，调用比较隐蔽。当然这肯定难不倒师傅们，动调一下就知道了。

动态获取kernel32.dll的基址，通过比较hash获取LoadLibraryA的地址，导入advapi32.dll，然后继续通过比较hash获取CryptAcquireContextA，CryptCreateHash，CryptHashData，CryptDeriveKey，CryptEncrypt的地址，分别push参数后调用。

1.3 32Byte转换成16Byte

for (int i = 0; i < 16; i++) {
    if ((uint8_t)(step1_2[i * 2] + 0x7f) != step1_2[i * 2 + 1]) {
        return false;
}
    step1_1[i] = step1_2[2 * i];
}

1.4 魔改aes

然后再走一波aes 256 ecb，key是Wo YongYuan XiHuan KanXun LunTan。不过这次是魔改的aes。

（才发现KanXun拼错了。。。题目都提交了，改的话太麻烦了，所以就先这样吧）

原版aes的使用的不可约多项式是283，我改成了299。

具体的魔改原理，师傅们可以参考

https://blog.csdn.net/u011516178/article/details/81221646。

为了欺骗师傅们使用的识别加密算法的插件，我还特意保留了原版的s盒和逆s盒。

2.1 码分复用解码

上学期准备计网结课考试的时候，就觉得这个算法放到逆向里，绝对很有意思。

这个算法本质上来说，其实就是n维空间向量的合成与分解。

单独的算法demo在这：码分复用DEMO - 狗剩DDoG (iyzyi.com)。本题结束前该文不公开。

每次传输的值为-4, -2, 0, -2, 4，共五种不同数值，原来想加个哈夫曼之类的压缩一下数据，但是实在没时间继续改了，所以简单地使用3bit来表示，有浪费的bit位。第二部分的serial的长达192Byte的罪魁祸首就在这儿。

192Byte -> 32Byte

2.2 模意义下的高斯消元

这个算法用于解多元单模线性方程组。我这里选用的模数是65423。

注册机是将16Byte的数据，分别乘以一个系数（由key数组生成）后求和取模，进行16次，16B的数据生成32B的结果，共32Byte。多次计算，构成单模多元线性方程组。

void multiplyUnderModule(uint8_t* step2_1, uint8_t* step2_2) {
    uint8_t key[] = { 233, 136, 189, 132, 157, 100, 196, 185, 138, 222, 90, 101, 115, 229, 161, 97 };
    for (int i = 0; i < 16; i++) {
        int temp = 0;
        for (int j = 0; j < 16; j++)
        {
            temp = (temp * key[i] + step2_1[j]) % 65423;
        }
        step2_2[i * 2] = temp & 0xff;
        step2_2[i * 2 + 1] = (temp >> 8) & 0xff;
    }
}

验证的时候就是用模意义下的高斯消元求出原来的那16个1B的数据。

好像和第三题重返地球考察的知识点有点冲突了。不过问题不大，因为这个算法是写在验证机里的，写注册机的时候可以把这个算法直接提取出来用。不是考察的重点。

2.3 利用md5进行check

这个思路来自《加密与解密》第四版的645页。

超级有意思的一个思路，师傅们可以去读下。

具体的可以看KEYGEN脚本。

最后输出16B，与user的md5的后8字节的md5进行验证

攻击思路

首先去下花指令。花指令的数量不少，手动去花不太现实。不过好在种类不多，一共也就十种左右吧。发现一次后就可以写个脚本批量去一下。

然后过反调试。反调试菜鸡我接触不多，所以本题的反调试只是聊胜于无罢了。而且我故意让反调试清一色地调用exit()（其实是交题时间截止在即，没时间继续改了，逃），所以只需要找到一处反调试，就可以查看交叉引用，直接找到所有的反调试。由于出题人水平受限，本题的反调试没多大意思。

最后一步就是逆向了。大多数都是算法求逆，考验算法功底。这里捡几个关键的点来说。

vm

拿到指令流的方式有两种。

一种是去掉花指令和反调试后把相关的代码提取出来，用它来处理一下字节码，即可拿到指令流。不过前面我也说了，字节码最后修改了4个错误的数据，由于异或操作，最后的大概十几条指令是错误的。需要发现tls回调修改的正确的数据，手动改一下字节码中的错误数据，然后再跑脚本。

另一种就是pin插桩。推荐这个方式。完美绕过我设置的tls回调的坑。

处理字节码得到伪代码后，读开头的几百行，应该能反应过来其实是一个嵌套的格式（吧）。

然后到伪代码最后的几百行提取所涉及的参数就行。如下：

1121766: mov $14, $15
1121774: shl $14, 0x12
1121781: and $14, 0xac7d9cc9
1121791: xor $14, $15
1121800: shl $14, 0x6
1121808: and $14, 0x570293d5
1121816: xor $14, $13
1121826: shl $14, 0x11
1121834: and $14, 0xdfce7fe6
1121842: xor $14, $12
1121852: shr $14, 0x1
1121861: and $14, 0x73f2ef73
1121868: xor $14, $11
1121878: shr $14, 0x8
1121888: and $14, 0x3db7a3b4
1121898: xor $14, $10
1121907: shr $14, 0xe
1121915: and $14, 0x5256d19e
1121923: xor $14, $9
1121931: shr $14, 0x17
1121940: and $14, 0x7c058e5d
1121949: xor $14, $0
1121957: shr $14, 0x16
1121966: and $14, 0xe8706ccd
1121974: xor $14, $2
1121982: shl $14, 0x6
1121992: and $14, 0xb80040bd
1122000: xor $14, $4
1122007: add $14, $14
1122015: and $14, 0xcabbf58c
1122025: xor $14, $6
1122033: shl $14, 0x1a
1122040: and $14, 0xa6e6880e
1122047: xor $14, $8
1122055: shl $14, 0xf
1122063: and $14, 0x2082faef
1122071: xor $14, $7
1122079: shl $14, 0x3
1122089: and $14, 0xa58b9ca0
1122099: xor $14, $5
1122108: shl $14, 0xd
1122118: and $14, 0x1797d5d5
1122128: xor $14, $3
1122135: shr $14, 0xf
1122145: and $14, 0xf496b3af
1122153: xor $14, $1

这个vm难度不大，比较低级的水平。（可能的）难点在于嵌套格式的识别。

一个坑点在于最后一个&的参数被改过了，（或许）需要发现TLS回调的那个函数。

字节码的臃肿不知道会不会对师傅们造成一点点小麻烦。不知道师傅们有没有什么优雅的处理方式。菜鸡我等师傅们的wp出来后学习一波。

aes256_shellcode

两种方法：

有写过shellcode经验的师傅，可以直接把汇编扣出来，改下hash，使得CryptEncrypt函数改成CryptDecrypt，就能跑，注意CryptEncrypt比CryptDecrypt多个参数，需要删掉最后一个参数。

或者有写过微软crypto api经验的可以直接知道是aes256 cbc， iv=0000000000000000，密钥被sha256了。（可以去msdn上查。但是好像查不到是cbc。我出题的时候试了一下，才发现其实是cbc）

魔改aes

关于不可约多项式生成s盒和逆s盒，可以参考

https://blog.csdn.net/u011516178/article/details/812216461

一个思路是动调拿到真正的s盒，然后去生成逆s盒。

模意义下的高斯消元

由于使用了利用md5进行check（见下一步），所以整个第二部分的验证函数都需要提取出来，用于从一组已知的注册码中求解出H数组(key)。

正向的算法很复杂，但是直接导出就能用。

逆向的算法就是一个用key加密flag，先乘后加然后取模，一共进行16次，组成单模多元线性方程组，输出等式右侧的计算结果。

不过，由验证机里的正向算法推出注册机的逆向算法可能会有些难度。

利用md5进行check

需要先用已知的一组注册码求出攻击脚本中的H数组，这一过程需要导出整个第二部分的正向算法。

有了H数组后，就可以逆向写出求解注册码的逻辑。

Last modification：January 10th, 2021 at 02:37 am

2020KCTF KeyMe设计说明和破解思路

iyzyi • 2021 年 01 月 10 日

（数学学的太差了，没控制好多解问题，这锅我背了，呜呜呜呜~）

看雪的神仙师傅太多了，菜鸡自认为做不出题来，所以只能转向防守方出个题了。

之前提交题目的时候正好碰上考试，设计说明写得有些简略，我再补充一下吧。

设计说明

用户名长度1~254，注册码长度448，注册码字符集为0-9a-f

将user取md5后，前8字节、后8字节分别再次md5，分别作为第一、二部分进行验证。

由于验证逻辑是f'(serial) == user，所以md5碰撞并不会导致多解（理论上存在多个user对于同一个serial的可能，但是不会存在一个user对于多个serial的情况）

将serial从hex字符串转换成byte数组，长度224，前32字节作为第一部分验证的输入，后192字节作为第二部分验证的输入。

然后分两部分进行验证。

1.1 qixi-vm

一个超小的vm。

编译后只涉及了六种汇编指令，mov, shr, shl, and, xor, add，所以我把这六种指令设计成了一个小vm，太低级了，甚至可能都不配被称之为vm。

指令格式如下：

uint16_t xor_data[] = {0x0123, 0x4567, 0x89ab, 0xcdef, 0x0f1e, 0x2d3c, 0x4b5a, 0x6978};
int pointer = 0;
uint32_t reg[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

struct VmCmd{
    uint32_t and_param;        //&运算的参数
    uint8_t rubbish_size;    //垃圾指令大小 
    uint8_t xor_index;         //异或的索引
    uint8_t reg_byte;        //(dst<<4) + src
    uint8_t dst;            //目的操作数 
    uint8_t src;            //源操作数 
    uint8_t op_byte;        //六种指令 
    uint8_t other_op_param; //其他运算的参数
};

uint32_t encrypt_vm(uint32_t plain){
    
    reg[15] = plain;         // [ebp+plain]
    
    while(pointer < (sizeof(vm_data) / sizeof(vm_data[0]))) {
        VmCmd vcmd;
        vcmd.and_param = *(uint32_t*)(vm_data + pointer);
        vcmd.rubbish_size = (((vcmd.and_param >> 16) & 1) << 1) + ((vcmd.and_param >> 7) & 1);
        vcmd.xor_index = (((vcmd.and_param >> 27) & 1) << 2) + (((vcmd.and_param >> 19) & 1) << 1) + ((vcmd.and_param >> 8) & 1);
        vcmd.reg_byte = *(vm_data + pointer + 4) ^ ((xor_data[vcmd.xor_index] >> 8) & 0xff);
        vcmd.dst = (vcmd.reg_byte >> 4) & 0xf;
        vcmd.src = (vcmd.reg_byte) & 0xf;
        vcmd.op_byte = *(vm_data + pointer + 4 + 1 + vcmd.rubbish_size) ^ (xor_data[vcmd.xor_index] & 0xff);
        vcmd.other_op_param = *(vm_data + pointer + 4 + 1 + vcmd.rubbish_size + 1);
        uint16_t new_data = ((*(vm_data + pointer + 4)) << 8) + (*(vm_data + pointer + 4 + 1 + vcmd.rubbish_size));
        for (int i = 0; i < 7; i++){
            xor_data[i] = xor_data[i+1];
        }
        xor_data[7] = new_data;
        pointer += 4 + 1 + vcmd.rubbish_size + 1 + 1;

        if (vcmd.op_byte & 64){                //and
            reg[vcmd.dst] &= vcmd.and_param;
        } else if (vcmd.op_byte & 32){        //shr
            reg[vcmd.dst] >>= vcmd.other_op_param;
        } else if (vcmd.op_byte & 16){        //shl
            reg[vcmd.dst] <<= vcmd.other_op_param;
        } else if (vcmd.op_byte & 8){        //xor
            reg[vcmd.dst] ^= reg[vcmd.src];
        } else if (vcmd.op_byte & 4){        //mov
            reg[vcmd.dst] = reg[vcmd.src];
        } else if (vcmd.op_byte & 2){        //add
            reg[vcmd.dst] += reg[vcmd.src];
        }
    }
    
    return reg[14];        //eax
}

由于vm指令的设计问题，只适用于所涉及的变量不多于16个的汇编代码。因为源操作数和目标操作数分别只有4个bit来标识。

一个字段可能会有多个含义。比如and_param既可以是&运算的参数，又可以从中提取两个bit表示填充的垃圾指令的长度。

1.2 aes256_shellcode

上一步的输出转为这一步的输入。

这一步是调用了微软的crypto api，算法是aes256 cbc， iv=0000000000000000，key是sha256(1_L0V3_BXS_F0REVER!)

看起来简单，但我是写了个shellcode的，调用比较隐蔽。当然这肯定难不倒师傅们，动调一下就知道了。

1.3 32Byte转换成16Byte

for (int i = 0; i < 16; i++) {
    if ((uint8_t)(step1_2[i * 2] + 0x7f) != step1_2[i * 2 + 1]) {
        return false;
}
    step1_1[i] = step1_2[2 * i];
}

1.4 魔改aes

然后再走一波aes 256 ecb，key是Wo YongYuan XiHuan KanXun LunTan。不过这次是魔改的aes。

（才发现KanXun拼错了。。。题目都提交了，改的话太麻烦了，所以就先这样吧）

原版aes的使用的不可约多项式是283，我改成了299。

具体的魔改原理，师傅们可以参考

https://blog.csdn.net/u011516178/article/details/81221646。

为了欺骗师傅们使用的识别加密算法的插件，我还特意保留了原版的s盒和逆s盒。

2.1 码分复用解码

上学期准备计网结课考试的时候，就觉得这个算法放到逆向里，绝对很有意思。

这个算法本质上来说，其实就是n维空间向量的合成与分解。

单独的算法demo在这：码分复用DEMO - 狗剩DDoG (iyzyi.com)。本题结束前该文不公开。

192Byte -> 32Byte

2.2 模意义下的高斯消元

这个算法用于解多元单模线性方程组。我这里选用的模数是65423。

void multiplyUnderModule(uint8_t* step2_1, uint8_t* step2_2) {
    uint8_t key[] = { 233, 136, 189, 132, 157, 100, 196, 185, 138, 222, 90, 101, 115, 229, 161, 97 };
    for (int i = 0; i < 16; i++) {
        int temp = 0;
        for (int j = 0; j < 16; j++)
        {
            temp = (temp * key[i] + step2_1[j]) % 65423;
        }
        step2_2[i * 2] = temp & 0xff;
        step2_2[i * 2 + 1] = (temp >> 8) & 0xff;
    }
}

验证的时候就是用模意义下的高斯消元求出原来的那16个1B的数据。

2.3 利用md5进行check

这个思路来自《加密与解密》第四版的645页。

超级有意思的一个思路，师傅们可以去读下。

具体的可以看KEYGEN脚本。

最后输出16B，与user的md5的后8字节的md5进行验证

攻击思路

首先去下花指令。花指令的数量不少，手动去花不太现实。不过好在种类不多，一共也就十种左右吧。发现一次后就可以写个脚本批量去一下。

最后一步就是逆向了。大多数都是算法求逆，考验算法功底。这里捡几个关键的点来说。

vm

拿到指令流的方式有两种。

另一种就是pin插桩。推荐这个方式。完美绕过我设置的tls回调的坑。

处理字节码得到伪代码后，读开头的几百行，应该能反应过来其实是一个嵌套的格式（吧）。

然后到伪代码最后的几百行提取所涉及的参数就行。如下：

1121766: mov $14, $15
1121774: shl $14, 0x12
1121781: and $14, 0xac7d9cc9
1121791: xor $14, $15
1121800: shl $14, 0x6
1121808: and $14, 0x570293d5
1121816: xor $14, $13
1121826: shl $14, 0x11
1121834: and $14, 0xdfce7fe6
1121842: xor $14, $12
1121852: shr $14, 0x1
1121861: and $14, 0x73f2ef73
1121868: xor $14, $11
1121878: shr $14, 0x8
1121888: and $14, 0x3db7a3b4
1121898: xor $14, $10
1121907: shr $14, 0xe
1121915: and $14, 0x5256d19e
1121923: xor $14, $9
1121931: shr $14, 0x17
1121940: and $14, 0x7c058e5d
1121949: xor $14, $0
1121957: shr $14, 0x16
1121966: and $14, 0xe8706ccd
1121974: xor $14, $2
1121982: shl $14, 0x6
1121992: and $14, 0xb80040bd
1122000: xor $14, $4
1122007: add $14, $14
1122015: and $14, 0xcabbf58c
1122025: xor $14, $6
1122033: shl $14, 0x1a
1122040: and $14, 0xa6e6880e
1122047: xor $14, $8
1122055: shl $14, 0xf
1122063: and $14, 0x2082faef
1122071: xor $14, $7
1122079: shl $14, 0x3
1122089: and $14, 0xa58b9ca0
1122099: xor $14, $5
1122108: shl $14, 0xd
1122118: and $14, 0x1797d5d5
1122128: xor $14, $3
1122135: shr $14, 0xf
1122145: and $14, 0xf496b3af
1122153: xor $14, $1

这个vm难度不大，比较低级的水平。（可能的）难点在于嵌套格式的识别。

一个坑点在于最后一个&的参数被改过了，（或许）需要发现TLS回调的那个函数。

字节码的臃肿不知道会不会对师傅们造成一点点小麻烦。不知道师傅们有没有什么优雅的处理方式。菜鸡我等师傅们的wp出来后学习一波。

aes256_shellcode

两种方法：

魔改aes

关于不可约多项式生成s盒和逆s盒，可以参考

https://blog.csdn.net/u011516178/article/details/812216461

一个思路是动调拿到真正的s盒，然后去生成逆s盒。

模意义下的高斯消元

由于使用了利用md5进行check（见下一步），所以整个第二部分的验证函数都需要提取出来，用于从一组已知的注册码中求解出H数组(key)。

正向的算法很复杂，但是直接导出就能用。

逆向的算法就是一个用key加密flag，先乘后加然后取模，一共进行16次，组成单模多元线性方程组，输出等式右侧的计算结果。

不过，由验证机里的正向算法推出注册机的逆向算法可能会有些难度。

利用md5进行check

需要先用已知的一组注册码求出攻击脚本中的H数组，这一过程需要导出整个第二部分的正向算法。

有了H数组后，就可以逆向写出求解注册码的逻辑。

设计说明

1.1 qixi-vm

1.2 aes256_shellcode

1.3 32Byte转换成16Byte

1.4 魔改aes

2.1 码分复用解码

2.2 模意义下的高斯消元

2.3 利用md5进行check

攻击思路

vm

aes256_shellcode

魔改aes

模意义下的高斯消元

利用md5进行check