«Затерянные в додекаэдре»

На Земле – египетские пирамиды, а на этой планете – один (зато какой!) гигантский додекаэдр, левитирующий в воздухе на высоте порядка десяти метров. Должно быть, именно в нём и кроется вся загадка этой планеты. Сама фигура как бы приглашает исследовать ее – одна из граней отсутствует, обозначая вход, и оттуда до земли свивает веревочная лестница. Разумеется, мы туда полезли.

«Вот так и пропадают неизвестно куда космические экспедиции…» – уныло говорили мы, уже третий час безуспешно пытаясь выбраться из дурацкого додекаэдра, дверь которого моментально заблокировалась, как только последний из нас забрался внутрь. Выломать дверь не удавалось, единственным выходом было блуждание по лабиринту объемной фигуры. Трудно сказать, сколько прошло времени, но наши поиски увенчались успехом: в одном из закоулков мы обнаружили вполне себе земной древний компьютер! Недовольно урча и подтормаживая, он все-таки загрузился. Всё, что удалось обнаружить – один файлик. Хорошо, что у меня с собой был ноутбук и флешка, я перекинул файл на ноут и стал внимательно его изучать.

Скачиваем предоставленный файл. Это бинарник qemu, но не совсем обычный.

Подсказка 2: нужно посмотреть все виртуальные устройства, которые можно использовать, среди них будет одно особенное, его нужно добавить при загрузке виртуалки. Для взаимодействия с устройством используйте IO порты.

Посмотрим список виртуальных устройств:

$ ./qemu-system-x86_64_final.qemu -device help

В разделе «Misc devices» находим то самое «особенное»:

name "a42b145c", bus PCI, desc "PCI -= Hex Sudoku =-"

Подсказка говорит нам, что дальше нужно загрузить что-то в qemu и взаимодействовать с устройством через IO порты. Но мы пойдем другим путем: раз есть виртуальное устройство, значит в предоставленном qemu есть его код, давайте его разреверсим.

Загружаем бинарник в IDA и видим, что все символы на месте, это нам на руку. Будем искать наше устройство. Поиск по «Hex Sudoku» ничего не дает, очевидно строки зашифрованы. Посмотрим как в qemu добавляются новые устройства, хороший пример есть здесь. Видим, что для регистрации устройства используется type_register_static. Найдем его в IDA и посмотрим, откуда он вызывается. Среди всех функций, одна сильно выделяется:



Похоже что это и есть нужное нам устройство.



В kYw8zJoR2P79 находим указатель на class_init:



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



Видим расшифровку строки «PCI -= Hex Sudoku =-», но она нас уже не интересует. Идем в init:



В wF5kdW6bDnmo находим указатели на функции чтения и записи:



Начнем с чтения:



Выглядит немного странно. Устройство хранит все данные кусками по 16 * 4 байт, разбросанными по fLA0hXGQ.

Подсказка 3: читаем из порта 0x0 значения – это начальные значения для судоку 16x16, старший байт – индекс, младший – значение.

Теперь, используя смещения из dword_88B6C64, мы можем получить все 92 начальных значения для судоку. Решаем любым удобным способом на свое усмотрение:

