Minecraft 1.12.2中逆推从世界地图到世界种子

12 月 ago
新, 韵
4 minutes

环境

    Minecraft 1.12.2 Java Edition

背景出自中国传统文化里的一个重要概念。

如果在Minecraft的多人游戏中透露了种子值，会发生什么呢？仅仅是容易想到的，也可以做到以下几点。

    • 採掘場付近のすべてのダイヤ鉱石の座標を列挙

 

    • 世界中のすべての村とネザー要塞の座標とチェストの中身を特定

 

    • レアバイオームの特定

 

    • エンチャント金りんごの最短入手経路の特定

 

    • ワールドのクローンを使ったクリエイティブでの実験

 

    • サーバーで認可されていないMODの使用による地形の調査

 

    • 特定の種類のスポーナーの検索

 

    • MODが入っている場合、MOD由来のレア構造物の検索

 

    レアバイオームの検索

因为这个原因，没有必要在客户端上安装MOD，所以无法通过服务器规则来控制客户端的版本、MOD或未修改的内容。

在只允许使用特定的客户端MOD和非公开种子的服务器上，如果只有一个特定的玩家知道种子并利用它，即使只是确定钻石矿石的坐标，也会造成相当大的平衡破坏。

所以，我們思考了一個多方非鯖魚罐播放器可以在不破解伺服器的情況下，僅使用合法手段獲取資訊來尋找種子的方法。如果這是可能的，即使服務器管理員將種子保密，我們仍然能夠通過物理手段來得知它，這就需要額外採取措施來監控行為和本地規則等。

规则

在一个安装了一些Forge MOD的Minecraft 1.12.2 Java版服务器上，生成了一个与原版相同的地形时，你可以了解到世界的种子。

条件 – The condition(s).

前提 – 假设的条件或基础。

    • ワールドの地形生成のコンフィグはデフォルトから一切弄っていない

 

    • シード値はlongの範囲でランダムである

 

    • 計算にはせいぜい数日程度しかかかってはならない

 

    個人用の一般的なパソコンで計算できなくてはならない

禁止使用

    • ワールドには正規の手段でしか接続してはならない

 

    • サーバーのルールにより認められていないMODは使えない

 

    • 改造したクライアントやMODを使ってワールドに接続してはならない

 

    サーバーにはMinecraftからしかアクセスしてはならない

有可能

    • オーバーワールドの地表を自由に探検することができる

 

    • F3による座標表示が利用できる

 

    • F3によるバイオーム表示が利用できる

 

    見た情報をスクリーンショットなどで自由に記録できる

作战计划

根本的戦略可以使用“尝试所有可能的种子候选以确定某个种子是否生成特定地形”。然而，由于存在2^64种可能的种子，即使对判定部分进行相当的加速，在普通个人电脑上也需要大约1万年的时间。要是使用超级计算机则可能很快完成，但这样很难说能否得知答案。

当对于所有可能的种子候选进行测试以确定是否生成特定地形时，可以将其用伪代码表示如下：”尝试所有可能的种子候选，以确定是否生成特定的地形”。

for (long seed = 0; seed != 0xFFFFFFFFFFFFFFFFL; seed++) { // (1)
    if (f(seed)) System.out.println(seed);
}

/**
 * あるシードがそのワールドを生成するか否かを返す関数。
 */
abstract boolean f(long seed); // (2)

在这里改进的点是(1)和(2)。(1)是因为目前循环次数太多，大约需要一万年的时间，所以必须采用更节约计算次数的循环方法。(2)必须尽可能使用简单的公式进行筛选。

(2) 可以将其分割成多个部分。

for (long seed = 0; seed != 0xFFFFFFFFFFFFFFFFL; seed++) {
    if (f1(seed) && f2(seed) && f3(seed)) System.out.println(seed);
}

/**
 * 候補を大まかに絞り込む高速な関数
 */
abstract boolean f1(long seed);

/**
 * 候補を数個に絞り込む中速な関数
 */
abstract boolean f2(long seed);

/**
 * 候補を1個に絞り込む低速な関数
 */
abstract boolean f3(long seed);

本次计划使用类似的策略来确定种子。

筛选备选者的快速函数

