首页
论坛
课程
招聘
[原创]CTF2018第二题分析(qwertyaa)
2018-6-18 16:16 1721

[原创]CTF2018第二题分析(qwertyaa)

2018-6-18 16:16
1721

一觉睡到2点发现一血已经没了...QAQ
结合这个信息和第二题的位置我假设这是一道非常有良心的题目。(^_^) (不像去年某些改DES、高精度库、LuaJIT的题)
然后下载好题目并打开,发现是输入一个字符串,然后打印一个是否正确的信息。
于是拖入IDA进行分析
首先注意到的是许多常量字符串都加了密,这没有关系,我们设断点把解密结果记下来即可,其中,解密算法如下:

  for ( i = 0; i < strlen(str); ++i )
  {
    str[i] ^= i * 17 * i + i * i * 96 * i - 29 * i - 127;
  }

这是个很常规的XOR加密算法,其中密钥由于当前位置相关的一个多项式给出。为了方便,下文给出的代码中这类加密字符串所存储的位置都被命名为对所存储内容的描述。
然后我们来看代码:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int result; // eax
  char content[32]; // [esp+10h] [ebp-44h]
  char ok[16]; // [esp+30h] [ebp-24h]
  char err[16]; // [esp+40h] [ebp-14h]

  scanf_s("%s", content, 32);
  sub_401360(ok);
  sub_401200(err);
  if ( str_isalnum(content, (int)err) )
  {
    if ( &content[strlen(content) + 1] - &content[1] == 22 )// len=22
      checkWithoutRangeCheck(content, (int)ok, (int)err);
    else
      print((int)err);
    memset(ok,0,sizeof ok);
    memset(err,0,sizeof err);
    system("pause");
    result = 0;
  }
  else
  {
    memset(ok,0,sizeof ok);
    memset(err,0,sizeof err);
    result = 0;
  }
  return result;
}

我们可以看到,输出信息被传递到checkWithoutRangeCheck里由该函数进行输出,外部主要进行两个判断:

  1. 字符串由大小写字母数字组成(良心啊,帮忙复述比赛规则)
  2. 字符串长度为 22

这里比较有意思的地方是大小写字母判断:

bool __cdecl isalpha(char chr)
{
  return (chr | 0x20) >= 'a' && (chr | 0x20) <= 'z';
}

粗看以为只可输入小写字母,很巧妙,反正我是没见过。

 

然后我们看到checkWithoutRangeCheck

int __cdecl checkWithoutRangeCheck(char *content, int ok, int err)
{
//省略定义信息

  v19 = 2;//打乱 content 信息
  v43 = 0;
  c5 = content[2];
  v18 = 3;
  v27 = 0;
  v42 = content[1];
  v50 = content[12];
  c7 = content[16];
  c3 = content[9];
  c6 = content[7];
  v48 = content[10];
  v45 = content[8];
  v21 = content[20];
  v17 = 4;
  v51 = 0;
  v33 = content[15];
  v16 = 2;
  v30 = 0;
  v15 = 2;
  v46 = 0;
  v26 = content[6];
  v32 = content[14];
  c4 = content[4];
  v29 = content[3];
  c1 = content[13];
  v14 = 3;
  v38 = 0;
  v25 = content[5];
  v36 = content[17];
  c2 = *content;
  v22 = content[21];
  v13 = 3;
  v34 = 0;
  c8 = content[19];
  v49 = content[11];
  v37 = content[18];
  v12 = 3;
  v23 = 0;
  v39 = 0;
  v40 = 0;
  newTrieTree(&v39);//插入Trie
  v52 = 0;
  initStr(&v11, &c1);
  insertStr(&v39, (int)&v11);
  initStr(&v10, &c2);
  insertStr(&v39, (int)&v10);
  initStr(&v9, &c3);
  insertStr(&v39, (int)&v9);
  initStr(&v8, &c4);
  insertStr(&v39, (int)&v8);
  initStr(&v7, &c5);
  insertStr(&v39, (int)&v7);
  initStr(&v6, &c6);
  insertStr(&v39, (int)&v6);
  initStr(&v5, &c7);
  insertStr(&v39, (int)&v5);
  initStr(&v4, &c8);
  insertStr(&v39, (int)&v4);
  if ( compareTrieTree(&v39, (int)&staticTireTree) )//比对两棵树
    finalCheck(&c2, &c6, (int)&c1, (int)&c7, ok, err);
  else
    print(err);
  v52 = -1;
  return sub_402AC0((void (__thiscall ****)(_DWORD, signed int))&v39);
}

