2015 华山杯 CTF Reverse 300

2015 华山杯 CTF Reverse 300#

提示

这是一篇迁移自 Jekyll 的文章,如有格式问题,可到 ⛺ SilverRainZ/bullet 反馈

程序在此: toetrix-crackme.exe, VC++ 6.0 编写,无壳, CLI 程序。

这题本来我是一点都不会的,幸得尖刀某大牛指点思路,之后回头看反编译的代码 总算是摸清楚了程序的流程。因为这种复杂度的题目之前没有做出来过,特此记录。

程序很像一个推箱子游戏,在一个 9*9 的二维地图中有三种元素: 0,1,10 * x + 2 分别代表空气,障碍和箱子,你需要做的就是将所有的箱子推出地图。

程序储存的地图如下:

.data:00407030 ; char map[]
.data:00407030 map             db 1, 1, 0, 1, 1, 1, 0, 1, 1
.data:00407030                 db 1, 0, 0, 0, 0, 0, 0, 0, 1
.data:00407030                 db 1, 0, 0, 0, 0, 0Ch, 16h, 0, 1
.data:00407030                 db 1, 20h, 0, 0, 0, 2Ah, 0, 0, 1
.data:00407030                 db 0, 0, 0, 0, 0, 0, 0, 0, 0
.data:00407030                 db 1, 0, 0, 34h, 0, 0, 0, 0, 1
.data:00407030                 db 0, 0, 0, 0, 0, 0, 3Eh, 0, 0
.data:00407030                 db 1, 48h, 0, 0, 52h, 0, 0, 0, 1
.data:00407030                 db 1, 1, 0, 1, 1, 1, 1, 0, 1

转化成十进制:

1,  1, 0,  1,  1,  1,  0, 1, 1
1,  0, 0,  0,  0,  0,  0, 0, 1
1,  0, 0,  0,  0, 12, 22, 0, 1
1, 32, 0,  0,  0, 42,  0, 0, 1
0,  0, 0,  0,  0,  0,  0, 0, 0
1,  0, 0, 52,  0,  0,  0, 0, 1
0,  0, 0,  0,  0,  0, 62, 0, 0
1, 72, 0,  0, 82,  0,  0, 0, 1
1,  1, 0,  1,  1,  1,  1, 0, 1

可以看到每个箱子都是 X2 形式的数字。

用 IDA 分析整理得到 main 函数代码如下:

int __cdecl main(int argc, const char **argv, const char **envp)
{
    char *step; // esi@1
    char direct; // bl@2
    int start; // eax@2
    int result; // eax@13
    int x; // [sp+8h] [bp-30h]@2
    int y; // [sp+Ch] [bp-2Ch]@2
    char input; // [sp+10h] [bp-28h]@1
    char v10; // [sp+36h] [bp-2h]@1

    step = &input;
    printf(aInputYourSn);
    scanf(aS, &input);
    v10 = 0;
    if ( input )
    {
        do
        {
            direct = step[1];
            start = *step - 48;
            step += 2;
            if ( !find_start(start, (int)&y, (int)&x) )// 遍历数组 返回的 x y 是箱子坐标
                break;
            switch ( direct )
            {
                case 49:                                // '1' 左
                    go_left(y, x);
                    break;
                case 50:                                // '2' 右
                    go_right(y, x);
                    break;
                case 51:                                // '3' 上
                    go_up(y, x);
                    break;
                default:
                    if ( direct != 52 )
                        goto LABEL_12;
                    go_down(y, x);                      // '4' 下
                    break;
            }
        }
        while ( *step );
    }
LABEL_12:
    if ( check_no_start() )
    {
        printf(aBDBuzeBuDGoodJ);                        // ∑(っ °Д °;)っ  good job!
        result = 0;
    }
    else
    {
        printf(aIsbuzebuIsjrII);                        // (╯°Д°)╯︵ ┻━┻  try again!
        result = 0;
    }
    return result;
}

