Каждый раз, когда блок разбивается в версиях Minecraft с бета-версии 1.8 по 1.12.2, точные координаты выпавшего предмета могут указать местоположение другого игрока .
«Randar» — это эксплойт для Minecraft, который использует сокращение решетки LLL для взлома внутреннего состояния неправильно повторно используемого java.util.Random на сервере Minecraft, а затем работает в обратном направлении, чтобы найти других игроков, загруженных в данный момент в мир.
Нажмите здесь, чтобы узнать о Рандаре в виде видео на YouTube.
Посмотрите таймлапс:
Больше таймлапсов можно посмотреть здесь (в виде файлов) или здесь (в формате YouTube).
Цель состоит в том, чтобы определить внутриигровое местоположение (то есть координаты) других игроков в мире, независимо от того, насколько далеко они находятся. Мы играем на 2b2t, старейшем и самом известном «анархическом» сервере Minecraft (что означает отсутствие правил, то есть игроков не банят ни по какой причине). Делать подобные вещи - это своего рода «цель» на этом сервере. На этом сервере единственное, что сохраняет ваши вещи в безопасности, это то, что карта огромна (3,6 квадриллиона квадратных плиток), и никто больше не знает, где вы находитесь. Так что иметь координационный эксплойт — это огромное дело (решающее игру). (кстати, до Рандара у нас также был еще один координационный эксплойт на 2b2t, Nocom, с 2018 по 2021 год; см. эту статью здесь, ветка HackerNews, YT)
Ошибка в коде Minecraft присутствует в версиях Beta 1.8 (выпущена в 2011 г.) по 1.12.2 (выпущена в 2017 г., но 2b2t оставался в этой версии до 14 августа 2023 г.). Ошибка заключается в том, что различные экземпляры генератора случайных чисел java.util.Random небрежно используются повторно в различных частях кода (и с самого начала они небезопасны). В частности, происходит повторное использование ГСЧ между созданием ландшафта и игровыми действиями, такими как добыча блоков.
Краткое описание эксплойта :
World.rand сбрасывает начальное значение в функцию координат чанка, чтобы проверить, где должен находиться ближайший лесной особняк (и действительно ли это именно этот чанк).World.rand.nextFloat() для выбора координат XY и Z от 0 до 1. Бот записывает временную метку и точные значения XYZ.World.rand , которое вызвало эти три плавающих числа. В общих чертах (подробнее будет позже), наблюдение за одним выходом ГСЧ может означать любое из примерно 16 миллионов возможных внутренних состояний ГСЧ. Однако мы опробовали выходные данные ГСЧ не один, а три раза подряд (координаты X, Y и Z выброшенного элемента) и знаем, как внутреннее состояние обновляется между каждым вызовом (простое умножение , добавить, затем изменить); поэтому мы можем использовать методы решетки, чтобы практически мгновенно сузить его до единственной возможности.java.util.Random можно отодвинуть назад так же легко, как и вперед, и, сделав шаг назад, мы можем найти его всего за несколько тысяч шагов (даже на загруженных серверах, таких как 2b2t, с большим количеством игроков и, следовательно, тяжелыми). использование RNG), который определяет самый последний момент сброса внутреннего состояния RNG и, следовательно, местоположение самого последнего фрагмента, загруженного на сервер.Даже если вы играете на сервере, который обновился до более новой версии Minecraft или иным образом исправил манипуляции с ГСЧ, ваши координаты по-прежнему подвергаются риску со стороны Рандара из-за возможности ретроспективного использования данных ГСЧ. Некоторые игроки Minecraft используют такие моды, как ReplayMod, которые регистрируют пакеты, и у них все еще могут храниться эти файлы журналов. Если кто-то использовал такой мод, пока вы были на своей базе, он мог (неосознанно) записать данные ГСЧ, которые могли бы раскрыть ваше местоположение, поскольку разрушение блоков — чрезвычайно распространенное действие, которое, вероятно, произойдет в таких записях, и каждый такой блок Break показывает состояние RNG сервера и, следовательно, местоположение последнего загруженного фрагмента. Это означает, что Randar — это довольно серьезное дело: из-за риска ретроактивного использования на каждом сервере Minecraft каждая локация, которая была активна в бета-версиях с 1.8 по 1.12.2, должна считаться скомпрометированной, даже если сервер уже давно обновился до версии 1.12. .2 или исправленные манипуляции с ГСЧ.
Если вы хотите самостоятельно использовать эксплойт Randar , зайдите сюда, где rebane2001 создал веб-сайт, на который вы можете перетащить файлы ReplayMod из 1.12.2 и посмотреть координаты других игроков. Он работает на стороне клиента, поэтому ваши записи не покинут ваш браузер. Вот видео того, как этот веб-сайт выглядит в действии, и вы можете запустить пример файла ReplayMod из этого видео, загрузив его здесь.
Рандар был обнаружен пользователем n0pf0x (pcm1k). Эта статья была написана leijurv, с дополнительными комментариями в конце, написанными n0pf0x. Эксплуататорами были 0x22, Babbaj, TheLampGod, leijurv, Negative_Entropy и rebane2001. Посмотрите видео TheLampGod здесь. Посмотрите 100% юмористическое, но не основанное на фактах видео HermeticLock здесь.
Оглавление: нажмите здесь, чтобы узнать о коде эксплойта более подробно, здесь, чтобы узнать о том, как использовалось сокращение решетки, здесь, чтобы узнать, как мы защитили наши собственные тайники от Рандара, здесь, если вы просто хотите увидеть полный код эксплойта, здесь, если вы используете сервер, на котором все еще установлена версия между бета-версиями 1.8 и 1.12.2, и вы хотите исправить Randar, или здесь для получения подробной информации о том, что n0pf0x сделал иначе, чем мы.
Схема ошибки (в формате PDF):
Схема эксплойта (в формате PDF):
Схема работающего примера эксплойта (в формате PDF):
Minecraft полагается на случайные числа на протяжении всей игры. Мы ожидаем, что большинство из них будут на самом деле случайными, например, случайность, используемая для появления мобов и погоды, но некоторые из них мы ожидаем, что они будут предсказуемыми, например, мы ожидаем, что одно и то же семя мира в одной и той же локации будет генерировать один и тот же ландшафт. В 2011 году, когда Нотч впервые добавил структуры в игру во время бета-тестирования 1.8, он случайно повторно использовал ГСЧ, который должен был быть непредсказуемым, чтобы разместить деревни в мире. С тех пор, вплоть до версии 1.13, этот небрежный код приводил к тому, что генерация мира влияла почти на все другие предположительно случайные события в игре. Примерно в мае 2018 года Earthcomputer и его друзья обнаружили эту ошибку, осознав, что загрузка фрагментов заметно влияет на ГСЧ игры, см. это объяснение. Однако они не осознавали или просто никогда публично не заявляли, что это можно сделать и в обратном направлении, определяя самый последний загруженный фрагмент на основе наблюдения за ГСЧ. Это открытие, Randar, было сделано n0pf0x (он же pcm1k) 7 октября 2022 года. Примерно через две недели он опубликовал краткое зашифрованное описание эксплойта на Pastebin, чтобы доказать, что он обнаружил его именно тогда. Он использовал этот эксплойт в основном на 9b9t и лишь в относительно небольшом количестве на 2b2t и других серверах. На 2b2t n0p обнаружил и исследовал различные локации, в конечном итоге добравшись до тайника Гринготтса. Его заметил rebane2001, и сначала он ничего не рассказал о том, как нашел это место. Однако примерно через месяц он начал разговор об этом с SpawnMasons. n0p сообщил, что использовал мощный эксплойт координат, и решил поделиться с нами объяснением в апреле 2023 года, поскольку у масонов уже есть опыт использования эксплойтов 2b2t в более крупных масштабах, поэтому было бы интересно увидеть, как это произойдет снова, и n0p был все равно мне это немного надоело. Мы согласились и начали записывать координаты выпадения предметов на нескольких учетных записях, которые уже круглосуточно и без выходных добывали камень/булыжник для несвязанного проекта (поэтому никаких изменений в поведении не произошло). Мы повторно использовали безголовую систему Minecraft от nocom и добавили базу данных Postgres для записи измерений. Как обсуждается далее в этом файле ознакомительных сведений, мы прошли несколько итераций программного обеспечения для взлома измерений ГСЧ и в конечном итоге остановились на асинхронном пакетном задании Cuda. По мере добавления в базу данных взломанных измерений мы также обновляли аналитическую таблицу с информацией о тепловой карте, в которой подсчитывались попадания по каждой координате с интервалами за все время, ежедневно и ежечасно. Это позволило простому пользовательскому интерфейсу Plotly Dash выбирать данные тепловой карты из определенных временных диапазонов и детализации для отображения в браузере, а также позволило нам удалить весь спам, связанный с загрузкой фрагментов Elytra, с учетом только координат, которые были загружены более чем через несколько отдельных часов. Мы добавили простую общую систему аннотаций, чтобы отслеживать, что мы нашли в каждой горячей точке на карте. Опять же, используя Nocom, у нас есть боты Baritone, которые автоматизируют весь процесс кражи тайников с предметами и сортировки результатов, полностью AFK. Многие каменщики помогали с этой частью, не зная об эксплойте, используя такие аккаунты, как munmap и 1248_test_user . Все тайники Гринготтса, вместе взятые, в конечном итоге выросли до 1,3 миллиарда предметов, из которых около половины принадлежит Nocom, а половина — Рандару.
Полная история объяснена в видео FitMC.
Карта Minecraft генерируется процедурно и по сути детерминирована на основе начального семени мира. По мере того, как игроки исследуют карту, по мере приближения игроков по требованию создаются новые области. Поскольку вся генерация должна быть повторяемой (детерминированной), для них вполне разумно использовать java.util.Random во многих местах. Они хотят, чтобы все было предсказуемо. Вот почему используется java.util.Random , поскольку это ГПСЧ (не совсем ГСЧ). Буква P технически означает «псевдо», но думайте об этом как о «предсказуемом». Предсказуемый ГСЧ. Он генерирует числа, которые кажутся случайными, но на самом деле они повторяемы, учитывая одно и то же начальное начальное число.
В Minecraft есть различные структуры, которые генерируются в мире, такие как деревни, океанские памятники, крепости и т. д. Они являются частью процедурной генерации, поэтому они также размещаются и генерируются детерминированно.
Чтобы понять это, нужна всего дюжина строк кода Minecraft, и я упростил и подробно прокомментировал его:
// (chunkX,chunkZ) is being loaded, and this function checks if it should generate a Woodland Mansion
protected boolean canSpawnStructureAtCoords ( int chunkX , int chunkZ ) {
// divide by 80, rounding down, to determine which "Woodland region" (my made up term) we're considering
int woodlandRegionX = Math . floorDiv ( chunkX , 80 );
int woodlandRegionZ = Math . floorDiv ( chunkZ , 80 );
// seed the random number generator deterministically in a way that's unique to this Woodland region
Random random = this . world . setRandomSeed ( woodlandRegionX , woodlandRegionZ , 10387319 );
// pick which chunk within this region will get the Woodland Mansion
int woodlandChunkX = woodlandRegionX * 80 + ( random . nextInt ( 60 ) + random . nextInt ( 60 )) / 2 ;
int woodlandChunkZ = woodlandRegionZ * 80 + ( random . nextInt ( 60 ) + random . nextInt ( 60 )) / 2 ;
// but is it *this* chunk, that we're loading right now?
if ( chunkX == woodlandChunkX && chunkZ == woodlandChunkZ ) {
// and, is this chunk in a biome that allows Woodland Mansions? (e.g. roofed forest)
if ( this . world . getBiomeProvider (). areBiomesViable ( chunkX * 16 + 8 , chunkZ * 16 + 8 , 32 , ALLOWED_BIOMES )) {
return true ;
}
}
return false ;
}
// and here's what it calls in World.java:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ; // this.getWorldInfo().getSeed() is the overall seed of the entire map, which has been cracked long ago for 2b2t (it's -4172144997902289642)
}Вышеуказанное прокомментировано и слегка изменено для ясности, но функционально соответствует реальному коду.
Итак, идея состоит в том, чтобы решить, где должен располагаться Лесной особняк в этом Лесном регионе (который состоит из кусков 80 на 80), проверить, находится ли это место прямо здесь , и если да, создать Лесной особняк, начиная прямо здесь.
Этот код может выглядеть немного глупо, вы можете подумать: «Абсурдно делать все эти проверки для каждого фрагмента, просто выберите, куда должны идти лесные особняки, один раз для каждого региона и покончите с этим». Причина в том, что чанки Minecraft генерируются независимо друг от друга и в неизвестном порядке, но мы все равно хотим сгенерировать детерминированный мир из заданного сида. Мы не знаем, в каком порядке игрок будет ходить по миру, и приятно иметь возможность генерировать любой фрагмент по требованию без сохранения состояния. Это хороший игровой опыт. Итак, такой странный код.
В любом случае, этот код вызывается при каждой загрузке фрагмента, для каждого фрагмента в большом квадрате вокруг загружаемого. Немного сложно объяснить, почему, поэтому я в основном пропущу это (основная идея заключается в том, что эти структуры (намного) больше одного фрагмента по размеру, поэтому нам нужно проверить происхождение структуры во многих соседних фрагментах, чтобы сгенерировать этот текущий правильно).
Обратите внимание, что это влияет только на верхний мир. Пустота безопасна, поскольку при создании всех ее структур всегда использовался безопасный ГСЧ. На загрузку фрагментов в The End влияют конечные города, но только при их первоначальном создании, а не при каждой последующей загрузке, поэтому The End относительно безопасен, поскольку каждый фрагмент на вашей базе влияет на ГСЧ только один раз при первой загрузке. это. Однако это не совсем надежно, так как игроки обычно генерируют новые фрагменты каждый раз, путешествуя на свою базу, а иногда генерируют новые фрагменты, уже находясь на своей базе.
Проблема в том, что он изменяет начальное значение глобального World.rand . Это просто ленивое кодирование. Все, что они делают, это четыре раза вызывают nextInt , чтобы выбрать координаты X и Z. Они могли бы заменить Random random = this.world.setRandomSeed(... на Random random = new Random(the same stuff) (другими словами, создать здесь новый Random а не возиться с существующим, который используется всем остальным? ??).
Важно отметить, setRandomSeed вызывается для проверки того, куда должен идти лесной особняк. Это происходит несмотря ни на что, при каждой загрузке фрагмента, везде. Вам не обязательно стоять внутри или рядом с особняком Вудленд или чем-то в этом роде.
Что ж, оказывается, что World.rand используется буквально в сотнях мест, и многие из этих мест можно легко увидеть, играя в игру в обычном режиме. Например, когда вы добываете блок:
/**
* Spawns the given ItemStack as an EntityItem into the World at the given position
*/
public static void spawnAsEntity ( World world , BlockPos pos , ItemStack stack ) {
double xWithinBlock = world . rand . nextFloat () * 0.5F + 0.25D ;
double yWithinBlock = world . rand . nextFloat () * 0.5F + 0.25D ;
double zWithinBlock = world . rand . nextFloat () * 0.5F + 0.25D ;
EntityItem entityitem = new EntityItem ( world , pos . getX () + xWithinBlock , pos . getY () + yWithinBlock , pos . getZ () + zWithinBlock , stack );
world . spawnEntity ( entityitem );
}Опять же, слегка измененный, но функционально точный для того, о чем мы говорим.
Идея здесь в том, что в Minecraft, когда вы добываете блок, из него выпадает предмет. Предмет выбрасывается в случайное место внутри блока. Например, если блок находился по адресу (10, 20, 30) , элемент появится где-то между (10.25, 20.25, 30.25) и (10.75, 20.75, 30.75) .
И точное местоположение этого элемента выбирается путем вызова world.rand.nextFloat() три раза подряд для X, Y и Z.
Это все, что нужно для кода Minecraft!
Я сказал, что мы можем что-то сделать с вызовами nextFloat . Во-первых, давайте посмотрим, сможем ли мы «поработать назад», чтобы увидеть, что представляют собой вызовы nextFloat . Это большая удача, но мы действительно можем. Обратите внимание в приведенном выше коде: случайное число с плавающей запятой умножается на 0,5, а затем добавляется к 0,25. Идея состоит в том, чтобы перейти от случайного числа от 0 до 1 к случайному числу от 0,25 до 0,75. Вы можете волноваться, потому что если бы вам пришлось разделить целое число на два, вы потеряли бы часть информации, поскольку результат округляется в меньшую сторону. К счастью, умножение числа с плавающей запятой на 0,5 полностью обратимо, поскольку оно просто уменьшает показатель степени, оставляя мантиссу нетронутой. Затем число с плавающей запятой преобразуется в двойное, что обеспечивает гораздо большую точность. Добавляется 0,25, затем добавляется координата блока. Затем он отправляется клиенту по сети в полной точности. В результате весь этот процесс обратим, поэтому мы можем получить ровно три числа с плавающей запятой, которые создал World.rand.nextFloat() .
Как java.util.Random генерирует числа с плавающей запятой? Ну на самом деле это довольно просто. Он генерирует целое число от 0 до 2^24, а затем делит его на 2^24 (в результате получается число от 0 до 1). Как он получает это случайное целое число? А еще довольно просто! Это линейный конгруэнтный генератор (ЛКГ). Это означает, что следующее начальное число — это умножение предыдущего начального числа на что-то плюс что-то еще, по модулю чего-то еще.
public float nextFloat () {
this . seed = ( this . seed * multiplier + addend ) % modulus ; // update the seed
int randomInteger = ( int ) ( this . seed >> 24 ); // take the top 24 bits of the seed
return randomInteger / (( float ) ( 1 << 24 )); // divide it by 2^24 to get a number between 0 and 1
}В данном случае множитель равен 25214903917, слагаемое — 11, а модуль — 2^48.
Получив в результате число с плавающей запятой, мы можем умножить его на 2^24, чтобы получить случайное целое число и, следовательно, получить «верхнюю половину» (самые значимые 24 бита) 48-битного начального числа.
Короче говоря, из нашего измерения мы узнаем, что начальное число находится между measuredRandomInteger * 2^24 и (measuredRandomInteger + 1) * 2^24 .
И мы можем сделать это три раза подряд для X, Y и Z.
И мы знаем, что между X и Y, а также между Y и Z начальное число было обновлено в соответствии с newSeed = (oldSeed * 25214903917 + 11) mod 2^48
Я должен отметить, что одним из допустимых вариантов является цикл for, который проверяет все 2^24 возможных младших бита. Я надеюсь, что программистам, читающим это, станет ясно, в чем проблема:
for ( long seed = firstMeasurement << 24 ; seed < ( firstMeasurement + 1 ) << 24 ; seed ++) {
// all these seeds will match the first measurement
if ( nextSeed ( seed ) >> 24 == secondMeasurement && nextSeed ( nextSeed ( seed )) >> 24 == thirdMeasurement ) {
// if nextSeed(seed) matches secondMeasurement, and nextSeed(nextSeed(seed)) matches thirdMeasurement
// then we found a seed that matches all three measurements! yay!
return seed ;
}
}Это могло бы сработать и работает, но это не так быстро и не так весело. Поэтому вместо этого мы используем решетки!
Однако я чувствую, что мне придется немного отойти от порядка. Здесь можно упомянуть об уменьшении решетки, но это действительно сложно, и я готов поспорить, что это не запомнится читателям, и я не хочу вас потерять. Поэтому я просто дам вам это решение для цикла for (которое ДЕЙСТВИТЕЛЬНО работает) и перейду к следующему шагу эксплойта. Объяснение метода редукции решетки будет сразу после :)
Что мы будем делать с этим семенем, когда оно у нас появится?
Во-первых, обратите внимание, что мы можем отодвинуть LCG назад. Очевидно, что сложение одиннадцати обратимо, но обратимо ли умножение на это большое число? Наш множитель 25214903917 — нечетное число, то есть оно не делится на два, и, следовательно, не имеет общих множителей с нашим модулем 2^48 (поскольку 2^48 — это буквально просто связка двоек). Поскольку оно относительно простое по модулю, мы можем инвертировать его, что означает найти другое число x , которое удовлетворяет условию x * 25214903917 - 1 делится на 2^48. Или, другими словами, 25214903917 * x mod 2^48 = 1 . Это число 246154705703781 . Это помогает инвертировать умножение, потому что если у нас есть, например, secret * 25214903917 и мы хотим вычислить secret , мы можем просто вычислить secret * 25214903917 * 246154705703781 mod 2^48 = secret * 1 mod 2^48 = secret .
Итак, мы можем выполнить внутреннее семя java.util.Random как вперед, так и назад. Вперед — это newSeed = (oldSeed * 25214903917 + 11) mod 2^48 , а назад — oldSeed = ((newSeed - 11) * 246154705703781) mod 2^48 . И это работает, потому что числа 25214903917 и 246154705703781 при умножении вместе получают 1 , если взять их по модулю 2^48.
Теперь, сделав шаг назад, мы хотели бы на каждом шаге проверять, может ли это начальное значение означать, что где-то в мире недавно была выполнена проверка Woodland Mansion (в этом весь смысл эксплойта). Как нам это сделать?
Мир Minecraft варьируется от -30 миллионов до +30 миллионов блоков. Каждый «Лесной регион» (область мира, где один лесной особняк размещается случайным образом, согласно коду, показанному ранее) имеет размер 80 на 80 блоков, что составляет 1280 на 1280 блоков. Это 23437,5 лесных регионов, но для всего нашего кода мы просто округлили до 23440, потому что это круглое число, и даже если ваш игрок не может путешествовать дальше 30 миллионов, вы загружаете фрагменты за его пределы, просто стоя рядом с ним, и мы просто не хотел обо всем этом беспокоиться.
Итак, от -23440 до +23440 по осям X и Z. Это (23440*2+1)^2 (он же 2197828161 ) возможных лесных регионов, каждый из которых генерирует уникальное «семя особняка» (определяемое как семя, которое показывает, что кто-то только что загрузил кусок в определенный лесной регион). Нам нужно иметь возможность проверить, является ли что-то семенем особняка. Можем ли мы перебрать все 2,2 миллиарда семян особняка, чтобы проверить каждое из них? Это было бы слишком медленно. Можно ли создать HashSet с 2,2 миллиардами записей? Это заняло бы слишком много оперативной памяти даже при использовании карты хроники, как мы это делали в nocom, и даже в C ++ с использованием abseil-cpp использовалось около 50 ГБ оперативной памяти. И это не говоря уже о другом: мы на самом деле хотим узнать, где они находятся в мире (в этом вся суть). Поэтому недостаточно знать, что это семя особняка, мы также хотим (эффективно) узнать, какой лесной регион его вызвал.
Вспомните функцию, которая переходит от лесного региона к семени особняка (примечание: для простоты я объединил некоторые константы, начиная с приведенного выше кода, это уравнение теперь специализировано для семени 2b2t ):
seed = x * 341873128712 + z * 132897987541 - 4172144997891902323 mod 2^48
(число -4172144997891902323 получается из -4172144997902289642 + 10387319 , что является семенем мира 2b2t + магическим значением, используемым для засеивания лесного региона (как показано ранее). Для любого другого мира вы просто поместите свое собственное семя в это уравнение. .)
С координатой x мы мало что можем сделать, поскольку она умножается на четное число. Но что это за коэффициент по координате z? Это похоже на нечетное число!!! Давайте воспользуемся тем же трюком, что и раньше, чтобы инвертировать его еще раз, и получим 211541297333629 .
Давайте представим, что у нас есть заданное семя. Что, если бы мы могли просто перебрать все возможные координаты X от -23440 до +23440 и для каждой из них вычислить, какой БЫЛА БЫЛА координата Z лесного региона, ЕСЛИ у него было это семя особняка . Другими словами, приведенное выше уравнение дает нам seed если мы знаем x и z , но можем ли мы составить уравнение, которое дает нам z если мы знаем seed и x ? Ответ: да. Мы просто переставляем приведенное выше уравнение и используем тот факт, что коэффициент при Z является обратимым по модулю 2^48, поскольку это нечетное число.
Уравнение:
z = (seed + 4172144997891902323 - x * 341873128712) * 211541297333629 mod 2^48
Так что это довольно хорошее решение, поскольку вместо двух вложенных циклов (один для X и один для Z), которые выполняют в общей сложности 2,2 миллиарда итераций, мы можем иметь один цикл for для X, который выполняет всего 46 881 итерацию. Вот это на Java:
private static WoodlandRegionCoord woodlandValid ( long internalSeed ) {
long seed = 25214903917 ^ internalSeed ; // java.util.Random XORs in the multiplier while doing setSeed, so XOR that back out to go from a "this.seed" to what the input to setSeed() would be
for ( int x = - 23440 ; x <= 23440 ; x ++) {
long z = (( seed + 4172144997891902323L - x * 341873128712L ) * 211541297333629L ) << 16 >> 16 ;
if ( z >= - 23440 && z <= 23440 ) {
return new WoodlandRegionCoord ( x , z );
}
}
return null ;
} (примечание: странный << 16 >> 16 выполняет мод 2^48, но на самом деле мы хотим сделать это, используя подписанные типы, чтобы мы все равно получали правильный ответ, когда z находится между -23440 и 0, это способ знак-расширение 48-битного числа до 64 бит, заполнение старших 16 бит правильным битом знака для дополнения до двух)
Так что это действительно работает и достаточно быстро... для одного семени. Но помните, что мы откатываем ГСЧ потенциально на тысячи шагов и выполняем эту проверку на каждом этапе, пока не найдем совпадение. В то время мы использовали дерьмовый дроплет DigitalOcean на самом нижнем уровне, и он фактически отставал от всего и не мог идти в ногу с реальным временем (боты добывали много блоков в секунду, каждый блок требовал тысячи шагов для взлома, и каждый шаг цикла требует 23440*2+1 операций для проверки, умножьте их вместе, и вы доберетесь до сотен миллионов операций в секунду, так что вы поймете, почему у этого были проблемы на дрянном VPS, особенно когда этот VPS тоже пытается для запуска нескольких обезглавленных экземпляров Minecraft).
В любом случае, мы перешли на подход с использованием таблицы поиска и переписали его на Cuda, чтобы он запускался на моем рабочем столе в виде пакетного задания каждые несколько минут. Он может выполнять буквально миллионы операций в секунду, поскольку каждое из тысяч ядер cuda может параллельно работать над своим собственным начальным числом. Вот идея: ключ таблицы поиска — это младшие 32 бита начального числа особняка, а значение — координата X региона Вудленд. Эта таблица поиска работает без конфликтов, поскольку каждое начальное значение особняка каким-то образом имеет уникальные младшие 32 бита. Я не понимаю, почему это правда, это увлекательно. Можно подумать, это не сработает. Но я думаю, что коэффициенты 341873128712 и 132897987541 могли быть специально выбраны, чтобы эта работа работала? Например, если у вас есть 2,2 миллиарда шариков и 4,3 миллиарда ведер, и вы независимо кладете каждый шарик в случайное ведро, какова вероятность того, что каждый шарик получит свое собственное ведро? По сути ноль. Ближе к концу каждый новый шарик с вероятностью более 50% попадет в уже наполненное ведро. Тем не менее, очевидно, что они не являются независимыми случайными, поэтому каким-то образом это работает. По иронии судьбы, если вы читаете это и понимаете, как это работает или почему эти два конкретных коэффициента заставляют это работать, дайте мне знать. В любом случае, это работает. Таблица поиска содержит 2^32 записи, каждая из которых имеет размер 2 байта (поскольку это просто число от -23440 до +23440), поэтому для этого требуется около 9 гигабайт видеопамяти на вашем графическом процессоре.
Функция проверки леса теперь выглядит так (опять же, это реальный код, но упрощенный, все хелперы, константы встроены и т. д.):
__global__ void computeSteps ( const int16_t * mansionTable, const int64_t * seedsArr, Result* resultArr, size_t numData) {
auto tid = blockIdx. x * blockDim. x + threadIdx. x ;
[[unlikely]] if (tid >= numData) {
return ;
}
auto seed = seedsArr[tid];
int steps = 0 ;
while ( true ) {
auto externalSeed = seed ^ 25214903917 ;
const auto x = mansionTable[externalSeed & (( 1LL << 32 ) - 1 )];
const auto z = ((externalSeed + 4172144997891902323LL - ( int64_t ) x * 341873128712LL ) * 211541297333629LL ) << 16 >> 16 ;
if (z >= - 23440 & z <= 23440 ) {
resultArr[tid] = {. startSeed = seedsArr[tid], . x = ( int16_t ) x, . z = ( int16_t ) z, . steps = steps};
return ;
}
seed = ((seed - 0xBLL ) * 0xdfe05bcb1365LL ) & (( 1LL << 48 ) - 1 ); // prevSeed(seed)
steps++;
}
}
// and that mansionTable was generated like this
// note: mansionTable must be calloc'd before this function because not every entry will be written to, and an x value outside -23440 to 23440 bounds could create a false positive later on while using the table
__global__ void writeToSeedTable ( int16_t * mansionTable) {
auto tid = blockIdx. x * blockDim. x + threadIdx. x ;
if (tid >= ( 23440 * 2 + 1 ) * ( 23440 * 2 + 1 )) return ;
auto x = tid / ( 23440 * 2 + 1 ) - 23440 ;
auto z = tid % ( 23440 * 2 + 1 ) - 23440 ;
auto seed = (( int64_t ) x * 341873128712LL + ( int64_t ) z * 132897987541LL - 4172144997891902323LL ) & (( 1LL << 48 ) - 1 );
mansionTable[seed & (( 1LL << 32 ) - 1 )] = ( int16_t ) x;
}Это отлично работает в гигантских партиях и может давать трещину порядка десяти миллионов семян в секунду на 3090. Оказывается, это не так уж и важно, когда некоторые потоки в варпе завершаются раньше, и мы не можем этого сделать. это быстрее, чем это. (причина в том, что мы принципиально не можем заранее знать, какие семена сделают больше/меньше шагов).
Ну вот и все. Учитывая начальное значение, именно так мы получаем регион Вудленд в мире, где произошла последняя загрузка фрагментов. Другими словами, мы только что узнали, что в последний раз кто-то гулял по 2b2t и загружал новую область мира где-то в пределах этого лесного региона размером 1280 на 1280, который мы только что определили. (это настолько точно, что их поиск займет всего несколько минут поиска)
На практике, сколько шагов ГСЧ потребовалось? На нижнем уровне надежные измерения начинаются с 4 шагов ГСЧ, все, что ниже, является ошибкой измерения/случайным шумом, о котором мы знаем, потому что код Woodland Mansion немедленно вызывает rand.nextInt четыре раза, прежде чем мы сможем его измерить. В среднем между каждым семенем Woodland проходит около 128 000 шагов, но на практике в подавляющем большинстве случаев на 2b2t мы находили семя Woodland в пределах нескольких десятков шагов. Это связано с особенностями того, что и в каком порядке происходит в тике Minecraft. Технически наше измерение происходит в самом начале тика, поскольку именно там обрабатываются пакеты для взлома блоков. Как правило, чанк был загружен в самой недавней истории во время предыдущего тика. Однако иногда событие может вызвать множество промежуточных шагов ГСЧ. Мы считаем, что это событие представляет собой взрывы, например, когда кто-то взрывает крайний кристалл, ударив его кулаком, или, возможно, иссушает черепа. Взрывы конечных кристаллов также могут происходить во время обработки пакетов из пакета удара игрока, а количество шагов ГСЧ также составляет 1354 шага (1352 из расчета повреждения блока в кубоиде).
А по координатам, используемым в качестве рабочего примера на этой диаграмме, приведенный выше код выводит следующее:
jshell> crackItemDropCoordinate(0.730696, 0.294929355, 0.634865435)
Item drop appeared at 0.730696 0.294929355 0.634865435
RNG measurements are therefore 16129481 1507579 12913941
This indicates the java.util.Random internal seed must have been 270607788940196
Found a woodland match at woodland region 123 456 which would have set the seed to 261215197308064
Located someone between 157312,583552 and 158591,584831
jshell>
Обратите внимание, как он находит Лесной регион 123,456 , и обратите внимание, что окончательное «нашел кого-то между» действительно включает в себя реальную координату, которую мы изначально ввели, которая была x=157440 z=583680. Кроме того, измерения RNG соответствуют шестнадцатеричному числу, указанному красным: 0xf61dc9 равно 16129481 , 0x1700fb равно 1507579 и 0xc50d15 равно 12913941 . А для начальных чисел 0xed92e70ba4a0 равно 261215197308064 , а 0xf61dc9221ba4 равно 270607788940196 .
Вероятно, вы можете найти патчи или параметры конфигурации для отключения манипуляций с ГСЧ, что-то подобное подойдет для исправления Рандара, и это, вероятно, самый простой способ. Если вы не можете найти простой способ отключить манипулирование ГСЧ, вот код, который необходимо настроить в классе World :
Уязвимая версия:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . rand . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . rand ;
}Если вам нужна идеальная защита, просто измените эту функцию, чтобы она каждый раз возвращала разные случайные значения:
Исправленная версия:
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
return new Random ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
} Это может не иметь высокой производительности, поэтому, если хотите, вы можете ввести новое поле, separateRandOnlyForWorldGen , которое не используется совместно ни с чем, например:
private final Random separateRandOnlyForWorldGen = new Random (); // new field on the World class
public Random setRandomSeed ( int seedX , int seedY , int seedZ ) {
this . separateRandOnlyForWorldGen . setSeed ( seedX * 341873128712L + seedY * 132897987541L + seedZ + this . getWorldInfo (). getSeed ());
return this . separateRandOnlyForWorldGen ;
}Если вы используете PaperMC для версии 1.12.2 , вы можете применить вот патч. Альтернативная ссылка.
Это будет дополнительный раздел, в котором я расскажу о некоторых дополнительных вещах, которые, с моей точки зрения, имеет смысл объяснить, поскольку, помимо основных идей, мы в основном разрабатывали вещи самостоятельно.
Первое, что хотелось бы отметить, это систему нахождения координат по семени. Мейсоны использовали большую справочную таблицу и обработку на графическом процессоре, вместо этого я полагался на кэш для обеспечения скорости. Всякий раз, когда происходит попадание, его координаты и все координаты в радиусе помещаются в HashMap. Семена обрабатываются в два прохода. Первый проход возвращает ГСЧ назад и проверяет, присутствует ли начальное число в кеше, или это было то же самое начальное число, обработанное в прошлый раз, что рассматривается по-другому. Второй проход происходит только в том случае, если первый проход завершается неудачей, он намного медленнее и использует относительно дорогой алгоритм, описанный ранее. Приятным побочным эффектом этой системы является то, что первый проход может «пропустить» другое «действительное», но с меньшей вероятностью правильное местоположение, что помогает при ложных срабатываниях.
Вот этот код:
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 ;
}
}Еще я хотел бы упомянуть, как я использовал это в «Конце». Как упоминалось ранее, чанки в The End влияют на ГСЧ только один раз, когда они впервые генерируются. Это значительно усложняет задачу, поскольку, в отличие от обычного мира, игрока нельзя найти, просто загрузив кусок на его базу.
Вместо этого есть два других основных сценария, на которые мы должны положиться:
По сути, первый сценарий означает, что мы все еще можем использовать наивный метод простого подсчета количества различных попаданий в регион, однако мы будем сильно ограничены, поскольку попадания могут быть очень редкими и могут быть сбиты с толку, если кто-то просто пролетит мимо области в несколько достаточно отчетливых раз. Второй сценарий требует от нас выявления и отслеживания этих следов.
Так как же именно мы идем по следам? Теоретически можно создать систему для автоматического определения и отслеживания следов, однако я никогда не реализовал это и просто визуально отслеживал следы вручную. При следовании по следам есть несколько идей, которые могут помочь. Например, несколько троп, ведущих к одному и тому же месту, скорее всего, означают, что база здесь есть. Знание того, что определенное попадание или след был вызван конкретным игроком, также может помочь, подробнее об этом позже.
Как же мы можем определить, какой игрок нанес тот или иной удар? В обычном мире мы можем просто искать «отдельные» попадания, которые происходят сразу после присоединения игрока. Однако здесь это вряд ли сработает, поэтому надо сделать что-то другое. На самом деле для этого существует изящная система. Он основан на предположении, что в The End не слишком много игроков одновременно находятся онлайн, и на идее, что мы можем сказать, кто эти игроки. Идея состоит в том, что количество вызовов ГСЧ за тик частично коррелирует с количеством загруженных в данный момент фрагментов, а значит, и с количеством игроков в этом измерении. Наблюдая за внезапным увеличением или уменьшением количества этих звонков сразу после того, как игрок присоединяется или уходит соответственно, мы можем идентифицировать игроков, находящихся в Конце. Мы назовем эту систему «Отслеживание занятости в конце» (EOT).
EOT поддерживает два набора. Первый отслеживает, кто, по нашему мнению, находится в Конце «прямо сейчас». Это может пропустить игроков, поэтому считается более склонным к ложноотрицательным результатам. Второй отслеживает, кто, по нашему мнению, был в Конце «в целом», вперед и назад определенное количество времени. Это объединяется с игроками, которые в данный момент находятся в сети, и считается более склонным к ложным срабатываниям. Просматривая эти наборы в момент попадания и делая некоторые выводы вручную, мы можем получить приблизительное представление о том, кто мог вызвать определенное попадание.
Следует отметить, что EOT когда-либо тестировался только на 9b9t и в настоящее время может зависеть от условий, которые могут быть неверны на других серверах, таких как 2b2t. Предполагается, что RNG может быть отобран каждый клещей без особых колебаний, что может быть сложнее для 2B2T из -за ограничения скорости блока. Вещи также могут быть более сложными, если на сервере значительно больше активности игрока, что, вероятно, может быть верно для 2B2T, поскольку это гораздо больший сервер.