这个newTrieTree函数里有这样一句话(大概是IDA通过残留的RTTI信息推测出来的)

  *v1 = &TrieTree::`vftable';

结合这是个良心题目的假设和“数据结构”这个题目,我就先当他是一颗Trie树了。
字符串打乱的过程不想看代码,于是拿起OD,输入abcdefghijklmnopqrstuv,直接单步获得c1-c8分别是:

c2.ab c5.cd c4.efg c6.hi c3.jklm c1.nop c7.qrs c8.tuv

 

结合这是棵Trie的假设粗略的读了这些函数的代码,发现这段程序的功能是先将一些字符串插入到这个Trie,最后将这个Trie和一颗staticTireTree比较是否相同。

 

双击staticTireTree发现是个变量,一路下来没看到初始化这个变量啊,估计是在哪个构造函数里初始化了吧。

 

用OD的内存断点或者直接用xref可以跟踪到如下初始化代码:

void *__thiscall initStaticTrieTree(void *this)
{
//省略定义信息

  v10 = this;
  sub_4015D0(&f);
  sub_401540(&t);
  sub_4016E0(&M);
  sub_401660(&_7);
  sub_401880(&_9);
  sub_401770(&k);
  sub_4014C0(&c);
  sub_4017F0(&kx);
  initStr(&v9, &_9);
  cpNode((int)&N9, &v9);
  initStr(&v8, &M);
  cpNode((int)&NM, &v8);
  initStr(&v7, &k);
  cpNode((int)&Nk, &v7);
  initStr(&v6, &c);
  cpNode((int)&Nc, &v6);
  initStr(&v5, &_7);
  cpNode((int)&N7, &v5);
  initStr(&v4, &t);
  cpNode((int)&Nt, &v4);
  initStr(&v3, &kx);
  cpNode((int)&Nkx, &v3);
  initStr(&v2, &f);
  cpNode((int)&Nf, &v2);
  linkNode(&NM, (int)&Nk);
  linkNode(&Nt, (int)&N9);
  linkNode(&N7, (int)&NM);
  linkNode(&Nt, (int)&Nf);
  linkNode(&Nc, (int)&N7);
  linkNode(&root, (int)&Nkx);
  linkNode(&Nc, (int)&Nt);
  linkNode(&root, (int)&Nc);
  setCount(&Nc, 0);
  setCount(&Nk, 1);
  setCount(&N9, 1);
  setCount(&Nt, 1);
  setCount(&N7, 1);
  setCount(&NM, 2);
  setCount(&root, 0);
  setCount(&Nf, 1);
  setCount(&Nkx, 1);
  setRoot(&staticTireTree, (int)&root);
  return v10;
}

首先是一堆加密串,手工动态解密之。
然后查看linkNode代码是在一个常量大小的边表里插入信息,不难猜出是在构建一个图,setCount是在设置一个属性值,由于所有这些属性的和为8,我们不难猜出这个值代表到这个节点为止的字符串数量。
PS: 这里面的kx是一个由两个字符组成的串,这里所谓的Trie其实应该是Radix Tree(基数树)。不过这与这里的分析其实没多大关系。
我们根据linkNode可以在草稿纸上画出图:
Visio作出的这个图
这样,我们得到以下内容

长度为2的串:
kx
c7
ct
长度为3的串:
c7M
c7M
ctf
ct9
长度为4的串:
c7Mk

 

这下要在c1-c8中对号入座还有3!*4!/2!种可能,我们来看两棵Radix Tree比对通过后进行的最后验证:

void __cdecl finalCheck(char *c2, char *c6, int c1, int c7, int ok, int err)
{
  if ( (c2[1] ^ *c2) != 84
    || (c6[1] ^ *c6) != 19
    || (*(char *)(c1 + 1) ^ *(char *)(c1 + 2)) != 18
    || (*(char *)(c7 + 2) ^ *(char *)(c7 + 1)) != 77 )
    print(err);
  else
    print(ok);
}

可以看到,这里检查了c1-c8中的几个字符串中的一些内容异或值是否正确,我们可以根据这些内容来对号入座。
我们先写个程序来查询异或值:

#include <stdio.h>
int main(){
    char a,b;
    while(1){
        scanf(" %c%c",&a,&b);
        printf("%d\n",a^b);    
    }
}

查询得(控制台信息)

kx
19
ct
23
c7
84
7M
122
tf
18
t9
77

 

这样我们确定了c1c2c6c7的值。
由于长度为4的空只有一个,余下的长度为2的空也只有一个,而两个余下的长度为3的字符串相同(交换次序后flag不变),我们对号入座得到:

c2.c7 c5.ct c4.c7M c6.kx c3.c7Mk c1.ctf c7.ct9 c8.c7M

 

也就是说flag为c7ctc7Mkxc7Mkctfct9c7M
经检验,这一flag正确。


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

最后于 2018-6-18 16:17 被qwertyaa编辑 ,原因:
收藏
点赞0
打赏
分享
最新回复 (5)
雪    币: 84
活跃值: 活跃值 (27)
能力值: ( LV8,RANK:135 )
在线值:
发帖
回帖
粉丝
光棍节 活跃值 2 2018-6-21 16:39
2
0
雪    币: 535
活跃值: 活跃值 (330)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
叶小北 活跃值 2018-7-4 19:43
3
0
先问下你的v17怎么求出来的M
雪    币: 535
活跃值: 活跃值 (330)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
叶小北 活跃值 2018-7-5 12:38
4
0
我求的得v17貌似是0
雪    币: 3088
活跃值: 活跃值 (34)
能力值: ( LV13,RANK:896 )
在线值:
发帖
回帖
粉丝
qwertyaa 活跃值 10 2018-7-6 16:45
5
0
李凯 我求的得v17貌似是0
你是说哪个v17?initStaticTrieTree里的M吗?OD动态跟踪出来的
雪    币: 535
活跃值: 活跃值 (330)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
叶小北 活跃值 2018-7-7 22:54
6
0
谢谢老哥搞定了
游客
登录 | 注册 方可回帖
返回