看雪 CTF 2018 Writeup - 数据结构

用IDA载程序，可以发现这个出题人很皮，把PDB删了还卖萌 = =

进程序看一下main函数

 scanf("%s", flag, 32);
  gencorrect(&correct_str);
  genwrong(&wrong_str);
  if ( isAlphaNumeric(flag, (int)&wrong_str) )
  {
    if ( &flag[strlen(flag) + 1] - &flag[1] == 22 )
      check(flag, (int)&correct_str, (int)&wrong_str);
    else
      output_str((int)&wrong_str);
    wrong_str = 0;
    v10 = 0;
    v11 = 0;
    v12 = 0;
    correct_str = 0;
    v6 = 0;
    v7 = 0;
    v8 = 0;
    system("pause");
    result = 0;
  }
  else
  {
    correct_str = 0;
    v6 = 0;
    v7 = 0;
    v8 = 0;
    wrong_str = 0;
    v10 = 0;
    v11 = 0;
    v12 = 0;
    result = 0;
  }
  return result;
}

先读入Flag，然后生成Answer correct和Answer Wrong的字符串，然后判断读入的Flag是否为字母数字且长度为22，若是则进入check函数。

check函数首先进行了一大串赋值

  v12[7] = 2;
  v13[30] = 0;
  v13[8] = flag[2];
  v12[6] = 3;
  v13[7] = 0;
  v13[29] = flag[1];
  v13[39] = flag[12];
  v13[16] = flag[16];
  v13[36] = flag[9];
  v13[32] = flag[7];
  v13[37] = flag[10];
  v13[33] = flag[8];
  v13[1] = flag[20];
  v12[5] = 4;
  v13[40] = 0;
  v13[14] = flag[15];
  v12[4] = 2;
  v13[10] = 0;
  v12[3] = 2;
  v13[34] = 0;
  v13[6] = flag[6];
  v13[13] = flag[14];
  v13[4] = flag[4];
  v13[9] = flag[3];
  v13[12] = flag[13];
  v12[2] = 3;
  v13[19] = 0;
  v13[5] = flag[5];
  v13[17] = flag[17];
  v13[28] = *flag;
  v13[2] = flag[21];
  v12[1] = 3;
  v13[15] = 0;
  v13[0] = flag[19];
  v13[38] = flag[11];
  v13[18] = flag[18];
  v12[0] = 3;
  v13[3] = 0;
  *(_DWORD *)&v13[20] = 0;
  *(_DWORD *)&v13[24] = 0;

这个是把读入的flag按照长度分组，各组分别为2 2 3 2 4 3 3 3。
下面重复调了两个函数，看上去是某个对象的初始化函数，且其中有一个函数非常的复杂。
尝试在程序中寻找有关的信息，发现RTTI的虚表：

很明显发现这是一个字典树（TrieTree）的结构。

关于字典树，可以参考链接：
Trie树（字典树，前缀树，键树）分析详解

经过一些调试，判断这两个函数的功能为新建一个单词，和将单词加入字典树。

加入完之后进行了一个判断

 v12 = this;
  if ( sub_10F3D70((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];
  while ( v11 != v5 )
  {
    v9 = *v11;
    v3 = sub_10F3670(v9, &v4);
    v8 = (int *)sub_10F3830((int *)a2, (int)v3);
    if ( !v8 )
      return 0;
    if ( sub_10F36D0(v8, v9) )
      return 0;
    ++v11;
  }
  return 1;
}

这是一个深度优先的遍历，判断树中的每一个节点内容相同，子节点个数相同，作为单词结尾的次数相同，然后对每一个子节点递归向下判断。
很明显，这是判断两棵字典树严格相等的函数。

传入函数的另一个参数即为正确的字典树，用JumpToXref定位到这棵树的生成函数：

 v10 = this;
  sub_10F15D0(&v12);                  // gen words
  sub_10F1540(&v13);
  sub_10F16E0(&v17);
  sub_10F1660(&v14);
  sub_10F1880(&Src);
  sub_10F1770(&v16);
  sub_10F14C0(&v15);
  sub_10F17F0(&v11);
  NewWord(&v9, &Src);
  cp_node((int)&9, &v9);
  NewWord(&v8, &v17);
  cp_node((int)&M, &v8);
  NewWord(&v7, &v16);
  cp_node((int)&k, &v7);
  NewWord(&v6, &v15);
  cp_node((int)&c, &v6);
  NewWord(&v5, &v14);
  cp_node((int)&7, &v5);
  NewWord(&v4, &v13);
  cp_node((int)&t, &v4);
  NewWord(&v3, &v11);
  cp_node((int)&kx, &v3);
  NewWord(&v2, &v12);
  cp_node((int)&f, &v2);
  sub_10F3940(&M, (int)&k);          // connect nodes
  sub_10F3940(&t, (int)&9);
  sub_10F3940(&7, (int)&M);
  sub_10F3940(&t, (int)&f);
  sub_10F3940(&c, (int)&7);
  sub_10F3940(&root, (int)&kx);
  sub_10F3940(&c, (int)&t);
  sub_10F3940(&root, (int)&c);
  sub_10F3650(&c, 0);       // the last appearance count        
  sub_10F3650(&k, 1);
  sub_10F3650(&9, 1);
  sub_10F3650(&t, 1);
  sub_10F3650(&7, 1);
  sub_10F3650(&M, 2);
  sub_10F3650(&root, 0);
  sub_10F3650(&f, 1);
  sub_10F3650(&kx, 1);
  cp_tree(&static_tree, (int)&root);
  return v10;

首先生成一些节点，然后按一定顺序把节点连起来，最后标记每个节点作为最后一个字符出现的次数。
生成的树大概是这个样子：

         |(root)0|
           /    \
      |kx  1|  |c   0|
                /   \
            |7  1| |t   1|
            /       /    \
         |M   2| |f   1| |9  1|
         /
      |k    1|

// 这里可以发现这是有优化的字典树，中间字符唯一且不会作为最后一个字符出现的字符串合并到了一个节点上，如那个kx节点
那么就可以得到需要的字符串：
kx ct c7 c7M c7M c7Mk ctf ct9
按照2 2 3 2 4 3 3 3的顺序排列，可以确定c7Mk的位置。
其他的位置要进最后的一个判重函数来确定：

  if ( (a1[1] ^ *a1) != 84
    || (a2[1] ^ *a2) != 19
    || (*(char *)(a3 + 1) ^ *(char *)(a3 + 2)) != 18
    || (*(char *)(a4 + 2) ^ *(char *)(a4 + 1)) != 77 )
  {
    result = output_str(a6);
  }
  else
  {
    result = output_str(a5);
  }
  return result;
}

可以确定第一段是c7, 第四段是kx，第六段是ctf，第七段是ct9。
最终的flag为