solution = [
    [ 0xF, 0x0, 0x3, 0xB,  0xD, 0xC, 0x4, 0xE,  0x8, 0x5, 0x2, 0xA,  0x9, 0x1, 0x6, 0x7 ],
    [ 0x4, 0xC, 0x8, 0xE,  0x1, 0xF, 0x5, 0x2,  0xB, 0x9, 0x7, 0x6,  0xD, 0x3, 0xA, 0x0 ],
    [ 0x9, 0x1, 0x5, 0x7,  0x6, 0xA, 0x0, 0x8,  0x4, 0xE, 0x3, 0xD,  0xB, 0xF, 0x2, 0xC ],
    [ 0xD, 0x6, 0x2, 0xA,  0xB, 0x7, 0x9, 0x3,  0x0, 0xF, 0x1, 0xC,  0x5, 0x4, 0x8, 0xE ],

    [ 0x5, 0x8, 0x7, 0x0,  0xA, 0xD, 0x2, 0x1,  0x9, 0x3, 0x6, 0x4,  0xE, 0xB, 0xC, 0xF ],
    [ 0x1, 0xE, 0xB, 0xC,  0x8, 0x9, 0x6, 0x7,  0xF, 0x0, 0xA, 0x2,  0x4, 0xD, 0x5, 0x3 ],
    [ 0x2, 0xA, 0x4, 0xD,  0xF, 0xB, 0x3, 0x0,  0xE, 0xC, 0x5, 0x1,  0x6, 0x9, 0x7, 0x8 ],
    [ 0x3, 0xF, 0x6, 0x9,  0xE, 0x5, 0xC, 0x4,  0xD, 0x7, 0xB, 0x8,  0x2, 0xA, 0x0, 0x1 ],

    [ 0x7, 0x3, 0xF, 0x5,  0x0, 0x6, 0xA, 0xB,  0x2, 0x4, 0x8, 0x9,  0xC, 0xE, 0x1, 0xD ],
    [ 0xE, 0x4, 0x0, 0x6,  0xC, 0x2, 0x8, 0xF,  0x1, 0xB, 0xD, 0x7,  0x3, 0x5, 0x9, 0xA ],
    [ 0xA, 0xB, 0xC, 0x2,  0x9, 0x1, 0xE, 0xD,  0x5, 0x6, 0x0, 0x3,  0x8, 0x7, 0xF, 0x4 ],
    [ 0x8, 0x9, 0xD, 0x1,  0x4, 0x3, 0x7, 0x5,  0xC, 0xA, 0xF, 0xE,  0x0, 0x2, 0xB, 0x6 ],

    [ 0xB, 0xD, 0x1, 0x4,  0x2, 0x0, 0xF, 0xA,  0x3, 0x8, 0xC, 0x5,  0x7, 0x6, 0xE, 0x9 ],
    [ 0x0, 0x7, 0xA, 0x8,  0x5, 0xE, 0xD, 0x9,  0x6, 0x2, 0x4, 0xF,  0x1, 0xC, 0x3, 0xB ],
    [ 0x6, 0x2, 0x9, 0xF,  0x3, 0x4, 0xB, 0xC,  0x7, 0x1, 0xE, 0x0,  0xA, 0x8, 0xD, 0x5 ],
    [ 0xC, 0x5, 0xE, 0x3,  0x7, 0x8, 0x1, 0x6,  0xA, 0xD, 0x9, 0xB,  0xF, 0x0, 0x4, 0x2 ]
]

Как теперь получить ответ? По адресу 0x4 устройство отдает 4096 байт — наверно там должен быть ключ, конечно после того, как мы предоставим правильное решение устройству. Посмотрим функцию записи:



В самом начале записывается переданное значение. Дальше проверяется правильность решения, и, если оно верное, то вычисляется ответ.

Сдампим содержимое fLA0hXGQ в файл и перепишем код на Python:

