首页
论坛
课程
招聘
[原创] 京东-看雪 2018 - 春季赛 第二题 - 数据结构
2018-6-19 01:30 1450

[原创] 京东-看雪 2018 - 春季赛 第二题 - 数据结构

aqs 活跃值
5
2018-6-19 01:30
1450

功能分析

拿到的是一个 win32 控制台程序

2018CMv4.exe: PE32 executable (console) Intel 80386, for MS Windows

运行一下, 输入一个字符串,返回正确或错误,没有其他

11111111
Answer is Wrong
请按任意键继续. . .

ida 打开程序看看

 

main 主要逻辑如下,传入一个字符串,长度为 22
对传入的 字符串有一个check 函数,一个字符一个字符判断

  • (chr | 0x20) 是不是在 ord('a') ~ ord('z') 的范围
  • chr 是否在 ord('0') 或 ord('9') 范围

字符check 过了之后会调用一个 main_logic_401C40 函数,这里就是主要逻辑了

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int result; // eax
  char input[32]; // [esp+10h] [ebp-44h]
  int corr; // [esp+30h] [ebp-24h]
  int v6; // [esp+34h] [ebp-20h]
  int v7; // [esp+38h] [ebp-1Ch]
  int v8; // [esp+3Ch] [ebp-18h]
  int wron; // [esp+40h] [ebp-14h]
  int v10; // [esp+44h] [ebp-10h]
  int v11; // [esp+48h] [ebp-Ch]
  int v12; // [esp+4Ch] [ebp-8h]

  input_401170("%s", input, 32);
  correct(&corr); // 生成 correct 字符串
  wrong(&wron);   // 生成 wrong 字符串
  if ( char_check_402180(input, &wron) )
  {
    if ( &input[strlen(input) + 1] - &input[1] == 0x16 )// 长度==22
      main_logic_401C40(input, &corr, &wron);
    else
      printsome(&wron);
  .....

main logic 函数, 将我们输入的字符串切割,然后存放到局部变量上
有点乱,后面直接调试看内存可以比较快看出来

  v19 = 2;
  v43 = 0;
  v28 = input[2];
  v18 = 3;
  v27 = 0;
  v42 = input[1];
  v50 = input[12];
  s4 = input[16];
  v47 = input[9];
  s2 = input[7];
  v48 = input[10];
  v45 = input[8];
  v21 = input[20];
  v17 = 4;
  v51 = 0;
  v33 = input[15];
  v16 = 2;
  v30 = 0;
  v15 = 2;
  v46 = 0;
  v26 = input[6];
  v32 = input[14];
  v24 = input[4];
  v29 = input[3];
  s3 = input[13];
  v14 = 3;
  v38 = 0;
  v25 = input[5];
  v36 = input[17];
  s1 = *input;
  v22 = input[21];
  v13 = 3;
  v34 = 0;
  v20 = input[19];
  v49 = input[11];
  v37 = input[18];
  v12 = 3;
  v23 = 0;
  tree = 0;
  v40 = 0;
  std::_Ref_count_obj<__ExceptionPtr>::_Ref_count_obj<__ExceptionPtr>(&tree);
  v52 = 0;

_Ref_count_obj 这个函数进行一些内存分配的操作
注意 &TrieTree::`vftable' 这里,这是 c++ 对象的写法
Tire Tree ?? 想起题目名字叫数据结构,是不是和这个有关?
找了一下资料,Tire Tree ,字典树,大概就是数据放到树上方便检索的操作
这个函数主要就是 创建一个 TireTree 对象,然后返回其指针,后续操作都在这个上面进行

_DWORD *__thiscall std::_Ref_count_obj<__ExceptionPtr>::_Ref_count_obj<__ExceptionPtr>(_DWORD *this)
{
  _DWORD *v1; // ST14_4
  _DWORD *Memory; // ST0C_4

  v1 = this;
  sub_403070(this);
  *v1 = &TrieTree::`vftable';
  Memory = operator new(0x110u);
  v1[1] = sub_403100(Memory);
  return v1;
}

