GreyCTF: a little XOR, a lot of insight

This is an illustrative practice write-up with a toy challenge, rather than a report of a specific GreyCTF problem or result.

The best CTF problems leave you with a better question than the one you started with. Here, that question is simple: what does it mean for a cipher to hide information?

Start with the operation

Suppose a message is encrypted by XORing every byte with the same one-byte key. XOR is its own inverse, so applying the key twice recovers the original message:

c_i = m_i \oplus k \qquad\Longrightarrow\qquad m_i = c_i \oplus k

The operation is reversible, but reversibility alone doesn’t make a cipher secure. The size of the key space matters.

A small, reproducible experiment

An eight-bit key has only $2^8 = 256$ possible values. We can try every one and check for a recognizable practice flag prefix.

def xor_bytes(data: bytes, key: int) -> bytes:
    return bytes(byte ^ key for byte in data)


# A self-contained toy ciphertext, not a real competition flag.
ciphertext = bytes.fromhex("4d474a4c707f62657254606e7278546a796e5465647f54646076")

for key in range(256):
    candidate = xor_bytes(ciphertext, key)
    if candidate.startswith(b"FLAG{"):
        print(f"key = {key:#04x}")
        print(candidate.decode("utf-8"))

The script prints key = 0x0b and FLAG{tiny_keys_are_not_ok}. A known prefix makes checking candidates convenient; it is not the underlying weakness. The tiny key space is.

Put a number on the work

For a message of $n$ bytes and a key of $b$ bits, exhaustive search takes approximately:

T(n,b) = \mathcal{O}\!\left(n\,2^b\right)

If each key is equally likely and keys are tested without replacement, the expected number of trials is:

\mathbb{E}[N] = \frac{2^b + 1}{2}

For $b=8$ , that is just $128.5$ trials on average. The distinction between a clever-looking operation and a secure construction becomes very concrete.

What I’m taking away

Identify the primitive before reaching for a tool.
Estimate the search space before optimizing the search.
Make examples reproducible so the explanation can be tested.

Small experiments are useful. They turn an abstract security claim into something you can inspect, run, and understand.