xor1_offset = [
    0x11b0, 0x180, 0xcd0, 0x1e10, 0x1d50, 0x13d0, 0x560, 0xf60,
    0x1a40, 0xe10, 0x1d00, 0x1100, 0xed0, 0xf10, 0xa20, 0x630, 
    0xd90, 0x2070, 0x1530, 0x1cc0, 0xf0, 0x1110, 0x1030, 0x1390,
    0x710, 0x6e0, 0x1d10, 0x3a0, 0x1290, 0x1150, 0x9d0, 0xcb0, 
    0x1ad0, 0x17b0, 0x6b0, 0x1510, 0xf30, 0xad0, 0x1350, 0x450,
    0x1160, 0x810, 0x8a0, 0x1550, 0x1ed0, 0x1f60, 0x1120, 0x1660, 
    0x2030, 0xfc0, 0x17e0, 0x1640, 0xde0, 0x900, 0xff0, 0x17f0,
    0xf40, 0x10f0, 0x8f0, 0x880, 0x160, 0x1400, 0x19d0, 0x7f0, 
    0x1490, 0x30, 0x1e80, 0x15b0, 0x1f20, 0xbf0, 0x11c0, 0x1a70,
    0x1380, 0x960, 0x1c50, 0x1fb0, 0x570, 0x1c30, 0xd60, 0x290, 
    0x1260, 0x240, 0x1060, 0x1b90, 0x1230, 0x280, 0xdf0, 0x1190,
    0x1240, 0xeb0, 0xb40, 0xdb0, 0x820, 0x1f70, 0x1330, 0xd70, 
    0xe90, 0xf00, 0xc60, 0xe60, 0x390, 0x1c00, 0x1bb0, 0x1690,
    0x600, 0x12a0, 0xef0, 0x17d0, 0x970, 0x670, 0x1990, 0xac0, 
    0x3f0, 0x1b70, 0x1790, 0xf70, 0x1b60, 0x1070, 0x1200, 0x1680,
    0x1b50, 0xf90, 0x4c0, 0x1840, 0x1800, 0x2e0, 0xbc0, 0x1780, 
    0x14d0, 0x80, 0x1dd0, 0x16a0, 0x8b0, 0x1e90, 0x7e0, 0x1450,
    0x20f0, 0x20e0, 0x2040, 0x9f0, 0x2150, 0x1250, 0xa70, 0xcc0, 
    0xa00, 0x5d0, 0x20, 0xfa0, 0x500, 0x1c70, 0x1ae0, 0x16d0,
    0x1470, 0x18b0, 0x270, 0xc80, 0x1850, 0x1a50, 0x1a90, 0xe30, 
    0x1440, 0x2110, 0x340, 0x1af0, 0x1010, 0x510, 0x310, 0x830,
    0x3c0, 0x860, 0x3e0, 0x13e0, 0x19f0, 0x1ac0, 0x1e60, 0xbe0, 
    0x950, 0x1b80, 0x680, 0x1220, 0xd40, 0x14a0, 0xb10, 0xe70,
    0x19e0, 0x1b20, 0x10a0, 0x1730, 0x4d0, 0x120, 0x12c0, 0x16e0, 
    0x14c0, 0x1de0, 0x1d0, 0x420, 0x910, 0x1b0, 0x2080, 0x1920,
    0x1460, 0x40, 0x11a0, 0x15e0, 0xb00, 0x1ba0, 0x1650, 0x440, 
    0x650, 0x350, 0x300, 0x330, 0x1e0, 0x13c0, 0xd50, 0x1fd0,
    0xae0, 0x12f0, 0xa80, 0x50, 0xbb0, 0x1e70, 0x1b30, 0xc0, 
    0x1340, 0xd20, 0x2c0, 0xaf0, 0x6d0, 0x1570, 0xc00, 0x1580,
    0x5e0, 0x1700, 0x1ea0, 0x1890, 0x1d20, 0x1aa0, 0x840, 0x1f40, 
    0x1590, 0x700, 0x150, 0x890, 0x4e0, 0x1720, 0xd30, 0x990,
    0x16f0, 0x3b0, 0x1970, 0x1c0, 0x0, 0x1320, 0x1ff0, 0x760
]

xor2_offset = 0x170

row_offset = [
    0xfb0, 0x2a0, 0xec0, 0x140, 0x1090, 0xdc0, 0x15f0, 0x610,
    0x7c0, 0x1a10, 0x780, 0x13b0, 0xc20, 0x1750, 0x1860, 0x6a0, 0x12B0
]

