TL;DR: мы выполнили обратную разработку программы, написанной для полностью неизвестной архитектуры ЦП без какой-либо документации на ЦП (без эмулятора, без ISA, без всего) всего за десять часов. Из статьи вы узнаете, как нам это удалось…
В прошлые выходные мы с командой CMU PPP поучаствовали Teaser CTF 2019 команды Dragon Sector, чтобы расслабиться и отойти от жёсткого дедлайна CHI 2020. Dragon Sector — это уважаемая польская команда, имеющая историю интересных CTF, поэтому мне было интересно, что у них есть в запасе.
Решив “ummmfpu”, — задачу, в которую входил реверс-инжиниринг байткода для сопроцессора с плавающей запятой Micromega uM-FPU, я решил поучаствовать в соревновании по решению задачи CPU Adventure, которая на тот момент не была решена ни одной из команд (в результате мы оказались единственными, кто справился с заданием).
Вот описание задачи CPU Adventure:
Мой дедушка в 60-х годах занимался разработкой компьютеров. Наводя порядок на его чердаке, я нашёл странную машину. Рядом с машиной лежала стопка перфокарт с пометкой “Dragon Adventure Game”. Спустя какое-то время мне удалось подключить её к современному оборудованию, но игра слишком сложная и я не могу добраться до конца без читерства. Сможете мне помочь? Прилагаю транскрипцию перфокарт, используемых в машине. Утверждается, что машина имеет 4 регистра общего назначения, 1 кибибайт памяти данных и 32 кибибайта памяти команд. Чтобы сыграть в игру, подключитесь к серверу следующим образом:socat tcp4-connect:cpuadventure.hackable.software:1234 fd:0,rawerПодсказка: процессор машины уникален, не пытайтесь гуглить информацию по нему.
game.bin
Подключившись к серверу, мы получили следующую информацию:
THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.
SELECT AN OPTION:
- GO (N)ORTH
- GO (E)AST
- (T)ALK TO VALIS
- (D)RINK
- SHOW (I)NVENTORY
YOUR CHOICE: Отлично. Это олдскульная игра-адвенчура. Немного поиграв в неё, мы поняли, что можно сражаться с врагами и получить от этого персонажа Valis флаг, если порадуем его:
YOUR CHOICE: T
YOU ENTER THE TAVERN AND APPROACH VALIS.
- HEY, I WAS WONDERING IF YOU COULD HELP ME FIND THE FLAG?
- THE FLAG? MAYBE, BUT FIRST, I NEED A REDBULL.
- I... I DON'T HAVE A REDBULL.
- WELL THEN, MAKE YOURSELF USEFUL AND FIND ONE.
THERE IS A TAVERN HERE. INSIDE THE TAVERN, YOU SEE VALIS.
SELECT AN OPTION:
- GO (N)ORTH
- GO (E)AST
- (T)ALK TO VALIS
- (D)RINK
- SHOW (I)NVENTORY
YOUR CHOICE: Первые шаги
Я не особо долго играл в игру, поняв, что скорее всего более важно выполнить реверс-инжиниринг файла
game.bin. Я открыл его в шестнадцатеричном редакторе, ожидая увидеть двоичные значения. Вообразите моё удивление, когда я увидел такое:110011111101000000111100110010001110000011001101000000000000110010011101010000001101001111100001111111001100111000000011...
Это в буквальном смысле двоичный файл — текстовый файл, не содержащий ничего, кроме ASCII-символов 1 и 0. Мы знаем, что это скорее всего машинный код процессора, но кроме того, что у него есть 4 регистра, 1 кибибайта памяти данных и 32 кибибайта памяти инструкций, о нём неизвестно ничего. Поэтому нашей первой серьёзной задачей будет определение размера единиц этого двоичного файла (например, имеет ли он 8-битную размерность? или, возможно, у него 12-битная или 18-битная размерность, как в некоторых древних архитектурах?)
Чтобы выяснить размерность неизвестного файла, я воспользовался старым трюком — изменял размер текстового окна, пока длина переноса строк не стала соответствовать выравниванию. Такой способ отлично подходит для вещей наподобие зашифрованного многократным XOR текста, неизвестных (несжатых) форматов файлов и кода с неизвестного ЦП:
Меняем размер текстового окна
Из этой быстрой проверки я выяснил, что размер единицы этого файла должен быть делителем 20 (ширина выровненного окна). Чтобы выяснить точный размер, я быстро написал скрипт, ищущий длинные повторяющиеся строки (предполагая, что любой код имеет повторяющиеся стереотипные последовательности). Самой длинной повторяющейся строкой стал следующий 425-битный блок, встречающийся в позициях 43625 и 44510:
10000011111110000001010100011111110100000101100010111000001001000101000100001000100001010001011000101000000001111111111100010000011110010100100001010100111100000110000010100000101000101000011110001111001101111001010100001010000111110100001010000110010011011110011111000000111011101000000001100000110000111101011010111011000100100010100000111000100011100011000000000101010101100010111000001010000001101010010000000011000001100
Так как расстояние между повторами равно 885, мы пришли к выводу, что размерность должна составлять 5 бит, т.е. неизвестный ЦП должен иметь 5-битные «байты». Прогресс!
Мы поискали 5-битные кодировки перфокарт и быстро остановились на старинной кодировке кодом Бодо. И в самом деле — когда мы воспользовались онлайн-декодером для раскодирования некоторых фрагментов, то получили читаемый текст!
⇩DRAGON⇩HERE⇧;⇧⇧⇩SHE⇩APPEARS⇩TO⇩BE⇩GUARDING⇩ SOME⇩KIND⇩OF⇩A⇩BOTTLE⇧;&.&.⇩␀THERE⇩IS⇩A⇩B
Расшированный при помощи LSB Baudot ITA 1 425-битный код
Затем мы попытались раскодировать при помощи кода Бодо весь файл, но примерно в первых 20 тысячах бит получили мусор, после которого шёл совершенно читаемый текст. Это дало нам понять, что первая часть файла относится к разделу «кода», за которым идёт раздел «данных», содержащий постоянные строки. Мы предположили, что машина, вероятно, использует код Бодо для ввода-вывода, и поэтому хранит в памяти постоянные строки тоже в кодировке Бодо. Чтобы сделать сегмент кода более читаемым, я решил закодировать его при помощи кодировки base-32, аналогично шестнадцатеричному кодированию, но расширив его алфавитом 0-9a-v. Вот как выглядит файл game.bin с закодированной base-32 первой частью и декодированной по Бодо второй частью (полный файл выложен здесь: game.b32):
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf1sf24p5f3r9c11qad0f0sf1df26p5f39c21qad0f05f1ff26p5f39c41qad0f08f1df26p5f39c81qad0f0hf1ef26p5f3r1c00qaq15c20qcl0f01f1of27p5f3p3g3psf35c10qal0f02f1nf27p5f3p3g3psf3rf0hf1nf27p5f3f05f16f27p5f3rf84f95101311fl0f510f84907qa40b518447qa40b514f84f95k9m0k9m0k9m0907qa40b511447qa40b512ruougf10f20g0i9g0i910931b320u2u1u0ro9f0o9f0ojh0o9f0o9f0o9f0olj0o9f0o9f0o9f0o9f0o9f0o9f0o9f0o9k1onp0o9f0o9f0o9f0o9f0onf0ot82odi0o9f0o9f0o9f0o9f0o9f0o9f0o9f0olg0o9f0f0gf1df24p5f3r9c11qa835548755
[...]
93e9n59ka8fo87r85g8ui8ml8ed87b9h89u291u82333333333456789abcdb01234567892)%c3BOTTLE OF SOPLICA PIGWOWAENEMY HEALTH:
YOU ATTACK
YOU APPROACH REDFORD.
YOU ENTER THE TAVERN AND APPROACH VALIS.
[...]Для упрощения ниже я буду называть пятибитные единицы «байтами». Между собой в команде мы придумали для ни другие названия — я называл их кибблами, а Зак — хеками.
Реверс-инжиниринг архитектуры неизвестного процессора
Теперь мы приступаем к трудной части — обратной разработке 4000 байт кода, выполнявшегося на совершенно неизвестной уникальной архитектуре ЦП. Из кода достаточно очевидно, что это должен быть набор инструкций переменной длины, потому что в нём невозможно найти заметного устойчивого повторяющегося паттерна. Я потратил на это несколько часов, позже мне начал помогать член нашей команды Закари Уэйд (@zwad3). В первую очередь я начал повторяющиеся части кода, предположив, что они часто будут использовать малое количество инструкций. Я начал разделять код на более короткие повторяющиеся последовательности, более удобные для анализа. Хотел бы я сказать, что это был строгий процесс, но на самом деле в основном использовался следующий расплывчатый алгоритм:
- Просматриваем код и ищем, не повторяется ли что-нибудь в нём очень часто
- Выполняем процедуру поиска и замены для вставки новой строки рядом с этим повторением
- Исследуем сходства/различия между получившимися разделёнными строками
- Повторяем этот процесс порядка часа…
Например, одним из обнаруженных мной паттернов был “0f0.f”, где “.” обозначает неизвестный символ. Я разбил на этом паттерне строку и получил следующее:
pv83pi70pk00p7a0qfgvpjg3f0kf13f28p5f3pv10pk40pn60f0sf
1sf24p5f3r9c11qad0f0sf
1df26p5f39c21qad0f05f
1ff26p5f39c41qad0f08f
1df26p5f39c81qad0f0hf
1ef26p5f3r1c00qaq15c20qcl0f01f
1of27p5f3p3g3psf35c10qal0f02fОчень полезно! Из второй и третьей строк мы видим, что есть “…p5f3r9c…” и “…p5f39c…”, и это намекает нам, что “r” — это однобайтный опкод, то есть “…5f3” — это конец одного опкода, а “9c..” — начало другого. В последних двух строках мы видим “p5f3r1c…” и это значит, что “1c..” — это ещё один опкод, а “p3…” — тоже другой опкод.
Я продолжал снова и снова разделять инструкции подобным образом, используя сходства и различия похожих блоков для нахождения вероятных инструкций. В конце концов я получил нечто такое:
pv83
pi70
pk00
p7a0
qfgv
pjg3
f0k
f13
f28
p5f3
pv10
pk40
pn60
f0s
f1s
f24
p5f3
r
9c11
qad0
f0s
f1d
f26
p5f3
9c21
qad0
f05
f1fЯ предположил, что “p” и “q” были инструкциями с тремя байтами операндов, “f0”, “f1” и “f2” были инструкциями с одним операндом, а “9c” была инструкцией с двумя операндами. Однако я пока не знал, чем является каждая из этих инструкций.
Поэтому я обратился к каталогу всех выделенных мной инструкций “p”, и обнаружил, что на данный момент самой частой инструкций с “p” была “p5f3”. Более того, взглянув на те места, где она встречается, я обнаружил, что ей всегда предшествуют инструкции “f0”, “f1” и “f2”. Посмотрев на все операнды “f0”, “f1” и “f2”, я заметил, что операнды f2 всегда находятся интервале 4-8. Помня, что ЦП имеет 32 кибибайта памяти программ для адресации которой требуется 15 бит, я предположил, что “f0”, “f1” и “f2” загружали некий адрес с f2 в качестве старшего байта. Когда я соединил вместе некоторые из этих адресов, то обнаружил, что все они указывают точно на начало постоянных строк в разделе данных. Я нашёл функцию
print! Из этого сразу же следовало, что “p5f3” на самом деле является какой-то инструкцией печати строки или вызова; если учесть трёхбайтный операнд, то скорее всего это “call”. Снова взглянув на инструкции “p”, я осознал, что три байта операнда обозначают адрес в прямом порядке (little-endian), то есть последний байт операнда является самым старшим байтом адреса.Это был огромный прорыв! Мы определили нашу первую инструкцию. Увидев, что “f0” и “f1” используются в некоторых других местах, я предположил, что они загружают не адреса, а один из четырёх регистров (например, f0 загружает регистр 0) 5-битными константами с непосредственной адресацией. Это логично для p5f3 — она загружает три аргумента регистра для функции 3f5 (“print_string”).
Я начал писать дизассемблер, распознающий идиому “print” (f0x, f1x, f2x, p5f3), поместив в дизассемблированный код подстановку печатаемой строки. Благодаря большому количеству строк в программе дизассемблированный код быстро стал очень читаемым, и стало проще выяснять местонахождение функциональных блоков (полный дизассемблированный код находится здесь):
0: call 38v
4: call 7i
8: call k
c: call a7
g: q vgf
k: call 3gj
o: print 83k # 'SELECT AN OPTION\x0e:\r\n\r\n\x0f\x00'
15: call 1v
19: call 4k
1d: call 6n
1h: print 4ss # '\r\nYOUR CHOICE\x0e: \x0f\x00'
1u: ret
1v: unk 9
20: unk c
21: unk 1
22: unk 1
23: q 0da
27: print 6ds # '\x0e- \x0fGO \x0e(\x0fS\x0e)\x0fOUTH\r\n\x00'
2k: unk 9
2l: unk c
2m: unk 2
2n: unk 1
2o: q 0da
2s: print 6f5 # '\x0e- \x0fGO \x0e(\x0fN\x0e)\x0fORTH\r\n\x00'
39: unk 9
3a: unk c
3b: unk 4
3c: unk 1
3d: q 0da
3h: print 6d8 # '\x0e- \x0fGO \x0e(\x0fE\x0e)\x0fAST\r\n\x00'
3u: unk 9
3v: unk c
40: unk 8
41: unk 1
42: q 0da
46: print 6eh # '\x0e- \x0fGO \x0e(\x0fW\x0e)\x0fEST\r\n\x00'
4j: retИз этого небольшого фрагмента кода мне удалось выяснить несколько аспектов: инструкция “q0” должна обозначать некое условное ветвление (потому что она используется для пропуска печати ненужных направлений в функции 1v), а инструкции “9c11”, “9c21”, “9c41”, “9c81” должны обозначать некую разновидность инструкции AND — они проверяют установленные биты, чтобы узнать, разрешены ли эти направления (на это вполне очевидно намекает использование в этих инструкциях “1”, “2”, “4” and “8”).
В течение следующих двух часов мы с Закари Уэйдом (@zwad3) разбирали различные инструкции, делая и уточняя свои предположения о том, что они делают. Наличие множества читаемых операторов печати намного облегчило нашу работу. Мы решили, что каждый из нас по отдельности напишет собственный дизассемблер, чтобы мы могли исследовать инструкции в своём темпе и обмениваться своими находками.
Реверс-инжиниринг кода
Спустя несколько часов у меня начался большой прогресс в дизассемблировании. Изучив код, работавший с инвентарём пользователя (а конкретнее, функцию «выпить» и каждый связанный с ней обработчик), мы нашли инструкции сохранения и загрузки из памяти (не забывайте, что у ЦП есть 1 кибибайт памяти данных). Затем мы выяснили, что некоторые арифметические/логические (АЛУ) инструкции берут операнды памяти (например, “9c41” означает «выполнить AND со значением по адресу данных 1 со значением 4»). Из этого мы смогли воссоздать переменные, находящиеся в памяти данных, например в [0] хранится идентификатор NPC в текущей локации, а в [6,7] хранится текущее здоровье игрока (младшие 5 бит в [6], старшие 5 бит в [7]). На этом этапе я перешёл от обратной разработки инструкций к аннотированию моего дизассемблированного кода и реверс-инжинирингу самой программы. Ниже показана моя забавная нотация для 5-битных значений:
_start:
call init
L4:
call check_moves
call print_menu
call handle_command
br 4
print_menu:
call print_itemname
print 83k # 'SELECT AN OPTION\x0e:\r\n\r\n\x0f\x00'
call print_moves
call print_npcmenu
call print_itemmenu
print 4ss # '\r\nYOUR CHOICE\x0e: \x0f\x00'
ret
print_moves:
and 0y1, [1]
brz 2k
print 6ds # '\x0e- \x0fGO \x0e(\x0fS\x0e)\x0fOUTH\r\n\x00'
2k: and 0y2, [1]
brz 39
print 6f5 # '\x0e- \x0fGO \x0e(\x0fN\x0e)\x0fORTH\r\n\x00'
39: and 0y4, [1]
brz 3u
print 6d8 # '\x0e- \x0fGO \x0e(\x0fE\x0e)\x0fAST\r\n\x00'
3u: and 0y8, [1]
brz 4j
print 6eh # '\x0e- \x0fGO \x0e(\x0fW\x0e)\x0fEST\r\n\x00'
4j: ret
print_npcmenu:
add 0y0, [0]
brz 6m
sub 0y2, [0]
br<c> 5p
print 7o1 # '\x0e- (\x0fT\x0e)\x0fALK TO \x00'
call print_npcname
call print_crlf
5p: sub 0y1, [0]
brz 6m
print 7n2 # '\x0e- (\x0fF\x0e)\x0fIGHT \x00'
call print_npcname
call print_crlf
6m: ret
print_itemmenu:
print 7nh # '\x0e- (\x0fD\x0e)\x0fRINK\r\n\x00'
print 765 # '\x0e- \x0fSHOW \x0e(\x0fI\x0e)\x0fNVENTORY\r\n\x00'
retУ нас по-прежнему есть множество неизвестных опкодов, например, хотя мы выяснили, что “qa” — это условный переход по нулю (branch-on-zero, brz), нам не удалось понять, что такое “qc” (выше обозначенное как br<c>). Но этого было достаточно, чтобы начать разбираться в логике программы.
По сути, игра позволяет игроку перемещаться по карте размером 8×8, на которой случайным образом размещены NPC (драконы, «red bulls» и люди). Можно сразиться с любым NPC (даже с Valis, несмотря на отсутствие соответствующего пункта меню). Во время боя можно нападать на противника, нанося случайное количество урона или промахиваясь, после чего противник нападает на игрока, тоже нанося случайное количество урона или промахиваясь. Также можно выбрать блокировку щитом, благодаря которой противник или промахивается, или попадает по щиту, не нанося урона. Наконец, можно читерить, подняв здоровье до 1000, но в этом случае скрытой переменной (“cheated”, адрес 10) задаётся значение 1. Если игрок успешно убивает врага, из него выпадает предмет, обычно это бутылка какого-нибудь алкоголя (очевидно, что эта игра не для детей).
Главный NPC Valis, от которого игрок должен получить флаг, имеет конечный автомат, в котором он просит у игрока несколько предметов — кучу напитков red bull (очевидно, получаемых при победе над врагами red bull), различные смешанные напитки (например, джин с тоником — чтобы получить их, надо победить синего дракона и серого дракона, а потом смешать выпавшие из них предметы), и power strip, который можно получить, если победить другого человека-NPC в игре (Redford) или помочь ему. Если выполнить всю эту долгую серию просьб, то он отдаст вам флаг, но только если переменная “cheated” не равна 1. То есть наша задача победить в игре без читерства. Так как мы начинаем всего с 100 HP, как и все враги, то при обычном прохождении победить всех врагов будет невозможно (для получения всех нужных вещей нужно победить примерно 20 противников). Нужно каким-то образом модифицировать RNG, чтобы противник всегда промахивался.
Генерация случайных чисел выполняется функцией, которая похожа на некую разновидность PRNG (адрес 37a), но она использует уникальные инструкции, которые больше нигде не применяются, поэтому мы не можем выполнить их реверс-инжиниринг. Однако мы заметили, что она загружает свой вектор состояния из трёх адресов в памяти ([11], [12] и [13]), то есть её полное состояние занимает всего 15 бит. Это значит, что RNG должен иметь короткий период — не больше 2^15 = 32768 в длину.
Пока мы (безуспешно) пытались реверснуть реализацию RNG, Джей Босамия (@jay_f0xtr0t) и Мэттью Сэвидж (@thebluepichu) реализовали эксплойт. Простой отправкой команды “shield” 100 000 раз подряд мы смогли получить последовательность вражеских «попаданий» и «промахов», соответствующих битовому выводу из RNG. Мы удостоверились, что эта последовательность повторяется с периодом 32767. Благодаря этому мы смогли собрать свой главный эксплойт — при бое с первым встреченным врагом мы 40 раз закрывались щитом, чтобы воссоздать последовательность попаданий и промахов, искали эту последовательность в большой периодической последовательности, а затем выясняли, когда закрываться щитом и когда нападать так, чтобы враг всегда промахивался. Затем мы просто обошли всю карту в режиме murderhobo, убивая всех и собирая их лут. В конце мы вернулись к Valis и вежливо попросили свой флаг, который и получили:
DrgnS{m4kin9-v4lis-happy-w1th-n4t1ve-b4ud0t-cpu}Фух! Действительно, настоящее приключение. Я всё ещё не могу до конца поверить, что мы пришли от двоичной строки и полного отсутствия документации по процессору к двум почти полным дизассемблерам и чистому дизассемблированному коду меньше чем за 10 часов! Весьь код выложен на GitHub: мой дизассемблер, дизассемблер Закари, мой сырой дизассемблированный код, мой аннотированный дизассемблированный код, экспойт-клиент Мэтта.
