Small StEps

2 minutos de lectura

Se nos proporciona una instancia remota para conectarnos:

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

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

>

También se nos proporciona el código fuente de Python del servidor:

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()

El servidor está utilizando RSA para cifrar la flag (opción 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

Explicación de RSA

RSA funciona de forma que, dado un mensaje $m$ en formato decimal, podemos cifrarlo de la siguiente manera:

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

La clave pública está formada por $n$ y $e$. Y $n = p \cdot q$, que son dos números primos grandes (mantenidos como clave privada).

Por otro lado, para descifrar se necesitan dos valores más: $\phi(n) = (p - 1) (q - 1)$ y $d = e^{-1} \mod{\phi(n)}$, de manera que:

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

El fallo de seguridad

Esta vez tenemos $e = 3$, que no se recomienda en RSA. El problema es que si el mensaje $m \ll n$, Entonces calcular $m^e$ sobre los enteros seguirá siendo más pequeño que $n$. Por lo tanto, la aplicación de módulo $n$ no proporciona seguridad ya que $m^3 = m^3 \mod{n}$.

Ataque de la raíz cúbica

El ataque para resolver este reto se conoce como ataque de raíz cúbica, y se explica por sí mismo. Solo necesitamos calcular $m = \sqrt[3]{c}$ por lo que explicamos antes. Esta operación se puede realizar mediante el módulo gmpy2 de Python:

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

Como iroot devuelve True, el resultado de la raíz cúbica es exacta.

Flag

Ahora, solo necesitamos convertir $m$ en bytes para capturar la flag:

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