Mountain climbing - BugkuCTF 逆向

分析

先拖到查壳软件看看是有没有什么壳，发现有UPX壳，然后试着用upx进行解压，但是发现解压失败，所以只能手动脱壳，由于该程序符合ESP定律，手动脱壳也挺简单的，这里我简述一下步骤，用od打开，程序会运行到pushad处，然后步进一步，下硬件断点，直接执行到popad，再步进寻找EOP，找到了之后直接脱壳即可，由于是手动脱壳，所以脱出来的程序反汇编会有一些问题，用IDA反汇编的时候是没有change_str_0函数的，需要手动修改函数位置才能正常反汇编出该函数。

简介程序

main_0（主程序）

// write access to const memory has been detected, the output may be wrong!
__int64 main_0()
{
  int v0; // edx
  __int64 v1; // ST04_8
  int v3; // [esp+D0h] [ebp-90h]
  int j; // [esp+DCh] [ebp-84h]
  int i; // [esp+E8h] [ebp-78h]
  char Str[104]; // [esp+F4h] [ebp-6Ch]

  srand(12u);
  j_memset(dword_423D80, 0, 0x9C40u);
  for ( i = 1; i <= 20; ++i )
  {
    for ( j = 1; j <= i; ++j )
      global_array[100 * i + j] = rand() % 100000;
  }
  printf("input your key with your operation can get the maximum:");
  scanf("%s", Str);
  if ( j_strlen(Str) == 19 )
  {
    change_str((int)Str);
    v3 = 0;
    j = 1;
    i = 1;
    global_sum += global_array[101];            // i=1, j=1
    while ( v3 < 19 )
    {
      if ( Str[v3] == 'L' )
      {
        global_sum += global_array[100 * ++i + j];// 向下走一格
      }
      else
      {
        if ( Str[v3] != 'R' )
        {
          printf("error\n");
          system("pause");
          goto LABEL_18;
        }
        global_sum += global_array[100 * ++i + ++j];// 向右下走一格
      }
      ++v3;
    }
    printf("your operation can get %d points\n", global_sum);
    system("pause");
  }
  else
  {
    printf("error\n");
    system("pause");
  }
LABEL_18:
  HIDWORD(v1) = v0;
  LODWORD(v1) = 0;
  return v1;
}

从主函数可以看出，程序先构建了一个二维数组，用rand（）来初始化，但是由于种子是固定的，所以每次初始化出来的数组也是固定的，让我们简单的写个程序来看看这个数组。

mountain.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    int i, j;
    srand(12);
    for (i = 1; i <= 20; i++)
    {
        for (j = 1; j <= i; j++)
        {
            printf("%7d", rand() % 100000);
        }
        puts("");
    }
    return 0;
}

运行结果如下：

D:\test>cl mountain.c
用于 80x86 的 Microsoft (R) 32 位 C/C++ 优化编译器 16.00.30319.01 版
版权所有(C) Microsoft Corporation。保留所有权利。

mountain.c
Microsoft (R) Incremental Linker Version 10.00.30319.01
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:mountain.exe
mountain.obj

D:\test>mountain.exe
     77
   5628   6232
  29052   1558  26150
  12947  29926  11981  22371
   4078  28629   4665   2229  24699
  27370   3081  18012  24965   2064  26890
  21054   5225  11777  29853   2956  22439   3341
  31337  14755   5689  24855   4173  32304    292   5344
  15512  12952   1868  10888  19581  13463  32652   3409  28353
  26151  14598  12455  26295  25763  26040   8285  27502  15148   4945
  26170   1833   5196   9794  26804   2831  11993   2839   9979  27428   6684
   4616  30265   5752  32051  10443   9240   8095  28084  26285   8838  18784   6547
   7905   8373  19377  18502  27928  13669  25828  30502  28754  32357   2843   5401  10227
  22871  20993   8558  10009   6581  22716  12808   4653  24593  21533   9407   6840  30369   2330
      3  28024  22266  19327  18114  18100  15644  21728  17292   8396  27567   2002   3830  12564   1420
  29531  21820   9954   8319  10918   7978  24806  30027  17659   8764   3258  20719   6639  23556  25786  11048
   3544  31948     22   1591    644  25981  26918  31716  16427  15551  28157   7107  27297  24418  24384  32438  22224
  12285  12601  13235  21606   2516  13095  27080  16331  23295  20696  31580  28758  10697   4730  16055  22208   2391  20143
  16325  24537  16778  17119  18198  28537  11813   1490  21034   1978   6451   2174  24812  28772   5283   6429  15484  29353   5942
   7299   6961  32019  24731  29103  17887  17338  26840  13216   8789  12474  24299  19818  18218  14564  31409   5256  31930  26804   9736

