Origine
L’inspiration de cette épreuve est venue lors de l’écriture du compte-rendu
de l’épreuve RSA Secure Dev de l’année précédente. Pour des raisons de
performance cette épreuve ne permet pas à ma connaissance de résoudre l’épreuve
précédente.
Énoncé de l’épreuve
On nous demande de produire un algorithme permettant de corriger des clefs privées RSA CRT alors même que la clef publique est inconnue (ni l’exposant public, ni le module public). Pour tester notre algorithme, un ensemble de 15 clefs erronées est fourni. Un script python est également fourni, permettant de vérifier pour chaque clef si la correction est celle attendue, puis indiquant la manière de retrouver le drapeau à l’aide des 15 clefs corrigées.
Analyse
Une clef privée RSA CRT est composée des éléments suivants:
- Un nombre premier $p$
- Un nombre premier $q$
- Un exposant privé $d_p$, tel que $d_p=e^{-1}\mod p-1$
- Un exposant privé $d_q$, tel que $d_q=e^{-1}\mod q-1$
- Un inverse modulaire $i_q$, tel que $i_q=q^{-1}\mod p$
- De plus, l’énoncé précise que $e$ fait moins de 100 bits. Soit $e_p=e\mod p-1$ et $e_q=e\mod q-1$, comme $p$ et $q$ sont bien plus grands que $e$, on a $e_p=e_q$.
On va donc utiliser ces égalités pour détecter et corriger les erreurs dans les clefs fournies. Voici une liste de test possible:
- Tester la primalité de $p$
- Tester la primalité de $q$
- Tester si $e_p=d_p^{-1}\mod p-1$ est plus petit que $2^{100}$
- Tester si $e_q=d_q^{-1}\mod q-1$ est plus petit que $2^{100}$
- Tester si $e_p=e_q$
- Tester si $d_p < p-1$
- Tester si $d_q < q-1$
- Tester si $q\cdot i_q=1\mod p$
- Tester si $i_q < p$
Analysons maintenant les clefs proposées:
| Clef | primalité de $p$ | primalité de $q$ | cohérence $d_p$ et $p$ | cohérence $d_q$ et $q$ | cohérence $q$, $i_q$, $p$ |
|---|---|---|---|---|---|
| 0 | ❎ | ✅ | ❎ | ❎ | ❎ |
| 1 | ✅ | ✅ | ✅ | ❎ | ✅ |
| 2 | ✅ | ✅ | ❎ | ❎ | ❎ |
| 3 | ❎ | ✅ | ❎ | ✅ | ❎ |
| 4 | ✅ | ❎ | ❎ | ❎ | ❎ |
| 5 | ✅ | ❎ | ✅ | ❎ | ❎ |
| 6 | ✅ | ✅ | ✅ | ❎ | ❎ |
| 7 | ✅ | ✅ | ❎ | ✅ | ❎ |
| 8 | ✅ | ✅ | ❎ | ❎ | ✅ |
| 9 | ✅ | ✅ | ❎ | ✅ | ✅ |
| 10 | ✅ | ✅ | ❎ | ✅ | ❎ |
| 11 | ✅ | ❎ | ✅ | ❎ | ✅ |
| 12 | ❎ | ✅ | ❎ | ✅ | ❎ |
| 13 | ✅ | ✅ | ✅ | ✅ | ❎ |
| 14 | ✅ | ✅ | ✅ | ❎ | ❎ |
Le niveau d’erreur des clefs varient. Les clefs 0 et 4 ne passent qu’un test, alors que les clefs 1, 9 ou 13 n’ont qu’une seule incohérence. Il n’y a probablement pas deux clefs ayant subit exactement la même faute puisque chaque ligne du tableau est différente.
Intuitions nécessaires
Les clefs peuvent être corrigées (sinon ce ne serait pas une épreuve de CTF), les erreurs ne sont donc pas trop difficiles. Si on constate plusieurs incohérences, comme pour la clef 0 par exemple, il faut trouver un moyen simple de corriger les composantes de cette clé. On peut par exemple se concentrer sur la clef 2, pour laquelle les composantes $p$ et $q$ semblent correctes, mais $d_p$, $d_q$ et $i_q$ semblent incorrect. On peut alors penser à tester si la clef serait correcte en inversant $p$ et $q$ $\dots$ Et miracle, on obtient la clef attendue ! De même en inversant 2 composantes des autres clefs, on arrive à corriger 10 clefs au total.
On peut se demander si les clefs sont équilibrées, à savoir si $q < p < 2q$ ou $p < q < 2p$. C’est bien le cas et pour s’en assurer on peut regarder les tailles des autres composantes $d_p$, $d_q$, $i_q$. Il aurait été possible d’avoir $|d_p|=|d_q|$ (où $|\cdot|$ désigne la taille en bit) avec des clefs déséquilibrées, mais cela aurait été sur la taille du plus petit premier. Cette taille n’aurait pas été cohérente avec les autres clefs, ce qui aurait intrigué.
Si un premier $p$ ou $q$ est remplacé par un autre nombre premier aléatoire, on ne le détectera pas au niveau de la cohérence. C’est un défaut de l’épreuve qui ajoute une difficulté sous-estimée lors de la conception (sûrement un démon qui veut du mal aux participants du FCSC 😈). Obtenir un nombre premier en conséquence d’une erreur aléatoire étant improbable, on n’y pensera pas facilement. On est alors amené à corriger l’exposant associé, ainsi que $i_q$. Cela donne une clef valide, mais pas la clef attendue (ce dont on se rend compte via les empreintes fournies pour chaque clef). Ce piège était présent pour les clefs 10 et 14, corriger l’une pouvait faciliter la correction de l’autre.
Solution
Il va s’agir de traiter exhaustivement tous les cas détectés et de voir si on obtient une clef cohérente/la clef attendue. On teste donc dans un premier temps tous les échanges de 2 paramètres. Cela permet effectivement de corriger $\binom{5}{2}=10$ clefs, celles d’indice 0, 2, 3, 4, 5, 6, 7, 8, 11, 12.
Pour corriger les 5 clefs restantes, il faut traiter le cas d’une erreur sur un seul des paramètres. Les cas les plus simples concernent la correction de $d_p$, $d_q$ et $i_q$:
- $d_p = e_q^{-1}\mod p-1$
- $d_q = e_p^{-1}\mod q-1$
- $i_q = q\mod p$
Les cas pour $q$ et $p$ sont moins faciles.
Corriger $q$
$q\mod p = i_q^{-1}\mod p$. Si $q < p$ on a retrouvé $q$. Si $p < q < 2p$, alors $q = (q\mod p) + p$. Si les clefs avaient été déséquilibrées, il aurait fallu tester tous les $(q\mod p)+k\cdot p$ jusqu’à trouver le bon $q$. Pour cette épreuve, on avait $q < p$ pour la clef 14, pas de pièges ici donc ( 😇 ).
Corriger $p$
Pour retrouver $p$, on va construire 2 multiples de $p$ et calculer leur pgcd. Un premier multiple s’obtient en calculant $t_1 = q\cdot i_q - 1$. Un second multiple s’obtient en calculant $t = j^{e_q\cdot d_p -1}\mod t_1$ pour un entier $j$. Toutefois la clef a été choisie pour minimiser les chances d’avoir $p=\mathrm{gcd}(t-1, t_1)$ (le vice 😈); par exemple pour $j < 44070$, on a $k\cdot p = \mathrm{gcd}(t-1, t_1)$ avec $k\neq 1$. Malgré tout, on s’en sort avec une simple élimination des petits facteurs premiers
def remove_easy_factor(p):
prime = 2
for _ in range(1000):
if gmpy2.is_prime(p):
return p
while 0 == (p%prime):
p = p//prime
prime = gmpy2.next_prime(prime)
return p
Voici le code regroupant les différents cas:
def test(p,q,iq,dp,dq):
t1 = q*iq-1
ep = 0
eq = 0
if 1==gmpy2.gcd(dp,p-1):
ep = gmpy2.invert(dp,p-1)
if 1==gmpy2.gcd(dq,q-1):
eq = gmpy2.invert(dq,q-1)
if iq > p:
return False
if dp > p:
return False
if dq > q:
return False
if ep != eq:
return False
if ep > 2**100 or eq > 2**100:
return False
if 0 == ep:
return False
if 0 != (t1%p):
return False
if not gmpy2.is_prime(p):
return False
if not gmpy2.is_prime(q):
return False
return True
def solve(p,q,iq,dp,dq):
t1 = q*iq-1
t2 = p*iq-1
ep = 0
eq = 0
if 1==gmpy2.gcd(dp,p-1):
ep = gmpy2.invert(dp,p-1)
if 1==gmpy2.gcd(dq,q-1):
eq = gmpy2.invert(dq,q-1)
#case where dp and dq have been exchanged
if test(p,q,iq,dq,dp):
return p,q,iq,dq,dp
#case where iq and dp have been exchanged
if test(p,q,dp,iq,dq):
return p,q,dp,iq,dq
#case where iq and dq have been exchanged
if test(p,q,dq,dp,iq):
return p,q,dq,dp,iq
#case where q and iq have been exchanged
if test(p,iq,q,dp,dq):
return p,iq,q,dp,dq
#case where q and dp have been exchanged
if test(p,dp,iq,q,dq):
return p,dp,iq,q,dq
#case where q and dq have been exchanged
if test(p,dq,iq,dp,q):
return p,dq,iq,dp,q
#case where p and dq have been exchanged
if test(dq,q,iq,dp,p):
return dq,q,iq,dp,p
#case where p and dp have been exchanged
if test(dp,q,iq,p,dq):
return dp,q,iq,p,dq
#case where p and iq have been exchanged
if test(iq,q,p,dp,dq):
return iq,q,p,dp,dq
#case where p and q have been exchanged
if 0 == (t2%q):
if test(q,p,iq,dp,dq):
return (q,p,iq,dp,dq)
else:
return False
#case where iq is wrong
if ep == eq :
if 1 == gmpy2.gcd(q,p):
iq = gmpy2.invert(q,p)
if test(p,q,iq,dp,dq):
return p,q,iq,dp,dq
else:
return False
#case where dq is wrong
t = 0
if 1 == gmpy2.gcd(ep,q-1):
t = gmpy2.invert(ep,q-1)
if test(p,q,iq,dp,t):
return p,q,iq,dp,t
#case where dp is wrong
t = 0
if 1 == gmpy2.gcd(eq,p-1):
t = gmpy2.invert(eq,p-1)
if test(p,q,iq,t,dq):
return p,q,iq,t,dq
#case where q is wrong
t = 0
if 1 == gmpy2.gcd(iq,p):
t = gmpy2.invert(iq,p)
if test(p,t,iq,dp,dq):
return p,t,iq,dp,dq
#case where p is wrong
for i in range(2,48000):
t = gmpy2.powmod(i, eq*dp-1, t1)
p = gmpy2.gcd(t-1,t1) #t1 is supposed to be a multiple of p
p = remove_easy_factor(p) #without this optimization, we may test many values of i
if test(p,q,iq,dp,dq):
return p,q,iq,dp,dq
return False
Anecdotes de conception
Lors de la conception, il est arrivé de tomber sur des clefs telles que $e_p=e_q < \mathrm{min}(p,q)$ sans qu’on cherche réellement l’explication de ce phénomène. Avec la borne $2^{100}$ cela levait les ambiguïtés.
À l’origine, seuls certains $e$ faisaient 80 bits, puis cela a été uniformisé sur l’ensemble des clefs pour des raisons esthétiques.
L’inversion des composantes $p$ et $q$ est une erreur qui peut arriver en pratique ? (toute ressemblance avec des faits réels serait fortuite)
Le mot de la fin : qui sait si cette épreuve n’en inspirera pas une autre pour la prochaine édition 😈?