Когда Random совсем не случаен

Этот пост — рассказ об истории, случившейся больше десятка лет назад; её код был мной утерян. Поэтому прошу простить меня, если я не вспомню точно все подробности. Кроме того, некоторые подробности упрощены, чтобы от этой статьи могли получить удовольствие все, кому нравится компьютерная безопасность, а не только любители World of Warcraft (хотя, полагаю, диаграмма Венна этих двух групп сильно пересекается).

Когда мне было примерно 14 лет, я узнал об игре World of Warcraft компании Blizzard Games, и она сразу же меня увлекла. Вскоре после этого я нашёл аддоны, позволявшие модифицировать внешний вид и функциональность интерфейса игры. Однако не все скачанные мной аддоны делали именно то, что мне было нужно. Мне хотелось большего, поэтому я начал разбираться, как они сделаны.

Забавно, что в моём серьёзном увлечении программированием можно обвинить World of Warcraft. Оказалось, что код был написан на языке Lua. Аддоны — это просто парочка файлов исходного кода на .lua в папке, напрямую загружаемых в игру. Барьер входа был невероятно низок: достаточно отредактировать файл, сохранить его и перезапустить интерфейс. То, что игра загружала твой исходный код и ты мог видеть его работу, было настоящим волшебством!

Мне это невероятно нравилось, и вскоре я уже практически не играл в игру, а занимался только написанием аддонов. За следующие два года я опубликовал приличное их количество; в большинстве случаев я просто копировал чужой код и рефакторил/комбинировал/настраивал его под свои нужды.

Безопасность аддонов

Возможно, вы подумаете, что давать пользователям возможность создания полностью программируемых аддонов — плохая идея, ведь так в игре появятся боты. Однако Blizzard придумала довольно умную систему, предотвращающую выполнение произвольных программируемых действий. Естественно, она ничего не сделала для предотвращения ботоводства, но, по крайней мере, обычные, подчиняющиеся правилам игроки были ограничены только той автоматизацией, которую допускала Blizzard.

Большинство создаваемых пользователями элементов UI было строго декоративным или информационным. Они ничем не ограничивались, потому что по большей мере использовали только API, занимавшиеся только сбором информации. Например, можно было создать полосу здоровья из двух рамок, передней и фоновой, и менять размер передней рамки, делая вызов API для получения здоровья персонажа.

Однако пользователям были доступны не все вызовы API. Некоторые были защищены, так что их можно было вызывать из официального кода Blizzard. Обычно это были вызовы API, перемещавшие персонажа, кастовавшие заклинания, применявшие предметы и так далее. По сути, всё, что позволяло выполнять внутриигровые действия, было защищено.

В какой-то момент времени стали защищёнными и API, получающие точное расположение игрока в мире и положение камеры. Так Blizzard отреагировала на новые аддоны, активно отрисовывавшие 3D-элементы поверх мира игры, что упрощало битвы с боссами.

Однако некоторые элементы UI должны были взаимодействовать с самой игрой, например, если нужно было создать кнопку, кастующую заклинание. Для этого можно было изготовить специальный тип кнопки, при нажатии исполнявшей код в защищённом окружении. Игрок мог создавать/уничтожать/перемещать такие кнопки, только не находясь в бою, поэтому нельзя было условными операторами помещать такие кнопки под курсор, чтобы автоматизировать действия во время боя.

Сложность заключалась в том, что это защищённое окружение позволяло программно задавать кастуемое заклинание, но не давало собирать информацию, необходимую для выполнения произвольной автоматизации. Весь доступ к состоянию снаружи защищённого окружения был заблокирован. Существовало несколько вызовов API сбора информации, схожих с более доступной системы внутриигровых макросов, но ничего более сложного, чем получение кулдаунов навыков или здоровья юнитов, что позволяло бы реализовать автоматическую оптимизацию кастования заклинаний.

Итак, существовало два окружения: незащищённое, в котором можно было получать всю информацию, но не действовать на её основании, и защищённое, в котором можно действовать, но нельзя получать информацию, необходимую для автоматизации.

Бэкдор-канал

