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

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

Я начал реверсить игры под PSP с целью моддинга где-то два года назад, до этого как-то всё не мог собраться, хотя и наблюдал за Youtube-каналами других моддеров. В своём локальном коммьюнити по моддингу трилогии Patapon я неожиданно стал одним из самых продвинутых специалистов и начал ради интереса исследовать в Тулкит для реверс-инженеров от АНБ США, переведённая в Open Source в 2019 году, бесплатная и постоянно развивающаяся альтернатива Ida, Binja, etc.</p>" data-abbr="Ghidra">Гидре абсолютно все игры, какие были на моей PSP-Go. Пока я это делал, я начал замечать, что в разделе данных иногда встречаются очень похожие друг на друга почти-что-ASCII строчки.

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

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

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

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

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

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

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

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

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

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

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

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

Open Source эмулятор PSP</p>" data-abbr="PPSSPP">PPSSPP и загрузчик самой PSP в таком случае поступают максимально просто - считывают размер этого хедера (байты [0x4; 0x7]), а затем скипают его, как будто его и не было. Как вы видите, внутри этого хедера лежит строчка, аналогичная той, которую я нашёл в данных игры (выделена). Если уж сама PSP не обращается к этому месту, становится понятно, что нам предстоит задача, аналогичная задаче понять язык, на котором уже никто не умеет ни читать, ни говорить.

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

В одной из игр я увидел, что рядом со строчкой стоял символ __psp_libinfo__, так что я стал исходить из того, что смысл этих строк - что-то вроде версии либы, с которой была статически слинкована программа, а называть их стал “libinfo” (либи́нфо, во множественном числе “libinfos”, либи́нфы, под ударением звук "ы"). Все PRX файлы с хедером ~SCE, которые были в моём распоряжении, оказались очень обрезанными - не то что дебажной информации или имён секций нет... Там вообще секций нет. Впрочем, внутри каждого нашлась ровно одна либинфа, совпадавшая с либинфой в хедере.

У меня сразу созрел план: собрать базу таких либинфочек, а потом автоматом Ахо-Корасик пройтись по файлам игр, чтобы понять, какие там присутствуют либы.

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

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

Я сразу решил, что бор нужно визуализировать посредством Чрезвычайно продвинутый фреймворк для визуализации графов. Имеет свой формат описания графов <code>*.gv</code>, по которым специальные утилиты конструируют изображения.</p><p></p>" data-abbr="Graphziv">графвиза. Как устанавливать его, рассказывать не буду, есть достаточно внятные инструкции в инете. К счастью, я уже с ним работал через Python (pygraphviz позволяет эмиттить *.gv-файлы), так что в этот раз было не шибко сложно. Мне было нужно обойти бор и зарегистрировать вершины (они здесь именуются не "vertex", а "node"), а затем проделать то же самое с рёбрами.

Обычно в боре пишут символы на рёбрах, а в вершинах пишут слова целиком, но я догадывался, что вершины будут огромные и картинка получится не очень наглядной, так что в вершинах я тоже писал символы. (Ну, кроме терминальных, конечно… Там всё-таки надо написать слова). Чтобы было совсем удобно, я всем терминальным вершинам в качестве тега дал имя модуля и разместил под строчкой. Кстати, тут уже base64 не поможет, надо запихивать наш недо-ASCII в граф. Я сделал свой рендерер, т.к. Питон считает, что x7F - printable. Может, DEL и на самом деле printable, но мне квадратики в консоли и пустое место на картинке не нужны…

Исследование

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

1. Длины либинф

2. Суммарный алфавит всех либинф

3. Символы, встречающиеся на i-ой позиции в либинфах

4. Сжатая форма алфавита - в отсортированном алфавите схлопываем рэнжи последовательно идущих символов (скажем, лист ['A','B','C','D','M','X'] превращается в строку "[A; D], M, X")

Оказалось, что все строчки имеют одинаковую длину 0x18 байт, причём у них общий префикс длиной 8 байт: yr=`c`0. Впрочем, последнее наблюдение можно было сделать и с помощью графа.

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

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

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

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

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

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

Тогда-то я и понял, что это, скорее всего, Шифрование осуществляется посредством замены i-ой буквы алфавита на i+k-ую (по модулю длины алфавита) по всем i, где k - длина этого циклического сдвига.</p>" data-abbr="Шифр Цезаря">шифр Цезаря! В данном случае, правда, алфавит - множество из 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. Все тела дешифровались и оказались просто сокращёнными версиями имён модулей (двойки оказались пробелами), а вот префикс и суффикс не починились. Тогда я предположил, что они зашифрованы другим сдвигом.

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

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

Я предположил, что это версии 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.