This maze problem is quite interesting. Later, I found that I could solve the collision CRC more often, so I thought it was more interesting

This program has TLS and several anti's, so you should be a little careful

401660  CheckRemoteDebuggerPresent

4015E0  NtQueryInformationProcess

401710 getthreadcontext check the sum of DRX

401690  setjmp3/SetUnhandledExceptionFilter

Input processing:

Encrypted maze initial data, four levels, each level map size is 6X5:

Several key functions:

Sub DE0 is a function that will be called in many places. After debugging and analysis, it is found that it is a pathfinding judgment function. The return value indicates that the two points are reachable. At the same time, we can see the labyrinth data decryption algorithm. The algorithm is relatively simple, XOR keys and XOR index numbers

First, decrypt the plaintext labyrinth data with the initial Labyrinth Key 3 for later Description:

From the above path finding judgment function, it can be analyzed that: the lower 4 digits in the map are 1, which means the point can be walked; if it is 0 and the next layer is 1X, which means the hole is padded high, it can also be walked

Sub 402460 goes to the specified position, if it encounters a prop, it will pick up automatically, 0x31 prop can change the key

Sub 4026a0 uses props at designated positions. From the function of using props, it can be analyzed that: mazes are stacked one by one from low to high three-dimensional level, 0X11 props can fall from the hole to the next level, and the next level is that the hole will continue to fall

Sub 402400 determines whether the previous close can be entered. If it can be reached, it will go to the coordinates of the lower right corner of the previous close (5,4)

Sub 402380 judge whether the next pass can be entered. If it can be reached, it will go to the upper left corner coordinate (0,0) of the next pass

.text:004023CE                 movzx   eax, byte ptr [ebx+198h]

. text: 004023d5 CMP [ebx + 10h], eax / / check the final key if (k = = w)

.text:004023D8                 jnz     short loc_4023F0

The meaning of this check is that the large number of the first 18 characters you enter requires a specific value

The main body of the game uses the key input to control the walking process, from the upper left corner of each layer to the lower right corner to enter the next level, until the fourth level is cleared

If you look at each level alone, the 6X5 map doesn't seem to be complicated, so you can walk and play it manually

Because the props of high-rise buildings will fall down, sometimes it is necessary to return to the front low-level gates to deal with the problem of heightening the proper positions

At the beginning, I also picked up the props of the first level. I can't walk down after the third level

After many attempts, it was found that picking up props was a burden. Ignoring props, it was easy to see the route, so I thought about whether I could walk through without picking 0x31 props,

Actually, the route steps are as follows:

01 12 13 06 3B 0B 0D 1E 06 17 3B 02 12 3B 01 10 1E 1E 10 06 3B 0D 0B 1E 06 10 17 0C 3B 0B 10 1E 10 1C 0C 17 3B 1A 12 1E 1C 11 3B 12 10 3B 19 17 15 17 3B 05 06 07 17 12 18 3B

Each step is converted into a plane coordinate, which means (V / 5, v% 5)

The steps less than 0x1E are in two groups. Take the 0X11 type box from one position and throw it into the 0x00 hole of the other position

0x1E is to return to the previous close and 0x3b is to enter the next close

Although the maze has been completed, there is a CRC judgment in the back:

Because the fake key is only 58 characters, 35 characters less than the maximum 93 characters can be used for collision. Intuitively, there is no reason for the collision. I think it's still interesting, so I decided to follow this path to the end

Unfortunately, the CRC problem was not solved until the end of the competition, because the collision efficiency with the pathfinding algorithm was too low, and all kinds of collision methods were not successful, and there was no distraction to solve the large number equations at that time

At the end of the competition, the author also posted a preset answer

When I was free at night, I continued to think about collision. This time, I avoided the efficiency problem of collision in the map

On my own route, I chose a time when I had 13 free footholds in the first pass. I wrote these 13 points directly into a one-dimensional array and threw away other points that could not be walked

First off state at that time:

In this way, we can do a large number exhausting in base 13. We don't need a path finding algorithm. It should be much faster

The theoretical basis is roughly estimated as follows: the 9th power of 13 is already greater than the 33rd power of 2, and more than twice of CRC space. Therefore, theoretically, the full arrangement of 9 steps makes each CRC value collide twice on average

In the last 20 minutes or so, the 9-Step collision was successful. After a look, the 9-Step space is about half full, and the 9-Step run is about 40 minutes

Although the first 18 characters can be entered as valid characters at will, in order to make it more beautiful, the key is constructed:

KCTF2019Q4LastLordGgEXiQVwXYixgiG7ww7XiVQwX7YoiQ7w7WoYiUgwWpTBJKNq9Aeig7iaYhYi4XlYgHi

Finally, I came up with another big number. It's a famous problem that has just been solved this year. Baidu can find the answer

（8866128975287528）^3+（–8778405442862239）^3+（–273611468807040）^3=33

Collision code:

The topic of the 2020 SDC (security developers Summit) was collected in Beijing, China in July!

Finally edited by ccfer at 20:46 on December 30, 2019 for the following reasons: