Minecraft(我的世界)中文论坛

 找回密码
 注册(register)
查看: 5655|回复: 94

[技巧] 地图种子的逆向研究(2)——结构与群系分布

[复制链接]
发表于 2018-6-28 21:15:40 | 显示全部楼层 |阅读模式

您尚未登录,立即登录享受更好的浏览体验!

您需要 登录 才可以下载或查看,没有帐号?注册(register)

x
本帖最后由 Vinogradov 于 2018-8-8 23:30 编辑

更新(2018年8月8日)
使用该方法,作者已经成功找出了USTC-Minecraft 9周目(原版1.13)的地图种子。真实性可向该周目玩家及腐竹求证。


原帖:
上一篇中,我们已经说明了通过基岩分布应该是无法逆向得到世界的种子的,原因在于标准分布的存在以及非标准分布对群系的依赖性。
在本文中,我们通过结构的分布与群系的分布成功逆向了一个存档的种子。这种方法具有普适性。注:该攻击方法并非作者,也就是@Vinogradov,即丢人素学姐首次发现。
由于本文内容疑似涉及作弊,我们将不会给出任何代码,并在阐明原理的前提下尽可能地忽略技术细节。
另外,由于写这个贴子的时间和实际完成的时间相差了几个月,所以可能某些地方有细小的错误,不过应该不会影响整体的阅读和技术分析。

约定:
  • 在本文中我们仅考虑了村庄的分布,事实上有一些其他结构的分布也是可以考虑的。
  • 本系列文章中的Minecraft指的都是Minecraft Java Edition, 1.12.2。
  • 本系列文章中引用的代码都来自 forge-1.12.2-14.23.2.2611-mdk。
  • 当我们说”区块(x,z)“时,我们指的是chunk coordinate为(x,z)的区块。
  • 我们将村庄中心所在的区块(也就是村里那口井所在的区块)称之为村庄区块


猴子都知道的常识1:2^64的搜索空间对一般民用计算设备太大了。
猴子都知道的常识2:群系生成非常复杂。


分析:
  • 让我们先看Village的生成判定:以下代码源自\net\minecraft\world\gen\structure\MapGenVillage.java
    1. protected boolean canSpawnStructureAtCoords(int chunkX, int chunkZ)
    2.     {
    3.         int i = chunkX;
    4.         int j = chunkZ;

    5.         if (chunkX < 0)
    6.         {
    7.             chunkX -= this.distance - 1;
    8.         }

    9.         if (chunkZ < 0)
    10.         {
    11.             chunkZ -= this.distance - 1;
    12.         }

    13.         int k = chunkX / this.distance;
    14.         int l = chunkZ / this.distance;
    15.         Random random = this.world.setRandomSeed(k, l, 10387312);//LINE_1
    16.         k = k * this.distance;
    17.         l = l * this.distance;
    18.         k = k + random.nextInt(this.distance - 8);
    19.         l = l + random.nextInt(this.distance - 8);

    20.         if (i == k && j == l)
    21.         {
    22.             boolean flag = this.world.getBiomeProvider().areBiomesViable(i * 16 + 8, j * 16 + 8, 0, VILLAGE_SPAWN_BIOMES);//LINE_2

    23.             if (flag)
    24.             {
    25.                 return true;
    26.             }
    27.         }

    28.         return false;
    29.     }
    复制代码
    其中LINE_1处的this.world.setRandomSeed是一个与世界种子和当前区块位置相关的函数。如果将LINE_2注释掉,那么村庄生成就与群系无关,我们将这样修改过后会生成村庄的区块称之为拟村庄区块。则我们有显然的结论:
    村庄区块必然是拟村庄区块,但反之不对。


  • 为什么我们要考虑拟村庄区块呢?这是因为拟村庄区块的判定直接取决于种子和区块位置(虽然群系分布也依赖于种子,但是我们这里的意思就是拟村庄区块不受群系影响),且它依赖的随机数生成器Java.util.random类不够安全(为什么不直接考虑村庄区块?那是因为生成群系时MC部分使用了自写的随机数生成器)。
  • 通过对java.util.random的代码分析可知,给定种子s后,它生成的随机数列只与s的低48bit有关,虽然s在64bit的整数范围内取值(这里忽略技术细节)。结合上面摘录的代码,我们易知:
    如果a≡b (mod 2^48),那么世界种子a和b所对应的拟村庄区块完全相同。

    这个结论说明了两个问题:一,仅通过村庄位置是无法完全确定世界种子的;二、我们可以将首次爆破的搜索空间减少到2^48。三、上文中我们提到群系生成使用了MC自写的随机数生存器,它使用了世界种子的全部64bit,使得村庄区块相对于拟村庄区块所需搜索空间暴涨了2^16倍,也就是说直接通过村庄区块精确匹配的话,我们需要搜索整个int64范围,更不用说复杂的群系生成方**使单个搜索分支变慢多少了。
  • 具体地说,我们首先通过跑图获得若干村庄区块(从而是拟村庄区块)的区块坐标(x_1,z_1),...,(x_n,...z_n) (这个n取多少读者自行决定,太多就会拖慢搜索速度,太少则会使通过的种子太多)。然后在0~2^48-1范围内搜索在(x_1,z_1),...,(x_n,...z_n) 这些位置是拟村庄区块的种子,得到若干备选项s_1,s_2,...,s_k(可能不止一个)。然后获得世界内某些位置的群系(当然,这种群系越稀少越好),再对每个n,计算以s_n+2^48*r( 1<=r<=2^16)为种子的地图内这些位置的群系是否与给定的群系吻合。通过这样两轮筛选,我们就能获得世界的种子了。



