[原创]看雪京东ctf2018 第二题数据结构-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创]看雪京东ctf2018 第二题数据结构

发表于: 2018-6-18 19:06 2219

[原创]看雪京东ctf2018 第二题数据结构

wyeMIAkidC 活跃值

2018-6-18 19:06

2219

大多数思路都在idb里了，这里说的不清楚可以看idb，关键部分应该和看代码差不多了。

先看main，简单调试就能得到如下结论

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int result; // eax
  char v4[64]; // [esp+10h] [ebp-44h]

  sub_C81170("%s", v4, 32);
  sub_C81360(&v4[32]);
  sub_C81200(&v4[48]);                          // 动态生成成功失败提示字符串
  if ( sub_C82180(v4, (int)&v4[48]) )           // 初步检查输入字符串是否有特殊符号等
  {
    if ( &v4[strlen(v4) + 1] - &v4[1] == 0x16 ) // 判断长度是不是 22
      sub_C81C40(v4, (int)&v4[32], (int)&v4[48]);
    else

看sub_C82180，分析内部函数，根据TrieTree等类名，反推数据结构应该是字典树。继续分析内部各个小函数，根据输入输出offset和实际数据，反推整个树的结构体如下（可见附件中的structure.h）：

#ifdef _FOR_IDA
typedef unsigned int       uint32_t;
#else
#include <stdint.h>
#endif // _FOR_IDA

typedef struct trie_tree_data_t_ {
	char data[128];
	uint32_t length;
}trie_tree_data_t;

typedef struct trie_tree_child_t_ {
	struct trie_tree_node_t_ * childs[32]; //128
	uint32_t child_count; 
}trie_tree_child_t; // 128 + 4 = 132

typedef struct trie_tree_node_t_ {
	void* vftable; // 4
	trie_tree_data_t data; // 132 + 4 = 136
	trie_tree_child_t child;
	uint32_t counter;
}trie_tree_node_t;// 272

typedef struct trie_tree_t_ {
	void* vftable; // 4
	trie_tree_node_t * child;
}trie_tree_t;

反推结构丢给ida，进一步明确各个小函数的逻辑，得到 sub_C82180 关键逻辑如下（可见idb）：

  data_set_string(&a2a, &v20[12]);
  insert_data(&v21, &a2a);
  data_set_string(&v10, Src);
  insert_data(&v21, &v10);
  data_set_string(&v9, &Src[8]);
  insert_data(&v21, &v9);
  data_set_string(&v8, &v20[4]);
  insert_data(&v21, &v8);
  data_set_string(&v7, &v20[8]);
  insert_data(&v21, &v7);
  data_set_string(&v6, &Src[4]);
  insert_data(&v21, &v6);
  data_set_string(&v5, &v20[16]);
  insert_data(&v21, &v5);
  data_set_string(&v4, v20);
  insert_data(&v21, &v4);
  if ( tree_is_same(&v21, &target_tree) )
    check_serial(Src, &Src[4], &v20[12], &v20[16], (char *)a2, (char *)a3);

这段前面还有个把输入字符串分割打乱的逻辑，懒得逆直接调试看数据，输入abcdefghij1234567890zx测试，得到输入字符串拆解后insert_data的顺序如下：

	// abcdefghij1234567890zx
	// 456
	// ab
	// j123
	// efg
	// cd
	// hi
	// 789
	// 0zx

逆向insert_data，得到树插入节点逻辑如下：

!same 
root +-> new 1

[new ]
[old            ]
|same| diff_old |
same 1 + -> diff_old old


[new                   ]
|same|     diff_new    |
[old            ]
|same| diff_old |

same old + 1
           + -> diff_old old 1
           + -> diff_new 1

[new ]
[old ]
|same|
same counter++

至此已经知道了输入会被构造成什么数据结构，下一步寻找目标数据结构看tree_is_same内部compare_childs根据之前已经标记好的函数，可以反推出来C87E48（idb已经标为target_tree）地址上应该是trie_tree_t数据结构，找到目标树初始化函数sub_C81900，分析其逻辑如下：

  data_set_string(&a2, &v11[28]);               // 9
  node_set_data(&node_9, &a2);
  data_set_string(&v8, &v11[24]);               // M
  node_set_data(&node_M, &v8);
  data_set_string(&v7, &v11[20]);               // k
  node_set_data(&node_k, &v7);
  data_set_string(&v6, &v11[16]);               // c
  node_set_data(&node_c, &v6);
  data_set_string(&v5, &v11[12]);               // 7
  node_set_data(&node_7, &v5);
  data_set_string(&v4, &v11[8]);                // t
  node_set_data(&node_t, &v4);
  data_set_string(&v3, v11);                    // kx
  node_set_data(&node_kx, &v3);
  data_set_string(&v2, &v11[4]);                // f
  node_set_data(&node_f, &v2);
  node_append_child(&node_M, &node_k);
  node_append_child(&node_t, &node_9);
  node_append_child(&node_7, &node_M);
  node_append_child(&node_t, &node_f);
  node_append_child(&node_c, &node_7);
  node_append_child(&node_root, &node_kx);
  node_append_child(&node_c, &node_t);
  node_append_child(&node_root, &node_c);
  node_set_counter(&node_c, 0);
  node_set_counter(&node_k, 1);
  node_set_counter(&node_9, 1);
  node_set_counter(&node_t, 1);
  node_set_counter(&node_7, 1);
  node_set_counter(&node_M, 2);
  node_set_counter(&node_root, 0);
  node_set_counter(&node_f, 1);
  node_set_counter(&node_kx, 1);
  tree_set_first_child(&target_tree, &node_root);

得到目标树结构应该如下：

	// root 0
	//  kx 1
	//  c 0
	//   7 1
	//    M 2
	//     k 1
	//   t 1
	//    9 1
	//    f 1

有了目标树结构，有了输入数据拆分结果，有了数据结构构造逻辑，反推SN如下

abcdefghij1234567890zx对应：
	// 456
	// ab
	// j123
	// efg
	// cd
	// hi
	// 789
	// 0zx
对应：
	// c7M
	// kx
	// c7Mk
	// c7M
	// c7
	// ct
	// ctf
	// ct9
对应kxc7c7Mctc7Mkc7Mctfct9

但是这个SN不对，看后面逻辑发现一个xor检查

int __cdecl check_serial(char *a1, char *a2, char *a3, char *a4, char *a5, char *a6)
{
  int result; // eax

  if ( (a1[1] ^ *a1) != 0x54                    // c7
    || (a2[1] ^ *a2) != 0x13                    // kx
    || (a3[1] ^ a3[2]) != 0x12                  // tf
    || (a4[2] ^ a4[1]) != 0x4D )                // t9
  {
    result = sub_C811D0(a6);
  }
  else
  {
    result = sub_C811D0(a5);
  }
  return result;
}

调试可知a5和a6分别是correct/wrong字符串，a1-a4是拆分后的输入字符串
懒推倒a1-a4分别是什么，直接调试走过来看a1-a4的值，再和xor运算结果去对，看看是那几个部分错了，再通过长度和xor结果反推a1a2前两位，a3 a4第2、3位字符串是什么（拆分结果固定位总共就这么几个字符串，xor试试就知道了）。
因为前面已经逆向得知比较输入树和目标树的时候并没有限制节点输入顺序，和同长度的拆分结果段交换一下位置，得到最终结果c7ctc7Mkxc7Mkctfct9c7M

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！

最后于 2018-6-18 23:11 被wyeMIAkidC编辑，原因：完善一下

上传的附件：