Skip to content

Предсказание и контроль случайности в Nethack

19/08/2009

Nethack, будучи однопользовательской игрой с неполным знанием, включает в себя большое количество элементов случайности. Случайные числа определяют сколько урона Вам нанесёт тот минотавр, чем является каждое пурпурное зелье, принесёт ли окунание в фонтан желание и т.д. Чтобы генерировать случайные числа, NetHack применяет генератор псевдослучайных чисел. Wikipedia говорит:

Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG) — алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).


Любой генератор случайных чисел использует начальное значение (seed), определяющее всю последовательность. Nethack использует текущее время (в особенности, количество секунд с полуночи, 1 января 1970) в качестве начального значения для генератора. Таким образом, две игры начатые в одну и ту же секунду будут иметь один и тот же seed. Это можно легко проверить открыв два окна с терминалом и быстро нажав Enter в обоих одновременно. После этого, если Вы выберете одинаковых персонажей, вы должы оказаться на абсолютно одинаковых уровнях с одинаковыми игровыми характеристиками. Если не получилось, смена секунды произошла между двумя нажатиями — просто попробуйте ещё раз. Если Вы играете обе игры абсолютно одинаково, вы будете получать одинаковые результаты. Естественно, Вы в любой момент можете разорвать эту связь, встретив ненужный результат в игре (например, смерть :)).

Довольно много мороки чтобы просто обмануть игру, да? Если Вы дошли до такого, проще поиграть в «режиме исследователя» с бессмертием или изменить исходники чтобы увеличить шанс выигрыша. Именно поэтому «вознесения» (прохождения игры) на публичном онлайн-сервере ценятся выше, чем однопользовательские вознесения. Вы не можете изменить исходный код сервера или играть в «режиме Бога», поэтому все знают что ваше вознесение было вполне легитимным.

Однако, публичные сервера Nethack всё равно используют ГПСЧ, поэтому существуют достаточно серьёзные возможности атаки на них. На публичном сервере nethack.alt.org у меня получалось злоупотреблять ГПСЧ в демонстративных целях (не для вознесений). На аккаунте WowDeath я убил себя пиная wand of wishing на первом уровне три раза за один день.

Хотя NetHack использует текущее время для старта ГПСЧ, очень просто изменить это на, например, опцию при старте NetHack’а. Вы можете запустить «игру из будущего», происходящую завтра в 11:00:00. Если результат Вас не устроит (например, неудачный стартовый инвентарь), вы можете порпробовать ещё раз — в 11:00:01. Процесс можно повторять до получения отличного стартового багажа, и впоследствии запустить игру на сервере точно в вычисленное время. Я пошёл дальше, генерируя тысячи стартовых уровней до получения wand of wishing (шанс такого события очень, очень мал). Paxed, один из администраторов nethack.alt.org, пропатчил Nethack для использования по настоящему случайного значения seed, и этот эксплоит больше там не работает.

Самой сложной частью, единственной где можно было провалиться, было начать игру на сервере в определённую секунду. Из за расхождения часов время сервера может быть на несколько секунд впереди или позади вашего. Сервер также не объявляет своё внутреннее время. Один из способов узнать текущее время — через сам seed! Начинаем игру на сервере, замечая текущее время на локальной машине. Потом генерируйте стартовые позиции Nethack’а, соответствующие этому времени, времени +/- 1 секунду, потом +/- 2 секунды и т.д. пока не окажетесь на той же карте с теми же характеристиками. Полученная разница — это и есть разница во времени между Вами и сервером. Правда эта разница может быть нецелой — Вы высчитываете её с разрешением в 1 секунду.

Этот метод описывает действительный путь злоупотребления ГПСЧ. Так как теперь у Вас есть серверная и локальная игры с одинаковым стартовым значением seed, вы можете играть локальную игру (помня о том что надо производить точно такие же действия на сервере) пока в какой то точке вы не решите «рассинхронизироваться». На самом деле это открывает ещё большие возможности, т.к. вы можете модифицировать локальную установку Nethack чтобы показывать предметы и всю карту. Наблюдающим за серверной игрой будет казаться что Вы заранее знаете где что находится.

Именно так мне впервые показали практическое использование ПГСЧ в nethack. Нетхакер по имени switch сказал мне начать игру и ждать. Потом он сказал «видишь ту кучу золота в правом верхнем углу комнаты? В ней 70 монет.» То что он сделал, я описал в предыдущем параграфе. Он нашёл seed моей игры и покопался в этой куче золота — предвидение.

Nethack.alt.org пропатчил вычисление начального значения seed, но как продемонстрировал нетхакер Adeon, всё ещё возможно узнать seed наблюдая за случайными эффектами. Имея возможность наблюдать случайные эффекты не изменяя состояния игры очень в этом помогает, т.к. перемещение монстров, происшествия на уровне и другие эффекты хода используют заранее неизвестное число случайных чисел. Используя что нибудь вроде artifact naming exploit вы можете наблюдать эффект определённого количества случайных чисел. Вы можете получить кусок последовательности любой необходимой Вам длины. Впоследствии это позволит Вам, например, получать желание при каждом глотке из фонтана — вы сможете просто «проматывать» те случайные числа, которые не приводят к получению желания.

Исправить это можно довольно просто — переинициализируя ГПСЧ каждые n (например 100) случайных чисел. Таким образом, ещё до того как вы сможете вычислить текущий seed, он будет заменён другим. Переинициализация должна использовать истинно случайные числа, иначе она будет происходить в нужную игроку секунду, с уже знакомыми нам последствиями.

Вам может быть интересно зачем вообще мы используем ГПСЧ; поему бы не использовать истинно случайный источник для каждого числа? К сожалению, у компьютера не так много источников по настоящему случайных чисел. Nethack, особенно на публичном сервере с 50 одновременно играющими людьми, быстро опустошит эти источники.

Этот тип эксплоитов может затронуть многие однопользовательские игры вроде Nethack’а, но я не думаю что есть смысл делать то же самое для других игр — одним из пред-условий такого хака является то что игра на сервере ценится больше чем игра на локальной машине. Коммерческие игры в любом случае используют серверы с закрытым исходным кодом. Настоящее применение такой тип эксплоитов находит только в криптоанализе.

Используйте истинно случайные числа для Ваших ключей! 🙂

Реклама
Добавить комментарий

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: