Go to Qiita Advent Calendar 2024 Top
LoginSignup
23
18

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@MirrgieRiana(Riana Mirrgie)

Minecraft 1.12.2　世界地図からのワールドのシードの逆算

Last updated at Posted at 2018-09-22

環境

  • Minecraft 1.12.2 Java Edition

背景

Minecraftのマルチプレイにおいてシード値が開示されるとどうなるのか。簡単に思いつくだけでも次のことができる。

  • 採掘場付近のすべてのダイヤ鉱石の座標を列挙
  • 世界中のすべての村とネザー要塞の座標とチェストの中身を特定
  • レアバイオームの特定
  • エンチャント金りんごの最短入手経路の特定
  • ワールドのクローンを使ったクリエイティブでの実験
  • サーバーで認可されていないMODの使用による地形の調査
  • 特定の種類のスポーナーの検索
  • MODが入っている場合、MOD由来のレア構造物の検索
  • レアバイオームの検索

これはクライアントにMODを入れる必要はないので、サーバーのルールレベルでクライアントのバージョン・MOD・非改造を規定しても対策ができない。

クライアントMOD制限あり・シード非公開のサーバーで特定の1プレイヤーだけがシードを知っている状況でそのプレイヤーがシードを活用した場合、ダイヤ鉱石の座標特定だけでも相当なバランス破壊となってしまう。

そこで、マルチの非鯖缶プレイヤーがサーバーをクラックすることなく正規の手段で手に入る情報だけを使ってシードを探すことができるかを考えた。これが可能なら、いくらサーバー管理者がシードを非公開にしても物理的に知ることが可能なので行動の監視やローカルルールなどで別途対策しなければならないことになる。

ルール

いくつかのForge MODが入れられた、バニラと同じ地形を生成するMinecraft 1.12.2 Java Editionのサーバーが建っていたときに、ワールドのシードを知る。

条件

前提

  • ワールドの地形生成のコンフィグはデフォルトから一切弄っていない
  • シード値はlongの範囲でランダムである
  • 計算にはせいぜい数日程度しかかかってはならない
  • 個人用の一般的なパソコンで計算できなくてはならない

禁止

  • ワールドには正規の手段でしか接続してはならない
  • サーバーのルールにより認められていないMODは使えない
  • 改造したクライアントやMODを使ってワールドに接続してはならない
  • サーバーにはMinecraftからしかアクセスしてはならない

可能

  • オーバーワールドの地表を自由に探検することができる
  • F3による座標表示が利用できる
  • F3によるバイオーム表示が利用できる
  • 見た情報をスクリーンショットなどで自由に記録できる

戦略

根本的な戦略は「あるシードが特定の地形を生成するかどうかを可能なすべてのシード候補について試す」を使う。しかしそのままでは2^64通りのシードが考えられるため、判定部分をかなり高速化しても普通の個人所有のPCでは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)は現状ではループ回数が多すぎて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　候補を大まかに絞り込む高速な関数

f1はとにかく早さが求められるので、GPGPUで扱える関数にしようと思う。そのためには次のようないくらかの条件を満たさなければならない。

  • Minecraftの実行中のインスタンスを利用しない
  • JREのライブラリに依存しない

例えばx -> x + 700 == 4は単純なので大丈夫。x -> Math.sin(x * 0.001) == 1はMath.sinをどうにかする必要がある。x -> world.getBiome(new BlockPos(x, 65, 0)) == Biome.FORESTは不可能である。

GPGPUにはAparapiを使う。

GPUにはこれを使った。

もっといいGPUを使うともっと短縮できる余地がある。

ここではf1に村の生成位置を用いる。

村の生成座標を使うと次の手順で候補を大まかに絞り込むことができる。

  • 村を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の内部処理については次を参照。

この関数はJREにもMinecraftのインスタンスにも依存していないのでAparapiから利用可能である。

以下ではdistanceがデフォルトの32固定であるとして話を進める。すると地域の中での村の生成座標は座標軸1個あたり24通りになる。

上の関数を調査した村の個数分だけ呼び出すと、シードを大まかに絞ることができる。

しかし、Randomの上位16ビット切り捨てのためにこの関数では原理的にいくら村を調査してもシードの候補を1個まで絞ることはできない。なので、次のようにして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通りが1万年かかるとすると、単純計算で2^48≒2.8E+14通りでは50日くらいで済む。その後の65536000≒6.5E+7通りからの絞り込みはそれに比べて遥かに少ない。

(1)　ループ部分の最適化

計算回数を50日程度まで短縮できたが、これでもまだ計算可能とは言い難い。しかし実はこれを1/24にする単純な手法が存在する。それには上で挙げた村生成のアルゴリズムとRandomの仕様を利用する。村の生成座標は村1個で1/(24*24)の絞り込み性能があり、座標の片側だけでも1/24はある。下記のコードはtestとtest2をまとめたものである。ここで、(3)時点でのseedはある程度予測することができる。

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? ???????? ????????

ここで-はRandomの仕様により無視される部分（村の配置に影響しない）、?は右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)
        
    }
}

