# UMDCTF 2025

In this year's UMDCTF, I participated with team [SNI](https://ctftime.org/team/279998/) and mostly did Cryptography and PPC problems. We manage to secured fourth place and barely snagged the consolation prize.

## Cry/Obsidian
This challenge involves an encryption scheme spanning two fields by doing addition and bit rotation.

from Crypto.Util.number import bytes_to_long
import os

def rot(n, r):
    return (n >> r) | ((n << (256 - r) & (2**256 - 1)))

round_constants = [3, 141, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27, 9, 50, 28, 84, 197, 169, 39, 93, 75]

M = 2**256

def encrypt(key, block):
    for i in range(24):
        block = (block + key) % M
        block = rot(block, round_constants[i])
    return block

key = os.urandom(32)
key = bytes_to_long(key)

p1 = b'please like and subscribe!!!!!!!'
p2 = b'UMDCTF{REDACTED}'
assert(len(p1) <= 32)
assert(len(p2) <= 32)

c1 = encrypt(key, bytes_to_long(p1))
c2 = encrypt(key, bytes_to_long(p2))

print(c1)
print(c2)

We are given one pair of plaintext and ciphertext, and we need to decrypt the flag. At first glance, it seems like the block and the key are not mixed well together, and we might be able to get approximated results of encryption by doing `encrypt(key, block) = encrypt(key, 0) + encrypt(0, block) + c` for some error `c`. After trying this out, it seems like the bit count of `c` tends to be small. Given that we may not need to decrypt `p2` precisely, we can give this a go.

from Crypto.Util.number import bytes_to_long
import os

def rot(n, r):
    return (n >> r) | ((n << (256 - r) & (2**256 - 1)))

round_constants = [3, 141, 59, 26, 53, 58, 97, 93, 23, 84, 62, 64, 33, 83, 27, 9, 50, 28, 84, 197, 169, 39, 93, 75]

M = 2**256

def encrypt(key, block):
    for i in range(24):
        block = (block + key) % M
        block = rot(block, round_constants[i])
    return block

def decrypt(key, block):
    for i in range(24):
        block = rot(block, 256 - round_constants[23-i])
        block = (block - key) % M
    return block % M


ct1 = 19970192951896076587357270489167937916618022198129516743091736664525698125224
ct2 = 78876026922201259108741049564691635166471597880603787944801336451046144103203

p1 = b'please like and subscribe!!!!!!!'
p2 = b'UMDCTF{REDACTED}'

cb = encrypt(0, bytes_to_long(p1))

k = ct1 - cb
print(k)
res = (ct2 - k) % M
res = decrypt(0, res)
from libnum import n2s
print(n2s(res))
#b'YMDCTFsdiamon\\_p\x89ckaxu_no_w\xe1i!!\x85'
# UMDCTF{diamond_pickaxe_no_way!!}

After some simple calculation, we got a pretty close approximation of the flag, and with a little bit of guessing, we found the flag.

## Cry/Prime Sponsorship
This is another challenge where we are given values from two different fields. The crux of the challenge is in the key generation.

import random
from Crypto.Util.number import bytes_to_long, long_to_bytes
from sage.arith.misc import crt

p1 = 211
p2 = 223
q = 1511

# strip UMDCTF{}\n
flag = open('flag.txt', 'rb').read()[7:-2]

def encode(msg):
    m = bin(bytes_to_long(msg))[2:].zfill(p1)
    return [0 if c == '0' else 1 for c in m]


Fq = GF(q)
F3 = GF(3)
Rq = PolynomialRing(Fq, 'x').quotient(x^p1 - x - 1)
R3 = PolynomialRing(F3, 'x').quotient(x^p1 - x - 1)

Rq_2 = PolynomialRing(Fq, 'x').quotient(x^p2 - x - 1)
R3_2 = PolynomialRing(F3, 'x').quotient(x^p2 - x - 1)

Rx.<x> = PolynomialRing(ZZ, 'x')
Qx = PolynomialRing(QQ, 'x')

