История о том, как Graphviz и бор взломали шифр от Sony

Мою первую статью я желаю посвятить истории о том, как я решил заняться исследованием часто встречающихся в модулях PlayStation Portable непонятных байтовых строк. Никакой документации в Homebrew коммьюнити найти не удалось, так что я взялся за дело сам.

---

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

Больше часа искал этот скрин в Дискорде, когда писал статью…

На них никто в программах не ссылался, так что способа выяснить, что это за звери, не было.

В один прекрасный день я заметил, что абсолютно такие же строчки присутствуют внутри ~SCE хедеров некоторых PRX модулей.

PRX в контексте Playstation Portable

Сейчас с моей стороны продолжить повествование и не обрисовать, что такое PRX, неприемлемо.

На PSP исполняемые файлы имеют формат PRX (Playstation Relocatable Executable).

На самом деле, это немного модифицированный ELF:

1. Переосмыслено поле p_paddr в структуре Elf32_Phdr

2. Добавлены новые виды релокации

3. Файл зашифрован криптографической системой KIRK

4. Приписан хедер, начинающийся с ~PSP

Однако существует ненулевое число модулей (как бы библиотеки, как обычный .dll/.so), у которых в начале стоит ещё один хедер:

Оказалось на практике, что у файлов с одинаковым именем могут быть разные либинфы, так что я начал приписывать к дублям суффикс _{номер}.

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

Я решил, что пора взламывать эти строки. Первая идея — XOR с каким-то ключом. Перебрал 256 ключей — всё мимо. Пробовать большие размеры ключей я не стал, т.к. там либо непонятно, как ксорить, либо уже слишком сложная задача выходит. Кроме того, очевидно, что эти строки никакие не хеши: слишком похожи…

Я упомянул чуть ранее автомат Ахо-Корасик. Если вы не знали, он базируется на структуре данных «бор».

Бор, он же Trie

(Кстати, от слова reTRIEval)

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

Теперь очевидно, как искать строки в боре: перебираем все буквы во входном слове и пытаемся пройти от корня такой же путь в дереве. Если нет какой-то вершины, сразу говорим, что строки в боре нет, а если мы успешно прошли весь путь, то проверяем, терминальная ли вершина. Удаление меня не интересует, но это делается очень просто — ищем слово, а затем снимаем флаг терминальности с вершины, если она нашлась. Плюс-минус ещё память чистим…

Неочевидным остаётся вопрос реализации этого дерева, т.к. каждая вершина должна как-то знать всех своих детей, причём проверка на включение должна быть быстрой, так что вектор из 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 — жуткий костыль, но у меня нет абсолютно никаких причин переосмысливать всю структуру. Тем более, что у меня нет ограничений по времени на работу…

Я сразу решил, что бор нужно визуализировать посредством )

А что насчёт частот символов?

Частотным анализом я баловаться не стал, т.к. не было никакой уверенности, что за этим кроется речь на каком-то языке. Тем более, что непонятно, с чем такое можно сверять… Ну вдруг это зашифрованный

Вот такой вот ствол у моего дерева

Дальнейшие открытия без визуальной составляющей я бы уже не сделал. Вглядываясь в SVG, я заметил, что либинфы, соответствующие модулям с одинаковыми названиями, как бы сгруппированы в поддеревья. Более того, глубина таких поддеревьев — 4 вершины, не считая корневую.

Теперь я бы хотел закрепить терминологию: префикс либинфы — первые 8 байт, тело либинфы — следующие 12 байт, суффикс либинфы — последние 4 байта.

У меня возникла гипотеза, что тело отвечает за идентификацию модуля, а суффикс — за версию. С учётом этого я сгенерировал новый SVG, где в качестве слов уже использовал обрезанные либинфы. Отрезал я префикс и суффиксы, а в качестве имени модуля использовал первый попавшийся из поддерева. Стало лучше, я бы сказал, минималистичнее.

Я был готов сдаться и начать паковать мои скрипты, чтобы отдать на растерзание PSP Homebrew коммьюнити, как вдруг меня осенило.

---

Пол второго ночи… Я очумелыми глазами пялился в группу библиотек libsfmt{цифры}, как вдруг я заметил, что на рёбрах в поддереве были написаны капсом буквы латинского алфавита. Немного сопоставлений… и я понял, что это всё значит!

Тогда-то я и понял, что это, скорее всего, 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. Все тела дешифровались и оказались просто сокращёнными версиями имён модулей (двойки оказались пробелами), а вот префикс и суффикс не починились. Тогда я предположил, что они зашифрованы другим сдвигом.

Начал я с префикса… Перебрал все сдвиги, ничего не нашёл.

Затем взял все суффиксы и стал перебирать сдвиги одновременно для всех.

Я предположил, что это версии SDK. Пошёл читать сурсы PPSSPP и подтвердил теорию! «500b», скорее всего, означает бета-версию! Что ж, пожалуй, теперь всё встаёт на свои места — у нас ревизий отдельных модулей может быть мало, а вот самих SDK было много.

Затем я ещё раз прогнал тесты над префиксом и понял, что плохо искал…

Всё было перед глазами, но я проглядел это.

Я поделился открытием с создателем PPSSPP (Henrik Rydgård), после чего он спросил, не смог бы я PRнуть в эмулятор логирование загрузки таких ~SCE модулей. Я смог. Здесь же можно посмотреть на пример полностью дешифрованных имён библиотек (на скрине).

Заключение

Я чрезвычайно рад, что смог наконец-то проломить эту тайну, которая меня донимала несколько месяцев!

1. Во-первых, я себя проявил в реверсе самой PSP, хотя казалось бы, что уже ничего не осталось там неизвестного, что мне подвластно.

2. Во-вторых, теперь можно официально начать охоту на статические библиотеки в исполняемых файлах. Пока я исследовал имеющиеся под рукой игры, я наткнулся на Locoroco 1. Там я нашёл ранее неизвестные якобы стандартные функции (начинаются с «sce», например scesupMsiolRename). Вообще, сейчас есть уже как минимум четыре либы, про которые нет никакой информации в интернете: supac2ms-SJ9, libwr2pt-SJ2, libmsiol-SJ5, spac2msR-PD0. Будем исследовать! Нашлась и либа, где последним символом стоит нуль-байт (и после дешифровки мы улетаем в область 0xec), так что я в pull request PPSSPP добавил проверку через isprint перед выводом в консоль.

3. В-третьих, моё открытие дало доказательство, что Lib-PSP iplloader не является официальным названием бутрома PSP (и поэтому на странице вики убрали Lib-PSP из альтернативного названия).

Если будет интересно, я планирую сделать что-то вроде цикла статей про Гидру и с чем её есть, к тому же я сам себе задолжал статью про ImHex.