WUSTCTF2020 level4

https://buuoj.cn/challenges#[WUSTCTF2020]level4

elf 64

程序输出：

Practice my Data Structure code.....
Typing....Struct.....char....*left....*right............emmmmm...OK!
Traversal!
Traversal type 1:2f0t02T{hcsiI_SwA__r7Ee}
Traversal type 2:20f0Th{2tsIS_icArE}e7__w
Traversal type 3:    //type3(&x[22]);   No way!

猜测 type3 的结果就是 flag

__int64 __fastcall type1(char *a1)// 中
{
  __int64 result; // rax
 
  if ( a1 )
  {
    type1(*((_QWORD *)a1 + 1));
    putchar(*a1);
    return type1(*((_QWORD *)a1 + 2));
  }
  return result;
}

int __fastcall type2(char *a1)// 后
{
  int result; // eax
 
  if ( a1 )
  {
    type2(*((_QWORD *)a1 + 1));
    type2(*((_QWORD *)a1 + 2));
    return putchar(*a1);
  }
  return result;
}

写过算法题的应该很清楚，就是树的遍历方式，前序，中序和后序，区别在于当前的根节点的输出时机

而通过中后可以推出前序的输出，其实也是分治：

1. 找到当前的根节点
2. 找到左和右
3. 按照前序输出

（啊，为什么突然有种怀时感伤之情（不是））但是 AI 帮我写

根树的遍历

mid = list("2f0t02T{hcsiI_SwA__r7Ee}")  
end = list("20f0Th{2tsIS_icArE}e7__w")  
pre = [0 for i in range(len(mid))]  
  
  
# 已知中序和后序遍历的结果，求前序遍历的结果  
def pre_spell(mid: list, end: list):  
    if len(mid) == 0:  
        return  
    root = end[-1]  
    print(root, end="")  
    index = mid.index(root)  
    pre_spell(mid[:index], end[:index])  
    pre_spell(mid[index + 1:], end[index:-1])  
 
 
pre_spell(mid, end)

wctf2020{This_IS_A_7reE}

---

当然还有其他更加“逆向”的方法

https://xia0ji233.pro/2021/11/02/WUSTCTF2020%20level4%20writeup/index.html

通过 patch 程序来达到修改顺序的效果

55                                      push    rbp
48 89 E5                                mov     rbp, rsp
48 83 EC 10                             sub     rsp, 10h
                        ; 4:   if ( a1 )
48 89 7D F8                             mov     [rbp+var_8], rdi
48 83 7D F8 00                          cmp     [rbp+var_8], 0
74 33                                   jz      short loc_400846
                        ; 6:     type1(*((_QWORD *)a1 + 1));
48 8B 45 F8                             mov     rax, [rbp+var_8]
48 8B 40 08                             mov     rax, [rax+8]
48 89 C7                                mov     rdi, rax
E8 DD FF FF FF                          call    type1
                        ; 7:     putchar(*a1);
48 8B 45 F8                             mov     rax, [rbp+var_8]
0F B6 00                                movzx   eax, byte ptr [rax]
0F BE C0                                movsx   eax, al
89 C7                                   mov     edi, eax        ; c
E8 9C FC FF FF                          call    _putchar
                        ; 8:     return type1(*((_QWORD *)a1 + 2));
48 8B 45 F8                             mov     rax, [rbp+var_8]
48 8B 40 10                             mov     rax, [rax+10h]
48 89 C7                                mov     rdi, rax
E8 BC FF FF FF                          call    type1
EB 01                                   jmp     short locret_400847

先 export data ，变换

# 上面的 type1(*((_QWORD *)a1 + 1));

0x48, 0x8B, 0x45, 0xF8, 0x48, 0x8B, 0x40, 0x08, 0x48, 0x89,

0xC7, 0xE8, 0xDD, 0xFF, 0xFF, 0xFF

# 中间的 putchar(*a1);

0x48, 0x8B, 0x45, 0xF8, 0x0F, 0xB6, 0x00, 0x0F, 0xBE, 0xC0,

0x89, 0xC7, 0xE8, 0x9C, 0xFC, 0xFF, 0xFF

采用 python 脚本来 patch bytes https://papayawd.github.io/2020/10/28/IDA-Python%E5%B8%B8%E7%94%A8%E5%87%BD%E6%95%B0/

里面的函数更新了，命名法是下划线，但是调用方式大差不差

import idc
start = here() # 光标点到开始位置 400813
 
modi = [
0x48, 0x8B, 0x45, 0xF8, 0x0F, 0xB6, 0x00, 0x0F, 0xBE, 0xC0,
 
0x89, 0xC7, 0xE8, 0x9C, 0xFC, 0xFF, 0xFF,
 
0x48, 0x8B, 0x45, 0xF8, 0x48, 0x8B, 0x40, 0x08, 0x48, 0x89,
 
0xC7, 0xE8, 0xDD, 0xFF, 0xFF, 0xFF
 
]
 
for i in range(len(modi)):
	idc.patch_byte(start+i,modi[i])
 

一行行 make code 之后用插件 keypatch 恢复 call 偏移量

patch 程序后拉到 linux 里跑

大 成 功 !!