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:

K = 254
A = 103 << (4 * K)   # 0x67 * 16^254
B = 104 << (4 * K)   # 0x68 * 16^254

and chooses query parameters so that the decrypted value lands either inside or outside exactly this band. That converts the weird prefix predicate into a comparison oracle for the original plaintext.

Attack Strategy

The successful attack is a Bleichenbacher-style interval attack, but driven by a prefix oracle instead of PKCS#1 padding.

1. Start from the known prefix only

The flag begins with UMDCTF{, but the total length is unknown. For a guessed total length L, let

t = L - len("UMDCTF{")

Then the plaintext must satisfy

PREFIX * 256^t <= m <= (PREFIX + 1) * 256^t - 1.

This gives one narrow initial interval per candidate length.

An early false start assumed the flag must end with } and used that suffix to prune lengths aggressively. That accidentally eliminated the real solution for all tested lengths up to 80. The robust version kept only the guaranteed prefix and let the oracle do the rest.

2. Turn the prefix test into a threshold test

For each active interval [lo, hi], the solve script chooses integers r and s so that

A <= s*m - r*n < B

is equivalent to a split near the middle of the current interval. Since querying ct * s^e mod n decrypts to s*m mod n, the oracle tells us whether s*m mod n falls into [A, B), which is the same as asking whether m is on one side of a computed threshold.

In the script this logic lives in choose_params(lo, hi), which returns:

• r: the wrap count modulo n
• s: the RSA multiplier to apply in the ciphertext domain
• threshold: the value used to shrink [lo, hi]

If the oracle is positive, keep the lower half; otherwise keep the upper half.

3. Track every plausible length at once

The script initializes states for every candidate total length:

for total_len in range(MIN_LEN, MAX_LEN + 1):
    tail_len = total_len - len(PREFIX)
    lo = PREFIX_INT << (8 * tail_len)
    hi = ((PREFIX_INT + 1) << (8 * tail_len)) - 1

Each length gets its own interval, and each round asks one oracle question for each surviving length hypothesis.

4. Batch queries aggressively

The service accepts comma-separated ciphertexts in one line, so the exploit batches many queries per request and also keeps multiple TCP connections open in parallel. That makes the interval attack practical instead of painfully slow.

5. Finish by brute force when intervals get tiny

When a candidate interval becomes small enough, the script simply tests candidates locally by re-encrypting them with the public key and checking whether they match the original ciphertext.

That final check confirms both the correct length and the exact plaintext. The recovered flag length was 111 bytes.

Exploit

The local exploit already present in the workspace is the full working solution:

#!/usr/bin/env python3
import concurrent.futures
import socket
import gmpy2
from Crypto.Util.number import bytes_to_long, long_to_bytes

HOST = "challs.umdctf.io"
PORT = 32767

n = 89496838321330017124211425752928111009238414395285545597372895783391482460166014550795440784240669454038164776392492949832230406030665778241454645944939829559549747525412818621247626093163657213524408194055221128159991890855776297338418179985226639927931716465641085590302394062423554511419578835789906477703
e = 65537
ct = 7754782549233547741892262011884269269634473224225227064848605234096464292342695844400918832869742989785685496372442722948589824059885664742180188925993430350247652395812127146595142859972102395302095473677093880196683037670451512853001503582104512714892761518926915267957380484576367984853786495267989619184
GN = gmpy2.mpz(n)
GE = gmpy2.mpz(e)
GCT = gmpy2.mpz(ct)

PREFIX = b"UMDCTF{"
PREFIX_INT = bytes_to_long(PREFIX)

K = 254
A = 103 << (4 * K)
B = 104 << (4 * K)

MIN_LEN = 8
MAX_LEN = 127
BRUTE_THRESHOLD = 200000
PARALLEL_ORACLES = 32


