首页
论坛
课程
招聘
[原创] KCTF 2021 Spr. 第二题 未选择的路
2021-5-11 21:00 4106

[原创] KCTF 2021 Spr. 第二题 未选择的路

HHHso 活跃值
22
2021-5-11 21:00
4106


《未选择的路》 (弗罗斯特)

黄色的树林里分出两条路,

可惜我不能同时去涉足,

我在那路口久久伫立,

我向着一条路极目望去,

直到它消失在丛林深处。

但我却选择了另外一条路,

它荒草萋萋,十分幽寂,

显得更诱人,更美丽;

虽然在这条小路上,

很少留下旅人的足迹。

那天清晨落叶满地,

两条路都未经脚印污染。

啊,留下一条路等改日再见!

但我知道路径延绵无尽头,

恐怕我难以再回返。

也许多少年后在某个地方,

我将轻声叹息将往事回顾:

一片树林里分出两条路--

而我选择了人迹更少的一条,

从此决定了我一生的道路。


【0x100】望

    (下载、)解压、执行,如图;console应用,相对(KCTF 2021 Spr. 第一题)的10KB,777KB略大。

【0x200】切

    拖进IDA进行分析,环境(IDA Pro 7.5, Python 3.8)

    如图,自动定位到_main函数处;

    概览下上下文,不妨根据上述输出信息猜定几个全局变量(Hi_stdout,Hi_stdin)和函数命名(Hi_init,Hi_cout,Hi_cin),其意义未必完全贴合其名,只是初步接近。


上图尾部的业务逻辑有些费解,F5伪码能很好应对这种情形,可见实现的是strlen功能,如下图

【0x210】

    _main函数伪码如下

int __cdecl main(int argc, const char **argv, const char **envp)
{
  char lv_kc; // al
  int lv_ki; // esi
  int lv_kv; // ecx
  int lv_ivm; // edx
  int lv_iv; // eax
  unsigned int lv_col; // ecx
  int lv_opAB; // eax
  int bsec; // edx
  int lv_is_odd_row; // eax
  char *lv_rAtRowCol; // eax
  char *lv_xrow_p; // eax
  int lv_sbz; // edx
  char *lv_xrow_end; // ecx
  int lv_is_even_row; // eax
  int lv_is_even_row_; // eax
  int lv_is_odd_row_; // eax
  int lv_ivm_; // [esp+1Ch] [ebp-60h]
  unsigned int lv_row; // [esp+20h] [ebp-5Ch]
  unsigned int lv_cur_col; // [esp+24h] [ebp-58h]
  char lv_tc; // [esp+2Bh] [ebp-51h]
  int lv_radix; // [esp+2Ch] [ebp-50h]
  char lv_key[76]; // [esp+30h] [ebp-4Ch] BYREF

  Hi_init();
  Hi_cout((int)&Hi_stdout, "Input your code: ");
  Hi_cin((int)&Hi_stdin, lv_key);
  if ( strlen(lv_key) <= 0x30 )
  {
    lv_kc = lv_key[0];
    if ( lv_key[0] )
    {
      lv_ki = 0;
      lv_row = 0;
      lv_cur_col = 0;
      lv_radix = Hi_radix;
      lv_tc = Hi_RN_tbl[0];
lbl_con:
      if ( lv_radix > 0 )
      {
        lv_kv = 0;
        if ( lv_tc == lv_kc )
        {
lbl_cv:
          lv_ivm = (lv_ki + lv_kv / 6) % 6;
          lv_iv = lv_kv + lv_ki;
          lv_col = lv_cur_col;
          lv_ivm_ = lv_ivm;
          lv_opAB = 5 - lv_iv % 6;
          for ( bsec = 0; ; bsec = 1 )
          {
            switch ( lv_opAB )
            {
              case 1:
                ++lv_col;
                break;
              case 2:
                lv_is_even_row = (lv_row++ & 1) == 0;
                lv_col += lv_is_even_row;
                break;
              case 3:
                lv_is_odd_row = (lv_row++ & 1) != 0;
                lv_col -= lv_is_odd_row;
                break;
              case 4:
                --lv_col;
                break;
              case 5:
                lv_is_odd_row_ = (lv_row-- & 1) != 0;
                lv_col -= lv_is_odd_row_;
                break;
              default:
                lv_is_even_row_ = (lv_row-- & 1) == 0;
                lv_col += lv_is_even_row_;
                break;
            }
            if ( lv_col > 9 )
              break;
            if ( lv_row > 8 )
              break;
            lv_rAtRowCol = &Hi_map[lv_row][lv_col];
            if ( *lv_rAtRowCol )
              break;
            *lv_rAtRowCol = 1;
            if ( bsec == 1 )
            {
              ++lv_ki;
              lv_cur_col = lv_col;
              lv_kc = lv_key[lv_ki];
              if ( lv_kc )
                goto lbl_con;
              goto lbl_end;
            }
            lv_opAB = lv_ivm_;
          }
        }
        else
        {
          while ( lv_radix != ++lv_kv )
          {
            if ( Hi_RN_tbl[lv_kv] == lv_kc )
              goto lbl_cv;
          }
        }
      }
    }
    else
    {
lbl_end:
      lv_xrow_p = (char *)Hi_map;
      lv_sbz = 0;
      do
      {
        lv_xrow_end = lv_xrow_p + 10;
        do
          lv_sbz += *lv_xrow_p++ == 0;
        while ( lv_xrow_end != lv_xrow_p );
      }
      while ( &Hi_map_end != lv_xrow_end );
      if ( !lv_sbz )
      {
        Hi_cout_buf_len(&Hi_stdout, "Good job!", 9);
        xdtor(&Hi_stdout);
        return 0;
      }
    }
  }
  Hi_cout_buf_len(&Hi_stdout, "Try again...", 12);
  xdtor(&Hi_stdout);
  return 0;
}

