这是关于字典树的题。大致意思是：先创建了一个字典树，要求构造字串，创建一样的字典树。

本着还原做题思路的想法，进行此篇writeup。

初探及流程分析

IDA载入，弹出有关pdb信息的弹窗，发现pdb文件名被改成You want to leak information from pdb path? No way! QAQ。这是何意？难道是文件名称会泄露题名中的数据结构？

先看main函数，代码如下

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int result; // eax
  char input[32]; // [esp+10h] [ebp-44h]
  char right[16]; // [esp+30h] [ebp-24h]
  char wrong[16]; // [esp+40h] [ebp-14h]

  scanf("%s", input, 32);
  init_rlt_str_1(right);
  init_rlt_str_2(wrong);
  if ( check_format(input, wrong) )
  {
    if ( &input[strlen(input) + 1] - &input[1] == 22 )// length=22
      check(input, (int)right, (int)wrong);
    else
      print((int)wrong);
    *(_DWORD *)wrong = 0;
    *(_DWORD *)&wrong[4] = 0;
    *(_DWORD *)&wrong[8] = 0;
    *(_DWORD *)&wrong[12] = 0;
    *(_DWORD *)right = 0;
    *(_DWORD *)&right[4] = 0;
    *(_DWORD *)&right[8] = 0;
    *(_DWORD *)&right[12] = 0;
    system("pause");
    result = 0;
  }
  else
  {
    *(_DWORD *)right = 0;
    *(_DWORD *)&right[4] = 0;
    *(_DWORD *)&right[8] = 0;
    *(_DWORD *)&right[12] = 0;
    *(_DWORD *)wrong = 0;
    *(_DWORD *)&wrong[4] = 0;
    *(_DWORD *)&wrong[8] = 0;
    *(_DWORD *)&wrong[12] = 0;
    result = 0;
  }
  return result;
}

流程明了，大概流程是：

• 输入key
• 解码正确与错误的信息字串
• 检查输入字符范围有效性，应为字母+数字
• 检查输入长度，应为22
• 进入主要check流程

再看主check流程：

