pseudo-key

This is my solution to the redpwnCTF 2020 cryptography challenge pseudo-key. This is a challenge based on examining some python code and figuring out the encryption and the inherent vulnerability of generating a pseudo key by operating on the key itself.

You are presented with two files – the encryption code (in Python) and a text file containing the ciphertext and a “pseudo-key”. I reproduce the code below as it’s impossible to write a walkthrough without them, but this challenge was created by the good folks at redpwnCTF and you should definitely check out their site for more.

The output text:

Ciphertext: z_jjaoo_rljlhr_gauf_twv_shaqzb_ljtyut
Pseudo-key: iigesssaemk

The Python code, which now includes my reverse engineering notes, and a function of my own devising to decrypt as we try to narrow down the correct key.

#!/usr/bin/env python3

from string import ascii_lowercase

#creates two dictionaries of characters a-z with zero indexed alphabet position
chr_to_num = {c: i for i, c in enumerate(ascii_lowercase)}
num_to_chr = {i: c for i, c in enumerate(ascii_lowercase)}
#print(chr_to_num)
#print(num_to_chr)

def encrypt(ptxt, key):
    ptxt = ptxt.lower()
    #modifies the key to become a repeated string of itself until it is as long as plaintext
    key = ''.join(key[i % len(key)] for i in range(len(ptxt))).lower()
    ctxt = ''
    #iterates through ptext
    for i in range(len(ptxt)):
        #ensures _ in plaintext is still represented by _ in ciphertext
        if ptxt[i] == '_':
            ctxt += '_'
            continue
        #converts each char of ptext to a zero-indexed alphabet position
        x = chr_to_num[ptxt[i]]
        #converts each char of the extended key to a zero indexed alphabet position
        y = chr_to_num[key[i]]
        #generates the ciphertext string with a zero indexed alphabet position based on those of ptext and key.
        ctxt += num_to_chr[(x + y) % 26]
        #output will be a ciphertext string of same length as ptext, and will include _ chars in same positions.
    return ctxt

#my decryptor
def decrypt(ctxt, key):
    ctxt = ctxt.lower()
    ptxt = ''
    for i in range(len(ctxt)):
        if ctxt[i] == '_':
            ptxt += '_'
            continue
        y = chr_to_num[key[(len(key) + i) % len(key)]]
        x = chr_to_num[ctxt[i]]
        diff = x-y
        if (x-y) > 26:
            diff -= 26
        elif (x-y) < 0:
            diff += 26
        ptxt += num_to_chr[diff]
    return ptxt

with open('flag.txt') as f, open('flag.txt') as k:
    flag = f.read()
    key = k.read()

#reads the flag and slices off the formatting flag{}
ptxt = flag[5:-1]

#runs the encryption function on the flag text
ctxt = encrypt(ptxt,key)
#here's the vulnerability; encrypting the key with itself gives us a chance to reverse it!
pseudo_key = encrypt(key,key)

#The following print lines were used to generate the out file, we don't need them 
#print('Ciphertext:',ctxt)
#print('Pseudo-key:',pseudo_key)
print(decrypt('z_jjaoo_rljlhr_gauf_twv_shaqzb_ljtyut', 'redpwwwnctf'))

While reversing the Python code, it occurred to me that if you know the algorithm behind the encryption, anything encoded with itself can be broken. The vulnerability lies in this bit of code:

        x = chr_to_num[ptxt[i]]
        y = chr_to_num[key[i]]
        ctxt += num_to_chr[(x + y) % 26]

The reason it is vulnerable is because if you encrypt the key with itself, ptxt = key, which means that in the above code, x = y and therefore:

(x + y) % 26 = 2x % 26

Let’s turn to the pseudo-key, iigesssaemk.

First we need to break it down into zero index alphabet positions.

i i g e s  s  s  a e m  k 
8 8 6 4 18 18 18 0 4 12 10

The maximum value of x is 25 (the alphabet position of z). Performing modulo on a value of 2x above 25 will also cause collisions. For example, the letter a = 0. The letter n = 13.

Taking our encryption formula (2 * x) % 26
(2 * 0) % 26 = 0 = a when alphabet indexed
(2 * 13) % 26 = 0 = a when alphabet indexed

