seed-cracking.md

Seed Cracking

Part 1: A little explanation about Java Random

• java.util.Random, An instance of this class is used to generate a stream of pseudorandom numbers. The class uses a 48-bit seed, which is modified using a linear congruential formula. (See Donald Knuth, The Art of Computer Programming, Volume 2, Section 3.2.1.)

• This class has 6 nifty functions:

  • nextBoolean()
  • nextDouble()
  • nextFloat()
  • nextGaussian()
  • nextInt()
  • nextLong()

• All of them are used in Minecraft source code but not all of them have the same use

• There is different reversal technics for each of them, its notably possible to reverse nextLong, nextInt (for power of 2)...

Part 2: Some generalities about Minecraft

• Minecraft is a procedurally generated world, which means that every content in the game is produce automatically by some algorithm.
• To help that generation, an unique seed is chosen/given at the beginning which will then be used for all other creation.
• This seed is 64 bits long, however not all the seed is used for all the content creation. We will call it a WorldSeed

Part 3: A bit of history about Seed Cracking

• This process is really old, since the source code was easily accessible, lot of people read it and noticed that since only 48 bits were used for some content creation, then it will be easily bruteforced with a gpu.
• To cite the most famous persons: L64, Taleden, Neil, KaptainWutax, Matthew are known to have tackled this problem

Part 4: How does it work

• We talked about the fact Minecraft use Java Random which has only a period of 2^48 since it can only use 48 bits number due to a mask applied after each operation on the internal state.

• Thus all content creation that deal with Java Random will inherently only deal with 48 bits of the 64 bits initial WorldSeed.

• A lot of elements are created in a Minecraft World, we can identify 4 differents phases:

  • Structure Generation
  • Biome Generation
  • Terrain Generation
  • Terrain Population

• To crack effectively the worldseed we need two things, a set of instruction that is deterministic and computationally light and enough informations

• Thus the logical choice is to go with the first phase, Structure Generation which only depends of the worldseed passed through Java Random and using the result of NextInt() called

• Since we need to recover the full 64 bits seed, we need to use biome generation which doesn't use Java Random but an internal Linear Congruential Generator (LCG)

Part 5: Bruteforce Optimization

• The Minecraft World Generation can leak information through several structure but one is notorious to leak 16 bits of the worldseed for free.
• This structure is the end spikes, those are generated with the following code:

Random random = new Random(WorldSeed);
long pillar_seed = random.nextLong() & 65535L;
 List<Integer> list = Lists.newArrayList(ContiguousSet.create(Range.closedOpen(Integer.valueOf(0), Integer.valueOf(10)), DiscreteDomain.integers()));
Collections.shuffle(list, new Random(pillar_seed));

• What is interesting about this is that the bitwise 65535 effectively reduce the number of possibilities for i to only 0 to 65535, thus giving only 65536 possible permutations of the range(0,10) (which is reality 10! or 3628800 so yes there is collisions)
• So we go from a 48bits search space to only a 32 bits one thanks to that simple reversal (bruteforcing 16bits is done in less than 0.1s on modern cpu)
• How do we get from a 32 bit seed to a correct 48bit seed accounting for the 16 bit found from the pillar is done via this function:

currentSeed = (seed << 16u & 0xFFFF00000000) | (pillar_seed << 16u) |
                  (seed &  0xFFFF);
    currentSeed = ((currentSeed - 0xb) * 0xdfe05bcb1365) & (unsigned long long) 0xffffffffffff;
    currentSeed = ((currentSeed - 0xb) * 0xdfe05bcb1365) & (unsigned long long) 0xffffffffffff;
    currentSeed ^= 0x5DEECE66D;