answer_offset = [
    0x12b0, 0xfd0, 0x1ca0, 0x2020, 0xaa0, 0x5a0, 0x470, 0x4f0,
    0x1a00, 0xa40, 0x1870, 0x1810, 0x690, 0x1410, 0x15d0, 0x20b0, 
    0x870, 0x1c60, 0x1da0, 0xa90, 0x980, 0x1000, 0x930, 0x2000,
    0x2160, 0x5c0, 0x1370, 0x15a0, 0xca0, 0x790, 0x200, 0x2060, 
    0xb30, 0x1fe0, 0x90, 0x18a0, 0x5b0, 0x1e40, 0x1d70, 0x1d30,
    0x530, 0x1d90, 0x2130, 0x1600, 0x9e0, 0x1940, 0x1910, 0x1670, 
    0x60, 0x10e0, 0x1950, 0xfe0, 0x430, 0x20c0, 0x380, 0x230,
    0xf80, 0x1270, 0x2b0, 0x1130, 0xe20, 0x20d0, 0x2010, 0x720, 
    0x1c40, 0x1df0, 0x16c0, 0x13a0, 0xc90, 0x320, 0x1ce0, 0x18d0,
    0x1dc0, 0x520, 0x250, 0x1fc0, 0x11f0, 0xe50, 0x800, 0x4b0, 
    0xc70, 0x1c90, 0xba0, 0x1ec0, 0x10c0, 0x8c0, 0xea0, 0x1db0,
    0x6c0, 0x1740, 0x1820, 0x590, 0x360, 0x1f80, 0xb20, 0x1770, 
    0x1e50, 0x940, 0x1710, 0x1bf0, 0x7a0, 0x1c20, 0x1310, 0x220,
    0xab0, 0xe00, 0x17a0, 0xf20, 0x730, 0x1cd0, 0x9a0, 0x640, 
    0x18c0, 0x19c0, 0x5f0, 0xdd0, 0x1560, 0x1bc0, 0x1360, 0x1c80,
    0x10, 0x1f0, 0xc10, 0xd80, 0x1500, 0x1620, 0x660, 0x2090, 
    0x1d40, 0xe80, 0x15c0, 0x850, 0xa60, 0x1e30, 0x14f0, 0x12d0,
    0xc30, 0x920, 0x10d0, 0x1210, 0x3d0, 0x1760, 0x740, 0x6f0, 
    0xe0, 0x1610, 0x1520, 0x19a0, 0xe40, 0x130, 0x1a30, 0x190,
    0xa50, 0xf50, 0xb0, 0xc40, 0x14b0, 0x1a0, 0x400, 0xb50, 
    0x480, 0xc50, 0x1d60, 0x1480, 0x9c0, 0x1d80, 0x1f90, 0x12e0,
    0x17c0, 0x1050, 0xa10, 0x1830, 0x620, 0x1e00, 0x1f00, 0x1430, 
    0x1170, 0xcf0, 0xb70, 0x2120, 0x1cb0, 0x1420, 0xce0, 0x1f10,
    0x210, 0x1980, 0x9b0, 0x100, 0x110, 0xd10, 0x550, 0x1eb0, 
    0x1960, 0x1930, 0xb80, 0x7b0, 0xd00, 0x1be0, 0x1900, 0x8d0,
    0x1fa0, 0x4a0, 0x1ab0, 0x580, 0x2100, 0x490, 0x8e0, 0x750, 
    0x1ef0, 0x2140, 0x1ee0, 0x11e0, 0x1b00, 0x16b0, 0x1a20, 0x1630,
    0x410, 0x540, 0xd0, 0x1b40, 0x260, 0x1b10, 0x11d0, 0xee0, 
    0x18f0, 0x2f0, 0x1300, 0x2050, 0x1880, 0x1a80, 0x1080, 0x1c10,
    0x1280, 0x18e0, 0x7d0, 0xb60, 0x2d0, 0x1e20, 0x13f0, 0x1bd0, 
    0xbd0, 0x1f50, 0x70, 0x1020, 0x1540, 0x10b0, 0x14e0, 0xda0,
    0x1f30, 0x19b0, 0x460, 0xa30, 0x1180, 0x20a0, 0x1140, 0x1040
]

