-
-
[原创] KCTF 2023 第五题 wp - 98k
-
发表于: 2023-9-11 23:52 8482
-
程序主逻辑没多少，但是加入了大量无关代码，单个函数体积膨胀非常大，这对正常逻辑分析造成了一定阻碍，没办法直接阅读 ida 生成的代码。不过加入的这些逻辑与主要逻辑无关，只要找 F5 中的关键变量（从函数参数或函数返回值入手）的交叉引用，将所有相关的语句手动组合起来即可得到判断逻辑。
大致逻辑恢复如下（后面的注释是该语句在二进制程序中对应的地址）：
提取出来后发现有一些跟主变量相关的逻辑也是无效逻辑（如重复异或一个值两次），直接忽略这些即可。还有一个函数用于反调试（检测调试器是否存在），直接 patch 为 return 0 。
程序主要逻辑：
将输入 base64 解码；
检查解码后数据的后 4 个字节对应的数值是前面的数据的 CRC32 校验；
解析前面的数据，得到两块数据，其具体结构体形式如下：
验证两个 seed 的值，判断的形式是 unsigned __int64 运算中的 seed * y % z == 1 ；
将两块数据中的 data 以 seed 作为随机数种子解密；
验证两段解密后的 data 的值，判断的形式是 char[200] 表示的大数的运算 data * Y % Z == 1 。
4 和 6 中的运算的两组 (y, z) 和 (Y, Z) 都是直接给出来的，就只是个有限域求逆的问题。反向求解输入就行。
先把两组 seed 、解密后的 data 值求出来，再将两者组合得到加密的 data ，再重构结构体、组合得到数据并求 CRC32 附在其后，最后 base64 。
但是此题由于几个地方没完全限制正确导致出现多解。导致多解的原因：
结构体中数据的对其导致多出来 2 字节的填充，这两组 2 字节可以为任意值；可行的解决方案：结构体定义中定义按 1 字节对齐，或者将 length 设置为 int 类型；
大数的结构为 char[200] ，但是实际计算中的 Z 只有 74 字节，也就是解密后的 data 有效字节数为 74 ，那么可以在解密的 data 后添加 0~126 字节的 0 （即高位补 0 ，增加长度但是不改变数值。 126 是因为数据结构 char[200] 是堆上分配的，过长将覆盖后面的数据导致程序崩溃。实际测试最长可增加 129 字节的 0 ）；可行的解决方案：增加对 length 的判断，并且还需要增加一条限制 data < Z 避免出现 data + kZ 的情况；
解析上述第 3 步中的两个数据结构时判断两块数据的长度不大于而不是等于输入的长度，所以这部分输入后面可以有任意长的填充；可行的解决方案：改成等于；
base64 解析时遇到 '=' 直接停止，后面的数据可以为任意值；可行的解决方案：限制输入长度，对第一个 '=' 后面的数据进行有效性判断或者预期输入中直接去掉填充的 '=' 。
题目整体的判断逻辑设计得挺好的，就是逆向的时候看到限制条件太松一定会产生非常多解的，之前的两道逆向题弄出心理阴影了，我都担心最后会出现一个哈希判断。虽然现在还鞭尸不太好，不过还是想多说一下，逆向题里用哈希限制输入的唯一性完全没必要，题目设计时限制条件处理好就不会产生多解。当然也可能会在自己意想不到的地方出现多解，不过公布题解后出题人也能学到一些新的东西，以后的题目中把限制条件做得更精确，大家也可以开心做题。而明明知道限制条件不够强会导致多解的情况下，硬给题目加一个哈希判断就是在耍流氓，加的这个条件达到了出题人限制输入唯一的目的，但是这条件对做题方没有任何帮助，这就是把本来应该由出题人干的活强行塞给做题方来干。当然也不排除某些情况下题目限制条件虽然会导致多解但是没办法再加限制条件了，或者说再加任何条件都会导致题目难度大量下降，如果这时的解不多那就可以加上哈希的条件。当然，我的建议是题目中给出目标哈希值，但是只对其至多两个字节（即 4 个十六进制数值，碰撞概率 1/65536 ）做判断。这样能大概率达到限制解唯一的情况，并且对做题方也很友好。
最后给出逆向脚本以及两组多解：
#include <stdio.h>#include <stdlib.h>#include <string.h>int has_debugger() { // 0x402220
// patch
return 0;
// ...
}int check1(char* buf, size_t size) { // 0x455F80
unsigned int crc = CRC32(buf, size - 4); // 0x457690
return crc == *(unsigned int*) (buf + size - 4); // 0x457C13
}int check2(void* buf, size_t size, unsigned short** buf1, unsigned short** buf2) {
if (size >= 0x10) { // 0x45942B
*buf1 = buf; // 0x45AF4E
if ((*buf1)[2] && (*buf1)[2] <= size - 16) { // 0x45B836
*buf2 = (unsigned short *)((unsigned char*) buf + (*buf1)[2] + 8); // 0x45CA22
if ((*buf2)[2] && (*buf2)[2] <= size - 16 - (*buf1)[2]) { // 0x45D3A3
return 1;
} else {
*buf2 = NULL;
}
} else {
*buf1 = NULL;
}
}
return 0;
}int check_inverse(unsigned long long x, unsigned long long y, unsigned long long z) {
return x * y % z == 1;
}int check3(unsigned int x, unsigned int y) { // 0x474170
unsigned long long p = 0x346F8717, a = 32069; // 0x47546A
if (check_inverse(a, x, p)) { // 0x477A1C
p = 0x729969FF;
a = 55057; // 0x478965
if (check_inverse(a, y, p)) { // 0x47A972
return 1;
}
}
return 0;
}unsigned int* alloc_map(size_t n) { // 0x4D2250
return (unsigned int*) malloc(4 * n * n); // 0x4D34CD
}void set_value(unsigned int* map, size_t n, unsigned int y, unsigned int x, unsigned int value) { // 0x4D45A0
map[n * y + x] = value;
}unsigned int get_value(unsigned int* map, size_t n, unsigned int y, unsigned int x) { // 0x4D6450
return map[n * y + x];
}void create_map(size_t n, unsigned int** map) { // 0x4D76B0
if (n % 4) return;
unsigned int* _map = alloc_map(n); // 0x4D82D0
int value = 1; // 0x4D8B3F
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
set_value(_map, n, y, x, value); // 0x4D956F
value++; // 0x4D986A
}
}
size_t y1 = 0; // 0x4DA51B
size_t y2 = n - 1; // 0x4DA9DB
while (y1 < y2) { // 0x4DB041
for (int x = 0; x < n; x++) { // 0x4DB3E7
if (x % 4 == 0 || x % 4 == 3) { // 0x4DB913
unsigned int a = get_value(_map, n, y1, x); // 0x4DC2A8
unsigned int b = get_value(_map, n, y2, x); // 0x4DCD5B
set_value(_map, n, y1, x, b); // 0x4DCD7D
set_value(_map, n, y2, x, a); // 0x4DD05C
}
}
y1++; // 0x4DDB3A
y2--; // 0x4DE105
}
*map = _map; // 0x4DF1E8
}void shuffle_map(unsigned int* map, size_t n, unsigned int seed) { // 0x4DF410
srand(seed); // 0x4DF75D
for (int y1 = 0; y1 < n; y1++) { // 0x4DFF3B
for (int x1 = 0; x1 < n; x1++) { // 0x4E017C
unsigned int v1 = get_value(map, n, y1, x1); // 0x4E04A6
unsigned int y2 = rand() % n; // 0x4E09C4
unsigned int x2 = rand() % n; // 0x4E0CA2
unsigned int v2 = get_value(map, n, y2, x2); // 0x4E1197
set_value(map, n, y1, x1, v2);
set_value(map, n, y2, x2, v1); // 0x4E12EC
}
}
}void trans(unsigned int seed, char* buf, size_t size) { // 0x4E1620
unsigned int* map;
size_t n = 16; // 0x4E1B9B
create_map(n, &map); // 0x4E21C3
shuffle_map(map, n, seed); // 0x4E27BD
int x = 0; // 0x4E4442
int y = 0; // 0x4E4452
int i = 0; // 0x4E445E
while (i < size) { // 0x4E4823
buf[i] ^= get_value(map, n, y, x); // 0x4E492B
if (i % n == 0) { // 0x4E4BDE
y++; // 0x4E4F92
x = 0; // 0x4E5402
}
x++; // 0x4E641B
i++; // 0x4E68C7
}
}char* alloc_buf() { // 0x423810
return (char*) malloc(200); //
}unsigned long long get_values1(char** buf, size_t* size) {
*size = 74;
char* _buf = (char*) malloc(74);
char __buf[] = {
// ...
};
memcpy(_buf, __buf, 74);
*buf = _buf; // 004A79EA;
return 0xAAC82A5B;
}void buf_set_values(char* buf, unsigned long long value) { // 0x426150
memset(buf, 0, 200); // ???
*(unsigned long long*) buf = value;
}int buf_len(char* buf) { // 0x421970
int i;
for (i = 199; i >= 0; i--) {
if (buf[i]) break;
}
return i + 1;
}int buf_empty(char* x) {
for (int i = 0; i < 200; i++) {
if (x[i]) {
return 0;
}
}
return 1;
}void buf_add(char* x, char* y, char* z) {
for (int i = 0; i < 200; i++) {
z[i] = x[i] + y[i];
}
}void buf_mul(char *x, char *y, char *z) { // 0x43C130
memset(z, 0, 200);
if (buf_empty(x) || buf_empty(y)) { // 0x43DFC5
return ;
}
int x_len = buf_len(x); // 0x43E86F
int y_len = buf_len(y); // 0x43EDAD
char* tmp = alloc_buf(); // 0x43F271
for (int x_index = 0; x_index < x_len; x_index++) { // 0x43F658
int y_index = 0; // 0x43F8A4
int value = 0; // 0x43FD65
memset(tmp, 0, 200);
while (y_index < y_len) { // 0x440589
int _value = value + (unsigned char) y[y_index] * (unsigned char) x[x_index]; // 0x440ACE
tmp[x_index + y_index] = _value; // 0x441393
value = _value & 0xff00; // 0x4419D8
value >>= 8; // 0x442168
++y_index; // 0x44057D
}
if (x_index + y_index < 200) { // 0x442E85
tmp[x_index + y_index] = value; // 0x44324F
}
buf_add(tmp, z, z); // 0x443B53
}
}void buf_cpy(char* x, char* y) { // 0x429980
memcpy(x, y, 200);
}void buf_divmod(char* x, char* y, char* z, char* w) { // 0x444F30
/*
memset(w, 0, 200);
if (buf_empty(y)) { // 0x447D10
return;
}
memset(w); // 0x447116
buf_cpy(w, x); // 0x449797
v582 = buf_len(w) - buf_len(y); // 0x449A5A
/**/
}void buf_mod(char* x, char* y, char* z) { // 0x44EA60
// ...
buf_divmod(x, y, tmp, z);
}int check_buf(char* x, char* y, char* z) {
if (buf_len(x) + buf_len(y) > 200) { // 0x4C6123
return 0;
}
char* tmp1 = alloc_buf(); // 0x4C6FF1
char* tmp2 = alloc_buf(); // 0x4C783E
buf_mul(x, y, tmp1); // 0x4C9B3F
buf_mod(tmp1, z, tmp2); // 0x4CA6CB
// return tmp2 == 1;
return 1;
}int check4(char* buf1, size_t len1, char* buf2, size_t len2) {
char* dst = alloc_buf(); // 0x461262
char* tmp = alloc_buf(); // 0x461ACB
char* out = alloc_buf(); // 0x462284
char* dst1, dst2;
size_t size1, size2;
unsigned long long value1 = get_values1(&dst1, &size1)// 0x462B2D
buf_set_values(dst, value1); // 0x4632D6
memcpy(tmp, buf1, len1); // 0x463BD4
memcpy(out, dst1, size1); // 0x46473E
if (check_buf(dst, tmp, out)) { // 0x468066
// 0x46D156
// get_value2 -> 0x8395475F, buf2, dst2 // 0x4C2285
// check_buf(dst, tmp, out); // 0x470F73
return 1;
}
return 0;
}int check(char* input) { // sub_47B430
char* output;
size_t length;
if (b64decode(input, &output, &length)) { // 0x47D609
if (has_debugger() == 1) { // 0x47E402
if ( (*output & 1) != 0 )
*output += rand() % 3 + 1;
else
*output += rand() % 4 + 4;
}
/*
char a[16] = {
33, -124, 16, 66, 8, 33, -124, 16,
66, -56, 81, -121, -61, 0x80, -44, 61
}
for (int i = 0; i < (length >> 1); i++) { // 0x47E8A7
output[i] ^= a[i % 16];
}
for (int i = 0; i < length; i++) { // 0x47F146
output[i] ^= 0x63;
}
for (int i = length - 1; i < >= 0; i--) { // 0x47F146
output[i] ^= 0xa3;
}
for (int i = 0; i < length; i++) {
output[i] ^= 0xa3;
}
for (int i = 0; i < length; i++) {
output[i] ^= 0x63;
}
for (int i = 0; i < (length >> 1); i++) { // 0x47FD46
output[i] ^= a[i % 16];
}
/**/
unsigned short* buf1;
unsigned short* buf2;
if (check1(output, output_length)) { // 0x480414
if (check2(output, output_length - 4, &buf1, &buf2)) { // 0x482D0E
if (check3(*(unsigned int*) buf1, *(unsigned int*) buf2)) { // 0x48564B
trans(*(unsigned int*) buf1, (char*)((unsigned char*) buf1 + 8), buf1[2]); // 0x48792E
trans(*(unsigned int*) buf2, (char*)((unsigned char*) buf2 + 8), buf2[2]); // 0x488229
if (check4((char*)((unsigned char*) buf1 + 8), buf1[2], (char*)((unsigned char*) buf2 + 8), buf2[2])) { // 0x489AFF
return 1;
}
}
}
}
}
return 0;
}#include <stdio.h>#include <stdlib.h>#include <string.h>int has_debugger() { // 0x402220
// patch
return 0;
// ...
}int check1(char* buf, size_t size) { // 0x455F80
unsigned int crc = CRC32(buf, size - 4); // 0x457690
return crc == *(unsigned int*) (buf + size - 4); // 0x457C13
}int check2(void* buf, size_t size, unsigned short** buf1, unsigned short** buf2) {
if (size >= 0x10) { // 0x45942B
*buf1 = buf; // 0x45AF4E
if ((*buf1)[2] && (*buf1)[2] <= size - 16) { // 0x45B836
*buf2 = (unsigned short *)((unsigned char*) buf + (*buf1)[2] + 8); // 0x45CA22
if ((*buf2)[2] && (*buf2)[2] <= size - 16 - (*buf1)[2]) { // 0x45D3A3
return 1;
} else {
*buf2 = NULL;
}
} else {
*buf1 = NULL;
}
}
return 0;
}int check_inverse(unsigned long long x, unsigned long long y, unsigned long long z) {
return x * y % z == 1;
}int check3(unsigned int x, unsigned int y) { // 0x474170
unsigned long long p = 0x346F8717, a = 32069; // 0x47546A
if (check_inverse(a, x, p)) { // 0x477A1C
p = 0x729969FF;
a = 55057; // 0x478965
if (check_inverse(a, y, p)) { // 0x47A972
return 1;
}
}
return 0;
}unsigned int* alloc_map(size_t n) { // 0x4D2250
return (unsigned int*) malloc(4 * n * n); // 0x4D34CD
}void set_value(unsigned int* map, size_t n, unsigned int y, unsigned int x, unsigned int value) { // 0x4D45A0
map[n * y + x] = value;
}unsigned int get_value(unsigned int* map, size_t n, unsigned int y, unsigned int x) { // 0x4D6450
return map[n * y + x];
}void create_map(size_t n, unsigned int** map) { // 0x4D76B0
if (n % 4) return;
unsigned int* _map = alloc_map(n); // 0x4D82D0
int value = 1; // 0x4D8B3F
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
set_value(_map, n, y, x, value); // 0x4D956F
value++; // 0x4D986A
}
}
size_t y1 = 0; // 0x4DA51B
size_t y2 = n - 1; // 0x4DA9DB
while (y1 < y2) { // 0x4DB041
for (int x = 0; x < n; x++) { // 0x4DB3E7
if (x % 4 == 0 || x % 4 == 3) { // 0x4DB913
unsigned int a = get_value(_map, n, y1, x); // 0x4DC2A8
unsigned int b = get_value(_map, n, y2, x); // 0x4DCD5B
set_value(_map, n, y1, x, b); // 0x4DCD7D
set_value(_map, n, y2, x, a); // 0x4DD05C
}
}
y1++; // 0x4DDB3A
y2--; // 0x4DE105
}
*map = _map; // 0x4DF1E8
}void shuffle_map(unsigned int* map, size_t n, unsigned int seed) { // 0x4DF410
srand(seed); // 0x4DF75D
for (int y1 = 0; y1 < n; y1++) { // 0x4DFF3B
for (int x1 = 0; x1 < n; x1++) { // 0x4E017C
unsigned int v1 = get_value(map, n, y1, x1); // 0x4E04A6
unsigned int y2 = rand() % n; // 0x4E09C4
unsigned int x2 = rand() % n; // 0x4E0CA2
unsigned int v2 = get_value(map, n, y2, x2); // 0x4E1197
set_value(map, n, y1, x1, v2);
set_value(map, n, y2, x2, v1); // 0x4E12EC
}
}
}void trans(unsigned int seed, char* buf, size_t size) { // 0x4E1620
unsigned int* map;
size_t n = 16; // 0x4E1B9B
create_map(n, &map); // 0x4E21C3
shuffle_map(map, n, seed); // 0x4E27BD
int x = 0; // 0x4E4442
int y = 0; // 0x4E4452
int i = 0; // 0x4E445E
while (i < size) { // 0x4E4823
buf[i] ^= get_value(map, n, y, x); // 0x4E492B
if (i % n == 0) { // 0x4E4BDE
y++; // 0x4E4F92
x = 0; // 0x4E5402
}
x++; // 0x4E641B
i++; // 0x4E68C7
}
}char* alloc_buf() { // 0x423810
return (char*) malloc(200); //
}unsigned long long get_values1(char** buf, size_t* size) {
*size = 74;
char* _buf = (char*) malloc(74);
char __buf[] = {
// ...
};
memcpy(_buf, __buf, 74);
*buf = _buf; // 004A79EA;
return 0xAAC82A5B;
}void buf_set_values(char* buf, unsigned long long value) { // 0x426150
memset(buf, 0, 200); // ???
*(unsigned long long*) buf = value;
}int buf_len(char* buf) { // 0x421970
int i;
for (i = 199; i >= 0; i--) {
if (buf[i]) break;
}
return i + 1;
}int buf_empty(char* x) {
for (int i = 0; i < 200; i++) {
if (x[i]) {
return 0;
}
}
return 1;
}void buf_add(char* x, char* y, char* z) {
for (int i = 0; i < 200; i++) {
z[i] = x[i] + y[i];
}
}void buf_mul(char *x, char *y, char *z) { // 0x43C130
memset(z, 0, 200);
if (buf_empty(x) || buf_empty(y)) { // 0x43DFC5
return ;
}
int x_len = buf_len(x); // 0x43E86F
int y_len = buf_len(y); // 0x43EDAD
char* tmp = alloc_buf(); // 0x43F271
for (int x_index = 0; x_index < x_len; x_index++) { // 0x43F658
int y_index = 0; // 0x43F8A4
int value = 0; // 0x43FD65
memset(tmp, 0, 200);
while (y_index < y_len) { // 0x440589
int _value = value + (unsigned char) y[y_index] * (unsigned char) x[x_index]; // 0x440ACE
tmp[x_index + y_index] = _value; // 0x441393
value = _value & 0xff00; // 0x4419D8
value >>= 8; // 0x442168
++y_index; // 0x44057D
}
if (x_index + y_index < 200) { // 0x442E85
tmp[x_index + y_index] = value; // 0x44324F
}
buf_add(tmp, z, z); // 0x443B53
}
}void buf_cpy(char* x, char* y) { // 0x429980
memcpy(x, y, 200);
}[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！
赞赏
|
|
|---|---|
|
|
他的文章
赞赏
雪币:
留言:
