首页
论坛
课程
招聘
[原创]看雪 CTF2018 第二题 TrieTree字典树基本结构
2018-6-19 11:50 1543

[原创]看雪 CTF2018 第二题 TrieTree字典树基本结构

HHHso 活跃值
20
2018-6-19 11:50
1543
0x00 粗测
执行样例,随便输出,提示"Answer is Wrong"
IDA静态分析,View>Open Subviews>String窗,找不"Answer is Wrong"或其他类似"success"信息



0x01 按图索骥
由start,进入main函数,如下
.text:0040443C push    eax ; envp
.text:0040443D push    dword ptr [edi] ; argv
.text:0040443F push    dword ptr [esi] ; argc
.text:00404441 call   _main

再main开头,由"%s"和console UI操作,猜定Hi_scanf_sub_401170
.text:00402230 push    20h
.text:00402232 lea     eax, [ebp+loc_inputkey]
.text:00402235 push    eax
.text:00402236 push    offset aS ; "%s"
.text:0040223B call    Hi_scanf_sub_401170

进一步,我们逆向得到
Hi_get_OK_msg_sub_401360 获取该函数内置数据解密出的提示信息"Answer correct!"
Hi_get_NO_msg_sub_401200 获取该函数内置数据解密出的提示信息"Answer is Wrong"
Hi_Is_AZaz09_sub_402180  判断输出loc_inputkey是否为限制于A-Za-z0-9
输入的inputkey长度要求为22个字符,卖弄函数主要逻辑如下
int __cdecl main(int argc,const char**argv,const char**envp)
{
  int result;// eax
  char loc_inputkey[32];// [esp+10h] [ebp-44h]
  char loc_i16_1_OK[16];// [esp+30h] [ebp-24h]
  char loc_i16_2_NO[16];// [esp+40h] [ebp-14h]

  Hi_scanf_sub_401170("%s",loc_inputkey,32);
  Hi_get_OK_msg_sub_401360(loc_i16_1_OK);//Answer correct!
  Hi_get_NO_msg_sub_401200(loc_i16_2_NO);//Answer is Wrong
  if(Hi_Is_AZaz09_sub_402180(loc_inputkey,(int)loc_i16_2_NO))
  {
    if(&loc_inputkey[strlen(loc_inputkey)+1]-&loc_inputkey[1]==22)
      Hi_check_key_sub_401C40(loc_inputkey,(int)loc_i16_1_OK,(int)loc_i16_2_NO);
    else
      Hi_printf_sub_4011D0(loc_i16_2_NO);
    //clear loc_i16_2_NO loc_i16_1_OK
    system("pause");
    result=0;
  }
  else
  {
    //clear loc_i16_2_NO loc_i16_1_OK
    result=0;
  }
}

在Hi_Is_AZaz09_sub_402180中,
通过Hi_is_AZ_az_sub_402140 和 Hi_is_09_sub_402110对输入key分别检测大小写字母与数字,如下
若错误,显示错误信息loc_i16_2_NO);//Answer is Wrong
char __cdecl Hi_Is_AZaz09_sub_402180(const char*a1,int a2)
{
  signed int loc_keylen;// kr00_4
  signed int loc_i;// [esp+Ch] [ebp-Ch]

  loc_keylen=strlen(a1);
  for(loc_i=0;loc_i<loc_keylen;++loc_i)
  {
    if(!Hi_is_AZ_az_sub_402140(a1[loc_i])&&!Hi_is_09_sub_402110(a1[loc_i]))
    {
      Hi_printf_sub_4011D0(a2);
      return 0;
    }
  }
  return 1;
}