追記： for (long i = 0; i <= 0x1FFL; i++) { は謎。 for (long i = 0; i <= 0x1FFFFL; i++) { が正しい説がある。

chunkX1・chunkZ1は村座標リストの最初の村のチャンク座標である。

ただし(5)にあるsは(3)時点でのseedを表しているので、ワールドのシードそのものを得るには少し計算しなければならない。sをseedにするには以下のようにする。

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回になる。だいたい2日で終わる計算なので十分現実的といえよう。実験では村8個分の座標を調査し、（しょぼい性能の）GPGPUを使って約27時間で計算が完了し、下位48ビットのパターンを250個程度の候補に絞ることができた。

f2　候補を数個に絞り込む中速な関数

前知識

この関数ではf1によって下位48ビットの中を約1000個程度まで候補が絞ったものを1個まで特定する。

実験では村を8個調査したので24^(2*8)の絞り込み性能（73ビット分）があるはずであるが、実際には候補が250個程度生まれてしまった。そのためf1で1個まで特定できるかは疑問である。多数の下位48ビットのパターンが一つの配置に対応してしまっていると考えられる。

f2は下位48ビットのパターンを1個に特定するために行う。f2にはそこまでの能力があるようだ。f3で数百倍の時間をかければf2はなくてよいが、f3は結構重いため節約していきたい。

戦略

ここでも村を使うが、今度は配置ではなく構造に注目する。

村は井戸・道路・街頭といった建物以外のパーツと、家・畑・教会といった建物なパーツで構成されている。ここでは目視でわかりやすい建物の個数に注目する。

例えば次の村は以下の建物で構成されている。

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である。

村の構造はワールドのシードと生成されるチャンク座標に依存して決まる。見た感じネザー要塞と違ってパターンのループはなさそうである。

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の中身を捜査して建物を数え上げてハッシュ値を作るコードを書いてreturnすればRandomとチャンク座標からそこに生成される村の構造を返す関数の出来上がりである。ただし、Minecraftの初期化処理を要求するWorldに依存するのでこの関数はmainに置くことはできない。この関数はWorldが入手可能なMinecraft内のコードから呼び出すことができる。例えば矢の右クリック処理を上書きしてこの関数を呼び出すコードを作れる。

ここまでの議論によって、「シードとチャンク座標を与えると村構造のハッシュ値を返す関数」ができた。これを「あるシードはあるチャンク座標にあるハッシュ値を持つ村を生成するか？」という条件に書き換えればf2は完成である。この結果、シードは上位16ビットが不明で下位48ビットが確定したところまでたどり着く。これにはせいぜい1個か2個の村を調査すればよい。計算時間はシングルスレッドで数秒である。

f3　候補を1個に絞り込む低速な関数

ここではシードの候補を上位16ビット分の65536パターンから1パターンに絞り込む。それにはバイオームを利用する。「そのシードは特定のXZ座標に特定のバイオームを生成するか？」という条件式である。

村は上位16ビットを無視するが、バイオームはちゃんと見るらしい。バイオーム決定のアルゴリズムは知らないが、Worldから得られるWorldInfoから導けるBiomeProviderが提供するgetBiomeで座標のバイオームが分かるので十分である。

ここで問題なのがどうやってBiomeProviderにシードを渡すかであるが、それにはBiomeProviderのコンストラクタに渡すWorldInfoがprivateで格納しているrandomSeedフィールドを書き換えればよい。ただしrandomSeedはprivateになっているため、publicに書き換える必要がある。

この過程もWorldを要求する。Minecraftを正しく起動せずに自前でMinecraftを初期化してWorldを生成すると、若干異なる地形が生成されるらしく成功しなかった。なので、この関数も時計アイテムかなんかの右クリック処理を改変してその中で呼び出すようにする。

この過程に渡す座標とバイオームのリストは慎重に作らなければならない。地形の調査は人力となるのでどうしても不安が残るので、座標はできればバイオームの真ん中で取りたい。さらに10個渡したら10個すべてマッチするようにするのではなく、8個以上マッチしたものを列挙してソートするなどの逐次的な確認を行いながら作業を進めたい。

この過程には実験ではバイオームを10個歩いて中央付近の座標をメモし関数に流し込むことで65536パターンから1パターンまで特定することに成功した。特定には数分の計算時間が必要である。

全体を通して、村8個分の座標、村1個の構造ハッシュ値、10点のバイオームを使って64ビット範囲のシードを1個に特定することができた。これには筆者の環境で約27時間を要した。

まとめ

**Minecraft 1.12.2 Java Editionのバニラのデフォルトの地形生成のワールドは、地表を歩き回るだけでシードを逆算できるほどの情報を集めることができる。そしてその情報を使って高々2日でシードを逆算することができる。**さらに実際にログインせずとも世界地図と原点の位置が与えられればそれだけで情報は揃ってしまう。

今回はシードがlongの範囲（2^64）であることを想定したため2日の計算時間を要したが、シードをintにしていた場合は村4個分の座標が分かれば4秒程度で探索が終了する。Object#hashCode()はintの戻り値であるため、文字列からシードを与えるとこうなってしまう。

この攻撃に対しては地形の生成パラメータを少し変えることは有効である。しかしワールドのシードは様々なところに影響しているため、今回利用した箇所以外の部分を利用して依然として逆算が可能であろう。今回決定打となったのはjava.util.Randomが与えたシード値の上位16ビットを切り捨てている事実である。Randomにシード値を入れた瞬間に世界は2^48個のパターンしか存在しなくなる。この時点で既に50日あれば全探索可能なので、複数台のコンピュータで計算すれば簡単に終わってしまう。

現状、逆算の条件を既に満たしているワールドではどんなにサーバーのセキュリティに気を配っても理論上シードがだだもれであるということになる。

23
18
29

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
23
18

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?