NeoQuest 2017: Getting out of the dodecahedron without launching anything in qemu

"Lost in the dodecahedron"

There are Egyptian pyramids on Earth, and on this planet there is one (but what!) Giant dodecahedron levitating in the air at a height of about ten meters. It must be in it lies the whole mystery of this planet. The figure itself invites to explore it - one of the faces is missing, indicating the entrance, and from there to the ground a rope ladder twists to the ground. Of course, we got there.

“This is how unknown to where space expeditions disappear ...” - we said sadly, for the third hour unsuccessfully trying to get out of the stupid dodecahedron, the door of which was instantly blocked as soon as the last of us got inside. It was not possible to break down the door, the only way out was to wander around the maze of a three-dimensional figure. It is difficult to say how much time has passed, but our searches have been crowned with success: in one of the back streets we found quite an earthly ancient computer! Dissatisfied rumbling and slowing down, he still booted. All that could detect - one file . It’s good that I had a laptop and a flash drive with me, I transferred the file to the laptop and began to carefully study it.

Download the file provided. This is a qemu binary, but not quite normal.

Tip 2: you need to look at all the virtual devices that can be used, one of them will be one special, you need to add it when booting the virtual machine. To interact with the device, use the IO ports.

Let's look at the list of virtual devices:

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

In the section "Misc devices" we find the very "special":
')

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

The hint tells us that further you need to load something into qemu and interact with the device through the IO ports. But we will go another way: once there is a virtual device, it means that in the provided qemu there is its code, let's reverse it.

We load the binary into IDA and see that all the symbols are in place, this is in our favor. We will look for our device. Searching for “Hex Sudoku” doesn’t give anything; obviously the strings are encrypted. Let's see how new devices are added to qemu, a good example is here . We see that type_register_static is used to register the device. Find it in IDA and see where it comes from. Among all the functions, one stands out:



It seems that this is the device we need.



In kYw8zJoR2P79 we find a pointer to class_init:



Here, for clarity, I added the necessary structures from qemu and set the correct types of variables:



We see the decoding of the string “PCI - = Hex Sudoku = -”, but it does not interest us anymore. Go to init:



In wF5kdW6bDnmo we find pointers to the read and write functions:



Let's start with reading:



Looks a little weird. The device stores all data in chunks of 16 * 4 bytes scattered across fLA0hXGQ.

Tip 3: read from port 0x0 the values ​​are the initial values ​​for sudoku 16x16, the high byte is the index, the low is the value.

Now, using the offsets from dword_88B6C64, we can get all 92 initial values ​​for sudoku. We decide in any convenient way at our discretion:

 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 ] ] 

How to get an answer now? At the address 0x4, the device gives 4096 bytes - probably there should be a key, of course, after we provide the right solution to the device. Let's look at the recording function:



At the very beginning, the transferred value is written. Then the correctness of the solution is checked, and, if it is correct, the answer is calculated.

Let’s upload the contents of fLA0hXGQ to a file and rewrite the code in 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='') 

Run and get an unusual key in the form of ASCII graphics: