- Initial view
- Decrypting
- The key
- The flag
So, this is a fairly long writeup for the pseudo-key challenge from the redpwnctf. It is ment to not only show the solution of the challenge, but also how to approach such a challenge. The challenge is based on the concept of Modular Arithmetics.
So, the first thing to do is to view the data given. In this case, we get two files: pseudo-key-output.txt and pseudo-key.py. This is fairly obvious, the pseudo-key-output.txt is the output generated by the pseudo-key.py file. One of the first things we should do, is to understand how this all works, so let's look into the code:
#!/usr/bin/env python3
from string import ascii_lowercase
chr_to_num = {c: i for i, c in enumerate(ascii_lowercase)}
num_to_chr = {i: c for i, c in enumerate(ascii_lowercase)}
def encrypt(ptxt, key):
ptxt = ptxt.lower()
key = ''.join(key[i % len(key)] for i in range(len(ptxt))).lower()
ctxt = ''
for i in range(len(ptxt)):
if ptxt[i] == '_':
ctxt += '_'
continue
x = chr_to_num[ptxt[i]]
y = chr_to_num[key[i]]
ctxt += num_to_chr[(x + y) % 26]
return ctxt
with open('flag.txt') as f, open('key.txt') as k:
flag = f.read()
key = k.read()
ptxt = flag[5:-1]
ctxt = encrypt(ptxt,key)
pseudo_key = encrypt(key,key)
print('Ciphertext:',ctxt)
print('Pseudo-key:',pseudo_key)
In order to look at the code and understand this, let's go through it line for line:
#!/usr/bin/env python3
The shebang) indicating that this is ment to be executed using python3.
from string import ascii_lowercase
import the asci_lowercase character set (abcdefghijklmnopqrstuvwxyz)
chr_to_num = {c: i for i, c in enumerate(ascii_lowercase)}
num_to_chr = {i: c for i, c in enumerate(ascii_lowercase)}
maps for char to number (0 → a, 1 → b) and number to char (a → 0, b → 1), this is useful for the crypto function later on.
def encrypt(ptxt, key):
ptxt = ptxt.lower()
key = ''.join(key[i % len(key)] for i in range(len(ptxt))).lower()
ctxt = ''
for i in range(len(ptxt)):
if ptxt[i] == '_':
ctxt += '_'
continue
x = chr_to_num[ptxt[i]]
y = chr_to_num[key[i]]
ctxt += num_to_chr[(x + y) % 26]
return ctxt
This is the encryption function, this takes some plaintext (ptxt) and a key (key), returning some ciphertext. Let's look at this line by line:
def encrypt(ptxt, key):
The function signature
ptxt = ptxt.lower()
Convert the given plaintext to lowercase
key = ''.join(key[i % len(key)] for i in range(len(ptxt))).lower()
Wrap the key, this means that if the plaintext is 8 bytes long (for example "12345678") and the key 3 bytes long ("key"), the key get's wrapped and gets repeated to be as long as the plaintext: ("keykeyke").
ctxt = ''
Define a ciphertext, this will be filled in the following loop
for i in range(len(ptxt)):
if ptxt[i] == '_':
ctxt += '_'
continue
x = chr_to_num[ptxt[i]]
y = chr_to_num[key[i]]
ctxt += num_to_chr[(x + y) % 26]
return ctxt
Iterate over all the characters in the plaintext, this skips over underscores (_), converts the n'th char from the plaintext and from the key to a number, adds the numbers and adds the chr representation of the result modulo 26 to the ciphertext (Don't worry if this sound's weird, I'll get to this in detail further down).
with open('flag.txt') as f, open('key.txt') as k:
flag = f.read()
key = k.read()
This imports data from two files: flag.txt and key.txt. These contain the values we want to get, they get encrypted further down.
ptxt = flag[5:-1]
The plaintext get's defined as some chars in the flag, to be more precise, the 5th char until the second last char.
ctxt = encrypt(ptxt,key)
This encrypts the plaintext using the key as a key
Now that we've got a basic understanding of how the given code is built up, let's define a goal. The overall goal we'd like to reach, is to get the plaintext of flag and the key. In order to do this, let's start by extracting the key.
First, let's decrypt the key. The encryption works like this: encryption(key, key), so we known that the n'th character in the key ist added to the n'th character in the key and then taken modulo 26. As we want to decrypt this, we want to reverse the process of the encryption.
x = chr_to_num[ptxt[i]]
y = chr_to_num[key[i]]
ctxt += num_to_chr[(x + y) % 26]
So we start at the last step, num_to_chr. Let's convert the crypted key iigesssaemk into it's numerical representation:
from string import ascii_lowercase
chr_to_num = {c: i for i, c in enumerate(ascii_lowercase)}
num_to_chr = {i: c for i, c in enumerate(ascii_lowercase)}
cipher_key = "iigesssaemk"
for i in range(0, len(cipher_key)):
print(chr_to_num[cipher_key[i]])
8
8
6
4
18
18
18
0
4
12
10
Next step, the actual crypto, the n'th numerical representation of the key get's added to the n'th numerical representation of the key and all of this is taken modulo 26, let's use an example to get a better understanding of this. Let's say we've got the character u in the key, the process of encryption works like this:
u → 20 → 20 + 20 = 40 → 40 % 26 = 14 → 14
in order to reverse this, we need to find a value, that when added to itself and taken modulo 26 equals 14. We can try to brute force this:
a = 14
for j in range(0, 26):
b = (j * 26) + a
if ((b/2) < 26):
print(b/2, end="")
print("")
7.0
20.0
We search for a multiple of 26 that when added to 14 and divided by two is smaller than 26 (the target range (a-z)).
As you can see above, we get two results, ((7+7) % 26) = 14 and ((20+20) % 26) = 14. This is one of the problems we encounter, and in this problem lies the "pseudo" security of this "encryption". With values that are big enough, this wouldn't be a problem, as the resulting values wouldn't be so many, but with the limited space we've got, we only get a few results.
We can now proceed and brute-force all possible values for all values in our ciphertext:
from string import ascii_lowercase
chr_to_num = {c: i for i, c in enumerate(ascii_lowercase)}
num_to_chr = {i: c for i, c in enumerate(ascii_lowercase)}
pseukey = "iigesssaemk"
for i in range(0, len(pseukey)):
print(pseukey[i], end=" → ")
a = chr_to_num[pseukey[i]]
for j in range(0, 10):
b = (j * 26) + a
if ((b/2) < 26):
print(b, end=", ")
print(num_to_chr[int(b/2)], end=", ")
print("")
i → 8, e, 34, r,
i → 8, e, 34, r,
g → 6, d, 32, q,
e → 4, c, 30, p,
s → 18, j, 44, w,
s → 18, j, 44, w,
s → 18, j, 44, w,
a → 0, a, 26, n,
e → 4, c, 30, p,
m → 12, g, 38, t,
k → 10, f, 36, s,
Here, we see what output might correspond to a given input. There literally is no way (that I know), that can be used to obtain the exact values needed, but we can try to see what we can get from this. In order to do this, let's try to get something out:
0 e, r <
1 > e, r
2 > d, q
3 c, p <
4 j, w <
5 j, w <
6 j, w <
7 a, n <
8 > c, p
9 g, t <
10 > f, s
the CTF this challenge was hosted in was redpwnctf, so this is one of the strings that seemed likely. If you don't find such options or don't find a string, try searching for ctf. This can be found here, starting at index 8. The next index (9) coult be g or t and the next f or s, so we could build the string ctf. The rest (redpwwwwnctf) can be found by trial and error.
So the resulting key is redpwwwnctf
The overall process is the same as with the key: For each character in the ciphertext, if the character is not an underscore, the values of the character at the respective indices in the ciphertext and the key are subtracted from each other, if this is less than zero, we add 26 (one modulo "round"). The result can be added to the flag string, so in the end we can print the flag:
flag{i_guess_pseudo_keys_are_pseudo_secure}
Overall, you should now have a basic understanding on how this works, if stuff is still unclear, try to repeat the process step by step, writing it down and try to visualize exactly how everything is done. If that doesn't help, find help (for example me, you'll figure out a way to contact me).
