Compress and Attack picoCTF 2021 Solution

Description

1. Step 1Understand the CRIME/BREACH compression oracle

   Observation

   The server compresses your input together with the flag before encrypting. That makes the output length leak how much your input shares with the secret, which is the classic CRIME and BREACH compression oracle.

   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 2Implement the oracle attack

   Observation

   With the oracle understood, the attack scripts easily: iterate every printable candidate, send each as a prefix alongside the known flag fragment, and keep whichever produces the shortest ciphertext.

   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 makes DEFLATE emit a back-reference, so the compressed output gets shorter, not longer. Picking the maximum length selects the wrong character every time. The signal is the minimum compressed length across the candidates for a 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 one-byte difference can disappear, because the right and wrong guesses round up to the same block count. Adding 1 to 15 bytes of filler before the candidate shifts that boundary, so the single-byte signal lands between two block counts and shows up 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.