Cover Image

CAF 2023 - Tower of Encryption

✍️ Valentin Lobstein  | 

Dans cet article, nous allons explorer le déroulement pas à pas (walkthrough) du challenge Cryptographie ‘Tower of Encryption’ proposé lors du CTF Cyber Africa Forum 2023.

Nous avons un fichier challenge_file.txt qui contient la donnée suivante:

JJFEMRKNKJFU4S2KIZKTIUZSJNEVUS2UJFKVUU2KJZCVMVKTGJKUURSLKZKVKMSLJJNEGVSNKZFVIR2KJRCVOVCTJRFVUS2WJNGVGSKKJJDEKR2WKNHEWWSGKZFVGS2PJFJEGVSLKZBVISSWIVLE2USDK5EVMSKUIVJTES2KJJCEKS2TJNLUUTSHIVLVOU2HJNNEKVSFJVJUYSSGJJCUOVSTJRFVESSVLFJVGU2JLJGEKS2VJJJUWNKGIZGVGS2VJFLEUVCFKMZEYSSKINCUWUZSKRFE4TCVKVKFGSCJKZGFMS2VGJEEUTSOIVEVMU2IJNGVURSBKNJUOSSKINLE6VSTKRFEERSWIVJVGVSMIZFFMR2WGJFEYSSHIVFU2U2WJJFEUVKXJZFUOSKVGJDEKTKTLBFEKMSVKVLEGRSLJZFFKUKTGIZESUSLKVLVKWSTJNHEIVKVKNJVMSZVJNDEOU2LJJFVUR2GJVJDEVSHJJCUKVKUKNHUSVSGKZGVKMSHJJFEYRKVKZFVUS2OJJKVOU2TJNEU4TCFGZLFGVCKJZDFIS2SKNLUWTSMKZDVEMSLJFNEMRSNKIZFKR2KIZCVSU2TJBEVMRSVGJKTEV2KJJDEKVKWJNMEUWSGKVHVGSZSJE2UYRKPKZFFGS22IZCU2VCDIZFVMTCFI5JFGTCKKZHEKS2WGJKUSTSGKVJVMU2EJNLEYVSLK5JVISSOJRCU2USKKVFVEQSWJVJVUVSKJZCEKT2VKJJUUSSGKZKVEMSHJJLEURCFKZBU2SSKIZDEWVSLKNFU4SCVKNLFGR2LLJDVMS2NKNFEUSSIIVHVMU2WJNFEMRSPKMZE6SK2IRCTEVJSKREU4RKVGRKEGRSHLJGEMR2WINGEWSSEIZFVES2TJNHEYVKTKZJUWS22IRLE2VJSJZFEMTSFJVJFGTSLJFNEMR2SGJFUSWSDKZJVKMSUJJBEKVSNKJJVOSJVI5LEOVRSJNFFURKFJNJDEU2KJZGUKVKXKNDUWVSIKZDU2U2YJJCTEVKZKJFUYS2SIZLESVCDINEVUQ2VK5KEWVCLLJDUKTKUINDEWNKMKVDVIQ2LJRFEIRKNKMZFMSSOJNCU6U2LGJEVMSSWI5KTERKKJZGEKWKWKNGEWNKKKZEVGU2OI5FEWVKTKZJUYS22IZKTIU2TK5FFMSSWKVLFGS2KLJBUKS2UGJLEOSSHIVKVGU2HJNNEWVSFJVJUQSSKJRCVKVSLLBFVUSSVKFJVGS2JJJGEKV2WKNGEWTSGKU2FEU2WJNHEYRSHKNBUYTCKIRLE2UJSKZDUUS2VKVJVGSKJKZBVMRKTGJHUUTSGIVCVMS22JNHEEVSNKIZDESSOINCUWVKDJNDVMRKGJNIEUNKIKU3FIMSQJE6Q====

A vu d’oeil nous pouvons remarquer que la chaîne de caractère possède uniquement des majuscules et ==== à la fin ce qui me donne déjà l’hypothèse que cette chaîne est encodée en base32.

En allant sur Cyberchef, je décide de déchiffrer 8 fois le base32, puisque c’est un enchaînement d’encodage.

