writeup.md

Writeup for Day23 of DailyCTF by n4m3n1ck

Challenge:

Reverse This Function to get the flag:

def encrypt23(s):
    encrypted = s[0]
    for i in range(1, len(s)):
        encrypted += str(ord(s[i])-ord(s[i-1]))
    return encrypted

Encrypted flag: f6-11620-13-918-2469-11157-94-116-115

What the encryption is doing:

The first letter of the plaintext is set to also be the first letter of the ciphertext. Then, each number in the ciphertext is the difference in ASCII value of the corresponding plaintext character and its previous character.

So, the ASCII value of the second character, s[1], of the plaintext minus the ASCII value of the first character, f, of the plaintext equals 6.

Therefore, 6+ord('f') equals ord(s[1]), so s[1] is chr(108) which is l (lower case L).

To further see this, we can call

print(encrypt23("flag"))

and the output will be f6-116

Solution:

Great, so as long as we figure out the differences of ASCII values given the ciphertext, we can reverse the encryption logic and figure out the plaintext.

So far, we have that the difference between the second and first characters of the plaintext is 6.

Continue reading the ciphertext, we have the difference between the third and second characters of the plaintext is -1...right?

We can check this by printing out ord("a")-ord("l") which actually gives -11.

Ok. This is the main problem. There are numerous ways to interpret or 'break' the ciphertext into a list of numbers (the differences of ASCII values). I'm pretty sure through trial and error, one can eventually figure this out manually, but it's also possible to brute force all valid combinations.

Breaking the ciphertext

Let's just consider this group of the ciphertext 11620 (we'll add the negative in later). There are 5 numbers, in which there are 4 slots for dividers. Each slot either has or does not have a divider, giving us a total of 2 to the 4th power number of possible ways to block this.

To implement this, I used itertools.product to give all the combinations of 0 and 1 for length len(group)-1. Then, I go through each combination and if there's a 1, then a space is inserted into that group of ciphertext, which will act as the divider.

from itertools import product

def str_insert(source_str, insert_str, pos):
    #https://stackoverflow.com/questions/4022827/insert-some-string-into-given-string-at-given-index
    return source_str[:pos] + insert_str + source_str[pos:]

def enumerate_groupings(group):
    """
    For a group with N number of elements, there are N-1 slots for dividers.
    Each slot either has or does not have a divider, therefore having 2 possibilites.
    The total number of possibilites becomes 2**(N-1)
    """
    leading_negative=False
    if group[0]=="-":
        leading_negative=True
        group=group[1:]

    inital_group=group
    groupings=[]
    for dividers in [''.join(p) for p in product('10', repeat=(len(group)-1))]:
        #https://stackoverflow.com/questions/30442808/create-list-of-binary-strings-python
        group=inital_group
        index_acc=0
        for i,divider in enumerate(dividers):
            if divider=="1":
                group=str_insert(group," ",i+1+index_acc)
                index_acc+=1

        if leading_negative:
            group="-"+group

        groupings.append(group)

    return groupings

Of course, if that negative sign is detected, then the program will remember that, strip that negative character temporarily, and then add it in as the last step after all 'dividers' have been inserted.

Putting it all together

The above code just takes care of one group of the ciphertext. It is up to the main program to create the groups, send them in, and then combine the 'divided' groupings together using yet again itertools.product into a grand list of numbers, representing the differences of ASCII values.

def decrypt23(e):
    decrypted=[]
    groups=e[1:].split("-")
    for i in range(1,len(groups)):
        groups[i]="-"+groups[i]

    for grouping in list(product(*[enumerate_groupings(group) for group in groups])):
        decrypt=e[0]
        int_grouping=list(map(int,[n for n in " ".join(grouping).split(" ")])) #converts all the string numbers to int.
        for i in range(len(int_grouping)):
            plain_ord=ord(decrypt[i])+int_grouping[i]
            if plain_ord not in range(33,126+1): #Ditch results that are outside of the printable ASCII range.
                break
            decrypt+=chr(plain_ord)
        else:
            decrypted.append(decrypt) #only append qualified ones (the 'break' didn't happen)

    return decrypted

print(decrypt23("f6-11620-13-918-2469-11157-94-116-115"))

Comments...

See complete code at solve.py

I apologize for the one-liners and possibly overly complicated and inefficient logic. If you have any comments, improvements, and feedback, I'd love to hear them!