XtraORdinary picoMini by redpwn Solution

Description

1. Step 1

   Understand the encryption scheme

   Observation

   I noticed the encryption script applies each of 5 fixed strings some number of times via XOR, and since XOR is self-inverting, applying any value an even number of times cancels out, which suggested that only the parity (odd or even count) of each string's application matters rather than the exact count.

   The flag is XORed with an unknown key. Then each of 5 fixed strings is XORed with the result some number of times. Because XOR is self-inverting, XORing with the same value an even number of times cancels out - only strings applied an odd number of times affect the final ciphertext.

   Learn more

   XOR (exclusive OR) is a bitwise operation with a critical cryptographic property: it is its own inverse. A XOR B = C implies C XOR B = A and A XOR B XOR B = A. Applied an even number of times, any XOR operation cancels perfectly, leaving the original value unchanged. Applied an odd number of times, exactly one application remains effective.

   This property makes XOR the foundation of stream ciphers and one-time pads, but it also creates predictable weaknesses when keys are reused or when the structure of key application is known. Here, the encryption applies 5 known strings each some number of times - the unknown is only whether each count is odd or even. This collapses the key space from an exponentially large set to exactly 2^5 = 32 possibilities.

   Understanding the algebraic structure of an encryption scheme - which operations cancel, which are redundant, what the minimal effective key space is - is the essence of cryptanalysis. Rather than attacking the algorithm itself, this challenge attacks the implementation's key schedule: the specific pattern of how keys are applied creates exploitable structure.

2. Step 2

   Enumerate all 32 combinations

   Observation

   I noticed that parity-only dependence collapses the effective key space to exactly 2^5 = 32 possibilities, and the known flag prefix 'picoCTF{' gives a free plaintext oracle, which suggested exhaustively testing all 32 combinations and filtering by the expected prefix rather than using any deeper cryptanalysis.

   There are 5 fixed strings, and each was either applied an odd or even number of times - giving 2^5 = 32 possible combinations. Brute-force all combinations, XOR them against the ciphertext, and check which result starts with the flag prefix picoCTF{.

   python

   python3 -c "
   from itertools import product
   # Load ciphertext and the 5 fixed strings
   ciphertext = bytes.fromhex(open('enc_flag').read().strip())
   strings = [b'...', b'...', b'...', b'...', b'...']
   for bits in product([0,1], repeat=5):
       result = bytearray(ciphertext)
       for use, s in zip(bits, strings):
           if use:
               for i in range(len(result)):
                   result[i] ^= s[i % len(s)]
       if result[:7] == b'picoCTF':
           print(result.decode())
   "

   Copied!

   Expected output

   picoCTF{w41t_s0_1_d1dnt_1nv3nt_x0r???}

   What didn't work first

   Tried: Trying all 32 combinations but only XORing the ciphertext with each string once, ignoring parity entirely

   Applying each string exactly once forces a single fixed combination rather than scanning all 32 parity vectors, so the correct parity tuple - where some strings must NOT be applied - is never checked. The loop over product([0,1], repeat=5) is required so that each bit controls whether a given string is included; omitting the bits variable and always applying all 5 strings tests only the (1,1,1,1,1) case and misses the correct answer if its parity vector differs.

   Tried: Using result[:7] == b'picoCTF{' (8 bytes with the brace) instead of b'picoCTF' (7 bytes) as the known-plaintext filter

   If the flag prefix check includes the opening brace, the byte count must match exactly what the challenge output contains - a minor off-by-one here causes the filter to pass no candidates, making it appear that no valid parity vector exists. The safer approach is to check the shortest unambiguous prefix (7 bytes, 'picoCTF') and then visually confirm the full result looks like a valid flag.

   Learn more

   itertools.product([0,1], repeat=5) generates all 32 combinations of five binary values: (0,0,0,0,0), (0,0,0,0,1), ..., (1,1,1,1,1). This is equivalent to counting from 0 to 31 in binary. Each tuple represents a "which strings were applied an odd number of times" configuration - 1 means apply this string, 0 means skip it (even applications cancel).

   Known-plaintext validation uses the known flag prefix picoCTF{ as a filter. After XORing the ciphertext with a candidate combination of strings, the result is valid only if it starts with the expected bytes. This check eliminates all incorrect combinations immediately - with 32 possibilities and 7 bytes of known prefix, only the correct combination (and possibly no false positives) passes.

   This brute-force is feasible because the key space is tiny (32 options) and each XOR operation is O(n) in the flag length. The total work is 32 * 5 * flag_length operations - trivially fast even in pure Python. For key spaces up to about 2^40, brute force with known plaintext checking is often the right approach in cryptographic CTF challenges.

   The repeating key XOR (s[i % len(s)]) handles fixed strings shorter than the ciphertext by cycling them - the same technique used in the Vigenère cipher and many stream ciphers. If the key period were unknown, frequency analysis or index-of-coincidence methods could find it. Here, the strings are known, so no analysis is needed.

   XOR algebra worked example:
     Suppose flag prefix m = "pico" = 0x70 0x69 0x63 0x6f
     Master key K = 0xAA 0xBB 0xCC 0xDD (unknown)
   
     After flag XOR K:    0x70^0xAA = 0xDA
                          0x69^0xBB = 0xD2
                          0x63^0xCC = 0xAF
                          0x6f^0xDD = 0xB2
   
   Then 5 fixed strings s1..s5 are applied each n_i times:
     s1 = 0x10 0x20 0x30 0x40   applied n1 times
     s2 = 0x01 0x02 0x03 0x04   applied n2 times
     ... etc.
   
   Because (a XOR b) XOR b = a, applying s_i an even number of times
   is identical to not applying it at all. Applying it an odd number
   is identical to applying it exactly once. So the effective ciphertext is:
     C = M XOR K XOR (parity_1 * s1) XOR (parity_2 * s2) XOR ...
   where parity_i in {0, 1}.
   
   There are 2^5 = 32 possible parity tuples. For each tuple, we compute:
     candidate_K_combined = K XOR (parities applied to s_i)
   and recover M_guess = C XOR candidate_K_combined.
   
   We test the parity (1, 0, 1, 0, 1) by computing
     C XOR s1 XOR s3 XOR s5
   and checking whether the first 7 bytes equal "picoCTF". Exactly one
   of the 32 tries will pass; that is the correct parity vector and
   the decoded message is the full flag.

Flag

XOR with the same value twice returns the original - strings applied an even number of times cancel completely, leaving only 32 effective combinations to test exhaustively.