Cada vez que se rompe un bloque en las versiones Beta 1.8 a 1.12.2 de Minecraft, las coordenadas precisas del elemento caído pueden revelar la ubicación de otro jugador .
"Randar" es un exploit para Minecraft que utiliza la reducción de celosía LLL para descifrar el estado interno de un java.util.Random reutilizado incorrectamente en el servidor de Minecraft, luego trabaja hacia atrás para localizar a otros jugadores actualmente cargados en el mundo.
Haga clic aquí para obtener más información sobre Randar en forma de vídeo de YouTube.
Mira el timelapse:
Vea más timelapses aquí (como archivos) o aquí (como YouTube).
El objetivo es determinar las ubicaciones dentro del juego (es decir, las coordenadas) de los otros jugadores en el mundo, sin importar qué tan lejos estén. Estamos jugando en 2b2t, que es el servidor de Minecraft "anárquico" más antiguo y famoso (lo que significa que no hay reglas, es decir, los jugadores no están baneados por ningún motivo). Hacer cosas como esta es "el objetivo" de este servidor. En este servidor, lo único que mantiene tus cosas seguras es que el mapa es enorme (3,6 mil billones de mosaicos cuadrados) y nadie más sabe dónde estás. Por lo tanto, es muy importante (un acuerdo revolucionario) tener un exploit coordinado. (Hablando de eso, antes de Randar también tuvimos otro exploit de coordinación en 2b2t, Nocom, de 2018 a 2021; vea ese artículo aquí, hilo de HackerNews, YT)
El error en el código de Minecraft está presente desde las versiones Beta 1.8 (lanzada en 2011) hasta 1.12.2 (lanzada en 2017, pero 2b2t permaneció en esta versión hasta el 14 de agosto de 2023). El error es que varias instancias del generador de números aleatorios, java.util.Random , se reutilizan descuidadamente en varias partes del código (y, para empezar, son inseguras). Específicamente, hay reutilización de RNG entre la generación del terreno y las acciones del juego, como la extracción de bloques.
El exploit se resume:
World.rand global tiene su semilla reiniciada en función de las coordenadas del fragmento, para verificar dónde debería estar una Mansión Woodland cercana (y si es este fragmento en particular).World.rand.nextFloat() para elegir las coordenadas XY y Z entre 0 y 1. El bot registra la marca de tiempo y los valores XYZ precisos.World.rand que causó esos tres flotadores. En términos generales (más detalles se darán más adelante), observar una salida del RNG podría implicar cualquiera de los aproximadamente 16 millones de posibles estados internos del RNG. Sin embargo, hemos muestreado la salida del RNG no sólo una sino tres veces seguidas (las coordenadas X, Y y Z del elemento eliminado), y sabemos cómo se actualiza el estado interno entre cada llamada (una simple multiplicación). , agregar, luego modificar); por lo tanto, podemos usar métodos de celosía para reducirlo instantáneamente a la única posibilidad.java.util.Random se puede retroceder tan fácilmente como avanzar, y al retroceder podemos encontrarlo en sólo unos pocos miles de pasos (incluso en servidores ocupados como 2b2t con muchos jugadores y, por lo tanto, pesados). uso de RNG), que identifica la hora más reciente en que se restableció el estado interno del RNG y, por lo tanto, la ubicación del fragmento más reciente que se cargó en el servidor.Incluso si juegas en un servidor que se ha actualizado a una versión más reciente de Minecraft, o que ha parcheado la manipulación del RNG, tus coordenadas aún están en riesgo por parte de Randar debido a la capacidad de explotar los datos del RNG de forma retroactiva. Algunos jugadores de Minecraft usan mods como ReplayMod que registran paquetes, y es posible que aún tengan esos archivos de registro. Si alguien estaba usando un mod de este tipo mientras estabas en tu base, es posible que haya grabado (sin saberlo) datos RNG que podrían revelar tu ubicación, porque romper bloques es una acción extremadamente común que probablemente haya ocurrido en tales grabaciones, y cada uno de esos bloques break revela el estado RNG del servidor y, por lo tanto, la ubicación del fragmento cargado más recientemente. Esto significa que Randar es un problema bastante importante: debido a este riesgo de explotación retroactiva, en cada servidor de Minecraft, cada ubicación que estuvo activa en las versiones Beta 1.8 a 1.12.2 debe considerarse comprometida, incluso si el servidor se actualizó hace mucho tiempo después de la versión 1.12. .2 o manipulación de RNG parcheada.
Si desea utilizar el exploit Randar usted mismo , vaya aquí donde rebane2001 ha creado un sitio web donde puede arrastrar sus archivos ReplayMod desde 1.12.2 y ver las coordenadas de otros jugadores. Se ejecuta en el lado del cliente para que sus grabaciones no salgan de su navegador. Aquí hay un video de cómo se ve ese sitio web en acción, y puede ejecutar el archivo ReplayMod de ejemplo de ese video descargándolo aquí.
Randar fue descubierto por n0pf0x (pcm1k). Este artículo fue escrito por leijurv, con algún comentario adicional al final escrito por n0pf0x. Los explotadores fueron 0x22, Babbaj, TheLampGod, leijurv, Negative_Entropy y rebane2001. Vea el vídeo de TheLampGod aquí. Vea el video 100% humorístico y 0% factual de HermeticLock aquí.
Tabla de contenidos: haga clic aquí para conocer el código explotable con más detalle, aquí para conocer cómo se utilizó la reducción de celosía, aquí para ver cómo protegimos nuestros propios escondites de Randar, aquí si solo desea ver el código de explotación completo, aquí si ejecuta un servidor que todavía tiene una versión entre Beta 1.8 y 1.12.2 y desea parchear Randar, o aquí para obtener detalles sobre lo que n0pf0x hizo de manera diferente a nosotros.
Diagrama del error (como PDF):
Diagrama del exploit (como PDF):
Diagrama de un ejemplo trabajado del exploit (como PDF):
Minecraft se basa en números aleatorios durante todo el juego. Esperamos que la mayoría de ellos sean realmente aleatorios, como la aleatoriedad utilizada para el desove de los mobs y el clima, pero esperamos que algunos de ellos sean predecibles, por ejemplo, esperamos que la misma semilla mundial en el mismo lugar genere el mismo terreno. En 2011, cuando Notch agregó estructuras al juego por primera vez durante la Beta 1.8, accidentalmente reutilizó un RNG que se supone que es impredecible para ubicar aldeas en el mundo. Desde entonces, hasta la versión 1.13, este código descuidado ha provocado que la generación mundial influya en casi todos los demás eventos supuestamente aleatorios del juego. Fue necesario hasta mayo de 2018 aproximadamente para que Earthcomputer y sus amigos descubrieran este error y se dieran cuenta de que las cargas fragmentadas afectan el RNG del juego de una manera observable; consulte esta explicación. Sin embargo, no se dieron cuenta, o simplemente nunca lo revelaron públicamente, que también se puede hacer esto al revés, determinando el fragmento cargado más reciente a partir de la observación del RNG. Ese descubrimiento, Randar, fue realizado por n0pf0x (también conocido como pcm1k) el 7 de octubre de 2022. Publicó una breve descripción cifrada del exploit en Pastebin unas dos semanas después, para demostrar que lo descubrió en ese momento. Usó el exploit principalmente en 9b9t, y sólo una cantidad relativamente pequeña en 2b2t y otros servidores. En 2b2t, n0p localizó y exploró varios lugares, y finalmente llegó a un escondite de Gringotts. Fue descubierto por rebane2001 e inicialmente no dijo nada sobre cómo encontró la ubicación. Sin embargo, aproximadamente un mes después, comenzó una conversación con los SpawnMasons al respecto. n0p reveló que había usado un poderoso exploit de coordenadas y decidió compartir una explicación con nosotros en abril de 2023, porque los albañiles tienen experiencia previa aprovechando exploits 2b2t a mayor escala, por lo que sería divertido ver que eso sucediera nuevamente, y n0p fue Me aburro un poco de todos modos. Aceptamos y comenzamos a registrar las coordenadas de caída de elementos en varias cuentas que ya estaban extrayendo piedra/adoquines las 24 horas del día, los 7 días de la semana para un proyecto no relacionado (por lo tanto, no hubo ningún cambio en el comportamiento). Reutilizamos el sistema Minecraft sin cabeza de nocom y agregamos una base de datos Postgres para registrar las medidas. Como se analiza más adelante en este archivo Léame, realizamos varias iteraciones de software para descifrar las mediciones de RNG y finalmente nos decidimos por un trabajo por lotes asíncrono de Cuda. A medida que se agregaron mediciones descifradas a la base de datos, también actualizamos una tabla de análisis con información de mapa de calor que contaba los impactos en cada coordenada en intervalos de todos los tiempos, diarios y por horas. Esto permitió que una interfaz de usuario simple de Plotly Dash seleccionara datos de mapas de calor de rangos de tiempo y granularidades específicos para mostrarlos en un navegador, y nos permitió eliminar todo el spam de carga de fragmentos de caza de alijo de Elytra considerando solo las coordenadas que se cargaron en más de unas pocas horas distintas. Agregamos un sistema simple de anotaciones compartidas para realizar un seguimiento de lo que encontramos en cada punto de acceso en el mapa. Nuevamente reutilizando de Nocom, tenemos robots Baritone que automatizan todo el proceso de robar objetos escondidos y ordenar los resultados, completamente AFK. Muchos albañiles ayudaron con esta parte, sin conocer el exploit, usando cuentas como munmap y 1248_test_user . Todos los alijos de Gringotts juntos finalmente crecieron hasta 1.300 millones de artículos, de los cuales aproximadamente la mitad es atribuible a Nocom y la otra mitad a Randar.
La historia completa se explica en el vídeo de FitMC.
El mapa de Minecraft se genera procedimentalmente y es esencialmente determinista en función de la semilla inicial del mundo. A medida que los jugadores exploran el mapa, se generan nuevas áreas a medida que los jugadores se acercan. Dado que toda la generación debe ser repetible (determinista), es perfectamente razonable que hayan usado java.util.Random en muchos lugares. Quieren que sea predecible. Es por eso que se usa java.util.Random , ya que es un PRNG (no realmente un RNG). La P técnicamente significa "pseudo", pero considérelo "predecible". RNG predecible. Genera números que parecen aleatorios, pero que en realidad son repetibles dada la misma semilla inicial.
Minecraft tiene varias estructuras que se generan en el mundo, como aldeas, monumentos oceánicos, fortalezas, etc. Estas son parte de la generación procedimental, por lo que también se ubican y generan de manera determinista.
Sólo se necesitan una docena de líneas de código de Minecraft para entender esto, y lo he simplificado y comentado mucho:
// (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)
}Lo anterior está comentado y ligeramente modificado para mayor claridad, pero es funcionalmente exacto al código real.
Entonces, la idea es decidir dónde debe ir Woodland Mansion en esta región de Woodland (que tiene 80 por 80 fragmentos), verificar si ese lugar está aquí y, de ser así, generar una Woodland Mansion comenzando justo aquí.
Este código puede parecer un poco tonto, podrías estar pensando "es absurdo hacer todas estas comprobaciones en cada fragmento, simplemente elige dónde debe ir Woodland Mansions una vez por región y listo". La razón es que los fragmentos de Minecraft se generan independientemente unos de otros y en un orden desconocido, pero aun así queremos generar un mundo determinista a partir de una semilla determinada. No sabemos en qué orden el jugador caminará por el mundo, y es bueno poder generar cualquier fragmento bajo demanda sin estado. Es una buena experiencia de juego. Por lo tanto, un código de aspecto extraño como este.
De todos modos, ese código se llama en cada carga de fragmentos, para cada fragmento en un cuadrado grande alrededor del que se está cargando. Es un poco complicado explicar por qué, así que lo omitiré (la idea básica es que estas estructuras son (mucho) más grandes que un fragmento, por lo que debemos verificar el origen de una estructura en muchos fragmentos cercanos para poder generar este actual correctamente).
Tenga en cuenta que esto sólo afecta al Overworld. El Nether es seguro, ya que toda su generación de estructuras siempre ha utilizado RNG seguro. La carga de fragmentos en The End se ve afectada debido a las ciudades finales, pero solo en su generación inicial, no cada vez que se cargan posteriormente, por lo que The End es relativamente seguro porque cada fragmento en tu base solo afecta el RNG una vez cuando cargas por primera vez. él. Sin embargo, esto no es totalmente infalible, ya que los jugadores suelen generar nuevos fragmentos cada vez que viajan a su base y, ocasionalmente, generan nuevos fragmentos mientras ya están en su base.
El problema es que modifica la semilla del World.rand global. Esto es simplemente codificación diferida. Todo lo que hacen es llamar nextInt cuatro veces para elegir las coordenadas X y Z. Podrían haber reemplazado Random random = this.world.setRandomSeed(... con Random random = new Random(the same stuff) (en otras palabras, ¿crear un nuevo Random aquí en lugar de alterar el existente que usa todo lo demás? ??).
Fundamentalmente, se llama a setRandomSeed para comprobar dónde debe ir Woodland Mansion. Sucede pase lo que pase, en cada carga parcial, en todas partes. No tienes que estar parado dentro o cerca de Woodland Mansion ni nada por el estilo.
Bueno, resulta que World.rand se usa literalmente en cientos de lugares, y muchos de esos lugares se pueden observar fácilmente jugando normalmente. Por ejemplo, cuando extraes un bloque:
/**
* 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 );
}Nuevamente, ligeramente modificado, pero funcionalmente preciso para lo que estamos hablando.
La idea aquí es que en Minecraft, cuando extraes un bloque, se suelta un elemento. El elemento se suelta en una posición aleatoria dentro del bloque. Por ejemplo, si el bloque estaba en (10, 20, 30) , el elemento aparecerá en algún lugar entre (10.25, 20.25, 30.25) y (10.75, 20.75, 30.75) .
Y la ubicación exacta de ese elemento se elige llamando world.rand.nextFloat() tres veces seguidas, para X, Y y Z.
¡Eso es todo el código de Minecraft que se necesita!
Ahora dije que podemos hacer algo con estas llamadas nextFloat . Primero, veamos si podemos "trabajar hacia atrás" para ver cuáles son las llamadas nextFloat . Es bastante afortunado, pero realmente podemos. Nota en el código anterior: el valor flotante aleatorio se multiplica por 0,5 y luego se suma a 0,25. La idea es pasar de un número aleatorio entre 0 y 1 a un número aleatorio entre 0,25 y 0,75. Quizás te preocupes, porque si dividieras un número entero entre dos perderías un poco de información ya que el resultado se redondea hacia abajo. Afortunadamente, multiplicar un flotante por 0,5 es totalmente reversible, ya que simplemente disminuye el exponente y deja la mantisa intacta. Luego, el flotador se convierte en un doble, que tiene mucha más precisión. Se suma 0,25 y luego se añade la coordenada del bloque. Luego, se envía al cliente a través de la red con total precisión. El resultado: todo este proceso es reversible, por lo que podemos obtener exactamente los tres flotadores que produjo World.rand.nextFloat() .
¿Cómo genera java.util.Random flotadores? Bueno, en realidad es bastante simple. Genera un número entero entre 0 y 2^24, luego lo divide por 2^24 (lo que da como resultado un número entre 0 y 1). ¿Cómo obtiene ese número entero aleatorio? ¡También bastante simple! Es un generador lineal congruencial (LCG). Eso significa que la siguiente semilla es la semilla anterior multiplicada por algo, más algo más, módulo algo más.
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
}En este caso, el multiplicador es 25214903917, el sumando es 11 y el módulo es 2^48.
Con el valor flotante que surgió de esto, podemos multiplicarlo por 2^24 para recuperar el número entero aleatorio y, por lo tanto, obtener la "mitad superior" (los 24 bits más significativos) de la semilla de 48 bits.
En resumen, de nuestra medición, aprendemos que la semilla está entre measuredRandomInteger * 2^24 y (measuredRandomInteger + 1) * 2^24 .
Y podemos hacer esto tres veces seguidas, para la X, la Y y la Z.
Y sabemos que entre la X y la Y, y entre la Y y la Z, la semilla se actualizó según newSeed = (oldSeed * 25214903917 + 11) mod 2^48
Debo mencionar que una opción válida es un bucle for que prueba los 2^24 bits inferiores posibles. Para los programadores que lean esto, espero que esto aclare cuál es el problema:
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 ;
}
}Esto funcionaría, y funciona, pero no es tan rápido ni tan divertido. ¡Así que usamos celosías en su lugar!
Sin embargo, siento que tengo que salirme un poco del orden. La parte de reducción de celosía viene aquí, pero es realmente complicada y apuesto a que tendría una baja retención de lectores y no quiero perderlos. Así que simplemente le daré esa solución de bucle for (que SÍ funciona) y continuaré con el siguiente paso del exploit. La explicación del método de reducción de celosía vendrá justo después :)
¿Qué hacemos con esta semilla una vez que la tenemos?
Primero, tenga en cuenta que podemos hacer retroceder la LCG. Obviamente, sumar once es reversible, pero ¿es reversible multiplicar por ese gran número? Nuestro multiplicador 25214903917 es un número impar, lo que significa que no es divisible por dos y, por lo tanto, no comparte ningún factor con nuestro módulo 2^48 (ya que 2^48 es literalmente solo un grupo de dos). Como es relativamente primo con respecto al módulo, podemos invertirlo, lo que significa encontrar otro número x que satisfaga x * 25214903917 - 1 es divisible por 2^48. O en otras palabras, 25214903917 * x mod 2^48 = 1 . Ese número es 246154705703781 . Esto ayuda a invertir la multiplicación porque si tenemos, por ejemplo, secret * 25214903917 y queremos descubrir secret , podemos simplemente calcular secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret .
Bien, entonces podemos avanzar la semilla interna de java.util.Random tanto hacia adelante como hacia atrás. Hacia delante es newSeed = (oldSeed * 25214903917 + 11) mod 2^48 y hacia atrás es oldSeed = ((newSeed - 11) * 246154705703781) mod 2^48 . Y esto funciona porque esos números 25214903917 y 246154705703781 , cuando se multiplican juntos, dan como resultado 1 cuando se toma mod 2^48.
Ahora, a medida que retrocedemos, nos gustaría comprobar en cada paso si esta semilla podría significar que se realizó recientemente una verificación de Woodland Mansion en algún lugar del mundo (el objetivo principal del exploit). ¿Cómo hacemos eso?
El mundo de Minecraft oscila entre -30 millones y +30 millones de bloques. Cada "región de Woodland" (un área del mundo donde se coloca una sola Mansión Woodland al azar, según el código mostrado anteriormente) tiene 80 por 80 fragmentos, que son 1280 por 1280 bloques. Estas son 23437,5 regiones de Woodland, pero para todo nuestro código simplemente redondeamos a 23440 porque es un número redondo y aunque tu jugador no puede viajar más allá de 30 millones, cargas fragmentos más allá simplemente parándote cerca de él, y simplemente No quería tener que preocuparme por todo eso.
Entonces, -23440 a +23440 en los ejes X y Z. Esas son (23440*2+1)^2 (también conocida como 2197828161 ) posibles regiones de Woodland, cada una de las cuales genera una "semilla de mansión" única (definida como una semilla que revela que alguien acaba de cargar un trozo en una determinada región de Woodland). Necesitamos poder comprobar si algo es una semilla de mansión. ¿Podríamos recorrer los 2.200 millones de semillas de mansión para comprobar cada una de ellas? Sería demasiado lento. ¿Podría crear un HashSet con 2.200 millones de entradas? Consumiría demasiada RAM incluso usando Chronicle Map como lo hicimos en Nocom, e incluso en C++ usando abseil-cpp usaba como 50 GB de RAM. Y eso sin mencionar la otra parte: en realidad queremos saber dónde están en el mundo (ese es el punto). Así que no es suficiente saber que se trata de una semilla de mansión, también queremos saber (de manera eficiente) qué región de Woodland la causó.
Recuerde la función que va desde la región Woodland hasta la semilla de la mansión (nota: ahora he combinado algunas constantes desde el código anterior para simplificar, esta ecuación ahora está especializada en la semilla de 2b2t ):
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
(el número -4172144997891902323 proviene de -4172144997902289642 + 10387319 , que es la semilla mundial 2b2t + el valor mágico utilizado para sembrar la región de Woodland (como se mostró anteriormente). Para cualquier otro mundo, simplemente colocarías tu propia semilla en esta ecuación .)
No podemos hacer mucho con la coordenada x, ya que se multiplica por un número par. ¿Pero cuál es ese coeficiente en la coordenada z? ¡¡¡Parece un número impar!!! Usemos el mismo truco que antes para invertirlo nuevamente y obtenemos 211541297333629 .
Imaginemos que tenemos una semilla determinada. ¿Qué pasaría si pudiéramos iterar a través de todas las coordenadas X posibles desde -23440 a +23440, y para cada una, calcular cuál SERÍA la coordenada Z de la región de Woodland, SI tuviera esta semilla de mansión ? En otras palabras, la ecuación anterior nos da seed si conocemos x y z , pero ¿podemos hacer una ecuación que nos dé z si conocemos seed y x ? Respuesta: sí. Simplemente reorganizamos la ecuación anterior y usamos el hecho de que el coeficiente de Z es invertible mod 2^48 ya que es un número impar.
La ecuación es:
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
Entonces esta es una solución bastante buena porque en lugar de dos bucles anidados (uno para X y otro para Z) que hacen un total de 2,2 mil millones de iteraciones, podemos tener un solo bucle for para X que solo hace 46,881 iteraciones. Aquí está 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 ;
} (nota: el extraño << 16 >> 16 está haciendo el mod 2^48, pero en realidad queremos hacerlo usando tipos con signo para que aún obtengamos la respuesta correcta cuando z esté entre -23440 y 0, esta es una forma de ampliar con signo el número de 48 bits a 64 bits, llenando los 16 bits superiores con el bit de signo correcto para el complemento a dos)
Entonces esto funciona y es razonablemente rápido... para una sola semilla. Pero recuerde que estamos retrocediendo el RNG en potencialmente miles de pasos y ejecutando esta verificación en cada paso hasta que encontremos una coincidencia. En ese momento, estábamos usando una gotita de mierda de DigitalOcean en su nivel más bajo, y esto en realidad estaba retrasando todo y no podía mantenerse al día con el tiempo real (los robots extraen muchos bloques por segundo, cada bloque toma miles de pasos para descifrarlo, y cada paso de rng toma 23440*2+1 operaciones para verificar, multiplíquelas y obtendrá cientos de millones de operaciones por segundo, para que vea por qué eso tuvo problemas en un VPS de mierda, especialmente cuando eso VPS también está intentando ejecutar múltiples instancias sin cabeza de Minecraft).
De todos modos, cambiamos a un enfoque de tabla de búsqueda y lo reescribimos en Cuda para ejecutarlo en mi escritorio como un trabajo por lotes cada pocos minutos. Puede funcionar literalmente millones por segundo porque cada uno de los miles de núcleos cuda puede trabajar en su propia semilla en paralelo. Esta es la idea: la clave de la tabla de búsqueda son los 32 bits inferiores de la semilla de la mansión y el valor es la coordenada X de la región de Woodland. Esta tabla de búsqueda funciona sin colisiones porque cada semilla de mansión tiene 32 bits inferiores únicos, de alguna manera . No entiendo por qué eso es cierto, es fascinante. Pensarías que no funcionaría. Pero creo que los coeficientes 341873128712 y 132897987541 pueden haber sido elegidos especialmente para que esto funcione. Por ejemplo, si tienes 2,2 mil millones de canicas y 4,3 mil millones de cubos, y colocas cada canica de forma independiente en un cubo aleatorio, ¿cuáles son las probabilidades de que cada canica tenga su propio cubo? Esencialmente cero. Cerca del final, cada canica nueva tiene más del 50% de posibilidades de golpear un cubo que ya está lleno. Sin embargo, claramente, estos no son aleatorios independientemente, por lo que de alguna manera funciona. Irónicamente, si estás leyendo esto y entiendes cómo funciona o por qué esos dos coeficientes específicos hacen que esto funcione, házmelo saber. De todos modos, funciona. La tabla de búsqueda tiene 2^32 entradas, y cada entrada tiene 2 bytes (ya que es solo un número entre -23440 y +23440), por lo que necesita alrededor de 9 gigabytes de VRAM en su GPU.
La función de verificación de Woodland ahora se ve así (nuevamente, este es el código real pero simplificado, todos los ayudantes y constantes incorporados, 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;
}Esto funciona muy bien en lotes gigantes y puede romper del orden de diez millones de semillas por segundo en un 3090. Resulta que no es gran cosa cuando algunos de los hilos en una deformación terminan antes de tiempo, y realmente no pudimos lograrlo. más rápido que esto. (la razón es que fundamentalmente no podemos saber de antemano qué semillas darán más o menos pasos).
Bueno, eso es todo. Dada la semilla, así es como llegamos a la región de Woodland en el mundo donde ocurrió la carga de trozos más reciente. En otras palabras, acabamos de enterarnos de que la vez más reciente en la que alguien caminó sobre 2b2t y cargó una nueva área del mundo, fue en algún lugar dentro de esta región Woodland de bloques de 1280 por 1280 que acabamos de identificar. (Eso es lo suficientemente preciso como para localizarlos en solo unos minutos de búsqueda)
En la práctica, ¿cuántos pasos de RNG se necesitaron? En el extremo inferior, las mediciones confiables comienzan con 4 pasos de RNG, todo lo que está debajo es error de medición/ruido aleatorio, lo cual sabemos porque el código de Woodland Mansion llama inmediatamente rand.nextInt cuatro veces antes de que nos sea posible medirlo. En promedio, hay alrededor de 128.000 pasos entre cada semilla de Woodland, pero en la práctica, la gran mayoría de las veces en 2b2t, encontramos una semilla de Woodland dentro de unas pocas docenas de pasos. Esto se debe a los detalles de lo que sucede y en qué orden en un tick de Minecraft. Nuestra medición técnicamente ocurre al comienzo del tick, ya que ahí es donde se procesan los paquetes para romper bloques. Generalmente, se ha cargado un fragmento en el historial muy reciente durante el tick anterior. Sin embargo, a veces, un evento puede provocar varios pasos de RNG en el medio. Creemos que este evento son explosiones, como que alguien haga estallar un cristal final al golpearlo, o posiblemente cráneos marchitos. Las explosiones de cristales finales también ocurrirían durante el procesamiento de paquetes del paquete perforado del jugador, y el número de pasos de RNG también se alinea en 1354 pasos (1352 al calcular el daño del bloque en un cuboide).
Y en las coordenadas utilizadas como ejemplo resuelto en este diagrama, esto es lo que genera el código anterior:
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>
Observe cómo ubica Woodland Region 123,456 y observe cómo el final "ubicó a alguien entre" incluye la coordenada real que habíamos ingresado originalmente, que era x=157440 z=583680. Además, las medidas de RNG coinciden con el hexadecimal en rojo: 0xf61dc9 es igual a 16129481 , 0x1700fb es igual a 1507579 y 0xc50d15 es igual a 12913941 . Y para las semillas, 0xed92e70ba4a0 equivale a 261215197308064 y 0xf61dc9221ba4 equivale a 270607788940196 .
Probablemente pueda encontrar parches u opciones de configuración para deshabilitar la manipulación de RNG, algo así funcionará para parchear Randar y probablemente sea la forma más fácil. Si no puede encontrar una manera fácil de desactivar la manipulación de RNG, aquí está el código que debe modificarse en la clase World :
Versión vulnerable:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ;
}Simplemente cambie esta función para devolver un Aleatorio diferente cada vez, si desea una protección perfecta:
Versión parcheada:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
return new Random ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
} Es posible que eso no tenga un gran rendimiento, por lo que si lo desea, puede introducir un nuevo campo, separateRandOnlyForWorldGen , que no se comparte con nada más, por ejemplo:
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 usa PaperMC para 1.12.2 , aquí hay un parche que puede aplicar. Enlace alternativo.
Esta será una sección adicional en la que repasaré algunas cosas adicionales que tendría más sentido explicar desde mi punto de vista, ya que, además de las ideas básicas, en su mayoría desarrollamos cosas de forma independiente.
Lo primero que me gustaría mencionar es el sistema para localizar las coordenadas de una semilla. Los Mason usaron una tabla de búsqueda grande y procesamiento de GPU; en cambio, confié en un caché para mayor velocidad. Cada vez que ocurre un impacto, sus coordenadas y todas las coordenadas dentro de un radio se colocan en un HashMap. Las semillas se procesan en dos pasadas. El primer paso hace retroceder el RNG y verifica si la semilla está presente en el caché o si fue la misma semilla procesada la última vez, lo cual se considera de manera diferente. El segundo paso sólo ocurre si el primero falla, es mucho más lento y utiliza el algoritmo relativamente costoso descrito anteriormente. Un efecto secundario agradable de este sistema es que la primera pasada tiene el potencial de "saltarse" una ubicación que de otro modo sería "válida", pero que es menos probable que sea correcta, lo que ayuda con los falsos positivos.
Aquí está ese código:
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 = MANSION_SALT ;
public int spacing = MANSION_SPACING ;
public RandarCoordFinder ( long worldSeed )
{
this . worldSeed = worldSeed ;
}
// a simple class that extends java.util.Random and provides some extra methods and constants we need
public static class RandarRandom extends Random
{
public static final long MULT = 0x5DEECE66DL ;
public static final long ADDEND = 0xBL ;
public static final long MASK = ( 1L << 48 ) - 1 ;
public static final long MULT_INV = 0xDFE05BCB1365L ;
public long seed ;
public RandarRandom ( long seed )
{
this . seed = seed ;
}
@ Override
public void setSeed ( long seed )
{
this . seed = seed ;
}
@ Override
public int next ( int bits )
{
seed = ( seed * MULT + ADDEND ) & MASK ;
return ( int )( seed >> 48 - bits );
}
public int prevInt ()
{
seed = (( seed - ADDEND ) * MULT_INV ) & MASK ;
return ( int )( seed >> 16 );
}
}
public enum FindType
{
HIT ,
SKIP ,
FAIL ;
}
public record FindResult ( FindType type , int xCoord , int zCoord , int steps )
{
}
public FindResult findCoordsSeed ( long seed , int maxSteps )
{
seed &= RandarRandom . MASK ;
// remember and update lastSeed
long last = lastSeed ;
lastSeed = seed ;
RandarRandom random = new RandarRandom ( seed );
// first pass - this is meant to be quick
for ( int i = 0 ; i < maxSteps + 100000 ; i ++)
{
if ( random . seed == last && i > 0 )
{
// we encountered the last processed seed while stepping back, skip
return new FindResult ( FindType . SKIP , 0 , 0 , i );
}
else
{
Long hashValue = hitCache . get ( random . seed );
if ( hashValue != null )
{
// we found a hit in our cache
int xCoord = ( int )(( hashValue >> 32 ) & 0xFFFFFFFF );
int zCoord = ( int )( hashValue & 0xFFFFFFFF );
cacheNearby ( xCoord , zCoord , 8 );
return new FindResult ( FindType . HIT , xCoord , zCoord , i );
}
}
random . prevInt ();
}
random . seed = seed ;
// second pass - this is slow and should only happen if the first pass fails
for ( int i = 0 ; i < maxSteps ; i ++)
{
// undo worldSeed and salt
long seedValue = ( random . seed ^ RandarRandom . MULT ) - worldSeed -
( long ) salt ;
Coords coords = findCoords ( seedValue , 1875000 / spacing + 8 );
if ( coords != null )
{
// we found a hit
cacheNearby ( coords . x , coords . z , 8 );
return new FindResult ( FindType . HIT , coords . x , coords . z , i );
}
random . prevInt ();
}
// we could not find anything
return new FindResult ( FindType . FAIL , 0 , 0 , - 1 );
}
public static long getRandomSeed ( int x , int z , int salt , long seed )
{
return (( long ) x * X_MULT + ( long ) z * Z_MULT ) + seed + ( long ) salt ;
}
private void cacheNearby ( int x , int z , int radius )
{
for ( int xOff = - radius ; xOff <= radius ; xOff ++)
{
for ( int zOff = - radius ; zOff <= radius ; zOff ++)
{
int cacheX = x + xOff ;
int cacheZ = z + zOff ;
long cacheSeed = ( getRandomSeed ( cacheX , cacheZ , salt ,
worldSeed ) ^ RandarRandom . MULT ) & RandarRandom . MASK ;
hitCache . put ( cacheSeed , ( long ) cacheX << 32 | cacheZ &
0xFFFFFFFFL );
}
}
}
public record Coords ( int x , int z )
{
}
public static Coords findCoords ( long value , int distance )
{
value &= RandarRandom . MASK ;
for ( int x = - distance ; x <= distance ; x ++)
{
long testValue = ( value - X_MULT * x ) & RandarRandom . MASK ;
long z = ( testValue * Z_MULT_INV ) << 16 >> 16 ;
if ( Math . abs ( z ) <= distance )
{
return new Coords ( x , ( int ) z );
}
}
return null ;
}
}Otra cosa que me gustaría mencionar es cómo usé esto en The End. Como se mencionó anteriormente, los fragmentos en The End solo afectan el RNG una vez cuando se generan por primera vez. Esto hace que las cosas sean mucho más complicadas, ya que, a diferencia del Overworld, no se puede encontrar a un jugador simplemente cargando un trozo en su base.
En cambio, existen otros dos escenarios principales en los que debemos confiar:
Básicamente, el primer escenario significa que todavía podemos usar el método ingenuo de simplemente contar cuántas veces distintas una región fue atacada; sin embargo, estaremos muy limitados ya que los impactos pueden ser muy poco frecuentes y pueden confundirse si alguien simplemente pasa volando por un área en unas cuantas veces bastante distintas. El segundo escenario requiere que identifiquemos y sigamos estos senderos.
Entonces, ¿cómo seguimos exactamente los senderos? En teoría, podrías crear un sistema para identificar y seguir senderos automáticamente, sin embargo, nunca implementé esto y simplemente seguí los senderos visualmente manualmente. Al seguir senderos, hay algunas ideas que pueden ayudar. Por ejemplo, varios senderos que conducen al mismo lugar probablemente signifiquen que hay una base. Saber que un determinado golpe o rastro fue causado por un jugador específico también puede ayudar; hablaremos de eso más adelante.
Entonces, ¿cómo podemos saber qué jugador causó un determinado golpe? En Overworld, podemos simplemente buscar golpes "distintos" que ocurren justo después de que un jugador se une. Sin embargo, es poco probable que eso funcione aquí, por lo que debemos hacer algo más. En realidad, existe un buen sistema para esto. Se basa en la suposición de que no hay muchos jugadores en línea en The End a la vez, y en la idea de que podemos saber quiénes son estos jugadores. La idea es que la cantidad de llamadas de RNG por tick esté, en parte, correlacionada con la cantidad de fragmentos cargados actualmente y, por lo tanto, con la cantidad de jugadores en esa dimensión. Al observar un aumento o disminución repentino en el número de estas llamadas justo después de que un jugador se une o se va, respectivamente, podemos identificar a los jugadores que están en The End. Llamaremos a este sistema "Rastreador de ocupación final" (EOT).
El EOT mantiene dos conjuntos. El primero realiza un seguimiento de quién creemos que está en The End "ahora mismo". Esto puede pasar por alto a los jugadores, por lo que se considera más propenso a generar falsos negativos. El segundo realiza un seguimiento de quién creemos que estuvo en The End "en general", hacia adelante y hacia atrás durante una cierta cantidad de tiempo. Esto se combina con los jugadores que están actualmente en línea y se considera más propenso a falsos positivos. Al observar estos conjuntos cuando ocurre un impacto y hacer algunas inferencias manuales, podemos tener una idea aproximada de quién puede haber causado un determinado impacto.
Cabe señalar que el EOT solo se probó en 9b9t y actualmente puede depender de condiciones que pueden no ser ciertas en otros servidores como 2b2t. Se supone que el RNG se puede probar cada tick sin mucha fluctuación, lo que puede ser más complicado para 2B2T debido al límite de velocidad del lugar de bloque. Las cosas también podrían hacerse más complicadas si al final hay significativamente más actividad de jugadores en el servidor, lo que probablemente podría ser cierto para 2B2T, ya que es un servidor mucho más grande.
