In this challenge from the first ever CTF competition organized by the H4x0rPsch0rr team, …

Your task is simple: ssh -i id_rsa -p 1122 ctf@1.ctf.link

Oh, and here’s the key, because we love you <3 :)

The (RSA) private key is…

-----BEGIN RSA PRIVATE KEY-----
MIMIECICAQACgggBANRFHE8WEB/STSEH+Coqqdw6sI3CyaLGNuH1A46qBC5JzXeX
Kg9KPSkbwydPj5HVZ+i2d9nDK5ifYv0mC7CCHAE2RuYqOwDJe3LKt0ZBHI11nomm
    [...roughly 11k more lines of base64...]
4ZcP2zJaIKd7LKH7b79gxtJyMJCHt+34AzdJqRGHwRef9FHp4j+VxtGdtycoUkvk
4oPCAd4tUhJuj35AlMWcXQHCYOH+opKBAgEBAgEBAgEAAgEAAgEA
-----END RSA PRIVATE KEY-----

…extraordinarily huge.

---

Trying to simply log in, as demanded by the task, quickly turns out to be quite hopeless: The SSH client immediately eats 100% CPU power and even after waiting a considerable amount of time, there is no significant progress in authenticating to the server.

So what’s wrong with the key? As it turns out (using openssl asn1parse and some regex magic to shorten the output), all private parts except $d$ are set to zero or one, that is, blanked out, and $d$ has over four million bits, much more than the modulus ($16384$ bits).

(Fun fact: OpenSSH does in fact accept keys of that format, i.e. without $p$, $q$, $d\bmod{\varphi(p)}$, $d\bmod{\varphi(q)}$, $q^{-1}\bmod p$. Hence the key is actually functional!, just a little bit, pun intended, oversized…)

---

It is a defining property of the exponents in the RSA signature system that $e$ and $d$ satisfy \[ ed\equiv1\pmod{\lambda(n)} \text, \] where, in this context, $\lambda$$(n)=\operatorname{lcm}(p-1,q-1)$. On the other hand, this implies that there is an infinite number of working private exponents $d$ for a given public key $(n, e)$ — and the one we are given seems to be a rather large one ;-). Now how can we obtain a smaller representant $d’$ of those possible exponents? Clearly we still need $ed’\equiv1\pmod{\lambda(n)}$. Since the canonical projection $\mathbb Z\to\mathbb Z/\lambda(n)\mathbb Z$ is a ring homomorphism, we can just replace $d$ by $d\bmod\lambda(n)$ without changing the validity of the congruence $d$ must satisfy.

But… We don’t know $\lambda(n)$, and it can’t easily be derived from $n$ since this task is essentially equivalent to factoring $n$. However, there is an efficient algorithm to determine the factors of $n$ given a pair $(e, d)$ which satisfies the usual congruence! A nice description of such a method can be found in Dan Boneh’s paper, proof of fact 1. (Also make sure to check out the implementation below. It’s the block commented “magic!”.)

After a factorization $n=pq$ has been obtained, one can simply compute \[ d’ := d\bmod \operatorname{lcm}(p-1,q-1) \] and create a new keyfile filling in the exponent $d’$ in place of $d$ and, if one wishes, the numbers missing from the given key (although that’s not strictly necessary, as commented above). The resulting key should work quickly enough to authenticate to the server in time.

Here’s the resulting script:

#!/usr/bin/env sage
import os, base64
from pyasn1.type import univ
from pyasn1.codec.der import encoder, decoder

################################################################################

# parse id_rsa and convert to a more workable format.
f = open('id_rsa', 'r').read()
f = ''.join(l for l in f.split('\n') if l and not l.startswith('-----'))
f = base64.b64decode(f)

dec = decoder.decode(f)
_, n, e, d, p, q, dp, dq, qi = map(int, dec[0])
print('decoded asn1.')

################################################################################

# magic! compute p, q from n, e, d.
g = 2   # may need to change this if "bad root" occurs

t, r, k = 0, e * d - 1, e * d - 1
while not r & 1:
    t += 1
    r >>= 1

x0 = Zmod(n)(g) ** (k >> t)
print('done with huge exponentiation.')
xs = [x0 ** (2 ** i) for i in reversed(range(t))]
for x in xs:
    if int(x) in [1, n - 1]:
        continue
    p = gcd(int(x) - 1, n)
    print('\x1b[32mp = {:#x}\x1b[0m'.format(p))
    assert p not in [1, n]
    break
else:
    print('\x1b[31moops, bad root\x1b[0m')
    exit(1)

q = n // p
print('\x1b[32mq = {:#x}\x1b[0m'.format(q))

################################################################################

# fix key.
d = d % lcm(p - 1, q - 1)
print('\x1b[32md := {:#x}\x1b[0m'.format(d))
p = q = 1
dp = dq = qi = 0

################################################################################

# encode new key.
key = ''
k = univ.SequenceOf(univ.Integer()).setComponents(0, n, e, d, p, q, dp, dq, qi)
enc = base64.b64encode(encoder.encode(k)).decode()
key += '-----BEGIN RSA PRIVATE KEY-----\n'
for i in range(0, len(enc), 64):
    key += enc[i:i+64] + '\n'
key += '-----END RSA PRIVATE KEY-----\n'

open('id_rsa.good', 'w').write(key)
os.chmod('id_rsa.good', int('0600', 8))

Using the resulting key file id_rsa.good, we can easily log in to the server and get the flag:

$ time ./pwn.sage

decoded asn1.
done with huge exponentiation.

p = 0xe5e99b73e1342107941b90b8b707e784eea7c2422d3a350b748776e31aef0e6[...]
q = 0xec5b07c03300cca94083a838da72d57fd78da1d4568c1434ce1e579b3324dca[...]
d := 0x13cb09f3b9ebf0fbac237b59c19ccecff14d0b3af1905309451292ad57df21e[...]

real    7m43.803s
user    7m42.330s
sys     0m1.337s

$ ssh -i id_rsa.good -p 1122 ctf@1.ctf.link
[...]

    hxp{n0T_ev3N_j4vA_B1gNum_c4n_h0lD_mY_k3yZ}

$