Nuit Du Hack Quals - "Another One" writeup

This writeup was cross-posted from balidani.blogspot.hu. Author: Dániel Bali.

"Another One" was a crypto task for 300 points, but according to the number of solutions, it was the second easiest. Nonetheless, it was a cool little task, so I decided to make a quick writeup.

The task description doesn't say too much about what to do: "This is a crypted image, you must extract the data.". Well, duh. After downloading the image, I realized that it's a bmp file. There must be a very good reason for using a bmp file here, otherwise it would be a waste of bandwidth. Let's look at the file in a hex editor.

Crypted Hex

It looks like there are some random bytes in the beginning, and then a lot of repetitions. Of course the bytes in the beginning aren't random, they are part of the header. Knowing the bmp format, we can tell that the bytes after the header are part of the bitmap data itself.

How could the bmp be encrypted? Could it be a simple repeating xor key? It could, but then why is this picture a bmp? A big hint here is that the repeating part is 16 bytes long, which is the typical block size for block ciphers. If it's a block cipher, the mode has to be ECB, since it's practically impossible for CBC to generate repeating blocks. If it's indeed encrypted using ECB, we have a solution. Assume that the repeating part is white, and display any block that isn't identical as a few black pixels next to each other.

Since the rows are reversed in bmp files, we can go from the bottom, so that the image won't be flipped.

There is one problem: we need to figure out the original size of the image, otherwise all we get is some mess. Let's try some numbers. Note that the size of the image gives us a clue about possible sizes. Fiddling around with an empty bmp file, 1440 * 960 gives a very similar result in size, so we can start off with 1440 as the width. Here's result.

Result

This looks like the philosoraptor and some text, but it's not perfect. Next, we can try 2880, since it looks like 4 dinosaurs are overlapped. At this point we got a bit lucky, because Ubuntu's image viewer is awesome, and after zooming out, it fixed most of the errors. Then we mirrored the image and got this.

Solution

It's not impossible to read the message now:

"AllMyLifeIThoughtAirWasFreeUntilIBoughtABagOfChips".

Here is the script that generated these images. Thanks for the Nuit du Hack team for organizing the qualifier, we liked the challenges a lot.