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
Taking into account that we can call encrypt_flag
multiple times, we should say that:
This is a clear example of Franklin-Reiter related-message attack, because we can define two polynomials
Since
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
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
.