看雪ctf2017数据结构 writeup

kanxue ctf 2017 writeup

Posted by fa1con on October 10, 2018

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。