0x03 在上述main中得到key校验函数
Hi_check_key_sub_401C40(loc_inputkey,(int)loc_i16_1_OK,(int)loc_i16_2_NO);
其主要业务逻辑是
(1)将input_key分成八个部分(产生八个字典字),
(2)将字添加到字典树中,与参考字典树比对(完成第一步检验)
(3)若通过(2)的检验,则由Hi_last_check_sub_401B80进一步对其中四个字进行限制检验
(*)若(2)或(3)都检验成功,则输出成功提示loc_i16_1_OK  //Answer correct!
   若不匹配,则输出错误提示            loc_i16_2_NO  //Answer is Wrong

int __cdecl Hi_check_key_sub_401C40(char*P1_inputkey,int P2_OK,int P3_Err)
{
  char v4;// [esp+4h] [ebp-47Ch]
  char v5;// [esp+88h] [ebp-3F8h]
  char v6;// [esp+10Ch] [ebp-374h]
  char v7;// [esp+190h] [ebp-2F0h]
  char v8;// [esp+214h] [ebp-26Ch]
  char v9;// [esp+298h] [ebp-1E8h]
  szWord v10;// [esp+31Ch] [ebp-164h]
  szWord loc_szword_kdef;// [esp+3A0h] [ebp-E0h]
  int v12;// [esp+424h] [ebp-5Ch]
  int v13;// [esp+428h] [ebp-58h]
  int v14;// [esp+42Ch] [ebp-54h]
  int v15;// [esp+430h] [ebp-50h]
  int v16;// [esp+434h] [ebp-4Ch]
  int v17;// [esp+438h] [ebp-48h]
  int v18;// [esp+43Ch] [ebp-44h]
  int v19;// [esp+440h] [ebp-40h]
  char loc_k131415[4];// [esp+444h] [ebp-3Ch]
  char loc_k456[4];// [esp+448h] [ebp-38h]
  char loc_k23[3];// [esp+44Ch] [ebp-34h]
  char loc_kdef[4];// [esp+450h] [ebp-30h]
  char loc_k101112[4];// [esp+454h] [ebp-2Ch]
  int loc_TrieTree[2];// [esp+458h] [ebp-28h]
  char loc_k01[3];// [esp+460h] [ebp-20h]
  char loc_k78[3];// [esp+464h] [ebp-1Ch]
  char loc_k9abc[5];// [esp+468h] [ebp-18h]
  int v29;// [esp+47Ch] [ebp-4h]

  v19=2;
  loc_k01[2]=0;
  loc_k23[0]=P1_inputkey[2];
  v18=3;
  loc_k456[3]=0;
  loc_k01[1]=P1_inputkey[1];
  loc_k9abc[3]=P1_inputkey[12];
  loc_k101112[0]=P1_inputkey[16];
  loc_k9abc[0]=P1_inputkey[9];
  loc_k78[0]=P1_inputkey[7];
  loc_k9abc[1]=P1_inputkey[10];
  loc_k78[1]=P1_inputkey[8];
  loc_k131415[1]=P1_inputkey[20];
  v17=4;
  loc_k9abc[4]=0;
  loc_kdef[2]=P1_inputkey[15];
  v16=2;
  loc_k23[2]=0;
  v15=2;
  loc_k78[2]=0;
  loc_k456[2]=P1_inputkey[6];
  loc_kdef[1]=P1_inputkey[14];
  loc_k456[0]=P1_inputkey[4];
  loc_k23[1]=P1_inputkey[3];
  loc_kdef[0]=P1_inputkey[13];
  v14=3;
  loc_k101112[3]=0;
  loc_k456[1]=P1_inputkey[5];
  loc_k101112[1]=P1_inputkey[17];
  loc_k01[0]=*P1_inputkey;
  loc_k131415[2]=P1_inputkey[21];
  v13=3;
  loc_kdef[3]=0;
  loc_k131415[0]=P1_inputkey[19];
  loc_k9abc[2]=P1_inputkey[11];
  loc_k101112[2]=P1_inputkey[18];
  v12=3;
  loc_k131415[3]=0;
  loc_TrieTree[0]=0;
  loc_TrieTree[1]=0;
  std::_Ref_count_obj<__ExceptionPtr>::_Ref_count_obj<__ExceptionPtr>(loc_TrieTree);
  v29=0;
  Hi_TTWord_asign_sub_403AB0(loc_szword_kdef.data,loc_kdef);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&loc_szword_kdef);
  Hi_TTWord_asign_sub_403AB0(v10.data,loc_k01);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v10);
  Hi_TTWord_asign_sub_403AB0(&v9,loc_k9abc);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v9);
  Hi_TTWord_asign_sub_403AB0(&v8,loc_k456);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v8);
  Hi_TTWord_asign_sub_403AB0(&v7,loc_k23);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v7);
  Hi_TTWord_asign_sub_403AB0(&v6,loc_k78);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v6);
  Hi_TTWord_asign_sub_403AB0(&v5,loc_k101112);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v5);
  Hi_TTWord_asign_sub_403AB0(&v4,loc_k131415);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v4);
  if((unsigned __int8)Hi_TT_cmp_sub_4030E0(loc_TrieTree,(int)&Hi_RefTT_dword_407E48))
    Hi_last_check_sub_401B80(loc_k01,loc_k78,(int)loc_kdef,(int)loc_k101112,P2_OK,P3_Err);
  else
    Hi_printf_sub_4011D0(P3_Err);
  v29=-1;
  return Hi_TT_dtor_sub_402AC0((void(__thiscall****)(_DWORD,signed int))loc_TrieTree);
}