考虑到f1需要强调速度，所以打算将其设计为可在GPGPU上运行的函数。为此，必须满足以下一些条件。

    • Minecraftの実行中のインスタンスを利用しない

 

    JREのライブラリに依存しない

举个例子，如果 x + 700 等于 4 的话就很简单了。如果 Math.sin(x * 0.001) 等于 1 的话，就需要对 Math.sin 进行一些处理。如果 world.getBiome(new BlockPos(x, 65, 0)) 等于 Biome.FOREST 的话是不可能的。

使用Aparapi来进行GPGPU计算。

    JavaでGPU演算(Aparapi)してみた – ka-ka_xyzの日記 http://ka-ka-xyz.hatenablog.com/entry/20180129/1517152510

我使用了这个GPU。

    真のローエンド「Geforce GT 710」レビュー。3,000円で買える超省電力グラボのベンチマーク・ゲーム性能 http://androgamer.net/2017/10/08/post-6852/

如果使用更好的GPU，可以进一步缩短时间。

在这里，我们使用F1来确定村庄的生成位置。

    Minecraft 1.12.2　村の座標決定部分のアルゴリズム – Qiita https://qiita.com/MirrgieRiana/items/0a3baee86bb661dc5f99

使用村庄的生成坐标可以通过以下步骤粗略筛选候选对象。

    • 村を8個くらい発見しておく

 

    • 村が生成されるチャンク座標をメモする

 

    その8か所の座標に村が生成されるシードだけを列挙する

在给定的区块坐标上生成村庄与否可以通过下面的函数test来确定。

int distance = 32;

boolean test(long seed, int chunkX, int chunkZ)
{
    seed += (long) getRegionIndex(chunkX) * 341873128712L + (long) getRegionIndex(chunkZ) * 132897987541L + 10387312L;
    seed = seed ^ 0x5DEECE66DL;
    seed = next(seed);
    if (!test2(seed, chunkX)) return false;
    seed = next(seed);
    if (!test2(seed, chunkZ)) return false;
    return true;
}

boolean test2(long s, int chunkIndex)
{
    return (s >> 17) % 24 == getChunkIndexInRegion(chunkIndex);
}

int getRegionIndex(int chunkIndex)
{
    if (chunkIndex < 0) chunkIndex -= 31;
    return chunkIndex / 32;
}

int getChunkIndexInRegion(int chunkIndex)
{
    return chunkIndex - getRegionIndex(chunkIndex) * 32;
}

long next(long s)
{
    return (s * 0x5DEECE66DL + 0xBL) & 0xffffffffffffL;
}

long prev(long s)
{
    return ((s - 0xBL) * 0xdfe05bcb1365L) & 0xffffffffffffL;
}

这段代码已经展开了Random内部的内容。关于Random的内部处理，请参考下一个选项。

    Randomの内部seedの推移の逆算 – Qiita https://qiita.com/MirrgieRiana/items/1833ec6ab9d90341760a#%E5%95%8F%E9%A1%8C

此函数不依赖于JRE或Minecraft实例，因此可供Aparapi使用。

假设距离默认为固定的32，接下来讲述。那么在区域中，生成村庄的坐标将有24种方式，每个坐标轴上有一种方式。

只要根据调查情况，调用上述函数的村庄数量，就可以粗略地筛选出种子。

然而，由于在这个函数中要将Random的前16位舍去，从原理上讲，无论调查多少个村庄，都无法将种子的候选数削减到只有一个。因此，我们将从2^48个可能性中筛选出大约1000个，然后再筛选出65536*1000个左右的候选数。

for (long seed = 0; seed != 0xFFFFFFFFFFFFL; seed++) {
    if (!test(seed, -16, -18)) continue; // シード1251341の村配置
    if (!test(seed, 12, -49)) continue;
    if (!test(seed, -77, 19)) continue;
    if (!test(seed, 21, -80)) continue;
    System.out.println(seed);
}

如果假设有2的64次方种可能性，需要一万年才能完成，那么根据简单计算，有2的48次方约等于2.8乘以10的14次方种可能性，只需要50天左右。相比之下，从接下来的6,553,6000（约等于6.5乘以10的7次方）种可能性中筛选，要少得多。

(1) 循环部分的优化

虽然我们已经成功将计算时间缩短到大约50天左右，但仍然难以说这已经是可计算的了。然而，事实上，存在一种简单的方法可以将计算时间缩短到1/24。这可以利用上述提到的村庄生成算法和随机数的特性来实现。每个村庄的生成坐标有能力缩小到1/(24*24)，即使只考虑坐标的一侧，也可以达到1/24的准确性。下面的代码是将test和test2合并在一起的。在此过程中，我们可以在(3)的时间点对种子进行一定程度的预测。

boolean test(long seed, int chunkX, int chunkZ)
{
    seed += (long) getRegionIndex(chunkX) * 341873128712L + (long) getRegionIndex(chunkZ) * 132897987541L + 10387312L;
    seed = seed ^ 0x5DEECE66DL;
    seed = next(seed);
    // (3)
    if (!((seed >> 17) % 24 == getChunkIndexInRegion(chunkX))) return false; // (4)
    seed = next(seed);
    if (!((seed >> 17) % 24 == getChunkIndexInRegion(chunkZ))) return false;
    return true;
}

假设getChunkIndexInRegion(chunkX)部分确定为20，那么(4)的判断式将变为(seed >> 17) % 24 == 20。只需要循环遍历右移17位并除以24后等于20的数值即可。

表达种子的位结构如下。

——– ——– 00000000 00000000 00000000 0000000? ???????? ????????

在这里，“ここで”被随机的规则忽略的部分（不影响村庄的布局），“?”被右移17位后丢弃的部分（会影响村庄的布局，但不会影响初始村庄的区块X）。为了固定初始村庄的区块X，只需要将剩下的0部分除以24后的余数为特定的值即可。同时，“?”的部分可以是任何值，为了产生17位的自由度，在内部进行循环处理。以下是将其转化为代码的结果。

int chunkX1 = 20;
int chunkZ1 = 20;

for (long j = getChunkIndexInRegion(chunkX1); j <= 0x7FFFFFFFL; j += 24) {
    for (long i = 0; i <= 0x1FFL; i++) {
        long s = (j << 17) | i; // (5)

    }
}

