CTF逆向-[MRCTF2020]VirtualTree-恒成立的jz花指令去除及smc变换原执行流程在二叉树上的应用，通过逆向思维编写脚本以解决

来源：https://buuoj.cn/

内容：

附件：链接：https://pan.baidu.com/s/1JuQqLSLskTFxOCbXZgUR8g?pwd=da2a 提取码：da2a

答案：MRCTF{@_7r3e_f0r_fuNN!}

总体思路

发现有花指令，去除

发现有smc，动调让其执行

对处理流程中涉及到的函数编写逆向思维脚本反着算

对二叉树的结构进行复原，并写出题目要求的顺序的遍历，按遍历进行操作

得到flag

详细步骤

查看文件内容
检查发现程序中广泛存在该类花指令，jump到一个指令的中间位置。

这种花指令其实是通过先清空eax以后然后给一个恒成立的跳转，并在跳转下面加了一个_emit 0xe8，如下图。
- ```
_asm
{
    xor eax,eax
        jz label1
        _emit 0xE8
        label1:
}
```
对于该花指令，只需要在下面一行右键选patching-patch byte，将e8（执行）改为90（跳过）即可，然后选中下面原来没能正常反汇编的数据，按c点force强行转换就可以得到原文了。
处理完成以后即可得到main函数，进去查看分析整理流程。
其中f_bintree_xor是点进去以后观察发现分别调用了a1，a1+4，a1+8，是典型的struct样式，猜测是二叉树（BinTree），右键a1点击create new struct创建一个结构。这样就会看得比较清楚了，发现它是将树的每一位异或了输入值 (&g_input + g_counter++) ^= a1->data
并且该异或的位置是在左遍历和右遍历中间，是中序遍历
查看f_bintree_xor的引用，发现除了main函数，还有其他地方也引用了，该地方是程序csu初始化的地方。

进入该函数，发现存在一些预处理，该预处理通过smc修改了f_encode_loop函数里面的内容，将每个0x401510替换成汇编list中的一个项。

查看list中的函数，发现也是有花指令，去除花指令以后得到函数原本的含义

int __cdecl f_add_a2(int a1, char a2)
{
  int result; // eax

  result = a1;
  *((_BYTE *)&g_input + a1) += a2;
  return result;
}

int __cdecl f_xor_ginputIndexOfa2(int a1, int a2)
{
  int result; // eax

  result = *((unsigned __int8 *)&g_input + a2);
  *((_BYTE *)&g_input + a1) ^= result;
  return result;
}

int __cdecl f_abs_inputA1_minus_inputA2(int a1, int a2)
{
  __int64 v2; // rax
  int result; // eax
	
  v2 = *((unsigned __int8 *)&g_input + a1) - *((unsigned __int8 *)&g_input + a2);// input[a1] - input[a2]
  result = (HIDWORd(v2) ^ v2) - HIDWORd(v2);    // = lowDWORd(v2) - highDWORd(v2)
  *((_BYTE *)&g_input + a1) = result;
  return result; 
}

注意：f_abs_inputA1_minus_inputA2 abs(input[a1]-input[a2]) 其实就是abs绝对值函数的计算方式，可以参考计算机组成原理

运行程序，观察发现f_loop函数已经被修改完成

int f_encode_loop()
{
  f_add_a2(0, 10);
  f_xor_ginputIndexOfa2(1, 2);
  f_add_a2(2, 7);
  f_abs_inputA1_minus_inputA2(3, 7);
  f_xor_ginputIndexOfa2(4, 5);
  f_abs_inputA1_minus_inputA2(6, 1);
  f_add_a2(7, 3);
  f_xor_ginputIndexOfa2(8, 7);
  f_abs_inputA1_minus_inputA2(9, 8);
  f_abs_inputA1_minus_inputA2(10, 7);
  f_xor_ginputIndexOfa2(11, 12);
  f_abs_inputA1_minus_inputA2(12, 2);
  f_xor_ginputIndexOfa2(14, 15);
  return f_add_a2(15, 2);
}