实现与测试(概率)
  • 第一部分爆破拟村庄区块的代码可以直接参考MC代码改写C++代码,第二部分群系判定比较复杂,可以参考某些已有的代码。
  • 在我们的测试中,第一部分使用CUDA技术(自行编写),在GT920M显卡上(满负载),跑完整个2^48范围大约需要41小时(把家里唯一一台电脑的显卡搞坏的话大概会被打死,所以作者并没有真的跑完41小时,而是把任务分成了1024组,通过前几十组的用时估算出了总用时)。第二部分我们没有进行完全的测试(虽然代码已经写好且经过验证是可行的),相信应该非常快。



预防:
几乎不可预防,除非把MC使用的伪随机数生成器给换掉或者改变村庄算法。



参考:



感谢:
  • TheMasterCaver,在帖子中解释了原理,并在MinecraftForum的私信中耐心地回复了我的疑惑。
  • @ustc_zzzz ,我又忘了为啥要感谢他了,,,谢了再说。
  • meow,给了我一些类型转换方面的知识。
  • 我的GT920M,,,你辛苦了,,,





注:通过分析目前我能看到的代码,该攻击方法很有可能在1.13中仍然有效。
====================
使用矿石分布代替群系分布进行第二轮验证在理论上是可以的,但是我没看到能现成给我用的C++版的代码(群系的有人写了),而且目测如果写的话不会比群系简单。


评分

参与人数 11人气 +27 金粒 +71 收起 理由
45gfg9 + 2 神乎其技,不服不行!
哦快快快 + 1 + 11 神乎其技,不服不行!
afjl + 2 数论+搜索?有启发操作吗?
gooding300 + 4 瑟瑟发抖
22b + 2 + 10 神乎其技,不服不行!
我的工业2 + 2 + 10 了解,低头
风扇滑翔翼 + 2 滚上6级
玄素 + 4 + 40 瑟瑟发抖
a6809936 + 2 字略大……
GiNYAi + 2 瑟瑟发抖
ustc_zzzz + 4 瑟瑟发抖

查看全部评分

回复

使用道具 举报

发表于 2018-6-28 21:53:14 | 显示全部楼层
你的群系是怎么获取呢?手动输入吗?

点评

待求种子的那个地图的群系当然是手动输入,然后第一轮筛下来以后那些要继续检查的种子,可以用某工具获得指定位置的群系  详情 回复 发表于 2018-6-28 22:02
回复

使用道具 举报

 楼主| 发表于 2018-6-28 22:02:56 | 显示全部楼层
ruhuasiyu 发表于 2018-6-28 21:53
你的群系是怎么获取呢?手动输入吗?

