Jedes Mal, wenn in den Minecraft-Versionen Beta 1.8 bis 1.12.2 ein Block aufgebrochen wird, können die genauen Koordinaten des fallengelassenen Gegenstands den Standort eines anderen Spielers verraten .
„Randar“ ist ein Exploit für Minecraft, der die LLL-Gitterreduktion nutzt, um den internen Zustand eines falsch wiederverwendeten java.util.Random auf dem Minecraft-Server zu knacken und dann rückwärts davon zu arbeiten, um andere aktuell in die Welt geladene Spieler zu lokalisieren.
Klicken Sie hier, um mehr über Randar in Form eines YouTube-Videos zu erfahren.
Sehen Sie sich den Zeitraffer an:
Weitere Zeitraffer finden Sie hier (als Dateien) oder hier (als YouTube).
Ziel ist es, die Standorte (also Koordinaten) der anderen Spieler auf der Welt im Spiel zu bestimmen, egal wie weit sie entfernt sind. Wir spielen auf 2b2t, dem ältesten und berühmtesten „Anarchy“-Minecraft-Server (was bedeutet, dass es keine Regeln gibt, dh Spieler werden aus keinem Grund gesperrt). Solche Dinge zu tun ist sozusagen „der Sinn“ auf diesem Server. Das Einzige, was auf diesem Server Ihre Sachen schützt, ist, dass die Karte riesig ist (3,6 Billiarden Quadratkacheln) und niemand sonst weiß, wo Sie sich befinden. Es ist also eine riesige (bahnbrechende) Sache, einen Koordinaten-Exploit zu haben. (Apropos, vor Randar hatten wir von 2018 bis 2021 auch einen weiteren Coord-Exploit auf 2b2t, Nocom; siehe diesen Artikel hier, HackerNews-Thread, YT)
Der Fehler im Minecraft-Code ist in den Versionen Beta 1.8 (veröffentlicht 2011) bis 1.12.2 (veröffentlicht 2017) vorhanden, aber 2b2t blieb bis zum 14. August 2023 bei dieser Version. Der Fehler besteht darin, dass verschiedene Instanzen des Zufallszahlengenerators java.util.Random in verschiedenen Teilen des Codes schlampig wiederverwendet werden (und sie von vornherein unsicher sind). Insbesondere gibt es die Wiederverwendung von RNG zwischen der Geländegenerierung und Spielaktionen wie dem Abbau von Blöcken.
Der Exploit zusammengefasst:
World.rand auf eine Funktion der Chunk-Koordinaten zurückgesetzt, um zu überprüfen, wo sich ein Woodland Mansion in der Nähe befinden sollte (und ob es sich speziell um diesen Chunk handelt).World.rand.nextFloat() -Aufrufe bestimmt wird, um die XY- und Z-Koordinaten zwischen 0 und 1 auszuwählen. Der Bot zeichnet den Zeitstempel und die genauen XYZ-Werte auf.World.rand bestimmen, der diese drei Floats verursacht hat. Im Großen und Ganzen (weitere Einzelheiten folgen später) könnte die Beobachtung einer Ausgabe des RNG einen beliebigen von etwa 16 Millionen möglichen internen Zuständen des RNG implizieren. Allerdings haben wir die Ausgabe des RNG nicht nur einmal, sondern dreimal hintereinander abgetastet (die X-, Y- und Z-Koordinaten des abgelegten Elements) und wissen, wie der interne Status zwischen jedem Aufruf aktualisiert wird (eine einfache Multiplikation). , hinzufügen, dann mod); Daher können wir Gittermethoden verwenden, um es im Wesentlichen sofort auf die einzige Möglichkeit einzugrenzen.java.util.Random lässt sich genauso leicht rückwärts wie vorwärts ändern, und indem wir rückwärts gehen, können wir ihn in nur wenigen tausend Schritten finden (selbst auf ausgelasteten Servern wie 2b2t mit vielen Spielern und daher schwer). Verwendung von RNG), die den letzten Zeitpunkt identifiziert, zu dem der interne Status des RNG zurückgesetzt wurde, und damit den Speicherort des zuletzt auf den Server geladenen Blocks.Selbst wenn Sie auf einem Server spielen, der auf eine neuere Version von Minecraft aktualisiert wurde oder die RNG-Manipulation anderweitig gepatcht hat, sind Ihre Koordinaten immer noch durch Randar gefährdet, da RNG-Daten rückwirkend ausgenutzt werden können. Einige Minecraft-Spieler verwenden Mods wie ReplayMod, die Pakete protokollieren, und möglicherweise liegen diese Protokolldateien immer noch herum. Wenn jemand einen solchen Mod verwendet hat, während Sie in Ihrer Basis waren, hat er möglicherweise (unwissentlich) RNG-Daten aufgezeichnet, die Ihren Standort verraten könnten, da das Aufbrechen von Blöcken eine äußerst häufige Aktion ist, die bei solchen Aufzeichnungen und bei jedem solchen Block wahrscheinlich vorgekommen ist break zeigt den RNG-Status des Servers und damit den Speicherort des zuletzt geladenen Chunks an. Das bedeutet, dass Randar eine ziemlich große Sache ist: Aufgrund dieses Risikos einer rückwirkenden Ausnutzung sollte auf jedem Minecraft-Server jeder Standort, der in den Versionen Beta 1.8 bis 1.12.2 aktiv war, als gefährdet betrachtet werden, selbst wenn der Server längst über 1.12 hinaus aktualisiert wurde .2 oder gepatchte RNG-Manipulation.
Wenn Sie den Randar-Exploit selbst nutzen möchten , gehen Sie hierher, wo rebane2001 eine Website erstellt hat, auf der Sie Ihre ReplayMod-Dateien aus 1.12.2 hineinziehen und die Koordinaten anderer Spieler sehen können. Es läuft clientseitig, sodass Ihre Aufzeichnungen Ihren Browser nicht verlassen. Hier ist ein Video, das zeigt, wie diese Website in Aktion aussieht. Sie können die ReplayMod-Beispieldatei aus diesem Video ausführen, indem Sie sie hier herunterladen.
Randar wurde von n0pf0x (pcm1k) entdeckt. Dieser Artikel wurde von leijurv verfasst, mit einigen zusätzlichen Kommentaren am Ende von n0pf0x. Ausnutzer waren 0x22, Babbaj, TheLampGod, leijurv, Negative_Entropy und rebane2001. Sehen Sie sich hier das Video von TheLampGod an. Sehen Sie sich hier das 100 % humorvolle und 0 % sachliche Video von HermeticLock an.
Inhaltsverzeichnis: Klicken Sie hier, um mehr über den ausnutzbaren Code zu erfahren, hier, um zu erfahren, wie die Gitterreduktion verwendet wurde, hier, um zu sehen, wie wir unsere eigenen Stashes vor Randar geschützt haben, hier, wenn Sie nur den vollständigen Exploit-Code sehen möchten, Hier finden Sie Informationen dazu, was n0pf0x anders gemacht hat als wir.
Diagramm des Fehlers (als PDF):
Diagramm des Exploits (als PDF):
Diagramm eines funktionierenden Beispiels des Exploits (als PDF):
Minecraft setzt im gesamten Spiel auf Zufallszahlen. Wir gehen davon aus, dass die meisten von ihnen tatsächlich zufällig sind, wie z. B. die Zufälligkeit, die für das Spawnen von Mobs und das Wetter verwendet wird, aber einige davon gehen wir davon aus, dass sie vorhersehbar sind, zum Beispiel erwarten wir, dass derselbe Weltsamen am selben Ort das gleiche Terrain erzeugt. Als Notch 2011 während der Beta 1.8 zum ersten Mal Strukturen zum Spiel hinzufügte, verwendete er versehentlich einen RNG, der unvorhersehbar sein sollte , um Dörfer in der Welt zu platzieren. Seitdem, bis 1.13, hat dieser schlampige Code dazu geführt, dass die Weltgenerierung nahezu alle anderen vermeintlich zufälligen Ereignisse im Spiel beeinflusst hat. Es dauerte bis etwa Mai 2018, bis Earthcomputer und seine Freunde diesen Fehler entdeckten und erkannten, dass Chunk-Loads den RNG des Spiels auf beobachtbare Weise beeinflussen, siehe diese Erklärung. Sie wussten jedoch nicht oder gaben es einfach nie öffentlich bekannt, dass man dies auch rückwärts tun kann, indem man den zuletzt geladenen Block anhand des RNG ermittelt. Diese Entdeckung, Randar, wurde am 7. Oktober 2022 von n0pf0x (alias pcm1k) gemacht. Etwa zwei Wochen später veröffentlichte er eine kurze, verschlüsselte Beschreibung des Exploits auf Pastebin, um zu beweisen, dass er ihn damals entdeckt hatte. Er nutzte den Exploit hauptsächlich auf 9b9t und nur relativ wenig auf 2b2t und anderen Servern. Auf 2b2t lokalisierte und erkundete n0p verschiedene Orte und gelangte schließlich zu einem Versteck in Gringotts. Er wurde von rebane2001 entdeckt und schwieg zunächst darüber, wie er den Ort gefunden hatte. Etwa einen Monat später begann er jedoch ein Gespräch mit den SpawnMasons darüber. n0p gab bekannt, dass er einen mächtigen Koordinaten-Exploit genutzt hatte, und beschloss, uns im April 2023 eine Erklärung mitzuteilen, da die Maurer in der Vergangenheit Erfahrung damit hatten, 2b2t-Exploits in größerem Maßstab auszunutzen Mir wird es sowieso etwas langweilig. Wir akzeptierten und begannen mit der Aufzeichnung der Koordinaten des Abwurfs von Gegenständen auf mehreren Konten, die bereits rund um die Uhr Steine/Kopfsteinpflaster für ein nicht damit zusammenhängendes Projekt abbauten (es gab also keine Verhaltensänderung). Wir haben das Headless-Minecraft-System von nocom wiederverwendet und eine Postgres-Datenbank zur Aufzeichnung der Messungen hinzugefügt. Wie später in dieser Readme-Datei besprochen wird, haben wir mehrere Software-Iterationen durchlaufen, um die RNG-Messungen zu knacken, und uns schließlich für einen asynchronen Cuda-Batch-Job entschieden. Als der Datenbank Rissmessungen hinzugefügt wurden, aktualisierten wir auch eine Analysetabelle mit Heatmap-Informationen, die Treffer an jeder Koordinate in zeitlichen Abständen, täglich und stündlich, zählte. Dies ermöglichte es einer einfachen Plotly Dash-Benutzeroberfläche, Heatmap-Daten aus bestimmten Zeitbereichen und Granularitäten für die Anzeige in einem Browser auszuwählen, und es ermöglichte uns, den gesamten Elytra-Stashhunting-Chunk-Load-Spam zu entfernen, indem wir nur Koordinaten berücksichtigten, die in mehr als ein paar verschiedenen Stunden geladen wurden. Wir haben ein einfaches gemeinsames Anmerkungssystem hinzugefügt, um den Überblick darüber zu behalten, was wir an jedem Hotspot auf der Karte gefunden haben. Wiederum eine Wiederverwendung von Nocom: Wir haben Bariton-Bots, die den gesamten Prozess des Stehlens von Gegenständen und Sortieren der Ergebnisse völlig automatisiert automatisieren. Viele Maurer halfen bei diesem Teil, ohne den Exploit zu kennen, indem sie Konten wie munmap und 1248_test_user verwendeten. Alle Gringotts-Vorräte zusammengenommen wuchsen schließlich auf 1,3 Milliarden Gegenstände an, von denen etwa die Hälfte auf Nocom und die Hälfte auf Randar entfällt.
Die vollständige Geschichte wird im FitMC-Video erklärt.
Die Karte von Minecraft wird prozedural generiert und ist im Wesentlichen deterministisch, basierend auf dem ursprünglichen Startwert der Welt. Während Spieler die Karte erkunden, werden bei Bedarf neue Gebiete generiert, wenn Spieler näher kommen. Da die gesamte Generierung wiederholbar (deterministisch) sein soll, ist es durchaus sinnvoll, dass sie an vielen Stellen java.util.Random verwendet haben. Sie wollen , dass es vorhersehbar ist. Aus diesem Grund wird java.util.Random verwendet, da es ein PRNG (nicht wirklich ein RNG) ist. Das P bedeutet technisch gesehen „Pseudo“, aber man kann es sich als „vorhersehbar“ vorstellen. Vorhersehbares RNG. Es generiert Zahlen, die zufällig erscheinen, in Wirklichkeit aber bei gleichem Startwert wiederholbar sind.
Minecraft verfügt über verschiedene Strukturen, die in der Welt generiert werden, wie z. B. Dörfer, Meeresdenkmäler, Festungen usw. Diese sind Teil der prozeduralen Generierung, werden also auch deterministisch platziert und generiert.
Um dies zu verstehen, sind nur ein Dutzend Zeilen Minecraft-Code erforderlich, und ich habe es vereinfacht und stark kommentiert:
// (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)
}Das Obige ist zur Verdeutlichung kommentiert und leicht modifiziert, entspricht aber funktionell dem echten Code.
Die Idee besteht also darin, zu entscheiden, wo das Woodland Mansion in dieser Waldregion (die 80 x 80 Stücke groß ist) stehen soll, zu prüfen, ob sich dieser Ort genau hier befindet, und wenn ja, ein Woodland Mansion zu erstellen, das genau hier beginnt.
Dieser Code sieht vielleicht etwas albern aus, Sie denken vielleicht: „Es ist absurd, all diese Überprüfungen für jeden Teil durchzuführen. Wählen Sie einfach einmal pro Region aus, wo Woodland Mansions hingehen sollen, und fertig.“ Der Grund dafür ist, dass Minecraft-Chunks unabhängig voneinander und in unbekannter Reihenfolge generiert werden, wir dennoch aus einem bestimmten Seed eine deterministische Welt generieren möchten. Wir wissen nicht, in welcher Reihenfolge der Spieler um die Welt laufen wird, und es ist schön, jeden Teil zustandslos bei Bedarf generieren zu können. Es ist ein gutes Spielerlebnis. Also seltsam aussehender Code wie dieser.
Wie auch immer, dieser Code wird bei jedem Chunk-Laden aufgerufen, für jeden Chunk in einem großen Quadrat um den Chunk, der geladen wird. Es ist etwas kompliziert zu erklären, warum das so ist, deshalb werde ich es größtenteils überspringen (die Grundidee ist, dass diese Strukturen (viel) größer als ein Block sind, sodass wir zum Generieren in vielen benachbarten Blöcken nach einem Strukturursprung suchen müssen dieses aktuelle richtig).
Beachten Sie, dass dies nur die Oberwelt betrifft. Der Nether ist sicher, da bei der gesamten Strukturgenerierung immer sicheres RNG verwendet wurde. Das Laden von Chunks in The End wird aufgrund von Endstädten beeinflusst, jedoch nur bei ihrer ersten Generierung, nicht bei jedem weiteren Laden. Daher ist The End relativ sicher, da jeder Chunk in Ihrer Basis den RNG nur einmal beeinflusst, wenn Sie ihn zum ersten Mal laden Es. Dies ist jedoch nicht völlig sicher, da Spieler normalerweise jedes Mal neue Blöcke generieren, wenn sie zu ihrer Basis reisen, und gelegentlich neue Blöcke generieren, während sie bereits an ihrer Basis sind.
Das Problem besteht darin, dass dadurch der Startwert des globalen World.rand verändert wird. Das ist einfach Lazy-Coding. Sie rufen lediglich viermal nextInt auf, um die X- und Z-Koordinate auszuwählen. Sie hätten Random random = this.world.setRandomSeed(... durch Random random = new Random(the same stuff) ersetzen können (mit anderen Worten, hier ein neues Random erstellen, anstatt mit dem vorhandenen herumzuspielen, das von allem anderen verwendet wird?) ??).
Entscheidend ist, dass setRandomSeed aufgerufen wird , um zu überprüfen, wohin das Woodland Mansion gehen soll. Es passiert, egal was passiert, bei jeder Chunk-Ladung, überall. Sie müssen nicht in oder in der Nähe des Woodland Mansion oder ähnliches stehen.
Nun, es stellt sich heraus, dass World.rand an buchstäblich Hunderten von Orten verwendet wird, und viele dieser Orte können durch normales Spielen des Spiels leicht beobachtet werden. Wenn Sie beispielsweise einen Block abbauen:
/**
* 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 );
}Auch hier leicht modifiziert, aber funktional genau auf die Dinge abgestimmt, über die wir sprechen.
Die Idee dahinter ist, dass in Minecraft beim Abbau eines Blocks ein Gegenstand fallen gelassen wird. Der Gegenstand wird an einer zufälligen Position innerhalb des Blocks abgelegt. Wenn der Block beispielsweise bei (10, 20, 30) lag, wird das Element irgendwo zwischen (10.25, 20.25, 30.25) und (10.75, 20.75, 30.75) erscheinen.
Und die genaue Position dieses Elements wird durch dreimaligen Aufruf von world.rand.nextFloat() für X, Y und Z ausgewählt.
Das ist alles, was Sie an Minecraft-Code benötigen!
Nun habe ich gesagt, dass wir mit diesen nextFloat -Aufrufen etwas anfangen können. Lassen Sie uns zunächst sehen, ob wir „rückwärts arbeiten“ können, um zu sehen, was die nextFloat -Aufrufe sind. Es ist ziemlich viel Glück, aber wir können es tatsächlich. Beachten Sie im obigen Code: Der zufällige Gleitkommawert wird mit 0,5 multipliziert und dann zu 0,25 addiert. Die Idee besteht darin, von einer Zufallszahl zwischen 0 und 1 zu einer Zufallszahl zwischen 0,25 und 0,75 zu gelangen. Sie könnten sich Sorgen machen, denn wenn Sie eine ganze Zahl durch zwei dividieren würden, würden Sie einige Informationen verlieren, da das Ergebnis abgerundet wird. Zum Glück ist die Multiplikation einer Gleitkommazahl mit 0,5 völlig reversibel, da dadurch nur der Exponent dekrementiert wird, während die Mantisse unberührt bleibt. Dann wird der Float in ein Double umgewandelt, was eine wesentlich höhere Präzision bietet. 0,25 wird hinzugefügt, dann wird die Blockkoordinate hinzugefügt. Anschließend wird es mit voller Präzision über das Netzwerk an den Client gesendet. Das Ergebnis: Dieser gesamte Prozess ist umkehrbar, sodass wir genau die drei Floats erhalten können, die World.rand.nextFloat() erzeugt hat.
Wie generiert java.util.Random Floats? Eigentlich ist es ganz einfach. Es generiert eine Ganzzahl zwischen 0 und 2^24 und dividiert diese dann durch 2^24 (was zu einer Zahl zwischen 0 und 1 führt). Wie kommt es zu dieser zufälligen Ganzzahl? Auch ziemlich einfach! Es handelt sich um einen linearen Kongruenzgenerator (LCG). Das bedeutet, dass der nächste Startwert der vorherige Startwert mal etwas plus etwas anderes ist, modulo etwas anderes.
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
}In diesem Fall beträgt der Multiplikator 25214903917, der Summand 11 und der Modul 2^48.
Mit dem daraus resultierenden Float können wir ihn mit 2^24 multiplizieren, um die randomInteger zurückzuerhalten und somit die „obere Hälfte“ (die höchstwertigen 24 Bits) des 48-Bit-Seeds zu erhalten.
Kurz gesagt, aus unserer Messung erfahren wir, dass der Startwert zwischen measuredRandomInteger * 2^24 und (measuredRandomInteger + 1) * 2^24 liegt.
Und wir können dies dreimal hintereinander tun, für X, Y und Z.
Und wir wissen, dass zwischen X und Y sowie zwischen Y und Z der Startwert gemäß newSeed = (oldSeed * 25214903917 + 11) mod 2^48 aktualisiert wurde
Ich muss erwähnen, dass eine gültige Option eine for-Schleife ist, die alle 2^24 möglichen unteren Bits durchprobiert. Für die Programmierer, die dies lesen, hoffe ich, dass dies klar macht, wo das Problem liegt:
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 ;
}
}Das würde funktionieren und funktioniert auch, aber es ist nicht so schnell und macht nicht so viel Spaß. Also verwenden wir stattdessen Gitter!
Allerdings habe ich das Gefühl, dass ich etwas aus der Reihe geraten muss. Der Teil mit der Gitterreduktion kommt hier zwar ins Spiel, aber er ist wirklich kompliziert und ich wette, er hätte eine geringe Leserbindung zur Folge, und ich möchte Sie nicht verlieren. Deshalb gebe ich Ihnen einfach die For-Loop-Lösung (die funktioniert) und fahre mit dem nächsten Schritt des Exploits fort. Die Erklärung der Gitterreduktionsmethode folgt gleich danach :)
Was machen wir mit diesem Samen, wenn wir ihn haben?
Beachten Sie zunächst, dass wir die LCG rückwärts bewegen können. Offensichtlich ist die Addition von elf umkehrbar, aber ist die Multiplikation mit dieser großen Zahl umkehrbar? Unser Multiplikator 25214903917 ist eine ungerade Zahl, was bedeutet, dass er nicht durch zwei teilbar ist und daher keine Faktoren mit unserem Modul 2^48 gemeinsam hat (da 2^48 buchstäblich nur ein Haufen Zweier ist). Da sie relativ teilerfremd zum Modul ist, können wir sie invertieren, was bedeutet, dass wir eine andere Zahl x finden, die x * 25214903917 - 1 ist durch 2^48 teilbar. Oder mit anderen Worten: 25214903917 * x mod 2^48 = 1 . Diese Nummer ist 246154705703781 . Dies hilft, die Multiplikation umzukehren, denn wenn wir beispielsweise secret * 25214903917 haben und secret herausfinden möchten, können wir einfach secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret berechnen.
Ok, also können wir den internen Startwert von java.util.Random sowohl vorwärts als auch rückwärts verschieben. Vorwärts ist newSeed = (oldSeed * 25214903917 + 11) mod 2^48 und rückwärts ist oldSeed = ((newSeed - 11) * 246154705703781) mod 2^48 . Und das funktioniert, weil diese Zahlen 25214903917 und 246154705703781 , wenn man sie mit Mod 2^48 multipliziert, 1 ergeben.
Wenn wir nun einen Schritt zurückgehen, möchten wir bei jedem Schritt prüfen, ob dieser Samen bedeuten könnte, dass kürzlich irgendwo auf der Welt eine Woodland Mansion-Überprüfung durchgeführt wurde (der springende Punkt des Exploits). Wie machen wir das?
Die Minecraft-Welt reicht von -30 Millionen bis +30 Millionen Blöcken. Jede „Waldregion“ (ein Bereich der Welt, in dem ein einzelnes Waldlandhaus zufällig platziert wird, gemäß dem zuvor gezeigten Code) ist 80 x 80 Blöcke groß, was 1280 x 1280 Blöcken entspricht. Das sind 23437,5 Waldregionen, aber für unseren gesamten Code haben wir gerade auf 23440 aufgerundet, weil es eine runde Zahl ist und Ihr Spieler zwar nicht weiter als 30 Millionen reisen kann, Sie aber darüber hinausgehende Brocken laden, indem Sie einfach in der Nähe stehen, und wir einfach Ich wollte mir darüber keine Sorgen machen müssen.
Also -23440 bis +23440 auf der X- und Z-Achse. Das sind (23440*2+1)^2 (auch bekannt als 2197828161 ) mögliche Woodland-Regionen, von denen jede einen einzigartigen „Herrenhaus-Seed“ generiert (definiert als ein Seed, der verrät, dass jemand gerade einen Brocken in einer bestimmten Woodland-Region geladen hat). Wir müssen in der Lage sein zu überprüfen, ob es sich bei etwas um einen Villa-Samen handelt. Könnten wir alle 2,2 Milliarden Villa-Seeds durchlaufen, um jeden einzelnen zu überprüfen? Wäre zu langsam. Könnte ein HashSet<Long> mit 2,2 Milliarden Einträgen erstellt werden? Würde zu viel RAM beanspruchen, selbst wenn wir Chronicle Map verwenden, wie wir es in Nocom getan haben, und selbst in C++ mit abseil-cpp verbrauchte es etwa 50 GB RAM. Und ganz zu schweigen vom anderen Teil: Wir wollen tatsächlich erfahren, wo sie sich auf der Welt befinden (das ist der springende Punkt). Es reicht also nicht aus, zu erfahren, dass es sich um einen Villa-Samen handelt, wir wollen auch (effizient) herausfinden, welche Waldregion ihn verursacht hat.
Erinnern Sie sich an die Funktion, die von Woodland Region zu Mansion Seed geht (Hinweis: Der Einfachheit halber habe ich seit dem obigen Code jetzt einige Konstanten kombiniert, diese Gleichung ist jetzt auf den Seed von 2b2t spezialisiert ):
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
(Die Zahl -4172144997891902323 kommt von -4172144997902289642 + 10387319 , was dem 2b2t-Welt-Seed + dem magischen Wert entspricht, der für das Seeding der Woodland-Region verwendet wird (wie zuvor gezeigt). Für jede andere Welt würden Sie stattdessen einfach Ihren eigenen Seed in diese Gleichung einsetzen .)
Mit der x-Koordinate können wir nicht viel anfangen, da sie mit einer geraden Zahl multipliziert wird. Aber was ist dieser Koeffizient auf der Z-Koordinate? Es sieht aus wie eine ungerade Zahl!!! Wenden wir den gleichen Trick wie zuvor an, um es erneut zu invertieren, und wir erhalten 211541297333629 .
Stellen wir uns vor, wir haben einen bestimmten Samen. Was wäre, wenn wir einfach alle möglichen Mit anderen Worten: Die obige Gleichung liefert uns seed wenn wir x und z kennen. Können wir aber eine Gleichung aufstellen, die uns z liefert, wenn wir seed und x kennen? Antwort: Ja. Wir ordnen einfach die obige Gleichung um und nutzen die Tatsache, dass der Koeffizient von Z invertierbar mod 2^48 ist, da es sich um eine ungerade Zahl handelt.
Die Gleichung lautet:
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
Das ist also eine ziemlich gute Lösung, denn anstelle von zwei verschachtelten Schleifen (eine für X und eine für Z), die insgesamt 2,2 Milliarden Iterationen durchführen, können wir eine einzige for-Schleife für Hier ist es in 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 ;
} (Hinweis: Das seltsame << 16 >> 16 macht Mod 2^48, aber wir wollen es eigentlich mit vorzeichenbehafteten Typen machen, damit wir immer noch die richtige Antwort bekommen, wenn z zwischen -23440 und 0 liegt, das ist eine Möglichkeit Vorzeichenerweitern der 48-Bit-Zahl auf 64 Bits, wobei die oberen 16 Bits mit dem richtigen Vorzeichenbit für das Zweierkomplement gefüllt werden)
Das funktioniert also und es geht einigermaßen schnell ... für einen einzelnen Samen. Denken Sie jedoch daran, dass wir den Zufallszahlengenerator möglicherweise um Tausende von Schritten zurücksetzen und diese Prüfung bei jedem Schritt durchführen, bis wir eine Übereinstimmung finden. Zu dieser Zeit verwendeten wir ein beschissenes DigitalOcean-Droplet auf der untersten Stufe, und das verzögerte tatsächlich alles und konnte nicht mit der Echtzeit mithalten (Bots schürfen viele Blöcke pro Sekunde, wobei jeder Block Tausende von RNG-Schritten benötigt, um zu knacken). Und jeder RNG-Schritt erfordert 23440*2+1 Operationen zur Überprüfung. Multiplizieren Sie diese miteinander und Sie kommen auf Hunderte Millionen Operationen pro Sekunde. Sie verstehen also, warum das insbesondere auf einem beschissenen VPS Probleme bereitete wenn dieser VPS auch versucht, mehrere kopflose Instanzen von Minecraft auszuführen).
Wie auch immer, wir sind auf einen Lookup-Table-Ansatz umgestiegen und haben ihn in Cuda neu geschrieben, damit er alle paar Minuten als Batch-Job auf meinem Desktop ausgeführt wird. Es kann buchstäblich Millionen pro Sekunde leisten, da jeder der Tausenden von Cuda-Kernen parallel an seinem eigenen Seed arbeiten kann. Hier ist die Idee: Der Schlüssel der Nachschlagetabelle sind die unteren 32 Bits des Villa-Seeds und der Wert ist die X-Koordinate der Woodland-Region. Diese Nachschlagetabelle funktioniert kollisionsfrei, da jeder Mansion-Seed irgendwie über eindeutige untere 32 Bit verfügt. Ich verstehe nicht, warum das so ist, es ist faszinierend. Man könnte meinen, es würde nicht funktionieren. Aber ich denke, die Koeffizienten 341873128712 und 132897987541 wurden möglicherweise speziell ausgewählt, damit dies funktioniert? Wenn Sie beispielsweise 2,2 Milliarden Murmeln und 4,3 Milliarden Eimer haben und jede Murmel einzeln in einen zufälligen Eimer legen, wie hoch ist dann die Wahrscheinlichkeit, dass jede Murmel ihren eigenen Eimer bekommt? Im Wesentlichen Null. Gegen Ende hat jede neue Murmel eine Chance von mehr als 50 %, einen bereits gefüllten Eimer zu treffen. Allerdings sind diese offensichtlich nicht unabhängig voneinander zufällig, also funktioniert es irgendwie. Wenn Sie dies lesen und verstehen, wie das funktioniert oder warum diese beiden spezifischen Koeffizienten dafür sorgen, dass dies funktioniert, lassen Sie es mich bitte wissen. Wie auch immer, es funktioniert. Die Nachschlagetabelle hat 2^32 Einträge, und jeder Eintrag ist 2 Bytes groß (da es sich nur um eine Zahl zwischen -23440 und +23440 handelt), sodass dafür etwa 9 Gigabyte VRAM auf Ihrer GPU benötigt werden.
Die Woodland-Check-Funktion sieht jetzt so aus (auch dies ist der eigentliche Code, aber vereinfacht, alle Helfer und Konstanten eingebunden usw.):
__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;
}Das funktioniert hervorragend in riesigen Chargen und kann auf einem 3090 in der Größenordnung von zehn Millionen Seeds pro Sekunde knacken. Es stellt sich als keine allzu große Sache heraus, wenn einige der Threads in einem Warp vorzeitig enden, und wir konnten es nicht wirklich schaffen es geht nicht schneller. (Der Grund dafür ist, dass wir grundsätzlich nicht im Voraus wissen können, welche Samen mehr oder weniger Schritte ausführen werden.)
Nun, das ist alles. Wenn wir das Saatgut kennen, erhalten wir auf diese Weise die Woodland-Region auf der Welt, in der die letzte Brockenladung stattgefunden hat. Mit anderen Worten, wir haben gerade erfahren, dass das letzte Mal, als jemand auf 2b2t herumgelaufen ist und einen neuen Bereich der Welt geladen hat, irgendwo in dieser 1280 x 1280 Blöcke großen Waldregion war, die wir gerade identifiziert haben. (Das ist so präzise, dass die Suche nur wenige Minuten dauert, um sie zu finden.)
Wie viele RNG-Schritte waren in der Praxis erforderlich? Am unteren Ende beginnen zuverlässige Messungen bei 4 RNG-Schritten, alles darunter ist Messfehler/zufälliges Rauschen, was wir wissen, weil der Woodland Mansion-Code rand.nextInt sofort viermal aufruft, bevor wir es messen können. Im Durchschnitt liegen zwischen jedem Woodland-Samen etwa 128.000 Schritte, aber in der Praxis haben wir auf 2b2t in den allermeisten Fällen innerhalb weniger Dutzend Schritte einen Woodland-Samen gefunden. Dies liegt an den Einzelheiten darüber, was in welcher Reihenfolge in einem Minecraft-Tick passiert. Unsere Messung findet technisch gesehen ganz am Anfang des Ticks statt, da dort die Pakete zum Aufbrechen von Blöcken verarbeitet werden. Im Allgemeinen wurde während des vorherigen Ticks ein Chunk in den jüngsten Verlauf geladen. Allerdings kann ein Ereignis manchmal eine Reihe von RNG-Schritten dazwischen verursachen. Wir glauben, dass es sich bei diesem Ereignis um Explosionen handelt, etwa wenn jemand einen Endkristall in die Luft sprengt, indem er darauf schlägt, oder dass möglicherweise Schädel verdorren. Endkristallexplosionen würden auch während der Paketverarbeitung aus dem Schlagpaket des Spielers auftreten, und die Anzahl der RNG-Schritte beläuft sich ebenfalls auf 1354 Schritte (1352 aus der Berechnung des Blockschadens in einem Quader).
Und für die Koordinaten, die in diesem Diagramm als Beispiel verwendet werden, gibt der obige Code Folgendes aus:
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>
Beachten Sie, wie Woodland Region 123,456 lokalisiert wird, und beachten Sie, dass die endgültige Angabe „jemanden zwischen gefunden“ die tatsächliche Koordinate enthält, die wir ursprünglich eingegeben hatten, nämlich x=157440 z=583680. Darüber hinaus stimmen die RNG-Messungen mit der Hexadezimalzahl in Rot überein: 0xf61dc9 entspricht 16129481 , 0x1700fb entspricht 1507579 und 0xc50d15 entspricht 12913941 . Und für die Samen entspricht 0xed92e70ba4a0 261215197308064 und 0xf61dc9221ba4 entspricht 270607788940196 .
Sie können wahrscheinlich Patches oder Konfigurationsoptionen zum Deaktivieren der RNG-Manipulation finden. So etwas funktioniert zum Patchen von Randar und ist wahrscheinlich der einfachste Weg. Wenn Sie keine einfache Möglichkeit finden, die RNG-Manipulation zu deaktivieren, finden Sie hier den Code, der in der World optimiert werden muss:
Anfällige Version:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ;
}Ändern Sie einfach diese Funktion, um stattdessen jedes Mal einen anderen Zufall zurückzugeben, wenn Sie perfekten Schutz wünschen:
Gepatchte Version:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
return new Random ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
} Das hat möglicherweise keine besonders gute Leistung. Wenn Sie möchten, können Sie also ein neues Feld einführen, separateRandOnlyForWorldGen , das mit nichts anderem geteilt wird, z. B.:
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 ;
}Wenn Sie PaperMC für 1.12.2 verwenden , finden Sie hier einen Patch, den Sie anwenden können. Alternativer Link.
Dies wird ein zusätzlicher Abschnitt sein, in dem ich auf einige zusätzliche Dinge eingehen werde, deren Erklärung aus meiner Sicht sinnvoller wäre, da wir abgesehen von den Grundideen größtenteils Dinge unabhängig voneinander entwickelt haben.
Als Erstes möchte ich das System zum Ermitteln der Koordinaten aus einem Samen erwähnen. Die Mason's verwendeten eine große Nachschlagetabelle und GPU-Verarbeitung, ich verließ mich stattdessen aus Geschwindigkeitsgründen auf einen Cache. Immer wenn ein Treffer auftritt, werden seine Koordinaten und alle Koordinaten innerhalb eines Radius in eine HashMap eingetragen. Die Samen werden in zwei Durchgängen verarbeitet. Der erste Durchgang führt den RNG zurück und prüft, ob der Seed entweder im Cache vorhanden ist oder ob es sich um denselben Seed handelte, der beim letzten Mal verarbeitet wurde, was unterschiedlich betrachtet wird. Der zweite Durchgang erfolgt nur, wenn der erste Durchgang fehlschlägt, ist viel langsamer und verwendet den zuvor beschriebenen relativ teuren Algorithmus. Ein angenehmer Nebeneffekt dieses Systems besteht darin, dass beim ersten Durchgang möglicherweise ein ansonsten „gültiger“, aber weniger wahrscheinlich korrekter Ort „übersprungen“ wird, was bei Fehlalarmen hilfreich ist.
Hier ist dieser Code:
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
