Compress and Attack picoCTF 2021 Solution

Description

1. Step 1

   Understand the CRIME/BREACH compression oracle

   Observation

   I noticed the server description says it compresses your input together with the flag before encrypting, which suggested the output length leaks information about shared substrings between the input and the secret, a classic CRIME/BREACH compression oracle side-channel.

   The server compresses your input + the secret flag together before encrypting. If your input shares a prefix with the flag, compression will produce shorter output. By guessing the flag one character at a time and observing output lengths, you can recover the flag.

   Learn more

   CRIME and BREACH attacks exploit the interaction between data compression and encryption. The attack works because:

   1. Compression algorithms like DEFLATE replace repeated substrings with back-references. If your input string matches a substring of the secret, the combined compressed output is shorter.
   2. When the server compresses (input + secret) together and you can observe the output length, you learn information about shared substrings between input and secret.

   The signal you're listening for. A correct one-character guess shrinks the compressed output by roughly one byte; a wrong guess produces an output one byte longer. With block ciphers padding to 16-byte boundaries, that 1-byte signal can fall between two blocks and become invisible - mitigated by adding 1-15 bytes of padding before each guess to push the boundary.

   Reading the oracle response. Whatever shape the server speaks, what you ultimately measure is byte count: HTTP responses give you a Content-Length header (or you count r.content); a netcat-style oracle just emits the ciphertext, count len(p.recvall()). If the channel is plaintext-on-the-wire and you can sniff it, tcpdump -A -i lo port <n> -w cap.pcap plus tshark -r cap.pcap -T fields -e tcp.len gives a tcp-level byte count.

   Character-by-character recovery: Suppose the flag is picoCTF{XXXX}. Guess each unknown character:

   • Send picoCTF{a + padding, observe compressed length
   • Send picoCTF{b + padding, observe compressed length
   • ...repeat for all characters...
   • The correct character produces the shortest compressed output
2. Step 2

   Implement the oracle attack

   Observation

   I noticed that once the compression oracle side-channel was understood, the attack could be scripted by iterating over all printable candidate characters, sending each as a prefix alongside the known flag fragment, and selecting whichever produces the shortest ciphertext response.

   Write a script that connects to the service, sends each candidate prefix, reads the response length, and identifies the shortest one as the correct next character.

   python

   python3 - <<'EOF'
   from pwn import *
   import string
   
   CANDIDATES = string.printable
   
   def query(prefix):
       p = remote('mercury.picoctf.net', <PORT_FROM_INSTANCE>)
       p.recvuntil(b'input: ')  # or whatever the prompt is
       p.sendline(prefix.encode())
       response = p.recvall(timeout=2)
       p.close()
       return len(response)
   
   known = 'picoCTF{'
   
   while not known.endswith('}'):
       lengths = {}
       for c in CANDIDATES:
           candidate = known + c
           length = query(candidate)
           lengths[c] = length
           log.info(f"Trying {c!r}: length={length}")
   
       best = min(lengths, key=lengths.get)
       known += best
       log.success(f"Recovered so far: {known}")
   
   print(f"Flag: {known}")
   EOF

   Copied!

   What didn't work first

   Tried: Guess each character by looking for the LONGEST response instead of the shortest.

   A correct prefix match causes DEFLATE to emit a back-reference, making the compressed output shorter, not longer. Picking the maximum length selects the wrong character every time. The correct signal is the minimum compressed length among all candidate guesses for a given position.

   Tried: Run the script without block-alignment padding and observe that all candidates produce the same response length.

   When a block cipher pads the compressed data to a 16-byte boundary, a 1-byte length difference in the compressed stream can vanish because both the correct and wrong guesses round up to the same block count. Adding 1-15 bytes of filler before the candidate prefix shifts the boundary so the single-byte signal falls between two distinct block counts and becomes visible again.

   Learn more

   Practical tips for compression oracle attacks:

   • Length differences may be small (1 byte or even less if block ciphers round up to block boundaries). Average multiple queries for the same input to reduce noise.
   • If a block cipher is used after compression, the output length increases in 16-byte steps. Add padding to your input to push the boundary between blocks, making single-character length differences visible.
   • The zlib compressor achieves better back-reference compression for longer matches. Starting from a known prefix (like picoCTF{) that is already in the flag makes subsequent characters easier to detect.

   Real-world CRIME defeated HTTPS SPDY compression (2012) and BREACH defeated HTTP body compression (2013). Both were mitigated by disabling response body compression or adding masking (secret mixing into the data stream). For more web-side compression and side-channel patterns, see web challenge bug patterns.

Flag

Static flag, confirmed consistent across multiple independent verified solutions.