project seed crack

[vh]

the task:
going from minecraft world to generated seed

the purpose:
1. because it's fun
2. cracking blacraft's seed in a legit manner inb4 bla says doing math is illegal
3. so i can find slime chunks

the feasibility:
1. a few people have allegedly been successful.
2. search space is 2^48, ~300 trillion, which is pretty feasible

preliminary info i've collected

1. in this thread one user provides code for engineering the seed from slime chunks. code is untested, no signs that the author succeeded
http://www.minecraftforum.net/forums/minecraft-java-edition/survival-mode/288285-would-it-be-possible-to-reverse-engineer-a-seed

2. this guy says its been done but never gave details on how
http://www.minecraftforum.net/forums/support/server-support/server-administration/2106483-world-seeds-can-be-reverse-engineered

3. this thread has a bunch of people who do'nt know what they're talking about
https://gaming.stackexchange.com/questions/95387/find-a-minecraft-smp-server-seed-based-on-known-locations

4. this playlist may come in handy when i need to read the mc source code and work out the math
https://www.youtube.com/playlist?list=PL255772B4187BF4B8

5. according to the guy from number 2, who was super concerned about this, there's been patches to spigot to make it harder to reverse engineer the seed based on structure data.
http://www.minecraftforum.net/forums/support/server-support/server-administration/2133175-server-ops-anyone-can-discover-your-world-seeds

6. plugin which may or may not have been written after the patch and may contain details
https://www.spigotmc.org/resources/is-slime-chunk.17278/

next steps
1. collecting more info on the task and how people have accomplished it
2. reading some source code

contributions welcome -- currently that would take the form of doing preliminary research on the subject and posting it here if it's something i haven't already covered. the most important thing is to know what other people have done, since it can save a huge amount of effort.

[Yqt1001]

gl with the decompiled source code. it's an entirely new skill that basically all programmers don't have, being able to follow through and understand code when all variables and method names are nonsense (and not an insignificant amount, we're talking easily 50k lines of code to deal with)

I recommend decompiling spigot jars as those tend to have some helpfully named methods and aren't completely nonsense. following through how the server runs is also easier to understand as it starts off pretty obvious ("MinecraftServer.class" which has a mega init method) from there you should be able to find the chunk loading fairly easily. From there you'll have to find where it handles chunks that don't exist and their generation, I've never done this but presumably I've been close since I've had to do custom chunk loading/saving before.

[vh]

i had to read semi-obfuscated assembly once too many times, so i'm not too scared.
anyway i thought most of the variable names are deobfuscated as well. i mean there is some mapping from the nonsense variable names to what they actually refer to, although i don't know where to find that mapping just yet

[vh]

some notes

world class is in net.mineraft.world

interesting parts of the world class
1. the WorldProvider provider, which provides worlds i guess
2. The IchunkProvider chunkProvider, which provides chunks i guess
3. the WorldInfo worldInfo, which contains worldinfo i guess
4. villageCollectionObj
5. the constructor method (duh)
6. the getBiomeProvider method. it's unclear how biome generation and world/chunk gen is tied together
7. getSeed (probably will be useful later...)

some notes i found on worldgen:
http://www.minecraftforge.net/forum/topic/40443-1102-world-generation/

----

so it looks like the world generator contains both the chunk generator and the biome provider
also, the chunk generator is responsible for the structures

i found an implementation of the chunk generator abstract class in ChunkGeneratorOverworld.java

---

searching in another part of the code (EntitySlime.java) revealed this nugget in the getCanSpawnHere function

Code: [Select]

            if (this.world.getDifficulty() != EnumDifficulty.PEACEFUL)
            {
                Biome biome = this.world.getBiome(blockpos);

                if (biome == Biomes.SWAMPLAND && this.posY > 50.0D && this.posY < 70.0D && this.rand.nextFloat() < 0.5F && this.rand.nextFloat() < this.world.getCurrentMoonPhaseFactor() && this.world.getLightFromNeighbors(new BlockPos(this)) <= this.rand.nextInt(8))
                {
                    return super.getCanSpawnHere();
                }

                if (this.rand.nextInt(10) == 0 && chunk.getRandomWithSeed(987234911L).nextInt(10) == 0 && this.posY < 40.0D)
                {
                    return super.getCanSpawnHere();
                }
            }

            return false;
for reference, here's getRandomWithSeed:

Code: [Select]

    public Random getRandomWithSeed(long seed)
    {
        return new Random(this.worldObj.getSeed() + (long)(this.xPosition * this.xPosition * 4987142) + (long)(this.xPosition * 5947611) + (long)(this.zPosition * this.zPosition) * 4392871L + (long)(this.zPosition * 389711) ^ seed);
    }
for reference, the nextInt function is equivalent to mod

so basically, this very light reading of the source-code is already sufficient for me to locate the seed, if i knew the locations of a few slime chunks (say 20 or so)

[vh]

another nice overview of mc worldgen

https://docs.spongepowered.org/stable/en/plugin/wgen/index.html

[vh]

i finished my prototype code
it can check compatibility between a seed and an ocean monument location at a rate of 30K/second
in the worst case, it should take around 6 ocean monuments to locate a seed (let's make it 10 to be safe...)
also, there are about 300 trillion possible seeds. so we need to run 3*10^15 checks, which is 10^11 seconds, which is just over 3000 years according to wolfram alpha

so.... now we need to do some optimizations.

edit:
so several hours later, i rewrote everything in c++. speed is up to 100 million checks per second, which means running 3 * 10^15 checks takes just 1 year. a speedup to 3000 just by rewriting in another language. but of course, we need to do better...

[vh]

so overnight i rewrote the code in CUDA, and now it's churning through 10 billion checks per second. this is another 100-fold speedup from my cpp code, and about one million times faster than my python code

here's sample console output

Code: [Select]

seed 0, launch 0, time 0 ms
seed 274877906944, launch 1024, time 29262 ms
seed 549755813888, launch 2048, time 29466 ms
seed 824633720832, launch 3072, time 29656 ms
seed 1099511627776, launch 4096, time 29665 ms
seed 1374389534720, launch 5120, time 29823 ms
compatible seed 1551918019795 found

also i overestimated the number of checks which have to be done. it should only be 3*10^14.

at this rate, it would take just over 8 hours to crack the seed.
but can we do better go faster?

edit: uh yeah there's no obvious optimizations due to how data independent and simple the code is, so i guess 8 hours is the best....unless i get my hands on a titan x and run it there

[vh]

now i just need to retrieve the locations of 6 or so blacraft monuments, and we'll run the cdoe

edit: mission accomplished, blacraft seed cracked

[atomic7732]

hype

[vh]

so i went back to benchmark my code for fun. there are 2^48 ~= 280 trillion structure-unique seeds. on a titan xp, my code crunches through 21.8 billion candidate seeds per second, so total run time is 12800 seconds or 3 hours and 35 minutes.

but can we come up with this figure without actually running the code?
the titan xp has 3840 cores operating in parallel, clocked at 1.5 billion cycles per second. the code is super light on memory and is nearly exclusively compute bound. for each seed, i estimate roughly 100 integer / long operations need to be executed*. each operation takes on average 4 cycles according to the CUDA documentation -- since GPU's are more specialized for floating point rather than integer, and certainly not long type operations.

* i arrived at 100 ops per seed by literally counting the number of *, +, -, /, %, &, etc. symbols in my code

so we need 280 trillion seeds * 4 cycles/op * 100 ops/seed = 112 quadrillion core-cycles. divide this by 1.5 billion cycles/sec and 3840 cores, and it comes out to about 19500 seconds. now say we did a bit of compiler optimization and stuff, and it seems very feasible that the time goes down to 12800 seconds.

i'm actually kind of amazed this sort of "cycle counting" analysis got so close to the actual answer