Location: Atlantis, Colorful Tower
Depth: 395

# Solution to Image

### Concept by Zev Benjamin, Joshua Oreman, and Rassi; implementation by Joshua Oreman

The puzzle is a file called "image" with no extension. If you download it and try to open it, or run file on it, you'll probably find that it's a TIFF image, which looks like the following maze, with complex non-graphical patterns on the top and bottom and some noise inside the maze walls. Each square of the maze contains a unique byte value represented in hexadecimal.

There is only one solution to the maze, and solving it gives the following path:

The bytes in this path are all unique:

B8 A2 E1 B7 C8 C6 1B FB A0 F2 C4 F8 A5 9E CA E5 A8 A4 98 4D 4F 55 4E 54 5F 46 49 4C 45 BA 88 0D E4 05 DB 1C D7 52 9B 97 94 51 F1 AD FA 06 AA 12 8C 13 E6 DD B5 ED 42 9F 0F 0E EA F6 80 C0 0A A3 19

Most of them appear random, but there's a sequence (bolded above) that's valid ASCII for MOUNT_FILE. By noticing that, or by getting suspicious about the patterns above and below the maze and running something like file --keep-going, or by running strings on the file and seeing things like /mnt, it's possible to realize the "image" file is also a valid ext2 filesystem image.

The root directory of the mounted filesystem contains a file image, which is a TIFF image containing the "START" square from the maze, and a directory south. Descending into south puts you in a directory that contains another image file (a TIFF of the EE square) and subdirectories north, south, and east; and the pattern continues.

