【南京邮电】maze 迷宫解法

时间:2021-02-03 09:27:27

【南京邮电】maze 迷宫解法

0x0 初步分析

题目中给出的执行文件是64位ELF可执行文件,可在64 位 Ubuntu下运行。这是一道简单的迷宫类型题目,通过静态分析即可获得flag。

在main函数中,能发现一段字符串

  *******   *  **** * ****  * ***  *#  *** *** ***     *********

为了方便阅读:

  • 空格替换为'.'
  • 二维重排列(8x8)
..******
*...*..*
***.*.**
**..*.**
*..*#..*
**.***.*
**.....*
********

通过该地图,可以预判:

  • '#' 为目标坐标
  • 左上角为(0,0)
  • '*' 为边界,空格(点)为通路
  • 手动画出通往目标的线

这道题目的意思很清晰,假设有一个小人站在初始坐标上,我们要控制小人走到‘#’所在的坐标。

需要通过逆向分析得出:

  • 小人的初始坐标
  • 指令的对应关系(上下左右)

0x1 逆向分析

以下分析结果基于IDA的伪代码 、IDA流程图、IDA反汇编结果等。

标准输入

scanf("%s", &s1, 0LL);

格式验证

 if ( strlen(&s1) != 24 || (v3 = "nctf{", strncmp(&s1, "nctf{", 5uLL)) || *(&byte_6010BF + 24) != '}' )
{
.......
}

输入应该以nctf{ 开头,以}结尾。

读取小人移动指令

 char v5 = 0
int v4 = 5; // 从nctf{后面的第一个字节开始读取
if ( strlen(&s1) - 1 > 5 ) // s1 是scanf 输入的数据。
{
while ( 1 )
{
v5 = *(&s1 + v4);
............

确认x、y轴变量

main函数中调用的一处验证函数。

__int64 __fastcall sub_400690(__int64 a1, int a2, int a3)
{
__int64 result; // rax result = *(unsigned __int8 *)(a1 + a2 + 8LL * a3);
LOBYTE(result) = (_DWORD)result == ' ' || (_DWORD)result == '#';
return result;
}
  • a3 * 8 => a3参数对应y轴
  • a2 对应x轴
  • 通路为空格或#

a3 通过edx传递

a2 通过esi传递

main函数中验证行动合理性的代码

mov     esi, dword ptr [rsp+28h+var_28+4] ;x
mov edx, dword ptr [rsp+28h+var_28] ;y
mov edi, offset asc_601060 ; " ******* * **** * **** * *** *# "...
call sub_400690 # 这个函数检查(x,y)是否合法,是不是通路

可以推断main函数中var_28 是y轴,var_28+4 是x轴。

main函数的头部可以找到初始化代码:

mov     dword ptr [rsp+28h+var_28+4], 0
mov dword ptr [rsp+28h+var_28], 0

可以推断小人的初始坐标为(0,0)

四个方向的指令

为方便阅读,笔者已经对代码合并处理。

		__int64 v10; // [rsp+0h] [rbp-28h]
if ( (unsigned __int8)v5 == 'O' )
{
v7 = sub_400650((char *)&v10 + 4, v3);
goto LABEL_14;
} bool __fastcall sub_400650(_DWORD *a1)
{ // 减法操作
int v1; // eax
v1 = (*a1)--;
return v1 > 0;
}

v10 这个变量其实就是[rsp+28h+var_28],

v10的地址 + 4 就是x轴变量地址。

如果伪代码不清晰可以看反汇编。

所以得出指令‘O’:

O => x-=1

其它三条指令类似处理。

		if ( v5 == 'o' )
{
v7 = sub_400660((char *)&v10 + 4, v3);
goto LABEL_14;
} bool __fastcall sub_400660(int *a1)
{
int v1; // eax v1 = *a1 + 1;
*a1 = v1;
return v1 < 8;
}

得出如下结论:

o => x+=1
		if ( (unsigned __int8)v5 == '.' )
{
v7 = sub_400670(&v10, v3);
goto LABEL_14;
}

sub_400670 前文已经分析过,为减法操作。

得出:

. => y-=1

最后一个操作:

        if ( v5 == '0' )
{
v7 = sub_400680(&v10, v3);
LABEL_14:
v6 = v7;
goto LABEL_15;
}

得出:

0 => y+=1

综合所有操作

O => x-=1 左移
. => y-=1 上移
o => x+=1 右移
0 => y+=1 下移

结果

nctf{o0oo00O000oooo..OO}