Scrambled: RSA picoCTF 2021 Solution

Description

1. Step 1Figure out what 'scrambled' actually means

   Observation

   The service returns the same ciphertext block for a repeated single character, but a different ordering for multi-character input. So encryption happens per character, and the only randomness is a shuffle of block order, not a nonce or a 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, which makes Wiener's the first RSA instinct, but Wiener needs d below n^0.25 and that does not hold here. The vulnerability is not in the key at all: it is per-character determinism, which probing single against multi-character inputs reveals immediately.

   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 known plaintext recover keystream bytes, but XORing output against input gives garbage here, because each character is independently RSA-encrypted. The tell is that encrypting 'a' twice returns the same block both times; a stream cipher would never 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 2Recover the flag character by character using the known prefix

   Observation

   Per-character RSA is deterministic, and the flag format guarantees the prefix picoCTF{. So anchor on that prefix and extend it one character at a time, 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

   A lookup table identifies which characters appear in the flag, but not their order, because the server reshuffles the blocks on every response. Without anchoring on the known picoCTF{ prefix you end up with an anagram of the flag body.

   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 sends ciphertext as concatenated decimal or hex text, not raw bytes, so a string replace on the decoded output is correct. Operate on the raw socket bytes before decoding and encoding mismatches leave the new-block variable empty, so every candidate character gets 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.