HeroCTF v3 — Crypto Write-up : Yours_truely

Du 23 avril au 25 avril 2021 a eu lieu la troisième édition du HeroCTF (page d’accueil du CTF). Notre équipe a terminé 2ème au classement général (première place au classement étudiant) sur plus de 600 équipes.

Nous allons voir dans ce write-up comment résoudre le challenge “Yours_truely” créé par yarienkiva.

Yours_truely

Pour ce challenge, nous disposons de l’énoncé suivant :

Alice <3 Bob <\3 Eve
nc chall3.heroctf.fr 9000

Nous disposons également d’un script python. En ouvrant un socket vers le serveur sur le port donné, nous pouvons confirmer qu’il s’agit du code présent sur la machine distante.

Au moment de la connexion, après un délai de quelques secondes, nous sommes accueillis par ce message :

➜  ~ nc chall3.heroctf.fr 9000
Bob my darling is that you ? It's me, Alice !
To prove you're the one I'm talking to, send me "the_proof_of_your_love".
Beware, I'll only accept it if it's signed with the (private) key to my heart.
I know that your love for me is strong enough to factor a 4096bit modulus <3
public modulus  : 10654903999976671248790103138047114532135472694164240310853002642558396626157432402557412210007196405546786987125304372130206299046667985501155213610015742825582067380042190863574708357651902491708163041881240169443955583802298763919337140809369971906173579942144847592742920964984673512503114801243611914579649266502166938358547138808694464750098743956878248124306283639309471126888419260141476059224761886129733069121462989280018178805292091155082665112959198838126547109039026528300141695674352978933245998982788227619227718304656280059018314352551503365259402986987309068242141018194194456331246920557404237174577
public exponent : 65537
input >>

Le script nous demande de prouver notre identité en lui retournant une phrase signée. Le message est accompagné d’un modulo et d’un exposant. Nous pouvons en déduire qu’il est question de RSA, un algorithme de chiffrement asymétrique reposant sur les nombres premiers.

A chaque exécution, le modulo change, cela explique le délai, qui correspond à la génération de ce dernier.

Le message, sous forme de lettre enflammée, nous défi de factoriser un modulo RSA de 4096 bits par amour !
En l’occurrence, celui proposé ne fait que 2048 bits, mais c’est déjà beaucoup.

Pour comprendre ce que nous devons faire, petit rappel sur le fonctionnement de l’algorithme RSA.

C’est un algorithme asymétrique, ce qui signifie qu’il fonctionne avec une paire de clés. L’une dite privée, l’autre publique. Chacune permet de chiffrer un message, mais pas de le déchiffrer. Ainsi un message chiffré avec la clé publique ne pourra être déchiffré qu’avec la clé privée et vice-versa.

La clé publique est généralement mise à disposition de tous, ce qui permet à tout le monde de nous envoyer des messages chiffrés.

Le RSA peut également servir à signer un message, en chiffrant le hash du message avec notre clé privée, les autres peuvent vérifier notre identité en déchiffrant la signature avec la clé publique de la personne que nous prétendons être.

Comme vous pouvez le voir sur le schéma ci-dessus, la plupart des exemples d’utilisation du RSA reprennent les prénoms Alice et Bob, comme l’énoncé de notre challenge. Ces prénoms ont été choisis par Ronald Rivest, l’un des trois inventeurs du RSA, acronyme qui se compose d’ailleurs de leurs initiales (Ronald Rivest, Adi Shamir et Leonard Adleman). Ces prénoms sont maintenant couramment utilisés dans les sujets de cryptographie, avec toujours les mêmes rôles :

• Alice, qui souhaite souvent discuter avec Bob, de manière discrète.
• Bob, qui souhaite recevoir des messages d’Alice
• Eve, qui espionne les conversations et tente de déchiffrer

Il existe d’autres personnages, mais qui ne seront pas utiles dans notre cas.

Dans cette épreuve, nous allons tenter de nous faire passer pour Bob auprès d’Alice. Pour cela, nous devons utiliser le principe de signature. Nous devons signer un message avec la clé privée détendue par Alice. Mais nous ne la connaissons pas, nous ne disposons que de la clé publique, formée par le modulo et l’exposant.

Pour comprendre comment trouver la clé privée, reprenons le procédé de génération des paires de clés RSA.

• un nombre “p” premier aléatoire est choisi
• un second nombre “q” premier, aléatoire et supérieur à “p” est également choisi
• le modulo “n” produit de “p” et “q” est calculé
• un exposant “e” premier avec “n” est calculé
• enfin, l’exposant de déchiffrement “d” inverse de “n” est calculé

Nous obtenons notre clé publique composée de “n” et “e”, et notre clé privée composée de “d” et “n”.