待求种子的那个地图的群系当然是手动输入,然后第一轮筛下来以后那些要继续检查的种子,可以用某工具获得指定位置的群系

点评

如果能计算例如某位置是否为矿石的话,而待求种子的地图的某位置有矿石的话应该会更加精准一点……  详情 回复 发表于 2018-6-28 22:07
回复

使用道具 举报

发表于 2018-6-28 22:07:39 | 显示全部楼层
Vinogradov 发表于 2018-6-28 22:02
待求种子的那个地图的群系当然是手动输入,然后第一轮筛下来以后那些要继续检查的种子,可以用某工具获得 ...

如果能计算例如某位置是否为矿石的话,而待求种子的地图的某位置有矿石的话应该会更加精准一点……

点评

就像我帖子里说的,地图的很多特征,关于种子都具有唯一性,但问题在于这种唯一性同时也代表了搜索空间的巨大(2^64bit)。爆破这个不太实际和划算,所以问题的关键在于如何适当地把搜索空间变小。在我这里就是引入  详情 回复 发表于 2018-6-28 22:44
回复

使用道具 举报

发表于 2018-6-28 22:25:19 | 显示全部楼层
本帖最后由 风扇滑翔翼 于 2018-6-28 22:29 编辑

用钻石坐标这种稀有方块坐标能不能更方便地反推出种子 #run
或许你可以租一个一天的服务器把这个任务算完(大多数的服务器租用都有个几天的试用期)
顺便说一下 ustc_zzzz这位大佬也是低级就开始肝这些东西

点评

如果专业显卡的话一个小时都不用应该就能算完。 另外关于矿石可不可行的问题,我在给ruhuasiyu的回复里说得比较详细  详情 回复 发表于 2018-6-28 22:45
稀有不代表方便逆向  详情 回复 发表于 2018-6-28 22:31
回复

使用道具 举报

发表于 2018-6-28 22:29:33 | 显示全部楼层
为什么不能给全点呢
我比较喜欢研究种子的那一方面
但论坛迟迟没有相关的文献及解释
为什么非得列入作弊

点评

有技术,能看懂我在说什么的人,应该已经有足够的信息和思路去写出程序了。 在这里我给出代码和更多技术细节只能满足伸手党。 更况且很多服务器的种子是不公开的,如果用这种方法获得了服务器的种子从而获得服务器资  详情 回复 发表于 2018-6-29 05:44
回复

使用道具 举报

 楼主| 发表于 2018-6-28 22:31:09 | 显示全部楼层
