ASIS CTF Finals 2013 - Chessboard (stegano 175)

This is a task from the ASIS CTF Finals 2013, "Stego" (steganography) category, and it was solved by 2 teams including ours. This was one of my favorite tasks on this CTF, since it was unconventional, interesting and didn't involve too much guessing.

We were given the following description:

Find the flag. Flag is in the form of ASIS_X which X is not a MD5 hash.

And the following PNG image:

The PNG file itself (as in: the PNG format) was clean - it did not contain any hidden data and there was no LSB-stegano - basically what you see is what you get, and what you get it an 8x8 matrix. The bitmap had total of 37-color squares: black plus 36 shades of grey, starting from RGB(5,5,5), up to RGB(180,180,180).

The important part here is that the RGBs of the shades of grey were always divisible by 5; so the darkest was RGB(5,5,5), then RGB(10,10,10), then RGB(15,15,15), ... - you get the picture. Dividing the RGB (or actually the average luminosity) by 5 you would get this:

.. 28 .. .. ..  7 .. ..
.. 16 .. .. 22  6 14 30
.. 19 .. .. .. .. .. ..
.. 31 20 34 26 .. .. ..
27 35 17 29 .. 15 33 ..
 1 23 21  9  5  2 25 18
36  4 .. 32 13  3 .. 24
.. .. .. .. 10 11  8 12

We can transcribe to coordinates of each square, counting from top-left, in the order pointed to by the above chart (by luminosity):

 1: 0,5
 2: 5,5
 3: 5,6
 4: 1,6
 5: 4,5
 [...]

There are a couple of things that can be deduced here:

1. There are 64 fields total, so this is probably some 64- or lower based encoding.
2. If this is a 64-based encoding (like base64), then the password will have to have unique base64 characters, since it's not possible to place more than one square on a given coordinate (and no shade was missing).
3. Taking the coordinates and doing a standard idx = x + y * 8 doesn't give you anything meaningful (i.e. converting what you get to base64 alphabet and decoding it doesn't give you anything meaningful).
4. Taking the reversed coordinates (bottom-right instead of top-left) doesn't give you anything meaningful either.

At this point I've changed my approach. In the task description we were given the information that the flag begins with ASIS_ (same as the flags in most of the tasks), so we did have a part of the plaintext. Encoding the ASIS_ string to base64 we get QVNJU18=, so we are sure that the first few chars will be Q, V, N, J, U and 1 (I'm not taking the last char ("8") into account, since it contains two bits of the next character 8-bit character, which in this case are of course zeroes, but could be anything in the full flag).

Translating the given base64 characters into indexes in the base64 alphabet gives you: 16, 21, 13, 9, 20, 53. And now the big question - how to get the value of e.g. 16 using the coordinates of the first square (0,5)?

Well, you can't do that using the top-left coordinates - if you would want to get 16 from the standard formula mentioned above you would have to have coordinates 0,2. But isn't 0,2 the coordinates of the first square in bottom-left coordinates which we haven't yet tried? Well, yes, it is.

Let's test this idea for the second square: bottom-left coordinates are 5,2, which means that the idx is 5 + 2 * 8, so 21, which is exactly the second element in the above number list!

So to get the flag you need to, going from the darkest to the brightest square:

1. Get it's bottom-left coordinate.
2. Calculate the idx using the idx = x + y * 8 formula.
3. Take the idx-th character in the base64 alphabet and append it to the result string.

After that you will get the string QVNJU19GTEFHM2dxaXpiS0RPWkY5b3hLejZI, which, after decoding, will result in the flag: ASIS_FLAG3gqizbKDOZF9oxKz6H.

From what I've read on IRC most of the teams were really really close with this task, but didn't end up testing the bottom-left coordinates. Funnily I did test this coordinate system, but due to a bug in my code I didn't get the code until did the plaintext attack - lucky me ;)