Therefore, where the key is ‘a’ or ‘n’, the ciphertext will be ‘a’. Similarly, the letter ‘o’ (14) would be encrypted as ‘c'(2), but so would ‘b'(1). Essentially we are compressing a 26 character alphabet into 13 characters (the even numbered characters in a zero indexed alphabet). Let’s see what happens when we try to reverse the pseudo-key, taking the upper characters (add 26 and then half the result).

i   i   g   e   s    s    s    a   e   m    k 
8   8   6   4   18   18   18   0   4   12   10
34  34  32  30  44   44   44   26  30  38   36 #ADD 26
17  17  16  15  22   22   22   13  15  19   18 #DIVIDE BY 2
r   r   q   p   w    w    w    n   p   t    s  #CONVERT TO CHAR

So that gives us one possible key of rrqpwwwnpts. Let’s see what happens when we run that through the decrypt function I wrote, along with the challenge ciphertext.

print(decrypt('z_jjaoo_rljlhr_gauf_twv_shaqzb_ljtyut', 'rrqpwwwnpts'))

>i_tuess_csruqb_keys_aee_cseudo_srchee

Hmm. redpwnCTF flags tend to have a phrase, so we’re not quite there. We can see what looks like a complete word ‘keys’, so that part looks solid. But some of those collisions in our key we need to toggle to our alternative. Remember that the key is repeated for the length of the plain/cipher text, so lets match them up and work out which characters need toggling.

i_tuess_csruqb_keys_aee_cseudo_srchee #CURRENT DECRYPT
rrqpwwwnptsrrqpwwwnptsrrqpwwwnptsrrqp #REPEATED KEY
--*++++--------++++-+*+-*+++++------- #TOGGLE(*) KEEP(+)

Looking at the result, ‘i’ is a word in it’s own right, and we can be somewhat confident that the ‘wwwn’ pattern of the key is correct, due to the word ‘keys’ being seen. Additionally, the challenge is called ‘pseudo’, and we have ‘cseudo’, so the key pattern pwwwn looks good. It’s reasonable to look at what we have and consider that the second word may be ‘guess’, the fifth could be ‘are’ and the sixth, as mentioned, looks like ‘pseudo’. Based on those workings let’s toggle some characters in the key (we will toggle the ones marked * above, and keep those marked + as we think they are correct).

r   r   q   p   w   w   w   n   p   t   s
+   ?   *   +   +   +   +   +   ?   +   *      #status, 1 pass
        g                               k      #pseudo key
        6                               10     #alpha index
        3                               5      #divide by 2
        d                               f      #0 index alpha char
r   r   d   p   w   w   w   n   p   t   f     #next key attempt

Ok so lets put that new key through our decryptor with the ciphertext.

print(decrypt('z_jjaoo_rljlhr_gauf_twv_shaqzb_ljtyut', 'rrdpwwwnptf'))

i_tuess_csruqb_keys_aee_cseudo_srchee     #FIRST KEY DECRYPT
i_guess_cseuqo_keys_are_pseudo_sechre     #SECOND KEY DECRYPT
rrdpwwwnptfrrdpwwwnptfrrdpwwwnptfrrdp     #REPEATED KEY
--++++++*+--*++++++-+++-++++++-+++?++     #TOGGLE(*), KEEP(+)

At this point the flag can probably be guessed; it’s clear that words 1, 2, 4, 5 and 6 are correct. Word 3 looks like it might be pseudo again, and by process of elimination we can work out candidates for another toggle; in fact they are the two we hadn’t quite made a decision on last round.

r   r   d   p   w   w   w   n   p   t   f
+   *   +   +   +   +   +   +   *   +   +      #status, 1 pass
    i                           e              #pseudo key
 chars
    8                           4              #alpha index
    4                           2              #divide by 2
    e                           c              #0 index alpha char
r   e   d   p   w   w   w   n   c   t   f     #next key attempt

D’oh! If only I’d spotted that earlier; redpwwwnctf – it’s a play on the name of the competition! Let’s try running that through the decryptor:

print(decrypt('z_jjaoo_rljlhr_gauf_twv_shaqzb_ljtyut', 'redpwwwnctf'))

>i_guess_pseudo_keys_are_pseudo_secure

Pop! I’m sure my solutions are never the most elegant, but I’m a self declared noob and when you work it out on your own, it’s a great buzz. Just need to remember to wrap that flag before submitting it…..

flag{i_guess_pseudo_keys_are_pseudo_secure}

There we go.