写出对应的Python逆向思维处理

def f_add_a2(a1: int, a2: int):
    flag[a1] -= a2


def f_xor_ginputIndexOfa2(a1: int, a2: int):
    flag[a1] ^= flag[a2]


def f_abs_inputA1_minus_inputA2(a1: int, a2: int):
    if flag[a1] < flag[a2]:
        # 如果flag[a1]

同时发现在csu下面，其还将f_bintree_xor函数的地址给修改了，变成了f_bintree_xor_same函数的地址，这个函数的逻辑是后序遍历。
查看g_tree的应用，发现除了main函数，还有其他地方也引用了，该地方是程序csu初始化的地方。找到二叉树初始化的位置，并用同样的方法将其转换为BinTree结构
同时发现在初始化额
则该二叉树的后序输出为 [13, 12, 7, 16, 15, 11, 6, 3, 10, 5, 14, 9, 8, 4, 2, 1]

发现data的赋值是 (*(&v1 + j))->data = j + 65;，即从65开始每往后增加1

将g_key的值按shift+e复制出来，17637703522E4A28521B17123A0A6C6200000000，编写逆向脚本

flag = '17637703522E4A28521B17123A0A6C6200000000'  # g_key的值
flag = [x for x in bytearray.fromhex(flag)]


def f_add_a2(a1: int, a2: int):
    flag[a1] -= a2


def f_xor_ginputIndexOfa2(a1: int, a2: int):
    flag[a1] ^= flag[a2]


def f_abs_inputA1_minus_inputA2(a1: int, a2: int):
    if flag[a1] < flag[a2]:
        # 如果flag[a1]

根据题目要求your flag: MRCTF{%s}n最后答案为 MRCTF{@_7r3e_f0r_fuNN!}

注意在后序输出中，是先遍历左子树，即B，再遍历右子树即C，最后才是A。（这里面的B和C都是一个狗，和sin狗的那个狗是同一个狗，什么妖魔鬼怪都可放，x）

前序：ABC 中序：BAC 后序：BCA

其他文档

CTF逆向-常用的逆向工具提取码：pnbt
B站教程中国某省队CTF集训(逆向工程部分)
- 中国某省队CTF集训(逆向工程部分)(已授权)(一)
- 基础加密方式例如 XXTEA、Base64换表
- Python库 Z3 方程式、不定式等的约束求解
- 基础的假跳转花指令(脏字节)
- 非自然程序流程
  - 扁平化程序控制流
  - OLLVM程序流程（虚拟机壳）很难一般不考
  - ida里面按X键跟踪，寻找所有Ty为w的引用（即类型是写入的），通常就是关键位置
- 中国某省队CTF集训(逆向工程部分)(已授权)(二)
- ollydb动调去壳，upx为例子
- python的逆向和自定义虚拟指令
  - 使用pycdc 提取码：dorr 解密python编译的exe或者pyc
  - 逐条去解析用py字典手动实现的指令调用
  - C++编译的程序的逆向
- 中国某省队CTF集训(逆向工程部分)(已授权)(三)
  - 简单模运算加密
  - base58 寻找一下特别大的数，这种数通常是算法的标识，或者ida7.7版本以上自带的find crypt插件ctrl+alt+f
  - 常见的关键位置是有新的内存分配的地方通常是关键地方，或者函数中间突然return的地方也是
  - 迷宫题注意绘制出来就好
  - 动调题
    - 注意观察会执行的反调试分支，例如出现int 3，需要跳过去
基本知识
- 大小端序

更多CTF逆向题通用性做法和常用工具下载参考该博文内容：CTF逆向Reverse题的玩法

CTF逆向-[MRCTF2020]VirtualTree-恒成立的jz花指令去除及smc变换原执行流程在二叉树上的应用，通过逆向思维编写脚本以解决

Python相关栏目本月热门文章