首页
论坛
课程
招聘
[原创]看雪CTF2018 - 2018CMv4 Writeup
2018-6-20 20:07 2962

[原创]看雪CTF2018 - 2018CMv4 Writeup

2018-6-20 20:07
2962

      本题的关键在于对 TrieTree 四个数据结构的识别,分别是 TrieTree,TrieTreeNode,Children,String,如下图1所示:


图 1

主函数逆向如下图2:

图 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


安卓应用层抓包通杀脚本发布!《高研班》2021年3月班开始招生!

收藏
点赞0
打赏
分享
最新回复 (9)
雪    币: 6817
活跃值: 活跃值 (153)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
聖blue 活跃值 2018-6-20 22:52
2
0
雪    币: 3676
活跃值: 活跃值 (186)
能力值: ( LV6,RANK:93 )
在线值:
发帖
回帖
粉丝
Adventure 活跃值 2018-6-21 10:23
3
0
楼主的IDA主题哪里搞的
雪    币: 926
活跃值: 活跃值 (13)
能力值: ( LV12,RANK:321 )
在线值:
发帖
回帖
粉丝
Iamakiller 活跃值 2 2018-6-21 12:16
4
0
Adventure 楼主的IDA主题哪里搞的
https://github.com/zyantific/IDASkins
最后于 2018-6-21 12:17 被Iamakiller编辑 ,原因:
雪    币: 1012
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Hauk 活跃值 2018-7-22 10:48
5
0

楼主你看 为啥我的IDA 7.0 出来的函数名称完全不知用途,而你的截图中 函数名字就能够知道名称?(恳求解答。
雪    币: 1012
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Hauk 活跃值 2018-7-22 10:50
6
0
或者说 楼主可否提供一下你使用的IDA版本号 或者下载地址 不胜感激
雪    币: 926
活跃值: 活跃值 (13)
能力值: ( LV12,RANK:321 )
在线值:
发帖
回帖
粉丝
Iamakiller 活跃值 2 2018-7-22 20:08
7
0
Hauk 或者说 楼主可否提供一下你使用的IDA版本号 或者下载地址 不胜感激
函数名字是我自己标注的。我用的是IDA 7.0 Pro,网上应该有一大堆可以下载吧,如果你用的是IDA 7.0,应该和你的一样。
雪    币: 1012
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
Hauk 活跃值 2018-7-22 21:58
8
0
Iamakiller 函数名字是我自己标注的。我用的是IDA 7.0 Pro,网上应该有一大堆可以下载吧,如果你用的是IDA 7.0,应该和你的一样。
多谢
雪    币: 1214
活跃值: 活跃值 (139)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
陈jack 活跃值 2018-7-24 15:11
9
0
写的很好
雪    币: 2749
活跃值: 活跃值 (58)
能力值: ( LV12,RANK:214 )
在线值:
发帖
回帖
粉丝
htg 活跃值 2 2018-12-3 18:55
10
0
数据结构识别工具真的很棒
游客
登录 | 注册 方可回帖
返回