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