Resetting the IV is fatal

CTFZone 2017 Decrypt the Undecryptable: Recovering a BMP from AES-CFB

An encrypted bitmap still shows its outline, because the cipher restarts every 128 bytes with a zero IV. The most common ciphertext chunk is the keystream, and XORing with it reveals the picture.

Hexfield editorial

EventCTFZone 2017
CategoryCrypto, reverse
Points724
FlawCFB with IV reset
Crypto724 pts
  1. 01

    Inspect

    The package holds a 64-bit ELF decryption utility and flag.encrypted, a 1200 by 800 BMP whose outline remains visible after encryption.

  2. 02

    Hypothesize

    A visible pattern means identical plaintext blocks give identical ciphertext, and a 128-byte repetition suggests a fixed segment size.

  3. 03

    Test

    Splitting the pixel data into 128-byte chunks shows one chunk dominating the file, which is what a uniform background would produce.

  4. 04

    Solve

    XORing every chunk with the most common one restores the picture except for artifacts after non-zero blocks, enough to read the flag.

Byte map of an uncompressed 24-bit BMP with a long uniform background and a header block at the start
An uncompressed bitmap is mostly runs of identical bytes, exactly the property that this cipher construction fails to hide.

What is in the package

The Decrypt the undecryptable task from CTFZone 2017 carries 724 points and is listed under both ppc and reverse engineering, though the decisive step is cryptanalytic. The story says the decryption keys to a secret store were lost, and the system was built by the lowest bidder, so it may be flawed. The download is a TAR file with two members: decrypt_utility, a 64-bit ELF program, and flag.encrypted, which is an encrypted 1200 by 800 BMP.

Looking inside the utility reveals what reverse engineering can and cannot do here. It uses AES-256, and it checks a supplied key against a stored SHA-1 digest. A key is not embedded, only its hash, so the utility is useless for recovery. A 256-bit key cannot be brute-forced, and the intended path is to look at the data instead.

The encrypted picture still shows a picture

Converting flag.encrypted to a viewable image, by treating it as a bitmap, shows something that strong encryption should never produce: a visible structure. Large areas are filled with a repeating texture, and the outline of the content can be seen. The hex dump gives the numeric version of the same observation, with identical 128-byte blocks repeating through the pixel data.

The numbers make the layout clear. A BMP starts with a 14-byte file header and a 40-byte info header, 54 bytes in all, which is 0x36. At 24 bits per pixel a row of 1200 pixels takes 3600 bytes, already a multiple of four, so there is no row padding. The pixel data therefore occupies 2,880,000 bytes, which is exactly 22,500 chunks of 128 bytes. The file is 54 bytes longer, and the header is not encrypted, which allows a viewer to open the result at all.

Why 128 bytes

AES works on 16-byte blocks, and CFB mode turns the block cipher into a stream cipher by encrypting the previous ciphertext block, or the IV for the first, and XORing the result with the plaintext. A correct implementation chains blocks through the whole message. Here the implementation splits the data into 128-byte fragments, eight AES blocks each, and starts every fragment again from an all-zero IV with the same key.

That reset is the flaw. The first keystream block of every fragment is the same value, AES under the key applied to zeros. If a fragment’s plaintext is all zero bytes, as in a black region of the picture, then every block of its ciphertext equals the keystream: block one is E(0), block two is E(block one), and so on. Every black fragment therefore encrypts to the same 128 bytes. The most frequent chunk in the file is simply the encryption of zeros, and it doubles as a 128-byte keystream.

The decoder

Counting chunk frequencies finds that keystream, and XORing each chunk with it undoes the first block of each fragment exactly.

from collections import Counter

n, hdr = 128, 0x36
data = open("flag.encrypted", "rb").read()
head, body = data[:hdr], data[hdr:]
chunks = [body[i:i + n] for i in range(0, len(body), n)]
key = Counter(chunks).most_common(1)[0][0]

out = bytearray(head)
for c in chunks:
    out += bytes(a ^ b for a, b in zip(c, key))
open("flag.bmp", "wb").write(out)

The XOR with the key removes the keystream for block one of any fragment, because block one equals plaintext XOR E(0), and E(0) is the key. For all-zero fragments the whole fragment is recovered.

Why it only almost works

A block two correct decryption requires that the ciphertext fed into AES matches the one in the all-zero case. That holds only if block one of the fragment was zero. If any block contains a non-zero byte, its ciphertext differs from the zero-fragment keystream, so the next AES input differs, the next keystream block differs, and the XOR no longer cancels it. The block that contains the non-zero data is still decoded correctly, because its keystream depends only on the earlier blocks. Everything after it in that fragment is garbage.

On a picture with a dark background and light text, the result is a faithful image with noisy streaks to the right of each stroke, extending up to the end of the 128-byte fragment. The text remains legible in spite of the noise, which is enough to read the flag.

Checking the diagnosis

Two quick measurements confirm the model before any decoding. First, the number of distinct 128-byte chunks should be far smaller than 22,500, with one value dominating. Second, the dominant chunk should be a multiple of eight AES blocks of apparently random bytes, with no internal repetition, because it is a chain of AES outputs. If the dominant chunk showed internal repetition, ECB would be the better explanation. Since the chunk is aligned to 128 bytes while rows are 3600 bytes, the alignment of fragments to pixel rows drifts from line to line, which is why the noise streaks do not line up in columns.

What transfers to other challenges

Look for structure in ciphertext before touching the key. Equal inputs giving equal outputs signals ECB, a fixed IV, or a reset counter, and an image or a file header makes the effect visible. Chunk frequency counting is a fast test, and so is a byte-map picture of the file, a technique covered in the overview of binary visualization. A mode of operation is only as strong as its chaining, and a 256-bit key does not help when the construction repeats itself. The affine cipher on base32 shows the opposite case, where a weak algorithm is broken from known text alone.

Questions readers ask

Why does the image keep its shape after AES encryption?

The construction restarts with a zero initialization vector for every 128-byte segment. Equal plaintext segments then encrypt to equal ciphertext segments, just as in ECB mode, so large uniform areas of the bitmap become large areas of one repeated pattern.

Why are there artifacts after the XOR step?

CFB feeds the previous ciphertext block into the next AES call. The shortcut only holds while all earlier blocks of a segment are zero. After the first non-zero block the chain differs from the all-zero case, so the remaining blocks in that segment decode wrongly.

Is recovering the key necessary?

No. The utility only stores a SHA-1 hash of the key to verify input, and a 256-bit key cannot be searched. The flaw is in how the cipher is applied, so the plaintext can be recovered without any key material.

New to capture the flag? Formats, teams and a first-month plan in one place.

Read the CTF guide