# keygen
h1, h2 = None, None
g_inv, f = None, None
while True:
    g = Rx([random.choice([-1,0,1]) for _ in range(p1)])
    g3 = R3(g)
    g3_2 = R3_2(g)
    if g3.is_unit() and g3_2.is_unit():
        g_inv = pow(g3, -1)
        f = Rx([random.choice([-1,0,1]) for _ in range(p1)])
        h1 = Rq(g) / Rq(3 * f)
        h2 = Rq_2(g) / Rq_2(3 * f)
        break

def round3(poly):
    new_poly = []
    for c in poly.list():
        c = ZZ(c)
        if c % 3 == 1:
            new_poly.append(c - 1)
        elif c % 3 == 0:
            new_poly.append(c)
        else:
            new_poly.append(c+1)
    return Rq(new_poly)


def encrypt(r):
    return round3(h1 * Rq(r))

def decrypt(ct, f, g_inv):
    e = Rq(3 * f) * ct
    e = [c.lift_centered() for c in e]
    print("e = ", e)
    return list(g_inv * R3(e))


print("With our new PRIME sponsorship, we bundled an extra public key for you*!")
print()

print("pk1 =", h1.list())
print("pk2 =", h2.list())

msg = encode(flag)
ct1 = encrypt(msg)

print("ct =", ct1.list())

print("*ciphertext not included")
        

The challenge gives `h1` and `h2`, and we can retrieve the flag if we can recover secrets `g` and `f`. We have, in `GF(1511)`:
- `h1 * 3f = g mod (x^211 - x - 1) = g mod f1(x)`
- `h2 * 3f = g mod (x^223 - x - 1) = g mod f2(x)`

First, let's look at how `h1 * 3f mod f1(x)` will be calculated. For each element of `f`, we can compute the result of `h1 * 3 * f_i * x^i mod f1(x)` which will have degree `211`. Similarly, for `h2 * 3f mod f2(x)`, we can compute the result of `h2 * 3 * f_i * x^i mod f2(x)` with degree `223`. Lastly, note that with the correct `f`, the difference of the two results should be zero.

Now, note that each element of `f` is in `{-1, 0, 1}`. Thus, we can just calculate `h1 * 3 * x^i mod f1(x)` and `h2 * 3 * x^i mod f2(x)` for each `i` up to `211` and find a linear combination that evaluates to zero. This is equivalent to solving for the left kernel. Also note that `f` is of degree `211` so there is no need to compute up to degree `223`.

import random
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha256

p1 = 211
p2 = 223
q = 1511

# strip UMDCTF{}\n
flag = open('flag.txt', 'rb').read()[7:-2]

def encode(msg):
    m = bin(bytes_to_long(msg))[2:].zfill(p1)
    return [0 if c == '0' else 1 for c in m]

def decode(bits):
    # Convert list of 0s and 1s back into a binary string
    bin_str = ''.join(str(b) for b in bits)
    # Convert binary string to integer
    n = int(bin_str, 2)
    # Convert integer back to bytes
    return long_to_bytes(n)


Fq = GF(q)
F3 = GF(3)
Rf = PolynomialRing(Fq, 'x')
Rq = PolynomialRing(Fq, 'x').quotient(x^p1 - x - 1)
R3 = PolynomialRing(F3, 'x').quotient(x^p1 - x - 1)

Rq_2 = PolynomialRing(Fq, 'x').quotient(x^p2 - x - 1)
R3_2 = PolynomialRing(F3, 'x').quotient(x^p2 - x - 1)

Rx.<x> = PolynomialRing(ZZ, 'x')
Qx = PolynomialRing(QQ, 'x')

def round3(poly):
    new_poly = []
    for c in poly.list():
        c = ZZ(c)
        if c % 3 == 1:
            new_poly.append(c - 1)
        elif c % 3 == 0:
            new_poly.append(c)
        else:
            new_poly.append(c+1)
    return Rq(new_poly)


def encrypt(r):
    return round3(h1 * Rq(r))

def decrypt(ct, f, g_inv):
    e = Rq(3 * f) * ct
    e = [c.lift_centered() for c in e]
    print("e = ", e)
    return list(g_inv * R3(e))

from output import pk1, pk2, ct

h1 = Rq(pk1)
h2 = Rq_2(pk2)

h2x = h2 * 3
h1x = h1 * 3

mat = []
for i in range(p1):
    h1l = list(h1x)[:p1]
    h2l = list(h2x)[:p2]
    diff = [i - j % q for i, j in zip(h1l, h2l)]
    
    mat.append(diff)

    h1x = h1x * x
    h2x = h2x * x

print("Kerneling")
M = Matrix(GF(q), mat)
R = M.left_kernel()
res = R.basis()
print("found sols: ", len(res))
print(res)
f = [i.lift_centered() for i in res[0]]

print("Got kernel", f)

g = h1 * Rq(f) * 3
print("Got g", list(g))
g = [i.lift_centered() for i in g]
g3 = R3(g)
g_inv = pow(g3, -1)

dec = decrypt(Rq(ct), Rq(f), g_inv)
print(decode(dec))

#UMDCTF{no_logan_paul_here}

After solving for `f` and `g`, we can just compute the flag using the given decryption algorithm.

## nyt/evaldle

This challenge presents a pyjail that limits input to five characters.

#!/usr/local/bin/python
f = open('flag.txt').read()

target = 'SIGMA'

while True:
    guess = input("Guess: ")
    if len(guess) != 5:
        print("Invalid guess.")
        continue
    for j in range(5):
        if target[j] == guess[j]:
            print('🟩', end='')
        elif guess[j] in target[j]:
            print('🟨', end='')
        else:
            print('⬛', end='')
    print('')
    try:
        exec(guess)
        print('🟩🟩🟩🟩🟩')
    except:
        print("🟥🟥🟥🟥🟥")     

One important feature to exploit is the try except block. We can leak some information with the following idea:
1. We can assign any string to a variable by doing:
- `A='' `
- `Z='c'`
- `A+=Z `
- Repeat
2. We can save the `chr` function to a variable:
- `I=chr`
3. We can compare strings to flag and output the result:
- `C=A>f`
- `C=C-1`
- `I(C) `

The final `chr` invocation will throw if `C` is negative, and will not throw if `C` is zero. Thus, we can compare strings to the flag, and we can do this by brute force or binary search.

from azunyan.conn import process, remote
import string

#r = process(['python3', 'evaldle.py'])#, level='debug')
r = remote('challs.umdctf.io', 31601)

def send(s: str, verify: bool = True):
    if len(s) < 5: s += ' ' * (5 - len(s))
    r.sendlineafter(b'Guess:', s.encode())
    r.recvline()
    res = r.recvline().decode()
    f = '🟩' in res
    if verify: assert(f)
    return '🟩' in res

charset = string.ascii_lowercase + string.ascii_uppercase + string.digits + "{}_"
charset = sorted(charset)

known: str = ''

def gen_str(target: str):
    send('A=""')
    for c in target:
        send(f"Z='{c}'")
        send(f"A=A+Z")
        
def append_gen(char: str):
    send(f"Z='{char}'")
    send('A=A+Z')
        
def init():
    send("I=chr")

def append_str(char: str):
    send(f"Z='{char}'")
    send('B=A+Z')

def query_big():
    send('C=B<f')
    send('C=C-1')
    return send('I(C)', False)

def binser(known: str):
    l = 0
    r = len(charset) - 1
    while l < r:
        mid = (l + r) // 2
        append_str(charset[mid])
        res = query_big()
        if res: l = mid+1
        else: r = mid
        print(l, r, end='\n')    
    return charset[l-1]
    
init()
known = 'UMDCTF{that_took_a_lot_more_than_six_guess'
print("Setting up")
gen_str(known)
print(charset)

while len(known) == 0 or known[-1] != '}':
    res = binser(known)
    known = known + res
    append_gen(res)
    print(f"Known={known}")
    
#UMDCTF{that_took_a_lot_more_than_six_guesses}

Binary search is preferred as remote queries can take some time.

