AES-ABC picoCTF 2019 Solution

Description

1. Step 1Understand the AES-ABC chaining

   Observation

   The provided Python defines a custom scheme: each ECB-encrypted block is added to the previous encrypted block, mod 2^128. That extra arithmetic layer is the whole puzzle, and reversing it does not require the AES key.

   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 2Modify the source to subtract instead of add

   Observation

   The chaining layer is pure arithmetic laid on top of ECB. Subtracting the previous encrypted block from each block undoes it, leaving ECB-encrypted pixel data that is still visually readable, because ECB preserves patterns.

   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 decryption call returns garbage. The point is that you never need the key: ECB preserves patterns, so the image is legible while still encrypted. Only the arithmetic chaining layer has to be reversed.

   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 is not the inverse you want. The correct inverse of (curr + prev) % UMAX is (curr - prev + UMAX) % UMAX, which matches the mathematical inverse without leaning on signed-modulo behavior.

   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 3Open the resulting PPM file to read the flag

   Observation

   The file is a PPM image, and stripping the chaining still leaves it AES-ECB encrypted. That is fine: ECB maps identical blocks to identical ciphertext, so the shapes and text drawn in the original survive. Open the output in an image viewer and read the flag.

   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. A browser shows a blank page or a download prompt, and a text editor shows binary garbage. Use a viewer that understands PPM (GIMP, ImageMagick's display, or eog) so the pixels actually render.

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

   The flag is drawn into the image as pixels, not stored as an ASCII string. The bytes that form the letters are ECB-encrypted values and are not printable text, so only rendering the image lets you read it.

   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.