-
-
[原创]看雪CTF2018 - 2018CMv4 Writeup
-
2018-6-20 20:07
-
本题的关键在于对 TrieTree 四个数据结构的识别，分别是 TrieTree，TrieTreeNode，Children，String，如下图1所示：
图 1
主函数逆向如下图2：
main函数中判断输入的字符串长度不能超过22，然后进入输入字符串的验证函数 check_input_key，如下图3：
图 3
该函数主要功能是将输入的字符串分别取出7个子字符串，插入到一个 TireTree 中，并与一个全局 TrieTree 进行比较，如果两个 TrieTree 相同，则进入last_check函数进行最后约束条件的比较，如下图4：
图 4
现在分析TrieTree插入算法，如下图5-8：
图 5
首先，在当前节点的所有子节点中，查找与需要插入的字符串具有公共子字符串的子节点，如果没有找到具有公共子字符串的节点，将该字符串插入到当前节点的子节点中，即图8中 case 5。如果发现具有公共子字符串的子节点，其中又分四种情况，第一种情况，公共子字符串是两者的真子集，以下图6方式插入；
图 6
第二种情况，要插入的字符串 str 是找到 Node 的子字符串，如图7所示，将 Node 中剩余部分以一个节点形式插入到 Node 的子节点中；
图 7
第三种情况，找到的 Node 节点是 str 的子字符串，如图8中case 3所示，截取str的剩余部分，插入到Node的子节点中；第四种情况，str 和 找到的 Node 节点的字符串相同，则将 Node 节点 occurence 加一即可。
图 8
TrieTree比较算法可类比分析，在此不再赘述。现在来看一下全局TrieTree的构造，如图9所示，
图 9
即构造了一个相对简单的TrieTree，如图10所示，
即输入的Key构造的TrieTree应该与之相同，再结合图4中提到的约束条件，可知，
‘c' ^ '7' == 84
'k' ^ 'x' == 19
't' ^ 'f' == 18
't' ^ '9' == 77
可以得出正确的Key应该为：c7ctc7Mkxc7Mkctfct9c7M
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
 楼主你看 为啥我的IDA 7.0 出来的函数名称完全不知用途，而你的截图中 函数名字就能够知道名称？（恳求解答。
|
|
|
|
|
|
函数名字是我自己标注的。我用的是IDA 7.0 Pro，网上应该有一大堆可以下载吧，如果你用的是IDA 7.0，应该和你的一样。 |
|
|
多谢 |
|
|
|
|
|
|
Adventure