J’obtiens ceci: JAH_{I0Y_F4U_H4EU3H_WO3_W0TVH}

Ça ressemble étrangement au format du flag. Et on dirai qu’une subtitution est appliquée sur la chaine.

Première solution (Non prévue sur ce challenge):

Je décide de créer un script python qui va proposer des solutions potentielles à partir du préfixe 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()

  • decrypt_vigenere_cipher_partial(text, key): Cette fonction a été réécrite pour déchiffrer partiellement une chaîne de texte chiffrée avec le chiffre de Vigenère en utilisant la clé donnée. Le déchiffrement est effectué seulement sur les caractères dont la position correspond à la longueur de la clé partielle fournie.

  • find_key_recursive(partial_key, max_key_length, found_decryptions): Cette fonction effectue un parcours récursif pour générer toutes les combinaisons possibles de clés en se basant sur la clé partielle donnée. Cette clé partielle est initialement vide et provient de la fonction main().

  • La fonction find_key_recursive() fonctionne de la manière suivante :

    • Elle déchiffre partiellement la chaîne given_string en utilisant la clé partielle fournie et stocke le résultat dans partial_decryption.
    • Si partial_decryption commence par le motif recherché et n’est pas déjà présent dans la liste found_decryptions, la fonction affiche la clé partielle et le déchiffrement partiel, ajoute le déchiffrement partiel à la liste found_decryptions et termine le programme.
    • Si la longueur de la clé partielle est inférieure à max_key_length, la fonction parcourt récursivement toutes les combinaisons possibles de clés en ajoutant un caractère ASCII majuscule à la fin de la clé partielle actuelle.

  • main(): Cette fonction sert de point d’entrée pour le programme. Elle initialise les variables max_key_length (longueur maximale de la clé) et found_decryptions (liste des déchiffrements déjà trouvés), puis appelle la fonction find_key_recursive() avec une clé partielle vide pour chaque longueur de clé possible, de 1 à max_key_length.

Voici le résultat que nous obtenons lors de son éxécution:

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

Généralement les flag ont des significations, et là c’est absolument illisible même si le préfixe y est.

Je me rend à nouveau sur Cyberchef et je me met à tatonner des mots commençant par HAC comme HACK, ça me donne de meilleurs résultats, puis j’essaies HACKED, en utilisant cette clé, on obtient enfin un résultat concluant:

Le flag est : CAF_{Y0U_C4N_H4CK3D_TH3_W0RLD}

Deuxième solution:

Après avoir obtenu le flag, je remarque que j’avais oublié d’exploiter un autre fichier du challenge key_file.txt qu contient la donnée suivante:

n = 1000000016000000063 
e = 23
c = 471055156725181012

Ça ressemble méchamment à des valeurs utilisées pour du chiffrement RSA.

La vulnérabilité exploitée ici est la factorisation d’un grand nombre en utilisant une méthode de factorisation classique. Dans ce cas, le nombre est n = p*q, où p et q sont des nombres premiers très grands et inconnus. Si l’on parvient à factoriser n en ses facteurs premiers p et q, on peut facilement calculer la clé privée d et déchiffrer le message c.

Dans cet exemple, nous avons factorisé n en utilisant la fonction factorint() de la bibliothèque sympy. Ensuite, nous avons calculé la valeur de phi_n, qui est la fonction d’Euler de n = (p-1)*(q-1). Nous avons ensuite calculé la clé privée d en utilisant la fonction mod_inverse() de la bibliothèque sympy (qui au passage utilise la librairie C msieve, beaucoup utilisée en CTF.).

Enfin, nous avons utilisé la fonction pow() de Python pour déchiffrer le message c en utilisant la clé privée d et le modulo n.

Voici le code complet en Python pour déchiffrer le 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("Message déchiffré :", m)

En éxécutant ce code:

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

On obtient la clé hacked comme dans la première solution.

Comme la première solution, on déchiffre avec Cyberchef le flag partiel avec la clé hacked:

Le flag est : CAF_{Y0U_C4N_H4CK3D_TH3_W0RLD}