_DWORD *__cdecl check(char *input, char *right, char *wong)
{
  char v4; // [esp+4h] [ebp-47Ch]
  char v5; // [esp+88h] [ebp-3F8h]
  char v6; // [esp+10Ch] [ebp-374h]
  char v7; // [esp+190h] [ebp-2F0h]
  char v8; // [esp+214h] [ebp-26Ch]
  char v9; // [esp+298h] [ebp-1E8h]
  char v10; // [esp+31Ch] [ebp-164h]
  char v11; // [esp+3A0h] [ebp-E0h]
  int v12; // [esp+424h] [ebp-5Ch]
  int v13; // [esp+428h] [ebp-58h]
  int v14; // [esp+42Ch] [ebp-54h]
  int v15; // [esp+430h] [ebp-50h]
  int v16; // [esp+434h] [ebp-4Ch]
  int v17; // [esp+438h] [ebp-48h]
  int v18; // [esp+43Ch] [ebp-44h]
  int v19; // [esp+440h] [ebp-40h]
  char v20; // [esp+444h] [ebp-3Ch]
  char v21; // [esp+445h] [ebp-3Bh]
  char v22; // [esp+446h] [ebp-3Ah]
  char v23; // [esp+447h] [ebp-39h]
  char v24; // [esp+448h] [ebp-38h]
  char v25; // [esp+449h] [ebp-37h]
  char v26; // [esp+44Ah] [ebp-36h]
  char v27; // [esp+44Bh] [ebp-35h]
  char v28; // [esp+44Ch] [ebp-34h]
  char v29; // [esp+44Dh] [ebp-33h]
  char v30; // [esp+44Eh] [ebp-32h]
  char Src; // [esp+450h] [ebp-30h]
  char v32; // [esp+451h] [ebp-2Fh]
  char v33; // [esp+452h] [ebp-2Eh]
  char v34; // [esp+453h] [ebp-2Dh]
  char v35; // [esp+454h] [ebp-2Ch]
  char v36; // [esp+455h] [ebp-2Bh]
  char v37; // [esp+456h] [ebp-2Ah]
  char v38; // [esp+457h] [ebp-29h]
  int v39; // [esp+458h] [ebp-28h]
  int v40; // [esp+45Ch] [ebp-24h]
  char v41; // [esp+460h] [ebp-20h]
  char v42; // [esp+461h] [ebp-1Fh]
  char v43; // [esp+462h] [ebp-1Eh]
  char v44; // [esp+464h] [ebp-1Ch]
  char v45; // [esp+465h] [ebp-1Bh]
  char v46; // [esp+466h] [ebp-1Ah]
  char v47; // [esp+468h] [ebp-18h]
  char v48; // [esp+469h] [ebp-17h]
  char v49; // [esp+46Ah] [ebp-16h]
  char v50; // [esp+46Bh] [ebp-15h]
  char v51; // [esp+46Ch] [ebp-14h]
  int v52; // [esp+47Ch] [ebp-4h]

  v19 = 2;
  v43 = 0;
  v28 = input[2];
  v18 = 3;
  v27 = 0;
  v42 = input[1];
  v50 = input[12];
  v35 = input[16];
  v47 = input[9];
  v44 = 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];
  Src = input[13];
  v14 = 3;
  v38 = 0;
  v25 = input[5];
  v36 = input[17];
  v41 = *input;
  v22 = input[21];
  v13 = 3;
  v34 = 0;
  v20 = input[19];
  v49 = input[11];
  v37 = input[18];
  v12 = 3;
  v23 = 0;
  v39 = 0;
  v40 = 0;
  std::_Ref_count_obj<__ExceptionPtr>::_Ref_count_obj<__ExceptionPtr>(&v39);
  v52 = 0;
  sub_403AB0(&v11, &Src);
  sub_402B40(&v39, (int)&v11);
  sub_403AB0(&v10, &v41);
  sub_402B40(&v39, (int)&v10);
  sub_403AB0(&v9, &v47);
  sub_402B40(&v39, (int)&v9);
  sub_403AB0(&v8, &v24);
  sub_402B40(&v39, (int)&v8);
  sub_403AB0(&v7, &v28);
  sub_402B40(&v39, (int)&v7);
  sub_403AB0(&v6, &v44);
  sub_402B40(&v39, (int)&v6);
  sub_403AB0(&v5, &v35);
  sub_402B40(&v39, (int)&v5);
  sub_403AB0(&v4, &v20);
  sub_402B40(&v39, (int)&v4);
  if ( compare_tries(&v39, (int)&tries_ori) )
    xor_check(&v41, &v44, (int)&Src, (int)&v35, (int)right, (int)wong);
  else
    print((int)wong);
  v52 = -1;
  return sub_402AC0((void (__thiscall ****)(_DWORD, signed int))&v39);
}

主check流程包括三部分：

• 输入字串分组，生成8组子串
• 使用输入子串构造某数据结构，并与407E48处的数据作比对
• 输入字串作部分异或检查

数据结构及算法分析

正如题目名所言，还得从数据结构入手。

再细分析主check流程时，发现了类。类名为诸如TrieTree此类。经查此为一种叫Trie树或字典数的数据结构。做下搬运工，相关的基本知识如下：

Trie树，又称字典树、前缀树、单词查找树、键树，是一种多叉树形结构，是一种哈希树的变种。Trie这个术语来自于retrieval，发音为/tri:/ “tree”，也有人读为/traɪ/ “try”。Trie树典型应用是用于快速检索（最长前缀匹配），统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计，搜索提示等场景。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。
Trie树的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
 Trie树有3个基本性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
• 每个节点的所有子节点包含的字符都不相同

答案还是要从比对的目标数据身上找。进行交叉引用查找。
发现目标数据的生成在sub_401900函数中，初始化过程中完成。伪代码如下：

