Un simple oracle 1/2 (Cryptanalyse) - 404CTF2022

Principe:
Utiliser un oracle RSA et lui envoyer C * 2**e pour qu'il le déchiffre, nous renvoie m*2 et en déduire m, le message original (le flag)

Infos (cf menu latéral):
🚩 Flaggué! +981 points gagnés — 💾 Téléchargez les fichiers du challenge
404CTF{L3s_0r4cl3s_RSA_s0n7_si_fr4g1l35}

Le challenge

Demandez un secret à l'oracle (mon fichier de résultats est là)

Oracle

On interroge un peu l'oracle, qui semble être à base de RSA

En RSA, étant donné que cypher = message ** exposant [mod N] un message nul 0 donnera toujours 0 et 1 donnera toujours 1

Si on envoie C à l'oracle, celui-ci refuse de répondre. L'oracle semble donc déchiffrer tout ce qu'on lui donnera en entrée, sauf le message qu'on est censé déchiffrer
Idem, si on envoie C + N, l'oracle refuse de répondre (dommage, car déchiffrer C ou C + k*N, cela revient au même puisqu'on est modulo N)

Chosen ciphertext

Comme on choisit le cypher, on est dans un chosen cyphertext attack, et on cherche donc quelles attaques existent sur RSA

L'idée est d'envoyer C * 2 ** e. L'oracle le déchiffrera, nous renvoyant 2*m soit le double du message original (modulo N)

Je scripte de quoi envoyer cette valeur au serveur (on pouvait aussi le faire à la main mais bon)
Et on divise la réponse de l'oracle par deux

On peut transformer la réponse de l'oracle en une chaine hexadécimale, puis diviser chaque paire d'octets par deux. En effet, la table ASCII s'arrête à 0x7f (pour les caractères qui nous intéressent), donc, le double sera forcément inférieur à 0xff et tiendra lui aussi sur deux octets

Plus qu'une petite étape
On remet le flag dans le bon sens après avoir rigolé un coup, et voilà!

Flag: 404CTF{L3s_0r4cl3s_RSA_s0n7_si_fr4g1l35}