CAF 2023 - Tower of Encryption

In this article, we will explore the step-by-step walkthrough of the Cryptography challenge ‘Tower of Encryption’ presented at the CTF Cyber Africa Forum 2023.

Challenge File

We have a challenge_file.txt file that contains the following data:

JJFEMRKNKJFU4S2KIZKTIUZSJNEVUS2UJFKVUU2KJZCVMVKTGJKUURSLKZKVKMSLJJNEGVSNKZFVIR2KJRCVOVCTJRFVUS2WJNGVGSKKJJDEKR2WKNHEWWSGKZFVGS2PJFJEGVSLKZBVISSWIVLE2USDK5EVMSKUIVJTES2KJJCEKS2TJNLUUTSHIVLVOU2HJNNEKVSFJVJUYSSGJJCUOVSTJRFVESSVLFJVGU2JLJGEKS2VJJJUWNKGIZGVGS2VJFLEUVCFKMZEYSSKINCUWUZSKRFE4TCVKVKFGSCJKZGFMS2VGJEEUTSOIVEVMU2IJNGVURSBKNJUOSSKINLE6VSTKRFEERSWIVJVGVSMIZFFMR2WGJFEYSSHIVFU2U2WJJFEUVKXJZFUOSKVGJDEKTKTLBFEKMSVKVLEGRSLJZFFKUKTGIZESUSLKVLVKWSTJNHEIVKVKNJVMSZVJNDEOU2LJJFVUR2GJVJDEVSHJJCUKVKUKNHUSVSGKZGVKMSHJJFEYRKVKZFVUS2OJJKVOU2TJNEU4TCFGZLFGVCKJZDFIS2SKNLUWTSMKZDVEMSLJFNEMRSNKIZFKR2KIZCVSU2TJBEVMRSVGJKTEV2KJJDEKVKWJNMEUWSGKVHVGSZSJE2UYRKPKZFFGS22IZCU2VCDIZFVMTCFI5JFGTCKKZHEKS2WGJKUSTSGKVJVMU2EJNLEYVSLK5JVISSOJRCU2USKKVFVEQSWJVJVUVSKJZCEKT2VKJJUUSSGKZKVEMSHJJLEURCFKZBU2SSKIZDEWVSLKNFU4SCVKNLFGR2LLJDVMS2NKNFEUSSIIVHVMU2WJNFEMRSPKMZE6SK2IRCTEVJSKREU4RKVGRKEGRSHLJGEMR2WINGEWSSEIZFVES2TJNHEYVKTKZJUWS22IRLE2VJSJZFEMTSFJVJFGTSLJFNEMR2SGJFUSWSDKZJVKMSUJJBEKVSNKJJVOSJVI5LEOVRSJNFFURKFJNJDEU2KJZGUKVKXKNDUWVSIKZDU2U2YJJCTEVKZKJFUYS2SIZLESVCDINEVUQ2VK5KEWVCLLJDUKTKUINDEWNKMKVDVIQ2LJRFEIRKNKMZFMSSOJNCU6U2LGJEVMSSWI5KTERKKJZGEKWKWKNGEWNKKKZEVGU2OI5FEWVKTKZJUYS22IZKTIU2TK5FFMSSWKVLFGS2KLJBUKS2UGJLEOSSHIVKVGU2HJNNEWVSFJVJUQSSKJRCVKVSLLBFVUSSVKFJVGS2JJJGEKV2WKNGEWTSGKU2FEU2WJNHEYRSHKNBUYTCKIRLE2UJSKZDUUS2VKVJVGSKJKZBVMRKTGJHUUTSGIVCVMS22JNHEEVSNKIZDESSOINCUWVKDJNDVMRKGJNIEUNKIKU3FIMSQJE6Q: ===

Initial Analysis

At first glance, we can notice that the character string has only uppercase letters and ==== at the end, which already gives me the hypothesis that this string is encoded in base32.

By going to CyberChef , I decide to decode base32 8 times, since it’s a chain of encodings.

I get this: JAH_{I0Y_F4U_H4EU3H_WO3_W0TVH}

This strangely resembles the flag format. And it looks like a substitution is applied to the string.

Solution 1 (Not intended for this challenge):

Python Script for Vigenère Cipher

I decide to create a Python script that will propose potential solutions from the prefix CAF_{:

import sys
import string

given_string: "JAH_{I0Y_F4U_H4EU3H_WO3_W0TVH}"
pattern: "CAF_{"


def decrypt_vigenere_cipher_partial(text, key):
    decrypted_text: []
    key_length: len(key)
    for i, char in enumerate(text):
        if i < key_length:
            if char.isalpha():
                shift: ord(key[i]) - ord('A')
                if char.islower():
                    decrypted_text.append(chr((ord(char) - ord('a') - shift) % 26 + ord('a')))
                else:
                    decrypted_text.append(chr((ord(char) - ord('A') - shift) % 26 + ord('A')))
            else:
                decrypted_text.append(char)
        else:
            decrypted_text.append(char)
    return "".join(decrypted_text)


def find_key_recursive(partial_key, max_key_length, found_decryptions):
    partial_decryption: decrypt_vigenere_cipher_partial(given_string, partial_key)

    if partial_decryption.startswith(pattern) and partial_decryption not in found_decryptions:
        print(f"Found partial key: {partial_key}, decryption: {partial_decryption}")
        found_decryptions.append(partial_decryption)
        sys.exit(0)

    if len(partial_key) < max_key_length:
        for next_char in string.ascii_uppercase:
            find_key_recursive(partial_key + next_char, max_key_length, found_decryptions)


def main():
    max_key_length: 6
    found_decryptions: []
    for key_length in range(1, max_key_length + 1):
        find_key_recursive("", key_length, found_decryptions)


if __name__ == "__main__":
    main()

Code Explanation

• decrypt_vigenere_cipher_partial(text, key): This function has been rewritten to partially decrypt a text string encrypted with the Vigenère cipher using the given key. Decryption is performed only on characters whose position corresponds to the length of the provided partial key.

• find_key_recursive(partial_key, max_key_length, found_decryptions): This function performs a recursive traversal to generate all possible key combinations based on the given partial key. This partial key is initially empty and comes from the main() function.

• The find_key_recursive() function works as follows:

  • It partially decrypts the given_string using the provided partial key and stores the result in partial_decryption.
  • If partial_decryption starts with the searched pattern and is not already present in the found_decryptions list, the function displays the partial key and partial decryption, adds the partial decryption to the found_decryptions list, and terminates the program.
  • If the length of the partial key is less than max_key_length, the function recursively traverses all possible key combinations by adding an uppercase ASCII character to the end of the current partial key.

• main(): This function serves as the entry point for the program. It initializes the variables max_key_length (maximum key length) and found_decryptions (list of already found decryptions), then calls the find_key_recursive() function with an empty partial key for each possible key length, from 1 to max_key_length.

Execution Result

Here is the result we get when executing it:

$ python flag.py 
Found partial key: HAC, decryption: CAF_{I0Y_F4U_H4EU3H_WO3_W0TVH}

Generally, flags have meanings, and here it’s absolutely unreadable even though the prefix is there.

I go back to CyberChef and start trying words starting with HAC like HACK, which gives me better results, then I try HACKED. Using this key, we finally get a conclusive result:

The flag is: CAF_{Y0U_C4N_H4CK3D_TH3_W0RLD}

Solution 2:

RSA Key File

After obtaining the flag, I notice that I had forgotten to exploit another challenge file key_file.txt which contains the following data:

n: 1000000016000000063 
e: 23
c: 471055156725181012

This strongly resembles values used for RSA encryption.

RSA Decryption Process

The vulnerability exploited here is the factorization of a large number using a classical factorization method. In this case, the number is n = p*q, where p and q are very large and unknown prime numbers. If we manage to factorize n into its prime factors p and q, we can easily calculate the private key d and decrypt the message c.

In this example, we factorized n using the factorint() function from the sympy library. Then, we calculated the value of phi_n, which is Euler’s totient function of n = (p-1)*(q-1). We then calculated the private key d using the mod_inverse() function from the sympy library (which by the way uses the C library msieve, widely used in CTF).

Finally, we used Python’s pow() function to decrypt the message c using the private key d and the modulo n.

Python Implementation

Here is the complete Python code to decrypt the message:

from sympy import factorint, mod_inverse

n: 1000000016000000063
e: 23
c: 471055156725181012
m: ''

factors: factorint(n)
p: list(factors.keys())[0]
q: int(n / p)

phi_n: (p - 1) * (q - 1)

d: mod_inverse(e, phi_n)

m_int: pow(c, d, n)

while m_int > 0:
    m += chr(m_int % 1000)
    m_int //= 1000

m: m[::-1] 

print("p =", p)
print("q =", q)
print("d =", d)
print("Decrypted message:", m)

Execution Result

By executing this code:

$ python flag.py 
p: 1000000007
q: 1000000009
d: 130434784434782615
Message déchiffré : hacked

We get the key hacked as in the first solution.

As in the first solution, we decrypt the partial flag with CyberChef using the key hacked:

The flag is: CAF_{Y0U_C4N_H4CK3D_TH3_W0RLD}