0x04 字典树基本结构
字典树的字串TTWord,字典树TrieTree,字典树字结点TrieTreeNode相关类型和内存结构如下定义
class TrieTree;
class TrieTreeNode;
typedef struct _TTWord{//cbSize:0x84
  /* .00  */ char szword[0x80];             //字典字串的字符串数据
  /* .80  */ unsigned int length;           //字典字串的字符串长度
} TTWord,*PTTWord;
typedef struct _TrieTreeNodeList{
  /* .00  */ TrieTreeNode* TTNBuffer[0x20];  //字典字结点的子字结点(分支结点)数组
  /* .80  */ unsigned int TTNCount;          //字典字结点的子字结点(分支结点)数组元素个数
} TrieTreeNodeList,*PTrieTreeNodeList;

class TrieTreeNode{//cbSize:0x110
  /* .00  */ //vft.TrieTreeNode :: vft.TrieTreeNodeAbs
  /* .04  */ TTWord ttword;                     //字结点 表示的 字串
  /* .88  */ TrieTreeNodeList subTTNList;       //字结点 的 子-字结点
  /* .10C */ unsigned int Count;                //字节点出现次数,表示其代表的 字串 出现次数
}
class TrieTree{//cbSize:0x08
  /* .00  */ //vft.TrieTree :: vft.TrieTreeAbs
  /* .04  */ TrieTreeNode root;                  //字典树  根字结点开始索引  一般 root.ttword.szword==""
}

0x05 input_key的字分割
前面分析可知input_key 长度为 22 (0x16),即char input_key[0x16];下标索引从0到0x15,
input_key被分为以下八个字串
k01 = input_key[0~1]
k23 = input_key[2~3]
k456 = input_key[4~6]
k78 = input_key[7~8]
k9abc = input_key[9~0xc]
kdef = input_key[0xd~0xf]
k101112 = input_key[0x10~0x12]
k131415 = input_key[0x13~0x15]

