2023 Cyber Apocalypse: Small sTeps

Challenge Information

Summary

This challenge features a textbook RSA implementation with a critical vulnerability: the use of a small public exponent (e=3). When e is small and the message is short enough, the ciphertext is less than the modulus before taking the modulo operation, allowing direct recovery of the plaintext using cube root extraction.

Analysis

The server code implements basic RSA:

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)

Key Vulnerability: When e=3 and the plaintext is short (20 bytes), the encrypted value m^3 may be smaller than n, meaning no reduction occurs. This allows direct recovery via the cube root.

Attack Strategy:

1. Connect to the server and request encryption of the flag
2. Receive the public key (N, e=3) and ciphertext C
3. Since C = m^3 (without modulo), compute m = ∛C
4. Convert the result back to bytes to get the flag

Solution

The exploitation process:

from pwn import *

def toAscii(data):
    return data.decode().strip()

def choiceE():
    r.sendlineafter(b"> ", b"E")
    r.recvuntil(b"N: ")
    N = eval(toAscii(r.recvline()))
    r.recvuntil(b"e: ")
    e = eval(toAscii(r.recvline()))
    r.recvuntil(b"The encrypted flag is: ")
    encrypted_flag = eval(toAscii(r.recvline()))
    return N, e, encrypted_flag

def pwn():
    N, e, encrypted_flag = choiceE()

    # Since e=3 and message is small, C = m^3 without modulo
    # We can recover m by taking the cube root
    m = round(encrypted_flag ** (1/3))

    # Convert to bytes
    flag = long_to_bytes(m)
    print(flag)

if __name__ == "__main__":
    r = remote("ip", port)
    pwn()

Key Takeaways

• Small public exponents (e=2, e=3) are cryptographically weak
• When plaintext^e < n, no modular reduction occurs
• This allows direct recovery via root extraction
• Proper RSA security requires e to be at least 65537
• Message padding (PKCS#1 v1.5 or OAEP) is essential for RSA security