void *__thiscall sub_401900(void *this)
{
  char v2; // [esp+0h] [ebp-448h]
  char v3; // [esp+84h] [ebp-3C4h]
  char v4; // [esp+108h] [ebp-340h]
  char v5; // [esp+18Ch] [ebp-2BCh]
  char v6; // [esp+210h] [ebp-238h]
  char v7; // [esp+294h] [ebp-1B4h]
  char v8; // [esp+318h] [ebp-130h]
  char v9; // [esp+39Ch] [ebp-ACh]
  void *v10; // [esp+420h] [ebp-28h]
  char v11; // [esp+424h] [ebp-24h]
  char v12; // [esp+428h] [ebp-20h]
  char v13; // [esp+42Ch] [ebp-1Ch]
  char v14; // [esp+430h] [ebp-18h]
  char v15; // [esp+434h] [ebp-14h]
  char v16; // [esp+438h] [ebp-10h]
  char v17; // [esp+43Ch] [ebp-Ch]
  char Src; // [esp+440h] [ebp-8h]

  v10 = this;
  gen_char_1(&v12);                             // f
  gen_char_2(&v13);                             // t
  gen_char_3(&v17);                             // M
  gen_char_4(&v14);                             // 7
  gen_char_5(&Src);                             // 9
  gen_char_6(&v16);                             // k
  gen_char_7(&v15);                             // c
  gen_char_8(&v11);                             // kx
  gen_word(&v9, &Src);
  add_word((int)&9_4074B0, &v9);
  gen_word(&v8, &v17);
  add_word((int)&M_4075C0, &v8);
  gen_word(&v7, &v16);
  add_word((int)&k_407D38, &v7);
  gen_word(&v6, &v15);
  add_word((int)&c_4077E8, &v6);
  gen_word(&v5, &v14);
  add_word((int)&7_407A08, &v5);
  gen_word(&v4, &v13);
  add_word((int)&t_407C28, &v4);
  gen_word(&v3, &v11);
  add_word((int)&kx_4076D0, &v3);
  gen_word(&v2, &v12);
  add_word((int)&f_407B18, &v2);
  add_child(&M_4075C0, (int)&k_407D38);
  add_child(&t_407C28, (int)&9_4074B0);
  add_child(&7_407A08, (int)&M_4075C0);
  add_child(&t_407C28, (int)&f_407B18);
  add_child(&c_4077E8, (int)&7_407A08);
  add_child(&root_4078F8, (int)&kx_4076D0);
  add_child(&c_4077E8, (int)&t_407C28);
  add_child(&root_4078F8, (int)&c_4077E8);
  set_count(&c_4077E8, 0);                      // c
  set_count(&k_407D38, 1);                      // k
  set_count(&9_4074B0, 1);                      // 9
  set_count(&t_407C28, 1);                      // t
  set_count(&7_407A08, 1);                      // 7
  set_count(&M_4075C0, 2);                      // M
  set_count(&root_4078F8, 0);                   // root
  set_count(&f_407B18, 1);                      // f
  set_count(&kx_4076D0, 1);                     // kx
  set_tree_node(&tries_ori, (int)&root_4078F8);
  return v10;
}

原来此处相当于是手动生成字典树的数据结构，校验处是用类生成。结合检验处生成字典树的代码，推测字典树节点的数据结构如下：

00000000 TrieTreeNode    struc ; (sizeof=0x110, mappedto_50)
00000000 p_methods       dd ?
00000004 words           db 128 dup(?)
00000084 words_size      dd ?
00000088 childs          dd 32 dup(?)
00000108 child_num       dd ?
0000010C count           dd ?
00000110 TrieTreeNode    ends

set_count函数是设置单词计数的（检验时用到）。似乎这个单词计数对词频统计很有用啊。

到此，关于字典树中最重要的一部分数据结构出来了，那节点的check代码就好理解了。节点的check代码如下：