通过TTWord的构建函数Hi_TTWord_asign_sub_403AB0,将构建上述字串的字典字;
并通过Hi_TT_add_TTNszw_sub_402B40将相应的字添加到字典树中,如下
  Hi_TTWord_asign_sub_403AB0(loc_szword_kdef.data,loc_kdef);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&loc_szword_kdef);
  Hi_TTWord_asign_sub_403AB0(v10.data,loc_k01);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v10);
  Hi_TTWord_asign_sub_403AB0(&v9,loc_k9abc);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v9);
  Hi_TTWord_asign_sub_403AB0(&v8,loc_k456);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v8);
  Hi_TTWord_asign_sub_403AB0(&v7,loc_k23);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v7);
  Hi_TTWord_asign_sub_403AB0(&v6,loc_k78);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v6);
  Hi_TTWord_asign_sub_403AB0(&v5,loc_k101112);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v5);
  Hi_TTWord_asign_sub_403AB0(&v4,loc_k131415);
  Hi_TT_add_TTNszw_sub_402B40(loc_TrieTree,(int)&v4);
  if((unsigned __int8)Hi_TT_cmp_sub_4030E0(loc_TrieTree,(int)&Hi_RefTT_dword_407E48))
    Hi_last_check_sub_401B80(loc_k01,loc_k78,(int)loc_kdef,(int)loc_k101112,P2_OK,P3_Err);

最后通过Hi_TT_cmp_sub_4030E0将input_key对应的字典树loc_TrieTree与全局字典树 Hi_RefTT_dword_407E48对比
比对要求字典树拥有相同的字结点,字结点出现的次数一样,且字结点之间的上下(父子)关系一致。

0x06 用于比对的全局字典树来源 RefTT
Hi_RefTT_dword_407E48字典树的初始化在运行时初始化向量函数Hi_Init_RefTT_sub_401900中完成,如下
其中函数一开始由内联函数生成的R1~R8为字典树的字结点的字串,其最终产生如下八个字典字,
相应的字串分别为"9","M","k","c","7","t","kx","f"
Hi_9_stru_4074B0
Hi_M_stru_4075C0
Hi_k_stru_407D38
Hi_c_stru_4077E8
Hi_7_stru_407A08
Hi_t_stru_407C28
Hi_kx_stru_4076D0
Hi_f_stru_407B18

其后系列的Hi_ecxTTWord_append_P1TTWord_sub_403940和Hi_TrieTreeNode_SetCount_sub_403650函数操作
决定了字典树中根结点Hi_TT_stru_4078F8和其它字结点之间的层次关系,也设置了出现的次数
Hi_TT_stru_4078F8
  kx 1
  c 0
    7 1
      M 2
        k 1
    t 1
      9 1
      f 1

即 k01,k23,k456,k78,k9abc,kdef,k101112,k131415的取值集合为
{kx,c7,c7M,c7M,c7Mk,ct,ct9,ctf}

k01 = input_key[0~1]
k23 = input_key[2~3]
k456 = input_key[4~6]
k78 = input_key[7~8]
k9abc = input_key[9~0xc]
kdef = input_key[0xd~0xf]
k101112 = input_key[0x10~0x12]
k131415 = input_key[0x13~0x15]

结合Hi_last_check_sub_401B80函数的限制条件,我们可以得到input_key其中以下四个部分的取值
 0x12 = kdef[1]^kdef[2]         >> kdef     = "ctf"
 0x54 = k01[0]^k01[1]           >> k01      = "c7"
 0x13 = k78[0]^k78[1]           >> k78      = "kx"
 0x4D = k101112[1]^k101112[2]   >> k101112  = "ct9"

其余四个部分在余下集合中取{c7M,c7M,c7Mk,ct},根据k对应长度即可得到相应的值
k456 = input_key[4~6]           ="c7M"
k23 = input_key[2~3]            ="ct"
k9abc = input_key[9~0xc]        ="c7Mk"
k131415 = input_key[0x13~0x15]  ="c7M"
      
于是由k01,k23,k456,k78,k9abc,kdef,k101112,k131415各部分组合成input_key
 c7 ct c7M kx c7Mk ctf ct9  c7M
input_key = "c7ctc7Mkxc7Mkctfct9c7M"

