Rolling My Own picoCTF 2021 Solution

Description

1. Step 1Identify the encryption routine
   Disassemble the binary with Ghidra or objdump. Find the function that transforms data - look for loops with XOR, bit rotation, addition, or substitution table lookups.
   bash

   objdump -d rmo | less

   Copied!

   bash

   strings rmo | grep -v '/\|lib\|gcc\|glibc'

   Copied!
   Learn more

   Rolling your own crypto is a well-known anti-pattern in security. Custom encryption algorithms almost always have weaknesses that standard, peer-reviewed algorithms avoid. In CTF challenges, custom ciphers are typically one of:

   • XOR cipher: Each byte is XORed with a key (or key byte, in a rotating key). Since XOR is its own inverse, decryption uses the same operation.
   • Custom substitution cipher: Each byte is looked up in a substitution table. Reverse the table to decrypt.
   • Combined rotation + XOR: Bytes are bit-rotated and XORed. Reverse each operation in reverse order.
   • State-based stream cipher: A PRNG-like state produces a keystream; plaintext XORed with keystream gives ciphertext. Recover the initial state to reproduce the keystream.
2. Step 2Reverse the algorithm
   Once the encryption function is understood, implement the inverse in Python. The binary contains either the encrypted flag or a known plaintext-ciphertext pair from which the key can be derived.
   python

   python3 - <<'EOF'
   # Implement the inverse of the custom cipher found in the binary
   
   encrypted = bytes([...])  # Extract from binary data section
   key = ...  # Key found in binary or derived from known plaintext
   
   # If XOR cipher:
   decrypted = bytes(c ^ key[i % len(key)] for i, c in enumerate(encrypted))
   
   # If substitution cipher:
   # fwd_table = [...]  # From binary
   # inv_table = [0] * 256
   # for i, v in enumerate(fwd_table): inv_table[v] = i
   # decrypted = bytes(inv_table[c] for c in encrypted)
   
   print(decrypted.decode('ascii', errors='replace'))
   EOF

   Copied!
   Learn more

   The key insight is that any invertible transformation can be reversed. For each operation in the forward direction (encrypt), there is a corresponding inverse operation (decrypt) that undoes it:

   • XOR with key K: inverse is XOR with the same key K
   • ADD constant C (mod 256): inverse is SUBTRACT C (mod 256)
   • ROL (rotate left by N bits): inverse is ROR (rotate right by N bits)
   • Lookup in table T: inverse is lookup in the inverse table T^-1

   Inverse table construction. If the binary stores a forward substitution table where index i maps to value v (fwd_table[i] = v), the inverse is built by swapping role: inv_table[v] = i. In Python: inv = [0]*256; [inv.__setitem__(v, i) for i, v in enumerate(fwd)], then plaintext = bytes(inv[c] for c in ciphertext).

   Find the key from a known pair. If the binary echoes back ciphertext for any input, send a known plaintext (e.g., AAAAAAAA) and capture the ciphertext. For a XOR cipher with single-byte key: key = ord('A') ^ ciphertext[0]. For multi-byte rotating keys: key[i] = plaintext[i] ^ ciphertext[i] across one key period. This sidesteps reading the key from disassembly entirely.

   Apply the inverse operations in the reverse order of the original. If the cipher does A then B then C, decryption does C^-1 then B^-1 then A^-1.

Alternate Solution

Flag

Custom ciphers in CTFs are always reversible by applying inverse operations in reverse order - identify each transformation and implement its mathematical inverse.