看雪·深信服 2021 KCTF 春季赛 | 第二题设计思路及解析
2021-05-12 18:59:00 Author: mp.weixin.qq.com(查看原文) 阅读量:187 收藏

KCTF 看雪学院

铛铛铛,本次大赛第二题《南冥神功》现已今中午12点截止答题,本题共计 4286 人围观,82支战队成功拿下此题。
该题开放之初,dotsu_战队仅用3188秒就拿下比赛的“一血”。随后不断有战队传来捷报,大家情绪高涨,气氛逐渐推上高潮。
现在该题已结束答题,想必不少小伙伴对该赛题本身也充满兴趣,接下来和我一起来看看该赛题的设计思路和相关解析吧~

专家点评

下面由深信服首席安全研究员:彭峙酿博士给大家带来第二道赛题的点评。

彭峙酿博士:第二题是一个有趣的迷宫吃豆游戏。根据用户输入让玩家从“S”开始走,要求走的过程每一步都要吃到豆子,走完后吃掉了迷宫中的所有豆子。选手通过逆向分析出程序原理,然后通过编程自动化完成游戏。难度不高,但是兼顾比赛性和游戏性,同时考察了大家的逆向分析和编程解决问题的能力。

出题团队简介

第二题《南冥神功》出题方 HU1战队:

lelfei(HU1战队队长),crack爱好者。学生时代对电脑产生了浓厚的兴趣,经历了很长时间的游戏沉迷后,开始慢慢转向学习技术,工作后自学了ASM、VB、VC、HTML、ASP、Python等语言的入门。对单机的逆向分析、算法比较感兴趣。

赛题设计思路

注册码:GJ0V4LA4VKEVQZSVCNGJ00N
难度:易

设计说明:

此题是一个迷宫吃豆游戏,迷宫数据如下:
其中“.”是豆子,“@”是炸弹,运动方向不是一般的上下左右4方向,而是蜂巢一样的6向,每个点链接周围一圈6个点。每走过一个点后该点变为“x”,也就是说每个点只能走一次。根据用户输入让玩家从“S”开始走,要求走的过程每一步都要吃到豆子,走完后吃掉了迷宫中的所有豆子。
程序读取用户输入,要求输入为数字和大写字母一共36个,转换为36进制数后,每一位再转换成2个6进制数,每一位6进制数就是指定一个运动步骤,0为向右上点走,1为向右走,2为向右下走,3为向左下走,4为向左走,5为向左上走。从左上角的“S”开始走,要求运动过程中只能在“.”上走,走后该位置变为“x”。根据用户输入走完全部步骤后,检测迷宫中的“.”数量为0即通关。

运动方向的定义:

 5 0
4 P 1
 3 2
运动记录应为:
1234321234321101210050543450501210121234322321
把这一串6进制数按规则转换为36进制字符即为正确通关码。
此crackme使用CodeBlocks设计,gcc编译,在win7x64下测试通过。
PS:此题pzcrackme意为puzzle迷宫。

赛题解析

本赛题解析由看雪论坛 HHHso 给出:


《未选择的路》 (弗罗斯特)
黄色的树林里分出两条路,
可惜我不能同时去涉足,
我在那路口久久伫立,
我向着一条路极目望去,
直到它消失在丛林深处。
但我却选择了另外一条路,
它荒草萋萋,十分幽寂,
显得更诱人,更美丽;
虽然在这条小路上,
很少留下旅人的足迹。
那天清晨落叶满地,
两条路都未经脚印污染。
啊,留下一条路等改日再见!
但我知道路径延绵无尽头,
恐怕我难以再回返。
也许多少年后在某个地方,
我将轻声叹息将往事回顾:
一片树林里分出两条路--
而我选择了人迹更少的一条,
从此决定了我一生的道路。

【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_keyRN36_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_bytesdef 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)%6opB = (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

主办方

看雪CTF(简称KCTF)是圈内知名度最高的技术竞技之一,从原CrackMe攻防大赛中发展而来,采取线上PK的方式,规则设置严格周全,题目涵盖Windows、Android、iOS、Pwn、智能设备、Web等众多领域。
看雪CTF比赛历史悠久、影响广泛。自2007年以来,看雪已经举办十多个比赛,与包括金山、360、腾讯、阿里等在内的各大公司共同合作举办赛事。比赛吸引了国内一大批安全人士的广泛关注,历年来CTF中人才辈出,汇聚了来自国内众多安全人才,高手对决,精彩异常,成为安全圈的一次比赛盛宴,突出了看雪论坛复合型人才多的优势,成为企业挑选人才的重要途径,在社会安全事业发展中产生了巨大的影响力。
合作伙伴
深信服科技股份有限公司成立于2000年,是一家专注于企业级安全、云计算及基础架构的产品和服务供应商,致力于让用户的IT更简单、更安全、更有价值。目前深信服在全球设有50余个分支机构,员工规模超过7000名。

第三题正在火热进行中,

👆还在等什么,快来参赛吧!

- End -
公众号ID:ikanxue
官方微博:看雪安全
商务合作:[email protected]

球分享

球点赞

球在看

“阅读原文一起来充电吧!

文章来源: http://mp.weixin.qq.com/s?__biz=MjM5NTc2MDYxMw==&mid=2458384835&idx=1&sn=2130da184dd4ba657acecb06355104bc&chksm=b180c94986f7405f3fb558858fcae10abca5a42024f017f6eb618cc123d22409c1a50debc785#rd
如有侵权请联系:admin#unsafe.sh