Small StEps

2 minutes to read

We are given a remote instance to connect to:

$ nc 188.166.152.84 32213
This is the second level of training.  

[E]ncrypt the flag.
[A]bort training.

>

We are also provided with the server’s Python source code:

from Crypto.Util.number import getPrime, bytes_to_long

FLAG = b"HTB{???????????????}"
assert len(FLAG) == 20


class RSA:

    def __init__(self):
        self.q = getPrime(256)
        self.p = getPrime(256)
        self.n = self.q * self.p
        self.e = 3

    def encrypt(self, plaintext):
        plaintext = bytes_to_long(plaintext)
        return pow(plaintext, self.e, self.n)


def menu():
    print('[E]ncrypt the flag.')
    print('[A]bort training.\n')
    return input('> ').upper()[0]


def main():
    print('This is the second level of training.\n')
    while True:
        rsa = RSA()
        choice = menu()

        if choice == 'E':
            encrypted_flag = rsa.encrypt(FLAG)
            print(f'\nThe public key is:\n\nN: {rsa.n}\ne: {rsa.e}\n')  
            print(f'The encrypted flag is: {encrypted_flag}\n')
        elif choice == 'A':
            print('\nGoodbye\n')
            exit(-1)
        else:
            print('\nInvalid choice!\n')
            exit(-1)


if __name__ == '__main__':
    main()

The server is using RSA to encrypt the flag (option E):

$ nc 188.166.152.84 32213
This is the second level of training.

[E]ncrypt the flag.
[A]bort training.

> E

The public key is:

N: 7802670787708982338810401265270821632177774801121169070488418066304851188120043397642742488240419069460959080124871803486562849954805729201222419964291931
e: 3

The encrypted flag is: 70407336670535933819674104208890254240063781538460394662998902860952366439176467447947737680952277637330523818962104685553250402512989897886053

RSA background

RSA works so that, given a message $m$ in decimal format, we can encrypt it as follows:

$$ c = m^e \mod{n} $$

The public key is formed by $n$ and $e$. And $n = p \cdot q$, which are two big primes (kept as private key).

On the other hand, the decryption needs two more values: $\phi(n) = (p - 1) (q - 1)$ and $d = e^{-1} \mod{\phi(n)}$, so that:

$$ m = c^d \mod{n} $$

The security flaw

This time, we have $e = 3$, which is not recommended in RSA. The problem is that if the message $m \ll n$, then computing $m^e$ over the integers will still be smaller than $n$. Therefore, applying modulo $n$ does not provide security since $m^3 = m^3 \mod{n}$.

Cube Root Attack

The attack to solve this challenge is known as Cube Root Attack, and it is self-explanatory. We only need to compute $m = \sqrt[3]{c}$ because of what we explained before. This operation can be done using module gmpy2 from Python:

$ python3 -q
>>> from gmpy2 import iroot
>>>
>>> c = 70407336670535933819674104208890254240063781538460394662998902860952366439176467447947737680952277637330523818962104685553250402512989897886053  
>>> e = 3
>>>
>>> iroot(c, e)
(mpz(412926389432612660984016953290834154417829082237), True)

Since iroot returns True, the result of the cube root is exact.

Flag

Now, we only need to convert $m$ to bytes to capture the flag:

>>> m = iroot(c, e)[0]
>>> bytes.fromhex(hex(m)[2:])  
b'HTB{5ma1l_E-xp0n3nt}'