Minecraft 버전 베타 1.8~1.12.2에서 블록이 깨질 때마다 떨어진 아이템의 정확한 좌표를 통해 다른 플레이어의 위치가 드러날 수 있습니다.
"Randar"는 LLL 격자 감소를 사용하여 Minecraft 서버에서 잘못 재사용된 java.util.Random 의 내부 상태를 해독한 다음, 그로부터 거꾸로 작업하여 현재 세계에 로드된 다른 플레이어를 찾는 Minecraft용 익스플로잇입니다.
대신 YouTube 동영상 형식으로 Randar에 대해 알아보려면 여기를 클릭하세요.
타임랩스 보기:
여기(파일) 또는 여기(YouTube)에서 더 많은 타임랩스를 확인하세요.
목표는 세계에 있는 다른 플레이어가 얼마나 멀리 떨어져 있는지에 관계없이 게임 내 위치(예: 좌표)를 결정하는 것입니다. 우리는 가장 오래되고 가장 유명한 "무정부" Minecraft 서버인 2b2t에서 플레이하고 있습니다(즉, 규칙이 없음을 의미합니다. 즉, 플레이어는 어떤 이유로든 금지되지 않습니다). 이와 같은 작업을 수행하는 것이 이 서버의 "핵심"입니다. 이 서버에서 귀하의 물건을 안전하게 지키는 유일한 방법은 지도가 거대하고(3600조 평방 타일) 다른 누구도 귀하가 어디에 있는지 모른다는 것입니다. 따라서 좌표적 익스플로잇을 갖는 것은 엄청난 일(게임을 깨는 거래)입니다. (말하자면, Randar 이전에 우리는 2018년부터 2021년까지 2b2t인 Nocom에 대한 또 다른 공동 익스플로잇도 있었습니다. 여기에서 해당 글을 참조하세요, HackerNews 스레드, YT)
Minecraft 코드의 실수 는 베타 1.8(2011년 출시)부터 1.12.2(2017년 출시, 2b2t는 2023년 8월 14일까지 이 버전에 유지됨)까지 존재합니다. 실수는 난수 생성기 java.util.Random 의 다양한 인스턴스가 코드의 다양한 부분에서 엉성하게 재사용된다는 것입니다(그리고 처음부터 안전하지 않습니다). 특히, 지형 생성과 블록 채굴과 같은 게임 작업 사이에 RNG가 재사용됩니다.
익스플로잇은 다음과 같이 요약됩니다.
World.rand 근처의 Woodland Mansion이 있어야 하는 위치(그리고 특히 이 청크인지 여부)를 확인하기 위해 청크 좌표의 함수로 시드를 재설정합니다.World.rand.nextFloat() 호출에 의해 결정된 채굴된 블록 내의 "임의" 좌표에 나타납니다. 봇은 타임스탬프와 정확한 XYZ 값을 기록합니다.World.rand 의 정확한 내부 상태를 확인할 수 있습니다. 광범위하게 말하면(자세한 내용은 나중에 설명하겠습니다) RNG의 출력 하나를 관찰하면 RNG의 약 1,600만 가지 가능한 내부 상태 중 하나를 의미할 수 있습니다. 그러나 우리는 RNG의 출력을 한 번이 아니라 연속으로 세 번(드롭된 항목의 X, Y, Z 좌표) 샘플링했으며, 각 호출 사이에서 내부 상태가 어떻게 업데이트되는지(단순 곱하기) 알고 있습니다. , 추가, 수정 후); 그러므로 우리는 격자 방법을 사용하여 본질적으로 즉시 유일한 가능성으로 범위를 좁힐 수 있습니다.java.util.Random 의 내부 상태는 앞으로 가는 것처럼 쉽게 뒤로 이동할 수 있으며, 뒤로 이동하면 단 몇 천 단계만으로 찾을 수 있습니다(2b2t와 같이 많은 플레이어가 있어 무거운 서버에서도 마찬가지). RNG의 내부 상태가 재설정된 가장 최근 시간과 서버에 로드된 가장 최근 청크의 위치를 식별합니다.최신 버전의 Minecraft로 업데이트했거나 RNG 조작 패치를 적용한 서버에서 플레이하는 경우에도 RNG 데이터를 소급하여 활용하는 기능으로 인해 좌표는 여전히 Randar의 위험에 노출되어 있습니다. 일부 Minecraft 플레이어는 패킷을 기록하는 ReplayMod와 같은 모드를 사용하며 해당 로그 파일이 여전히 남아 있을 수 있습니다. 당신이 기지에 있는 동안 누군가 그러한 모드를 사용하고 있었다면, 그들은 (무의식적으로) 당신의 위치를 드러낼 수 있는 RNG 데이터를 기록했을 수도 있습니다. 왜냐하면 블록을 부수는 것은 그러한 기록에서 일어날 가능성이 있는 매우 일반적인 행동이기 때문입니다. break는 서버의 RNG 상태와 가장 최근에 로드된 청크의 위치를 표시합니다. 이는 Randar가 꽤 큰 문제라는 것을 의미합니다. 모든 Minecraft 서버에서 소급하여 악용할 위험이 있으므로 베타 1.8부터 1.12.2 버전까지 활성화된 모든 위치는 서버가 1.12 이후로 업데이트된 지 오래 되었더라도 손상된 것으로 간주되어야 합니다. .2 또는 패치된 RNG 조작.
Randar 공격을 직접 사용하려면 rebane2001이 1.12.2에서 ReplayMod 파일을 끌어서 다른 플레이어의 좌표를 볼 수 있는 웹사이트를 만든 여기로 이동하세요. 클라이언트 측에서 실행되므로 녹음 내용이 브라우저를 벗어나지 않습니다. 다음은 해당 웹사이트의 실제 모습을 보여주는 비디오입니다. 여기서 다운로드하여 해당 비디오에서 예제 ReplayMod 파일을 실행할 수 있습니다.
Randar는 n0pf0x(pcm1k)에 의해 발견되었습니다. 이 글은 lejurv가 작성했으며 마지막에는 n0pf0x가 작성한 몇 가지 추가 설명이 있습니다. 공격자는 0x22, Babbaj, TheLampGod, lejurv, Negative_Entropy 및 rebane2001이었습니다. 여기에서 TheLampGod의 비디오를 확인하세요. 여기에서 HermeticLock의 100% 유머러스하고 0% 사실적인 동영상을 확인하세요.
목차: 악용 가능한 코드에 대해 자세히 알아보려면 여기를 클릭하고, 격자 축소가 사용된 방법에 대해 알아보려면 여기를 클릭하고, Randar로부터 우리의 은닉물을 어떻게 보호했는지 알아보려면 여기를 클릭하고, 전체 악용 코드를 보려면 여기를 클릭하세요. 아직 베타 1.8과 1.12.2 사이의 버전인 서버를 실행하고 Randar를 패치하고 싶다면 여기를 클릭하세요. n0pf0x가 우리와 다르게 수행한 작업에 대한 자세한 내용은 여기를 참조하세요.
실수 다이어그램(PDF):
익스플로잇 다이어그램(PDF):
익스플로잇의 실제 예제 다이어그램(PDF):
Minecraft는 게임 전반에 걸쳐 난수를 사용합니다. 대부분은 몹 생성 및 날씨에 사용되는 무작위성과 같이 실제로 무작위일 것으로 예상하지만 일부는 예측 가능하다고 기대합니다. 예를 들어 동일한 위치에 있는 동일한 월드 시드가 동일한 지형을 생성할 것으로 기대합니다. 2011년, Notch는 베타 1.8에서 처음으로 게임에 구조를 추가했을 때 마을을 세계에 배치하기 위해 예측할 수 없는 RNG를 실수로 재사용했습니다. 그 이후로 1.13까지 이 엉성한 코드로 인해 세계 생성이 게임의 거의 모든 무작위 이벤트에 영향을 미쳤습니다. Earthcomputer와 친구들이 이 실수를 발견하고 청크 로드가 관찰 가능한 방식으로 게임의 RNG에 영향을 미친다는 것을 깨닫는 데는 2018년 5월쯤이 걸렸습니다. 이 설명을 참조하세요. 그러나 그들은 이 작업을 거꾸로 수행하여 RNG를 관찰하여 가장 최근에 로드된 청크를 결정할 수도 있다는 사실을 인식하지 못했거나 공개적으로 공개하지 않았습니다. Randar는 2022년 10월 7일 n0pf0x(일명 pcm1k)에 의해 발견되었습니다. 그는 당시 발견했음을 증명하기 위해 약 2주 후에 Pastebin에 익스플로잇에 대한 짧고 암호화된 설명을 게시했습니다. 그는 주로 9b9t에서 익스플로잇을 사용했으며 2b2t 및 기타 서버에서는 상대적으로 적은 양만 사용했습니다. 2b2t에서 n0p는 다양한 위치를 찾아 탐색하고 결국 Gringotts 보관소 위치에 도달했습니다. 그는 rebane2001에 의해 발견되었으며 처음에는 위치를 어떻게 찾았는지에 대해 침묵했습니다. 그러나 약 한 달 후 그는 SpawnMasons와 이에 대해 대화를 시작했습니다. n0p는 자신이 강력한 좌표 익스플로잇을 사용했다고 밝혔으며 2023년 4월에 우리와 설명을 공유하기로 결정했습니다. 왜냐하면 메이슨들은 과거에 더 큰 규모로 2b2t 익스플로잇을 활용한 경험이 있기 때문에 그런 일이 다시 일어나는 것을 보는 것이 재미있을 것이고 n0p는 어쨌든 약간 지루해집니다. 우리는 관련 없는 프로젝트를 위해 이미 연중무휴로 돌/조약돌을 채굴하고 있는 여러 계정에서 아이템 드롭 좌표를 수락하고 기록하기 시작했습니다(따라서 동작에는 변화가 없었습니다). 우리는 nocom의 헤드리스 Minecraft 시스템을 재사용하고 Postgres 데이터베이스를 추가하여 측정값을 기록했습니다. 이 Readme의 뒷부분에서 논의된 것처럼 우리는 RNG 측정을 해독하기 위해 여러 번의 소프트웨어 반복을 거쳐 결국 비동기 Cuda 배치 작업에 정착했습니다. 균열된 측정값이 데이터베이스에 추가됨에 따라 우리는 전체 시간, 매일, 매시간 간격으로 각 좌표에서 적중을 계산하는 히트맵 정보로 분석 테이블도 업데이트했습니다. 이를 통해 간단한 Plotly Dash UI가 브라우저에 표시하기 위해 특정 시간 범위 및 세분성에서 히트맵 데이터를 선택할 수 있었고, 몇 시간 이상 로드된 좌표만 고려하여 Elytra 스태시헌팅 청크 로드 스팸을 모두 제거할 수 있었습니다. 지도의 각 핫스팟에서 찾은 내용을 추적하기 위해 간단한 공유 주석 시스템을 추가했습니다. 다시 Nocom을 재사용하여 아이템 보관함을 훔치고 결과를 정렬하는 전체 프로세스를 완전히 AFK로 자동화하는 Baritone 봇이 있습니다. 많은 메이슨들이 익스플로잇을 알지 못한 채 munmap 및 1248_test_user 와 같은 계정을 사용하여 이 부분을 도왔습니다. Gringotts의 모든 보관함은 결국 13억 개의 항목으로 늘어났으며, 그 중 약 절반은 Nocom에, 나머지 절반은 Randar에 귀속되었습니다.
전체 내역은 FitMC 영상에 설명되어 있습니다.
Minecraft의 지도는 절차적으로 생성되며 기본적으로 세계의 초기 시드를 기반으로 결정적입니다. 플레이어가 지도를 탐색하면서 플레이어가 가까이 다가가면 필요에 따라 새로운 영역이 생성됩니다. 모든 세대는 반복 가능(결정적)을 의미하므로 여러 곳에서 java.util.Random 사용하는 것이 합리적입니다. 그들은 그것이 예측 가능하기를 원합니다 . 이것이 PRNG(실제로는 RNG가 아님)이기 때문에 java.util.Random 이 사용되는 이유입니다. P는 기술적으로 "유사"를 의미하지만 "예측 가능"이라고 생각하세요. 예측 가능한 RNG. 무작위로 보이는 숫자를 생성하지만 동일한 시작 시드가 주어지면 실제로는 반복 가능합니다.
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 지역(80 x 80 덩어리)에서 Woodland Mansion이 어디로 가야 하는지 결정하고, 그 장소가 바로 여기 인지 확인하고, 그렇다면 바로 여기에서 시작하는 Woodland Mansion을 생성하는 것입니다.
이 코드는 약간 어리석게 보일 수 있습니다. "모든 청크에 대해 이러한 모든 검사를 수행하는 것은 터무니없는 일입니다. Woodland Mansions가 지역별로 한 번씩 어디로 가야 하는지 선택하고 완료하면 됩니다."라고 생각할 수 있습니다. 그 이유는 Minecraft 청크가 서로 독립적으로, 알 수 없는 순서로 생성되지만 우리는 여전히 주어진 시드에서 결정론적인 세계를 생성하기를 원하기 때문입니다. 우리는 플레이어가 어떤 순서로 세계를 돌아다닐지 알지 못하며, 무상태 방식으로 요청에 따라 청크를 생성할 수 있다는 점은 좋습니다. 좋은 게임 경험입니다. 따라서 이상하게 보이는 코드는 다음과 같습니다.
어쨌든 해당 코드는 로드되는 항목 주변의 큰 사각형에 있는 모든 청크에 대해 모든 청크 로드에서 호출됩니다. 이유를 설명하는 것은 약간 복잡하므로 대부분 생략하겠습니다(기본 아이디어는 이러한 구조가 크기가 한 청크보다 (훨씬) 크다는 것입니다. 따라서 생성하려면 근처에 있는 많은 청크에서 구조 원점을 확인해야 합니다. 이 현재 것이 정확합니다).
이는 오버월드에만 영향을 미칩니다. Nether는 모든 구조 생성이 항상 안전한 RNG를 사용했기 때문에 안전합니다. The End의 청크 로드는 엔드 도시로 인해 영향을 받지만 이후 로드될 때마다가 아니라 초기 생성 시에만 영향을 받습니다. 따라서 The End는 기지의 각 청크가 처음 로드할 때 RNG에 한 번만 영향을 미치기 때문에 상대적으로 안전합니다. 그것. 그러나 플레이어가 기지로 이동할 때마다 일반적으로 새 청크를 생성하고 때때로 이미 기지에 있는 동안 새 청크를 생성하기 때문에 이것이 완전히 안전한 것은 아닙니다.
문제는 이것이 글로벌 World.rand 의 시드를 수정한다는 것입니다. 이것은 단지 게으른 코딩입니다. 그들이 하는 일은 X와 Z 좌표를 선택하기 위해 nextInt 네 번 호출하는 것뿐입니다. 그들은 Random random = this.world.setRandomSeed(... Random random = new Random(the same stuff) 로 대체했을 수 있습니다. 즉, 다른 모든 것에서 사용되는 기존 Random을 엉망으로 만드는 대신 여기서 새로운 Random 만드시겠습니까? ??).
결정적으로 Woodland Mansion이 어디로 가야 하는지 확인하기 위해 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 );
}다시 말하지만, 약간 수정되었지만 기능적으로는 우리가 말하는 내용에 정확합니다.
여기서 아이디어는 Minecraft에서 블록을 채굴하면 아이템을 떨어뜨린다는 것입니다. 아이템은 블록 내 임의의 위치에 떨어집니다. 예를 들어 블록이 (10, 20, 30) 에 있는 경우 항목은 (10.25, 20.25, 30.25) 와 (10.75, 20.75, 30.75) 사이에 나타납니다.
그리고 해당 항목의 정확한 위치는 X, Y, Z에 대해 world.rand.nextFloat() 세 번 연속 호출하여 선택됩니다.
이것이 필요한 Minecraft 코드의 전부입니다!
이제 nextFloat 호출로 뭔가를 할 수 있다고 말씀드렸습니다. 먼저, nextFloat 호출이 무엇인지 보기 위해 "역방향 작업"이 가능한지 살펴보겠습니다. 꽤 운이 좋지만 실제로는 가능합니다. 위 코드에서 참고하세요. 무작위 부동소수점에 0.5를 곱한 다음 0.25에 더합니다. 아이디어는 0과 1 사이의 난수에서 0.25와 0.75 사이의 난수로 이동하는 것입니다. 걱정하실 수도 있습니다. 정수를 2로 나누면 결과가 반올림되기 때문에 약간의 정보가 손실될 수 있기 때문입니다. 고맙게도 float에 0.5를 곱하면 가수는 그대로 두고 지수만 감소하기 때문에 완전히 되돌릴 수 있습니다. 그런 다음 float가 double로 캐스팅되어 훨씬 더 정밀해집니다. 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입니다.
여기서 나온 float를 사용하여 이에 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 에 따라 업데이트되었음을 알고 있습니다.
유효한 옵션 중 하나는 가능한 모든 2^24 하위 비트를 시도하는 for 루프라는 점을 언급해야 합니다. 이 글을 읽는 프로그래머들에게 문제가 무엇인지 명확해지기를 바랍니다.
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-loop 솔루션(작동하는)을 제공하고 익스플로잇의 다음 단계를 계속 진행하겠습니다. 격자 축소 방법에 대한 설명은 바로 이어서 하겠습니다 :)
일단 이 씨앗을 갖게 되면 우리는 무엇을 합니까?
먼저, LCG를 뒤로 이동할 수 있다는 점에 유의하세요. 분명히 11을 더하는 것은 되돌릴 수 있지만 그 큰 숫자를 곱하는 것은 되돌릴 수 있습니까? 승수 25214903917 은 홀수입니다. 즉, 2로 나눌 수 없으므로 모듈러스 2^48과 어떤 요소도 공유하지 않습니다(2^48은 말 그대로 2의 묶음이기 때문입니다). 이는 모듈러스에 대해 상대적으로 소수이므로 이를 반전할 수 있습니다. 이는 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 세계의 범위는 -3천만에서 +3천만 블록까지입니다. 각 "우드랜드 지역"(앞서 표시된 코드에 따라 단일 우드랜드 맨션이 무작위로 배치되는 세계 영역)은 80 x 80 청크, 즉 1280 x 1280 블록입니다. 이것은 23437.5 Woodland 지역이지만 모든 코드에 대해 23440으로 반올림했습니다. 이는 어림수이고 플레이어가 3천만 이상 이동할 수 없더라도 근처에 서 있는 것만으로도 그 이상의 청크를 로드할 수 있기 때문입니다. 그 모든 것에 대해 걱정하고 싶지 않았습니다.
따라서 X축과 Z축 모두에서 -23440 ~ +23440입니다. 이는 (23440*2+1)^2 (일명 2197828161 ) 가능한 Woodland 지역이며, 각 지역은 고유한 "맨션 시드"(누군가 특정 Woodland 지역에 청크를 방금 로드했음을 나타내는 시드로 정의됨)를 생성합니다. 무언가가 맨션 시드인지 확인할 수 있어야 합니다. 22억 개의 맨션 시드를 모두 반복하여 각각을 확인할 수 있을까요? 너무 느릴 것입니다. 22억 개의 항목이 포함된 HashSet<Long> 만들 수 있나요? nocom에서 했던 것처럼 Chronicle Map을 사용하더라도 너무 많은 RAM을 차지할 것이며, 심지어 abseil-cpp 사용하는 C++에서도 50GB RAM 정도를 사용했습니다. 그리고 다른 부분은 말할 것도 없습니다. 우리는 실제로 그들이 세계 어디에 있는지 알고 싶습니다(그게 요점입니다). 따라서 이것이 맨션 시드인지 아는 것만으로는 충분하지 않습니다. 우리는 또한 어떤 Woodland 지역이 이를 발생시켰는지 (효율적으로) 알고 싶습니다.
Woodland Region에서 맨션 시드로 이동하는 함수를 떠올려보세요(참고: 단순화를 위해 위 코드 이후 일부 상수를 결합했습니다. 이 방정식은 이제 2b2t의 시드에 특화되었습니다 ).
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
( -4172144997891902323 숫자는 -4172144997902289642 + 10387319 에서 나옵니다. 이는 2b2t 세계 시드 + 우드랜드 지역 시드에 사용되는 마법 값입니다(앞서 설명한 것처럼). 다른 세계의 경우 이 방정식에 대신 자신의 시드를 넣으면 됩니다. .)
x 좌표에 짝수를 곱하기 때문에 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
따라서 이것은 총 22억 번의 반복을 수행하는 두 개의 중첩 루프(X에 대해 하나, Z에 대해 하나) 대신 46,881회 반복을 수행하는 X에 대한 단일 for 루프를 가질 수 있기 때문에 매우 좋은 솔루션입니다. 다음은 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비트를 2의 보수에 대한 올바른 부호 비트로 채웁니다.
따라서 이것은 작동하며 단일 씨앗의 경우 합리적으로 빠릅니다. 그러나 우리는 잠재적으로 수천 단계에 대해 RNG를 뒤로 물러나고 일치하는 항목을 찾을 때까지 각 단계에서 이 검사를 실행한다는 점을 기억하십시오. 당시 우리는 가장 낮은 계층에서 형편없는 DigitalOcean 드롭릿을 사용하고 있었는데 이로 인해 실제로 모든 것이 뒤처지고 실시간을 따라잡을 수 없었습니다(봇은 초당 많은 블록을 채굴하고 각 블록은 크래킹하는 데 수천 개의 단계가 필요하며, 그리고 확인하기 위해 23440*2+1 작업을 수행하는 각 rng 단계를 확인하고 이를 곱하면 초당 수억 개의 작업이 가능하므로 특히 해당 VPS가 다음과 같은 경우 형편없는 VPS에서 문제가 발생한 이유를 알 수 있습니다. Minecraft의 여러 헤드리스 인스턴스를 실행하려고 합니다).
어쨌든 그래서 우리는 조회 테이블 접근 방식으로 전환하고 Cuda에서 이를 다시 작성하여 몇 분마다 내 데스크탑에서 배치 작업으로 실행했습니다. 수천 개의 쿠다 코어 각각이 자체 시드에서 병렬로 작동할 수 있기 때문에 문자 그대로 초당 수백만 개의 작업을 수행할 수 있습니다. 아이디어는 다음과 같습니다. 조회 테이블의 키는 맨션 시드의 하위 32비트이고 값은 Woodland 지역의 X 좌표입니다. 이 조회 테이블은 각 맨션 시드가 고유 한 하위 32비트를 갖기 때문에 충돌 없이 작동합니다. 그게 왜 사실인지 이해가 안 가는데, 정말 매력적이에요. 당신은 그것이 작동하지 않을 것이라고 생각할 것입니다. 하지만 이 작업을 수행하기 위해 계수 341873128712 및 132897987541 특별히 선택되었을 수 있다고 생각합니다. 예를 들어, 22억 개의 구슬과 43억 개의 양동이가 있고 각 구슬을 무작위 양동이에 독립적으로 넣으면 각 구슬이 자신의 양동이를 가질 확률은 얼마나 될까요? 본질적으로 0입니다. 끝이 가까워지면 각각의 새로운 구슬이 이미 채워져 있는 양동이에 부딪힐 확률이 50% 이상입니다. 그러나 분명히 이것들은 독립적으로 무작위가 아니므로 어떻게든 작동합니다. 이 글을 읽고 이것이 어떻게 작동하는지 또는 두 가지 특정 계수가 왜 작동하는지 이해한다면 알려주시기 바랍니다. 어쨌든 작동합니다. 조회 테이블에는 2^32개의 항목이 있고 각 항목은 2바이트(-23440에서 +23440 사이의 숫자이므로)이므로 GPU에 약 9GB의 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에서 초당 천만 개의 씨앗을 깨뜨릴 수 있습니다. 워프의 스레드 중 일부가 일찍 종료되면 그다지 큰 문제가 아닌 것으로 밝혀졌으며 실제로는 만들 수 없었습니다. 이것보다 더 빠릅니다. (그 이유는 어떤 씨앗이 더 많은 단계를 거치거나 더 적은 단계를 밟게 될지 근본적으로 미리 알 수 없기 때문입니다.)
글쎄, 그게 다야. 시드가 주어지면 가장 최근에 청크 로드가 발생한 세계에서 Woodland 지역을 얻는 방법입니다. 즉, 우리는 누군가가 2b2t를 돌아다니며 세계의 새로운 영역을 로드한 가장 최근 시간이 우리가 방금 식별한 1280 x 1280 블록의 우드랜드 지역 어딘가에 있다는 것을 방금 배웠습니다. (검색하는 데 몇 분 밖에 걸리지 않을 정도로 정확합니다.)
실제로 몇 개의 RNG 단계가 필요했습니까? 가장 낮은 수준에서 신뢰할 수 있는 측정은 4개의 RNG 단계에서 시작됩니다. 그 아래의 모든 것은 측정 오류/랜덤 노이즈입니다. 이는 Woodland Mansion 코드가 측정이 가능하기 전에 즉시 rand.nextInt 4번 호출하기 때문에 알고 있습니다. 평균적으로 각 Woodland 시드 사이에는 약 128,000개의 단계가 있지만 실제로는 2b2t의 대부분의 경우 수십 단계 이내에 Woodland 시드를 발견했습니다. 이는 Minecraft 진드기에서 어떤 순서로 무슨 일이 일어나는지에 대한 세부 사항 때문입니다. 우리의 측정은 기술적으로 틱의 시작 부분에서 이루어집니다. 블록을 깨기 위한 패킷이 처리되는 곳이기 때문입니다. 일반적으로 이전 틱 동안 가장 최근 기록에 청크가 로드되었습니다. 그러나 때로는 이벤트로 인해 그 사이에 여러 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 측정값은 빨간색의 16진수와 일치합니다. 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 ;
}완벽한 보호를 원한다면 매번 다른 Random을 반환하도록 이 함수를 변경하기만 하면 됩니다.
패치 버전:
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 ;
}1.12.2용 PaperMC를 사용하는 경우 적용할 수 있는 패치는 다음과 같습니다. 대체 링크.
이것은 기본 아이디어 외에 대부분 독립적으로 개발했기 때문에 내 관점에서 설명하는 것이 더 타당할 수 있는 몇 가지 추가 항목을 검토하는 추가 섹션이 될 것입니다.
가장 먼저 언급하고 싶은 것은 시드에서 좌표를 찾는 시스템입니다. Mason's는 대규모 조회 테이블과 GPU 처리를 사용했지만 대신 속도를 위해 캐시에 의존했습니다. 적중이 발생할 때마다 해당 좌표와 반경 내의 모든 좌표가 HashMap에 저장됩니다. 종자는 2단계로 처리됩니다. 첫 번째 단계에서는 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
