Saturday, April 5, 2014

Nuit Du Hack Quals - "Another One" writeup

"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.


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.


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.


It's not impossible to read the message now: 

"AllMyLifeIThoughtAirWasFreeUntilIBoughtABagOfChips".

Here is the script that generated these images: https://gist.github.com/balidani/9999716
Thanks for the Nuit du Hack team for organizing the qualifier, we liked the challenges a lot.

7 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. How could you recover the BMP header ?

    ReplyDelete
    Replies
    1. There was no need to recover the BMP header. I simply cut it off and reconstructed the image as a PNG

      Delete
    2. thank you,
      in your code, there is :
      for i, chunk in enumerate(reverse_chunks):
      for j in range(i * 6, (i +1) * 6):
      what does it mean ? 1 byte in bmp = 6 byte in png ???

      Delete
    3. That's an approximation, since I was assuming it's a 24bit bmp. If so, then one pixel will be 3 bytes, and 16 bytes (one ECB block) would cover 16/3 pixels, which is 5.33. Maybe 5 would result in a better quality image, but the most important factor is guessing the width

      Delete
    4. Wonderful :)
      I'm very interested in steganography !
      Thank you for you great write up :)

      Delete
  3. This comment has been removed by the author.

    ReplyDelete