One Step Closer

2 minutes to read

We are given a Python code to encrypt the flag, and a Flask application that calls the encryption function:

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)

We can express the above RSA computations in mathematical terms (let $F$ be the flag in decimal format):

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

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

Taking into account that we can call encrypt_flag multiple times, we should say that:

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

This is a clear example of Franklin-Reiter related-message attack, because we can define two polynomials $f, g \in \mathbb{Z}/n\mathbb{Z}[x]$ that relate two ciphertexts:

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

Since $f(F)^e - c_1 = 0$ and $g(F)^e - c_2 = 0$, the polynomials $f(x)^e - c_1$ and $g(x)^e - c_2$ share a common factor, which will be a linear polynomial $x - F$, whose root is $F$.

We can implement the attack in SageMath as follows:

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

Notice the use of composite_modulus_gcd because $\mathbb{Z}/n\mathbb{Z}$ is not a finite field, so we cannot define the Greatest Common Divisor (GCD) in this polynomial ring. However, we can apply the Euclidean algorithm (more information in mathematica.stackexchange.com).

The only thing we need to do is get the encryption parameters from the Flask applicaton and perform the attack:

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

The full script can be found in here: solve.sage.