Pickme - Crypto

Points: 316 | Flag: BCCTF{R54_Br0K3n_C0nF1rm3d????} | Solved by: Smothy @ 0xN1umb

what we got

nc service + a server.py. The server lets you submit an RSA private key in PEM format, runs a bunch of validation checks on it, then encrypts the flag with YOUR key. If decryption fails, it leaks the ciphertext. Classic "find the edge case" crypto challenge.

key = load_pem_private_key(
    pem,
    password=None,
    backend=default_backend(),
    unsafe_skip_rsa_key_validation=True,  # 👀👀👀
)

and the juicy part:

m = FLAG
c = pow(m, pub.e, pub.n)
if m != pow(c, priv.d, pub.n):
    return f"Some unknown error occurred! Maybe you should take a look: {c}"

so if decryption fails we get the ciphertext. nice. but all the checks look solid:

• p, q must be prime and >= 512 bits
• n = p*q
• e >= 65537, prime, at most 2 bits set (so basically e = 65537)
• d is valid inverse of e mod phi
• CRT components checked

the solve

ok so i stared at this for a bit thinking "if all checks pass, RSA should just work right??" and then it hit me

there's no check that p != q

if we set p = q (same prime), then n = p^2 and phi = (p-1)^2. all the validation still passes because:

• both are prime ✅
• both >= 512 bits ✅
• n = p*q = p^2 ✅
• phi = (p-1)(q-1) = (p-1)^2 ✅
• d = e^(-1) mod (p-1)^2 ✅

BUT rsa decryption breaks on n = p^2. here's why: euler's totient of p^2 is actually p(p-1), not (p-1)^2. so when we compute d as the inverse of e mod (p-1)^2, the math doesn't work out mod p^2 anymore. decryption fails, and we get the ciphertext leaked.

then since we know p, and the flag is way smaller than p (it's like 31 bytes vs a 512-bit prime), we just decrypt mod p:

ez

the only tricky part is iqmp (inverse of q mod p) - when p = q this doesn't exist since q mod p = 0. but unsafe_skip_rsa_key_validation=True lets us put whatever we want there, and the server never checks it lmao

from pwn import *
from Crypto.Util.number import getPrime, GCD, long_to_bytes
from cryptography.hazmat.primitives.asymmetric.rsa import RSAPrivateNumbers, RSAPublicNumbers
from cryptography.hazmat.primitives.serialization import Encoding, PrivateFormat, NoEncryption

# p = q, same prime. rsa is cooked
p = getPrime(512)
q = p
n = p * q  # = p^2
e = 65537
phi = (p - 1) * (q - 1)  # = (p-1)^2, NOT phi(p^2) = p(p-1)
d = pow(e, -1, phi)
dp = d % (p - 1)
dq = dp  # same since p=q
iqmp = 1  # doesn't exist but who cares

pub_numbers = RSAPublicNumbers(e, n)
priv_numbers = RSAPrivateNumbers(p, q, d, dp, dq, iqmp, pub_numbers)
key = priv_numbers.private_key(unsafe_skip_rsa_key_validation=True)
pem = key.private_bytes(Encoding.PEM, PrivateFormat.TraditionalOpenSSL, NoEncryption())

io = remote('chal.bearcatctf.io', 56025)
io.recvuntil(b'Enter your key in pem format:\n')
for line in pem.strip().split(b'\n'):
    io.sendline(line)

response = io.recvall(timeout=5)
c = int(response.split(b'look: ')[1].strip())

# decrypt mod p since FLAG < p
d_p = pow(e, -1, p - 1)
flag = long_to_bytes(pow(c % p, d_p, p))
print(flag)

first try baby

flag

BCCTF{R54_Br0K3n_C0nF1rm3d????}

ngl the ???? in the flag is fitting because thats exactly the face i made when i realized p=q just... works. like the server checks EVERYTHING except the one thing that actually matters. unsafe_skip_rsa_key_validation doing the heavy lifting for us here fr

the math behind it is kinda beautiful tho - RSA fundamentally relies on n being a product of TWO DISTINCT primes. the moment p = q, the totient changes from (p-1)(q-1) to p(p-1) and the whole thing falls apart. R54 Br0K3n C0nF1rm3d indeed 💀

smothy out ✌️