La sécurité du RSA repose sur le fait qu’il est difficile de factoriser “n” pour retrouver “p” et “q”. La prime actuelle pour la factorisation d’un modulo de 2048 bits est de 200000$, toujours en jeu faute de gagnant. Il est donc clair qu’il doit y avoir un moyen plus simple de trouver la clé privée.

Regardons comment la clé est générée dans le code :

“p” est obtenu de manière aléatoire grâce à la lib crypto, mais “q” est simplement dérivé de “p”. Plus précisément, “q” est le 10eme nombre premier après “p”. Ces conditions ne garantissent pas la sécurité, car nous savons que “p” et “q” se trouvent tous les deux très proches de la racine carrée du modulo “n” que nous connaissons.

Il suffit maintenant de calculer la racine carrée de “n”, puis de trouver le nombre premier suivant qui valide la division euclidienne avec ce dernier.

Nous avons donc fait une courte fonction qui permet de retrouver “p” et “q” à partir de “n” :

Une fois cela fait, il ne nous reste plus qu’à calculer “d” pour avoir la clé privée. Pour cela, nous reprenons simplement le code du challenge.

Maintenant nous pouvons calculer le modulo du hash du message pour le signer.

Enfin, nous assemblons tout cela dans une fonction “solve_chall”.

Testons !

>>>solve_chall(10654903999976671248790103138047114532135472694164240310853002642558396626157432402557412210007196405546786987125304372130206299046667985501155213610015742825582067380042190863574708357651902491708163041881240169443955583802298763919337140809369971906173579942144847592742920964984673512503114801243611914579649266502166938358547138808694464750098743956878248124306283639309471126888419260141476059224761886129733069121462989280018178805292091155082665112959198838126547109039026528300141695674352978933245998982788227619227718304656280059018314352551503365259402986987309068242141018194194456331246920557404237174577,"the_proof_of_your_love")

Résultat :

6442203526454661770679148989303027892333716972673744499200391955693626017163439096691741288073438010599792719517810695233040816633633728592198191067045333405341823289893196944752170572960755617808869587550920537456657857409813771873632122212992276689903188527266694098288426701811179024776499738122802832640685964578031537951663458116141297605562288276349396949848120305486906599437547599870436958345426192759724831346182414278677495096644789743113238560125426743789190241136141258123758028226697976035094421476902554152564527601162918532744198168148573491036106290289486247715725083973472043809263475949487214432928

Nous l’envoyons au serveur… c’est validé !

… enfin presque

Le serveur nous retourne une magnifique adaptation d’un poème de Paul Eluard, accompagné du flag chiffré.

On peut observer dans le code du challenge que le message est chiffré en AES 256, algorithme que ne dispose pas de vulnérabilité publique permettant de déchiffrer le message sans la clé quand il est utilisé dans de bonnes conditions.

Nous connaissons au moins les IV qui sont dérivés du timestamp.

Nous ne connaissons pas la clé, qui provient d’une variable d’environnement. Mais la clé est passée dans une fonction avant d’être utilisée.

Cette fonction retourne le hash SHA256 de la clé, pourquoi pas.

Mais si vous vous êtes familier de python, et plus précisément de la librairie hashlib, vous aurez tout de suite remarqué une erreur dans l’utilisation des méthodes de la librairie. La fonction hashlib.sha256().update(data) ne retourne pas directement le hash, elle ne retourne rien, et ne doit être utilisée qu’avec un objet hashlib pour une récupération du hash ultérieure.

Le résultat étant complété par du padding pour atteindre la taille d’un block AES (ici 16 octets), il est rempli … de vide.

Démonstration avec les valeurs intermédiaires :

>>> key = "SUP3R_S3CR3T_K3Y"
>>> key = hashlib.sha256().update( key.encode() )
>>> print(key)
None
>>> key = pad(str(key).encode(), 16)
>>> print(key)
b'None\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'

Le hash n’étant pas retourné, la clé correspond au mot “None”.

Nous pouvons donc simplement déchiffrer le message avec la clé ci-dessus et les IV dérivés du timestamp auquel nous avons démarré le challenge:

>>>print(key)
b'None\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c\x0c'
>>>iv = pad(long_to_bytes(int(timestamp)), 16)
>>>cipher = AES.new(key, AES.MODE_CBC, iv)
>>>print(cipher.decrypt(base64.b64decode('mij0uktUasof05jiwdYwLkUQhq3e6MsDsDynqjy0QVY=')))
b'Hero{P4ul_Eluh4ck}\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'

Et c’est le flag !

Hero{P4ul_Eluh4ck}

Contactez-moi :

Etienne Sellan
@LesPiresHat