Internet Problem Solving Contest

• Correct output for I1
• Correct output for I2

Once again, we decided to test the boundaries of the comfort zone of our contestants.

There were several ways how to solve this problem. The easy subproblem was easily solvable on any platform. You just had to realize that you are holding a full disk image and you had to attach it to your OS. (For some, such as Windows, this requires the installation of a custom driver, but it should be quick and painless if you have a clue about what you are doing.)

Below we will describe one possible solution, using standard Linux utilities. First we need to find out what the input files are. If we don’t already have an educated guess (e.g., from opening one in a text editor and seeing the string /mnt), we can ask the useful file utility.

$ file I1.in
I1.in: Linux rev 1.0 ext2 filesystem data, UUID=58a84427-92cc-4538-b61f-8f984f07f4bd (large files)
$ file I2.in
I2.in: Linux rev 1.0 ext2 filesystem data, UUID=ef5d870a-7ba3-4a5b-a3d3-7c29626efdcf (large files)

We can see that we are dealing with images of ext2 filesystem. To access files inside we need to mount it. However, we can only mount block devices, not files. So we need to create a block device from this file, so-called loop device. Mount will do this for us when we specify the loop option. And just to be on the safe side, let’s mount the filesystem read-only (ro option).

# mount -o loop,ro I1.in /mnt
# cd /mnt

In the easy subproblem, we can see that there is a structure of folders with symlink loops. Do we have any files?

# find -type f
./11/not-password-5
./27/8/not-password-13
./27/10/not-password-12
./27/not-password-12
./14/not-password-7
./26/password-9
...

OK, so let’s filter out only password-x files:

# find -name 'password*'
./26/password-9
./12/password-5
./19/password-8
./9/21/password-4
./9/4/password-3
./8/password-2
./0/password-0
./15/password-6
./4/6/password-1
./17/password-7

There are 10 of them, so we just print them in the correct order:

# for i in `seq 0 9`; do find -name "password-$i" -exec cat {} +; done
Password: uBUJpO7fWB5IGTUQ7z4JE32V69W22d3u
Password: Zk5kvD87CeiZfCUbFsp0cjHH4xo9dW6g
Password: y18Sq2V94lixg1OoZWyHYDbEnGYEAT91
Password: CP0MuBxNPmKUl3zGGeUIEAZxZR44oibF
Password: 9fPZZb06YAr0xlRip9f3DWdxYCizyDwF
Password: XCNSWRY8NBh9DC3BQ6pmnr0nDzJfDxwh
Password: W0cV0ItSiB3GdJmuZpvwamdVpUX18Ydh
Password: 3AGgg26w2YOSXhHt8aeGAg742GxVA34H
Password: yUboh0Zw712exxfjA1pMWQ4la2YT3p3l
Password: cRI2hCO8aCJhZnbYe2pUM1gVCjDoHzMD

Since we should only submit the 32-character strings let’s strip ‘Password:’.

# for i in `seq 0 9`; do find -name "password-$i" -exec cat {} +; done | cut -c 11-
uBUJpO7fWB5IGTUQ7z4JE32V69W22d3u
Zk5kvD87CeiZfCUbFsp0cjHH4xo9dW6g
y18Sq2V94lixg1OoZWyHYDbEnGYEAT91
CP0MuBxNPmKUl3zGGeUIEAZxZR44oibF
9fPZZb06YAr0xlRip9f3DWdxYCizyDwF
XCNSWRY8NBh9DC3BQ6pmnr0nDzJfDxwh
W0cV0ItSiB3GdJmuZpvwamdVpUX18Ydh
3AGgg26w2YOSXhHt8aeGAg742GxVA34H
yUboh0Zw712exxfjA1pMWQ4la2YT3p3l
cRI2hCO8aCJhZnbYe2pUM1gVCjDoHzMD

(Yeah, we know, you probably stopped two steps ago and did the rest in a text editor.)

In the hard subproblem we have just one file _YOU_NEED_TO_LOOK_DEEPER and lost+found folder. What’s deeper than files in an ext filesystem? After a bit of reading Wikipedia we can find out that files and directories are represented by inodes. And directories contain list of filenames and inode numbers of files in them. Now what is the lost+found folder for? After a bit of googling we will find that this folder is used by a filesystem check utility, which can recover some lost information, like inodes not attached to any directory.

So let’s check whether we are really dealing with a corrupted filesystem:

# e2fsck I2.in
e2fsck 1.42.13 (17-May-2015)
I2.in: clean, 13/1280 files, 199/5120 blocks

Well, the e2fsck thinks the filesystem is clean. That just means that all pending writes were successfully made before the system was unmounted, not that the system is not corrupted. Let’s do a forced check:

# e2fsck -f I2.in
e2fsck 1.42.13 (17-May-2015)
Pass 1: Checking inodes, blocks, and sizes
Pass 2: Checking directory structure
Pass 3: Checking directory connectivity
Pass 4: Checking reference counts
Unattached inode 214
Connect to /lost+found<y>? yes
Inode 214 ref count is 2, should be 1.  Fix<y>? yes
Pass 5: Checking group summary information

I2.in: ***** FILE SYSTEM WAS MODIFIED *****
I2.in: 13/1280 files (0.0% non-contiguous), 199/5120 blocks

Ha!

# mount -o loop,ro I2.in /mnt
# cd /mnt/lost+found/
# ls
'#214'
# cat \#214
OR0
xVv
1nM
fyD
XoN
bgW
erL
VgI
wz4
7JK
qtb
F8o
zt

The last thing that remains is to join the lines.

# paste -s -d'\0' \#214
OR0xVv1nMfyDXoNbgWerLVgIwz47JKqtbF8ozt