[SigSegv2] RektSA

La deuxième édition du famoso “SigSeg” organisé par l’asso RTFM se décompose en deux étapes. La première est un CTF de qualifications en ligne pour participer à la seconde : l’évènement en présentiel sur Paris qui propose CTF, confs, boissons, et amis hackers de renom.

Lors des qualifications en ligne, 5 challenges ont été proposés dont un de crypto qui m’a demandé pas mal de boulot ! Voilà le write-up de cette épreuve.

Énoncé

État de l’art

Voilà le contenu du fichier de challenge encrypt.py.

#!/usr/bin/python2.7

import sys
from secret import FLAG
from Crypto.Util.number import getPrime, bytes_to_long
from gmpy2 import invert

p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1028)

e = 0x10001

N = p * q * r
phi = (p - 1) * (q - 1) * (r - 1)

print 'N:', N
print 'phi:', phi % 2**2050
print 'r:', r

print 'Give me d: '

sys.stdout.flush()

try:
    d = int(raw_input())
except:
    print 'Invalid input!'
    exit(1)

if d == invert(e, phi):
    print 'Congratulations: %s' % FLAG
else:
    print 'Nope!'
    exit(1)

Il s’agit du code exécuté côté serveur.
Une connexion à ce dernier nous donne les valeurs de N, phi et r.
À partir de celles-ci, on doit trouver d = invert(e, phi).

Théorie

Normalement, mon kill chain pour un challenge comme celui-ci est à peu près le suivant.

Mais dans ce cas, ce raisonnement m’a fait perdre pas mal de temps. La pression du flag toussa toussa. Quelques cookies, et on reprend les choses autrement.

Etude du lien entre N et phi

Un développement du calcul de phi nous permet de souligner le lien avec N.

N = pqr
phi = (p-1)*(q-1)*(r-1) = pqr+p-p*q-p*r+q-q*r+r-1

phi < N
phi = N+(p-p*q-p*r+q-q*r+r-1)

Un peu d’analyse sur les tailles (en bits) nous permet d’identifier que les 1023 bits de poids fort sont les mêmes entre N et phi.

bit_length(phi) = 3075
bit_length(N) = 3075
bit_length(p−pq−pr+q−qr+r-1) = 2053

Tentons de comprendre comment la connaissance des 1023 MSB peut nous aider.

bit_length(phi % 2**2050) = 2049
2**2050 = 1000...00 (2049 bits)
//Etude de : phi/2**2050
+----------+-----------+   +-----------+   +----------+--------+
| 1011...0 | ???...??? | / | 1000...00 | = | 1011...0 | ????   |
+----------+-----------+   +-----------+   +----------+--------+
| 1023bits | 2053 bits |   | 2049 bits |   | 1023bits | 4 bits*|
+----------+-----------+   +-----------+   +----------+--------+
*2053 - 2049 = 4

Si on a 1023 MSB identiques sur N et phi, on peut retrouver phi à 4 bits près en connaissant le reste. Pourquoi ? C’est le fait que notre diviseur soit un ‘1’ suivi de 2048 ‘0’. La division ‘découpe’ le dividende.

Soit la division Dividende / Diviseur = Quotient + Reste.

Dans notre cas, le diviseur de 2049 bits ne couvrant pas les 2053 bits différents entre N et phi, il reste 4 bits à trouver.

Trouver phi

phi = 2**2050 * entier(phi / 2**2050) + reste or entier(phi / 2**2050) = entier(N / 2**2050) à 4 bits près, soit phi = 2**2050 * [entier(N / 2**2050) - variable] + reste

En faisant le calcul de (N/2**2050 - phi/2**2050) en local, on a bien une différence qui varie de 2 à 8 en décimal soit 4 bits.
Une preimère solution serait de bruteforcer, de définir la variable à 4 et de tenter jusqu’à ce que ça marche avec ~60% de chances de succès.

Une autre solution est d’utiliser un autre élément qui nous est donné : le facteur r. Si phi % (r - 1) = 0, alors on a le bon phi.

Pratique

#!/usr/bin/env python
# coding: utf-8

import socket
from gmpy2 import invert

host = "qual-challs.rtfm.re"
port = 9001

socket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
socket.connect((host, port))
print '[+] Connected...'

challenge = socket.recv(4096)

N = int(challenge.split('\n')[0].split(':')[1].strip(' '))
remain_phi = int(challenge.split('\n')[1].split(':')[1].strip(' '))
r = int(challenge.split('\n')[2].split(':')[1].strip(' '))

print '[+] Received the values...'

e = 0x10001

for i in range(8):
    i += 1
    print '[+] Trying ', i
    phi = 2**2050 * ((N / 2**2050) - i) + remain_phi
    if phi % (r - 1) == 0:
        d = invert(e, phi)
        print "[+] Sending answer..."
        socket.send(str(d) + '\n')
        print socket.recv(4096)
        exit(0)