Each directory in the filesystem represents a square in another maze that has no relation to the one in the image. The byte inside the square is whatever the image file contains, and the walls of the square are defined by the directions you can move from this one: e.g., if you can go north, there's no wall above you. The directions work exactly like you would expect them to in a maze, though they're a bit strange for a filesystem: if you go south and then north, you wind up back where you started. (This is implemented by directory hardlinks, which most operating systems won't let you create but which can be accessed just fine in a read-only filesystem.)

The filesystem maze can be solved manually or programmatically to produce the following path:

EE EB A6 F2 86 83 49 BE 80 B7 8A BB EA DA 8F A1 88 E5 D6 1E 18 10 1C 69 0F 07 05 15 1D ED D9 57 DF 25 9D 53 85 72 D0 D2 CD 71 A2 E2 B6 50 EF 32 CA 5A AA 98 95 A4 0C BF 46 40 A5 B2 C5 E0 39 92 2E

This path is the same length (65 bytes) as the one produced by solving the graphical maze. XOR'ing corresponding bytes together gives:

56 49 47 45 4E 45 52 45 20 45 4E 43 4F 44 45 44 20 41 4E 53 57 45 52 3D 50 41 4C 59 58 57 51 5A 3B 20 46 4F 52 20 4B 45 59 20 53 4F 4C 56 45 20 46 49 4C 45 20 49 4E 20 49 4E 4F 44 45 20 33 31 37

which is all valid ASCII: VIGENERE ENCODED ANSWER=PALYXWQZ; FOR KEY SOLVE FILE IN INODE 317.

Inode 317 is a deleted inode (it doesn't correspond to any file you can reach from the root directory) but a tool such as debugfs can easily extract the data blocks it references. They're... another maze with stuff on the top and bottom! This time only an 8x8 one.

Which also happens to be another valid ext2 filesystem. Do the same thing to it that you did to the big maze. Solve the graphical maze:

2C 6A 3F 2B 79 30 70 60 7F 72 29 38 7A 21 39 32 78 6C 2A 65 25 24 27

Mount the filesystem and solve the filesystem maze:

68 2F 7C 64 3D 75 31 2E 2C 27 7A 71 34 66 72 77 21 25 67 24 62 61 74

XOR the two same-length solutions together:

44 45 43 4F 44 45 41 4E 53 55 53 49 4E 47 4B 45 59 49 4D 41 47 45 53

Which is ASCII for DECODEANSUSINGKEYIMAGES. Use the key IMAGES (really IMAGESIM, since the key gets repeated until it's the same length as the plaintext/ciphertext) to de-Vigenere PALYXWQZ and you get the answer: HOLSTEIN.

## How it works

Nothing in this section is required figuring-out for solving the puzzle, but it's interesting nonetheless.
• The big TIFF files are laid out using tiles: in the file, the contents of each 64x64 maze square are contiguous.
• The filesystem block size is 1KB, so there are 12 filesystem blocks in each maze square. You can easily see the block boundaries by looking at some of the non-maze squares above and below the maze, which contain filesystem metadata.
• The TIFF header occupies the first 1KB, which is reserved for the bootloader in an ext2 filesystem. The next blocks are, in order:
• Superblock
• Block descriptor table (only one block group)
• Block bitmap for the first block group
• Bnode bitmap for the first block group
• Many blocks (the mostly-black ones with vertical patterns) for inodes. (In order to make the maze border clear, some inodes are filled with all white and just have the nlink field set to 0 so fsck doesn't complain about them; the zeroed nlink fields form the vertical dotted lines of yellow-cyan, blue, and red.)
• In the big maze: an all-white block used to fill in white sections of the small maze
• The TIFF header for the small images in the filesystem (all the images use the same TIFF header block to save space, since they all have the same data layout)
• In the big maze: all the above filesystem metadata for the small maze, including its TIFF header.
• The blocks that are mostly empty and just look like lines, at the upper-right and bottom-left of the maze image, are directories. Directories are also packed into the horizontal maze walls.
• The RGB pattern at the extreme lower-right of the big maze corresponds to the indirect blocks and doubly-indirect block for the embedded small maze. No other indirect blocks are used.
• Every single block in the big maze is used for something, and there's nothing in the filesystem that's not visible when you open the image in a graphics program.
• TIFF is probably the only image format flexible enough to let you do something like this. The big maze image's TIFF header actually needed to be longer than 1KB due to specifying all the tile offsets and sizes, but we just put the overflow part way at the end of the file after all the image data.
• Each image's data blocks, after the header, are the 10 middle blocks of the 12 that form its square. The top and bottom blocks are not needed because they don't contain any of the square contents, just the edges. 10 data blocks + 1 header block fits in an inode without using any indirect blocks. The TIFF header for each maze-square image in the filesystem contains directives so the pixels that correspond to the left and right walls of the square will not be displayed. Graphically:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@................
.......................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
........o@@@@ooooooooooo...o@@@@ooooooooooo............@@@@
@@@@@
........@@@@@@@@@@@@@@@@...@@@@@@@@@@@@@@@@............@@@@
@@@@@
........o@@@@@@@@@@@@@@@...o@@@@@@@@@@@@@@@............@@@@
@@@@@
...........@@@.......@@@......@@@.......@@@............@@@@
@@@@@
...........@@@.......@@@......@@@.......@@@............@@@@
@@@@@
...........@@@.......@@@......@@@.......@@@............@@@@
@@@@@
...........@@@...o@o.o@o......@@@...o@o.o@o............@@@@
@@@@@
...........@@@...@@@..........@@@...@@@................@@@@
@@@@@
...........@@@@@@@@@..........@@@@@@@@@................@@@@
@@@@@
...........@@@@@@@@@..........@@@@@@@@@................@@@@
@@@@@
...........@@@@@@@@@..........@@@@@@@@@................@@@@
@@@@@
...........@@@...@@@..........@@@...@@@................@@@@
@@@@@
...........@@@...o@o..o@o.....@@@...o@o..o@o...........@@@@
@@@@@
...........@@@........@@@.....@@@........@@@...........@@@@
@@@@@
...........@@@........@@@.....@@@........@@@...........@@@@
@@@@@
...........@@@........@@@.....@@@........@@@...........@@@@
@@@@@
........o@@@@@@@@@@@@@@@@..o@@@@@@@@@@@@@@@@...........@@@@
@@@@@
........@@@@@@@@@@@@@@@@@..@@@@@@@@@@@@@@@@@...........@@@@
@@@@@
........o@@@@@@@@@@@@@@@@..o@@@@@@@@@@@@@@@@...........@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@
.......................................................@@@@
@@@@@.......................................................@@@@
@@@@@.......................................................@@@@
@@@@@.......................................................@@@@
@@@@@.......................................................@@@@
@@@@@.......................................................@@@@

Red pixels are in blocks that aren't referenced by the inner file; yellow pixels are in the inner file but outside the ranges the TIFF header says to display; green pixels are displayed.
• The maze square data in the inner image uses the same bytes as the maze square data in the outer image. The top and bottom boundaries of each inner image maze square are all produced using the same block in the outer image, but the left and right boundaries aren't separable in that way and the mazes had to be constructed so that a given byte had the same left/right boundaries in both mazes.
• The inner maze contains only bytes with hex values between 20 and 40 or 60 and 80; when you XOR together two of these, you wind up with something between 40 and 60, i.e. an uppercase letter. That's why the inner maze's solution phrase doesn't have the spaces and punctuation that the outer one does.
• The filesystems were tailored to avoid as many fsck errors as possible, but the ones about cross-linked files and directories can't be avoided with this puzzle structure.