solution = [
    [ 0xF, 0x0, 0x3, 0xB,  0xD, 0xC, 0x4, 0xE,  0x8, 0x5, 0x2, 0xA,  0x9, 0x1, 0x6, 0x7 ],
    [ 0x4, 0xC, 0x8, 0xE,  0x1, 0xF, 0x5, 0x2,  0xB, 0x9, 0x7, 0x6,  0xD, 0x3, 0xA, 0x0 ],
    [ 0x9, 0x1, 0x5, 0x7,  0x6, 0xA, 0x0, 0x8,  0x4, 0xE, 0x3, 0xD,  0xB, 0xF, 0x2, 0xC ],
    [ 0xD, 0x6, 0x2, 0xA,  0xB, 0x7, 0x9, 0x3,  0x0, 0xF, 0x1, 0xC,  0x5, 0x4, 0x8, 0xE ],

    [ 0x5, 0x8, 0x7, 0x0,  0xA, 0xD, 0x2, 0x1,  0x9, 0x3, 0x6, 0x4,  0xE, 0xB, 0xC, 0xF ],
    [ 0x1, 0xE, 0xB, 0xC,  0x8, 0x9, 0x6, 0x7,  0xF, 0x0, 0xA, 0x2,  0x4, 0xD, 0x5, 0x3 ],
    [ 0x2, 0xA, 0x4, 0xD,  0xF, 0xB, 0x3, 0x0,  0xE, 0xC, 0x5, 0x1,  0x6, 0x9, 0x7, 0x8 ],
    [ 0x3, 0xF, 0x6, 0x9,  0xE, 0x5, 0xC, 0x4,  0xD, 0x7, 0xB, 0x8,  0x2, 0xA, 0x0, 0x1 ],

    [ 0x7, 0x3, 0xF, 0x5,  0x0, 0x6, 0xA, 0xB,  0x2, 0x4, 0x8, 0x9,  0xC, 0xE, 0x1, 0xD ],
    [ 0xE, 0x4, 0x0, 0x6,  0xC, 0x2, 0x8, 0xF,  0x1, 0xB, 0xD, 0x7,  0x3, 0x5, 0x9, 0xA ],
    [ 0xA, 0xB, 0xC, 0x2,  0x9, 0x1, 0xE, 0xD,  0x5, 0x6, 0x0, 0x3,  0x8, 0x7, 0xF, 0x4 ],
    [ 0x8, 0x9, 0xD, 0x1,  0x4, 0x3, 0x7, 0x5,  0xC, 0xA, 0xF, 0xE,  0x0, 0x2, 0xB, 0x6 ],

    [ 0xB, 0xD, 0x1, 0x4,  0x2, 0x0, 0xF, 0xA,  0x3, 0x8, 0xC, 0x5,  0x7, 0x6, 0xE, 0x9 ],
    [ 0x0, 0x7, 0xA, 0x8,  0x5, 0xE, 0xD, 0x9,  0x6, 0x2, 0x4, 0xF,  0x1, 0xC, 0x3, 0xB ],
    [ 0x6, 0x2, 0x9, 0xF,  0x3, 0x4, 0xB, 0xC,  0x7, 0x1, 0xE, 0x0,  0xA, 0x8, 0xD, 0x5 ],
    [ 0xC, 0x5, 0xE, 0x3,  0x7, 0x8, 0x1, 0x6,  0xA, 0xD, 0x9, 0xB,  0xF, 0x0, 0x4, 0x2 ]
]

memory = bytearray(open("memory", "rb").read())

def mem_read(addr):
    return memory[addr * 4] | (memory[addr * 4 + 1] << 8) | (memory[addr * 4 + 2] << 16) | (memory[addr * 4 + 3] << 24)

def mem_write(addr, value):
    memory[addr * 4] = value & 0xff;
    memory[addr * 4 + 1] = (value >> 8) & 0xff;
    memory[addr * 4 + 2] = (value >> 16) & 0xff;
    memory[addr * 4 + 3] = (value >> 24) & 0xff;

def set_cell(row, col, value):
    mem_write(row_offset[row] + col, value)

def get_cell(row, col):
    return mem_read(row_offset[row] + col)

for row in range(16):
    for col in range(16):
        set_cell(row, col, solution[row][col])

for i in range(16):
    for cell in range(256):
        c1 = get_cell(cell >> 4, cell & 0xf)
        c2 = get_cell((cell + 1) >> 4, (cell + 1) & 0xf)
        xor1 = mem_read(i + xor1_offset[cell]) & 0xff
        xor2 = mem_read(i + xor2_offset)
        mem_write(i + answer_offset[cell], ((c2 & 0xff) | (c1 << 4)) ^ xor1 ^ xor2)

for i in range(16):
    for j in range(256):
        print(chr(mem_read(answer_offset[j] + i)), end='')

Запускаем и получаем необычный ключ в виде ASCII-графики: