FCSC 2023 - Quelque chose cloche
Intro
Le FCSC est un CTF de type “jeopardy”, avec cette année une soixantaine d’épreuves de difficultés variées dans les catégories suivantes : crypto, reverse, pwn, web, forensics, hardware, attaque par canaux auxiliaires ou en faute et misc.
La catégorie Side channel était particulièrement intéressante car elle proposait ce challenge d’attaque par fautes, ainsi que 2 challenges de défense (voir post suivant).
Signature
Voici ce que donne une première connexion au serveur utilisant l’implémentation décrite.
$$s = m^{d}[n]$$ $$m = s^{e}[n]$$
Nous avons à la fin s qui sera notée par la suite s': la signature erronée calculée par le serveur.
Nous ne pouvons malheureusement pas signer m = 1 car cela nous donnerait dp et dq et on pourrait factoriser n directement.
Le but est de retrouver la clé privée d afin de déchiffrer le ciphertext c, sachant que la paire ((n,e),d) change à chaque éxécution.
Ainsi, nous pourrons récupérer le flag $$ m = c^{d} [n]$$
Résolution
Énorme coup de chance, la doc que j’avais cherché pour RSA - Secure dev (avec google sur RSA-CRT : iq,dp,dq) donne la solution …
L’algorithme d’Euclide étendu (egcd) permet de trouver les coefficients de Bezout, tels que
ap + bq = 1
D’après l’énoncé nous avons:
La signature calculée avec le théorème des Restes Chinois (CRT) vaut, avec $$i_{q}= q^{-1} [p]$$
Le Théorème des Restes Chinois (CRT) est souvent utilisé pour optimiser le déchiffrement RSA en découpant les calculs en sous-problèmes.
Version Équations Modulaires :
Dans le contexte de RSA, supposons que nous ayons un message $m$ chiffré $c$ et les modules de chiffrement $N_1, N_2, \ldots, N_k$. Calculons les $M_i$ et les coefficients d’inversion $y_i$ pour chaque $i$ de $1$ à $k$. Ensuite, en utilisant le CRT, la valeur déchiffrée $x$ est donnée par :
$$ m = (c_1 \cdot M_1 \cdot y_1 + c_2 \cdot M_2 \cdot y_2 + \ldots + c_k \cdot M_k \cdot y_k) \ (\mathrm{mod} \ N), $$
où $N = N_1 \cdot N_2 \cdot \ldots \cdot N_k$.
Si vous ne me croyez pas ,c’est dans ce document !
https://www.cosade.org/cosade19/cosade14/presentations/session2_b.pdf
On chiffre donc un message au hasard et on retrouve q avec la seconde méthode.
Explication:
On dispose de s' lorsque le serveur répond: la signature erronée. Notons s la vraie signature.
D’où:
$${s’}^{e}[n] - {s}^{e}[n] = {s’}^{e}[n] - m $$
Notons $$\delta = {s’}^{e}[n] - m$$
Nous avons un diviseur commun avec n: $$\delta \wedge n != 1$$
C’est l’attaque de Bellcore: https://eprint.iacr.org/2012/553.pdf
Script
Voici le script qui déroule le tout (~1min)
| |
FCSC{1ec0d4b4c2de4329e2431fb65d229fb7ba2fbf93206e8c273ca22172bdb64d99}