X Marked the Spot (crypto)

A perfect first challenge for beginners. Who said pirates can't ride trains...

48B

ct

248B

public.py

from itertools import cycle

flag = b"uiuctf{????????????????????????????????????????}"
# len(flag) = 48
key  = b"????????"
# len(key) = 8
ct = bytes(x ^ y for x, y in zip(flag, cycle(key)))

with open("ct", "wb") as ct_file:
    ct_file.write(ct)

We are given the above encryption code, along with the produced ciphertext. Each character in the flag is XOR'ed with a character in the key. Since the length of the flag is 48 while the length of the key is 8, the key is cycled through 6 times.

Notice that the first 7 characters of the flag are known, along with the last character of the flag. The first 7 characters of the flag would be XOR'ed with the first 7 characters of the key, while the last character of the flag would be XOR'ed with the last character of the key.

Let $k_i$ be bit $i$ in the key, $p_i$be a bit in the plaintext, and $c_i$ be a bit in the ciphertext. A key property of XOR is that if $p_i \oplus k_i = c_i$, then $p_i \oplus c_i = k_i$. Therefore if we know the characters in the plaintext and ciphertext at an index $i$, we can perform an XOR operation between them to obtain the $i$-th character in the key, $k_i$.

To retrieve the first 7 characters of the key, we XOR the first 7 characters of the plaintext with the first 7 characters of the ciphertext. To retrieve the last character of the key, we XOR the last character of the plaintext with the last character of the ciphertext. Once we have retrieved the key, we XOR it with the ciphertext to retrieve the plaintext!

from itertools import cycle

with open("ct", "rb") as ct_file:
    data = ct_file.read()
assert len(data) == 48
# len(flag) = 48
flag_temp = b"uiuctf{}"
# retrieve key by XORing first 7 chars of pt and ct, and XORing their last char
key = bytes(x ^ y for x, y in zip(flag_temp, data[:7] + data[-1].to_bytes(1, "little")))
assert len(key) == 8
print(key)
# len(key) = 8
flag = b"uiuctf{"
for j in range(7, 48):
    flag += (data[j] ^ key[j % 8]).to_bytes(1, "little")
assert len(flag) == 48
print(flag) # uiuctf{n0t_ju5t_th3_st4rt_but_4l50_th3_3nd!!!!!}