-
-
[原创]看雪.京东 2018CTF 第二题 数据结构
-
发表于:
2018-6-19 14:48
2173
-
[原创]看雪.京东 2018CTF 第二题 数据结构
根据类名TrieTreeNode可以得知，本题使用的数据结构为字典树。主要涉及的类有TrieTreeNodeAbs,TrieTreeNode,TrieTreeStatic, TrieTreeNodeStatic, TrieTreeStatic。
其中TrieTreeNodeAbs,TrieTreeNode,TrieTree用于根据用户的输入生成字典树，TrieTreeNodeStatic, TrieTreeStatic用于程序自己构造字典树。
首先输入为22个字符，全都是字母或者数字。并且程序会将22个字符分成8组，例如输入为0123456789abcdefghijkl时，会被分成def,01, 9abc,456,23,78,ghi,jkl。
TrieTreeNodeAbs的布局如下：
1 2 3 4 5 | class TrieTreeNodeAbs size(0x84)
+---
0 | char chars[0x80];
0x80 | int len;
+---
|
TrieTreeNode的布局如下：
1 2 3 4 5 6 7 8 9 10 11 | class TrieTreeNode size(0x110)
+---
0 | void *vftable;
| +--- (base class TrieTreeNodeAbs)
4 | | char chars[0x80];
0x84 | | int len;
| +---
0x88 | TrieTreeNode *child_nodes[32];
0x108 | int child_nums;
0x10c | int complete;
+---
|
其中TrieTreeNode.complete为当前节点所表示的字符串的个数。
TrieTree的布局如下：
1 2 3 4 5 | class TrieTree size(0x8)
+---
0 | void *vftable;
0x4 | TrieTreeNode *node;
+---
|
TrieTreeNodeStatic, TrieTreeStatic的布局和TrieTreeNode, TrieTree类似。
程序生成的字典树为
1 2 3 4 5 6 7 8 9 | "", 2, 0
/ \
"kx", 0, 1 "c", 2, 0
/ \
"7", 1, 1 "t", 2, 1
/ / \
"M", 1, 2 "9",0,1 "f",0,1
/
"k", 0, 1
|
其中"kx", 0, 1表示
1 2 3 | trieTreeNode.chars = "kx"
trieTreeNode.child_nums = 0
trieTreeNode.complete = 1
|
也就是说，程序生成字典树所用的八个字符串为"kx", "c7", "c7M", "c7M", "c7Mk", "ct", "ct9", "ctf"。当用户输入生成的字典树与程序生成的字典树相同，并满足input[0] ^ input[1] == 0x54等约束时验证成功。所以flag为c7ctc7Mkxc7Mkctfct9c7M。
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2018-6-19 14:59
被iweizime编辑
，原因：