程序接受的输入以两个十进制位位为一组, 第一位 start 来指定一个箱子: 地图中值为(10 * start + 2)的元素 (在 find_start 函数中处理,返回 x,y 为箱子的坐标); 第二位 direct 用来指定推箱子的方向,字符 1 2 3 4 分别代表方向左右上下 (由 go_xx 函数处理)。

比如序列 2321 就是把值为 2*10 + 2 = 22 的箱子往上 3 移动, 再把该箱子往左 1 移动。

看一下 find_start 函数:

char __cdecl find_start(int start, int e_y, int e_x)
{
    int x; // ecx@3
    int y; // eax@5

    *(_DWORD *)e_y = 0;
    while ( 2 )
    {
        *(_DWORD *)e_x = 0;
        do
        {
            x = *(_DWORD *)e_x;
            /* *(&map + 9 * (*e_y) + *e_x)  ->  map[y][x] */
            if ( *(&map[8 * *(_DWORD *)e_y] + *(_DWORD *)e_y + *(_DWORD *)e_x) == 10 * start + 2 )
                return 1;
            *(_DWORD *)e_x = x + 1;
        }
        while ( x + 1 < 9 );
        y = *(_DWORD *)e_y + 1;
        *(_DWORD *)e_y = y;
        if ( y < 9 )
            continue;
        break;
    }
    return 0;
}

函数遍历整个二维数组 map,如果在 map 中发现等于 10 * start + 2 的数字就 return 此时 e_x e_y 中便是该点坐标。

接下来看 go_left 函数:

char *__cdecl go_left(int y, int x)
{
  int i; // eax@1

  for ( i = x - 1; i >= 0; --i )
  {
    if ( *(&map[9 * y] + i) )                   // 遇到非 0 点
      break;
  }
  if ( i == -1 )
    *(&map[8 * y] + y + x) = 1;                 // 边缘检测
  return xchg_point(y, x, y, i + 1);            // 交换本次起点和终点的值,如果到达边缘,交换的就是同一个点。
}

该函数接受箱子的坐标,然后往坐标的左边走(x -> 0), 如果遇到一个非 0 点,即跳出循环。

如果 i == -1 说明从该箱子左边到边界都是 0,箱子可以移出地图了, 于是把该箱子坐标处的值标记为 1(变成障碍了,便于接下来交换)。

接下来函数把箱子的坐标 (x, y) 和 移动终点的坐标 (i+1, y) 传给函数 xchg_point, 函数 xchg_point 比较简单,仅仅是交换两个点的值。

这样就完成了一次左移,go_right go_up 等函数同理。

备注

如果终点是边界的话,箱子的值会被置为 1,交换后的结果就是:箱子处变为 0,终点变为 1。

处理完一次移动之后 step 自增 2,进行下一次移动,直到整个序列结束。 就执行 check_no_start 做最后的检查:

char check_no_start()
{
    signed int y; // esi@1
    signed int x; // ecx@2

    y = (signed int)map;
    while ( 2 )
    {
        x = 0;
        do
        {
            if ( *(_BYTE *)(y + x) % 10 == 2 )      // 有一个箱子
                return 0;
            ++x;
        }
        while ( x < 9 );
        y += 9;
        if ( y < (signed int)&end_of_map )
            continue;
        break;
    }
    return 1;
}

检查整个 map 中是否有形如 X2 的数字,即是否还有箱子存在, 如果没有的话,返回 1,这就是我们期望的结果。

根据以上流程我们就可以手动算出一个能移除所有箱子的序列,

备注

每个箱子移动可以不是连续的,可以先移动一个箱子到一个地方,再去移动另一个。

移动箱子的顺序的和路径如下:

62 = 62
52 = 515351
82 = 8183
72 = 7372
42 = 4441
12 = 141114
32 = 3431
22 = 23
42 = 4244

因此得到 key: 625153518183737244411411143431234244

附上分析时使用的 idb 数据库

评论

如果你有任何意见,请在此评论。 如果你留下了电子邮箱,我可能会通过 回复你。