附加说明：对于 (long i = 0; i <= 0x1FFL; i++) { 这段代码令人费解。有一种观点认为 (long i = 0; i <= 0x1FFFFL; i++) { 才是正确的解释。

chunkX1 和 chunkZ1 是村落坐标列表中第一个村庄的区块坐标。

然而，(5)中的s表示的是(3)时刻的种子，要获得世界的实际种子，需要进行一些计算。将s作为种子，需要按照以下的方式进行。

long seed = s;
seed = prev(seed);
seed = seed ^ 0x5DEECE66DL;
seed -= (long) getRegionIndex(chunkX1) * 341873128712L + (long) getRegionIndex(chunkZ1) * 132897987541L + 10387312L;
seed = seed & 0xFFFFFFFFFFFFL;

通过循环这个种子，一个在特定地区的某个X坐标上生成村庄的世界，能够得到循环次数为2^48/24次。由于计算大约在两天内完成，因此可以说是足够现实。在实验中，我们研究了8个村庄的坐标，并使用了性能较差的GPGPU，在约27小时内完成了计算，将下48位的模式缩小到了大约250个候选项。

筛选候选项的中速函数，将其缩小为数个选项。

预先了解

在这个函数中，通过f1将下48位约缩小到大约1000个候选项，然后确定其中1个特定项。

由于在实验中调查了8个村庄，因此预计应该有24^(2*8)的筛选能力（相当于73位），但实际上产生了大约250个候选人。因此，是否可以通过f1推断到一个人仍然存疑。可能存在多个下48位模式对应一个配置的情况。

f2的目的是为了确定下位48位的模式，它似乎有这样的能力。如果在f3上花费数百倍的时间，那就不需要f2了，但由于f3相当重，我们希望节约使用它。

战略的意思是计划或者行动，旨在达到长期目标。

这里我们仍然使用村庄，但这一次不再关注布局，而是关注结构。

    • Minecraft 1.12.2　村の座標決定部分のアルゴリズム – Qiita https://qiita.com/MirrgieRiana/items/0a3baee86bb661dc5f99

Minecraft 1.12.2　村建物一覧 – Qiita https://qiita.com/MirrgieRiana/items/b5d56b4d78c503ddb7a0

这个村庄由除了井房、路道、和街头之外的部分，以及房屋、农田、教堂等建筑部分构成。在这里，我们重点关注可以通过目视辨识的建筑物数量。

例如，下一个村庄由以下建筑构成。

2018-09-22_22.03.33.png
    • House1　本棚の家　3個

 

    • House2　鍛冶場　2個

 

    • House3　ダンスホール　1個

 

    • House4Garden　キューブ　6個

 

    • WoodHut　便所　5個

 

    • Hall　庭の家　3個

 

    • Church　教会　2個

 

    • Field1　ダブル畑　2個

 

    Field2　シングル畑　4個

我们决定用下面的方式来表示这个例子的哈希值为0x422356123L。使用建筑物数量来表示村庄的结构，我们可以通过使用==运算符来判断大致是否具有相同的形状，这样问题就变得简单了。另外，由于可以通过目视确认信息并进行简单的计算，因此使用村庄建筑物数量进行表示可以方便地进行信息收集。即使通过对1个或2个村庄进行调查，这种表示方式仍具有将种子的低48位的模式从1000个缩小到1个的性能。

由于这个村庄的生成区块坐标是-16，-18，因此可以说：“种子1251341在区块坐标-16，-18生成了一个名为0x422356123L的村庄”。

生成决定村庄结构的随机数在MapGenBase#generate中生成，稍作修改后在MapGenStructure#recursiveGenerate中使用，并在MapGenVillage.Start#new中调用。将其转化为代码的话，大致如下所示。

World worldIn = どこかから与えられたワールドインスタンス;
int size = 1;

Random rand = new Random(getSeedInChunk(1251341, -16, -18));
rand.nextInt();
new MapGenVillage.Start(worldIn, rand, -16, -18, size);

/**
 * ワールドのシードと村のチャンク座標を与えると村構造用のシードを返す関数
 */
long getSeedInChunk(long seed, long chunkX, long chunkZ)
{
    Random rand = new Random(seed);
    long j = rand.nextLong();
    long k = rand.nextLong();
    (chunkX * j) ^ (chunkZ * k) ^ seed;
}

MapGenVillage.Start#new函数接受World、基准区块坐标和村庄尺寸作为参数。村庄尺寸默认为1。

村庄的结构取决于世界的种子和生成的区块坐标。从外观上看，与下界要塞不同，似乎没有重复的模式。

    Minecraft 1.12.2　ネザー要塞のスポーン座標決定のアルゴリズム – Qiita https://qiita.com/MirrgieRiana/items/e01a3db6fd7bf183fbbb

进行中MapGenVillage.Start#new内的模拟并计算村庄结构的哈希值，但是这个构造函数大体上如下。

List<structurecomponent> components = new ArrayList<>();

MapGenVillage.Start(World worldIn, Random rand, int x, int z, int size)
{
    List<PieceWeight> list = 建物の種類と重みと個数上限の組の一覧を得るメソッド();
    StructureVillagePieces.Start start = new StructureVillagePieces.Start(
        worldIn.getBiomeProvider(), 0, rand, (x << 4) + 2, (z << 4) + 2, list, size);
    components.add(start); // (7)
    start.buildComponent(start, components, rand); // (8)
    List<StructureComponent> list1 = start.pendingRoads;
    List<StructureComponent> list2 = start.pendingHouses;

    while (!list1.isEmpty() || !list2.isEmpty()) { // (9)
        if (list1.isEmpty()) {
            int i = rand.nextInt(list2.size());
            StructureComponent structurecomponent = list2.remove(i);
            structurecomponent.buildComponent(start, components, rand);
        } else {
            int j = rand.nextInt(list1.size());
            StructureComponent structurecomponent2 = list1.remove(j);
            structurecomponent2.buildComponent(start, components, rand);
        }
    }

    // (6)
}

(6)时，组件(components)中包含了构成村庄的部件列表。StructureVillagePieces.Start#new似乎表示了最初的水井，然后在(7)中将其添加到components中。(8)似乎使用buildComponent生成了从水井衍生出的4条道路。然后在(9)中，不断将生成的结构物派生并添加到components中。最终，在(6)处完成。实际上，此后还会继续进行处理，但由于计算哈希值时不使用，可以忽略不计。

如果编写一段代码，在(6)附近搜索components的内容并计算建筑物数量，然后返回哈希值，就可以得到一个函数，通过Random和区块坐标来返回在那里生成的村庄的结构。然而，由于依赖于需要进行Minecraft初始化处理的World，所以该函数无法放置在main函数中。这个函数可以从Minecraft内的可以获得World的代码中调用。例如，可以编写用于覆盖箭矢右击处理并调用该函数的代码。

通过这次讨论，我们成功地创建了一个函数，它可以根据给定的种子和区块坐标返回一个村庄结构的哈希值。只需将其改写为”一个种子是否会生成一个具有特定哈希值的村庄在某个区块坐标上？”的条件，f2函数就完成了。结果是，种子的前16位仍未确定，而后48位已经确定。我们只需检查最多1或2个村庄即可。计算时间仅需几秒钟，单线程即可完成。

将f3函数缩小到仅有一个备选项的低速函数。

在这里，我们从65536种16位Seed候选中筛选出一种Seed。这是通过使用生物群系来实现的。其条件是“这个Seed是否在特定的XZ坐标上生成特定的生物群系？”

村庄似乎忽略了高位的16位，但生物群系却仔细查看。虽然我不知道生物群系选取的算法是什么，但通过从World中获取的WorldInfo，可以通过BiomeProvider提供的getBiome方法来了解坐标所属的生物群系，这已经足够了。

在这里的问题是如何将种子传递给BiomeProvider，只需要一种选择：通过修改BiomeProvider的构造函数，传递存储在WorldInfo私有字段randomSeed中的值。然而，由于randomSeed是私有的，所以需要将其改为公共的。

只需一个选项，将以下内容以汉语进行本地化改写：
在不正确启动Minecraft的情况下自行初始化并生成世界时，似乎会产生略有不同的地形，并且无法成功。因此，为了在这个过程中需要World，可以修改右键点击处理时的时钟物品之类的功能，从而在其中调用这个函数。

在这个过程中，必须仔细制作坐标和生物群系的列表。由于地形勘测是人工的，所以总会存在一些不确定性，因此最好在生物群系的中心获取坐标。此外，不是一次性提交10个，而是逐步进行确认，列举出至少匹配8个以上的选项并进行排序，然后继续工作。

通过在实验中走遍十个生物圈并记录下中央附近的坐标，将这些坐标作为参数传入函数中，成功地从65536种模式中确定了一种模式。确定这个模式需要几分钟的计算时间。

透过整体的处理，我们能够利用8个村座标、1个村结构哈希值和10个生物群系来确定一个64位范围的种子。在我环境下，需耗时约27小时完成此过程。

总结

Minecraft 1.12.2 Java版的原始默认地形生成世界，通过仅仅在地表上行走就能够收集到足够的信息来逆推种子。利用这些信息，最多只需两天就能够逆推出种子。此外，如果提供了世界地图和原点位置，即使无需实际登录游戏，也能够完整获取所需信息。

由于当前种子的范围是long（2^64），因此需要2天的计算时间，但如果将种子设为int，则仅需知道4个村庄的坐标即可在大约4秒内完成搜索。由于Object＃hashCode（）的返回值是int，因此当从字符串提供种子时，就会变成这样。

这次攻击对于改变地形生成参数会有一定的效果。但由于世界的种子影响到各个不同的地方，所以即使利用了除了本次使用的部分以外的地方仍然可以逆推。这次决定性的因素是java.util.Random截断了提供的种子值的高16位。一旦对Random输入了种子值，世界上只存在2^48种不同的模式。在这个点上，如果有50天的时间，就可以进行完全的探索，只需要在多台计算机上进行计算就可以很容易地完成。

在当前情况下，即使我们对服务器的安全性格外重视，但从理论上讲，在满足所有逆算条件的世界中，种子还是有可能会泄露的。

✖
广告
将在 10 秒后关闭
bannerAds