PE02 - Figure Out The Chess’s Path

Key takeaways

Reversing the Knight’s tour 6x6
Find out the real path and target

Case Summary

If you execute the program, your first step was to type in the input that have 36 bytes but it might not take them to compare directly. It ran the DFS Knight’s tour algorithm, next was to build the 36 bytes permutation which is used to permute the input that should be product[i] = input[path[i]]. Last, program will compare it with result table. Inverting the table permutation yields the valid input.

Analysts

Analysis and reporting completed by IDA, x64dbg & Cyberchef.

Static Analyst

Initial input

First time, i tried to run binary file, it made me to get type in the input and got the “Try again: (((” string. Of course, it was a wrong answer. However, with that little information, i was able to find out where that string located.

There was a call to the IsDebuggerPresent function, but it was easy to bypass.The crucial component was the DFS_chess function which I had previously renamed—accepting two parameters, both initialized to zero.

Next, I found that v4 and v5 are the coordinates the piece will move to on the 6×6 grid. In addition, dx_chess and dy_chess are arrays of the eight move offsets. From these offsets, you can tell the piece is a knight.

Once sum_foot equals N6*N6 (all 36 cells visited), the code flattens check_board built during recursion into path.

It builds a 36-byte output by permuting the input (GETINP) with path and stores the result in dword_40501C

Pseodu code makes sense :

for(int i =0; i< 36; i++){
    index = path[i]
    product[i] = input[index]
}

Finally, It will take the modified input to compare the table dword_405160 if you dump that data stored in dword_405160. You will receive that string

Of course, I had looked over it in advance, I paid attention on some uppercase letter like ‘U’,‘T’,‘E’,‘C’,‘T’,‘F’, it was resemble a format flag.

Dynamic Analyst (x32dbg)

(You can use IDA to debug)

All right, I saw there were two breakpoints i had set before and two registers ESI & EDI were both zero.

It meant two variable v4 & v5 that I had mentioned later. At that time, the function DFS will take two parameters ESI & EDI to start to call recursion.

As i mentioned on static analyst, path arrays would be containing the ordinal number of steps that Knight was walking during recursion, so I will set breakpoint at the end of the loop to dump all the path data and take them to inverse the string.

I counted the number and there were correctly 36 bytes coming from 00 to 36 (decimal). However, it was not a path to decode the flag, after a bit of trial and error, I found the excatly path.

Path :

0x00,0x07,0x04,0x13,0x02,0x09,
0x05,0x12,0x01,0x08,0x21,0x14,
0x0E,0x1B,0x06,0x03,0x0A,0x1F,
0x11,0x18,0x0F,0x20,0x15,0x22,
0x1C,0x0D,0x1A,0x17,0x1E,0x0B,
0x19,0x10,0x1D,0x0C,0x23,0x16,

In conclusion, let’s take all the path bytes and get them into the reverse code till you get the real flag.

Code python :

def rebuild_input_from_path(scrambled: str, path: list[int]) -> str:
    if len(scrambled) != 36 or len(path) != 36:
        raise ValueError("scrambled and path must be 36 bytes")
    if len(set(path)) != 36 or any(not (0 <= x < 36) for x in path):
        raise ValueError("path must contain from 0 to 35")

    # produced[j] = GETINP[path[j]]  =>  GETINP[path[j]] = scrambled[j]
    out = ['?'] * 36
    for j, idx in enumerate(path):
        out[idx] = scrambled[j]
    return "".join(out)


scrambled = "UtTlE3F4Th3kg0{C_<w_t3i3u1rgdk4_nn}n"  # from 0x405160

path_dumped = [
    0x00,0x07,0x04,0x13,0x02,0x09,
    0x05,0x12,0x01,0x08,0x21,0x14,
    0x0E,0x1B,0x06,0x03,0x0A,0x1F,
    0x11,0x18,0x0F,0x20,0x15,0x22,
    0x1C,0x0D,0x1A,0x17,0x1E,0x0B,
    0x19,0x10,0x1D,0x0C,0x23,0x16,
]

result = rebuild_input_from_path(scrambled, path)
print(result)

check = "".join(result[idx] for idx in path)
assert check == scrambled, "verify failed"

Flag : UTECTF{th3_kn1gt_w4lking_4r0und<333}

PE02 - Figure Out The Chess's Path