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 数据库
如果你有任何意见，请在此评论。 如果你留下了电子邮箱，我可能会通过 回复你。