void*__thiscall Hi_Init_RefTT_sub_401900(void*this)
{
  char v2;// [esp+0h] [ebp-448h]
  char v3;// [esp+84h] [ebp-3C4h]
  char v4;// [esp+108h] [ebp-340h]
  char v5;// [esp+18Ch] [ebp-2BCh]
  char v6;// [esp+210h] [ebp-238h]
  char v7;// [esp+294h] [ebp-1B4h]
  char v8;// [esp+318h] [ebp-130h]
  char v9;// [esp+39Ch] [ebp-ACh]
  void*v10;// [esp+420h] [ebp-28h]
  char loc_R7;// [esp+424h] [ebp-24h]
  char loc_R8;// [esp+428h] [ebp-20h]
  char loc_R6;// [esp+42Ch] [ebp-1Ch]
  char loc_R5;// [esp+430h] [ebp-18h]
  char loc_R4;// [esp+434h] [ebp-14h]
  char loc_R3;// [esp+438h] [ebp-10h]
  char loc_R2;// [esp+43Ch] [ebp-Ch]
  char loc_R1;// [esp+440h] [ebp-8h]

  v10=this;
  sub_4015D0(&loc_R8);
  sub_401540(&loc_R6);
  sub_4016E0(&loc_R2);
  sub_401660(&loc_R5);
  sub_401880(&loc_R1);
  sub_401770(&loc_R3);
  sub_4014C0(&loc_R4);
  sub_4017F0(&loc_R7);
  Hi_TTWord_asign_sub_403AB0(&v9,&loc_R1);
  Hi_ecx_eq_P1TTWord_sub_403620((int)&Hi_9_stru_4074B0,&v9);
  Hi_TTWord_asign_sub_403AB0(&v8,&loc_R2);
  Hi_ecx_eq_P1TTWord_sub_403620((int)&Hi_M_stru_4075C0,&v8);
  Hi_TTWord_asign_sub_403AB0(&v7,&loc_R3);
  Hi_ecx_eq_P1TTWord_sub_403620((int)&Hi_k_stru_407D38,&v7);
  Hi_TTWord_asign_sub_403AB0(&v6,&loc_R4);
  Hi_ecx_eq_P1TTWord_sub_403620((int)&Hi_c_stru_4077E8,&v6);
  Hi_TTWord_asign_sub_403AB0(&v5,&loc_R5);
  Hi_ecx_eq_P1TTWord_sub_403620((int)&Hi_7_stru_407A08,&v5);
  Hi_TTWord_asign_sub_403AB0(&v4,&loc_R6);
  Hi_ecx_eq_P1TTWord_sub_403620((int)&Hi_t_stru_407C28,&v4);
  Hi_TTWord_asign_sub_403AB0(&v3,&loc_R7);
  Hi_ecx_eq_P1TTWord_sub_403620((int)&Hi_kx_stru_4076D0,&v3);
  Hi_TTWord_asign_sub_403AB0(&v2,&loc_R8);
  Hi_ecx_eq_P1TTWord_sub_403620((int)&Hi_f_stru_407B18,&v2);
  Hi_ecxTTWord_append_P1TTWord_sub_403940(&Hi_M_stru_4075C0,(int)&Hi_k_stru_407D38);
  Hi_ecxTTWord_append_P1TTWord_sub_403940(&Hi_t_stru_407C28,(int)&Hi_9_stru_4074B0);
  Hi_ecxTTWord_append_P1TTWord_sub_403940(&Hi_7_stru_407A08,(int)&Hi_M_stru_4075C0);
  Hi_ecxTTWord_append_P1TTWord_sub_403940(&Hi_t_stru_407C28,(int)&Hi_f_stru_407B18);
  Hi_ecxTTWord_append_P1TTWord_sub_403940(&Hi_c_stru_4077E8,(int)&Hi_7_stru_407A08);
  Hi_ecxTTWord_append_P1TTWord_sub_403940(&Hi_TT_stru_4078F8,(int)&Hi_kx_stru_4076D0);
  Hi_ecxTTWord_append_P1TTWord_sub_403940(&Hi_c_stru_4077E8,(int)&Hi_t_stru_407C28);
  Hi_ecxTTWord_append_P1TTWord_sub_403940(&Hi_TT_stru_4078F8,(int)&Hi_c_stru_4077E8);
  Hi_TrieTreeNode_SetCount_sub_403650(&Hi_c_stru_4077E8,0);
  Hi_TrieTreeNode_SetCount_sub_403650(&Hi_k_stru_407D38,1);
  Hi_TrieTreeNode_SetCount_sub_403650(&Hi_9_stru_4074B0,1);
  Hi_TrieTreeNode_SetCount_sub_403650(&Hi_t_stru_407C28,1);
  Hi_TrieTreeNode_SetCount_sub_403650(&Hi_7_stru_407A08,1);
  Hi_TrieTreeNode_SetCount_sub_403650(&Hi_M_stru_4075C0,2);
  Hi_TrieTreeNode_SetCount_sub_403650(&Hi_TT_stru_4078F8,0);
  Hi_TrieTreeNode_SetCount_sub_403650(&Hi_f_stru_407B18,1);
  Hi_TrieTreeNode_SetCount_sub_403650(&Hi_kx_stru_4076D0,1);
  Hi_ecxTT_assign_P1TT_sub_403A60(&Hi_TT_stru_4078F8);
  return v10;
}