再次回到 main_logic 函数 后续的内容
这里在两个函数重复操作了 8 次, 后续分析之后发现这里是

  • 前面将传入的 22 个 byte 的字符串切割成 八个部分
  • 对每个子串 调用 下面的 store, insert 函数,其实就是插入前面分配的树上, 就是将子串插入到字典树上的操作了
    在 对应的 store 函数上下断点,调试一下就可以看出插入的顺序
    下面的注释是调试出来的对应的 输入字符串的 下标
    store1_403AB0(&v11, &s3);                     // 13 14 15
    insert_402B40(&tree, &v11);
    store1_403AB0(&v10, &s1);                     // 0 1
    insert_402B40(&tree, &v10);
    store1_403AB0(&v9, &v47);                     // 9 10 11 12
    insert_402B40(&tree, &v9);
    store1_403AB0(&v8, &v24);                     // 4 5 6
    insert_402B40(&tree, &v8);
    store1_403AB0(&v7, &v28);                     // 2 3
    insert_402B40(&tree, &v7);
    store1_403AB0(&v6, &s2);                      // 7 8
    insert_402B40(&tree, &v6);
    store1_403AB0(&v5, &s4);                      // 16 17 18
    insert_402B40(&tree, &v5);
    store1_403AB0(&v4, &v20);                     // 19 20 21
    insert_402B40(&tree, &v4);
    
    插入完成之后 我们就得到了一棵字典树了,后面会 和一个全局的 gtree_407E48
    进行比较
    其实就是我们传入一个字符串,切割插入字典树之后看看和预先定义好的一棵树是不是一样
  if ( cmp_tree_4030E0(&tree, &gtree_407E48) )  // maybe 判断两棵树是不是一样
    last_check_401B80(&s1, &s2, &s3, &s4, correct, wrong);
  else
    printsome(wrong);
  v52 = -1;
  return sub_402AC0(&tree);
}

如果两个树一样,后面还会有一个 check 函数, 对 字符串 子串进行一些值的判断,现在还没有用,这个可以在后面帮助反推输入的值

int __cdecl last_check_401B80(char *chr_0_1, char *char_7_8, int char_13_14_15, int char_16_17_18, int correct, int wrong)
{
  int result; // eax

  if ( (chr_0_1[1] ^ *chr_0_1) != 0x54
    || (char_7_8[1] ^ *char_7_8) != 0x13
    || (*(char_13_14_15 + 1) ^ *(char_13_14_15 + 2)) != 0x12
    || (*(char_16_17_18 + 2) ^ *(char_16_17_18 + 1)) != 0x4D )
  {                                             // 2 个 byte 的比较
    result = printsome(wrong);
  }
  else
  {
    result = printsome(correct);
  }
  return result;
}

okay 到这里思路就很明确了,程序利用我们的输入构建了一棵字典树
这棵树要和一棵预先准备好的树一样,那么我们就需要先找到这棵树
ida 看一下引用
找到函数 sub_40190
看其调用可以知道
这里程序是通过

_scrt_common_main_seh

这个函数进行了一些预处理,然后再通过它调用main 函数,去除一些初始化的操作, 预先准备好的字典树 的初始化大体是下面
程序调用了 initterm 函数,这个函数的效果大致是传两个地址,这两个地址之间的值不为0的 指针都当作函数从头到尾调用一遍

  else
  {
    dword_407464 = 1;
    if ( initterm_e(&unk_405154, &unk_405160) )
      return 255;
    initterm(&somefunc_40511C, &unk_405150);
    dword_407464 = 2;
  }

somefunc 里面是下面, 前面是一些初始化 TireTree 对象的操作,主要是最后一个函数

.rdata:0040511C somefunc_40511C db    0                 ; DATA XREF: __scrt_common_main_seh(void)+71↑o
.rdata:0040511D                 db    0
.rdata:0040511E                 db    0
.rdata:0040511F                 db    0
.rdata:00405120                 dd offset sub_40433B
.rdata:00405124                 dd offset sub_401000
.rdata:00405128                 dd offset sub_401030
.rdata:0040512C                 dd offset sub_401050
.rdata:00405130                 dd offset sub_401070
.rdata:00405134                 dd offset sub_401090
.rdata:00405138                 dd offset sub_4010B0
.rdata:0040513C                 dd offset sub_4010D0
.rdata:00405140                 dd offset sub_4010F0
.rdata:00405144                 dd offset sub_401110
.rdata:00405148                 dd offset sub_401130

.rdata:0040514C                 dd offset sub_401150
.rdata:00405150 unk_405150      db    0

sub_401150 函数包含了 我们用于比较的字典树的生成的操作
主要逻辑如下
下面的几个函数都是一样的操作,生成一个字符串然后存放到 一个地址里面
比如 f_4015D0(&v12) 这个函数 生成了 'f' 然后存放到 v12 这个局部变量里面

