GUET-CTF2019 number_game

https://buuoj.cn/challenges#[GUET-CTF2019]number_game

64 elf

unsigned __int64 __fastcall main(int a1, char **a2, char **a3)
{
  _QWORD *v4; // [rsp+8h] [rbp-38h]
  char *input; // [rsp+10h] [rbp-30h] BYREF
  __int16 v6; // [rsp+18h] [rbp-28h]
  __int64 v7; // [rsp+20h] [rbp-20h] BYREF
  __int16 v8; // [rsp+28h] [rbp-18h]
  char v9; // [rsp+2Ah] [rbp-16h]
  unsigned __int64 v10; // [rsp+38h] [rbp-8h]
 
  v10 = __readfsqword(0x28u);
  input = 0LL;
  v6 = 0;
  v7 = 0LL;
  v8 = 0;
  v9 = 0;
  __isoc99_scanf("%s", &input);
  if ( (unsigned int)sub_4006D6(&input) )
  {
    v4 = trans((__int64)&input, 0, 10);
    trans2((__int64)v4, (__int64)&v7);
    v9 = 0;
    store((char *)&v7);
    if ( (unsigned int)check() )
    {
      puts("TQL!");
      printf("flag{");
      printf("%s", (const char *)&input);
      puts("}");
    }
    else
    {
      puts("your are cxk!!");
    }
  }
  return __readfsqword(0x28u) ^ v10;
}

__int64 __fastcall sub_4006D6(const char *a1)
{
  int i; // [rsp+1Ch] [rbp-4h]
 
  if ( strlen(a1) == 10 )
  {
    for ( i = 0; i <= 9; ++i )
    {
      if ( a1[i] > 52 || a1[i] <= '/' )         // 48~52 0 1 2 3 4
        goto LABEL_2;
    }
    return 1LL;
  }
  else
  {
LABEL_2:
    puts("Wrong!");
    return 0LL;
  }
}

在 0 到 4 之间

输入 0 到 4 的十个数字

_QWORD *__fastcall build_tree(char *ptr, int a2, signed int edge)
{
  char v5; // [rsp+1Fh] [rbp-11h]
  _QWORD *v6; // [rsp+28h] [rbp-8h]
 
  v5 = ptr[a2];
  if ( v5 == ' ' || v5 == '\n' || a2 >= edge )
    return 0LL;
  v6 = malloc(0x18uLL);
  *(_BYTE *)v6 = v5;                            // store data
  v6[1] = build_tree(ptr, 2 * a2 + 1, edge);
  v6[2] = build_tree(ptr, 2 * (a2 + 1), edge);
  return v6;
}

递归建立全二叉树

更改数据结构

struct node
 
{
 
_BYTE data;
 
_QWORD *p1;
 
_QWORD p2;
 
};

node *__fastcall build_tree(char *ptr, int a2, signed int edge)
{
  char v5; // [rsp+1Fh] [rbp-11h]
  node *v6; // [rsp+28h] [rbp-8h]
 
  v5 = ptr[a2];
  if ( v5 == ' ' || v5 == '\n' || a2 >= edge )
    return 0LL;
  v6 = (node *)malloc(0x18uLL);
  v6->data = v5;                                // store data
  v6->p1 = build_tree(ptr, 2 * a2 + 1, edge);
  v6->p2 = build_tree(ptr, 2 * (a2 + 1), edge);
  return v6;
}

分析下一个函数

node *__fastcall trans2(node *now, __int64 a2)
{
  node *result; // rax
 
  result = now;
  if ( now )
  {
    trans2((node *)now->p1, a2);
    *(_BYTE *)(a2 + dword_601080++) = now->data;
    return trans2((node *)now->p2, a2);
  }
  return result;
}

发现又是两个递归，有点像中序输出

从后面的数据流看出，这里的目标是存储到 a2 里面，所以把 a2 看成是数组

node *__fastcall trans2(node *now, char *res)
{
  node *result; // rax
 
  result = now;
  if ( now )
  {
    trans2((node *)now->p1, res);
    res[index++] = now->data;
    return trans2((node *)now->p2, res);
  }
  return result;
}

回到主函数，发现 v8 v9 都没有用，推测输入的是存在栈上的数组

unsigned __int64 __fastcall main(int a1, char **a2, char **a3)
{
  node *root; // [rsp+8h] [rbp-38h]
  char input[10]; // [rsp+10h] [rbp-30h] BYREF
  char res[11]; // [rsp+20h] [rbp-20h] BYREF
  unsigned __int64 v7; // [rsp+38h] [rbp-8h]
 
  v7 = __readfsqword(0x28u);
  memset(input, 0, sizeof(input));
  memset(res, 0, sizeof(res));
  __isoc99_scanf("%s", input);
  if ( (unsigned int)input_filter(input) )
  {
    root = build_tree(input, 0, 10);
    mid_spell(root, res);
    res[10] = 0;
    store(res);
    if ( (unsigned int)check() )
    {
      puts("TQL!");
      printf("flag{");
      printf("%s", input);
      puts("}");
    }
    else
    {
      puts("your are cxk!!");
    }
  }
  return __readfsqword(0x28u) ^ v7;
}

整理一下数据结构

__int64 __fastcall store(char *res)
{
  __int64 result; // rax
 
  dump[2] = *res;
  dump[7] = res[1];                             // 14#2330#1#0#23##3##042##1
  dump[9] = res[2];
  dump[11] = res[3];
  dump[14] = res[4];
  dump[15] = res[5];
  dump[17] = res[6];
  dump[18] = res[7];
  dump[22] = res[8];
  result = (unsigned __int8)res[9];
  dump[23] = res[9];
  return result;
}

__int64 check()
{
  unsigned int v1; // [rsp+0h] [rbp-10h]
  int i; // [rsp+4h] [rbp-Ch]
  int j; // [rsp+8h] [rbp-8h]
  int k; // [rsp+Ch] [rbp-4h]
 
  v1 = 1;
  for ( i = 0; i <= 4; ++i )
  {
    for ( j = 0; j <= 4; ++j )
    {
      for ( k = j + 1; k <= 4; ++k )
      {
        if ( dump[5 * i + j] == dump[5 * i + k] )
          v1 = 0;
        if ( dump[5 * j + i] == dump[5 * k + i] )
          v1 = 0;
      }
    }
  }
  return v1;
}

用脚本推回去 dump 里所有元素，再对应到树上，根据中序输出和确定个数的完全二叉树推出前序就能做出来

但是从更高角度去理解，当出现循环嵌套的时候，要及时意识到这可能是二维的东西，是一个用一维数值实现二维操作的 trick

就比如说这题，就是 5x5 的表要求行和列上的元素互不相同的意思，其实就是一个另类的数独

14#23
30#1#
0#23#
#3##0
42##1

---

14023
30412
01234
23140
42301

0421421430

知道是中序转前序，用动调输入 0123456789 得到变换 7381940526 （set IP）

flag = list("0421421430")  
flag1= [' ']*len(flag)  
  
seq = [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]  
  
for i in range(len(seq)):  
    flag1[seq[i]]=flag[i]  
  
  
print("".join(flag1))

1134240024