看雪CTF 2018第2题 Writeup
一、概览
程序的主要逻辑：传入一个字符串，长度为22
004022BC |. 837D AC 16 cmp dword ptr [ebp-0x54], 0x16
sub_401360和sub_401200分别正确和错误信息解密出来，“Answer correct!.”、“Answer is Wrong.”
sub_00402180检查输入，要求为数字或大小写字母（a-z,A-Z），否则打印“Answer is wrong”
0018FEE4 0018FEFC ASCII"123abcABC"
0018FEE8 0018FF2C ASCII "Answer isWrong"
核心函数sub_401C40，这里是程序主要逻辑。
004022DC |. E8 5FF9FFFF call 00401C40
0018FEE0 0018FEFC ASCII"123abcABC123abcABC123a"
0018FEE4 0018FF1C ASCII "Answercorrect!"
0018FEE8 0018FF2C ASCII "Answer isWrong"
sub_401C40里将输入的字符串切割成八个部分SN[14][15][16]、SN[1][2]、SN[10][11][12][13]、SN[5][6][7]、SN[3][4]、SN[8][9]、SN[17][18][19]、SN[20][21][22]进行处理，直接调试看内存可以得出。
当时跟踪到sub_402B40就晕菜了。不知道程序采用了啥数据结构，搜索字符串发现了AVTrieTree。
二、TrieTree相关知识
Trie树，又称单词查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
trie树的性质：
1.根节点的字符串是空
2.其它节点字符串不为空
3.一个节点的所有子节点的所有字符串，不能有相同前缀：比方说abc和agf就不能在同一个节点下面，因为他们有相同前缀a
4.从根节点开始，走到任意一个节点，将走过的路径上的所有字符串拼接起来，那个终点节点的数便是拼接起来的字符串的映射到的频率（或者不一定是频率，也可以是某个其它value）。比方说，这张图，就很明显了。romane，就映射到1，ruber，就映射到5。
三、详细分析
将输入切割成8份后进入sub_403AB0完成节点初始化，sub_402B40将其插入到TrieTree中。
sub_4030E0将比较根据输入字符串生成的TrieTree和系统默认的TrieTree，两者相等的话，sub_401B80进行最后一轮检查。
sub_401B80：如果满足sn[1] xor sn[2]=0x54，sn[8] xor sn[9]=0x13，sn[15] xor sn[16]=0x12，sn[18] xor sn[19]=0x4D，则打印"Answer correct!"
004020D1 |. E8 AAFAFFFF call 00401B80
0018FA40 0018FEB8 ASCII "12"=SN[1][2]
0018FA44 0018FEBC ASCII "BC"=SN[8][9]
0018FA48 0018FEA8 ASCII "bcA"=SN[14][15][16]
0018FA4C 0018FEAC ASCII "BC1"=SN[17][18][19]
0018FA50 0018FF1C ASCII "Answercorrect!"
0018FA54 0018FF2C ASCII "Answer isWrong"
{
18FEB8[0] xor 18FEB8[1]=0x54 --> sn[1] xorsn[2]=0x54
18FEBC[0] xor 18FEBC[1]=0x13 --> sn[8] xorsn[9]=0x13
18FEA8[2] xor 18FEA8[1]=0x12 --> sn[15] xorsn[16]=0x12
18FEAC[1]xor 18FEAC[2]=0x4D --> sn[18] xorsn[19]=0x4D
}
现在需要找出生成默认TrieTree的地方。根据dword_407E48的引用，定位到sub_401900。
调试过程中总结出TrieTree的数据结构如下，Node+0x4为节点表示的单词；Node+0x88存储子节点地址，最多有32个子节点；Node+0x108存储子节点数；Node+0x10C为单词引用次数，即词频。
00000000 treeNode struc ; (sizeof=0x110, mappedto_43)
00000000 constAddr dd ?
00000004 string db 128dup(?)
00000084 len dd ?
00000088 childNode dd 32 dup(?)
00000108 childNum dd ?
0000010C stringNum dd ?
00000110 treeNode ends
下图为调试过程中节点c的存储视图，可以对照上面的数据结构看。
系统默认的TrieTree如下图所示
8个节点组成了这些单词：kx, c7,ct, c7M, c7M, c7Mk, ct9, ctf。这些单词不知道哪个先哪个后，利用sub_401B80中的4个异或等式，最后得出flag：c7ctc7Mkxc7Mkctfct9c7M
sub_402B60生成的TrieTree如下图所示。sub_402B60分5种情况将输入字串插入到TrieTree中。