Перенесёмся на пару лет вперёд, когда я почти перестал играть. Меня стало в основном интересовать «серьёзное программирование», а играл я лишь время от времени, чаще всего просто экспериментируя с идеями аддонов. Но меня не переставало будоражить защищённое окружение; я хотел его взломать.

Разумеется, было стороннее ПО, полностью отключавшее ограничения безопасности Blizzard, но разве это весело? Я хотел сделать это «законным образом», решить эту сложную задачу при помощи только разрешённых инструментов.

Очевидно, что использование хитрого кода для обхода защит не лучше, чем применение стороннего ПО: скорее всего, и то, и другое приведёт к бану. Я не хотел пользоваться этим кодом, просто думал проверить, сможет ли он работать.

Я изучил список разрешённых в защищённом окружении функций, чтобы проверить, смогу ли контрабандой протащить какую-нибудь информацию снаружи в защищённое окружение. Всё это казалось практически безнадёжным, пока я не увидел крошечную невинную функцию random.

В моей голове возникла хитроумная идея: используемые в компьютерах генераторы случайных чисел (RNG) почти всегда бывают псевдослучайными и имеют внутреннее состояние (скрытое). Если мне удастся манипулировать этим состоянием, то, возможно, я смогу передать информацию в защищённое окружение.

Ужасы генератора случайных чисел

Функция random оказалась лишь тонкой обёрткой поверх rand языка C. Я был в восторге! Это значило, что существовала единое глобальное переменное состояние случайности, общее для процесса. Помогло и то, что реализации rand обычно имели слабые стороны. Так как World of Warcraft компилировалась при помощи MSVC, реализация rand была такой:

uint32_t state;

int rand() {
    state = state * 214013 + 2531011;
    return (state >> 16) & 0x7fff;
}

Этот RNG был (не могу подобрать более подходящего слова) хреновым. Это голый линейный конгруэнтный генератор, и в этом заключалась его слабость. А она была мне на руку.

Я могу понять, что в MSVC rand сохранялась одинаковой ради обратной совместимости, и, по крайней мере, во всей найденной мной документации rand  не рекомендовали использовать её для криптографических задач. Но разве настолько плохая реализация PRNG вообще может пригодиться для чего-либо?

Давайте сломаем эту функцию. Так как состояние так смехотворно мало и мы можем непосредственно видеть 15 битов состояния, то можно хранить полный список всех возможных состояний, согласованных с единственным выходным значением RNG, и использовать дальнейшие вызовы RNG для устранения возможных вариантов, пока не останется только один. Но можно поступить и гораздо умнее.

Сначала обратим внимание на то, что старший бит state не влияет ни на что в этом RNG. (state >> 16) & 0x7fff маскирует 15 битов после сдвига нижних 16 битов, то есть, по сути, работает как mod 231231. Так как при любом обновлении новое состояние оказывается линейной функцией от предыдущего состояния, мы можем распространить эту форму с вычислением остатка вниз вплоть до исходного состояния, поскольку

для любой линейной f.

Пусть a = 214013 и b = 2531011. Мы наблюдаем 15-битный вывод r₀​, r₁​ двух вызовов RNG. Вызовем 16-битную часть состояния RNG, скрытую сдвигом ℎ₀,ℎ₁ для состояний после первого и второго вызова. Это значит, что состояние RNG после первого вызова имеет вид 2¹⁶r₀​ + h_0​ и аналогично для 2¹⁶r₁ ​+ h₁​ после второго вызова. Получаем следующее равенство:

Теперь если c ≥ 0 будет известной константой (2¹⁶(r₁​ − ar₀​) − b) mod 2³¹, то для некого целого k мы имеем

Стоит отметить, что левая часть изменяется в интервале от 0 до (2¹⁶ − 1) ≈ 2^33.71. То есть мы должны иметь −1 ≤ k ≤ 2^2.71 < 7. Изменив порядок членов, получим следующее выражение для h₀​:

Так как a > 2¹⁶ и 0 ≤ h₁ ​< 2¹⁶, отметим, что член 0 ≤ h₁​/a <1. Значит, предположив существование решения, мы должны получить

