HKCERT CTF 2022 Postmortem (III): The Remaining Challenges

WriteUp 1个月前 admin
127 0 0
HKCERT CTF 2022 Postmortem (III): The Remaining Challenges

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.

nc HOST PORT
🔧 1 37 37 97
🥺 33
😡
nc HOST PORT
🔧 1 85 85 97
🥺 85
🔧 2 2 26 97
🥺 24
😡

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

from pwn import *
from z3 import *
from operator import add, mul
from functools import reduce
from rich.progress import track
import itertools

# TODO: change this to the remote service
r = process('./chall')

for _ in track(range(100)):
    r.recvuntil('🔧 '.encode())

    m, s, p, q = map(int, r.recvline().decode().split())

    _s = Solver()
    xs = [Int(f'x_{i}') for i in range(m)]

    subss = [Int(f'ss_{i}') for i in range(m)]
    subps = [Int(f'ps_{i}') for i in range(m)]

    # The base conditions
    for i in range(1, m):
        _s.add(xs[i-1] <= xs[i])
    for i in range(0, m):
        _s.add(Not(xs[i] <= 0))
    for i in range(0, m):
        _s.add(xs[i] < q)
    for i, j in itertools.product(range(0, m), repeat=2):
        _s.add(Implies(i != j, xs[i] != xs[j]))

    # The "s" and "p" requirements
    _s.add(subss[0] == xs[0])
    _s.add(subps[0] == xs[0])
    for i in range(m-1):
        _s.add(subss[i+1] == subss[i] + (i+2)*xs[i+1])
        _s.add(subps[i+1] == subps[i] * (i+2)*xs[i+1])
    _s.add(subss[m-1] % q == s)
    _s.add(subps[m-1] % q == p)

    assert _s.check() == sat
    md = _s.model()
    x0s = [md.evaluate(xs[i]) for i in range(m)]
    r.sendlineafter('🥺 '.encode(), ' '.join(map(str, x0s)).encode())

print(r.recvline().strip().decode())
🤯 Wait what, solve.py? Hear me out… This is not a mistake.

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,qfrom the server and we need to find (x1,x2,...,xm) satisfying the base conditions:

  1. x1≤x2≤...≤xm,
  2. 0<xi<q for i=1,2,...,m, and
  3. For any i≠j, xi≠xj.

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

  1. x1+2x2+...+mxm≡s (mod q), and
  2. x1⋅2x2⋅...⋅mxm ≡p (mod q).

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

0<x1<x2<...<xm<q.

We can also simplify the product requirement:

x1⋅x2⋅...⋅xm≡p′(mod q),

where p′≡p⋅(1⋅2⋅...⋅m)−1 mod q.

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:

{x1+2x2+...+mxm≡s(mod q)x1⋅x2⋅...⋅xm≡p′(mod q)

🎯 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 x0=s.

This is easy. We can just assume that x1=1,x2=2,...,xm−2=m−2. What is remaining in the equations are:

{1+2⋅2+...+(m−2)⋅(m−2)+(m−1)xm−1+mxm≡s(mod q)1⋅2⋅...⋅(m−2)⋅xm−1⋅xm≡p′(mod q),

which is equivalent to

{(m−1)xm−1+mxm≡s′(mod q)xm−1⋅xm≡p′′(mod q).

Here s′=s−[1+22+...+(m−2)2] (mod q) and p′′=p′⋅[1⋅2⋅...⋅(m−2)]−1 (mod q).

Now we have a different objective: Find m−2<xm−1<xm<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)⋅xm−1≡s−m⋅xm(mod q).

Substituting the above to the product condition, we have

(s−m⋅xm)⋅xm≡(m−1)⋅p′′(mod q)⟹m⋅xm2−s⋅xm+(m−1)⋅p′′≡0(mod q),

which is a quadratic congruence in xm. To solve the equation, we will first reduce it into the form u2≡b (mod q).

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

m⋅xm2−s⋅xm+(m−1)⋅p′′≡0(mod q)⟹xm2−(s⋅m−1)⋅xm+(m−1)⋅m−1⋅p′′≡0(mod q)⟹xm2−2⋅[s⋅(2m)−1]⋅xm+(m−1)⋅m−1⋅p′′≡0(mod q)⟹xm2−2⋅[s⋅(2m)−1]⋅xm+[s⋅(2m)−1]2≡[s⋅(2m)−1]2−(m−1)⋅m−1⋅p′′(mod q)⟹[xm−s⋅(2m)−1]2≡[s⋅(2m)−1]2−(m−1)⋅m−1⋅p′′(mod q)

With u=xm−s⋅(2m)−1 and b=[s⋅(2m)−1]2−(m−1)⋅m−1⋅p′′, we have the equation u2≡b (mod q). To find the values of u, we can apply the Tonelli-Shanks algorithm. After that, we can compute xm from u+s⋅(2m)−1 and obtain xm−1 easily.

It is not uncommon that either no solutions exist, or m−2<xm−1<xm<q does not hold. In these cases, we can use another set of values for (x1,x2,...,xm−3,xm−2) such that xm−2 is small enough. After that, we can find xm−1 and xm with the above approach and stop when we have xm−2<xm−1<xm<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.

HKCERT CTF 2022 Postmortem (III): The Remaining Challenges

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.

HKCERT CTF 2022 Postmortem (III): The Remaining Challenges
🤩 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 livestreamdated 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º).

HKCERT CTF 2022 Postmortem (III): The Remaining Challenges
The four orientations of a grass block.

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

HKCERT CTF 2022 Postmortem (III): The Remaining Challenges
The screenshot with some grass blocks labelled with rotations.

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/422) 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:

