CTFZone 2017: Decrypt the undecryptable

Decrypt the undecryptable

CTF: CTFZone 2017
Points: 724
Category: ppc, reverse

Description

Oh noes! It looks like we’ve lost decryption keys to our super-secret archive that contains all the blackmail material we’ve accumulated over the years!
Luckily, the encryption system was built with the government money by the lowest bidder, so maybe it contains some flaws.

In this challenge we were given a TAR archive decrypt_the_undecryptable.tar, which contained two files:

• decrypt_utility – an 64-bit ELF executable
• flag.encrypted – a 1200×800 BMP image

flag.encrypted

Solution

By looking at the encrypted image we can clearly see a repeating pattern, which might indicate that data was XOR’ed with a key of currently unknown length. Hex dump confirmed that theory. Indeed there were repeating 128-byte blocks inside the image data.
As a result of this simple analysis, we came up with very straightforward idea for decryption:

1. Split image into 128-byte chunks.
2. Find the most common chunk (it probably represents some solid color of background).
3. XOR all data blocks with discovered key.

Although the result is not perfect, it’s enough to extract the flag: ctfzone{5784e25b2af8b3fd817621cdf48e6e675d0e9388}.

Why this method “almost” works

First, a quick recap on block ciphers. Blocks ciphers work on fixed-size groups of bits and transform them using a secret key. The same key is used for both encryption and decryption.

In our case, AES-256 is responsible for data encryption and that means block size of 128 bits (16 bytes) and key size of 256 bits (32 bytes). Although presence of decryption utility might give us some hope of extracting the key, it is unfortunately impossible. The only trace of the original encryption key remains as its SHA1 sum, used to verify whether the key supplied as argument from command line is correct.

All of this leads us to the final ingredient and ultimately the flaw, which allowed us to decrypt the data. AES is used in CFB mode which uses ciphertext from previous block as input for the next block (look at diagram below for reference), however, it is used in an unusual way. Data is split into 128-byte fragments (8 AES blocks), each of which is encrypted separately i.e. resetting IV to zeros. The XOR “key” that our Python script found is basically an encrypted fragment of zero bytes. Since we know the output of AES with IV as input, we’re able to recover the plaintext. We can repeat this trick if plaintext contains only zero bytes. Unfortunately, when we encounter a block with some non-zero bytes, our decryption method breaks for the next block (different ciphertext used as input for AES). Thus the result contains some artifacts.

In the diagram, you can see, how blocks are chained in CFB mode. Orange color represents our XOR “key”, grey represents zero byte block, and green some non-zero bytes. We are able to decrypt everything until some unexpected, non-zero byte appears. In that case we XOR this block correctly, because output of AES isn’t changed, but the next block is impossible to decrypt.