首页
论坛
课程
招聘
[原创]看雪.京东 2018CTF 第二题 数据结构
2018-6-19 14:48 926

[原创]看雪.京东 2018CTF 第二题 数据结构

2018-6-19 14:48
926

根据类名TrieTreeNode可以得知,本题使用的数据结构为字典树。主要涉及的类有TrieTreeNodeAbs,TrieTreeNode,TrieTreeStatic, TrieTreeNodeStatic, TrieTreeStatic

 

其中TrieTreeNodeAbs,TrieTreeNode,TrieTree用于根据用户的输入生成字典树,TrieTreeNodeStatic, TrieTreeStatic用于程序自己构造字典树。

 

首先输入为22个字符,全都是字母或者数字。并且程序会将22个字符分成8组,例如输入为0123456789abcdefghijkl时,会被分成def,01, 9abc,456,23,78,ghi,jkl

 

TrieTreeNodeAbs的布局如下:

      class TrieTreeNodeAbs      size(0x84)
      +---
0     | char chars[0x80];
0x80  | int  len;
      +---

TrieTreeNode的布局如下:

      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的布局如下:

      class TrieTree           size(0x8)
      +---
0     | void *vftable;
0x4   | TrieTreeNode *node;
      +---

TrieTreeNodeStatic, TrieTreeStatic的布局和TrieTreeNode, TrieTree类似。

 

程序生成的字典树为

              "", 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表示

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


[招聘] 欢迎你加入看雪团队!

最后于 2018-6-19 14:59 被iweizime编辑 ,原因:
收藏
点赞0
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回