NNS CTF: parcellocker, small RSA signatures

Challenge

These new parcel lockers promise convenience: no queues, no staff, and 24/7 access. Everything is managed through a web UI, complete with API documentation at /api/docs. Your task as a user is simple: open the app, claim your parcel, and the assigned locker slot will unlock.

However, rumours are spreading - someone has already found a way to open any slot in any locker. Can you do it too?

  • Category: crypto
  • Difficulty: easy
  • Flag: NNS{th4nkfully_th15_w0uldn7_h4pp3n_1n_r34l_l1f3_r1gh7?_r1gh7?}

The service is three containers behind an nginx proxy: a Svelte frontend, the API, and the backend holding the lockers. The frontend asks the API for your parcel and then lets you open any locker by presenting a signature for its id. The relevant parts of the backend:

while 1:
    p = getPrime(128)
    q = getPrime(128)
    n = p * q
    if q != p and n.bit_length() >= 256:
        break

e = 2**16 + 1

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# 3 boxes, 2 columns and 6 rows
package_count = 3 * 2 * 6
package_store = [
    "Aldri for sent å snu",
    ...
    "Den som venter på noe godt, venter ikke forgjeves: " + FLAG,
    ...
]
random.shuffle(package_store)


def as_message(id: int) -> int:
    return bytes_to_long(str(id).encode("utf-8"))


def verify(id: int, sig: int) -> bool:
    return as_message(id) == pow(sig, e, n)


@app.get("/open/{id}")
def open_box(id: int, sig: str):
    if id not in range(len(package_store)):
        return {"id": id, "success": False, "content": "No ParcelBox exists with the given ID"}

    try:
        signature = int(sig, 16)
    except ValueError:
        return {"id": id, "success": False, "content": "Failed converting [sig] from hex to decimal"}

    if not verify(id, signature):
        return {"id": id, "success": False, "content": "Signature verification failed"}

    return {"id": id, "success": True, "content": package_store[id]}


@app.get("/my_parcel")
def get_own_parcel():
    id = package_store.index("Den som gir seg, har tapt på forhånd")
    assert id >= 0

    m = as_message(id)
    sig = pow(m, d, n)

    return {"id": id, "sig": hex(sig), "n": hex(n), "e": hex(e)}

I made this one for NNS CTF 2025.

Analysis

The signature scheme is fine. The vulnerability is the size of the key: a 256-bit composite number is easily factorized with modern tools and hardware.

Input to vulnerability

GET /api/my_parcel calls get_own_parcel(), which returns {id, sig, n, e} - a valid signature for your own locker, plus the public modulus. n is only 256 bits (the product of two 128-bit primes), so factoring it recovers p and q, and the private exponent follows directly:

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

Exploit to execution

Sign every id with sign(id) = pow(as_message(id), d, n), send it to /api/open/{id}?sig=..., and read package_store[id]. Every locker opens; the flag sits in locker 8, behind the proverb “Den som venter på noe godt, venter ikke forgjeves: …”.

Exploit

from Crypto.Util.number import bytes_to_long
from Crypto.PublicKey import RSA
import requests

# Recover the private key from the factored n
privkey = RSA.import_key("""-----BEGIN RSA PRIVATE KEY-----
...
-----END RSA PRIVATE KEY-----""")

d, e, n = privkey.d, privkey.e, privkey.n


def sign(id: int) -> int:
    m = bytes_to_long(str(id).encode("utf-8"))
    return pow(m, d, n)


for id in range(36):
    sig = sign(id)
    box = requests.get(
        f"http://<instance>/api/open/{id}", params={"sig": hex(sig)}
    )
    print(box.json())

Factoring the 256-bit modulus is the bottleneck.