writeup for 看雪ctf2018 数据结构
运行一下程序,随便输入,然后回车
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
F:\CTF\kanxuectf\2
λ 2018CMv4.exe
csa
Answer is Wrong
请按任意键继续. . . 拖进IDA,F5
sub_401170("%s", v4, 32);
sub_401360(&v5);
sub_401200(&v9); sub_401170明显是输入,进入sub_401360
int __cdecl sub_401360(_BYTE *a1)
{
int result; // eax
unsigned int i; // [esp+0h] [ebp-8h]
*a1 = -64;
a1[1] = -69;
a1[2] = -8;
a1[3] = -108;
a1[4] = 120;
a1[5] = 11;
a1[6] = 23;
a1[7] = -12;
a1[8] = -74;
a1[9] = 79;
a1[10] = 113;
a1[11] = 14;
a1[12] = -42;
a1[13] = 85;
a1[14] = -50;
result = 1;
a1[15] = 0;
for ( i = 0; i < 0xF; ++i )
{
a1[i] ^= i * 17 * i + i * i * 96 * i - 29 * i - 127;
result = i + 1;
}
return result;
} 改变v5的值,直接写个C程序输出a1可得
F:\CTF\kanxuectf\2
λ g1
Answer correct!
result = 15 那么sub_401200一样可得Answer is Wrong。接着看sub_402180
char __cdecl sub_402180(const char *a1, int a2)
{
signed int v2; // kr00_4
signed int i; // [esp+Ch] [ebp-Ch]
v2 = strlen(a1);
for ( i = 0; i < v2; ++i )
{
if ( !sub_402140(a1[i]) && !sub_402110(a1[i]) )
{
sub_4011D0(a2);
return 0;
}
}
return 1;
} 由流程可知要返回1,所以```sub_402140(a1[i])```和```sub_402110(a1[i])```必须为1,进入sub_402140,```return (a1 | 0x20) >= 97 && (a1 | 0x20) <= 122;``` 写python验证一下哪些符合
>>> [chr(a1) for a1 in range(1,128) if 1==((a1 | 0x20) >= 97 and (a1 | 0x20) <= 122)]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'] 然后加上sub_402110,可得输入的字符串应在a-z,A-Z,0-9。 然后```&v4[strlen(v4) + 1] - &v4[1] == 22```很明显flag长度为22 进入sub_401C40,这里开始就比较复杂了,涉及到C++逆向,这部分我刚接触没多久。 ```std::_Ref_count_obj<__ExceptionPtr>::_Ref_count_obj<__ExceptionPtr>(&v39);```应该是初始化对象。```sub_403AB0(&v11, &Src);```则是存储数据,共调用了8次这个函数,通过查看栈的地址可以发现实际上是将flag切成8份,分别存储。暂时先不看sub_402B40干了些什么,不过题目是数据结构,我猜测这里应该是一个树。
.data:01087020 00000010 C .?AVtype_info@@
.data:01087038 00000014 C .?AVbad_alloc@std@@
.data:01087054 00000014 C .?AVexception@std@@
.data:01087070 0000001F C .?AVbad_array_new_length@std@@
.data:01087098 0000000F C .?AVTrieTree@@
.data:010870B0 00000012 C .?AVTrieTreeAbs@@
.data:010870CC 00000013 C .?AVTrieTreeNode@@
.data:010870E8 00000016 C .?AVTrieTreeNodeAbs@@
.data:01087108 00000019 C .?AVTrieTreeNodeStatic@@
.data:0108712C 00000015 C .?AVTrieTreeStatic@@ 查看字符串,确实是一个树。
char Src; // [esp+450h] [ebp-30h]
char v32; // [esp+451h] [ebp-2Fh]
char v33; // [esp+452h] [ebp-2Eh]
char v34; // [esp+453h] [ebp-2Dh]
Src = a1[13];
v32 = a1[14];
v33 = a1[15];
v34 = 0; ```strcpy_s```复制字符串时,读到'\0'截断 整理一下就是
1---flag[13]->flag[15]
2---flag[0]->flag[1]
3---flag[9]->flag[12]
4---flag[4]->flag[6]
5---flag[2]->flag[3]
6---flag[7]->flag[8]
7---flag[16]->flag[18]
8---flag[19]->flag[21] 然后看到```sub_10830E0(&v39, (int)&dword_1087E48)```,进入```&dword_1087E48```,发现没有定义,那么应该是程序运行时生成了,既然我们v39是个树,那么```&dword_1087E48```也应该是个树,选中```&dword_1087E48```,按x,IDA的一个功能,看函数被调用情况。 ```Up o sub_1081900+25F mov ecx, offset dword_1087E48```点击进入发现这是一个生成树的函数。本地写代码看树中含有哪些字母。 ```sub_1083AB0```复制字符串,```sub_1083620```生成结点,```sub_1083940```连接结点。 ```sub_1083650```给结构体传一个数字,暂时不知道干嘛。 整理一下树如下, ![](http://wx2.sinaimg.cn/mw690/0060lm7Tly1fxg5vnkrq0j30dq0acmx8.jpg)
接着看最后一个验证函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int __cdecl sub_1081B80(char *a1, char *a2, int a3, int a4, int right, int wrong)
{
int result; // eax
if ( (a1[1] ^ *a1) != 84
|| (a2[1] ^ *a2) != 19
|| (*(char *)(a3 + 1) ^ *(char *)(a3 + 2)) != 18
|| (*(char *)(a4 + 2) ^ *(char *)(a4 + 1)) != 77 )
{
result = sub_10811D0(wrong);
}
else
{
result = sub_10811D0(right);
}
return result;
依照函数调用关系可以得到
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
54
55
56
57
flag[1]^flag[0]=84
flag[8]^flag[7]=19
flag[14]^flag[15]=18
flag[17]^flag[18]=77 写脚本验证一下
flag_c = ['k','x','c','t','k','9','7','M','f']
for i in flag_c:
for j in flag_c:
if ord(i) ^ ord(j) == 84:
print i,j 输出为
c 7
7 c 那么按照树生成的规则,显然是c7,所以得到
1---flag[13]->flag[15]--------?tf(显然为ctf)
2---flag[0]->flag[1]----------c7
3---flag[9]->flag[12]---------
4---flag[4]->flag[6]----------
5---flag[2]->flag[3]----------
6---flag[7]->flag[8]----------kx
7---flag[16]->flag[18]--------?t9(显然为ct9)
8---flag[19]->flag[21]-------- 第三个有四位字母,显然为c7Mk,然后呢。。。不会了,orz。这时候想到每个字母都赋了一个值,那么猜想1.这是该字母使用次数 2.以该字母开头的次数 3.这是以该字母结尾的次数。 1,2显然是错的,那么假设3正确,则4为c7M,5为c7,8为c7M。加起来就是c7ctc7Mkxc7Mkctfct9c7M。 得到flag后回过头来,
int __thiscall sub_1083940(_DWORD *this, int a2)
{
int result; // eax
if ( this[66] >= 0x20u )
exit(-1);
this[this[66] + 34] = a2;
result = (int)(this + 34);
++this[66];
return result;
}
_DWORD *__thiscall sub_1083650(_DWORD *this, int a2)
{
_DWORD *result; // eax
result = this;
this[67] = a2;
return result;
}
//char __thiscall sub_1083730(int *this, int a2)
v12 = this;
if ( sub_1083D70((const char *)this + 4, a2 + 4) )
return 0;
v7 = v12[66];
v6 = *(_DWORD *)(a2 + 264);
if ( v7 != v6 )
return 0;
if ( v12[67] != *(_DWORD *)(a2 + 268) )
return 0;
v10 = v12 + 34;
v11 = v12 + 34;
v5 = &v12[v12[66] + 34]; 树结构是一样的,```sub_1083940```计算结点的儿子数,```sub_1083650```计算次数以该节点结尾次数,所以可以推断出``` v7 != v6 ```是在比较结点的儿子数是否一样,```v12[67] != *(_DWORD *)(a2 + 268)```比较以该节点结尾次数是否一样。```sub_1083830```copy字符,比较字符。至于```sub_1082B40```生成树,,,过程有点复杂。感兴趣的自己看吧。
保存字符串的结构体
1
2
3
4
5
6
7
8
9
10
struct store{
char buf[0x80];
int length;
} 树结点结构体
struct treenode{
struct treenode* child[0x20];
int childcount;
int repeat;
} 暂时就先这样orz。