-
-
[原创] 京东-看雪 2018 - 春季赛 第二题 - 数据结构
-
2018-6-19 01:30
-
功能分析
拿到的是一个 win32 控制台程序
2018CMv4.exe: PE32 executable (console) Intel 80386, for MS Windows
运行一下, 输入一个字符串，返回正确或错误，没有其他
11111111 Answer is Wrong 请按任意键继续. . .
ida 打开程序看看
main 主要逻辑如下，传入一个字符串，长度为 22
对传入的 字符串有一个check 函数，一个字符一个字符判断
- (chr | 0x20) 是不是在 ord('a') ~ ord('z') 的范围
- chr 是否在 ord('0') 或 ord('9') 范围
字符check 过了之后会调用一个 main_logic_401C40 函数，这里就是主要逻辑了
int __cdecl main(int argc, const char **argv, const char **envp)
{
int result; // eax
char input[32]; // [esp+10h] [ebp-44h]
int corr; // [esp+30h] [ebp-24h]
int v6; // [esp+34h] [ebp-20h]
int v7; // [esp+38h] [ebp-1Ch]
int v8; // [esp+3Ch] [ebp-18h]
int wron; // [esp+40h] [ebp-14h]
int v10; // [esp+44h] [ebp-10h]
int v11; // [esp+48h] [ebp-Ch]
int v12; // [esp+4Ch] [ebp-8h]
input_401170("%s", input, 32);
correct(&corr); // 生成 correct 字符串
wrong(&wron); // 生成 wrong 字符串
if ( char_check_402180(input, &wron) )
{
if ( &input[strlen(input) + 1] - &input[1] == 0x16 )// 长度==22
main_logic_401C40(input, &corr, &wron);
else
printsome(&wron);
.....
main logic 函数, 将我们输入的字符串切割，然后存放到局部变量上
有点乱，后面直接调试看内存可以比较快看出来
v19 = 2; v43 = 0; v28 = input[2]; v18 = 3; v27 = 0; v42 = input[1]; v50 = input[12]; s4 = input[16]; v47 = input[9]; s2 = input[7]; v48 = input[10]; v45 = input[8]; v21 = input[20]; v17 = 4; v51 = 0; v33 = input[15]; v16 = 2; v30 = 0; v15 = 2; v46 = 0; v26 = input[6]; v32 = input[14]; v24 = input[4]; v29 = input[3]; s3 = input[13]; v14 = 3; v38 = 0; v25 = input[5]; v36 = input[17]; s1 = *input; v22 = input[21]; v13 = 3; v34 = 0; v20 = input[19]; v49 = input[11]; v37 = input[18]; v12 = 3; v23 = 0; tree = 0; v40 = 0; std::_Ref_count_obj<__ExceptionPtr>::_Ref_count_obj<__ExceptionPtr>(&tree); v52 = 0;
_Ref_count_obj 这个函数进行一些内存分配的操作
注意 &TrieTree::`vftable' 这里，这是 c++ 对象的写法
Tire Tree ?? 想起题目名字叫数据结构，是不是和这个有关？
找了一下资料，Tire Tree ，字典树，大概就是数据放到树上方便检索的操作
这个函数主要就是 创建一个 TireTree 对象，然后返回其指针，后续操作都在这个上面进行
_DWORD *__thiscall std::_Ref_count_obj<__ExceptionPtr>::_Ref_count_obj<__ExceptionPtr>(_DWORD *this)
{
_DWORD *v1; // ST14_4
_DWORD *Memory; // ST0C_4
v1 = this;
sub_403070(this);
*v1 = &TrieTree::`vftable';
Memory = operator new(0x110u);
v1[1] = sub_403100(Memory);
return v1;
}
再次回到 main_logic 函数 后续的内容
这里在两个函数重复操作了 8 次， 后续分析之后发现这里是
- 前面将传入的 22 个 byte 的字符串切割成 八个部分
- 对每个子串 调用 下面的 store， insert 函数，其实就是插入前面分配的树上， 就是将子串插入到字典树上的操作了
在 对应的 store 函数上下断点，调试一下就可以看出插入的顺序
下面的注释是调试出来的对应的 输入字符串的 下标store1_403AB0(&v11, &s3); // 13 14 15 insert_402B40(&tree, &v11); store1_403AB0(&v10, &s1); // 0 1 insert_402B40(&tree, &v10); store1_403AB0(&v9, &v47); // 9 10 11 12 insert_402B40(&tree, &v9); store1_403AB0(&v8, &v24); // 4 5 6 insert_402B40(&tree, &v8); store1_403AB0(&v7, &v28); // 2 3 insert_402B40(&tree, &v7); store1_403AB0(&v6, &s2); // 7 8 insert_402B40(&tree, &v6); store1_403AB0(&v5, &s4); // 16 17 18 insert_402B40(&tree, &v5); store1_403AB0(&v4, &v20); // 19 20 21 insert_402B40(&tree, &v4);
插入完成之后 我们就得到了一棵字典树了，后面会 和一个全局的 gtree_407E48
进行比较
其实就是我们传入一个字符串，切割插入字典树之后看看和预先定义好的一棵树是不是一样
if ( cmp_tree_4030E0(&tree, >ree_407E48) ) // maybe 判断两棵树是不是一样
last_check_401B80(&s1, &s2, &s3, &s4, correct, wrong);
else
printsome(wrong);
v52 = -1;
return sub_402AC0(&tree);
}
如果两个树一样，后面还会有一个 check 函数, 对 字符串 子串进行一些值的判断，现在还没有用，这个可以在后面帮助反推输入的值
int __cdecl last_check_401B80(char *chr_0_1, char *char_7_8, int char_13_14_15, int char_16_17_18, int correct, int wrong)
{
int result; // eax
if ( (chr_0_1[1] ^ *chr_0_1) != 0x54
|| (char_7_8[1] ^ *char_7_8) != 0x13
|| (*(char_13_14_15 + 1) ^ *(char_13_14_15 + 2)) != 0x12
|| (*(char_16_17_18 + 2) ^ *(char_16_17_18 + 1)) != 0x4D )
{ // 2 个 byte 的比较
result = printsome(wrong);
}
else
{
result = printsome(correct);
}
return result;
}
okay 到这里思路就很明确了，程序利用我们的输入构建了一棵字典树
这棵树要和一棵预先准备好的树一样，那么我们就需要先找到这棵树
ida 看一下引用
找到函数 sub_40190
看其调用可以知道
这里程序是通过
_scrt_common_main_seh
这个函数进行了一些预处理，然后再通过它调用main 函数，去除一些初始化的操作， 预先准备好的字典树 的初始化大体是下面
程序调用了 initterm 函数，这个函数的效果大致是传两个地址，这两个地址之间的值不为0的 指针都当作函数从头到尾调用一遍
else
{
dword_407464 = 1;
if ( initterm_e(&unk_405154, &unk_405160) )
return 255;
initterm(&somefunc_40511C, &unk_405150);
dword_407464 = 2;
}
somefunc 里面是下面, 前面是一些初始化 TireTree 对象的操作，主要是最后一个函数
.rdata:0040511C somefunc_40511C db 0 ; DATA XREF: __scrt_common_main_seh(void)+71↑o .rdata:0040511D db 0 .rdata:0040511E db 0 .rdata:0040511F db 0 .rdata:00405120 dd offset sub_40433B .rdata:00405124 dd offset sub_401000 .rdata:00405128 dd offset sub_401030 .rdata:0040512C dd offset sub_401050 .rdata:00405130 dd offset sub_401070 .rdata:00405134 dd offset sub_401090 .rdata:00405138 dd offset sub_4010B0 .rdata:0040513C dd offset sub_4010D0 .rdata:00405140 dd offset sub_4010F0 .rdata:00405144 dd offset sub_401110 .rdata:00405148 dd offset sub_401130 .rdata:0040514C dd offset sub_401150 .rdata:00405150 unk_405150 db 0
sub_401150 函数包含了 我们用于比较的字典树的生成的操作
主要逻辑如下
下面的几个函数都是一样的操作，生成一个字符串然后存放到 一个地址里面
比如 f_4015D0(&v12) 这个函数 生成了 'f' 然后存放到 v12 这个局部变量里面
void *__thiscall gtree_401900(void *this)
{
..........
v10 = this;
f_4015D0(&v12);
t_401540(&v13);
M_4016E0(&v17);
7_401660(&v14);
9_401880(&Src);
k_401770(&v16);
c_4014C0(&v15);
kx_4017F0(&v11);
后面执行了和之前 前面 main logic 生成字典树差不多的操作
猜测这里就是在 构造字典树了
store1_403AB0(&v9, &Src); copy(&node_9, &v9); store1_403AB0(&v8, &v17); copy(&node_M, &v8); store1_403AB0(&v7, &v16); copy(&node_k, &v7); store1_403AB0(&v6, &v15); copy(&node_c, &v6); store1_403AB0(&v5, &v14); copy(&node, &v5); store1_403AB0(&v4, &v13); copy(&node_t, &v4); store1_403AB0(&v3, &v11); copy(&node_kx, &v3); store1_403AB0(&v2, &v12); copy(&node_f, &v2);
存放之后会进行一系列的操作，一开始不知道是干什么
观察 copysome_403940 函数 可以猜测这里应该是在构建字典树的过程
给一个节点孩子什么的
比如 copysome_403940(&node_M, &node_k)
操作的效果就是 node_M 是父节点， node_k 加入成为 node_M 的子节点
通过下面的操作我们也可以构建出一棵树出来
copysome_403940(&node_M, &node_k);
copysome_403940(&node_t, &node_9);
copysome_403940(&node, &node_M);
copysome_403940(&node_t, &node_f);
copysome_403940(&node_c, &node);
copysome_403940(&root, &node_kx);
copysome_403940(&node_c, &node_t);
copysome_403940(&root, &node_c);
//----------------------------------------//
_DWORD *__thiscall copysome_403940(_DWORD *this, int a2)
{
_DWORD *result; // eax
if ( this[66] >= 0x20u )
exit(-1);
this[this[66] + 0x22] = a2;
result = this + 0x22;
++this[66];
return result;
}
字典树构建完成之后， 会给每个节点 执行 sub_403650 函数，赋一个数字值，估计就是引用计数了
sub_403650(&node_c, 0); sub_403650(&node_k, 1); sub_403650(&node_9, 1); sub_403650(&node_t, 1); sub_403650(&node, 1); sub_403650(&node_M, 2); sub_403650(&root, 0); sub_403650(&node_f, 1); sub_403650(&node_kx, 1); sub_403A60(>ree_407E48, &root); return v10; }
很好，到了这里，自己重构一下 字典树就可以找出所有可能的字符串了
mspaint 画了一棵树，勿喷
因为 M 的引用计数是两个，所以猜测需要有两个一样的串，和前面构建字典树的字符的数量也相符
不过这里有些 字符串的长度是一样的，不是到哪个先哪个后，这就需要前面提到的 last_check_401B80 函数了， 将对应的字符 的byte 异或一下就可以知道哪个是哪个了
int __cdecl last_check_401B80(char *chr_0_1, char *char_7_8, int char_13_14_15, int char_16_17_18, int correct, int wrong)
{
int result; // eax
if ( (chr_0_1[1] ^ *chr_0_1) != 0x54
|| (char_7_8[1] ^ *char_7_8) != 0x13
|| (*(char_13_14_15 + 1) ^ *(char_13_14_15 + 2)) != 0x12
|| (*(char_16_17_18 + 2) ^ *(char_16_17_18 + 1)) != 0x4D )
{ // 2 个 byte 的比较
其实自己排列组合爆破一下也是可以的
最后得到的flag
c7ctc7Mkxc7Mkctfct9c7M
|
|
|---|---|
|
|
您是怎么判断这个函数是生成字符串的，我怎么都解不明白  我运行代码怎么都是解不出来 a1 = [141,180,251,69,81,152,144,139,175,218,207,96,171,100,39,0] # a1 = [0xb4,0xFB,0x45,0x51,0x98,0x90,0x8B,0xAF,0xDA,0xCF,0x60,0xAB,0x64,0x27,0x00] for i in range(0,15): a1[i] ^= i * 34 * i + i * i * 58 * i - 78 * i - 52 result = i + 1 print(a1) [-191, -146, 371, 1655, 3941, 7538, 13088, 20841, 31091, 44064, 60503, 80498, 104047, 132206, 164711, 0] [-136, -223, 461, 1635, 4012, 7546, 13115, 20813, 30982, 44085, 60664, 80569, 104096, 132141, 164672]
最后于 2018-6-23 21:08
被zjhkx学院编辑
，原因：
|
|
|
|
