XtraORdinary picoMini by redpwn Solution

Description

1. Step 1Understand the encryption scheme

   Observation

   The script XORs five fixed strings in some number of times each. XOR undoes itself, so an even count cancels entirely and only the parity of each string matters, never 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 2Enumerate all 32 combinations

   Observation

   Parity alone leaves 32 possible combinations, and the known flag prefix gives you a free oracle. Test all 32 and filter on the prefix; no further cryptanalysis is needed.

   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 once tests one combination out of 32, and the right answer probably leaves some strings out. Loop over every five-bit pattern, letting each bit decide whether that string is included. Always applying all five tests exactly one case.

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

   Including the opening brace in the prefix check means the byte count has to match the output exactly, and an off-by-one there passes no candidates at all, which looks like no valid combination existing. Check the shortest unambiguous prefix and read the winner yourself.

   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.