cryptofreehard

no-brainrot-allowed

umdctf

Task: a remote textbook-RSA service decrypts chosen ciphertexts and only reveals whether the plaintext's minimal hex form begins with 67. Solution: characterize that leak as a union-of-intervals oracle, combine it with RSA multiplicative malleability and the known prefix UMDCTF{, and run a Bleichenbacher-style adaptive interval attack until one plaintext remains.

$ ls tags/ techniques/
rsatextbook_rsachosen_ciphertextrsa_oraclehex_prefixinterval_oracle
rsa_malleabilityoracle_characterizationbleichenbacher_style_interval_attackprefix_interval_narrowingadaptive_comparison_queries

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

no-brainrot-allowed — UMDCTF

Description

No separate organizer statement was preserved in the workspace files.

English summary: the challenge exposes a remote RSA service at nc challs.umdctf.io 32767 and provides the source in server.py. The server prints the RSA-encrypted flag, then accepts comma-separated ciphertexts and tells us only whether the decrypted plaintext looks like "brainrot" according to a hex-prefix rule.

Useful artifacts already present locally:

  • tasks/umdctf/no-brainrot-allowed/server.py
  • tasks/umdctf/no-brainrot-allowed/solve.py
  • source URL: https://umdctf2026-uploads.storage.googleapis.com/uploads/b2831e73d8ee9c6826840edb3a8af043396fd7e31fe2306dda7f4545cc77ca33/server.py

Analysis

The service uses textbook RSA:

flag = bytes_to_long(flag_bytes)
ct = pow(flag, e, n)

Then it decrypts any user-supplied ciphertext with the secret exponent d and checks only this condition:

pt = hex(pow(user_ct, d, n))
if pt.startswith("0x67"):
    print("ERROR: BRAINROT DETECTED. THIS INCIDENT WILL BE REPORTED.")
else:
    print("The UMDCTF team thanks you for your message!")

There is no padding, so RSA is multiplicatively malleable. If the flag ciphertext is ct = m^e mod n, then querying

ct' = ct * s^e mod n

decrypts to

m' = s * m mod n.

So even though the oracle does not return plaintext bytes, it leaks a one-bit property of carefully transformed versions of the unknown flag integer.

Oracle Characterization

The important subtlety is that Python's hex() uses the minimal hexadecimal representation. The oracle does not test a fixed byte prefix; it tests whether the first hex digits of the integer are 67.

Manual probing shows that all of these trigger the oracle:

  • 0x67
  • 0x670
  • 0x678

Therefore the accepted set is not a single interval. It is the union

m in [0x67 * 16^k, 0x68 * 16^k)   for some k >= 0.

To turn this into something useful, the solve script fixes one large band:

...

$ grep --similar

Similar writeups