在 Minecraft Beta 1.8 至 1.12.2 版本中，每当一个方块被破坏时，掉落物品的精确坐标就可以揭示另一个玩家的位置。
“Randar”是 Minecraft 的一个漏洞，它使用 LLL 晶格缩减来破解 Minecraft 服务器中错误重用的java.util.Random的内部状态，然后从中反向查找当前加载到世界中的其他玩家。
单击此处以 YouTube 视频的形式了解 Randar。
观看延时摄影：
在此处（作为文件）或此处（作为 YouTube）查看更多延时摄影。
目标是确定世界上其他玩家的游戏位置（即坐标），无论他们相距多远。我们在 2b2t 上玩，这是最古老、最著名的“无政府主义”Minecraft 服务器（这意味着没有规则，即玩家不会因任何原因被禁止）。做这样的事情是这个服务器上的“重点”。在这个服务器上，唯一能保证你的东西安全的是地图很大（3.6万亿平方格）并且没有其他人知道你在哪里。因此，协调利用是一件大事（打破游戏规则的交易）。 （说到，在 Randar 之前，从 2018 年到 2021 年，我们还对 2b2t、Nocom 进行了另一个协调利用；请参阅此处的文章，HackerNews 线程，YT）
Minecraft 代码中的错误从版本 Beta 1.8（2011 年发布）到 1.12.2（2017 年发布，但 2b2t 一直保留在该版本上直到 2023 年 8 月 14 日）都存在。错误在于，随机数生成器java.util.Random的各种实例在代码的各个部分中被草率地重用（并且它们一开始就是不安全的）。具体来说，在生成地形和游戏动作（例如采矿块）之间重复使用 RNG。
该漏洞利用总结如下：
World.rand将其种子重置为块坐标的函数，以便检查附近的 Woodland Mansion 应该在哪里（以及是否是这个块）。World.rand.nextFloat()调用来选择 0 和 1 之间的 XY 和 Z 坐标确定。机器人记录时间戳和精确的 XYZ 值。World.rand的确切内部状态。从广义上讲（稍后会详细介绍），观察 RNG 的一个输出可能意味着 RNG 大约 1600 万种可能的内部状态中的任何一种。然而，我们不仅对 RNG 的输出进行了一次采样，而且连续采样了三次（掉落物品的 X、Y 和 Z 坐标），并且我们知道内部状态如何在每次调用之间更新（一个简单的乘法） ，添加，然后取模）；因此我们可以使用格子方法来立即将其缩小到唯一的可能性。java.util.Random的内部状态可以像向前一样轻松地向后步进，并且通过向后步进，我们可以在短短几千步内找到它（即使在像 2b2t 这样的繁忙服务器上，有很多玩家，因此很重） RNG 的使用），它标识 RNG 内部状态重置的最近时间，以及服务器上加载的最新块的位置。即使您在已更新到较新版本 Minecraft 的服务器上玩游戏，或者以其他方式修补了 RNG 操作，由于能够追溯利用 RNG 数据，您的坐标仍然面临来自 Randar 的风险。一些 Minecraft 玩家使用像 ReplayMod 这样的 mod 来记录数据包，并且他们可能仍然保留着这些日志文件。如果有人在你在基地时使用这样的模组，他们可能（在不知不觉中）记录了可能泄露你位置的 RNG 数据，因为破坏方块是一种极其常见的行为，很可能在此类记录中发生，并且每个此类方块Break 显示服务器的 RNG 状态，从而显示最近加载的块的位置。这意味着 Randar 是一个相当大的问题：由于这种追溯利用的风险，在每个Minecraft 服务器上，在 Beta 1.8 到 1.12.2 版本中活跃的每个位置都应被视为受到威胁，即使服务器早已更新到 1.12 以上.2 或修补 RNG 操作。
如果您想自己使用 Randar 漏洞，请转到此处，rebane2001 创建了一个网站，您可以在其中拖入 1.12.2 中的 ReplayMod 文件并查看其他玩家的坐标。它在客户端运行，因此您的录音不会离开您的浏览器。这是该网站实际运行情况的视频，您可以在此处下载该视频中的示例 ReplayMod 文件。
Randar 是由 n0pf0x (pcm1k) 发现的。这篇文章是由 leijurv 撰写的，最后还有一些由 n0pf0x 撰写的附加评论。漏洞利用者包括 0x22、Babbaj、TheLampGod、leijurv、Negative_Entropy 和 rebane2001。请在此处观看 TheLampGod 的视频。请在此处观看 HermeticLock 100% 幽默 0% 事实的视频。
目录：点击此处更详细地了解可利用代码，点击此处了解如何使用晶格缩减，点击此处了解我们如何保护我们自己的存储免受 Randar 的侵害，点击此处如果您只想查看完整的利用代码，如果您运行的服务器版本仍在 Beta 1.8 和 1.12.2 之间并且您想要修补 Randar，请单击此处，或者单击此处详细了解 n0pf0x 与我们的做法有何不同。
错误图（PDF）：
漏洞利用图（PDF 格式）：
漏洞利用示例图（PDF 格式）：
《我的世界》在整个游戏中都依赖随机数。我们期望其中大多数实际上是随机的，例如生物生成和天气的随机性，但我们期望其中一些是可预测的，例如我们期望相同位置的相同世界种子生成相同的地形。 2011 年，当 Notch 在 Beta 1.8 期间首次向游戏添加结构时，他意外地重复使用了本应不可预测的 RNG，以便将村庄放置在世界中。从那时起，直到 1.13，这种草率的代码导致世界生成影响了游戏中几乎所有其他所谓的随机事件。直到 2018 年 5 月左右，Earthcomputer 和朋友们才发现这个错误，意识到块负载以可观察的方式影响游戏的 RNG，请参阅此解释。然而，他们没有意识到，或者只是从未公开透露，你也可以向后执行此操作，通过观察 RNG 来确定最近加载的块。 Randar 是由 n0pf0x（又名 pcm1k）于 2022 年 10 月 7 日发现的。大约两周后，他在 Pastebin 上发布了该漏洞的简短加密描述，以证明他当时发现了该漏洞。他主要在 9b9t 上使用该漏洞，在 2b2t 和其他服务器上只使用了相对少量的漏洞。在 2b2t 中，n0p 定位并探索了各个地点，最终来到了古灵阁的藏匿地点。他被 rebane2001 发现，最初对他如何找到该位置保持沉默。然而，大约一个月后，他开始与 SpawnMasons 讨论此事。 n0p 透露他使用了强大的坐标漏洞，并决定在 2023 年 4 月与我们分享解释，因为泥瓦匠们过去有大规模利用 2b2t 漏洞的经验，所以看到这种情况再次发生会很有趣，n0p 是无论如何，有点厌倦了。我们接受并开始记录几个帐户的物品掉落坐标，这些帐户已经为不相关的项目 24/7 开采石头/圆石（因此，行为没有变化）。我们重用了 nocom 的无头 Minecraft 系统，并添加了 Postgres 数据库来记录测量结果。正如本自述文件后面所讨论的，我们经历了几次软件迭代来破解 RNG 测量结果，最终选择了异步 Cuda 批处理作业。随着破解的测量结果添加到数据库中，我们还更新了包含热图信息的分析表，该热图信息以所有时间、每天和每小时的间隔对每个坐标的点击次数进行计数。这使得简单的 Plotly Dash UI 能够从特定时间范围和粒度中选择热图数据以在浏览器中显示，并且它让我们能够通过仅考虑在几个不同小时内加载的坐标来删除所有 Elytra stashhunting 块加载垃圾邮件。我们添加了一个简单的共享注释系统来跟踪我们在地图上每个热点发现的内容。再次从 Nocom 重用，我们有 Baritone 机器人，可以自动执行窃取物品储藏室和对结果进行排序的整个过程，完全 AFK。许多石匠在不知道漏洞利用的情况下使用munmap和1248_test_user等帐户帮助完成了这部分。古灵阁的所有藏品最终增加到了 13 亿件，其中大约一半属于诺科姆，一半属于兰德尔。
FitMC 视频中解释了完整的历史。
《我的世界》的地图是根据世界的初始种子按程序生成的，并且本质上是确定性的。当玩家探索地图时，随着玩家靠近，新区域会按需生成。由于所有生成都是可重复的（确定性的），因此他们在很多地方使用java.util.Random是完全合理的。他们希望它是可预测的。这就是使用java.util.Random的原因，因为它是一个 PRNG（不是真正的 RNG）。 P 在技术上意味着“伪”，但将其视为“可预测的”。可预测的RNG。它生成的数字看起来是随机的，但在给定相同的起始种子的情况下，它们实际上是可重复的。
Minecraft 具有在世界中生成的各种结构，例如村庄、海洋纪念碑、要塞等。这些是程序生成的一部分，因此它们也是确定性地放置和生成的。
理解这一点只需要十几行 Minecraft 代码，我已经对其进行了简化和大量注释：
// (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)
}为了清楚起见，上面的内容已被注释并稍作修改，但它在功能上与真实代码是准确的。
所以我们的想法是决定 Woodland Mansion 应该在这个 Woodland 区域（80 x 80 块）中的哪个位置，检查那个地方是否就在这里，如果是，则从这里开始生成一个 Woodland Mansion。
这段代码可能看起来有点傻，你可能会想“对每个块进行所有这些检查是荒谬的，只需选择每个区域 Woodland Mansions 应该去的地方并完成它”。原因是 Minecraft 块是彼此独立生成的，并且以未知的顺序生成，但我们仍然希望从给定的种子生成一个确定性的世界。我们不知道玩家将以什么顺序走遍世界，能够以无状态的方式按需生成任何块是很好的。这是一次很好的游戏体验。因此，像这样看起来很奇怪的代码。
不管怎样，对于每个块加载，对于正在加载的块周围的大正方形中的每个块，都会调用该代码。解释原因有点复杂，所以我基本上会跳过它（基本思想是这些结构的大小（远）大于一个块，因此我们需要检查许多附近块中的结构起源，以便生成当前的这一点正确）。
请注意，这仅影响主世界。下界是安全的，因为它的所有结构生成始终使用安全的 RNG。在 The End 中加载区块会受到末地城市的影响，但仅限于它们的初始生成，而不是每次加载时，因此 The End 相对安全，因为您基地的每个区块在您第一次加载时只会影响 RNG 一次它。然而，这并不完全万无一失，因为玩家通常每次前往基地时都会生成新的区块，并且偶尔会在已经到达基地时生成新的区块。
问题在于它修改了全局World.rand的种子。这只是懒惰的编码。他们所做的就是调用nextInt四次来选择 X 和 Z 坐标。他们可以用 Random random Random random = new Random(the same stuff) Random random = this.world.setRandomSeed(... （换句话说，在这里创建一个新的Random而不是弄乱其他所有东西使用的现有随机数？ ??）。
至关重要的是，调用setRandomSeed是为了检查Woodland Mansion 应该去哪里。无论如何，它会在每个块负载上、任何地方发生。你不必站在林地大厦或类似的地方/附近。
好吧，事实证明World.rand在数百个地方使用，并且通过正常玩游戏可以轻松观察到其中许多地方。例如，当您开采一个区块时：
/**
* 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 );
}再次稍作修改，但功能上对于我们正在讨论的内容来说是准确的。
这里的想法是，在《我的世界》中，当你开采一个方块时，它会掉落一个物品。该项目被丢弃在块内的随机位置。例如，如果该块位于(10, 20, 30) ，则该项目将出现在(10.25, 20.25, 30.25)和(10.75, 20.75, 30.75)之间的某个位置。
通过连续调用world.rand.nextFloat()三次（针对 X、Y 和 Z）来选择该项目的确切位置。
这就是 Minecraft 所需的全部代码！
现在，我说我们可以用这些nextFloat调用做一些事情。首先，让我们看看是否可以“向后工作”来看看nextFloat调用的是什么。这很幸运，但我们实际上可以。注意上面代码中：随机浮点乘以0.5，然后加上0.25。这个想法是从 0 到 1 之间的随机数移动到 0.25 到 0.75 之间的随机数。您可能会担心，因为如果您将一个整数除以二，您会丢失一些信息，因为结果是向下舍入的。值得庆幸的是，将浮点数乘以 0.5 是完全可逆的，因为它只是减少指数，而尾数不变。然后，将浮点型转换为双精度型，这样精度更高。添加0.25，然后添加块坐标。然后，它通过网络完全精确地发送到客户端。结果：整个过程是可逆的，因此我们可以获得World.rand.nextFloat()生成的确切的三个浮点数。
java.util.Random如何生成浮点数？其实这很简单。它生成 0 到 2^24 之间的整数，然后将其除以 2^24（得到 0 到 1 之间的数字）。它如何获得该随机整数？也很简单！它是一个线性同余发生器（LCG）。这意味着下一个种子是前一个种子乘以某个值，加上其他值，再对其他值取模。
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
}在本例中，乘数为 25214903917，加数为 11，模数为 2^48。
利用由此产生的浮点数，我们可以将其乘以 2^24 以返回 randomInteger，从而获得 48 位种子的“上半部分”（最高有效的 24 位）。
简而言之，从我们的测量中，我们了解到种子位于measuredRandomInteger * 2^24和(measuredRandomInteger + 1) * 2^24之间。
我们可以对 X、Y 和 Z 连续执行三次。
我们知道，在 X 和 Y 之间，以及 Y 和 Z 之间，种子是根据newSeed = (oldSeed * 25214903917 + 11) mod 2^48更新的
我必须提到一个有效的选项是 for 循环，它尝试所有 2^24 可能的较低位。对于阅读本文的程序员来说，我希望这能清楚地说明问题所在：
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 ;
}
}这会起作用，而且确实起作用，但它不是那么快，也不是那么有趣。所以我们用格子代替！
然而，我觉得我必须走得有点乱。格子缩减部分确实在这里出现，但它真的很复杂，我敢打赌它的读者保留率会很低，我不想失去你。因此，我将只为您提供 for 循环解决方案（该解决方案确实有效），然后继续进行漏洞利用的下一步。晶格约简方法的解释将在后面介绍:)
一旦我们有了这颗种子，我们该如何处理它呢？
首先，请注意我们可以将 LCG 向后移动。显然，加11是可逆的，但是乘以那么大的数字是可逆的吗？我们的乘数25214903917是一个奇数，这意味着它不能被二整除，因此它不与我们的模数 2^48 共享任何因数（因为 2^48 实际上只是一堆二）。由于它与模数互质，我们可以将其求逆，即找到另一个满足x * 25214903917 - 1能被 2^48 整除的数字x 。或者换句话说， 25214903917 * x mod 2^48 = 1 。该号码是246154705703781 。这有助于反转乘法，因为如果我们有secret * 25214903917并且我们想要计算出secret ，我们可以只计算secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret 。
好的，我们可以向前和向后步进java.util.Random的内部种子。向前是newSeed = (oldSeed * 25214903917 + 11) mod 2^48 ，向后是oldSeed = ((newSeed - 11) * 246154705703781) mod 2^48 。这是有效的，因为这些数字25214903917和246154705703781当相乘时，当你取模 2^48 时结果为1 。
现在，当我们向后退一步时，我们希望在每一步中检查该种子是否意味着最近在世界某个地方执行了 Woodland Mansion 检查（漏洞利用的全部要点）。我们该怎么做呢？
Minecraft 世界范围从 -3000 万到 +3000 万块。每个“林地区域”（世界上随机放置单个林地大厦的区域，根据前面显示的代码）都是 80 x 80 块，即 1280 x 1280 块。这是 23437.5 个林地区域，但对于我们所有的代码，我们只是四舍五入到 23440，因为它是一个整数，即使你的玩家不能移动超过 3000 万，你只要站在它附近就可以加载超出它的块，我们只是不想担心这一切。
因此，X 轴和 Z 轴上的值都是 -23440 到 +23440。这是(23440*2+1)^2 （又名2197828161 ）个可能的林地区域，每个区域都会生成一个独特的“豪宅种子”（定义为表明有人刚刚在某个林地区域加载了一块块的种子）。我们需要能够检查某物是否是豪宅种子。我们可以迭代所有 22 亿个豪宅种子来检查每一个吗？会太慢。可以制作一个包含 22 亿个条目的HashSet吗？即使像我们在 nocom 中那样使用历史地图，也会占用太多 RAM，甚至在使用abseil-cpp的 C++ 中，它也使用了 50GB 的 RAM。更不用说另一部分了：我们实际上想了解他们在世界上的哪个位置（这就是重点）。因此，仅了解这是豪宅种子还不够，我们还想（有效地）了解哪个林地区域导致了它。
回想一下从林地区域到豪宅种子的函数（注意：为了简单起见，我现在组合了上面代码以来的一些常量，该方程现在专门用于 2b2t 的种子）：
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
（ -4172144997891902323数字来自-4172144997902289642 + 10387319 ，这是 2b2t 世界种子 + 用于播种林地区域的魔法值（如前所示）。对于任何其他世界，您只需将自己的种子放入此等式中即可.)
我们对 x 坐标无能为力，因为它要乘以偶数。但是 z 坐标上的系数是多少？看起来是奇数！！！让我们使用与之前相同的技巧再次反转它，我们得到211541297333629 。
假设我们有一个给定的种子。如果我们可以迭代从 -23440 到 +23440 的所有可能的 X 坐标，并且对于每个坐标，计算林地区域的 Z 坐标（如果它有这个豪宅种子），会怎么样。换句话说，如果我们知道x和z ，上面的方程给我们提供了seed ，但是如果我们知道seed和x ，我们可以创建一个给我们z方程吗？答：是的。我们只是重新排列上面的方程，并利用 Z 的系数是可逆 mod 2^48 的事实，因为它是奇数。
方程为：
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
因此，这是一个非常好的解决方案，因为我们可以为 X 使用一个仅执行 46,881 次迭代的 for 循环，而不是使用总共 22 亿次迭代的两个嵌套循环（一个用于 X，一个用于 Z）。这是 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 ;
} （注意：奇怪的<< 16 >> 16正在执行 mod 2^48，但我们实际上希望使用有符号类型来执行此操作，以便当 z 在 -23440 和 0 之间时我们仍然得到正确的答案，这是一种方法将 48 位数字符号扩展为 64 位，用正确的符号位填充高 16 位作为二进制补码）
所以这确实有效，而且速度相当快......对于单个种子来说。但请记住，我们可能会将 RNG 后退数千步，并在每一步运行此检查，直到找到匹配项。当时，我们在最低层使用了糟糕的 DigitalOcean Droplet，这实际上使一切都滞后并且无法跟上实时（机器人每秒挖掘许多块，每个块需要数千个 rng 步骤才能破解，每个 rng 步骤需要 23440*2+1 次操作来检查，将它们相乘，您就可以达到每秒数亿次操作，所以您明白为什么在蹩脚的 VPS 上会遇到麻烦，尤其是当该 VPS 也在尝试时运行 Minecraft 的多个无头实例）。
无论如何，我们改用查找表方法，并在 Cuda 中重写它，以便每隔几分钟在我的桌面上作为批处理作业运行一次。它每秒可以执行数百万次任务，因为数千个 cuda 核心中的每一个都可以并行处理自己的种子。想法是这样的：查找表的键是豪宅种子的低 32 位，值是林地区域的 X 坐标。该查找表不会发生冲突，因为不知何故，每个豪宅种子都有唯一的低 32 位。我不明白为什么这是真的，这很有趣。你可能会认为这行不通。但我认为系数341873128712和132897987541可能是专门选择的以使这项工作有效？例如，如果你有 22 亿个弹珠和 43 亿个桶，并且你独立地将每个弹珠放入一个随机桶中，那么每个弹珠获得自己的桶的几率是多少？基本上为零。接近尾声时，每个新弹珠都有超过 50% 的机会击中已装满的水桶。然而，显然，这些并不是独立随机的，所以它以某种方式起作用。讽刺的是，如果您正在阅读本文并了解其工作原理或为什么这两个特定系数能够实现此目的，请告诉我。无论如何，它有效。查找表有 2^32 个条目，每个条目为 2 个字节（因为它只是 -23440 到 +23440 之间的数字），因此 GPU 上需要大约 9 GB 的 VRAM。
林地检查函数现在看起来像（同样，这是实际的代码，但经过简化，所有帮助器和常量内联等）：
__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;
}这在大批量中效果很好，并且可以在 3090 上每秒破解一千万个种子。事实证明，当经纱中的某些线程提前终止时，这并不是什么大不了的事情，而且我们无法真正做到这一点它比这更快。 （原因是我们根本无法事先知道哪些种子会采取更多/更少的步骤）。
嗯，就是这样。给定种子，这就是我们获得世界上最近发生块加载的林地区域的方式。换句话说，我们刚刚了解到，最近一次有人在 2b2t 上行走并加载世界的新区域，是在我们刚刚确定的这个1280 x 1280 块林地区域内的某个地方。 （这足够精确，只需几分钟的搜索即可找到它们）
在实践中，需要多少 RNG 步骤？在低端，可靠的测量从 4 个 RNG 步骤开始，低于该步骤的所有内容都是测量误差/随机噪声，我们知道这一点，因为 Woodland Mansion 代码在我们可以测量它之前立即调用rand.nextInt四次。平均而言，每个 Woodland 种子之间大约有 128,000 步，但实际上，在 2b2t 上的绝大多数时间里，我们在几十步之内发现了一个 Woodland 种子。这是由于 Minecraft 中发生的事情的顺序的细节。从技术上讲，我们的测量发生在tick的一开始，因为那是处理用于破坏块的数据包的地方。一般来说，在上一个tick期间，一个块已经被加载到最近的历史记录中。然而，有时，一个事件可能会导致中间出现一堆 RNG 步骤。我们认为这个事件是爆炸，比如有人用拳头将末影水晶炸毁，或者可能是枯萎的头骨。玩家打孔数据包处理过程中也会发生末地水晶爆炸，RNG 步数也为 1354 步（计算长方体中的方块伤害为 1352 步）
在此图中用作工作示例的坐标上，上面的代码输出如下：
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>
请注意它如何定位 Woodland Region 123,456 ，并注意最终的“位于之间的某人”如何包含我们最初输入的真实坐标，即 x=157440 z=583680。此外，RNG 测量结果与红色的十六进制匹配： 0xf61dc9等于16129481 、 0x1700fb等于1507579 、 0xc50d15等于12913941 。对于种子， 0xed92e70ba4a0等于261215197308064 ， 0xf61dc9221ba4等于270607788940196 。
您可能可以找到用于禁用 RNG 操作的补丁或配置选项，类似的东西可以用于修补 Randar，这可能是最简单的方法。如果您找不到禁用 RNG 操作的简单方法，这里是需要在World类中调整的代码：
易受攻击的版本：
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ;
}如果您想要完美的保护，只需更改此函数即可每次返回不同的随机数：
补丁版本：
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
return new Random ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
}这可能不会有很好的性能，所以如果您愿意，您可以引入一个新字段， separateRandOnlyForWorldGen ，它不与其他任何内容共享，例如：
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 ;
}如果您使用 PaperMC 1.12.2 ，则可以应用以下补丁。备用链接。
这将是一个附加部分，我将在其中讨论一些额外的内容，从我的角度来看，这些内容更有意义，因为除了基本想法之外，我们大多是独立开发的东西。
我想提到的第一件事是从种子定位坐标的系统。 Mason 使用大型查找表和 GPU 处理，而我则依靠缓存来提高速度。每当发生命中时，其坐标以及半径内的所有坐标都会放入 HashMap 中。种子分两次处理。第一遍将 RNG 后退，并检查种子是否存在于缓存中，或者是否与上次处理的种子相同，这是不同的考虑方式。第二遍仅在第一遍失败时发生，速度慢得多，并且使用前面描述的相对昂贵的算法。该系统的一个令人愉快的副作用是，第一次通过有可能“跳过”原本“有效”的位置，但不太可能是正确的位置，这有助于误报。
这是该代码：
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 = MANSION_SALT ;
public int spacing = MANSION_SPACING ;
public RandarCoordFinder ( long worldSeed )
{
this . worldSeed = worldSeed ;
}
// a simple class that extends java.util.Random and provides some extra methods and constants we need
public static class RandarRandom extends Random
{
public static final long MULT = 0x5DEECE66DL ;
public static final long ADDEND = 0xBL ;
public static final long MASK = ( 1L << 48 ) - 1 ;
public static final long MULT_INV = 0xDFE05BCB1365L ;
public long seed ;
public RandarRandom ( long seed )
{
this . seed = seed ;
}
@ Override
public void setSeed ( long seed )
{
this . seed = seed ;
}
@ Override
public int next ( int bits )
{
seed = ( seed * MULT + ADDEND ) & MASK ;
return ( int )( seed >> 48 - bits );
}
public int prevInt ()
{
seed = (( seed - ADDEND ) * MULT_INV ) & MASK ;
return ( int )( seed >> 16 );
}
}
public enum FindType
{
HIT ,
SKIP ,
FAIL ;
}
public record FindResult ( FindType type , int xCoord , int zCoord , int steps )
{
}
public FindResult findCoordsSeed ( long seed , int maxSteps )
{
seed &= RandarRandom . MASK ;
// remember and update lastSeed
long last = lastSeed ;
lastSeed = seed ;
RandarRandom random = new RandarRandom ( seed );
// first pass - this is meant to be quick
for ( int i = 0 ; i < maxSteps + 100000 ; i ++)
{
if ( random . seed == last && i > 0 )
{
// we encountered the last processed seed while stepping back, skip
return new FindResult ( FindType . SKIP , 0 , 0 , i );
}
else
{
Long hashValue = hitCache . get ( random . seed );
if ( hashValue != null )
{
// we found a hit in our cache
int xCoord = ( int )(( hashValue >> 32 ) & 0xFFFFFFFF );
int zCoord = ( int )( hashValue & 0xFFFFFFFF );
cacheNearby ( xCoord , zCoord , 8 );
return new FindResult ( FindType . HIT , xCoord , zCoord , i );
}
}
random . prevInt ();
}
random . seed = seed ;
// second pass - this is slow and should only happen if the first pass fails
for ( int i = 0 ; i < maxSteps ; i ++)
{
// undo worldSeed and salt
long seedValue = ( random . seed ^ RandarRandom . MULT ) - worldSeed -
( long ) salt ;
Coords coords = findCoords ( seedValue , 1875000 / spacing + 8 );
if ( coords != null )
{
// we found a hit
cacheNearby ( coords . x , coords . z , 8 );
return new FindResult ( FindType . HIT , coords . x , coords . z , i );
}
random . prevInt ();
}
// we could not find anything
return new FindResult ( FindType . FAIL , 0 , 0 , - 1 );
}
public static long getRandomSeed ( int x , int z , int salt , long seed )
{
return (( long ) x * X_MULT + ( long ) z * Z_MULT ) + seed + ( long ) salt ;
}
private void cacheNearby ( int x , int z , int radius )
{
for ( int xOff = - radius ; xOff <= radius ; xOff ++)
{
for ( int zOff = - radius ; zOff <= radius ; zOff ++)
{
int cacheX = x + xOff ;
int cacheZ = z + zOff ;
long cacheSeed = ( getRandomSeed ( cacheX , cacheZ , salt ,
worldSeed ) ^ RandarRandom . MULT ) & RandarRandom . MASK ;
hitCache . put ( cacheSeed , ( long ) cacheX << 32 | cacheZ &
0xFFFFFFFFL );
}
}
}
public record Coords ( int x , int z )
{
}
public static Coords findCoords ( long value , int distance )
{
value &= RandarRandom . MASK ;
for ( int x = - distance ; x <= distance ; x ++)
{
long testValue = ( value - X_MULT * x ) & RandarRandom . MASK ;
long z = ( testValue * Z_MULT_INV ) << 16 >> 16 ;
if ( Math . abs ( z ) <= distance )
{
return new Coords ( x , ( int ) z );
}
}
return null ;
}
}我想提的另一件事是我在《The End》中如何使用它。如前所述，The End 中的区块仅在首次生成时影响 RNG 一次。这使得事情变得更加棘手，因为与主世界不同，玩家不能通过简单地在其基地加载一个块来找到玩家。
相反，我们必须依赖另外两个主要场景：
第一种情况本质上意味着我们仍然可以使用简单的方法来简单地计算一个区域被击中的不同次数，但是我们将受到很大的限制，因为击中可能非常罕见，并且可能会被仅仅飞过某个区域的人所迷惑。几次明显的足够的时间。第二种情况要求我们识别并追踪这些踪迹。
那么我们究竟该如何追踪踪迹呢？理论上，您可以创建一个系统来自动识别和跟踪踪迹，但我从未实现过这一点，只是手动直观地跟踪踪迹。在追踪踪迹时，有一些想法可以提供帮助。例如，通往同一个地方的多条路径可能意味着存在一个基地。知道特定的命中或踪迹是由特定玩家造成的也很有帮助，稍后会详细介绍。
那么我们如何判断哪个玩家造成了特定的点击呢？在主世界中，我们可以简单地寻找玩家加入后立即发生的“独特”点击。然而，这在这里不太可能奏效，所以我们必须做点别的事情。实际上有一个简洁的系统可以做到这一点。它基于这样的假设：The End 中实际上并没有太多玩家同时在线，并且我们可以辨别这些玩家是谁。这个想法是，每个周期的 RNG 调用数量部分与当前加载的块数量相关，因此与该维度中的玩家数量相关。通过观察玩家加入或离开后这些呼叫数量的突然增加或减少，我们可以识别出处于 The End 的玩家。我们将该系统称为“最终占用跟踪器”(EOT)。
EOT 维护两套。第一个记录了我们认为“现在”处于末日之中的人。这可能会漏掉玩家，因此被认为更容易出现漏报。第二个记录了我们认为“整体”中“结局”中的人物，在一定时间内前后移动。这与当前在线的玩家相结合，并且被认为更容易出现误报。通过在发生命中时查看这些集合并进行一些手动推理，我们可以粗略地了解谁可能造成了特定的命中。
应该注意的是，EOT 仅在 9b9t 上进行过测试，目前可能依赖于其他服务器（例如 2b2t）上可能不成立的条件。它假设可以在没有太大波动的情况下对RNG进行采样，这对于2B2T可能会更棘手，因为块位置速度限制。如果服务器上的末端有明显更多的播放器活动，则可能会变得更棘手，因为它是一个更大的服务器，这对于2B2T来说可能是正确的。
