AES-ABC picoCTF 2019 Solution

Description

1. Step 1

   Understand the AES-ABC chaining

   Observation

   I noticed the challenge name 'AES-ABC' and the provided Python source defined a custom encryption scheme where each ECB-encrypted block was added to the previous encrypted block mod 2^128, which suggested that reversing this arithmetic chaining (without needing the AES key) would be the core of the solution.

   The AES-ABC mode: encrypt each 16-byte block with AES-ECB, then add the previous encrypted block (mod UMAX = 2^128) to produce the output. To reverse this, go through each block and subtract the previous block (mod UMAX). The result is still ECB-encrypted, but ECB preserves patterns - so the resulting file is a visually readable image.

   Learn more

   Why ECB leaks structure. In Electronic Codebook (ECB) mode, AES is applied to each 16-byte block independently with no chaining: C_i = AES_K(P_i). AES is a deterministic permutation, so identical plaintext blocks produce identical ciphertext blocks: P_i = P_j => C_i = C_j. The ciphertext therefore preserves the equality pattern of the plaintext blocks - it acts like a "codebook" lookup, hence the name.

   The ECB penguin. Encrypt an image of Tux with ECB and the silhouette is still visible. Why: the image has large uniform regions (e.g., the white belly), which means many adjacent blocks contain identical pixel patterns. Those blocks all encrypt to the same ciphertext, preserving the shape exactly. With CBC each block also XORs the previous ciphertext, so uniform plaintext produces wildly varying ciphertext.

   Worked example with two-block plaintext. Suppose P_1 = "AAAAAAAAAAAAAAAA" and P_2 = "BBBBBBBBBBBBBBBB":

   ECB:  C_1 = AES_K(P_1)
         C_2 = AES_K(P_2)
         C_1 != C_2 only because P_1 != P_2
   
   If P_1 == P_2, then C_1 == C_2 byte for byte.
   Attacker can detect repeated plaintext without the key.

   This challenge. The encrypted file is a PPM image whose pixel data was run through the AES-ABC chaining described above. Stripping the chaining (subtract the previous block mod 2^128) leaves ECB-encrypted pixel data, and because ECB preserves equal blocks, the flag text stays legible when you open the resulting PPM - no key needed; the patterns survive because ECB preserved them.

2. Step 2

   Modify the source to subtract instead of add

   Observation

   I noticed the chaining layer was pure arithmetic (addition mod 2^128) applied after ECB encryption, which suggested that subtracting the previous encrypted block from each block would undo the chaining and leave ECB-encrypted pixel data that is still visually readable due to ECB's pattern-preserving property.

   Take the provided Python encryption script. Remove the AES key reference (you don't have it), but keep the block parsing logic. Rewrite the encrypt method as a decrypt method: for each block, compute new_block = (UMAX - prev_block + current_block) % UMAX. Write the result to a .ppm output file.

   python

   python3 << 'EOF'
   # Modified from the challenge source - removes AES (no key) and reverses the ABC chaining
   UMAX = pow(2, 128)
   BLOCK_SIZE = 16
   
   def remove_abc(ciphertext_blocks):
       new_blocks = []
       prev = int.from_bytes(b'\x00' * BLOCK_SIZE, 'big')
       for block in ciphertext_blocks:
           curr = int.from_bytes(block, 'big')
           new_curr = (UMAX - prev + curr) % UMAX
           new_blocks.append(new_curr.to_bytes(BLOCK_SIZE, 'big'))
           prev = curr
       return b''.join(new_blocks)
   
   with open('body.enc', 'rb') as f:
       raw = f.read()
   
   # Parse the file: header (unencrypted), then encrypted blocks
   # Header is the PPM header ending at the pixel data start
   header_end = raw.index(b'\n', raw.index(b'\n', raw.index(b'\n') + 1) + 1) + 1
   header = raw[:header_end]
   body = raw[header_end:]
   
   blocks = [body[i:i+BLOCK_SIZE] for i in range(0, len(body), BLOCK_SIZE)]
   plaintext_body = remove_abc(blocks)
   
   with open('flag.ppm', 'wb') as f:
       f.write(header + plaintext_body)
   
   print("Wrote flag.ppm - open it to read the flag")
   EOF

   Copied!

   Expected output

   Wrote flag.ppm - open it to read the flag

   What didn't work first

   Tried: Try to decrypt using AES-CBC with a guessed or empty key before stripping the chaining.

   Without the AES key, any standard AES decryption call will produce garbage. The insight is that you do not need the key at all - the ECB pattern-preservation property means the image is readable even while still ECB-encrypted; you only need to reverse the arithmetic chaining layer, not the AES itself.

   Tried: Use (prev_block - current_block) % UMAX instead of (UMAX - prev_block + current_block) % UMAX to reverse the addition.

   Python's modulo of a negative number returns a positive result, so (prev - curr) % UMAX gives a different value than the correct subtraction formula. The correct inverse of (curr + prev) % UMAX is (curr - prev + UMAX) % UMAX, which avoids relying on Python's signed modulo behavior and matches the mathematical inverse exactly.

   Learn more

   The custom AES-ABC mode chains ECB-encrypted blocks by adding the previous ECB-encrypted block via addition mod 2^128. Since we don't have the AES key, we cannot fully decrypt back to plaintext - but we can strip the chaining by subtracting previous blocks. The result is still ECB-encrypted pixel data, which is fine: ECB preserves patterns, so the image is visually readable even when the individual pixel bytes are encrypted.

3. Step 3

   Open the resulting PPM file to read the flag

   Observation

   I noticed the encrypted file was a PPM image and that after stripping the arithmetic chaining the data would still be AES-ECB encrypted, which suggested that opening the output in an image viewer would reveal the flag visually because ECB's identical-block-to-identical-ciphertext property preserves the shapes and text drawn in the original image.

   Open flag.ppm with an image viewer (GIMP, or install a PPM viewer). Because ECB encryption applies the same transformation to equal blocks, the visual patterns of the original image survive. The flag text is visible in the image even though the pixel values are encrypted.

   bash

   gimp flag.ppm

   Copied!

   What didn't work first

   Tried: Open flag.ppm directly in a web browser or text editor expecting to read the flag as text.

   PPM is a binary image format - opening it in a browser shows a blank page or download prompt, and a text editor shows binary garbage. You need an image viewer that understands PPM (GIMP, display from ImageMagick, or eog) so the pixel data is rendered as a visual image where the flag text is legible.

   Tried: Run strings on flag.ppm looking for the flag as an embedded ASCII string.

   The flag is rendered visually as pixel data in the image, not stored as a literal ASCII string in the file. The pixel bytes that draw the flag characters are ECB-encrypted values - they are not printable ASCII. Only rendering the image lets you read the flag text visually.

   Learn more

   This is the classic ECB penguin demonstration: encrypt an image with AES-ECB and the silhouette is still recognizable because uniform regions (same pixel color) produce identical ciphertext blocks. The AES-ABC chaining was designed to hide this flaw, but stripping the chaining via subtraction exposes it again.

   Why not to roll your own crypto: The designers tried to improve ECB by adding block chaining via arithmetic, but the fix was reversible without the key. Real CBC mode XORs the previous ciphertext block into the plaintext before encryption - this is not reversible without the key because you cannot reconstruct the plaintext XOR mask.

Flag

Strip the custom block chaining by subtracting previous blocks (mod 2^128), then the ECB-encrypted image is visually readable - the flag is visible in the resulting PPM.