Every time a block is broken in Minecraft versions Beta 1.8 through 1.12.2, the precise coordinates of the dropped item can reveal another player's location.
"Randar" is an exploit for Minecraft which uses LLL lattice reduction to crack the internal state of an incorrectly reused java.util.Random in the Minecraft server, then works backwards from that to locate other players currently loaded into the world.
Click here to learn about Randar in the form of a YouTube video instead.
Watch the timelapse:
See more timelapses here (as files) or here (as YouTube).
The goal is to determine the in-game locations (i.e. coordinates) of the other players in the world, no matter how far away they are. We're playing on 2b2t, which is the oldest and most famous "anarchy" Minecraft server (which means no rules, i.e. players aren't banned for any reason). Doing stuff like this is kind of "the point" on this server. On this server, the only thing keeping your stuff safe is that the map is huge (3.6 quadrillion square tiles) and no one else knows where you are. So it's a huge deal (a game-breaking deal) to have a coordinate exploit. (speaking of, before Randar we also had another coord exploit on 2b2t, Nocom, from 2018 to 2021; see that writeup here, HackerNews thread, YT)
The mistake in Minecraft's code is present from versions Beta 1.8 (released 2011) through 1.12.2 (released 2017, but 2b2t stayed on this version until August 14, 2023). The mistake is that various instances of the random number generator, java.util.Random, are reused sloppily in various parts of the code (and they're insecure to begin with). Specifically, there's reuse of RNG between generating terrain and in game actions such as mining blocks.
The exploit summarized:
World.rand has its seed reset to a function of the chunk coordinates, in order to check where a nearby Woodland Mansion should be (and whether it's this chunk in particular).World.rand.nextFloat() calls to pick the X Y and Z coordinates between 0 and 1. The bot records the timestamp and the precise X Y Z values.World.rand that caused those three floats. Broadly speaking (more detail will come later), observing one output of the RNG could imply any one of about 16 million possible internal states of the RNG. However, we have sampled the output of the RNG not just once but three times in a row (the X, Y, and Z coordinates of the dropped item), and we know how the internal state is updated between each call (a simple multiply, add, then mod); therefore we can use lattice methods to essentially instantly narrow it down to the only possibility.java.util.Random can be stepped backwards just as easily as forwards, and by stepping backwards we can find it in just a few thousand steps (even on busy servers like 2b2t with many players and therefore heavy usage of RNG), which identifies the most recent time that the RNG's internal state was reset, and therefore the location of the most recent chunk that was loaded on the server.Even if you play on a server that has updated to a newer version of Minecraft, or has otherwise patched RNG manipulation, your coordinates are still at risk from Randar due to the ability to exploit RNG data retroactively. Some Minecraft players use mods like ReplayMod that log packets, and they might still have those log files sitting around. If anyone was using such a mod while you were at your base, they may have (unknowingly) recorded RNG data that could reveal your location, because breaking blocks is an extremely common action that's likely to have happened in such recordings, and every such block break reveals the server's RNG state and therefore the location of the most recently loaded chunk. This means Randar is a pretty big deal: due to this risk of exploiting retroactively, on every Minecraft server, every location that was active in versions Beta 1.8 through 1.12.2 should be considered compromised, even if the server has long since updated past 1.12.2 or patched RNG manipulation.
If you want to use the Randar exploit yourself, go here where rebane2001 has created a website where you can drag in your ReplayMod files from 1.12.2 and see the coordinates of other players. It runs client-side so your recordings will not leave your browser. Here's a video of what that website looks like in action, and you can run the example ReplayMod file from that video by downloading it here.
Randar was discovered by n0pf0x (pcm1k). This writeup was written by leijurv, with some additional commentary at the end written by n0pf0x. Exploiters were 0x22, Babbaj, TheLampGod, leijurv, Negative_Entropy and rebane2001. See TheLampGod's video here. See HermeticLock's 100% humorous 0% factual video here.
Table of contents: click here to learn about the exploitable code in more detail, here to learn about how lattice reduction was used, here to see how we protected our own stashes from Randar, here if you just want to see the complete exploit code, here if you run a server that's still on a version between Beta 1.8 and 1.12.2 and you want to patch Randar, or here for details on what n0pf0x did differently than us.
Diagram of the mistake (as PDF):
Diagram of the exploit (as PDF):
Diagram of a worked example of the exploit (as PDF):
Minecraft relies on random numbers throughout the game. Most of them we expect to be actually random, such as randomness used for mob spawning and weather, but some of them we expect to be predictable, for example we expect the same world seed at the same location to generate the same terrain. In 2011, when Notch first added structures to the game during Beta 1.8, he accidentally reused an RNG that's supposed to be unpredictable in order to place Villages in the world. Ever since then, until 1.13, this sloppy code has caused world generation to influence nearly all other supposedly random events in the game. It took until around May 2018, for Earthcomputer and friends to discover this mistake, realizing that chunk loads affect the game's RNG in an observable way, see this explanation. However, they did not realize, or just never revealed publicly, that you can also do this backwards, determining the most recent loaded chunk from observing the RNG. That discovery, Randar, was made by n0pf0x (aka pcm1k) on October 7, 2022. He posted a short, encrypted description of the exploit on Pastebin about two weeks after, to prove that he discovered it then. He used the exploit mostly on 9b9t, and only a relatively small amount on 2b2t and other servers. On 2b2t, n0p located and explored various locations, eventually coming to a Gringotts stash location. He was spotted by rebane2001, and initially silent about how he found the location. However, about a month later, he began a conversation with the SpawnMasons about it. n0p revealed he had used a powerful coordinate exploit and decided to share an explanation with us in April 2023, because the masons have past experience taking advantage of 2b2t exploits at larger scale, so it would be fun to see that happen again, and n0p was getting slightly bored with it anyway. We accepted and began recording item drop coordinates on several accounts that were already mining stone/cobblestone 24/7 for an unrelated project (so, there was no change in behavior). We reused the headless Minecraft system from nocom and added a Postgres database to record the measurements. As discussed later in this readme, we went through several iterations of software to crack the RNG measurements, eventually settling on an async Cuda batch job. As cracked measurements were added to the database, we also updated an analytics table with heatmap information that counted hits at each coordinate at intervals of all time, daily, and hourly. This allowed a simple Plotly Dash UI to select heatmap data from specific time ranges and granularities for display in a browser, and it let us remove all the Elytra stashhunting chunk load spam by only considering coordinates that were loaded in more than a few distinct hours. We added a simple shared annotation system to keep track of what we found at each hotspot on the map. Again reusing from Nocom, we have Baritone bots that automate the entire process of stealing item stashes and sorting the results, completely AFK. Many masons helped with this part, without knowing the exploit, using accounts such as munmap and 1248_test_user. All Gringotts stashes put together eventually grew to 1.3 billion items, of which about half is attributable to Nocom and half to Randar.
The full history is explained in the FitMC video.
Minecraft's map is procedurally generated and essentially deterministic based on the initial seed of the world. As players explore the map, new areas are generated on-demand as players get near. Since all the generation is meant to be repeatable (deterministic), it's perfectly reasonable for them to have used java.util.Random in a lot of places. They want it to be predictable. This is why java.util.Random is used, since it's a PRNG (not really a RNG). The P technically means "pseudo" but think of it as "predictable". Predictable RNG. It generates numbers that seem random, but they're actually repeatable given the same starting seed.
Minecraft has various structures that are generated in the world, such as villages, ocean monuments, strongholds, etc. These are part of the procedural generation, so they're also placed and generated deterministically.
There's only a dozen lines of Minecraft code needed to understand this, and I've simplified and commented it heavily:
// (chunkX,chunkZ) is being loaded, and this function checks if it should generate a Woodland Mansion
protected boolean canSpawnStructureAtCoords(int chunkX, int chunkZ) {
// divide by 80, rounding down, to determine which "Woodland region" (my made up term) we're considering
int woodlandRegionX = Math.floorDiv(chunkX, 80);
int woodlandRegionZ = Math.floorDiv(chunkZ, 80);
// seed the random number generator deterministically in a way that's unique to this Woodland region
Random random = this.world.setRandomSeed(woodlandRegionX, woodlandRegionZ, 10387319);
// pick which chunk within this region will get the Woodland Mansion
int woodlandChunkX = woodlandRegionX * 80 + (random.nextInt(60) + random.nextInt(60)) / 2;
int woodlandChunkZ = woodlandRegionZ * 80 + (random.nextInt(60) + random.nextInt(60)) / 2;
// but is it *this* chunk, that we're loading right now?
if (chunkX == woodlandChunkX && chunkZ == woodlandChunkZ) {
// and, is this chunk in a biome that allows Woodland Mansions? (e.g. roofed forest)
if (this.world.getBiomeProvider().areBiomesViable(chunkX * 16 + 8, chunkZ * 16 + 8, 32, ALLOWED_BIOMES)) {
return true;
}
}
return false;
}
// and here's what it calls in World.java:
public Random setRandomSeed(int seedX, int seedY, int seedZ) {
this.rand.setSeed(seedX * 341873128712L + seedY * 132897987541L + seedZ + this.getWorldInfo().getSeed());
return this.rand; // this.getWorldInfo().getSeed() is the overall seed of the entire map, which has been cracked long ago for 2b2t (it's -4172144997902289642)
}The above is commented and slightly modified for clarity, but it's functionally accurate to the real code.
So the idea is to decide where the Woodland Mansion should go in this Woodland region (which is 80 by 80 chunks), check if that place is right here, and if so, generate a Woodland Mansion starting right here.
This code might look a little silly, you might be thinking "it's absurd to do all these checks on every chunk, just pick where Woodland Mansions should go once per region and be done with it". The reason is that Minecraft chunks are generated independently of each other, and in unknown order, yet we still want to generate a deterministic world from a given seed. We don't know in what order the player is going to walk around the world, and it's nice to be able to generate any chunk on-demand in a stateless manner. It's a good game experience. Thus, weird-looking code like this.
Anyway, that code gets called on every chunk load, for every chunk in a large square around the one being loaded. It's a bit complicated to explain why so I'll mostly skip it (the basic idea is that these structures are (much) larger than one chunk in size, so we need to check for a structure origin in many nearby chunks in order to generate this current one correctly).
Note that this only affects the Overworld. The Nether is safe, as all of its structure generation has always used safe RNG. Loading chunks in The End is affected due to end cities, but only on their initial generation, not every subsequent time they're loaded, thus The End is relatively safe because each chunk at your base only affects the RNG once ever when you first load it. However, this is not totally foolproof, as players commonly generate new chunks each time while travelling to their base, and occasionally generate new chunks while already at their base.
The problem is that it modifies the seed of the global World.rand. This is just lazy coding. All they're doing is calling nextInt four times to pick the X and Z coordinate. They could have replaced Random random = this.world.setRandomSeed(... with Random random = new Random(the same stuff) (in other words, make a new Random here rather than messing with the existing one that's used by everything else???).
Crucially, the setRandomSeed is called in order to check where the Woodland Mansion should go. It happens no matter what, on every chunk load, everywhere. You don't have to be standing in/near the Woodland Mansion or anything like that.
Well, turns out World.rand is used in literally hundreds of places, and many of those places can be easily observed by playing the game normally. For example, when you mine a block:
/**
* Spawns the given ItemStack as an EntityItem into the World at the given position
*/
public static void spawnAsEntity(World world, BlockPos pos, ItemStack stack) {
double xWithinBlock = world.rand.nextFloat() * 0.5F + 0.25D;
double yWithinBlock = world.rand.nextFloat() * 0.5F + 0.25D;
double zWithinBlock = world.rand.nextFloat() * 0.5F + 0.25D;
EntityItem entityitem = new EntityItem(world, pos.getX() + xWithinBlock, pos.getY() + yWithinBlock, pos.getZ() + zWithinBlock, stack);
world.spawnEntity(entityitem);
}Again, slightly modified, but functionally accurate for the stuff we're talking about.
The idea here is that in Minecraft when you mine a block, it drops an item. The item is dropped at a random position within the block. For example, if the block was at (10, 20, 30), the item will appear somewhere between (10.25, 20.25, 30.25) and (10.75, 20.75, 30.75).
And the exact location of that item is chosen by calling world.rand.nextFloat() three times in a row, for the X, the Y, and the Z.
That's all the Minecraft code needed!
Now, I said that we can do something with these nextFloat calls. First, let's see if we can "work backward" to see what the nextFloat calls are. It's pretty lucky, but we actually can. Note in the above code: the random float is multiplied by 0.5, then added to 0.25. The idea is to move from a random number between 0 and 1 to a random number between 0.25 and 0.75. You might be worried, because if you were to divide an integer by two, you'd lose a bit of information since the result is rounded down. Thankfully, multiplying a float by 0.5 is totally reversible, since it just decrements the exponent while leaving the mantissa untouched. Then, the float is casted to a double, which has way more precision. 0.25 is added, then the block coordinate is added. Then, it's sent to the client over the network in full precision. The upshot: this whole process is reversible so we can get the exact three floats that World.rand.nextFloat() produced.
How does java.util.Random generate floats? Well actually it's quite simple. It generates an integer between 0 and 2^24, then divides it by 2^24 (resulting in a number between 0 and 1).
How does it get that random integer? Also pretty simple! It's a linear congruential generator (LCG). That means that the next seed is the previous seed times something, plus something else, modulo something else.
public float nextFloat() {
this.seed = (this.seed * multiplier + addend) % modulus; // update the seed
int randomInteger = (int) (this.seed >> 24); // take the top 24 bits of the seed
return randomInteger / ((float) (1 << 24)); // divide it by 2^24 to get a number between 0 and 1
}In this case, the multiplier is 25214903917, the addend is 11, and the modulus is 2^48.
With the float that came out of this, we can multiply it by 2^24 to get back the randomInteger, and therefore get the "top half" (the most significant 24 bits) of the 48 bit seed.
In short, from our measurement, we learn that the seed is between measuredRandomInteger * 2^24 and (measuredRandomInteger + 1) * 2^24.
And we can do this three times in a row, for the X, the Y, and the Z.
And we know that between the X and the Y, and between the Y and the Z, the seed was updated according to newSeed = (oldSeed * 25214903917 + 11) mod 2^48
I must mention that one valid option is a for-loop that tries all 2^24 possible lower bits. For the programmers reading this, I hope this makes clear what the problem is:
for (long seed = firstMeasurement << 24; seed < (firstMeasurement + 1) << 24; seed++) {
// all these seeds will match the first measurement
if (nextSeed(seed) >> 24 == secondMeasurement && nextSeed(nextSeed(seed)) >> 24 == thirdMeasurement) {
// if nextSeed(seed) matches secondMeasurement, and nextSeed(nextSeed(seed)) matches thirdMeasurement
// then we found a seed that matches all three measurements! yay!
return seed;
}
}This would work, and does work, but it's not that fast and not that fun. So we use lattices instead!
However, I feel like I have to go a bit out of order. The lattice reduction part does come in right here but it's really complicated and I bet it would have low reader retention and I don't want to lose you. So I'll just give you that for-loop solution (which DOES work), and continue to the next step of the exploit. The explanation of the lattice reduction method will come right after :)
What do we do with this seed once we have it?
First, note that we can step the LCG backwards. Obviously, adding eleven is reversible, but is multiplying by that big number reversible? Our multiplier 25214903917 is an odd number, meaning it isn't divisible by two, and therefore it doesn't share any factors with our modulus 2^48 (since 2^48 is literally just a bunch of twos). Since it's relatively prime to the modulus, we can invert it, which means to find another number x that satisfies x * 25214903917 - 1 is divisible by 2^48. Or in other words, 25214903917 * x mod 2^48 = 1. That number is 246154705703781. This helps invert the multiplication because if we have, for example, secret * 25214903917 and we want to figure out secret, we can just compute secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret.
Ok, so we can step the internal seed of java.util.Random both forwards and backwards. Forwards is newSeed = (oldSeed * 25214903917 + 11) mod 2^48 and backwards is oldSeed = ((newSeed - 11) * 246154705703781) mod 2^48. And this works because those numbers 25214903917 and 246154705703781, when multiplied together, come out to 1 when you take it mod 2^48.
Now, as we step backwards, we would like to check at each step whether this seed could mean that a Woodland Mansion check was recently performed somewhere in the world (the whole point of the exploit). How do we do that?
The Minecraft world ranges from -30 million to +30 million blocks. Each "Woodland region" (an area of the world where a single Woodland Mansion is placed at random, as per the code shown previously) is 80 by 80 chunks, which is 1280 by 1280 blocks. This is 23437.5 Woodland regions, but for all of our code we just rounded up to 23440 because it's a round number and even though your player can't travel beyond 30 million, you load chunks beyond it just by standing near it, and we just didn't want to have to worry about all that.
So, -23440 to +23440 on both X and Z axes. That's (23440*2+1)^2 (aka 2197828161) possible Woodland regions, each of which generates a unique "mansion seed" (defined as a seed that reveals that someone just loaded a chunk at a certain Woodland region). We need to be able to check if something is a mansion seed. Could we iterate over all 2.2 billion mansion seeds to check each one? Would be too slow. Could make a HashSet<Long> with 2.2 billion entries? Would take up too much RAM even using chronicle map like we did in nocom, and even in C++ using abseil-cpp it used like 50gb ram. And that's not to mention the other part: we actually want to learn where they are in the world (that's the whole point). So it's not good enough to learn this is a mansion seed, we also want to (efficiently) learn which Woodland region caused it.
Recall the function that goes from Woodland Region to mansion seed (note: I've now combined some constants since the code above for simplicity, this equation is now specialized to 2b2t's seed):
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
(the -4172144997891902323 number comes from the -4172144997902289642 + 10387319, which is the 2b2t world seed + the magic value used for seeding the Woodland region (as shown earlier). For any other world you would just put your own seed instead into this equation.)
Not much we can do with the x coordinate, since it's being multiplied by an even number. But what's that coefficient on the z coordinate? It looks like an odd number!!! Let's use the same trick as before to invert it again, and we get 211541297333629.
Let's imagine we have a given seed. What if we could just iterate through all possible X coordinates from -23440 to +23440, and for each one, compute what the Woodland region's Z coordinate WOULD be, IF it had this mansion seed. In other words, the above equation gives us seed if we know x and z, but can we make an equation that gives us z if we know seed and x? Answer: yes. We just rearrange the above equation, and use the fact that the coefficient of Z is invertible mod 2^48 since it's an odd number.
The equation is:
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
So this is a pretty good solution because instead of two nested loops (one for X and one for Z) that do a total of 2.2 billion iterations, we can have a single for-loop for X that just does 46,881 iterations. Here it is in Java:
private static WoodlandRegionCoord woodlandValid(long internalSeed) {
long seed = 25214903917 ^ internalSeed; // java.util.Random XORs in the multiplier while doing setSeed, so XOR that back out to go from a "this.seed" to what the input to setSeed() would be
for (int x = -23440; x <= 23440; x++) {
long z = ((seed + 4172144997891902323L - x * 341873128712L) * 211541297333629L) << 16 >> 16;
if (z >= -23440 && z <= 23440) {
return new WoodlandRegionCoord(x, z);
}
}
return null;
}(note: the weird << 16 >> 16 is doing mod 2^48, but we actually want to do it using signed types so that we still get the correct answer when z is between -23440 and 0, this is a way to sign-extend the 48-bit number to 64 bits, filling the upper 16 bits with the correct sign bit for two's complement)
So this does work and it's reasonably fast.... for a single seed. But remember that we're stepping back the RNG for potentially thousands of steps, and running this check at each step until we find a match. At the time, we were using a shitty DigitalOcean droplet on their lowest tier, and this was actually lagging everything out and couldn't keep up with real time (bots mining many blocks per second, each block taking thousands of rng steps to crack, and each rng step taking 23440*2+1 operations to check, multiply those together and you get well into the hundreds of millions of operations per second, so you see why that had trouble on a crappy VPS, especially when that VPS is also trying to run multiple headless instances of Minecraft).
Anyway so we switched to a lookup table approach and rewrote it in Cuda to run on my desktop as a batch job every few minutes. It can do literally millions per second because each of the thousands of cuda cores can work on their own seed in parallel. Here's the idea: the lookup table's key is the lower 32 bits of the mansion seed, and the value is the X coordinate of the Woodland region. This lookup table works with no collisions because each mansion seed has a unique lower 32 bits, somehow. I don't understand why that's true, it's fascinating. You'd think it wouldn't work. But I think the coefficients 341873128712 and 132897987541 may have been specially chosen to make this work? Like, if you have 2.2 billion marbles, and 4.3 billion buckets, and you independently put each marble in a random bucket, what are the odds that each marble gets its own bucket? Essentially zero. Nearing the end, each new marble has a more than 50% chance of hitting a bucket that's already filled. Yet, clearly, these are not independently random, so somehow it works. Unironically if you're reading this and understand how this works or why those two specific coefficients make this work, please let me know. Anyway, it works. The lookup table has 2^32 entries, and each entry is 2 bytes (since it's just a number between -23440 and +23440), so this needs about 9 gigabytes of VRAM on your GPU.
The woodland check function now looks like (again, this is the actual code but simplified, all helpers and constants inlined etc):
__global__ void computeSteps(const int16_t* mansionTable, const int64_t* seedsArr, Result* resultArr, size_t numData) {
auto tid = blockIdx.x * blockDim.x + threadIdx.x;
[[unlikely]] if (tid >= numData) {
return;
}
auto seed = seedsArr[tid];
int steps = 0;
while (true) {
auto externalSeed = seed ^ 25214903917;
const auto x = mansionTable[externalSeed & ((1LL << 32) - 1)];
const auto z = ((externalSeed + 4172144997891902323LL - (int64_t) x * 341873128712LL) * 211541297333629LL) << 16 >> 16;
if (z >= -23440 & z <= 23440) {
resultArr[tid] = {.startSeed = seedsArr[tid], .x = (int16_t) x, .z = (int16_t) z, .steps = steps};
return;
}
seed = ((seed - 0xBLL) * 0xdfe05bcb1365LL) & ((1LL << 48) - 1); // prevSeed(seed)
steps++;
}
}
// and that mansionTable was generated like this
// note: mansionTable must be calloc'd before this function because not every entry will be written to, and an x value outside -23440 to 23440 bounds could create a false positive later on while using the table
__global__ void writeToSeedTable(int16_t* mansionTable) {
auto tid = blockIdx.x * blockDim.x + threadIdx.x;
if (tid >= (23440 * 2 + 1) * (23440 * 2 + 1)) return;
auto x = tid / (23440 * 2 + 1) - 23440;
auto z = tid % (23440 * 2 + 1) - 23440;
auto seed = ((int64_t) x * 341873128712LL + (int64_t) z * 132897987541LL - 4172144997891902323LL) & ((1LL << 48) - 1);
mansionTable[seed & ((1LL << 32) - 1)] = (int16_t) x;
}This works great in giant batches and can crack on the order of ten million seeds per second on a 3090. Turns out to not be too big of a deal when some of the threads in a warp terminate early, and we couldn't really make it any faster than this. (the reason is that we fundamentally can't know beforehand which seeds will take more/less steps).
Well that's about it. Given the seed, that's how we get the Woodland region in the world where the most recent chunk load happened. In other words, we just learned that the most recent time that someone walked around on 2b2t and loaded a new area of the world, was somewhere within this 1280 by 1280 block Woodland region that we just identified. (that's precise enough that locating them takes just a few minutes of searching)
In practice, how many RNG steps were needed? On the low end, reliable measurements start at 4 RNG steps, everything below that is measurement error / random noise, which we know because the Woodland Mansion code immediately calls rand.nextInt four times before it's possible for us to measure it. On average, there are about 128,000 steps between each Woodland seed, but in practice, the vast majority of the time on 2b2t, we found a Woodland seed within a few dozen steps. This is due to the particulars of what happens in what order in a Minecraft tick. Our measurement technically happens at the very beginning of the tick, since that's where the packets for breaking blocks are processed. Generally, a chunk has been loaded in the very recent history during the previous tick. However, sometimes, an event can cause a bunch of RNG steps in between. We believe that this event is explosions, such as someone blowing up an end crystal by punching it, or possibly wither skulls. End crystal explosions would also occur during packet processing from the player punch packet, and the number of RNG steps also lines up at 1354 steps (1352 from calculating the block damage in a cuboid
And on the coordinates used as a worked example in this diagram, this is what the above code outputs:
jshell> crackItemDropCoordinate(0.730696, 0.294929355, 0.634865435)
Item drop appeared at 0.730696 0.294929355 0.634865435
RNG measurements are therefore 16129481 1507579 12913941
This indicates the java.util.Random internal seed must have been 270607788940196
Found a woodland match at woodland region 123 456 which would have set the seed to 261215197308064
Located someone between 157312,583552 and 158591,584831
jshell>
Note how it locates Woodland Region 123,456, and note how the final "located someone between" does include the real coordinate that we had originally inputted, which was x=157440 z=583680. Additionally, the RNG measurements match the hexadecimal in red: 0xf61dc9 equals 16129481, 0x1700fb equals 1507579, and 0xc50d15 equals 12913941. And for the seeds, 0xed92e70ba4a0 equals 261215197308064 and 0xf61dc9221ba4 equals 270607788940196.
You can probably find patches or config options for disabling RNG manipulation, something like that will work for patching Randar and it's probably the easiest way. If you can't find an easy way to disable RNG manipulation, here is the code that needs to be tweaked in the World class:
Vulnerable version:
public Random setRandomSeed(int seedX, int seedY, int seedZ) {
this.rand.setSeed(seedX * 341873128712L + seedY * 132897987541L + seedZ + this.getWorldInfo().getSeed());
return this.rand;
}Simply change this function to instead return a different Random each time, if you want perfect protection:
Patched version:
public Random setRandomSeed(int seedX, int seedY, int seedZ) {
return new Random(seedX * 341873128712L + seedY * 132897987541L + seedZ + this.getWorldInfo().getSeed());
}That might not have great performance, so if you like you can introduce a new field, separateRandOnlyForWorldGen, which isn't shared with anything else, e.g.:
private final Random separateRandOnlyForWorldGen = new Random(); // new field on the World class
public Random setRandomSeed(int seedX, int seedY, int seedZ) {
this.separateRandOnlyForWorldGen.setSeed(seedX * 341873128712L + seedY * 132897987541L + seedZ + this.getWorldInfo().getSeed());
return this.separateRandOnlyForWorldGen;
}If you use PaperMC for 1.12.2, here is a patch you can apply. Alternate link.
This will be an additional section where I go over some extra stuff that would make more sense to explain from my point-of-view, as other than the basic ideas, we mostly independently developed things.
First thing I would like to mention, is the system for locating the coordinates from a seed. The Mason's used a large lookup table and GPU processing, I instead relied on a cache for speed. Whenever a hit occurs, its coordinates, and all the coordinates within a radius are put into a HashMap. Seeds are processed in two passes. The first pass steps the RNG back, and checks if the seed is either present in the cache, or it was the same seed processed last time, which is considered differently. The second pass only happens if the first pass fails, is much slower, and uses the relatively expensive algorithm described previously. A pleasant side effect of this system, is that the first pass has the potential to "skip over" an otherwise "valid", but less likely to be correct location, which helps with false positives.
Here is that code:
public class RandarCoordFinder
{
public static final long X_MULT = 341873128712L;
public static final long Z_MULT = 132897987541L;
public static final long Z_MULT_INV = 211541297333629L;
public static final int MANSION_SALT = 10387319;
public static final int MANSION_SPACING = 80;
public static final int CITY_SALT = 10387313;
public static final int CITY_SPACING = 20;
// the last seed we processed
public long lastSeed = -1;
// a mapping of seed -> x,z that is updated everytime we get a hit
public final HashMap<Long, Long> hitCache = new HashMap<>();
// set this according to the server's seed
public long worldSeed;
// change these if you need to use different structures
public int salt