void *__thiscall gtree_401900(void *this)
{
  ..........

  v10 = this;
  f_4015D0(&v12);
  t_401540(&v13);
  M_4016E0(&v17);
  7_401660(&v14);
  9_401880(&Src);
  k_401770(&v16);
  c_4014C0(&v15);
  kx_4017F0(&v11);

后面执行了和之前 前面 main logic 生成字典树差不多的操作
猜测这里就是在 构造字典树了

  store1_403AB0(&v9, &Src);
  copy(&node_9, &v9);
  store1_403AB0(&v8, &v17);
  copy(&node_M, &v8);
  store1_403AB0(&v7, &v16);
  copy(&node_k, &v7);
  store1_403AB0(&v6, &v15);
  copy(&node_c, &v6);
  store1_403AB0(&v5, &v14);
  copy(&node, &v5);
  store1_403AB0(&v4, &v13);
  copy(&node_t, &v4);
  store1_403AB0(&v3, &v11);
  copy(&node_kx, &v3);
  store1_403AB0(&v2, &v12);
  copy(&node_f, &v2);

存放之后会进行一系列的操作,一开始不知道是干什么
观察 copysome_403940 函数 可以猜测这里应该是在构建字典树的过程
给一个节点孩子什么的
比如 copysome_403940(&node_M, &node_k)
操作的效果就是 node_M 是父节点, node_k 加入成为 node_M 的子节点
通过下面的操作我们也可以构建出一棵树出来

  copysome_403940(&node_M, &node_k);
  copysome_403940(&node_t, &node_9);
  copysome_403940(&node, &node_M);
  copysome_403940(&node_t, &node_f);
  copysome_403940(&node_c, &node);
  copysome_403940(&root, &node_kx);
  copysome_403940(&node_c, &node_t);
  copysome_403940(&root, &node_c);

//----------------------------------------//
_DWORD *__thiscall copysome_403940(_DWORD *this, int a2)
{
  _DWORD *result; // eax

  if ( this[66] >= 0x20u )
    exit(-1);
  this[this[66] + 0x22] = a2;
  result = this + 0x22;
  ++this[66];
  return result;
}

字典树构建完成之后, 会给每个节点 执行 sub_403650 函数,赋一个数字值,估计就是引用计数了

  sub_403650(&node_c, 0);
  sub_403650(&node_k, 1);
  sub_403650(&node_9, 1);
  sub_403650(&node_t, 1);
  sub_403650(&node, 1);
  sub_403650(&node_M, 2);
  sub_403650(&root, 0);
  sub_403650(&node_f, 1);
  sub_403650(&node_kx, 1);
  sub_403A60(&gtree_407E48, &root);
  return v10;
}

很好,到了这里,自己重构一下 字典树就可以找出所有可能的字符串了
mspaint 画了一棵树,勿喷

 

因为 M 的引用计数是两个,所以猜测需要有两个一样的串,和前面构建字典树的字符的数量也相符
不过这里有些 字符串的长度是一样的,不是到哪个先哪个后,这就需要前面提到的 last_check_401B80 函数了, 将对应的字符 的byte 异或一下就可以知道哪个是哪个了

int __cdecl last_check_401B80(char *chr_0_1, char *char_7_8, int char_13_14_15, int char_16_17_18, int correct, int wrong)
{
  int result; // eax

  if ( (chr_0_1[1] ^ *chr_0_1) != 0x54
    || (char_7_8[1] ^ *char_7_8) != 0x13
    || (*(char_13_14_15 + 1) ^ *(char_13_14_15 + 2)) != 0x12
    || (*(char_16_17_18 + 2) ^ *(char_16_17_18 + 1)) != 0x4D )
  {                                             // 2 个 byte 的比较

其实自己排列组合爆破一下也是可以的
最后得到的flag

c7ctc7Mkxc7Mkctfct9c7M

看雪侠者千人榜,看看你上榜了吗?

上传的附件:
收藏
点赞0
打赏
分享
最新回复 (2)
雪    币: 474
活跃值: 活跃值 (12)
能力值: ( LV4,RANK:40 )
在线值:
发帖
回帖
粉丝
zjhkx学院 活跃值 2018-6-23 16:34
2
0


您是怎么判断这个函数是生成字符串的,我怎么都解不明白
我运行代码怎么都是解不出来
a1 = [141,180,251,69,81,152,144,139,175,218,207,96,171,100,39,0]
# a1 = [0xb4,0xFB,0x45,0x51,0x98,0x90,0x8B,0xAF,0xDA,0xCF,0x60,0xAB,0x64,0x27,0x00]
for i in range(0,15):
	a1[i] ^= i * 34 * i + i * i * 58 * i - 78 * i - 52
	result = i + 1
print(a1)

[-191, -146, 371, 1655, 3941, 7538, 13088, 20841, 31091, 44064, 60503, 80498, 104047, 132206, 164711, 0]
[-136, -223, 461, 1635, 4012, 7546, 13115, 20813, 30982, 44085, 60664, 80569, 104096, 132141, 164672]
最后于 2018-6-23 21:08 被zjhkx学院编辑 ,原因:
雪    币: 2732
活跃值: 活跃值 (10)
能力值: ( LV15,RANK:828 )
在线值:
发帖
回帖
粉丝
aqs 活跃值 5 2018-6-23 22:39
3
0
额,我是直接调试看的
游客
登录 | 注册 方可回帖
返回