def ceildiv(a: int, b: int):
    return -(-a // b)


def ciphertext_for_multiplier(s: int):
    return int((GCT * gmpy2.powmod(gmpy2.mpz(s), GE, GN)) % GN)


def is_flag_candidate(m: int):
    return int(gmpy2.powmod(gmpy2.mpz(m), GE, GN)) == ct


def choose_params(lo: int, hi: int):
    mid = (lo + hi) // 2
    s = (B - 1) // mid
    if 0 < s < n:
        threshold = (B - 1) // s
        if s * lo >= A and s * hi < min(n, 16 * A) and lo <= threshold < hi:
            return 0, s, threshold

    width = max(1, hi - lo)
    estimate = max(0, (mid * mid) // (n * width))
    for delta in (128, 2048, 32768):
        start = max(0, estimate - delta)
        end = estimate + delta
        for r in range(start, end + 1):
            lower = max(ceildiv(r * n + A, lo), ((r * n + B - 1) // hi) + 1)
            upper = min((((r + 1) * n) - 1) // hi, (r * n + B - 1) // lo)
            if lower > upper or lower <= 0 or lower >= n:
                continue

            target = (r * n + B - 1) // mid
            s = min(max(target, lower), upper)
            threshold = (r * n + B - 1) // s
            if s * lo >= r * n + A and s * hi < (r + 1) * n and lo <= threshold < hi:
                return r, s, threshold

    raise RuntimeError(f"failed to choose params for interval {lo}..{hi}")


class Oracle:
    def __init__(self, host: str, port: int, verbose: bool = True):
        self.host = host
        self.port = port
        self.verbose = verbose
        self.sock = None
        self.buf = b""
        self.connect()

    def connect(self):
        if self.sock is not None:
            try:
                self.sock.close()
            except Exception:
                pass
        self.sock = socket.create_connection((self.host, self.port))
        self.sock.settimeout(15)
        self.buf = b""
        banner = self._recv_until_prompt()
        if self.verbose:
            print(banner.decode(errors="replace"), end="")

    def _recv_to_buffer(self):
        chunk = self.sock.recv(65536)
        if not chunk:
            raise ConnectionError("connection closed")
        self.buf += chunk

    def _recv_until_prompt(self):
        marker = b"Your messages: "
        while marker not in self.buf:
            self._recv_to_buffer()
        data, self.buf = self.buf.split(marker, 1)
        return data

    def query_batch(self, ciphertexts):
        payload = ",".join(str(c) for c in ciphertexts).encode() + b"\n"
        for attempt in range(2):
            try:
                self.sock.sendall(payload)
                data = self._recv_until_prompt().decode(errors="replace")
                verdicts = []
                for line in data.splitlines():
                    if "BRAINROT DETECTED" in line:
                        verdicts.append(True)
                    elif "thanks you for your message" in line:
                        verdicts.append(False)
                if len(verdicts) != len(ciphertexts):
                    raise RuntimeError(f"expected {len(ciphertexts)} verdicts, got {len(verdicts)}")
                return verdicts
            except (BrokenPipeError, ConnectionError, OSError, TimeoutError, socket.timeout):
                if attempt == 1:
                    raise
                print("[!] Connection dropped, reconnecting")
                self.connect()
        raise RuntimeError("unreachable")


def initial_states():
    states = {}
    for total_len in range(MIN_LEN, MAX_LEN + 1):
        tail_len = total_len - len(PREFIX)
        if tail_len < 0:
            continue
        lo = PREFIX_INT << (8 * tail_len)
        hi = ((PREFIX_INT + 1) << (8 * tail_len)) - 1
        states[total_len] = [lo, hi]
    return states


def maybe_bruteforce(states):
    for total_len, (lo, hi) in list(states.items()):
        if lo > hi:
            del states[total_len]
            continue

        count = (hi - lo) + 1
        if count > BRUTE_THRESHOLD:
            continue

        print(f"[*] Bruteforcing len={total_len} over {count} candidates")
        for m in range(lo, hi + 1):
            if is_flag_candidate(m):
                flag = long_to_bytes(m)
                print(f"[+] Found flag at len={total_len}: {flag!r}")
                return flag
        del states[total_len]
        print(f"[-] Eliminated len={total_len}")
    return None


def main():
    states = initial_states()
    print(f"[*] Tracking {len(states)} candidate lengths")

    oracles = [Oracle(HOST, PORT, verbose=(i == 0)) for i in range(PARALLEL_ORACLES)]
    rounds = 0

    while states:
        flag = maybe_bruteforce(states)
        if flag is not None:
            try:
                print(flag.decode())
            except Exception:
                pass
            return

        batch = []
        meta = []

        for total_len, (lo, hi) in states.items():
            if lo == hi:
                if is_flag_candidate(lo):
                    flag = long_to_bytes(lo)
                    print(f"[+] Found flag at len={total_len}: {flag!r}")
                    try:
                        print(flag.decode())
                    except Exception:
                        pass
                    return
                meta.append((total_len, None, None, None))
                batch.append(0)
                continue

            r, s, threshold = choose_params(lo, hi)
            c2 = ciphertext_for_multiplier(s)
            batch.append(c2)
            meta.append((total_len, r, s, threshold))

        real_batch = []
        real_meta = []
        for entry, c2 in zip(meta, batch):
            if entry[1] is not None:
                real_meta.append(entry)
                real_batch.append(c2)

        if not real_batch:
            break

        groups = []
        start = 0
        for i in range(PARALLEL_ORACLES):
            end = start + (len(real_batch) + i) // PARALLEL_ORACLES
            groups.append((real_meta[start:end], real_batch[start:end]))
            start = end

        answers = []
        with concurrent.futures.ThreadPoolExecutor(max_workers=PARALLEL_ORACLES) as executor:
            futures = []
            for oracle, (_, batch_part) in zip(oracles, groups):
                if batch_part:
                    futures.append(executor.submit(oracle.query_batch, batch_part))
                else:
                    futures.append(None)

            for future in futures:
                if future is None:
                    continue
                answers.extend(future.result())

        idx = 0
        for total_len, r, s, threshold in meta:
            if r is None:
                del states[total_len]
                continue

            positive = answers[idx]
            idx += 1
            lo, hi = states[total_len]
            if positive:
                hi = min(hi, threshold)
            else:
                lo = max(lo, threshold + 1)
            if lo <= hi:
                states[total_len] = [lo, hi]
            else:
                del states[total_len]

        rounds += 1
        if rounds % 10 == 0:
            widths = sorted((((hi - lo) + 1), total_len) for total_len, (lo, hi) in states.items())
            smallest = widths[:5]
            largest = widths[-5:]
            print(f"[*] Round {rounds}, active lengths={len(states)}")
            print(f"    smallest candidate counts: {smallest}")
            print(f"    largest candidate counts:  {largest}")

    print("[-] No flag found")


if __name__ == "__main__":
    main()

Why the attack works

The exploit succeeds because three facts line up perfectly:

1. Textbook RSA is malleable. We can multiply the hidden plaintext by chosen values through the ciphertext.
2. The oracle leaks a structured predicate. "Hex starts with 67" sounds odd, but it still defines intervals.
3. The flag format gives a strong prefix. Knowing only UMDCTF{ is enough to initialize narrow plaintext ranges for each possible total length.

Once those are in place, the problem stops looking like factorization and starts looking like an adaptive interval-search oracle.