首页
论坛
课程
招聘
[原创]第二题 数据结构 的分析
2018-6-20 02:41 1680

[原创]第二题 数据结构 的分析

2018-6-20 02:41
1680
本题目是一个字典树的数据结构,关键是对字典树的理解,程序在一开始就初始化了静态的字典树结构。在程序里面,已经能看到字典树结构,当然,最开始并不知道是字典树...
先拖到IDA里面,进入到main,略去无关紧要的代码,直接到 sub_12F1C40

在sub_12F1C40里面,可以明显地看到程序将输入的22个字符截成了8段,长度依次是2, 2, 3, 2, 4, 3, 3, 3,截取出的字符串通过 sub_12F3AB0 函数做过第一步变换,再将变换的结果通过sub_12F2B40函数做第二次变换。跳转到sub_12F3AB0函数,查看代码后可定义出第一个结构体:
// 保存字符串的结构
struct _st_dataobj
{
char szBufs[0x80];
unsigned int buflen;
};
然后进入 sub_12F2B40 函数,该函数的实现较复杂,也没有打算完全去理解它,只需要知道它把保存字符串的结构体存到了一个数据结构中就可以了。经过8次调用,数据结构已经生成成功,然后调用到sub_12F30E0函数,该函数返回成功调用到sub_12F1B80,失败就直接打印出错误信息。可基本确定这至少是主要的对比函数之一

 sub_12F1B80函数就两个输入,一个是根据输入生成的结构,一个是全局的dword_12F7E48,查找该变量的交叉引用,发现到一个关键的虚函数表

程序告诉了我们这是一个字典树,估且当做字典树来分析一下。既然dword_12F7E48是对比的关键之一,首先查看一下该变量的初始化。直接交叉引用,找到关键的初始化代码 sub_12F1900, 在这个函数里面发现对sub_E43AB0和sub_E43620的几次调用,生成了几个标识明显的数据结构,把sub_E43AB0的第一个参数转换成前面定义好的 struct _st_dataobj, 同时通过sub_E43620函数的第一个参数,可以猜测出字典树节点的结构体长度为272字节,其中,第4字节开始为一个_st_dataobj的结构体。根据字典树的定义,每一个节点包括有字符串(根节点为空)、子节点数组、个数等,再结合sub_E43940,sub_E43650,以及节点结构的长度,定义出节点结构体:
// 字典树节点定义
struct _st_trie_tree_node
{
void *pvftables;
_st_dataobj pdataobj;
struct _st_trie_tree_node * arChilds[32];
unsigned int counts; // 描述子节点的个数
unsigned int repeats;
};


结构定义好后,在相应的位置转换成结构/结构指针,同时动态调试,在子函数sub_E43730里面,查看到了初始化的和根据输入的字符串生成的字典树对比,因为定义好了结构,直接在监视器里面查看正确的树的节点的值,根据字典树的定义,还原出初始化的树,

,还原出来的树如下:
root
kx    -  c
NULL |   7 - t
  M | 9 - f
  k
正确的树出来了,根据树再构造单词,可以推测出单词为如下的序列: kx c7 c7M ct c7Mk c7M ct9 ctf
去掉空格后执行调试,sub_13130E0函数测试通过,进入到sub_1311B80 函数,测试不通过。很简单了,调整序列,让 sub_1311B80测试通过即可,最终获得结果 c7 ct c7M kx c7Mk ct9 ctf c7M

附件中是 IDA7的idb文件。有详细标注


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

上传的附件:
收藏
点赞0
打赏
分享
最新回复 (2)
雪    币: 6327
活跃值: 活跃值 (3391)
能力值: ( LV12,RANK:200 )
在线值:
发帖
回帖
粉丝
pureGavin 活跃值 2 2018-8-16 23:29
2
0
就想问为什么你的函数地址是16进制显示的,刚开始看我找了半天也没找到。。。(怎么改
雪    币: 6327
活跃值: 活跃值 (3391)
能力值: ( LV12,RANK:200 )
在线值:
发帖
回帖
粉丝
pureGavin 活跃值 2 2018-8-16 23:31
3
0
还有就是截取了八份这个我看到了,但是每份的长度你是怎么看出来的??(我是新手,这是我第一次看树结构的逆向)
游客
登录 | 注册 方可回帖
返回