0x07 内存中字典树实例信息的dump
.text:004020A5 push    offset Hi_RefTT_dword_407E48
.text:004020AA lea     ecx, [ebp+loc_TrieTree]
.text:004020AD call    Hi_TT_cmp_sub_4030E0
IDA+WINDBG+IDAPython,可以在004020AD出断下
通过dump出不同输入input_key生成的字典树与参考字典树的差异性对比分析。
def ninfo(na,pref):
   nn = GetString(na+4,-1,ASCSTR_C)
   sn_cnt = Dword(na+0x88+0x80)
   print pref+nn,Dword(na+0x88+0x80+4)
   for i in xrange(0,sn_cnt):
     ninfo(Dword(na+0x88+i*4),pref+'  ')

def ListTrieTree(ta=0x407E48,pref=''):
 na = Dword(ta+4)
 cnt = Dword(na+0x88+0x80)
 for i in xrange(0,cnt):
   ninfo(Dword(na+0x88+i*4),pref+'  ')


ListTrieTree(GetOperandValue(0x4020A5,0)) #参考字典树信息
(1)内部参考字典树的信息
  kx 1
  c 0
    7 1
      M 2
        k 1
    t 1
      9 1
      f 1
ListTrieTree(ecx寄存器值)#输入input_key生成的字典树信息
(2)正确input_key = c7ctc7Mkxc7Mkctfct9c7M的字典树信息
  c 0
    t 1
      f 1
      9 1
    7 1
      M 2
        k 1
  kx 1
(3)错误input_key = c7kxctfkxc7Mkctfct9c7M的字典树信息
  c 0
    t 0
      f 2
      9 1
    7 1
      M 1
        k 1
  kx 2

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

收藏
点赞0
打赏
分享
最新回复 (1)
雪    币: 205
活跃值: 活跃值 (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
东临碣石A 活跃值 2018-6-23 20:50
2
0
为什么我的start点进去的函数地址不对呀
text:004044BC                                  public  start
.text:004044BC  start                      proc  near
.text:004044BC
.text:004044BC  ;  FUNCTION  CHUNK  AT  .text:0040434D  SIZE  0000012C  BYTES
.text:004044BC  ;  FUNCTION  CHUNK  AT  .text:004044B6  SIZE  00000006  BYTES
.text:004044BC
.text:004044BC                                  call        sub_4049CA
.text:004044C1                                  jmp          loc_40434D
.text:004044C1  start                      endp  ;  sp-analysis  failed

这是怎么回事,粗了什么问题?
游客
登录 | 注册 方可回帖
返回