In the last part, I will include the two non-crypto challenges I wrote for HKCERT CTF 2022: *Numbers go brrr* and *Minecraft geoguessr*.

## 觀塘海濱音樂噴泉 / Numbers go brrr (Reverse)

### Challenge Summary

This program is generating 100 sets of random numbers and they are asking me to send something back, in exchange for a flag. Can you figure out how to get them through?

There is a `nc`

service, and we will be given some numbers upon connecting. We are asked to send something each time the 🥺 emoji appeared. From the description, we will be given the flag after sending correct responses 100 times.

On top of that, there is an attachment called `solve.py`

:

**🤯 Wait what,**Hear me out… This is not a mistake.

`solve.py`

?### Solution

**Presentation?**Some of you may prefer to read slides rather than words. If that’s the case, please refer to the slides I used for

*CUHK Open Innovation Lab’s sharing*dated November 28, 2022.

#### Part I: An unintended solution

To solve the challenge, we can just run `solve.py`

and it is done. Just kidding, it is impossible to solve the challenge in this way. Let's read the solve script and see what is going on.

#### Part II: Understanding the solve script

There are 100 rounds in total. In each round, we will receive four numbers $m,s,p,q$from the server and we need to find $(x_{1},x_{2},...,x_{m})$ satisfying the base conditions:

- $x_{1}≤x_{2}≤...≤x_{m}$,
- $0<x_{i}<q$ for $i=1,2,...,m$, and
- For any $ij$, $x_{i}x_{j}$.

In addition, the $m$-tuple needs to satisfy the "s" and "p" requirements (short for *sum* and *product*, respectively):

- $x_{1}+2x_{2}+...+mx_{m}≡s(modq)$, and
- $x_{1}⋅2x_{2}⋅...⋅mx_{m}≡p(modq)$.

That is it! We can deduce the actual problem statement from the solution script, and we can simplify the base condition:

$0<x_{1}<x_{2}<...<x_{m}<q.$

We can also simplify the product requirement:

$x_{1}⋅x_{2}⋅...⋅x_{m}≡p_{′}(modq),$

where $p_{′}≡p⋅(1⋅2⋅...⋅m_{−1}modq$.

#### Part III: Reducing an undetermined system

If we consider only the *sum* and *product* requirements, there are $m$ unknowns and two equations. If $m>2$, then the system is underdetermined:

${x+x++mxx⋅x⋅⋅x ≡s(modq)≡p(modq) $

**Objective.**In this section, we will reduce the challenge from $m>2$ to $m=2$, and its solution will be discussed in the next part. For $m=1$, it is obvious that the system is solvable if and only if $s=p$, with the solution being $x_{0}=s$.

This is easy. We can just assume that $x_{1}=1,x_{2}=2,...,x_{m−}=m−2$. What is remaining in the equations are:

${+⋅++(m−)⋅(m−)+(m−)x+mx⋅⋅⋅(m−)⋅x⋅x ≡s(modq)≡p(modq) ,$

which is equivalent to

${(m−)x+mxx⋅x ≡s(modq)≡p(modq) .$

Here $s_{′}=s−[1+_{2}+...+(m−2_{2}](modq)$ and $p_{′′}=p_{′}⋅[1⋅2⋅...⋅(m−2)_{−1}(modq)$.

Now we have a different objective: Find $m−2<x_{m−}<x_{m}<q$ such that the above system holds. Although the range of values are a little bit stricter, it is still easy to find a solution set.

#### Part IV: Solving a system of two equations, modulo prime $q$

From the two equations, we can just rewrite the sum condition:

$(m−1)⋅x_{m−}≡s−m⋅x_{m}(modq).$

Substituting the above to the product condition, we have

$ (s−m⋅x)⋅x≡(m−)⋅p(modq)⟹m⋅x−s⋅x+(m−)⋅p≡(modq), $

which is a quadratic congruence in $x_{m}$. To solve the equation, we will first reduce it into the form $u_{2}≡b(modq)$.

This is simple. We are essentially completing the square in modulo $q$:

$ m⋅x−s⋅x+(m−)⋅p≡(modq)⟹x−(s⋅m)⋅x+(m−)⋅m⋅p≡(modq)⟹x−⋅[s⋅(m)−1]⋅x+(m−)⋅m⋅p≡(modq)⟹x−⋅[s⋅(m)−1]⋅x+[s⋅(m)−1]2≡[s⋅(m)−1]2−(m−)⋅m⋅p(modq)⟹[x−s⋅(m)−1]2≡[s⋅(m)−1]2−(m−)⋅m⋅p(modq) $

With $u=x_{m}−s⋅(2m_{−1}$ and $b=[s⋅(2m_{−1}_{2}−(m−1)⋅m_{−1}⋅p_{′′}$, we have the equation $u_{2}≡b(modq)$. To find the values of $u$, we can apply the Tonelli-Shanks algorithm. After that, we can compute $x_{m}$ from $u+s⋅(2m_{−1}$ and obtain $x_{m−}$ easily.

It is not uncommon that either no solutions exist, or $m−2<x_{m−}<x_{m}<q$ does not hold. In these cases, we can use another set of values for $(x_{1},x_{2},...,x_{m−},x_{m−})$ such that $x_{m−}$ is small enough. After that, we can find $x_{m−}$ and $x_{m}$ with the above approach and stop when we have $x_{m−}<x_{m−}<x_{m}<q$.

With that implemented, we can finally pass the 100 rounds. We will eventually get the flag: `hkcert22{z3_i5_4n_sw1s5_4rmy_kn1f3_bu7_1t_i5_n0t_alw4y5_f4s7}`

.

## CGA 香港電競館 / Minecraft Geoguessr (Misc)

### Challenge Summary

Do you know Rainbolt? If you send him a photo, he could immediately tell you where it was taken in.

Can you do the same in the Minecraft world?

Note: If you are desperate, you can watch Rainbolt's most insane geoguessr moments, or LiveOverflow's video series on Minecraft Hacking.

By the way, the map is generated with Minecraft 1.17.1. With that said, you may be unable to look for the better caves.

We are given a web service that receives 5-tuples $(x,y,z,θ,φ)$ from players, where $x,y,z$ are the coordinates, and $θ$ and $φ$ are respectively the yaw and pitch. We will receive a screenshot taken in the specified location. Also, $−20000≤x,z≤20000$, $0≤y≤256$, $−180≤θ≤180$, $−90≤φ≤90$.

On the other hand, we are also given the below screenshot, where only the prefix of the flag `hkcert22{`

is shown. The objective is to recover the flag.

**🤩 Where does the inspiration come from?**This challenge is inspired by “They Cracked My Server!" by

*@LiveOverflow*in the

*Minecraft:HACKED*series.

### Solution

**Presentation?**Some of you may prefer to read slides rather than words. If that’s the case, please refer to the slides I used for

*HKCERT’s livestream*dated November 19, 2022.

#### Part I: Doing some OSINTs with the screenshot

The most attractive thing about the screenshot is the prefix of the flag. But what else can we retrieve from it?

Let's talk about Minecraft history. @SimplySarc uploaded a video in 2012 that showed that the rotation of lily pads is only dependent on their position. Also, snapshot 14w27b (for version 1.8) was released eight years ago. Below is an excerpt of the patch notes:

The block state files now support an array of models allowing for random models. As a result of this, grass blocks, dirt, sand, red sand, stone, netherrack, bedrock, and TNT all have their top texture randomly rotated.

When they say "random", it is dependent on the position like the lily pads. With that said, we can collect information from the grass blocks' rotation to find its coordinates. Surprising, right?

A legendary GeoGuessr player, @georainbolt, once said *why touch grass when you can study grass*. We can do the same in the Minecraft world. Now, look at a grass block. There are four rotations (rotated 0º, 90º, 180º and 270º).

Well, I know this is probably the most difficult part -- labelling. Let's identify the orientations of some grass blocks in the screenshot:

From above, I collected the rotations of 22 grass blocks.

(0, 0, 0) ➡️ |
(0, 0, 1) ⬅️ |
(-1, 0, 1) ⬆️ |
(1, 0, 2) ⬅️ |
(0, 0, 2) ⬅️ |
(-1, 0, 2) ⬆️ |

(0, 0, 3) ⬇️ |
(-1, 0, 3) ⬆️ |
(0, 0, 4) ⬆️ |
(-1, 0, 4) ⬅️ |
(-2, 0, 4) ➡️ |
(0, 0, 5) ⬇️ |

(-1, -1, 5) ⬅️ |
(1, -1, 6) ⬆️ |
(0, -1, 6) ⬇️ |
(-1, -1, 6) ⬇️ |
(2, -1, 7) ⬅️ |
(1, -1, 7) ➡️ |

(2, -1, 8) ➡️ |
(1, -2, 8) ⬇️ |
(0, -2, 8) ➡️ |
(1, -2, 9) ➡️ |

It is very unlikely (with the probability being $1/_{22}$) for a patch of 22 blocks that has the same rotations. Thus, there should be only one matching coordinate if we scan through every block in $−20000≤x,z≤20000$ and $0≤y≤256$. Below is the pseudo-code that we are going to implement:

A final problem is we don't know which direction the player is facing. Luckily, as there are only four possibilities, we can simply exhaust them all. By the way, some players can identify the player's orientation, so they can speed up their algorithm (at least) four times faster than our brute-forcing approach!

#### Part II: Reverse engineering Minecraft

**Is reverse engineering necessary?**No. We are not required to decompile and reverse engineer the source code of Minecraft to study the “rotation” of the blocks. There is a community of Minecraft working on reverse engineering (mostly on modding) and there are some resources discussing the rotation.

*hacker mann* uploaded a video in 2019 discussing a way to recover the coordinates from block rotation. The below code is a simplified, yet accurate way to compute the texture rotation of a block. It is a combination of multiple functions:

Hereby `Random`

is an implementation from the JDK, which can be referenced from their source code. To summarize, the random is a *linear congruential generator* (LCG), with the initial state, $s_{0}$, being

$s_{0}:=(seed⊕5DEECE66D_{16})mod_{48}.$

The subsequent states $s_{1},s_{2},...$ are all 48 bits and deduced by the current state:

$s_{i+}:=(5DEECE66D_{16}⋅s_{i}+B_{16})mod_{48}.$

If the current state is $s_{i}$, then the output of `nextInt()`

would be $y_{i}:=⌊s_{i+}_{16}⌋$. Simply put, it is the top 32 bits of the next state. Also, `nextLong()`

is defined by the below code snippet:

#### Part III: Preparing a program for brute-forcing

**Is brute force the only way to go?**I am not sure. Please share with us if you have a solution without brute-forcing.

From the above implementation, we know that the seed is derived from the coordinates of the block. This is my translation in *Golang* which optimized the algorithm a bit:

Well, I didn't compare the running times of the implementations in Golang and Java, which may be similar. I use Golang simply because I rarely code in Java anyway.

After that, what is missing is just a routine that exhausts the whole search space, and includes the block rotation we found from the screenshot. We can decrease the running time with multithreading, too.

I implemented my solution using Golang. With 8 threads and search space being $−20000≤x,z≤20000$ and $64≤y<100$, it only takes 6 minutes to run.

The coordinates we found are $(16551,67,4170)$. We can now ask our intern to teleport nearby for the whole flag: `hkcert22{s33d_cr34kin9_1s_r3ver53_4nd_cryp70_com61ned}`

.

**Alternate tools.**19MisterX98/TextureRotations is a repository (in Java) that does the same thing. You can use the code to recover the coordinates.

#### Part IV: Reducing the search time

There are two notable ways to reduce the search time, provided by the contestants @HotDawggyy and *Gameboy612*. We can recover the coordinates in less than ten seconds with either of the two improvements implemented. This is remarkable!

##### Hey, look at the clouds!

@HotDawggyy looked at the cloud and found that the $z$-coordinate should be roughly 4180 when taken modulo 6144. Assuming that the absolute error is 64 blocks, i.e., $4180−64<zmod6144<4180+64$. This reduced the search space by 98.0%.

##### Look at the water, too!

On the other hand, *Gameboy612* reduced the search space by determining the sea level. If we assume that the pool of water is at sea level (i.e., $y=62$), we can just fix the $y$-coordinate to one single value. This reduces the search space by 97.2%.

Finally, it is impressive that *Gameboy612* is a secondary school student and their team got the first blood 🩸 of this challenge. Congratulations!