One Step Closer

Se nos proporciona el código fuente en Python para cifrar la flag, y una aplicación Flask que llama a la función de cifrado:

from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, inverse
import random

FLAG = b'HTB{--REDACTED--}'
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 257


def encrypt_flag():
    a = random.getrandbits(1024)
    b = random.getrandbits(1024)

    flag = bytes_to_long(FLAG)

    msg = a*flag + b

    ct = pow(msg, e, n)
    return {'ct': format(ct, 'x'), 'n': format(n, 'x'), 'e': format(e, 'x'), 'a': format(a, 'x'), 'b': format(b, 'x')}  

from flask import *
from chall import encrypt_flag

app = Flask(__name__)


@app.route('/', methods=['GET'])
def index():
    return render_template('index.html')


@app.route('/api/get_flag', methods=['GET'])  
def get_flag():
    payload = encrypt_flag()
    return jsonify(payload)


if __name__ == '__main__':
    app.run(host='0.0.0.0', port=1337)

Podemos expresar los cálculos anteriores de un criptosistema RSA en términos matemáticos (sea $F$ la flag en formato decimal):

$$ m = a \cdot F + b $$

$$ c = m ^ e \mod{n} = (a \cdot F + b) ^ e \mod{n} $$

Teniendo en cuenta que podemos llamar a encrypt_flag varias veces, podríamos matizar que:

$$ c_i = (a_i \cdot F + b_i) ^ e \mod{n} $$

Esto es un claro ejemplo de ataque de Franklin-Reiter related-message, ya que podemos definir dos polinomios $f, g \in \mathbb{Z}/n\mathbb{Z}[x]$ que relacionan dos textos cifrados:

$$ f(x) = a_1 \cdot x + b_1 \qquad g(x) = a_2 \cdot x + b_2 $$

Como $f(F)^e - c_1 = 0$ y $g(F)^e - c_2 = 0$, los polinomios $f(x)^e - c_1$ y $g(x)^e - c_2$ comparten un factor común, que será un polinomio lineal $x - F$, cuya raíz es $F$.

Podemos implementar el ataque en SageMath así:

def composite_modulus_gcd(f, g):
    if g == 0:
        return f.monic()

    return composite_modulus_gcd(g, f % g)


def franklin_reiter(n, e, ct1, ct2, a1, a2, b1, b2):
    P.<x> = PolynomialRing(Zmod(n))
    f = (a1 * x + b1) ^ e - ct1
    g = (a2 * x + b2) ^ e - ct2

    return -composite_modulus_gcd(f, g).coefficients()[0] % n  

Nótese el uso de composite_modulus_gcd porque $\mathbb{Z}/n\mathbb{Z}$ no es un cuerpo finito, por lo que no podemos definir el Máximo Común Divisor (GCD) en este anillo de polinomios. Sin embargo, podemos aplicar el algoritmo de Euclides (más información en mathematica.stackexchange.com).

Lo único que falta es tomar los parámetros de cifrado de la aplicación Flask y realizar el ataque:

$ sage solve.sage 104.248.162.85:32441
HTB{RSA_f1n1t3_d1ffs_@nd_r31473d_m355493_4774ck5_:eyes:}  

El script completo se puede encontrar aquí: solve.sage.