[原创]第二题南冥神功-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

[原创]第二题南冥神功

2021-5-12 15:38 4191

[原创]第二题南冥神功

brucy

2021-5-12 15:38

4191

0x01 分析

IDA分析，结构很清晰。

100

101

102

103

104

105

106

107

108

109

110

111

112

int __cdecl main(int argc, const char **argv, const char **envp)
{
...
  printf_0((int)&dword_4B8860, "Input your code: ");
  scanf((int)&dword_4B8680, input);//接受用户输入
  if ( strlen(input) <= 0x30 )//长度不能超过0x30
  {
    v3 = input[0];
    if ( input[0] )
    {
      v4 = 0;
      v21 = 0;
      v22 = 0;
      v24 = dword_4B7020;                       // 0x24
      v23 = byte_4B7040[0];
LABEL_4:
      if ( v24 > 0 )
      {
        v5 = 0;
        if ( v23 == v3 )
        {
LABEL_11:                        //这是一个循环结构的循环首，循环次数为input的长度
          v7 = (v4 + v5 / 6) % 6;
          v8 = v5 + v4;
          v9 = v22;
          v20 = v7;
          v10 = 5 - v8 % 6;
          for ( i = 0; ; i = 1 )//实际循环两次
          {
            switch ( v10 )
            {
              case 1:
                ++v9;
                break;
              case 2:
                v17 = (v21++ & 1) == 0;
                v9 += v17;
                break;
              case 3:
                v12 = (v21++ & 1) != 0;
                v9 -= v12;
                break;
              case 4:
                --v9;
                break;
              case 5:
                v19 = (v21-- & 1) != 0;
                v9 -= v19;
                break;
              default:
                v18 = (v21-- & 1) == 0;
                v9 += v18;
                break;
            }
            if ( v9 > 9 )//v9大于9结束最外层循环
              break;
            if ( v21 > 8 )//v21大于8结束最外层循环
              break;
            v13 = &byte_4B7080[10 * v21 + v9];
            if ( *v13 )                         // 这里的v13必须==0，否则直接转到输出Try again!
              break;
            *v13 = 1;//修改byte_4B7080[10 * v21 + v9]=1,标志该地方已经走过
            if ( i == 1 )
            {
              ++v4;//最外层循环的控制变量
              v22 = v9;
              v3 = input[v4];//依次取出input
              if ( v3 )
                goto LABEL_4;//到循环首
              goto LABEL_19;//到判定结果的起始位置
            }
            v10 = v20;
          }
        }
        else
        {
          while ( v24 != ++v5 )
          {
            if ( byte_4B7040[v5] == v3 )
                //v3是input中的某个字符，该循环实际是取得v3字符在byte_4B7040中的下标位置
                //如果v3不存在byte_4B7040中，那么直接转到输出Try again
              goto LABEL_11;
          }
        }
      }
    }
    else
    {
LABEL_19:
      v14 = byte_4B7080;
      v15 = 0;
      do
      {
        v16 = v14 + 10;
        do
          v15 += *v14++ == 0;
        while ( v16 != v14 );//循环10次
      }                                         // 内层循环表示v14[0:10]全为1
      while ( &dword_4B70DA != (_UNKNOWN *)v16 );//一共循环90次
      //所以判定输入正确的条件为byte_4B7080[0:90]均为1！
      if ( !v15 )
      {
        sub_4ABF30(&dword_4B8860, "Good job!", 9);
        sub_4AD980(&dword_4B8860);
        return 0;
      }
    }
  }
  sub_4ABF30(&dword_4B8860, "Try again...", 12);
  sub_4AD980(&dword_4B8860);
  return 0;
}

for循环两次，正确的情况下，输入的一个字符将会把byte_4B7080两个不同地方的0变为1。

让我有许多疑惑的就是for循环中的switch结构，一开始我猜测byte_4B7080是一个迷宫数据，然后我被v9和v21给迷惑住了，以为迷宫是v9*v21的一个长度，但这显然与最后的判定循环次数为90次不符，然后又猜测是不是v9*10，这样确实是符合了数据长度，接下来我以9*10的形式dump下byte_4B7080数据:

0x53 0 1 0 0 1 0 0 1
1    1 1 0 0 1 0 0 1
0    0 0 0 1 0 1 1 1
1    1 0 0 1 1 0 1 0
0    1 0 0 0 0 1 0 0
1    0 0 1 1 1 1 0 1
1    1 0 1 0 1 0 0 1
1    1 1 0 1 0 1 0 1
1    0 0 1 0 1 0 1 0
0    0 1 0 0 1 1 0 0

这个迷宫数据很特别，要怎么走取决于switch结构的运算，在动态调试的时候也不是很明白switch中控制的方向如何，它不是常见的上、下、左、右四种方向，尤其是switch中的位运算，给我一种乱糟糟的感觉。我看不懂方向，所以没法手动去画出路线，这是一个拖我节奏的地方了。也正是看不懂方向，甚至让我怀疑这不是一道迷宫题，而只是另一种算法题——要求在位置不重复的情况下，通过switch结构，将byte_4B7080序列中的0全变为1。

然后，我将伪代码翻译成python代码，并在某些地方做了一些剪枝，试图利用递归去解决这个问题。我通过计数byte_4B7080中的0确定了输入的长度为23。下面是我的解题脚本：

def Check(v):
    t =[0x53,0x0,0x1,0x0,0x0,0x1,0x0,0x0,0x1,0x1,0x1,0x1,0x0,0x0,0x1,0x0,0x0,0x1,0x0,0x0,0x0,0x0,0x1,0x0,0x1,0x1,0x1,0x1,0x1,0x0,0x0,0x1,0x1,0x0,0x1,0x0,0x0,0x1,0x0,0x0,0x0,0x0,0x1,0x0,0x0,0x1,0x0,0x0,0x1,0x1,0x1,0x1,0x0,0x1,0x1,0x1,0x0,0x1,0x0,0x1,0x0,0x0,0x1,0x1,0x1,0x1,0x0,0x1,0x0,0x1,0x0,0x1,0x1,0x0,0x0,0x1,0x0,0x1,0x0,0x1,0x0,0x0,0x0,0x1,0x0,0x0,0x1,0x1,0x0,0x0]
    v9=v21=v22=0
    for i in range(len(v)):
        if v[i]=='':
            return False
        v5=tbl.find(v[i])
        v7 = (i + v5 // 6) % 6
        v8=i+v5
        v9=v22
        v10=5-v8%6
        for j in range(2):
            if v10 == 1:
                v9+=1
            elif v10 == 2:
                v17 = (v21 &1)==0
                v21+=1
                v9+=v17
            elif v10 == 3:
                v12 = (v21 &1)!=0
                v21+=1
                v9-=v12
            elif v10 == 4:
                v9-=1
            elif v10 == 5:
                v19=(v21 &1)!=0
                v21-=1
                v9-=v19
            else:
                v18=(v21 & 1)==0
                v21-=1
                v9+=v18
            if v9 >9 or v9<0  or v21 >8 or v21<0:
                return False#剪枝1
            if t[10*v21+v9] == 1:
                return False#剪枝2
            t[10*v21+v9] = 1
            if j==1:
                v22=v9
            else:
                v10=v7
 
    if len(v)==23:#剪枝3
        return t.count(0)==0
    return True
 
def Trace(v,k,i):
    if k>=23:
        return v
    for j in range(i,len(tbl)):
        if Check(v+[tbl[j]])==True:
            v.append(tbl[j])
            v=Trace(v,k+1,0)
            break
 
    #回溯
    if k>=len(v):
        if len(v)>0:
            p=tbl.find(v[len(v)-1])
            v.pop()
            v=Trace(v,k-1,p+1)
    return v
 
tbl='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
flag=[]
print(''.join(Trace(flag,0,0)))
#GJ0V4LA4VKEVQZSVCNGJ00N