浅谈 Minecraft 种子逆向

Monad · 2020-05-26 20:11:07 · 个人记录

under construction

有意见欢迎提出

洛谷 Markdown 不支持脚注吗？

前言

想象你在机房摸鱼玩 Minecraft 的时候，你心血来潮突然想修个史莱姆农场（不要问为什么），所以你需要找到史莱姆区块。你知道有一个网站叫做 ChunkBase^1，可以根据种子查找史莱姆区块。但是，当你在服务器内执行 /seed 的时候，很不幸你得到了一条错误信息：

服务器禁止 /seed 怎么办？一个比较简单的方法就是 py 服主。但是你询问之后，服主以没有女装照为由拒绝了你。简单啊，拍一张不就好了嘛

所幸，我们有更好的解决方法。

一个想法

一个很显然的破解种子的方法就是把每一个种子都试一遍，看看哪个种子生成出来的地图跟服务器的地图一样就可以了。这种做法理论上是可行的，但是实际中 Minecraft 种子的取值范围是 [-2^{63}, 2^{63}-1] 的，我们假设验证一个种子需要 10s（假设新建地图后你可以认出出生点），那么全部遍历完需要高达 6 万亿年！

然后另一个很显然的地方就是，我们比较文件没有必要逐个字节地去比较，我们只需要必交他们的哈希值就可以了。同理，对于 Minecraft 的地图，我们只需要比较它们特征性的地方就可以了。就比如村庄（结构）的位置、某处的生物群系，甚至末地的黑曜石柱都可以利用。也就是说，如果服务器地图的某一处有一个村庄，那么相同种子的地图的同一个地方也有村庄。

我们这里抛砖引玉，讲一下结构的生成好了。

结构的生成

研究结构的生成的最好方式就是研究源代码。Mojang 于去年 9 月公开了 Minecraft 的混淆映射表^2，也就是说我们能够用反编译工具（如 DecompilerMC^3）反编译出可阅读的代码了。

这里我们以女巫小屋为例，分析其生成方式。代码来源：DecompilerMC 反编译 Minecraft 1.15.2。

女巫小屋的生成属于 RandomScatteredFeature 这一类型，RandomScatteredFeature 的相关代码位于 net/minecraft/world/level/levelgen/feature/RandomScatteredFeature.java 中。

@Override
protected ChunkPos getPotentialFeatureChunkFromLocationWithOffset(ChunkGenerator<?> chunkGenerator, Random random, int n, int n2, int n3, int n4) {
    int n5 = this.getSpacing(chunkGenerator);
    int n6 = this.getSeparation(chunkGenerator);
    int n7 = n + n5 * n3;
    int n8 = n2 + n5 * n4;
    int n9 = n7 < 0 ? n7 - n5 + 1 : n7;
    int n10 = n8 < 0 ? n8 - n5 + 1 : n8;
    int n11 = n9 / n5;
    int n12 = n10 / n5;
    ((WorldgenRandom)random).setLargeFeatureWithSalt(chunkGenerator.getSeed(), n11, n12, this.getRandomSalt());
    n11 *= n5;
    n12 *= n5;
    return new ChunkPos(n11 += random.nextInt(n5 - n6), n12 += random.nextInt(n5 - n6));
}

@Override
public boolean isFeatureChunk(BiomeManager biomeManager, ChunkGenerator<?> chunkGenerator, Random random, int n, int n2, Biome biome) {
    ChunkPos chunkPos = this.getPotentialFeatureChunkFromLocationWithOffset(chunkGenerator, random, n, n2, 0, 0);
    return n == chunkPos.x && n2 == chunkPos.z && chunkGenerator.isBiomeValidStartForStructure(biome, this);
}

其中 isFeatureChunk 就是用来判断某个区块能否生成女巫小屋用的。n, n2 就是这个区块的 (x,\,z) 坐标（这个坐标是区块坐标，而非方块坐标）。然后上面的逻辑我们可以整理一下，其中 this.getSpacing()、this.getSeparation() 和 this.getRandomSalt() 都是 Magic number，chunkGenerator.getSeed() 就是当前地图的种子。整理如下：

