![](https://habrastorage.org/getpro/habr/upload_files/8eb/882/d45/8eb882d45a38e57704903497d520a2ad.png)
Мою первую статью я желаю посвятить истории о том, как я решил заняться исследованием часто встречающихся в модулях PlayStation Portable непонятных байтовых строк. Никакой документации в Homebrew коммьюнити найти не удалось, так что я взялся за дело сам.
Я начал реверсить игры под PSP с целью моддинга где-то два года назад, до этого как-то всё не мог собраться, хотя и наблюдал за Youtube-каналами других моддеров. В своём локальном коммьюнити по моддингу трилогии Patapon я неожиданно стал одним из самых продвинутых специалистов и начал ради интереса исследовать в Гидре абсолютно все игры, какие были на моей PSP-Go. Пока я это делал, я начал замечать, что в разделе данных иногда встречаются очень похожие друг на друга почти-что-ASCII строчки.
Больше часа искал этот скрин в Дискорде, когда писал статью...
![Вся эта последовательность ненулевых байт меня очень тогда заинтересовала Вся эта последовательность ненулевых байт меня очень тогда заинтересовала](https://habrastorage.org/getpro/habr/upload_files/bea/366/da3/bea366da355b64031b8438c338a814b3.png)
На них никто в программах не ссылался, так что способа выяснить, что это за звери, не было.
В один прекрасный день я заметил, что абсолютно такие же строчки присутствуют внутри ~SCE
хедеров некоторых PRX модулей.
PRX в контексте Playstation Portable
Сейчас с моей стороны продолжить повествование и не обрисовать, что такое PRX, неприемлемо.
На PSP исполняемые файлы имеют формат PRX (Playstation Relocatable Executable).
На самом деле, это немного модифицированный ELF:
Переосмыслено поле
p_paddr
в структуреElf32_Phdr
Добавлены новые виды релокации
Файл зашифрован криптографической системой KIRK
Приписан хедер, начинающийся с
~PSP
Однако существует ненулевое число модулей (как бы библиотеки, как обычный .dll
/.so
), у которых в начале стоит ещё один хедер:
![Файлик шрифтовой библиотеки в ресурсах игры Файлик шрифтовой библиотеки в ресурсах игры](https://habrastorage.org/getpro/habr/upload_files/136/510/876/136510876d1c8ca19dfb3e1f6e418f9b.png)
PPSSPP и загрузчик самой PSP в таком случае поступают максимально просто - считывают размер этого хедера (байты [0x4; 0x7]
), а затем скипают его, как будто его и не было. Как вы видите, внутри этого хедера лежит строчка, аналогичная той, которую я нашёл в данных игры (выделена). Если уж сама PSP не обращается к этому месту, становится понятно, что нам предстоит задача, аналогичная задаче понять язык, на котором уже никто не умеет ни читать, ни говорить.
Мой реверс-инжениринг сильно упростился, когда я нашёл достаточно много игр, которые ушли в релиз с дебажной информацией (я не о логах, которые в небольшом количестве присутствуют почти во всех играх, а о настоящей "-g" отладочной информации с номерами строк, сигнатурами функций, в общем, DWARF в лучшей своей форме).
В одной из игр я увидел, что рядом со строчкой стоял символ __psp_libinfo__
, так что я стал исходить из того, что смысл этих строк - что-то вроде версии либы, с которой была статически слинкована программа, а называть их стал “libinfo” (либи́нфо, во множественном числе “libinfos”, либи́нфы, под ударением звук "ы"). Все PRX файлы с хедером ~SCE
, которые были в моём распоряжении, оказались очень обрезанными - не то что дебажной информации или имён секций нет... Там вообще секций нет. Впрочем, внутри каждого нашлась ровно одна либинфа, совпадавшая с либинфой в хедере.
У меня сразу созрел план: собрать базу таких либинфочек, а потом автоматом Ахо-Корасик пройтись по файлам игр, чтобы понять, какие там присутствуют либы.
![Сразу узнаем, какие функции из SDK есть смысл искать в бинарнике, а какие - нет! А там уж и до содержательного кода дойдём... Сразу узнаем, какие функции из SDK есть смысл искать в бинарнике, а какие - нет! А там уж и до содержательного кода дойдём...](https://habrastorage.org/getpro/habr/upload_files/6fa/318/df4/6fa318df4eac987f5df97883fdfdd4ef.png)
Оказалось на практике, что у файлов с одинаковым именем могут быть разные либинфы, так что я начал приписывать к дублям суффикс _{номер}
.
![База - обычный JSON-файл, в котором имени сопоставляется base64 от байтов либинфы База - обычный JSON-файл, в котором имени сопоставляется base64 от байтов либинфы](https://habrastorage.org/getpro/habr/upload_files/d38/796/568/d3879656817ef652d0d9cb885132a8cb.png)
base64
от байтов либинфыМне показалось, что это нормально, ну в самом деле, если уж это версия библиотеки, то тут очевидно, что будет не одна либинфа. Впрочем, в столь большое количество ревизий библиотек не верилось. Вспомнить, откуда у меня в базе взялась та или иная запись, можно только обратившись к логам скрипта, который пополняет имеющуюся базу. Со сбором информации мне помог знакомый, который прогнал мой скрипт на PRX-ах из своего хранилища игр (у него несколько сотен игр по ощущениям).
Я решил, что пора взламывать эти строки. Первая идея - XOR с каким-то ключом. Перебрал 256 ключей - всё мимо. Пробовать большие размеры ключей я не стал, т.к. там либо непонятно, как ксорить, либо уже слишком сложная задача выходит. Кроме того, очевидно, что эти строки никакие не хеши: слишком похожи…
Я упомянул чуть ранее автомат Ахо-Корасик. Если вы не знали, он базируется на структуре данных "бор".
Бор, он же Trie
(Кстати, от слова reTRIEval
)
![Бор, содержащий слова “he”, “she”, “his” и “hers” Бор, содержащий слова “he”, “she”, “his” и “hers”](https://habrastorage.org/getpro/habr/upload_files/167/2ca/8fe/1672ca8fee7597917756f2a01ccee71e.png)
Эта структура позволяет относительно эффективно (и наглядно) хранить множество строк. Можно добавлять новые элементы, удалять их, а также проверять, есть ли строка во множестве. Бор - это корневое ориентированное дерево, где рёбра олицетворяют символы, а вершины - слова. Первое добавляемое в бор слово просто разбивается на цепочку символов и подвешивается к корню, при этом последняя вершина помечается, как "терминальная". Это нужно, чтобы структура знала, какие слова на самом деле содержатся в ней. При добавлении нового слова бор делает то же самое, но вместо того, чтобы подвешивать всегда к корню, он создаёт новую ветку в том месте, где у него уже не хватает символов в дереве (т.е. новое слово как бы отпочковывается в середине ветви). Таким образом достигается экономия - если у двух слов есть общий префикс, то он будет сохранён лишь единожды (см. фото выше). Чтобы добавить слово, чья цепочка уже имеется в боре, мы просто делаем последнюю вершину в ней терминальной.
Теперь очевидно, как искать строки в боре: перебираем все буквы во входном слове и пытаемся пройти от корня такой же путь в дереве. Если нет какой-то вершины, сразу говорим, что строки в боре нет, а если мы успешно прошли весь путь, то проверяем, терминальная ли вершина. Удаление меня не интересует, но это делается очень просто - ищем слово, а затем снимаем флаг терминальности с вершины, если она нашлась. Плюс-минус ещё память чистим...
Неочевидным остаётся вопрос реализации этого дерева, т.к. каждая вершина должна как-то знать всех своих детей, причём проверка на включение должна быть быстрой, так что вектор из std::unique_ptr
не очень подойдёт. Если алфавит (множество букв, которое может встретиться в строчках) имеет размер N
, можно в вершине хранить массив из N
указателей и char
превращать в индекс через вычитание первого символа алфавита… Но не всегда это удобно, так что я использовал словари. Кроме того, я добавил всем вершинам поле "тег", чтобы хранить какую-нибудь дополнительную информацию в нём.
Получился вот такой код:
class TrieNode:
def __init__(self):
self.value = 0x0
self.terminal = False
self.children: Dict[int, TrieNode] = collections.defaultdict(TrieNode)
self.tag: Any = None
def __repr__(self):
return chr(self.value)
def __str__(self):
return chr(self.value)
# That's the generator behind the TrieIterator class
def get_trie_words(root: TrieNode):
if root.terminal:
# We're a word in the Trie, let's return nothing
yield b""
for letter, child in root.children.items():
suffixes = get_trie_words(child)
yield from (letter.to_bytes(1, "little") + word for word in suffixes)
def count_trie_words(root: TrieNode):
count = 1 if root.terminal else 0
for child in root.children.values():
count += count_trie_words(child)
return count
# Constructed by the Trie.__iter__ method
class TrieIterator:
def __init__(self, node: TrieNode):
self.gen = get_trie_words(node)
def __iter__(self):
return self
def __next__(self):
value = next(self.gen)
if value is None:
raise StopIteration
return value
class Trie:
def __init__(self):
self.root = TrieNode()
def add(self, word: bytes, tag: Optional[Any] = None):
current = self.root
for letter in word:
current = current.children[letter]
current.value = letter
if not current.terminal:
current.terminal = True
if tag is not None:
current.tag = tag
def __contains__(self, item):
current = self.root
for letter in item:
if letter not in current.children:
return False
current = current.children[letter]
return current.terminal
def __getitem__(self, item):
current = self.root
for letter in item:
if letter not in current.children:
raise KeyError(f"{item} not found in Trie!")
current = current.children[letter]
return current
def __iter__(self):
return TrieIterator(self.root)
def __len__(self):
return count_trie_words(self.root)
Эффективен ли этот код? По-моему, get_trie_words
- жуткий костыль, но у меня нет абсолютно никаких причин переосмысливать всю структуру. Тем более, что у меня нет ограничений по времени на работу...
Я сразу решил, что бор нужно визуализировать посредством графвиза. Как устанавливать его, рассказывать не буду, есть достаточно внятные инструкции в инете. К счастью, я уже с ним работал через Python (pygraphviz
позволяет эмиттить *.gv
-файлы), так что в этот раз было не шибко сложно. Мне было нужно обойти бор и зарегистрировать вершины (они здесь именуются не "vertex", а "node"), а затем проделать то же самое с рёбрами.
Обычно в боре пишут символы на рёбрах, а в вершинах пишут слова целиком, но я догадывался, что вершины будут огромные и картинка получится не очень наглядной, так что в вершинах я тоже писал символы. (Ну, кроме терминальных, конечно… Там всё-таки надо написать слова). Чтобы было совсем удобно, я всем терминальным вершинам в качестве тега дал имя модуля и разместил под строчкой. Кстати, тут уже base64
не поможет, надо запихивать наш недо-ASCII в граф. Я сделал свой рендерер, т.к. Питон считает, что \x7F
- printable. Может, DEL
и на самом деле printable, но мне квадратики в консоли и пустое место на картинке не нужны…
Исследование
Наконец все инструменты изготовлены, можно начинать анализ! Во-первых, я решил собрать статистику. Скрипт-анализатор загружает базу либинф и печатает на экран следующую информацию:
Длины либинф
Суммарный алфавит всех либинф
Символы, встречающиеся на i-ой позиции в либинфах
Сжатая форма алфавита - в отсортированном алфавите схлопываем рэнжи последовательно идущих символов (скажем, лист
['A','B','C','D','M','X']
превращается в строку"[A; D], M, X"
)
А что насчёт частот символов?
Частотным анализом я баловаться не стал, т.к. не было никакой уверенности, что за этим кроется речь на каком-то языке. Тем более, что непонятно, с чем такое можно сверять… Ну вдруг это зашифрованный Shift-JIS с иероглифами… А даже если английский, оно всё равно оно маловероятно будет подчиняться известному распределению, всё-таки выборка очень специфичная.
Оказалось, что все строчки имеют одинаковую длину 0x18 байт, причём у них общий префикс длиной 8 байт: \yr=`c`0
. Впрочем, последнее наблюдение можно было сделать и с помощью графа.
Вот такой вот ствол у моего дерева
![Я по традиции экспортирую в SVG, т.к. обычно мои графы ОЧЕНЬ большие и на PNG не влезают в приемлемом качестве… Я по традиции экспортирую в SVG, т.к. обычно мои графы ОЧЕНЬ большие и на PNG не влезают в приемлемом качестве…](https://habrastorage.org/getpro/habr/upload_files/d79/31a/8d7/d7931a8d703b4d930697719e38288b72.png)
Дальнейшие открытия без визуальной составляющей я бы уже не сделал. Вглядываясь в SVG, я заметил, что либинфы, соответствующие модулям с одинаковыми названиями, как бы сгруппированы в поддеревья. Более того, глубина таких поддеревьев - 4 вершины, не считая корневую.
![Семейство таких похожих, но таких разных libmd5.prx Семейство таких похожих, но таких разных libmd5.prx](https://habrastorage.org/getpro/habr/upload_files/759/18f/93f/75918f93fd973af46b0397fff1a3e79b.png)
libmd5.prx
Теперь я бы хотел закрепить терминологию: префикс либинфы - первые 8 байт, тело либинфы - следующие 12 байт, суффикс либинфы - последние 4 байта.
У меня возникла гипотеза, что тело отвечает за идентификацию модуля, а суффикс - за версию. С учётом этого я сгенерировал новый SVG, где в качестве слов уже использовал обрезанные либинфы. Отрезал я префикс и суффиксы, а в качестве имени модуля использовал первый попавшийся из поддерева. Стало лучше, я бы сказал, минималистичнее.
![](https://habrastorage.org/getpro/habr/upload_files/9b8/a3a/813/9b8a3a813f98172a0cc9bae556783295.png)
Я был готов сдаться и начать паковать мои скрипты, чтобы отдать на растерзание PSP Homebrew коммьюнити, как вдруг меня осенило.
Пол второго ночи… Я очумелыми глазами пялился в группу библиотек libsfmt{цифры}
, как вдруг я заметил, что на рёбрах в поддереве были написаны капсом буквы латинского алфавита. Немного сопоставлений... и я понял, что это всё значит!
![Двойку я воспринял, как некий терминальный символ, которым забивают тело, если ещё остались байты Двойку я воспринял, как некий терминальный символ, которым забивают тело, если ещё остались байты](https://habrastorage.org/getpro/habr/upload_files/5dd/00c/eb5/5dd00ceb58b01782fb5f97a494ca8a10.png)
Тогда-то я и понял, что это, скорее всего, шифр Цезаря! В данном случае, правда, алфавит - множество из 256 значений одного байта. Первые 128 - ASCII, остальное - вообще говоря, ничего, но на практике там у нас живёт региональный extended ASCII… но не будем о грустном.
def _transform(word: bytes, shift: int):
ans = bytearray(len(word))
for index, letter in enumerate(word):
ans[index] = letter - shift
return ans.decode("ascii")
Я написал дешифровщик для нашего шифра и прогнал его на всех либинфах, взяв сдвиг равным -0x12
. Все тела дешифровались и оказались просто сокращёнными версиями имён модулей (двойки оказались пробелами), а вот префикс и суффикс не починились. Тогда я предположил, что они зашифрованы другим сдвигом.
Начал я с префикса… Перебрал все сдвиги, ничего не нашёл.
Затем взял все суффиксы и стал перебирать сдвиги одновременно для всех.
![Единственным сдвигом, который выглядел правдоподобно, оказался -0x14 Единственным сдвигом, который выглядел правдоподобно, оказался -0x14](https://habrastorage.org/getpro/habr/upload_files/743/a0c/ef7/743a0cef7bc56ad044e69f1da97c92f9.png)
-0x14
Я предположил, что это версии SDK. Пошёл читать сурсы PPSSPP и подтвердил теорию! "500b", скорее всего, означает бета-версию! Что ж, пожалуй, теперь всё встаёт на свои места - у нас ревизий отдельных модулей может быть мало, а вот самих SDK было много.
Затем я ещё раз прогнал тесты над префиксом и понял, что плохо искал…
Всё было перед глазами, но я проглядел это.
![А ларчик просто открывался! А ларчик просто открывался!](https://habrastorage.org/getpro/habr/upload_files/a31/6bf/123/a316bf123695f1a48d7b410dfa571059.png)
Я поделился открытием с создателем PPSSPP (Henrik Rydgård), после чего он спросил, не смог бы я PRнуть в эмулятор логирование загрузки таких ~SCE
модулей. Я смог. Здесь же можно посмотреть на пример полностью дешифрованных имён библиотек (на скрине).
Заключение
Я чрезвычайно рад, что смог наконец-то проломить эту тайну, которая меня донимала несколько месяцев!
Во-первых, я себя проявил в реверсе самой PSP, хотя казалось бы, что уже ничего не осталось там неизвестного, что мне подвластно.
Во-вторых, теперь можно официально начать охоту на статические библиотеки в исполняемых файлах. Пока я исследовал имеющиеся под рукой игры, я наткнулся на Locoroco 1. Там я нашёл ранее неизвестные якобы стандартные функции (начинаются с "sce", например
scesupMsiolRename
). Вообще, сейчас есть уже как минимум четыре либы, про которые нет никакой информации в интернете:supac2ms-SJ9
,libwr2pt-SJ2
,libmsiol-SJ5
,spac2msR-PD0
. Будем исследовать! Нашлась и либа, где последним символом стоит нуль-байт (и после дешифровки мы улетаем в область0xec
), так что я в pull request PPSSPP добавил проверку черезisprint
перед выводом в консоль.В-третьих, моё открытие дало доказательство, что
Lib-PSP iplloader
не является официальным названием бутрома PSP (и поэтому на странице вики убралиLib-PSP
из альтернативного названия).
Если будет интересно, я планирую сделать что-то вроде цикла статей про Гидру и с чем её есть, к тому же я сам себе задолжал статью про ImHex.