#
**Substitution Ciphers**

The second crypto session of **CTF101** focused on symmetric encryption, and more specifically substitution ciphers.

## stellar-caesar

The first challenge was a simple Caesar Cipher, as hinted by the name. The ciphertext is `vy{vkliwlqj_olnh_wkh_dqflhqw_urpdqv}`

and just putting this in CyberChef with ROT13 shifted by -3 returns the flag: `sv{shifting_like_the_ancient_romans}`

. The shift of -3 could be either computed by knowing that the flag begins with `sv`

, or guessed, since it was the one supposedly used by Caesar, or even bruteforced easily.

## trial-and-error

The second challenge was the python version of the Caesar Cipher: a single byte XOR. The idea here is to simply bruteforce all the possible keys, since there are only 256 possibilities to chose one byte, and then find a way to detect when the output is correct (checking by hand 256 possibilities is still doable, but automating it is much more helpful for the next challenge and way less boring). First of all, we need a function to xor a key against our plaintext. We can use the `xor`

function from `pwntools`

or write a simple helper function like this:

1
2
3

def single_key_xor(data, k):
out = bytes([x ^ k for x in data])
return out

Here `k`

is a number, which will simplify the next step. The simple way to check for correct output is to look for the presence of `b'sv{'`

in the output.

1
2
3
4
5
6
7
8

with open('out.xor', 'rb') as fh:
data = fh.read()
for k in range(256):
guess = single_key_xor(data, k)
if b'sv{' in guess:
print(guess)
print(f'{k = }')

In the decrypted text, with `k=105`

, we can find the flag: `sv{t1m3s_4r3_ch4ng1ng}`

. Other strategies include checking that the most frequent characters in the output are either `e`

or a whitespace, the two most common characters in written English, or checking that the whole output consists in ASCII characters. This is an example of the former, while we will see the latter in the next challenge:

1
2
3
4
5
6
7
8
9
10
11

for k in range(256):
guess = single_key_xor(data, k)
e_count = guess.count(b'e')
space_count = guess.count(b' ')
max_count = max([ guess.count(bytes([i])) for i in range(256) ])
if e_count == max_count or space_count == max_count:
print(f'{k = }')
print(f'{guess = }')

## pygenere

Once again the name tells us a lot about the challenge: we face a *Vigenere Cipher* in its python version, i.e. a multi-key xor. Unlike the previous exercise, we cannot bruteforce the keys: the number of possible keys of length \(s\) is \(256^s\), so we cannot hope to go much further than maybe 3 characters. We need to come up with a smarter method. There are three main things to observe:

- if we knew the key length, we did not have to bruteforce all the possible keys, but we could build the key character by character. Let say the length is three: then the first byte of the plaintext is xored with the first byte of the key, the second with the second, the third with the third, but then the fourth with the first and so on. So if we split the ciphertext in three groups, each one that got xored against a different byte of the key, we have three parallel instances of single key xor that we can target. This drastically reduces the bruteforce cost from \(256^3\) to \(3 \times 256\), which is very feasible;
- what we lose with this approach is the adjacence of the characters: we cannot hope to find the flag in any of the groups, since if
`s`

goes in the first group,`v`

goes in the second and`{`

in the third one; however, the frequency of the characters will stay more or less unchanged, and hence we can still look for`e`

and whitespace as the most frequent characters or rule out keys that produce non ASCII characters; - finally, notice that we made one big assumption: all that works if we know the key length, which we do not. There exist some smart techniques to guess the key length from the text (e.g. coincidence indexes) but they are usually not actually needed, especially if the key is not too long and the first two steps are implemented properly. What we can do instead is to bruteforce the key length and see how many good keys we get for each possible length; we will see that in this case for the wrong key length we authomatically filter all the possible keys.

Now letâ€™s implement it. First we need a function that tells us which single byte keys are good for a group of characters. The simplest option is to filter out all the keys that result in non ASCII plaintext, and return all the others.

1
2
3
4
5
6
7
8
9

from pwn import xor
def good_keys(b):
good = []
for k in range(256):
guess = xor(b, k)
# Is only chars
if min(guess.replace(b'\n', b'')) >= 32 and max(guess) <= 126:
good.append(k)
return good

Now the idea is that given a keylength `l`

we split the ciphertext in `n`

chunk, and for each of those we compute the good keys. We need two helper functions, the first that produces the chunks, and the second one that given a list of possibilities for each characters combines them all together (probably both can be done in one line or so with `itertools`

, but none of this function will be the bottleneck of our approach and having handwritten helpers allows for extra flexibility in this kind of challenges).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def bytes_to_chunks(b, n_chunks):
chunks = [[] for _ in range(n_chunks)]
for i in range(len(b)):
chunks[i % n_chunks].append(b[i])
return [bytes(c) for c in chunks]
def generate_all_keys(poss):
all_comb = []
count = [0 for _ in poss]
while True:
# Check if the count is valid
for i in range(len(count)-1, 0, -1):
if count[i] >= len(poss[i]):
count[i] = 0
count[i-1] += 1
# If the first one is out of range return
if count[0] >= len(poss[0]):
return all_comb
# Generate a key
k = bytes([poss[i][count[i]] for i in range(len(poss))])
all_comb.append(k)
# Increment
count[-1] += 1

Now, the last part: for each possible key length we can generate all the possible *good keys*. However, these can still be a lot (even with stricter constraint on what a good key is). So we need another good criterion to filter among the good keys to find the correct one. But now we are talking about full keys, so for each key we can recover the generated plaintext. There we can look for the flag, and discard all the keys that does not contain one. Since the flag starts with `sv{`

and ends with `}`

, we can even focus only on the part of the ciphertext contained among those characters, reducing a lot our manual work.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def test_key(data, k):
plain = xor(data, k)
if not b'sv{' in plain:
return False
idx = plain.index(b'sv{')
if not b'}' in plain[idx:]:
return False
end_idx = idx + plain[idx:].index(b'}')
return plain[idx:end_idx+1]
data = open('out.xor', 'rb').read()
for keylen in range(1, 10):
print(f'{keylen = }')
chunks = bytes_to_chunks(data, keylen)
good = [good_keys(c) for c in chunks]
all_keys = generate_all_keys(good)
print(f'Found {len(all_keys)} possible keys')
for k in all_keys:
is_ok = test_key(data, k)
if is_ok:
print('----------------------')
print(f'{k = } --> guess = {is_ok}')

In the end we find 5 possible keys all of length 7, among which only one produce a meaningful result: the key is `stellar`

and the resulting flag is `sv{p0ly4lph4b3t1c_cyph3r_m4st3r!}`

.

Source Code

The source code of the solution is available here