[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 the characters starting from the last character.

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). (Don't search for "mangled" on Ecosia, it will show gory images.) (Oh, this is a feature of GCC and Clang, see http://web.mit.edu/tibbetts/Public/inside-c/www/mangling.html)

Going off-topic, it is important to use a font that distinguishes between 0 and O. The font in the command prompt can be set to raster fonts (I don't know why the font options in Visual Studio's output window are limited, if you choose a different font, it will default to SimSun).

Finally, we have this section:

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 specific position, so we just need to reverse the process to get the original string. (But I still analyzed the binary tree)

The Node* type is a user-defined structure (I forgot why I used ' 们 ' because Ghidra's auto-generated code helped a bit).

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

Then there is 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 view the structure of root, we can see the tree structure:

(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 the name of this binary tree, but it is clear that it is in level order, from left to right.

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

First, fill in the data with a depth-first search, and then restore the order of building the tree with a 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, we just need to calculate the MD5 hash.

Random thoughts: When I tried to write a 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 the Node ref type, but after finishing it, I got a blue warning, and then I realized that I should use byref now. And when returning, I couldn't directly take the address of the member, so I had to bind it with let first.

Then I was confused, and then I found out that I should discard the old node and return a new one when modifying the node. Ah, I forgot to use functional programming. (But I still used a global variable counter.)

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