TokyoWesterns CTF 4th 2018: Crypto - Revolutional Secure Angou

Posted on 04 Sep 2018, 08:23 in WriteUps

Challenge description

The challenge was called Revolutional Secure Angou. A zipfile was given to us. Inside we could find three file: an RSA public key publickey.pem (PEM formatted), the encrypted flag flag.encrypted and the ruby script called generator.rb used to generate both the public key and the ciphertext. Our goal is obvious: decrypt the file flag.encrypted.

The source code of generator.rb is quite simple:

  1 2 3 4 5 6 7 8 9 10 11 12 13 require 'openssl' e = 65537 while true p = OpenSSL::BN.generate_prime(1024, false) q = OpenSSL::BN.new(e).mod_inverse(p) next unless q.prime? key = OpenSSL::PKey::RSA.new key.set_key(p.to_i * q.to_i, e, nil) File.write('publickey.pem', key.to_pem) File.binwrite('flag.encrypted', key.public_encrypt(File.binread('flag'))) break end 

As we can see line 6, q is generated in a very peculiar way: it is set to be the inverse of e modulo p. Line 7 ensures that q is prime in order to avoid a trivial factorisation. The rest of the script just encrypts the flag and write the publickey.

This challenge is just another RSA-based challenge where the vulnerability is in the prime numbers generation.

Solution

My approach when I need to face those RSA-based challenge is to write down the informations that I have as equations. Here we know:

• The public modulus $$n = p.q$$;
• The public exponent $$e = 65537$$;

We don't know the value of either $$p$$ or $$q$$ but we know that $$q = e^{-1} \mod p$$, thus $$qe = 1\mod p$$. We can also express this congruence as: $$\exists k, qe = kp + 1$$. Since $$q$$ is roughly the same size as $$p$$, then $$k$$ must be approximatly the same size as $$e$$. Hence, even if we don't know the exact value of $$k$$, it will be easy to brute-force if we have a correct criterion to validate its value.

Since $$qe = kp + 1$$, then $$qep = ne = kp^2 + p$$. Thus, $$p$$ is a positive integer root of the polynomial $$kX^2 + X - ne$$. As a first step, and because we don't know the value of all the coefficients of this polynomial, we use this property, along with the standard method of resolution of a 2nd degree polynomial, to find $$k$$ which is such that:

• $$\Delta = 1 + 4kne$$ is a perfect square;
• $$2k$$ is dividing $$\sqrt{\Delta} - 1$$.

Once such a $$k$$ is found, then we can compute $$p = \frac{\sqrt{\Delta} - 1}{2k}$$. The modulus being factorised, we can compute the associated private key and decrypt the flag.

Here is the python script used to solve the challenge:

Python source code
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa
import math

def isqrt(n):
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m

with open("publickey.pem", "rb") as key_file:
backend=default_backend())

e = pubkey.public_numbers().e
n = pubkey.public_numbers().n

for k in range(1, e):
delta = 1 + 4*k*n*e
sqr = isqrt(delta)
if not sqr*sqr == delta:
continue
if (sqr - 1)%(2*k) == 0:
p = (sqr - 1)//(2*k)
q = n//p
assert p*q == n
print("Factorisation found!")
break

d = modinv(e, (p-1)*(q-1))
iqmp = rsa.rsa_crt_iqmp(p, q)
dmp1 = rsa.rsa_crt_dmp1(d, p)
dmq1 = rsa.rsa_crt_dmq1(d, q)
public_numbers = rsa.RSAPublicNumbers(e, n)

private_numbers = rsa.RSAPrivateNumbers(p, q, d, dmp1, dmq1, iqmp,
public_numbers)
privkey = private_numbers.private_key(default_backend())
with open("flag.encrypted", "rb") as cipher: