SMP Seed Compromise via Slime Spawning

The random number generator used to determine where slimes can spawn for Y < 40 is not cryptographically secure, leading to the ability to determine an SMP seed from sufficient observations of slimes spawning in known chunks.

The world's secret seed is added to a calculated value for any given chunk (a constant function of chunk X and Z), xored with another constant, and this is run through one update of the Java Random() generator. If the returned result is a multiple of 10, the chunk spawns slimes. Each time we observe slimes spawning in a chunk, this forms an observation on the seed, reducing the number of seeds by a theoretical 10 times. In practice, getting independent observations is difficult because the random generator itself produces patterns.

The Java Random() generator, even after combining with the chunk value, only uses the lower 48 bits of the seed, allowing this to be practically attacked independently of the top 16. In addition, due to the generator being composed entirely of addition, multiplication and xor, whether the returned value is odd (cannot be a multiple of 10) or even (can be) for any given chunk is entirely determined by the lower 18 bits of the seed.

I have a practical implementation of this, though have not acquired enough slime observations on a real SMP server to reduce the possibilities to a single seed. The slime patterns rapidly become very similar for a whole list of seeds, so getting observations to tell them apart becomes harder. I can, however, produce a list of 8,300 possible values of the lower 48 bits for a large, real SMP server in about 5 seconds of processing.

I would encourage using a known, cryptographically secure random number generator whenever the world seed is an input. If cryptographically secure generators are too slow, single-purpose sub-seeds could be produced with a cryptographic hash function (e.g. SHA1, SHA3, etc). This would ensure that one insecure generator compromises only its own area, not the actual world seed.

P.S. The random number generators for chunk generation are of the same type (Linear Congruential Generators). While they use the full 64 bits, and are used in much less predictable ways, they are also theoretically vulnerable to finding similar patterns.