[2019_Redhat]childRE - BuringStraw

64-bit PE without shell. Open the main function.

Source of the problem: xctf

First, check if the input length is 31 characters. If not, it will get stuck.

scanf("%s",input);
lVar5 = -1;
do {
 str_len = lVar5 + 1;
 lVar4 = lVar5 + 1;
 lVar5 = str_len;
} while (input[lVar4] != '\0');
if (str_len != 31) {
 do {
   Sleep(1000);
 } while( true );
}

According to other write-ups, we need to analyze from the last character comparison.

while( true ) {
   if ("1234567890-=!@#$%^&*()_+qwertyuiop[]QWERTYUIOP{}asdfghjkl;\'ASDFGHJKL:\"ZXCVBNM<>?zxcvbnm, ./"
      [(int)(&out_DAT_1400056c0)[lVar5] % 0x17] != (&DAT_140003478)[lVar5]) {
                 /* WARNING: Subroutine does not return */
     _exit(_Code);
   }
   if ("1234567890-=!@#$%^&*()_+qwertyuiop[]QWERTYUIOP{}asdfghjkl;\'ASDFGHJKL:\"ZXCVBNM<>?zxcvbnm, ./"
      [(int)(&out_DAT_1400056c0)[lVar5] / 0x17] !=
      "55565653255552225565565555243466334653663544426565555525555222"[lVar5]) break;
   _Code = _Code + 1;
   lVar5 = lVar5 + 1;
   if (0x3d < _Code) {
     printf("flag{MD5(your input)}\n");
     __security_check_cookie(uVar3 ^ (ulonglong)auStack_58);
     return extraout_EAX_00;
   }
 }

Copy the value of DAT_140003478 and write a script.