То есть для −1 ≤ k < 7 мы вычислим приведённую выше догадку о скрытой части состояния RNG после первого состояния. Это даёт нам 8 попыток, после чего мы можем отклонять неправильные догадки при помощи последующих вызовов RNG, пока не останется единственный уникальный ответ.

Сегодня мне с лёгкостью удалось вывести всё приведённое выше, но в 18 лет я не был таким опытным в дискретной математике. Поэтому я задал вопрос на crypto.SE, объяснив его тем, что хочу «показать коллегам, насколько слаб этот RNG». Это сработало, что вызывает множество интересных этических вопросов.

Пример реализации этого процесса на Python:

import random

A = 214013
B = 2531011

class MsvcRng:
    def __init__(self, state):
        self.state = state
        
    def __call__(self):
        self.state = (self.state * A + B) % 2**32
        return (self.state >> 16) & 0x7fff

# Создаём случайное состояние RNG, которое будем реверс-инжинирить.
hidden_rng = MsvcRng(random.randint(0, 2**32))

# Вычисляем догадки о скрытом состоянии по двум наблюдениям.
r0 = hidden_rng()
r1 = hidden_rng()
c = (2**16 * (r1 - A * r0) - B) % 2**31
ceil_div = lambda a, b: (a + b - 1) // b
h_guesses = [ceil_div(c + 2**31 * k, A) for k in range(-1, 7)]

# Валидируем догадки, пока не остается единственная.
guess_rngs = [MsvcRng(2**16 * r0 + h0) for h0 in h_guesses]
guess_rngs = [g for g in guess_rngs if g() == r1]
while len(guess_rngs) > 1:
    r = hidden_rng()
    guess_rngs = [g for g in guess_rngs if g() == r]
    
# Верхний бит невозможно восстановить, потому что никогда не влияет на вывод,
# но мы восстановили истинное скрытое состояние.
assert guess_rngs[0].state % 2**31 == hidden_rng.state % 2**31

Хотя я написал показанный выше процесс с помощью цикла while, похоже, что ему всегда максимум требуется лишь третье входное значение, чтобы сузить поиск до единственной догадки.

Соединяем всё вместе

Выполнив реверс-инжирининг внутреннего состояния генератора случайных чисел, мы можем принимать произвольные автоматизированные решения в окружении, которое должно быть защищённым. Работало это следующим образом:

1. Регистрировался незащищённый хук, исполнявшийся прямо перед запуском кода защищённого окружения.

2. В этом хуке у нас есть полный доступ к информации и принимается решение о том, какое действие должно быть выполнено (например, кастование конкретного заклинания). Это действие ищется в заранее заданном списке для получения индекса.

3. При помощи описанного выше процесса выполняется реверс-инжиниринг текущего состояния RNG.

4. Мы предсказываем результат следующего вызова RNG. Если он (делённый по модулю на длину нашего списка действий) не даёт нам нужного результата, то мы сдвигаем RNG и пробуем снова. Процесс повторяется, пока следующее случайное число не будет соответствовать нужному действию.

5. Хук выполняет возврат, и запускается защищённое окружение. Оно генерирует «случайное» число, индексирует наш список действий и выполняет «случайное» действие.

Вот и всё! Имея возможность симулировать RNG и заглядывать на один шаг вперёд, мы можем использовать это как канал информации, выбирая идеальный момент для вызова random в защищённом окружении. Если вам нужен список из n возможных действий, то для получения нужного номера, который можно передать, RNG в среднем понадобится n шагов, но на практике это не представляло проблемы.

Заключение

Не знаю, когда Blizzard устранила проблему со слабым и общим для игры состоянием RNG, да и вообще знала ли компания о ней. Несколько лет спустя я попробовал из любопытства снова запустить код, но он уже не работал. Возможно, разработчики перешли на другой алгоритм или отделили состояние RNG от защищённого окружения.

В целом это слишком трудоёмкая работа для нишевого эксплойта видеоигры, которым я даже не собирался пользоваться. Но в том, чтобы сманипулировать чем-то на первый взгляд случайным для получения нужного результата было настоящее волшебство; я походил на фокусника, вытянувшего четыре туза их перетасованной колоды.