(1)在switch分支中,我们有理由猜测是vm或迷宫,稍微深入些分析,确定是迷宫无疑;

如下图,这是各行、列号从0开始,列号lv_col不超过9,行号不超过8的9行10列迷宫图,char map[9][10]

(2)其方向基础操作码有6个,分别为1,2,3,4,5,0,由于2、3、5、0着四个操作码考虑到行号奇偶属性,复用出8种操作,结合1、4两个操作,总共是6个操作码10种操作。如下图,为操作码对应的操作动作

操作动作方向示意图:

【0x220】

我们看下key到操作码的转换过程,

(1)lv_ki记录每个字符lv_kc在lv_key中的位置,lv_kv为lv_kc通过36进制数转换而来,基本关系如下Python伪码

#lv_key
RN36_tbl = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
for lv_ki,lv_kc in enumerate(lv_key)
  lv_kv = RN36_tbl.index(lv_kc)


(2)每个lv_kv值延申出两个操作码,opA和opB,从当前位置根据操作码执行对应的操作进行路径选择,

从S(0,0)开始,只能走向0的位置,走过后被置为1,最后检验所有0的位置都走过(置一)后则通过。


(3)迷宫

    通过下述IDAPython代码,我们可以得到类似下图的迷宫,从S开始,只能往”0“位置走,需要一次过踏遍迷宫中所有的”0“,由于一个key字符回产生两个操作,所以走迷宫的时候,一般也是两步两步走。

import ida_bytes
def get_map(ea = 0x4B7080):
  print("--"*20)
  m = ida_bytes.get_bytes(ea,90)
  m = m.replace(b'\x00',b'0').replace(b'\x01',b'1').decode()
  for i in range(0,len(m),10):
    print("{} {}".format((i//10)&1,m[i:i+10]))

get_map()

  【0x230】未选择的路


(1)起步姿势都不会有问题,从S(0,0)开始向右(Right)走到(0,1),然后往右下方(even-row Down & Right)到(1,2)位置;

(2)但从(1,2)位置可以选择的路径右三条之多,哪一条才是正确的呢?这里产生了路径选择。

        理论上,通过完整的算法理论去枚举原则上是可行的。不过放着大脑不用,有点浪费。

(3)既然都用上了逆向工具,我们不妨用下逆向思维,用类似逆向推定、各个(段)击破的方式,用人脑识别下:

(3.1)分段逆推,比如上述迷宫地图右下角(8,9)位置,只能来自(8,8)位置,而(8,8)位置只能源自(7,8)位置,依次类推,我们得到某一小段路径(图中A),

        同理,通过路径上的一些位置如图中红色箭头所示位置,从这些点位置向两端扩散,直到产生歧路为止,如图可得到A、B、C、D四小段。

       

 如果从(1,2)位置选择B路径,当走到A时,会导致部分路径没走过,所以否决往B路径走,这时B路径不扩散到(1,2)位置,则继续往下扩散。

且决定了从(1,2)位置只能往路径D方向走,而从D到C,C不能往A走,于是整条路径就唯一决定了。


于是,从S(0,0位置开始,经过D、C、B、A一次过走完迷宫中所有”0“位置,根据定义的操作

我们可以使用上述定义的操作来描述行走的轨迹strace=opABs,如下,其中分号“;”对key产生的操作两两分组,逗号“,”分隔组内操作。每组两个操作对应key的一个字符来源。如开始的轨迹“R,0DR;1DL,L;0D,1D"翻译为自然语言就是:从S(0,0)开始,根据key[0]对应产生两个操作R(向右),0DR(偶行号向下和向右),来到了(1,2)位置。接着由下个key[1]对应产生的两个操作1DL(奇行号向下和向左),L(向左),来到(2,0)位置。依次类推.


在main代码中
opA = 5 - (ki+kv)%6
opB = (ki+kv/6) %6
所以知道了key[ki]对应产生的两个操作码opA,opB和ki就可以简单逆推得到kv,从而得到key[ki],这里原则上可以使用numpy的solve方法解方程。
但考虑kv取值为[0,36),直接枚举求解。
def get_kv(ki,a,b):
  for x in range(36):
    if 5-((x+ki)%6)==a and (ki+(x//6))%6==b:
      return x

于是通过下述Python代码,将迷宫轨迹opABs各个行动操作转换为操作码,再求解kv则可得到最终的key

从上述操作名到操作码的反向映射 opName2opCode


opName2opCode = {
  "R":1,
  "0DR":2,
  "1D":2,
  "0D":3,
  "1DL":3,
  "L":4,
  "0U":5,
  "1UL":5,
  "0UR":0,
  "1U":0
}

def get_kv(ki,a,b):
  for x in range(36):
    if 5-((x+ki)%6)==a and (ki+(x//6))%6==b:
      return x

opABs = "R,0DR;1DL,L;0D,1D;R,0DR;1DL,L;0D,1D;R,R;0UR,R;1D,R;0UR,1U;0U,1U;0U,L;1DL,L;0U,1U;0U,1U;R,0DR;R,1U;R,0DR;R,1D;0D,L;1DL,0DR;1D,0D;1D,R"
opABs = opABs.split(";")
key = ''
for i,opAB in enumerate(opABs):
  opA,opB = opAB.split(',')
  kv = get_kv(i,opName2opCode[opA],opName2opCode[opB])
  print(i,opAB,(opName2opCode[opA],opName2opCode[opB]),kv)
  key += '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'[kv]

print(key)

GJ0V4LA4VKEVQZSVCNGJ00N


则,key为 GJ0V4LA4VKEVQZSVCNGJ00N







看雪招聘平台创建简历并且简历完整度达到90%及以上可获得500看雪币~

收藏
点赞3
打赏
分享
最新回复 (1)
雪    币: 3643
活跃值: 活跃值 (3824)
能力值: ( LV9,RANK:181 )
在线值:
发帖
回帖
粉丝
nevinhappy 活跃值 2 2021-5-12 13:28
2
0
分析的很清楚了!
游客
登录 | 注册 方可回帖
返回