_Code = 0
lVar5 = 0
out_DAT_1400056c0 = [" "] * 0x3e
DAT_140003478 = [ 0x28, 0x5f, 0x40, 0x34, 0x36, 0x32, 0x30, 0x21, 0x30, 0x38, 0x21, 0x36, 0x5f, 0x30, 0x2a, 0x30, 0x34, 0x34, 0x32, 0x21, 0x40, 0x31, 0x38, 0x36, 0x25, 0x25, 0x30, 0x40, 0x33, 0x3d, 0x36, 0x36, 0x21, 0x21, 0x39, 0x37, 0x34, 0x2a, 0x33, 0x32, 0x33, 0x34, 0x3d, 0x26, 0x30, 0x5e, 0x33, 0x26, 0x31, 0x40, 0x3d, 0x26, 0x30, 0x39, 0x30, 0x38, 0x21, 0x36, 0x5f, 0x30, 0x2a, 0x26 ]
while True:
    ans = 0
    print(DAT_140003478[lVar5])
    for i in range(128):
        print(i, end=" ")
        if ord("""1234567890-=!@#$%^&*()_+qwertyuiop[]QWERTYUIOP{}asdfghjkl;\'ASDFGHJKL:\"ZXCVBNM<>?zxcvbnm,. /"""[i % 0x17]) != DAT_140003478[lVar5]:              
            continue
        if ord("""1234567890-=!@#$%^&*()_+qwertyuiop[]QWERTYUIOP{}asdfghjkl;\'ASDFGHJKL:\"ZXCVBNM<>?zxcvbnm,. /"""[i // 0x17]) !=         ord("55565653255552225565565555243466334653663544426565555525555222"[lVar5]):
            continue
        ans = i
        break
    out_DAT_1400056c0[_Code] = ans
    _Code = _Code + 1;
    lVar5 = lVar5 + 1;
    print()
    if (0x3d < _Code):
        print("".join(map(chr,out_DAT_1400056c0)))
        break

Obtain private: char * __thiscall R0Pxx::My_Aut0_PWN(unsigned char *)

Moving forward:

UnDecorateSymbolName(symbol_name,&out_DAT_1400056c0,0x100,0);
lVar5 = -1;
do {
 lVar4 = lVar5 + 1;
 pcVar1 = &DAT_1400056c1 + lVar5;
 lVar5 = lVar4;
} while (*pcVar1 != '\0');
if (lVar4 != 62) {
 this = FUN_1400018a0((longlong *)cout_exref);
 std::basic_ostream<char,struct_std::char_traits<char>_>::operator<<
          ((basic_ostream<char,struct_std::char_traits<char>_> *)this,FUN_140001a60);
 __security_check_cookie(uVar3 ^ (ulonglong)auStack_58);
 return extraout_EAX;
}

Regarding UnDecorateSymbolName, it is well known that compilers transform symbols into unreadable forms (referred to as mangling) (do not search for "mangled" using Ecosia, it will show graphic images, eww). (Oh, this is a thing in GCC and Clang, see http://web.mit.edu/tibbetts/Public/inside-c/www/mangling.html)

Going off-topic, make sure to use a font that distinguishes between 0 and O. The font in cmd can be set to raster fonts (I don't know why the font options in VS output window are limited, if you choose a different font it will fall back to SimSun).

Finally, we have this part:

iVar2 = FUN_140001280(input);
root = (Node *)CONCAT44(extraout_var,iVar2);
symbol_name = &sym_name_DAT_1400057c0;
if (root != (Node *)0x0) {
 dfs(root->left);
 dfs(root->right);
 symbol_name[i_DAT_1400057e0] = root->v;
 i_DAT_1400057e0 = i_DAT_1400057e0 + 1;
}

To save time: dynamic debugging reveals that it is a permutation at a certain position, so we just need to reverse the process to get the original order. (But I still analyzed this binary tree)

The Node* type is a user-defined structure (I forgot what it's called, but Ghidra's auto-generated code helped).

Offset	Length	Type	Name
0	1	char	v
1~7	1	undefined
8	8	Node *	left
16	8	Node *	right

Then there's the dfs function, before renaming it to dfs, I couldn't understand it.

But now it's clear, it's a post-order traversal and stores the values in sym_name.

void dfs(Node *param_1)
{
 if (param_1 != (Node *)0x0) {
   dfs(param_1->left);
   dfs(param_1->right);
   (&sym_name_DAT_1400057c0)[i_DAT_1400057e0] = param_1->v;
   i_DAT_1400057e0 = i_DAT_1400057e0 + 1;
 }
 return;
}

Using IDA to debug and check the structure of root, we can see what the tree looks like:

(IDA may not recognize the operation of splitting a variable in memory into two registers, for example, you need to right-click on v6 and map it to v4.)

I forgot what this binary tree is called, but it's basically a level-order traversal from left to right.

By the way, let's practice writing data structures in F#.

First, fill in the data using depth-first search, then restore the order using breadth-first search.

open System.Collections.Generic

type Node =
    { v: char
      l: Node option
      r: Node option }

let mutable cnt = 0

let s = "?My_Aut0_PWN@R0Pxx@@AAEPADPAE@Z"

let rec dfs (dep: int) (p: Node) : Node =
    if dep <= 5 then
        let r =
            { p with
                l = Some({ v = ' '; l = None; r = None } |> dfs (dep + 1))
                r = Some({ v = ' '; l = None; r = None } |> dfs (dep + 1))
                v = s[cnt] }

        cnt <- cnt + 1
        r
    else
        p

let root = dfs 1 { v = ' '; l = None; r = None }

let q = new Queue<Node>()

q.Enqueue root

while q.Count > 0 do
    let t = q.Dequeue()
    printf "%c" t.v

    if t.l.IsSome then
        q.Enqueue t.l.Value

    if t.r.IsSome then
        q.Enqueue t.r.Value

We get: Z0@tRAEyuP@xAAA?M_A0_WNPx@@EPDP

Finally, calculate the MD5 hash.

Random thoughts: When I tried to write the binary tree in F#, I initially wanted to make the nodes mutable. As a result, it became type Node ={ v: char;l: Node ref option;r: Node ref option}.

Want to access the Node inside? Unwrap two layers. And when passing by reference, I initially wrote Node ref type, but after finishing, I got a blue warning telling me to use byref. And when returning, I couldn't directly take the address of the member, I had to bind it with let first.

Then I was stuck, only to find out that when modifying a node, I should discard it and return a new one. Ah, I forgot to use functional programming. (But I still used a global variable for counting.)

Actually, I randomly came across this problem. I felt like doing the challenges in order of difficulty, but suddenly there were a few new challenges that couldn't satisfy my OCD, so I decided to break the order here. Then I randomly came across this difficulty 6 challenge. Then I was scared by the function for building the tree. Then I looked at the write-up. Then I was told it was a sign-up challenge. Sob sob sob.