char __thiscall node_compare(TrieTreeNode *this, TrieTreeNode *a2)
{
  const char *v3; // eax
  char v4; // [esp+0h] [ebp-A4h]
  int *v5; // [esp+84h] [ebp-20h]
  int v6; // [esp+88h] [ebp-1Ch]
  int v7; // [esp+8Ch] [ebp-18h]
  int *v8; // [esp+90h] [ebp-14h]
  int v9; // [esp+94h] [ebp-10h]
  _DWORD *v10; // [esp+98h] [ebp-Ch]
  int *v11; // [esp+9Ch] [ebp-8h]
  TrieTreeNode *v12; // [esp+A0h] [ebp-4h]

  v12 = this;
  if ( str_compare(this->words, (int)a2->words) )
    return 0;
  v7 = v12->child_num;
  v6 = a2->child_num;
  if ( v7 != v6 )
    return 0;
  if ( v12->count != a2->count )
    return 0;
  v10 = v12->childs;
  v11 = v12->childs;
  v5 = &v12->childs[v12->child_num];
  while ( v11 != v5 )                           // check child
  {
    v9 = *v11;
    v3 = (const char *)sub_403670(v9, &v4);
    v8 = (int *)sub_403830(&a2->p_methods, v3);
    if ( !v8 )
      return 0;
    if ( j_node_compare(v8, v9) )
      return 0;
    ++v11;
  }
  return 1;
}

可以看出这是一个递归check，不仅check了节点的字符，还check了子节点数和单词计数。所以此题目的就是通过输入字串构造一个与预设字典树完全相同的字典树。

目标字典树的结构及其单词可以直接写出来，然后就是这些单词的符合异或cehck点的排列组合了。

下面是异或check算法，检查输入的4个子串的位置。

int __cdecl xor_check(char *a1, char *a2, char *a3, char *a4, char *wrong, char *right)
{
  int result; // eax

  if ( (a1[1] ^ *a1) != 84 || (a2[1] ^ *a2) != 19 || (a3[1] ^ a3[2]) != 18 || (a4[2] ^ a4[1]) != 77 )
    result = print(right);                      // right
  else
    result = print(wrong);
  return result;
}

求解

用于检验的目标字典树结构大致为:

        root
      /     \
     kx       c
            /  \
           7    t
          /    /  \    
         M    9    f
       / 
      k

输入的字符范围就在其中。而且输入字串为kx ctf ct9 c7Mk的组合或前半部分组合，而且通过字典树计数限制了子串出现与否及重复出现次数。
通过上面的计数，可以得到所有出现的单词：

kx c7 c7M(两次) c7Mk ct ct9 ctf

到这里就比较明晰了。

再加上异或确定的4组子串组合及顺序，这个排列组合可以就可以完全确定了。

输入分组情况如下：

第1组： 0/1
第2组： 2/3
第3组： 4/5/6
第4组： 7/8
第5组： 9/10/11/12
第6组： 13/14/15
第7组： 16/17/18
第8组： 19/20/21

异或检查输入的第1、4、6、7组子串。

如下为4个异或运算的可能取值。

a:5
b:6
c:7
d:0
e:1
f:2
g:3
l:8
m:9
0:d
1:e
2:f
3:g
5:a
6:b
7:c
8:l
9:m
========================
a:r
b:q
c:p
d:w
e:v
f:u
g:t
i:z
j:y
k:x
p:c
q:b
r:a
t:g
u:f
v:e
w:d
x:k
y:j
z:i
========================
a:s
b:p
c:q
d:v
e:w
f:t
g:u
h:z
j:x
k:y
p:b
q:c
s:a
t:f
u:g
v:d
w:e
x:j
y:k
z:h
========================
t:9
u:8
x:5
y:4
z:7
4:y
5:x
7:z
8:u
9:t

综合上面条件，所以先出的4组为

0/1  7/8  13/14/15 16/17/18
c7   kx   ctf      ct9

子串中只有一个字串是4字节。所以9/10/11/12就为c7Mk。

0/1 2/3 4/5/6 7/8 9/10/11/12 13/14/15 16/17/18 19/20/21
c7            kx  c7Mk       ctf      ct9

由于计数除了c7M为2，其它都为1。所以剩下的3字节的两个位置就是此子串了。

0/1 2/3 4/5/6 7/8 9/10/11/12 13/14/15 16/17/18 19/20/21
c7      c7M   kx  c7Mk       ctf      ct9      c7M

还剩下一个2字节的子串。为了满足计数要求，没用过的只有ct了。
最后结果为:c7ctc7Mkxc7Mkctfct9c7M

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法