From above, we know (x0+0, y0+0, z0+0) is pointing rightwards and
                    (x0+0, y0+0, z0+1) is pointing leftwards and ... and
                    (x0+1, y0-2, z0+9) is pointing rightwards
for some (x0, y0, z0).

For each -20000 <= x <= 20000, 0 <= y <= 256, -20000 <= z <= 20000:
  If (x+0, y+0, z+0) is pointing rightwards and
     (x+0, y+0, z+1) is pointing leftwards and ... and
     (x+1, y-2, z+9) is pointing rightwards, then:
    (x, y, z) are the coordinates we want!

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:

// An Java implementation of the `getRotation`
public static long getRotation(int x, int y, int z) {
    // Math#getSeed
    long l = (long)(x * 3129871) ^ (long)z * 116129781L ^ (long)y;
    l = l * l * 42317861L + l * 11L;
    long seed = l >> 16;

    // ModelBlockRenderer#tesselateWithAO
    Random random = new Random(seed);

    // WeightedBakedModel#getQuads
    return Math.abs(random.nextLong()) % 4;
}

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, s0, being

s0:=(seed⊕5DEECE66D16) mod 248.

The subsequent states s1,s2,... are all 48 bits and deduced by the current state:

si+1:=(5DEECE66D16⋅si+B16) mod 248.

If the current state is si, then the output of nextInt() would be yi:=⌊si+1/216⌋. Simply put, it is the top 32 bits of the next state. Also, nextLong() is defined by the below code snippet:

public long nextLong() {
    return ((long)(next(32)) << 32) + next(32);
}

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:

func getRotation(x, y, z int) int32 {
	/*
		long l = (long)(x * 3129871) ^ (long)z * 116129781L ^ (long)y;
		l = l * l * 42317861L + l * 11L;
		long seed = l >> 16;
	*/
	x2 := int(int32(x * 3129871))
	z2 := z * 116129781

	l := x2 ^ y ^ z2
	l = l * (l*42317861 + 11) // l = l*l*42317861 + l*11

	seed := l >> 16

	/*
		Random random = new Random(seed);
	*/
	seed ^= 0x5DEECE66D

	/*
		return Math.abs(random.nextLong()) % 4;
	*/
	v := int32((seed*0xBB20B4600A69 + 0x40942DE6BA) >> 16)
	if v < 0 {
		v = -v
	}
	return v & 3
}

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<z mod 6144<4180+64. This reduced the search space by 98.0%.

HKCERT CTF 2022 Postmortem (III): The Remaining Challenges
OSINT using clouds? That's better than Rainbolt!
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%.

HKCERT CTF 2022 Postmortem (III): The Remaining Challenges
OSINT using clouds? That's better than Rainbolt!

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

 

版权声明:admin 发表于 2022年12月27日 下午8:42。
转载请注明:HKCERT CTF 2022 Postmortem (III): The Remaining Challenges | CTF导航

相关文章

暂无评论

暂无评论...