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 zip file 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
from cryptography.hazmat.primitives.asymmetric.padding import PKCS1v15
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:
    pubkey = serialization.load_pem_public_key(
            key_file.read(),
            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:
    print("Flag: {}".format(privkey.decrypt(cipher.read(),
                    PKCS1v15()).decode()))