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 the block multiset of each candidate prefix against the encrypted flag's.

   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, split the reply into fixed-width blocks, and count them. Accept the candidate when every block it uses appears in the encrypted flag at least as many times as the candidate prefix uses it. Counting rather than plain membership is what makes repeated characters behave. Stop when you append '}'.

   python

   python3 - <<'PY'
   import string
   from collections import Counter
   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()
   
   # Every character encrypts to the same fixed width, so one probe gives it.
   width = len(enc("a"))
   
   def blocks(ct):
       return [ct[i:i + width] for i in range(0, len(ct), width)]
   
   flag_blocks = Counter(blocks(flag_ct))
   
   decoded = "picoCTF{"
   while not decoded.endswith("}"):
       for ch in string.printable:
           # Order is randomized, so compare multisets of blocks, never substrings.
           cand = Counter(blocks(enc(decoded + ch)))
           if all(cand[b] <= flag_blocks[b] for b in cand):
               decoded += ch
               break
       print(decoded)
   
   print("FLAG:", decoded)
   PY

   Copied!

   Expected output

   FLAG: picoCTF{bad_1d3a5_...}

   Because single characters encrypt deterministically, block equality is exact: the only thing the shuffle costs you is ordering, which the growing prefix supplies. The loop adds one 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: Isolate the new character's block with a string replace, e.g. cur.replace(prev, '', 1)

   That only works if the blocks for the known prefix stay contiguous and in the same order inside the longer response, and they do not: the server reshuffles them on every reply. Split the response into fixed-width blocks and compare multisets (collections.Counter) instead, which is order independent.

   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: extending it by one character adds exactly that character's block to the reply, and you only accept the guess if the encrypted flag still has room for every block the extended prefix uses, counted with multiplicity.

   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.