Chaque fois qu'un bloc est brisé dans les versions bêta 1.8 à 1.12.2 de Minecraft, les coordonnées précises de l'objet déposé peuvent révéler l'emplacement d'un autre joueur .
"Randar" est un exploit pour Minecraft qui utilise la réduction de réseau LLL pour déchiffrer l'état interne d'un java.util.Random mal réutilisé dans le serveur Minecraft, puis fonctionne à rebours à partir de cela pour localiser les autres joueurs actuellement chargés dans le monde.
Cliquez ici pour en savoir plus sur Randar sous la forme d'une vidéo YouTube.
Regardez le timelapse :
Voir plus de timelapses ici (sous forme de fichiers) ou ici (sous forme de YouTube).
Le but est de déterminer les emplacements dans le jeu (c'est-à-dire les coordonnées) des autres joueurs dans le monde, quelle que soit leur distance. Nous jouons sur 2b2t, qui est le serveur Minecraft "anarchie" le plus ancien et le plus célèbre (ce qui signifie pas de règles, c'est-à-dire que les joueurs ne sont bannis pour aucune raison). Faire des trucs comme ça est en quelque sorte "le but" sur ce serveur. Sur ce serveur, la seule chose qui assure la sécurité de vos affaires est que la carte est immense (3,6 quadrillions de tuiles carrées) et que personne d'autre ne sait où vous êtes. C'est donc une affaire énorme (une affaire révolutionnaire) d'avoir un exploit coordonné. (en parlant de cela, avant Randar, nous avons également eu un autre exploit de coordination sur 2b2t, Nocom, de 2018 à 2021 ; voir cet article ici, fil HackerNews, YT)
L'erreur dans le code de Minecraft est présente depuis les versions Beta 1.8 (publiées en 2011) jusqu'à 1.12.2 (publiées en 2017, mais 2b2t est resté sur cette version jusqu'au 14 août 2023). L'erreur est que diverses instances du générateur de nombres aléatoires, java.util.Random , sont réutilisées de manière négligente dans diverses parties du code (et elles ne sont pas sécurisées au départ). Plus précisément, il y a une réutilisation du RNG entre la génération du terrain et les actions du jeu telles que l'extraction de blocs.
L'exploit résumé :
World.rand global voit sa graine réinitialisée en fonction des coordonnées du morceau, afin de vérifier où devrait se trouver un Woodland Mansion à proximité (et s'il s'agit de ce morceau en particulier).World.rand.nextFloat() pour choisir les coordonnées XY et Z entre 0 et 1. Le bot enregistre l'horodatage et les valeurs XYZ précises.World.rand qui a provoqué ces trois flottements. D'une manière générale (plus de détails viendront plus tard), l'observation d'une sortie du RNG pourrait impliquer l'un des environ 16 millions d'états internes possibles du RNG. Cependant, nous avons échantillonné la sortie du RNG non pas une mais trois fois de suite (les coordonnées X, Y et Z de l'élément déposé), et nous savons comment l'état interne est mis à jour entre chaque appel (une simple multiplication , ajouter, puis mod); nous pouvons donc utiliser des méthodes de réseau pour le réduire instantanément à la seule possibilité.java.util.Random peut être reculé aussi facilement qu'avant, et en reculant, nous pouvons le trouver en seulement quelques milliers d'étapes (même sur des serveurs très occupés comme 2b2t avec de nombreux joueurs et donc lourds). utilisation du RNG), qui identifie l'heure la plus récente à laquelle l'état interne du RNG a été réinitialisé, et donc l'emplacement du morceau le plus récent chargé sur le serveur.Même si vous jouez sur un serveur qui a été mis à jour vers une version plus récente de Minecraft ou qui a corrigé la manipulation RNG, vos coordonnées sont toujours menacées par Randar en raison de la possibilité d'exploiter les données RNG de manière rétroactive. Certains joueurs de Minecraft utilisent des mods comme ReplayMod qui enregistrent les paquets, et ils peuvent toujours avoir ces fichiers journaux à disposition. Si quelqu'un utilisait un tel mod pendant que vous étiez à votre base, il se peut qu'il ait (sans le savoir) enregistré des données RNG qui pourraient révéler votre position, car briser des blocs est une action extrêmement courante qui est susceptible de se produire dans de tels enregistrements, et chacun de ces blocs break révèle l'état RNG du serveur et donc l'emplacement du morceau le plus récemment chargé. Cela signifie que Randar est un gros problème : en raison de ce risque d'exploitation rétroactive, sur chaque serveur Minecraft, chaque emplacement actif dans les versions bêta 1.8 à 1.12.2 doit être considéré comme compromis, même si le serveur a depuis longtemps été mis à jour après la version 1.12. .2 ou manipulation RNG corrigée.
Si vous souhaitez utiliser vous-même l'exploit Randar , rendez-vous ici où rebane2001 a créé un site Web sur lequel vous pouvez glisser vos fichiers ReplayMod de la 1.12.2 et voir les coordonnées des autres joueurs. Il fonctionne côté client afin que vos enregistrements ne quittent pas votre navigateur. Voici une vidéo de ce à quoi ressemble ce site Web en action, et vous pouvez exécuter l'exemple de fichier ReplayMod à partir de cette vidéo en le téléchargeant ici.
Randar a été découvert par n0pf0x (pcm1k). Cet article a été rédigé par leijurv, avec quelques commentaires supplémentaires à la fin rédigés par n0pf0x. Les exploiteurs étaient 0x22, Babbaj, TheLampGod, leijurv, Negative_Entropy et rebane2001. Voir la vidéo de TheLampGod ici. Regardez la vidéo 100 % humoristique et 0 % factuelle d'HermeticLock ici.
Table des matières : cliquez ici pour en savoir plus sur le code exploitable, ici pour en savoir plus sur la manière dont la réduction de réseau a été utilisée, ici pour voir comment nous avons protégé nos propres caches de Randar, ici si vous souhaitez simplement voir le code d'exploitation complet, ici si vous exécutez un serveur qui est toujours sur une version comprise entre Beta 1.8 et 1.12.2 et que vous souhaitez mettre à jour Randar, ou ici pour plus de détails sur ce que n0pf0x a fait différemment de nous.
Schéma de l'erreur (au format PDF) :
Schéma de l'exploit (au format PDF) :
Schéma d'un exemple concret de l'exploit (au format PDF) :
Minecraft s'appuie sur des nombres aléatoires tout au long du jeu. Nous nous attendons à ce que la plupart d'entre eux soient réellement aléatoires, comme le caractère aléatoire utilisé pour l'apparition des foules et la météo, mais nous nous attendons à ce que certains d'entre eux soient prévisibles, par exemple nous nous attendons à ce que la même graine mondiale au même endroit génère le même terrain. En 2011, lorsque Notch a ajouté pour la première fois des structures au jeu lors de la bêta 1.8, il a accidentellement réutilisé un RNG censé être imprévisible afin de placer des villages dans le monde. Depuis lors, jusqu'à la version 1.13, ce code bâclé a amené la génération mondiale à influencer presque tous les autres événements soi-disant aléatoires du jeu. Il a fallu attendre environ mai 2018 pour qu'Earthcomputer et ses amis découvrent cette erreur, réalisant que les charges de fragments affectent le RNG du jeu de manière observable, voir cette explication. Cependant, ils n'ont pas réalisé, ou n'ont tout simplement jamais révélé publiquement, que vous pouvez également faire cela à l'envers, en déterminant le morceau chargé le plus récemment à partir de l'observation du RNG. Cette découverte, Randar, a été faite par n0pf0x (alias pcm1k) le 7 octobre 2022. Il a publié une courte description cryptée de l'exploit sur Pastebin environ deux semaines plus tard, pour prouver qu'il l'avait découvert à ce moment-là. Il a utilisé l'exploit principalement sur 9b9t, et seulement une quantité relativement faible sur 2b2t et d'autres serveurs. Sur 2b2t, n0p a localisé et exploré divers endroits, pour finalement arriver à une cachette de Gringotts. Il a été repéré par rebane2001 et a d'abord gardé le silence sur la façon dont il a trouvé l'emplacement. Cependant, environ un mois plus tard, il a entamé une conversation avec les SpawnMasons à ce sujet. n0p a révélé qu'il avait utilisé un puissant exploit de coordonnées et a décidé de partager une explication avec nous en avril 2023, car les maçons ont l'expérience de tirer parti des exploits 2b2t à plus grande échelle, il serait donc amusant de voir cela se reproduire, et n0p était ça m'ennuie un peu de toute façon. Nous avons accepté et commencé à enregistrer les coordonnées de dépôt d'objets sur plusieurs comptes qui exploitaient déjà des pierres/pavés 24h/24 et 7j/7 pour un projet sans rapport (il n'y a donc eu aucun changement de comportement). Nous avons réutilisé le système Minecraft sans tête de nocom et ajouté une base de données Postgres pour enregistrer les mesures. Comme indiqué plus loin dans ce fichier Lisez-moi, nous avons utilisé plusieurs itérations de logiciel pour déchiffrer les mesures RNG, pour finalement nous contenter d'un travail par lots asynchrone Cuda. Au fur et à mesure que les mesures fissurées ont été ajoutées à la base de données, nous avons également mis à jour un tableau d'analyse avec des informations de carte thermique qui comptaient les accès à chaque coordonnée à des intervalles de temps, quotidiens et horaires. Cela a permis à une simple interface utilisateur de Plotly Dash de sélectionner des données de carte thermique à partir de plages de temps et de granularités spécifiques pour les afficher dans un navigateur, et cela nous a permis de supprimer tous les spams de chargement de blocs de chasse de cache Elytra en considérant uniquement les coordonnées chargées en plus de quelques heures distinctes. Nous avons ajouté un système d'annotation partagé simple pour garder une trace de ce que nous avons trouvé à chaque point chaud de la carte. Encore une fois en réutilisant Nocom, nous avons des robots Baryton qui automatisent l'ensemble du processus de vol des réserves d'objets et de tri des résultats, complètement AFK. De nombreux maçons ont contribué à cette partie, sans connaître l'exploit, en utilisant des comptes tels que munmap et 1248_test_user . Toutes les réserves de Gringotts rassemblées ont finalement atteint 1,3 milliard d'articles, dont environ la moitié est attribuable à Nocom et l'autre moitié à Randar.
L'historique complet est expliqué dans la vidéo FitMC.
La carte de Minecraft est générée de manière procédurale et essentiellement déterministe, basée sur la graine initiale du monde. Au fur et à mesure que les joueurs explorent la carte, de nouvelles zones sont générées à la demande à mesure que les joueurs s'approchent. Puisque toute la génération est censée être répétable (déterministe), il est tout à fait raisonnable qu'ils aient utilisé java.util.Random dans de nombreux endroits. Ils veulent que ce soit prévisible. C'est pourquoi java.util.Random est utilisé, puisqu'il s'agit d'un PRNG (pas vraiment un RNG). Le P signifie techniquement « pseudo », mais considérez-le comme « prévisible ». RNG prévisible. Il génère des nombres qui semblent aléatoires, mais qui sont en réalité reproductibles avec la même graine de départ.
Minecraft possède diverses structures générées dans le monde, telles que des villages, des monuments océaniques, des forteresses, etc. Celles-ci font partie de la génération procédurale, elles sont donc également placées et générées de manière déterministe.
Il n'y a qu'une douzaine de lignes de code Minecraft nécessaires pour comprendre cela, et je l'ai simplifié et largement commenté :
// (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)
}Ce qui précède est commenté et légèrement modifié pour plus de clarté, mais il est fonctionnellement précis par rapport au code réel.
L'idée est donc de décider où le Woodland Mansion devrait aller dans cette région Woodland (qui fait 80 morceaux sur 80), de vérifier si cet endroit est ici , et si c'est le cas, de générer un Woodland Mansion commençant ici.
Ce code peut paraître un peu idiot, vous pensez peut-être "c'est absurde de faire toutes ces vérifications sur chaque morceau, il suffit de choisir où Woodland Mansions doit aller une fois par région et d'en finir". La raison en est que les morceaux de Minecraft sont générés indépendamment les uns des autres et dans un ordre inconnu, mais nous souhaitons toujours générer un monde déterministe à partir d'une graine donnée. Nous ne savons pas dans quel ordre le joueur va parcourir le monde, et c'est bien de pouvoir générer n'importe quel morceau à la demande, sans état. C'est une bonne expérience de jeu. Ainsi, un code étrange comme celui-ci.
Quoi qu'il en soit, ce code est appelé à chaque chargement de morceau, pour chaque morceau dans un grand carré autour de celui en cours de chargement. C'est un peu compliqué d'expliquer pourquoi, donc je vais surtout l'ignorer (l'idée de base est que ces structures sont (beaucoup) plus grandes qu'un seul morceau, nous devons donc vérifier l'origine d'une structure dans de nombreux morceaux proches afin de générer celui-ci actuel correctement).
Notez que cela n’affecte que l’Overworld. Le Nether est sûr, car toute sa génération de structure a toujours utilisé du RNG sûr. Le chargement des morceaux dans The End est affecté en raison des villes de fin, mais uniquement lors de leur génération initiale, pas à chaque fois qu'ils sont chargés ultérieurement. The End est donc relativement sûr car chaque morceau de votre base n'affecte le RNG qu'une seule fois lors de votre premier chargement. il. Cependant, cela n'est pas totalement infaillible, car les joueurs génèrent généralement de nouveaux morceaux à chaque fois qu'ils se rendent à leur base, et génèrent occasionnellement de nouveaux morceaux lorsqu'ils sont déjà à leur base.
Le problème est que cela modifie la graine du World.rand global. C'est juste un codage paresseux. Tout ce qu'ils font, c'est appeler nextInt quatre fois pour choisir les coordonnées X et Z. Ils auraient pu remplacer Random random = this.world.setRandomSeed(... par Random random = new Random(the same stuff) (en d'autres termes, créer un nouveau Random ici plutôt que de jouer avec celui existant qui est utilisé par tout le reste ? ??).
Fondamentalement, setRandomSeed est appelé afin de vérifier où le Woodland Mansion doit aller. Cela se produit quoi qu’il arrive, à chaque chargement de morceau, partout. Vous n'êtes pas obligé d'être dans/près du Woodland Mansion ou quelque chose comme ça.
Eh bien, il s'avère que World.rand est utilisé dans des centaines d'endroits, et bon nombre de ces endroits peuvent être facilement observés en jouant normalement. Par exemple, lorsque vous exploitez un bloc :
/**
* 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 );
}Encore une fois, légèrement modifié, mais fonctionnellement précis pour ce dont nous parlons.
L'idée ici est que dans Minecraft, lorsque vous exploitez un bloc, il laisse tomber un objet. L'élément est déposé à une position aléatoire dans le bloc. Par exemple, si le bloc était à (10, 20, 30) , l'élément apparaîtra quelque part entre (10.25, 20.25, 30.25) et (10.75, 20.75, 30.75) .
Et l'emplacement exact de cet élément est choisi en appelant world.rand.nextFloat() trois fois de suite, pour le X, le Y et le Z.
C'est tout le code Minecraft nécessaire !
Maintenant, j'ai dit que nous pouvons faire quelque chose avec ces appels nextFloat . Tout d’abord, voyons si nous pouvons « travailler à rebours » pour voir quels sont les appels nextFloat . C'est une chance, mais nous le pouvons. Remarque dans le code ci-dessus : le flottant aléatoire est multiplié par 0,5, puis ajouté à 0,25. L’idée est de passer d’un nombre aléatoire compris entre 0 et 1 à un nombre aléatoire compris entre 0,25 et 0,75. Vous pourriez être inquiet, car si vous deviez diviser un entier par deux, vous perdriez un peu d'information puisque le résultat est arrondi à l'inférieur. Heureusement, multiplier un float par 0,5 est totalement réversible, car cela décrémente simplement l'exposant tout en laissant la mantisse intacte. Ensuite, le flotteur est lancé en double, ce qui offre beaucoup plus de précision. 0,25 est ajouté, puis la coordonnée du bloc est ajoutée. Ensuite, il est envoyé au client via le réseau en toute précision. Le résultat : tout ce processus est réversible afin que nous puissions obtenir exactement les trois flotteurs produits par World.rand.nextFloat() .
Comment java.util.Random génère-t-il des flotteurs ? Eh bien en fait, c'est assez simple. Il génère un entier compris entre 0 et 2^24, puis le divise par 2^24 (ce qui donne un nombre compris entre 0 et 1). Comment obtient-il cet entier aléatoire ? Aussi assez simple ! C'est un générateur congruentiel linéaire (LCG). Cela signifie que la graine suivante est la graine précédente multipliée par quelque chose, plus quelque chose d'autre, modulo quelque chose d'autre.
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
}Dans ce cas, le multiplicateur est 25214903917, l'addition est 11 et le module est 2^48.
Avec le float qui en résulte, nous pouvons le multiplier par 2 ^ 24 pour récupérer le randomInteger, et donc obtenir la "moitié supérieure" (les 24 bits les plus significatifs) de la graine de 48 bits.
En bref, d'après notre mesure, nous apprenons que la graine est comprise entre measuredRandomInteger * 2^24 et (measuredRandomInteger + 1) * 2^24 .
Et nous pouvons faire cela trois fois de suite, pour le X, le Y et le Z.
Et nous savons qu'entre le X et le Y, et entre le Y et le Z, la graine a été mise à jour selon newSeed = (oldSeed * 25214903917 + 11) mod 2^48
Je dois mentionner qu'une option valide est une boucle for qui essaie les 2 ^ 24 bits inférieurs possibles. Pour les programmeurs qui lisent ceci, j'espère que cela montre clairement quel est le problème :
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 ;
}
}Cela fonctionnerait et fonctionne, mais ce n'est pas si rapide ni si amusant. Nous utilisons donc plutôt des treillis !
Cependant, j'ai l'impression que je dois y aller un peu dans le désordre. La partie réduction du réseau entre en jeu ici, mais c'est vraiment compliqué et je parie que cela aurait une faible rétention des lecteurs et je ne veux pas vous perdre. Je vais donc simplement vous donner cette solution en boucle for (qui fonctionne) et passer à l'étape suivante de l'exploit. L'explication de la méthode de réduction de réseau viendra juste après :)
Que fait-on de cette graine une fois que nous l’avons ?
Tout d’abord, notons que nous pouvons faire reculer le LCG. Évidemment, l’addition de onze est réversible, mais la multiplication par ce grand nombre est-elle réversible ? Notre multiplicateur 25214903917 est un nombre impair, ce qui signifie qu'il n'est pas divisible par deux et qu'il ne partage donc aucun facteur avec notre module 2^48 (puisque 2^48 n'est littéralement qu'un groupe de deux). Puisqu'il est relativement premier au module, nous pouvons l'inverser, ce qui signifie trouver un autre nombre x qui satisfait x * 25214903917 - 1 est divisible par 2 ^ 48. Ou en d'autres termes, 25214903917 * x mod 2^48 = 1 . Ce numéro est 246154705703781 . Cela permet d'inverser la multiplication car si nous avons, par exemple, secret * 25214903917 et que nous voulons comprendre secret , nous pouvons simplement calculer secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret .
Ok, nous pouvons donc faire avancer et reculer la graine interne de java.util.Random . L'avant est newSeed = (oldSeed * 25214903917 + 11) mod 2^48 et l'arrière est oldSeed = ((newSeed - 11) * 246154705703781) mod 2^48 . Et cela fonctionne parce que ces nombres 25214903917 et 246154705703781 , lorsqu'ils sont multipliés ensemble, donnent 1 lorsque vous le prenez mod 2 ^ 48.
Maintenant, en reculant, nous aimerions vérifier à chaque étape si cette graine pourrait signifier qu'un contrôle de Woodland Mansion a été récemment effectué quelque part dans le monde (tout l'intérêt de l'exploit). Comment fait-on cela ?
Le monde de Minecraft s'étend de -30 millions à +30 millions de blocs. Chaque "région forestière" (une zone du monde où un seul manoir forestier est placé au hasard, selon le code indiqué précédemment) mesure 80 morceaux sur 80, soit 1 280 blocs sur 1 280. Il s'agit de 23437,5 régions boisées, mais pour tout notre code, nous avons simplement arrondi à 23440 car c'est un nombre rond et même si votre joueur ne peut pas voyager au-delà de 30 millions, vous chargez des morceaux au-delà simplement en vous tenant près de lui, et nous je ne voulais pas avoir à m'inquiéter de tout ça.
Donc, -23440 à +23440 sur les axes X et Z. Cela représente (23440*2+1)^2 (alias 2197828161 ) régions forestières possibles, dont chacune génère une "graine de manoir" unique (définie comme une graine qui révèle que quelqu'un vient de charger un morceau dans une certaine région forestière). Nous devons être capables de vérifier si quelque chose est une graine de manoir. Pourrions-nous parcourir les 2,2 milliards de graines de manoir pour vérifier chacune d'elles ? Ce serait trop lent. Pourrait-il créer un HashSet<Long> avec 2,2 milliards d'entrées ? Cela prendrait trop de RAM même en utilisant une carte de chronique comme nous l'avons fait dans nocom, et même en C++ en utilisant abseil-cpp il utilisait comme 50 Go de RAM. Et c'est sans parler de l'autre partie : nous voulons en fait savoir où ils se trouvent dans le monde (c'est tout l'intérêt). Il ne suffit donc pas d'apprendre qu'il s'agit d'une graine de manoir, nous voulons également savoir (efficacement) quelle région forestière l'a provoquée.
Rappelez-vous la fonction qui va de Woodland Region à la graine du manoir (remarque : j'ai maintenant combiné quelques constantes depuis le code ci-dessus pour plus de simplicité, cette équation est maintenant spécialisée dans la graine de 2b2t ) :
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
(le nombre -4172144997891902323 vient du -4172144997902289642 + 10387319 , qui est la graine mondiale 2b2t + la valeur magique utilisée pour ensemencer la région boisée (comme indiqué précédemment). Pour tout autre monde, vous mettriez simplement votre propre graine dans cette équation. .)
Nous ne pouvons pas faire grand-chose avec la coordonnée x, puisqu'elle est multipliée par un nombre pair. Mais quel est ce coefficient sur la coordonnée z ? Cela ressemble à un nombre impair !!! Utilisons la même astuce que précédemment pour l'inverser à nouveau, et nous obtenons 211541297333629 .
Imaginons que nous ayons une graine donnée. Et si nous pouvions simplement parcourir toutes les coordonnées X possibles de -23440 à +23440, et pour chacune d'elles, calculer quelle serait la coordonnée Z de la région Woodland, SI elle avait cette graine de manoir . En d’autres termes, l’équation ci-dessus nous donne seed si nous connaissons x et z , mais pouvons-nous faire une équation qui nous donne z si nous connaissons seed et x ? Réponse : oui. Nous réorganisons simplement l'équation ci-dessus et utilisons le fait que le coefficient de Z est inversible mod 2^48 puisque c'est un nombre impair.
L'équation est :
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
C'est donc une très bonne solution car au lieu de deux boucles imbriquées (une pour X et une pour Z) qui font un total de 2,2 milliards d'itérations, nous pouvons avoir une seule boucle for pour X qui ne fait que 46 881 itérations. Le voici en 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 ;
} (remarque : l'étrange << 16 >> 16 fait le mod 2 ^ 48, mais nous voulons en fait le faire en utilisant des types signés afin d'obtenir toujours la bonne réponse lorsque z est compris entre -23440 et 0, c'est une façon de sign-étend le nombre de 48 bits à 64 bits, en remplissant les 16 bits supérieurs avec le bit de signe correct pour le complément à deux)
Donc cela fonctionne et c'est raisonnablement rapide... pour une seule graine. Mais rappelez-vous que nous reculons le RNG de potentiellement des milliers d'étapes et que nous effectuons cette vérification à chaque étape jusqu'à ce que nous trouvions une correspondance. À l'époque, nous utilisions une gouttelette DigitalOcean merdique sur leur niveau le plus bas, et cela était en fait en retard sur tout et ne pouvait pas suivre le temps réel (les robots extrayaient de nombreux blocs par seconde, chaque bloc prenant des milliers d'étapes pour se fissurer, et chaque étape rng prend 23440*2+1 opérations pour vérifier, multipliez-les ensemble et vous obtenez des centaines de millions d'opérations par seconde, vous voyez donc pourquoi cela a eu des problèmes sur un VPS merdique, surtout quand ce VPS essaie également d'exécuter plusieurs instances sans tête de Minecraft).
Quoi qu'il en soit, nous sommes passés à une approche de table de recherche et l'avons réécrit dans Cuda pour qu'il s'exécute sur mon bureau en tant que travail par lots toutes les quelques minutes. Cela peut littéralement faire des millions par seconde, car chacun des milliers de cœurs cuda peut travailler en parallèle sur sa propre graine. Voici l'idée : la clé de la table de recherche correspond aux 32 bits inférieurs de la graine du manoir et la valeur est la coordonnée X de la région Woodland. Cette table de recherche fonctionne sans collision car chaque graine de manoir a, d'une manière ou d'une autre , 32 bits inférieurs uniques. Je ne comprends pas pourquoi c'est vrai, c'est fascinant. On pourrait penser que ça ne marcherait pas. Mais je pense que les coefficients 341873128712 et 132897987541 ont peut-être été spécialement choisis pour que cela fonctionne ? Par exemple, si vous avez 2,2 milliards de billes et 4,3 milliards de seaux et que vous placez indépendamment chaque bille dans un seau aléatoire, quelles sont les chances que chaque bille obtienne son propre seau ? Essentiellement zéro. Vers la fin, chaque nouvelle bille a plus de 50 % de chances de toucher un seau déjà rempli. Pourtant, il est clair que ces éléments ne sont pas aléatoires de manière indépendante, donc cela fonctionne d’une manière ou d’une autre. Ironiquement, si vous lisez ceci et comprenez comment cela fonctionne ou pourquoi ces deux coefficients spécifiques font que cela fonctionne, faites-le moi savoir. Quoi qu'il en soit, ça marche. La table de recherche contient 2 ^ 32 entrées, et chaque entrée fait 2 octets (puisqu'il s'agit simplement d'un nombre compris entre -23440 et +23440), cela nécessite donc environ 9 Go de VRAM sur votre GPU.
La fonction de vérification de Woodland ressemble maintenant à (encore une fois, c'est le code réel mais simplifié, toutes les aides et constantes intégrées, etc.) :
__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;
}Cela fonctionne très bien dans des lots géants et peut craquer de l'ordre de dix millions de graines par seconde sur un 3090. Il s'avère que ce n'est pas trop grave lorsque certains des fils d'une chaîne se terminent prématurément et que nous ne pouvons pas vraiment faire c'est plus rapide que ça. (la raison est que nous ne pouvons fondamentalement pas savoir à l'avance quelles graines feront plus/moins de pas).
Eh bien, c'est à peu près tout. Compte tenu de la graine, c'est ainsi que nous obtenons la région forestière du monde où le chargement de fragments le plus récent s'est produit. En d’autres termes, nous venons d’apprendre que la dernière fois que quelqu’un s’est promené sur 2b2t et a chargé une nouvelle zone du monde, c’était quelque part dans cette région boisée de blocs de 1 280 x 1 280 que nous venons d’identifier. (c'est suffisamment précis pour que leur localisation ne prenne que quelques minutes de recherche)
En pratique, combien d’étapes RNG ont été nécessaires ? Au bas de l'échelle, les mesures fiables commencent à 4 étapes RNG, tout ce qui se trouve en dessous est une erreur de mesure/un bruit aléatoire, que nous connaissons car le code de Woodland Mansion appelle immédiatement rand.nextInt quatre fois avant qu'il nous soit possible de le mesurer. En moyenne, il y a environ 128 000 étapes entre chaque graine Woodland, mais en pratique, la grande majorité du temps sur 2b2t, nous trouvons une graine Woodland en quelques dizaines d'étapes. Cela est dû aux détails de ce qui se passe dans quel ordre dans un tick Minecraft. Techniquement, notre mesure a lieu au tout début du tick, puisque c'est là que les paquets destinés à casser les blocs sont traités. Généralement, un morceau a été chargé dans l’historique très récent lors du tick précédent. Cependant, parfois, un événement peut provoquer de nombreuses étapes RNG entre les deux. Nous pensons que cet événement est constitué d'explosions, comme le fait que quelqu'un fasse exploser un cristal d'extrémité en le frappant, ou éventuellement des crânes flétris. Des explosions de cristaux de fin se produiraient également pendant le traitement des paquets à partir du paquet de frappe du joueur, et le nombre d'étapes RNG s'aligne également à 1354 étapes (1352 à partir du calcul des dégâts de bloc dans un cuboïde).
Et sur les coordonnées utilisées comme exemple concret dans ce diagramme, voici ce que le code ci-dessus produit :
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>
Notez comment il localise la région boisée 123,456 et comment le dernier « quelqu'un localisé entre » inclut la coordonnée réelle que nous avions initialement saisie, qui était x=157440 z=583680. De plus, les mesures RNG correspondent à l'hexadécimal en rouge : 0xf61dc9 est égal à 16129481 , 0x1700fb est égal à 1507579 et 0xc50d15 est égal à 12913941 . Et pour les graines, 0xed92e70ba4a0 est égal à 261215197308064 et 0xf61dc9221ba4 est égal à 270607788940196 .
Vous pouvez probablement trouver des correctifs ou des options de configuration pour désactiver la manipulation RNG, quelque chose comme ça fonctionnera pour patcher Randar et c'est probablement le moyen le plus simple. Si vous ne trouvez pas de moyen simple de désactiver la manipulation RNG, voici le code qui doit être modifié dans la classe World :
Version vulnérable :
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ;
}Modifiez simplement cette fonction pour renvoyer un Random différent à chaque fois, si vous souhaitez une protection parfaite :
Version corrigée :
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
return new Random ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
} Cela n'aura peut-être pas d'excellentes performances, donc si vous le souhaitez, vous pouvez introduire un nouveau champ, separateRandOnlyForWorldGen , qui n'est partagé avec rien d'autre, par exemple :
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 ;
}Si vous utilisez PaperMC pour 1.12.2 , voici un correctif que vous pouvez appliquer. Lien alternatif.
Ce sera une section supplémentaire dans laquelle je passerai en revue quelques éléments supplémentaires qu'il serait plus logique d'expliquer de mon point de vue, car outre les idées de base, nous avons pour la plupart développé des choses de manière indépendante.
La première chose que je voudrais mentionner, c'est le système de localisation des coordonnées à partir d'une graine. Les Mason ont utilisé une grande table de recherche et un traitement GPU, je me suis plutôt appuyé sur un cache pour la vitesse. Chaque fois qu'un hit se produit, ses coordonnées et toutes les coordonnées dans un rayon sont placées dans un HashMap. Les graines sont traitées en deux passes. Le premier passage fait reculer le RNG et vérifie si la graine est présente dans le cache ou s'il s'agit de la même graine traitée la dernière fois, ce qui est considéré différemment. La deuxième passe n’a lieu que si la première échoue, est beaucoup plus lente et utilise l’algorithme relativement coûteux décrit précédemment. Un effet secondaire agréable de ce système est que le premier passage a le potentiel de « sauter » un emplacement autrement « valide », mais moins susceptible d'être correct, ce qui aide avec les faux positifs.
Voici ce 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