接下来我们看看主程序的核心部分：

v3 = 0;
j = 1;
i = 1;
global_sum += global_array[101];            // i=1, j=1
while ( v3 < 19 )
{
    if ( Str[v3] == 'L' )
    {
    global_sum += global_array[100 * ++i + j];// 向下走一格
    }
    else
    {
    if ( Str[v3] != 'R' )
    {
        printf("error\n");
        system("pause");
        goto LABEL_18;
    }
    global_sum += global_array[100 * ++i + ++j];// 向右下走一格
    }
    ++v3;
}
printf("your operation can get %d points\n", global_sum)

从这里可以看出，这个程序就是在模拟现实生活中下山的场景，从山顶走到山脚下，L就是向下走，R就是向右下走，再把所有的路程累加，路程最大时，即是我们要的flag，所以接下来就直接用深度优先遍历进行求最大解，代码如下：

dfs.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 20
#define L 1
#define R 2

int global_mountain[SIZE][SIZE] = {
    {    77,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    {  5628,  6232,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    { 29052,  1558, 26150,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    { 12947, 29926, 11981, 22371,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    {  4078, 28629,  4665,  2229, 24699,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    { 27370,  3081, 18012, 24965,  2064, 26890,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    { 21054,  5225, 11777, 29853,  2956, 22439,  3341,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    { 31337, 14755,  5689, 24855,  4173, 32304,   292,  5344,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    { 15512, 12952,  1868, 10888, 19581, 13463, 32652,  3409, 28353,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    { 26151, 14598, 12455, 26295, 25763, 26040,  8285, 27502, 15148,  4945,     0,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    { 26170,  1833,  5196,  9794, 26804,  2831, 11993,  2839,  9979, 27428,  6684,     0,     0,     0,     0,     0,     0,     0,     0,     0,},
    {  4616, 30265,  5752, 32051, 10443,  9240,  8095, 28084, 26285,  8838, 18784,  6547,     0,     0,     0,     0,     0,     0,     0,     0,},
    {  7905,  8373, 19377, 18502, 27928, 13669, 25828, 30502, 28754, 32357,  2843,  5401, 10227,     0,     0,     0,     0,     0,     0,     0,},
    { 22871, 20993,  8558, 10009,  6581, 22716, 12808,  4653, 24593, 21533,  9407,  6840, 30369,  2330,     0,     0,     0,     0,     0,     0,},
    {     3, 28024, 22266, 19327, 18114, 18100, 15644, 21728, 17292,  8396, 27567,  2002,  3830, 12564,  1420,     0,     0,     0,     0,     0,},
    { 29531, 21820,  9954,  8319, 10918,  7978, 24806, 30027, 17659,  8764,  3258, 20719,  6639, 23556, 25786, 11048,     0,     0,     0,     0,},
    {  3544, 31948,    22,  1591,   644, 25981, 26918, 31716, 16427, 15551, 28157,  7107, 27297, 24418, 24384, 32438, 22224,     0,     0,     0,},
    { 12285, 12601, 13235, 21606,  2516, 13095, 27080, 16331, 23295, 20696, 31580, 28758, 10697,  4730, 16055, 22208,  2391, 20143,     0,     0,},
    { 16325, 24537, 16778, 17119, 18198, 28537, 11813,  1490, 21034,  1978,  6451,  2174, 24812, 28772,  5283,  6429, 15484, 29353,  5942,     0,},
    {  7299,  6961, 32019, 24731, 29103, 17887, 17338, 26840, 13216,  8789, 12474, 24299, 19818, 18218, 14564, 31409,  5256, 31930, 26804,  9736,}
};

unsigned char global_behavior[SIZE];
int global_max;

void print()
{
    int i;
    printf("%9d: ", global_max);
    for (i = 0; i < SIZE - 1; i++)
    {
        if (global_behavior[i] == R)
        {
            printf("R");
        }
        else if (global_behavior[i] == L)
        {
            printf("L");
        }
        else
        {
            fprintf(stderr, "Error\n");
            exit(-1);
        }
    }
    puts("");
}

void dfs(int x, int y, int sum)
{
    sum += global_mountain[y][x];
    if (y + 1 == SIZE)
    {
        if (sum > global_max)
        {
            global_max = sum;
            print();
        }
        return;
    }

    global_behavior[y] = L;
    dfs(x, y + 1, sum);

    global_behavior[y] = R;
    dfs(x + 1, y + 1, sum);
}

int main()
{
    global_max = 0;
    dfs(0, 0, 0);
}

运行结果如下所示：

D:\test>cl dfs.c
用于 80x86 的 Microsoft (R) 32 位 C/C++ 优化编译器 16.00.30319.01 版
版权所有(C) Microsoft Corporation。保留所有权利。

dfs.c
Microsoft (R) Incremental Linker Version 10.00.30319.01
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:dfs.exe
dfs.obj

D:\test>dfs.exe
   303755: LLLLLLLLLLLLLLLLLLL
   311629: LLLLLLLLLLLLLLLLLRL
   336687: LLLLLLLLLLLLLLLLLRR
   337003: LLLLLLLLLLLLLLLLRLR
   340349: LLLLLLLLLLLLLLLRLLL
   365407: LLLLLLLLLLLLLLLRLLR
   385717: LLLLLLLLLLLLLRLLLLR
   409956: LLLLLLLLLLRLLLLLLLR
   414282: LLLRRRLLLLLRRLRLLLR
   417845: LLLRRRLRLLLLRLRLLLR
   418308: LLLRRRLRRRRRRRRRLRL
   421759: LLRLRRLLLLLRRLRLLLL
   431261: LLRLRRLLLLLRRLRLLLR
   434824: LLRLRRLRLLLLRLRLLLR
   435287: LLRLRRLRRRRRRRRRLRL
   435796: RRRRRLLRRLLRRRRRLRL
   436700: RRRRRLLRRLRRLRLLRRL
   437600: RRRRRLLRRLRRLRRRLRL
   438528: RRRRRLLRRRLLLLRRRRL
   440237: RRRRRLLRRRLLRRLLRRL
   441137: RRRRRLLRRRLLRRRRLRL
   443840: RRRRRLLRRRLRLRLLRRL
   444740: RRRRRLLRRRLRLRRRLRL

所以RRRRRLLRRRLRLRRRLRL就是我们要走的路径，但是别忘了，还有change_str()函数对Str进行了变换，这个函数需要手动标识，IDA无法正常识别。

void __cdecl change_str(int Str)
{
  change_str_0(Str);
}
void __cdecl change_str_0(int Str)
{
  signed int i; // [esp+D0h] [ebp-44h]

  sub_4110A5(&loc_411953, &loc_411994 - &loc_411953, 4);
  for ( i = 0; i < 19; ++i )
  {
    if ( i % 2 )
      *(_BYTE *)(i + Str) ^= 4u;
  }
  sub_4110A5(&loc_411953, &loc_411994 - &loc_411953, 4);
  nullsub_2();
}

对汇编代码修复完后，就是上面的样子，可以看出该程序对我们的输入的字符串的下标为偶数的值和4进行了异或操作，所以我们只需写一段代码返回他原来样子即可

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char str[] = "RRRRRLLRRRLRLRRRLRL";
    int i;
    for (i = 0; i < strlen(str); i++)
    {
        if (i % 2)
        {
            str[i] ^= 4;
        }
    }
    puts(str);
    return 0;
}

然后我们便拿到了flag。

总结

逆向主要考验选手的洞察能力，以及对一些程序流程的熟悉程度，还有算法也非常重要。

Mountain climbing - BugkuCTF 逆向

TOC

分析