bool checkChunk(const long long seed, const int cx, const int cz) {
    const int spacing = 32;
    const int separation = 8;
    const int random_salt = 14357620;

    int x = cx, z = cz;

    if (x < 0) x -= spacing - 1;
    if (z < 0) z -= spacing - 1;
    x /= spacing;
    z /= spacing;

    long long inner_seed = x * 341873128712LL + z * 132897987541LL + seed + random_salt;
    Random rng = fromSeed(inner_seed);

    x *= spacing;
    z *= spacing;
    x += rng.nextInt(spacing - separation);
    z += rng.nextInt(spacing - separation);

    return cx == x && cz == z;
}

其中的 spacing、separation 和 random_salt 就是上面的三个 Magic number，fromSeed 和 nextInt 为 Java 的随机数生成器相关。注意到我忽略了 chunkGenerator.isBiomeValidStartForStructure(biome, this) 这个条件，因为生物群系的生成过于复杂，而且忽略也不影响接下来的步骤。

到了这里，我们只需要收集一下一些结构的坐标（其实 7 到 8 个就够了），写个程序，枚举一下种子，就可以在 2 万年内跑出来了。快了一亿多倍，惊不惊喜（其实并不行，下面会讲到）

Java Random

Java 随机数的源代码可以从 OpenJDK 的网站上找到^4。

这里我就直接整理了几个相关的函数，用 C++ 实现：

constexpr long long MULTIPLIER = 0x5DEECE66D;
constexpr long long ADDEND = 0xB;
constexpr long long MASK = (1LL << 48) - 1;

struct Random {
    long long seed;

    Random(const long long p) {
      seed = (p ^ MULTIPLIER) & MASK;
    }

    long long next(const int bits) {
        seed = (seed * MULTIPLIER + ADDEND) & MASK;
        return seed >> (48 - bits);
    }

    int nextInt(const int mod) {
        if (mod & (mod - 1))
            return next(31) % mod;
        else
            return ((long long)mod * next(31)) >> 31;
    }

    long long nextLong() {
        return ((long long)next(32) << 32) | next(32);
    }

    float nextFloat() {
        return (double)next(24) / (1 << 24);
    }

    double nextDouble() {
        return (((long long)next(26) << 27) | next(27)) * 0x1.0p-53; // 1.0 / (1LL << 53);
    }
};

从中我们可以发现，传入 Random 的种子都会与 MULTIPLIER 亦或一下，然后与 MASK 与（AND）一下。也就是说，结构的生成（在忽略生物群系的情况下）只跟种子的低 48 位有关。

也就是说，根据结构可以过滤出种子的低 48 位，也就是说我们只需要枚举 2^{48} 就够了。现在我们只需要用 4 个月就可以算出种子的低 48 位啦（高 16 位下面会说到），又快了 6 万倍。如果你的 GPU 比较好你也可以直接用显卡加速，显卡加速只需要 1 天就可以了。

继续优化

如果你没有一个好的显卡，又不想等那么久，说白了就是懒，那还能不能继续优化呢。

答案是可以的。根据这篇文章^5，Random.randInt 在模 8 的情况下，返回的结果只跟种子的低 20 位有关。换句话说，上上面的代码相当于比较当前区块的偏移量与 rng.nextInt(spacing - separation) 是否相等，我们只需要对这两个都模 8，就可以快速过滤出种子的低 20 位。

结合上面的程序，现在就只需要 \text{O}(2^{20}+2^{28})，也就是几十秒的时间，就可以搞到种子的低 48 位了。

高 16 位

搞完了低 48 位，高 16 位怎么破？当然用生物群系啦。

Q：等等，你前面不是说生物群系的代码很难写吗？

A：确实，但是又不用我们自己写......

检查生物群系，我们可以用 cubiomes^6 这个库，这个库可以输入一个种子和一个方块坐标，就能算出这个位置的生物群系。这个库十分良心，现在还在更新。

用同样的思路，我们只要收集几个位置的生物群系，然后枚举一下高 16 位，扔进去库里面算一算看看是不是一样的就可以了。

小结

看到这里，相信你已经会暴力出一个服务器的种子了，赶快去服务器搞事情吧！

其实除了女巫小屋之外，丛林神庙、沙漠神庙那些也是可以的（random_salt 不同），海底遗迹也行（x, z 偏移量需要用 (rng.nextInt(spacing - separation) + rng.nextInt(spacing - separation)) / 2 来算）。具体可以看 Minecraft 的源代码。

Q & A

Q：我不想写代码，我只想要开箱即用的工具。

A：请参考 BV1H7411p73T。

Q：我甚至懒到不想跑图，还有更快的方法吗？

A：女装吧，少年。记得给我捎一张照片。