• In this function seed is a 32 bits seed used to bruteforce on that search space and the pillar seed is the one matching the pillar formation seems before, 0xdfe05bcb1365 is the modular inverse of 0x5DEECE66D (mod 2^48-1).
• So if we go from last to first we have the xor 0x5DEECE66D which is the random mask applied when we pass a seed to the Random object, then we go 2 times back in the internal state of the LCG which is due to the random.nextLong() call ((next(32) << 32) + next(32)) then we assemble the 32 bits seed and the pillar seed as follows: 16 upper of the 32 | pillar Seed | 16 lower of the 32.
• This is due to the fact that the random.nextLong call is bitwise with 65535 so we only get the bottom 16bits of that nextLong call which correspond to the second next(32) but next is also implemented as: (seed * 0x5deece66d + 0xb) & ((1 << 48) - 1)>> (16) so from the 48 bit internal state we only get 32 higher which we take the 16 lower so we take effectively the 16 middle which are our pillar seed
• So now that we know how to get from a 32bits seed to a 48 correct one with 16bits of Pillar then we can simply bruteforce through the 32 bits search space since that's easily accessible under a minute on modern CPU and under 15s on modern GPU. We use for that the structures and their Chunk Position which are determined from nextInt calls
• Now we just need to use the 48bits seed we got from the structure + pillars to get the 64 bits seed, so either it was random generated from a Random() object then we can use that algorithm:

public class SimpleReversal {

	private static final LCG INVERSE_LCG = Rand.JAVA_LCG.combine(-1);

	public static boolean isRandomSeed(long worldSeed) {
		long potentialSeed = fromNextLong(worldSeed);
		return new Rand(potentialSeed, false).nextLong() == worldSeed;
	}

	public static long fromNextInts(int nextInt1, int nextInt2) {
		long a = (24667315 * (long)nextInt1 + 18218081 * (long)nextInt2 + 67552711) >> 32;
		long b = (-4824621 * (long)nextInt1 + 7847617 * (long)nextInt2 + 7847617) >> 32;
		return INVERSE_LCG.nextSeed(7847617 * a - 18218081 * b);
	}

	public static long fromNextLong(long nextLong) {
		return fromNextInts((int)(nextLong >>> 32), (int)(nextLong & MagicMath.MASK_32));
	}

}

https://github.com/KaptainWutax/SeedUtils/blob/master/src/main/java/kaptainwutax/seedutils/magic/SimpleReversal.java#L13 https://twitter.com/Geosquare_/status/1169623192153010176

• Else we need to bruteforce accross 16 higher bits by using some data from biomes

Part 6: Current Development

• Today we can use Lattices, since technically all of the internal state of the LCG are linked and the scramblers (or the 6 functions i previously showed) are just fancy one way functions.
• The point is to gather enough bits of data to fully reconstruct from the scramblers output the current internal state then go back enough times till we hit a known point in Minecraft Code so we can reverse it to an usable Seed.
• One of the fancy ones are dungeons, those can yield between 36 and 55 bits of data with only one floor (size is between 7x7 and 9x9), and all the choice are made through a nextInt(4) which is easily reversable since a power of 2.
• So we can currently recover the full 48bits lower bits from one dungeon floor without the 5 needed structures (or decorator) like before.
• Technically everything in Minecraft can be reversed but the only issue is to know from where it has been called, if the number of random call before such action is unknown then it's harder to guess the correct number of step we need to go back for the internal state.
• Today research is focused on reversing Scrambling functions that are not yet reversed (nextInt(p) for instance) and good upper and lower bounds for different reversal technics based on different content creation.

Part 7: Side Notes

• In alpha/Beta the biome only use Java Random thus only 48 lower bits of the world were truly used.
• In 1.15 for the first time the seed was given to the client, except it was hashed with Sha256 and then used to applied the last layer of biome generation (called VoronoiZoom)
• In 1.13, structures got all their own salts which was not the case for Temples before.
• In 1.16, the nether only use Java Random to generate the world so there is 65535 same nether for a seed

Sources

https://twitter.com/Geosquare_/status/1169623192153010176 https://github.com/KaptainWutax/SeedCracke https://github.com/hube12/MinecraftSeedCrackingC https://pastebin.com/ftjY6ZzZ https://github.com/MostAwesomeDude/java-random/blob/master/javarandom.py https://stackoverflow.com/questions/54712600/what-is-the-true-maximum-and-minimum-value-of-random-nextgaussian/54739116#54739116