## nyt/spindle
We are tasked with solving the [Spindle](https://playspindle.com/) puzzle optimally. After some trial and error, it seems like we need to solve it in 8 moves.


As the solution needs to be optimal, we can write some BFS algorithm to find a solution. I eventually went with brute force BFS with pruning on a distance metric. The distance itself is calcualted based on how far the board is from making the target word "FANUM", and is estimated by the lower bound as follows:

def distance(self):
    target = "FANUM"
    dist = 0
    for i in range(5):
        c = target[i]
        if c == self.state[0][i]: continue
        elif c in self.state[0]: dist += 1
        elif c in [self.state[idx][i] for idx in range(5)]: dist += 1
        else: dist += 2
    return dist

The logic is based on the fact that a character can only be moved column-wise or row-wise with a single move (not both), so if a character is not in the same column and row as the targetted cell, it will take at least two moves to move it there. With the same logic, it will take at least one move if the character is in the same column or row.

Note that this calculation is not the actual lower bound, as multiple characters can be moved within the same row or column at once.

words = open('dictionary.txt').readlines()
dictionary = [w.strip() for w in words]
visited = set()
class Spindle:
    state = [
        list("FAHEM"),
        list("KAELB"),
        list("VNTKE"),
        list("OGUYU"),
        list("PJPFN")
    ]
    
    def __init__(self, state: str = None):
        if state is None: return
        for i in range(5):
            for j in range(5):
                self.state[i][j] = state[i * 5 + j]
    
    def get_state(self):
        res = ''
        for i in range(5):
            for j in range(5):
                res += self.state[i][j]
        return res
    
    def get_moves(self):
        #horizontal
        valid_moves = []
        moves = []
        for i in range(5):
            for j in range(5):
                for l in range(2, 6):
                    if j + l > 5: break
                    word = ''.join(self.state[i][j:j+l])
                    if word in dictionary:
                        valid_moves.append(word)
                        moves.append((i, j, l, True))
                    if word[::-1] in dictionary:
                        valid_moves.append(word[::-1])
                        moves.append((i, j, l, True))
        
        
        #vertical
        for i in range(5):
            for j in range(5):
                for l in range(2, 6):
                    if i + l > 5: break
                    word = ''.join([self.state[a][j] for a in range(i, i+l)])
                    
                    if word in dictionary:
                        valid_moves.append(word)
                        moves.append((i, j, l, False))
                    if word[::-1] in dictionary:
                        valid_moves.append(word[::-1])
                        moves.append((i, j, l, False))
        
        return moves, valid_moves
    
    def play_move(self, move):
        ix, jy, l, isHori = move
        
        new_state = [[a for a in b] for b in self.state]
        
        # horizontal
        if isHori:
            letters = [self.state[ix][jy + i] for i in range(l)]
            rotated = letters[::-1]

            for i in range(l):
                new_state[ix][jy + i] = rotated[i]
                
        # vertical
        else:
            letters = [self.state[ix + i][jy] for i in range(l)]
            rotated = letters[::-1]
            for i in range(l):
                new_state[ix + i][jy] = rotated[i]
                
        self.state = [[b for b in c] for c in new_state]
        
    def distance(self):
        target = "FANUM"
        dist = 0
        for i in range(5):
            c = target[i]
            if c == self.state[0][i]: continue
            elif c in self.state[0]: dist += 1
            elif c in [self.state[idx][i] for idx in range(5)]: dist += 1
            else: dist += 2
        return dist

    
game = Spindle()
visited.add(game.get_state())

moves, words = game.get_moves()

games: list[Spindle] = [(Spindle(game.get_state()),[move]) for move in moves]

for i in range(len(moves)):
    games[i][0].play_move(moves[i])

from tqdm import tqdm
start_move = 3
for it in range(10):
    new_games = []
    
    print(f"Found {len(games)} games")
    for gh in tqdm(games):
        game, history = gh
        if game.distance() + start_move + it > 8: continue
        if game.get_state() in visited: continue
        visited.add(game.get_state())
        moves, words = game.get_moves()
        if "FANUM" in words:
            print("Found")
            print(game.state)
            print(history)
            exit(0)
        cur_new_games: list[Spindle] = [(Spindle(game.get_state()), history + [move])for move in moves]
        for i in range(len(moves)):
            cur_new_games[i][0].play_move(moves[i])
        
        new_games += cur_new_games
    
    games = [g for g in new_games]
    print(f"Next {len(games)} games")
    
print("Failed")

Eventually, a solution is found by guessing the first three moves (by trial and error) and running the solver.