Spiiin's blogИгра посвящена событиям двадцатилетней давности, а именно Чемпионату Мира по футболу в США 1990 года.
Понять, что именно этому, а не какого-нибудь другому, можно только по дате выхода игры, потому что разработчики из Tecmo взяли из 24 реально участвующих там команд 13, добавили к ним зачем-то Францию, Польшу и Японию (Впрочем, Японию понятно зачем).
Регламент турнира они тоже изменили, и поэтому выбранной игроком команде в борьбе за чемпионский тутил предстоит победить всех остальных. Так как турнир при таком раскладе получается для одной из команд довольно длинный, то игроку представлена возможность начать игру не сначала, а с некоторым количеством уже выбитых команд, указав для удостоверения своих результатов выдаваемый игрой пароль.
Для разминки мозгов мне захотелось найти метод генерации этого пароля. Процесс разгадывания сгодится как базовый туториал по хаку игр.
Часть 1.
Пароли в игре состоят из 9 букв, причем игра позволяет вводить только буквы от A до P. 16 символов в 9 позициях, значит всего существует 16**9 = 68 719 476 736 паролей. Число правильных паролей также можно посчитать. Для каждой команды есть пятнадцатиразрядный вектор из двоичных значений, показывающий, выбит ли её соответствующий соперник. Все такие вектора являются правильными паролями, кроме вектора из всех нулей (нет пароля, пока никто не выбит) и вектора из всех единиц (нет пароля на все выбитые команды). Значит, всего есть 16 * (2**15-2) = 524 256 верных значений.
Часть 2.
Отношение верных паролей к полному их числу показывает, что на миллион паролей приходится где-то 7-8 правильных.
То есть просто выбирая случайные цифры, подобрать правильный пароль сложно. Но можно взять один из правильных паролей, сгенерированных игрой, и попробовать менять пары его символов. Данный метод изредка работает, из одного правильного пароля таким образом удается получить еще 3-4, что для начала неплохо, но получить из этого какие-то правила пока сложно.
Дальше можно набрать как можно больше паролей и сравнивать разность наиболее близких по смыслу пар паролей (метод “черного ящика” - внутренности системы неизвестны, зато можно легко анализировать её входы и выходы). Для получение большого числа паролей нужно как-то ускорить процесс их получения. Например, можно использовать поиск читов в эмуляторе FceUltra или ArtMoney.
С помощью поиска нужно найти в памяти ячейки, которые отвечают за кол-во минут до конца матча и счет. Так можно за несколько секунд прописывать себе победу и сохранять сгенерированный игрой пароль. Полученная таблица для всех побежденных 1-х соперников сборной Бразилии :
Германия GDJGMBAFA |
Соседние пароли отличаются друг от друга довольно сильно :( Тут мне не повезло, так как я взял в качестве своей команды сборную Бразилии, стоящую в списке команд первой, и долго не замечал той вещи, что если “выбивать” Бразилию, то разность паролей от этого меняется меньше всего, что должно было бы сразу сигнализировать, что на пароль влияют не только выбитые команды, но и номер побежденного соперника.
Но к этому я пришел только, когда заметил, что при выбивании команд в разном порядке можно получить разные пароли. Зато в ходе экспериментов оказалось, что правильных паролей существует во 30 раз больше (каждый раз игра может сгенерировать 15 разных, в зависимости от текущей команды соперника, и, кроме того, при поражении выдается специальный пароль, который позволяет сыграть с той же самой командой, без жеребьевки, что еще вдвое удваивает количество верных пассов). После этого осталось только найти в памяти с помощью того же поиска читов номер текущего соперника и занулять его сразу после финального свистка судьи. Так получилась “чистая таблица” в которой были исключительно эффекты от победы над командой:
Германия EDJGMDONA |
Здесь уже точно видно, что каждая из команд _почти_ всегда выбивается взаимным изменением пары символов (например, для устранения Франции 1-й символ увеличивается на 1, а третий - на 2). Запомнив эту разность, ее можно проверить на другом исходном правильном пароле и убедиться, что действительно выбивается та же команда. _почти_ всегда.
Примерно в одном из восьми случаев внезапно вместо пары символов меняются почти все. Это показывает, что в генераторе пароля где-то присутствует обратная связь, мешающая просто убирать команды таким методом.
Кажется, что этот иногда работающий способ - лучший, которого можно добиться, просто анализируя генерируемые игрой пароли, если только вы не Шерлок Холмс и не прогнозирующая нейронная сеть.
Часть 3.
Так как простые методы не дают результата, приходится использовать более мощные инструменты. Далее понадобится сборка эмулятора для отладки FCEUltra SP и дизассемблер Ida Pro, понимающий архитектуру 6502 для интерактивного анализа кода.
Сначала необходимо получить образ памяти для анализа, так как просто открыть ROM в дизассемблере мало - в нем может быть несколько банков памяти, отражающихся на одно адресное пространство процессора.
Вместо этого лучше открыть в эмуляторе просмотр памяти (ёTools->HexEditorё) и скопировать ее всю в отдельный файл.
Необходимо найти в памяти функцию, проверяющую правильность введенного пользователем пароля. Сложная, иногда требующая интуиции и удачи часть. Здесь решается относительно просто. Нужно в игре набрать случайный пароль и дальше найти его в памяти эмулятора. Там он есть в виде аски символов на экране и в виде чисел от 0 до 15.
Теперь на найденные адреса в отладчике ставятся точки остановки на чтение (нужно узнать, какая инструкция попытается считать введенные значения). Далее следует еще один сложный шаг - пошаговое слежение за выполнением функции в отладчике, с целью отловить ее окончание, чтобы понять, куда вернется программа, выполнив проверку на корректность пароля.
В результате выясняется, что вызов функции проверки находится по адресу $A816 [JSR A8A2], которая с адреса $A95E [RTS] возвращает управление обратно. Эти 328 байт необходимо из машинных инструкций мысленно превратить в код и понять его смысл.
Настоятельно рекомендую делать это с помощью отдельного дизассемблера ( например Ida Pro, туториал по использованию есть у Griever’а), потому что в отладчике делать это очень неудобно.
Дизассемблированный код алгоритма (с комментариями): http://www.everfall.com/paste/id.php?bpgzprxyq26j
Дальше код алгоритма надо переписать в отдельную программу (на любом языке, например, python), которая будет проверять его на корректность и выдавать результат - (команда игрока, команда соперника, какие команды выбиты и будет ли жеребьевка перед стартом очередного матча).
Код: http://www.everfall.com/paste/id.php?coljec5m2j2r
Так можно запустить подборщик паролей. А пока он работает, еще чуть посчитать. Правильное число правильных паролей - 256*256*16*16*2 (два байта на выбитые команды, 256 пар и бит жеребьевки) = 33 554 432, в 64 раза больше начальных прикидок.
Среди правильных паролей имеются такие, которые игра никогда не выдаст, и даже такие, которые по логике не должны выпадать никогда.
Например, игра с уже побежденной командой, выбивание своей собственной команды, “пустой пароль” без выбитых команд и “зеркальная игра” одной сборной:
Первый найденный брутфорсом пароль AAAAEBPFJ.
Собственно, подборщик лучше остановить, так как он будет работать очень долго, и заняться процедурой генерации пароля.
Ее можно получить, “развернув” все действия в обратном направлении или просто найти в памяти, поставив точку остановки отладчика на чтение на адрес $A6F1, где хранятся константы трансформации, найденные во время реверсирования процедуры проверки.
Версия генератора на питоне:
http://www.everfall.com/paste/id.php?ou56bj09642s
Попутно можно исследовать байт, в котором хранится бит жеребьевки. Другие биты и байты по соседству управляют состоянием матча и номерами-указателями на цвета команда.
Лулзов ради можно сдвинуть эти указатели за границу стандартных шестнадцати цветов команд и сыграть матч между сборной Фиолетововолосых Травяных Людей и сборной Пандорры:
Напоследок можно вырвать из видеопамяти кусок, хранящий шрифт игры ( Tools->PPU Viewer… в FCEUltra в момент, когда на экране есть текст), и отрисовывать пароли именно им.
Пароли на все возможные финалы:
