# Pseudo Key

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.

# Initial view

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

`pseudo_key = encrypt(key,key)`

This encrypts the key using itself

`print('Ciphertext:',ctxt) print('Pseudo-key:',pseudo_key)`

this prints the result

# Decrypting

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.

## 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 **de**crypt 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 flag

Having the key, we can decode the flag. In order to do this, let's first define the crypted flag and the key used to encrypt it.

```
key = "redpwwwnctf"
public = "z_jjaoo_rljlhr_gauf_twv_shaqzb_ljtyut"
ctxt = "z_jjaoo_rljlhr_gauf_twv_shaqzb_ljtyut"
key = ''.join(key[i % len(key)] for i in range(len(public)+20)).lower()
```

The key is defined in this weird way, defining it so that it is repeated to be as long as the ciphertext:

```
redpwwwnctfredpwwwnctfredpwwwnctfredpwwwnctfredpwwwnctfre
```

We can now decrypt the flag:

```
flag = ""
for i in range(0, len(ctxt)):
if (ctxt[i] != "_"):
a = chr_to_num[ctxt[i]]
b = chr_to_num[key[i]]
c = a - b
if c < 0:
c = (26 + a) - b
flag += num_to_chr[c]
else:
flag += "_"
flag += "}"
```

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).