首页
论坛
课程
招聘
[原创]看雪.京东 2018CTF 第二题 数据结构 AVTrieTree 详解
2018-6-19 20:58 2243

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

2018-6-19 20:58
2243

目录

0x00 测试

吐槽一下:这几天忙,没注意时间,居然错过了第一题。。。

 

先看下程序语言
ExeInfo

 

随便输入点什么,查看报错内容

 

Test

 

拖进IDA,居然被挑衅了

 

IDA_1

 

果然字符串没发现什么有用信息,
根据数据结构的题目,这是一个AVTrieTree
只分析过平衡二叉树,对这个树并不太了解

 

IDA_2

0x01 IDA分析

以下代码均为配合OD调试整理

 

程序主函数
IDA_main

 

很多赋值操作
IDA_Check_1

 

初始化操作
IDA_Check_2

 

TrieTree核心比较函数
IDA_Check_3

0x02 OD调试

老薛语录:观察数据变化,注重大局,不拘小节

  • 新建节点
    由代码可知,并未进行初始化,
    直接在0x20*4的位置保存当前节点字符串长度,
    中间会有很多无效数据,给后面分析造成很大不便,
    这里我们手动初始化置0,
    下面显示红色部分字节,大部分为手动置0;
    TreeNode
    ecx传参,可知节点是一个类或结构体
    TreeNode
    新建节点
    TreeNode

  • 插入节点
    push 子节点,ecx传入this指针
    AddNode
    this指针指向位置
    TrieTree
    第一个字段为vftable虚函数表,
    TrieTree
    第二个字段为根节点,指向位置大小为0x110
    TrieTree
    添加节点后数据变化
    TrieTree

  • TrieTree比较
    节点插入完毕,根据代码可得知对树作比较
    内存中可以看到根节点下只有两个子节点
    TrieTree
    跟踪节点,可以遍历到这几个字符
    kx,c,7,M,k,t,9,f
    ChildNode
    ChildNode
    ChildNode
    ChildNode
    ChildNode
    ChildNode
    ChildNode
    ChildNode
    结构如下
    Structure
    到这基本差不多猜出了密码
    8个节点,组合成这几个单词
    kx,c7,c7m,c7mk,ct,ctf,ct9
    好像少了一个单词?
    这里还有一个小坑
    有一个单词是重复的
    通过单步跟踪找到M
    原来M使用了2次
    ChildNode
    两个树比较相同后,进入下一个比较函数,
    检查字符串顺序
    ChildNode
    Bingo!
    Correct

0x03 TrieTree内存结构

经过以上分析,可得知本程序中TrieTree内存结构

0x04 心得总结

对TrieTree不熟悉,到节点比较位置就卡住了,分析了一下午,没什么成果,搜索了一些相关资料,参考demo,才顺利搞定!

  • 两个小坑
    1.输入的密码生成的树是局部变量,在堆栈中,并且没有初始化,垃圾数据较多,给分析造成很大不便
    2.节点的最后一个字段是以当前字符为结尾的单词数,这个容易被忽略

  • 收获
    又多熟悉了一种数据结构

0x05 致谢

感谢15PB各位老师的辛勤教导~
感谢看雪各位大佬的无私分享~


看雪学院推出的专业资质证书《看雪安卓应用安全能力认证 v1.0》(中级和高级)!

最后于 2018-6-20 09:10 被DKni编辑 ,原因:
收藏
点赞1
打赏
分享
最新回复 (5)
雪    币: 5638
活跃值: 活跃值 (425)
能力值: ( LV17,RANK:1185 )
在线值:
发帖
回帖
粉丝
holing 活跃值 15 2018-6-20 12:33
2
0
不知道Trie但是还是逆出来了,这个我佩服
-----------------------------------------------------------
好吧还是参考了资料的(当我没说

不知道这题如果不给提示能有多少人能逆出来(逃
最后于 2018-6-20 13:20 被holing编辑 ,原因:
雪    币: 3870
活跃值: 活跃值 (114)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
DKni 活跃值 1 2018-6-20 21:26
3
0
holing 不知道Trie但是还是逆出来了,这个我佩服-----------------------------------------------------------好吧还是参考了资料的(当我没说不知道这题 ...
膜拜大佬,没提示的话估计得少个三分之一吧,哈哈~
雪    币: 4819
活跃值: 活跃值 (19)
能力值: ( LV4,RANK:45 )
在线值:
发帖
回帖
粉丝
HeyLXF 活跃值 2018-6-20 22:08
4
0
holing 不知道Trie但是还是逆出来了,这个我佩服-----------------------------------------------------------好吧还是参考了资料的(当我没说不知道这题 ...
Orz。大佬能不能放源码呢
雪    币: 5638
活跃值: 活跃值 (425)
能力值: ( LV17,RANK:1185 )
在线值:
发帖
回帖
粉丝
holing 活跃值 15 2018-6-21 05:06
5
0
HeyLXF Orz。大佬能不能放源码呢
https://bbs.pediy.com/thread-222959.htm
已发
雪    币: 139
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
王小祁 活跃值 2018-8-7 09:45
6
0
游客
登录 | 注册 方可回帖
返回