Introduction

Prélude

L’arborescence du site découvert à l’étape précédente contient une série de fichiers relatifs aux différentes épreuves, mais aussi un client lourd permettant d’interagir avec les services du challenge.

Ce binaire, en fait un py2exe, interagit avec les fameux ports 44544, 44645 et 44546 brièvement mentionnés plus tôt. On peut récupérer l’ensemble du code python, mais celui-ci est protégé par pyarmor. Des projets permettant de contourner pyarmor existent mais ça ne m’a pas semblé utile pendant les épreuves.

En se connectant via ce client lourd on apprend qu’il faudra résoudre les step 1 et 4 avant de passer au step 2, puis step 3.

Retour au step 1

Ce challenge est proposé sous la forme d’un script python implémentant une exponentiation modulaire dans \$GF_2\$. Le script va ensuite tirer un nombre aléatoire \$m\$ compris entre \$2^10 et 2^1000\$, calculer \$c = m^e mod N\$ et demander le nombre \$d\$ tel que \$c^d mod N = m\$.

Bref. Un RSA.

Résolution (dans \$N\$)

La résolution assez simple nécessite deux étapes :

  • factoriser N (si possible)

  • calculer le totient d’Euler \$phi(N)\$ (ou la version réduite \$lambda(N)\$ ). Pour l’espace des entiers naturels \$phi(N) = (p-1)(q-1)\$

La valeur de la clé de déchiffrement ( \$d\$ ) peut ensuite être calculée simplement :

\$d = e^-1 mod phi(N)\$

Résolution (dans \$GF2\$)

En théorie, sauf qu’on est dans GF2. N étant un polynôme, il faut le factoriser en polynômes irréductibles ( dans \$N\$, N finissant par 5, une facteur trivial serait 5, c’est pas top pour une clé privée). Il suffit de demander à sage :

N = 131112461083260041466258559989852650048846977423676023208693096772757828312140757610949989273566247604399260337743520516344780224409356362489492887146748841094452709115063856352029664073256510410313419262026728741800154737100926401064995382067588953172165650115436825536620238998816599395608416117110767847385

GF_2048.<x> = GF(2^2048)
F.<x> = GF(2)
R.<x> = PolynomialRing(F)
poly_N = R(N.bits())

factors = poly_N.factor()
for fac in factors:
    print(GF_2048(fac[0]).to_integer())

Nous donne la liste des composants de N suivante :

r1 = [
    3,
    7,
    220257,
    1183345,
    5590282333,
    221812995075,
    2501459234597438556180263,
    288263694650404644897512632143022491544960084195,
    504851978770360816229159785311395352861267873643049434918424770244997450595715019287037412884927103731534756431990663645703077509560629180609926133192552856507226368721736114935659407845276866098028589347
]

Le calcul de \$phi(N)\$ est également différents dans GF2. En considérant que d est le degré du polynôme p : \$phi(p)=2^d - 1\$. Comme on représente les polynômes par un entier le degré est tout simplement la nombre de bits de ce nombre - 1. En python :

def GF2_phi(factors):
    phi = 1
    for f in factors:
        phi *= ( 2**(f.bit_length()-1) - 1)
    return phi

Reste le calcul de d, j’ai longtemps cru, travaillant dans GF2, qu’il fallait faire l’inversion modulaire dans GF2 (le script solve.py contient un code dédié, testé sur les clés COCONUT98 de sstic 2020), ce qui n’a pas vraiment de sens au final, e étant un entier…​. On reste donc dans l’espace des entiers naturels et on a :

N1 = 131112461083260041466258559989852650048846977423676023208693096772757828312140757610949989273566247604399260337743520516344780224409356362489492887146748841094452709115063856352029664073256510410313419262026728741800154737100926401064995382067588953172165650115436825536620238998816599395608416117110767847385
r1 = [
    3,
    7,
    220257,
    1183345,
    5590282333,
    221812995075,
    2501459234597438556180263,
    288263694650404644897512632143022491544960084195,
    504851978770360816229159785311395352861267873643049434918424770244997450595715019287037412884927103731534756431990663645703077509560629180609926133192552856507226368721736114935659407845276866098028589347
]


N = N1
factors = r1
E = 65533

n_check = 1
for r in factors:
    n_check = GF2_mul(n_check, r)

if n_check != N:
    print("Factorisation error !!!")
    exit()


phi = GF2_phi(factors)
print("PHI : %d"%phi)

d = pow(E, -1, phi)

En l’utilisant pour résoudre le challenge du client lourd, on obtient le flag chiffré :

flag_enc = 0x339c28835be94cdfed18f3f3a06b7dc3141bbe97ac7cc1fe9e97b9f0f8d2d46ae5cd72baa7b8cac2a0827650be50486199b74be9f7cfbdfed3b29de73ce0a91188c98f4c772a2e3d9e7487aca10bb1a3d0c4ab57c1bb6b02edb35f4e144d7bd1e547dce4e8450819addb78541da4f72e72cfe5fcfb68538a818dadd7542fedb7
flag = GF2_pow_mod(flag_enc, d, N)
flag = binascii.unhexlify(hex(flag)[2:].strip("L").zfill(256)).decode()
print ('flag1 : ' +flag)
print()

Nous donne :

flag1 : SSTIC{f5ab077834d560a2711413da4646bfa1f02e9b24df9c0863}

Resource: solve.py