狗儿

热爱的话就坚持吧~

0%

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

(数学学的太差了,没控制好多解问题,这锅我背了,呜呜呜呜~)

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

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

设计说明

用户名长度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。

指令格式如下:

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
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

1
2
3
4
5
6
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。多次计算,构成单模多元线性方程组。

1
2
3
4
5
6
7
8
9
10
11
12
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回调的坑。

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

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

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
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数组后,就可以逆向写出求解注册码的逻辑。