Scrambled: RSA picoCTF 2021 Solution

Description

1. Step 1

   Figure out what 'scrambled' actually means

   Observation

   I noticed the service produces the same ciphertext block for a single repeated character but a different ordering for multi-character inputs, which suggested the encryption is applied per character and the only randomness is a block-order shuffle rather than any nonce or stream cipher.

   The service does NOT encrypt the message as one big integer. It encrypts each character separately with textbook RSA (c_i = ord(char)^e mod n), then concatenates the per-character ciphertexts in a randomized order. Encrypting the same single character always yields the same block; encrypting a multi-character string yields the same set of blocks but shuffled. That shuffle is the only 'scramble' there is, and it is exactly what makes the scheme breakable.

   bash

   # Probe the behavior by hand first:
   nc mercury.picoctf.net <PORT_FROM_INSTANCE>
   # send: a        -> note the ciphertext
   # send: a        -> identical (single chars are deterministic)
   # send: ab       -> note it
   # send: ab       -> same two blocks, different order

   Copied!

   What didn't work first

   Tried: Treat the entire encrypted flag as one large integer and try to factor n or apply Wiener's theorem

   The server prints n and e=65537, making Wiener's theorem the first RSA instinct, but Wiener requires d < n^0.25, which is not the case here. The real vulnerability is not in the key at all - the break comes from per-character determinism, which probing behavior (single vs. multi-character inputs) immediately reveals.

   Tried: Assume the scramble is XOR or a transposition cipher applied to the full ciphertext bytes, and try known-plaintext XOR recovery

   XOR-based scrambling would let you recover keystream bytes if you know plaintext, but sending a known string and XORing the output with the input produces garbage here because each character is independently RSA-encrypted. The telltale sign is that encrypting 'a' twice gives the same block both times - a stream cipher XOR result would not repeat like that.

   Learn more

   Why per-character RSA is fatal. Textbook RSA is deterministic: a given plaintext block always maps to the same ciphertext block under a fixed key. The author tried to add confusion by shuffling the block order, but shuffling does not hide which blocks are present. Since the flag is encrypted the same way the service encrypts your input, the set of ciphertext blocks in the encrypted flag is just { Enc(c) for each character c in the flag }.

   The only thing you are missing is order. If you encrypt every printable character once, you can build a lookup from ciphertext-block to character and immediately recover the multiset of flag characters. The shuffle destroys their order, so the last problem is reconstructing the sequence. The flag format picoCTF{...} gives you a known starting prefix to anchor that reconstruction.

2. Step 2

   Recover the flag character by character using the known prefix

   Observation

   I noticed that per-character RSA is deterministic and the flag format guarantees the prefix picoCTF{, which suggested anchoring on that known prefix and extending it one character at a time by matching each candidate's isolated ciphertext block against the encrypted flag.

   Walk the flag left to right. Maintain the part you have recovered so far (seed it with 'picoCTF{'). For each candidate next character, encrypt prefix+candidate and isolate the candidate's block by removing the blocks you get from encrypting prefix alone. If that isolated block appears in the encrypted flag, accept the candidate and append it. Stop when you append '}'.

   python

   python3 - <<'PY'
   import string
   from pwn import remote
   
   r = remote("mercury.picoctf.net", <PORT_FROM_INSTANCE>)
   
   # The banner prints the encrypted flag, n, and e. Capture the flag ciphertext
   # as the raw decimal/hex string the service prints (do not parse it as one int;
   # treat it as the concatenation of fixed-width per-character blocks).
   flag_ct = r.recvline_contains(b"flag").split(b":")[1].strip().decode()
   
   def enc(s):
       r.sendline(s.encode())
       return r.recvline().strip().decode()
   
   decoded = "picoCTF{"
   while not decoded.endswith("}"):
       prev = enc(decoded)              # blocks for the current known prefix
       for ch in string.printable:
           cur = enc(decoded + ch)      # prefix blocks + the new character's block
           # the new character's block is whatever 'cur' has that 'prev' did not
           new_block = cur.replace(prev, "", 1)
           if new_block and new_block in flag_ct:
               decoded += ch
               break
       print(decoded)
   
   print("FLAG:", decoded)
   PY

   Copied!

   Expected output

   FLAG: picoCTF{bad_1d3a5_...}

   Because single characters encrypt deterministically, every comparison is exact and the search never backtracks. The loop adds one correct character per round until it hits the closing brace.

   What didn't work first

   Tried: Build a full lookup table by encrypting every printable character once, then map each block in the flag ciphertext to a character and sort alphabetically

   The lookup table approach correctly identifies which characters are in the flag but cannot recover their order because the server shuffles the blocks on every response. Without anchoring on the known 'picoCTF{' prefix, you end up with an anagram of the flag body rather than the actual flag.

   Tried: Use cur.replace(prev, '', 1) to isolate the new block but apply it to raw ciphertext bytes instead of the decimal string the server prints

   The server outputs ciphertext as a decimal or hex string concatenation, not raw bytes, so string replace on the decoded text works correctly. Attempting to operate on raw socket bytes before decoding introduces encoding mismatches and the new_block variable comes out empty, causing every candidate character to be skipped.

   Learn more

   Why the prefix anchor is necessary. Without it you could decode the multiset of characters but not their order, and a flag is meaningless scrambled. By always encrypting the full known prefix you keep the comparison unambiguous: the single block that appears when you extend the prefix by one character is precisely the encryption of that character, and you only accept it if the encrypted flag actually contains that block at that stage.

   The lesson. Encrypting a message in small independent units (here, one character at a time) leaks structure no matter how you reorder the ciphertext. This is the same weakness that makes ECB block-cipher mode insecure: identical plaintext units produce identical ciphertext units. Real RSA encrypts a single padded block (OAEP) so this attack has nothing to chew on.

Flag

The service encrypts each character independently with textbook RSA and concatenates the blocks in random order. Single characters are deterministic, so you map ciphertext blocks back to characters and use the known picoCTF{ prefix to recover their order one at a time.