风扇滑翔翼 发表于 2018-6-28 22:25
用钻石坐标这种稀有方块坐标能不能更方便地反推出种子 #run
或许你可以租一个一天的服务器把这个任务算完( ...

稀有不代表方便逆向
回复

使用道具 举报

 楼主| 发表于 2018-6-28 22:44:24 | 显示全部楼层
ruhuasiyu 发表于 2018-6-28 22:07
如果能计算例如某位置是否为矿石的话,而待求种子的地图的某位置有矿石的话应该会更加精准一点…… ...

就像我帖子里说的,地图的很多特征,关于种子都具有唯一性,但问题在于这种唯一性同时也代表了搜索空间的巨大(2^64bit)。爆破这个不太实际和划算,所以问题的关键在于如何适当地把搜索空间变小。在我这里就是引入了所谓的拟村庄区块,适当放宽匹配精度,使得第一轮搜索空间变成2^48。

总之,暴力穷举谁都想得出来,但是要真的在可接受的时间内算出来不是那么随意的。

我没仔细看过矿石的代码,不过我估计应该不比直接拿群系简单,而直接拿群系也已经是远远超过可接受范围了。

点评

我说的是你验证种子那一步,不是暴力破解那步……  详情 回复 发表于 2018-6-28 23:13
回复

使用道具 举报

 楼主| 发表于 2018-6-28 22:45:48 | 显示全部楼层
风扇滑翔翼 发表于 2018-6-28 22:25
用钻石坐标这种稀有方块坐标能不能更方便地反推出种子 #run
或许你可以租一个一天的服务器把这个任务算完( ...

如果专业显卡的话一个小时都不用应该就能算完。

另外关于矿石可不可行的问题,我在给ruhuasiyu的回复里说得比较详细
回复

使用道具 举报

发表于 2018-6-28 23:13:07 | 显示全部楼层
Vinogradov 发表于 2018-6-28 22:44
就像我帖子里说的,地图的很多特征,关于种子都具有唯一性,但问题在于这种唯一性同时也代表了搜索空间的 ...

我说的是你验证种子那一步,不是暴力破解那步……

点评

没看过矿石的代码不清楚。第二步我用群系的原因是已经有人把群系生成的代码改写成C++并封装好了(虽然写得很烂),我要做的就是调用他的代码,然后改写一点点,比较方便。矿石的话这人没做,我估计应该是基于群系的  详情 回复 发表于 2018-6-29 05:35
回复

使用道具 举报

 楼主| 发表于 2018-6-29 05:35:34 | 显示全部楼层
ruhuasiyu 发表于 2018-6-28 23:13
我说的是你验证种子那一步,不是暴力破解那步……

没看过矿石的代码不清楚。第二步我用群系的原因是已经有人把群系生成的代码改写成C++并封装好了(虽然写得很烂),我要做的就是调用他的代码,然后改写一点点,比较方便。矿石的话这人没做,我估计应该是基于群系的,会很麻烦,所以想法很好,但实现起来有点麻烦大概。回头我再翻翻代码。
回复

使用道具 举报

 楼主| 发表于 2018-6-29 05:44:35 | 显示全部楼层
彩狗dalao 发表于 2018-6-28 22:29
为什么不能给全点呢
我比较喜欢研究种子的那一方面
但论坛迟迟没有相关的文献及解释

有技术,能看懂我在说什么的人,应该已经有足够的信息和思路去写出程序了。
在这里我给出代码和更多技术细节只能满足伸手党。
更况且很多服务器的种子是不公开的,如果用这种方法获得了服务器的种子从而获得服务器资源,在某种程度上就是利用BUG作弊。

点评

这....都可以写程序还需要你说呢,人家不会自己拆了他的源代码嘛  详情 回复 发表于 2018-8-23 01:59
有这个雅兴跑完这个任务 在按坐标去挖矿 还不如拿起稿子挖挖矿 不知用末地门逆推会不会更方便  详情 回复 发表于 2018-6-29 23:04
回复

使用道具 举报

发表于 2018-6-29 23:04:46 | 显示全部楼层
本帖最后由 风扇滑翔翼 于 2018-6-29 23:05 编辑
Vinogradov 发表于 2018-6-29 05:44
有技术,能看懂我在说什么的人,应该已经有足够的信息和思路去写出程序了。
在这里我给出代码和更多技术 ...


有这个雅兴跑完这个任务 在按坐标去挖矿 还不如拿起稿子挖挖矿
不知用末地门逆推会不会更方便
hide代码是个好东西 未满7级也可以找版主申请

点评

看不懂。不过说真的,我还不如用truckbase那个网站或locate指令来找想要的地形,更快更准  详情 回复 发表于 2018-8-7 20:52
回复

使用道具 举报

发表于 2018-7-8 16:15:54 | 显示全部楼层
也就是能通过方块位置推算出地图种子。

点评

严格地说是通过结构+群系。虽然最终还是要用方块,但本质上不太一样  详情 回复 发表于 2018-7-8 16:41
回复

使用道具 举报

 楼主| 发表于 2018-7-8 16:41:37 | 显示全部楼层
77882243344 发表于 2018-7-8 16:15
也就是能通过方块位置推算出地图种子。

严格地说是通过结构+群系。虽然最终还是要用方块,但本质上不太一样
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册(register)

本版积分规则

Archiver|小黑屋|Mcbbs.net ( 京ICP备15023768号-1 ) | 手机版本

GMT+8, 2018-9-21 05:08 , Processed in 0.131140 second(s), 8 queries , Memcache On.

"Minecraft"以及"我的世界"为Mojang Synergies AB的商标。本站与Mojang以及微软公司没有从属关系。

© 2010-2017 我的世界中文论坛 版权所有。本站原创图文内容版权属于原创作者,未经许可不得转载。

快速回复 返回顶部 返回列表