BronoCTF : Custom Cipher Writeup

Summary

pscheme.py implements a toy "encryption" scheme that encodes each 4-byte
chunk of the flag as extra roots multiplied directly into a public
polynomial. Because the polynomial multiplication is invertible and the
original public key is handed to you in the ciphertext, the scheme
collapses to straightforward polynomial division: divide each ciphertext
polynomial by the known public key, factor the resulting quartic to recover
the plaintext bytes, then use the appended 8-bit order field to undo the
scheme's internal shuffle. No knowledge of the private root set is needed at
all.

The Source

import cmath
import itertools
import random


class Poly:
    def __init__(self, coeff: list):
        self.coeff = coeff
        self.coeff.reverse()
        self.coeff = list(itertools.dropwhile(lambda x: x == 0, self.coeff))
        self.coeff.reverse()

        if len(self.coeff) == 0:
            self.coeff = [0]

    def get_degree(self):
        return len(self.coeff) - 1

    def __mul__(self, other):
        if other.get_degree() == 1 and other.coeff[0] == 0:
            return Poly([0])

        newdeg = self.get_degree() + other.get_degree()
        newcoeff = [0 for _ in range(newdeg + 1)]
        for i1, c1 in enumerate(self.coeff):
            for i2, c2 in enumerate(other.coeff):
                newcoeff[i1 + i2] += c1 * c2

        return Poly(newcoeff)

    def to_distrib_form(self, delim: str = " "):
        return delim.join(map(str, self.coeff[:-1]))


def keygen(root_bits: int, key_degree: int):
    private = sorted([random.randint(1, 2**root_bits - 1) for _ in range(key_degree)])
    public = Poly([1])
    for root in private:
        root_poly = Poly([-root, 1])
        public = public * root_poly
    return (private, public)


def encrypt(public: Poly, message: list[int]):
    for root in message:
        root_poly = Poly([-root, 1])
        public = public * root_poly

    order = sorted(message)
    for i, e in enumerate(order):
        ind = message.index(e)
        order[i] = ind
        message[ind] = -1
    order = sum([x << (2 * i) for i, x in enumerate(order)])

    return (public, order)


def encrypt_string(enc: str, pub: Poly):
    send_list = []
    for substr in itertools.batched(enc, 4):
        message = list(map(ord, substr))
        message += [0 for _ in range(4 - len(message))]
        to_send, order = encrypt(pub, message)
        send_list.append(to_send.to_distrib_form() + " " + str(order))
    return "/".join(send_list)


if __name__ == "__main__":
    N = 64
    B = 8
    FLAG = "bronco{REDACTED}"

    priv, pub = keygen(8, 64)
    print("====PUBLIC KEY====")
    print(pub.to_distrib_form())
    print("====MESSAGE====")
    print(encrypt_string(FLAG, pub))

Key things this tells us:

• keygen picks 64 private roots in [1, 255] and builds a monic degree-64 polynomial pub = ∏(x - root_i). pub is printed under ====PUBLIC KEY====, excluding the leading coefficient (always 1 since the polynomial is monic) — to_distrib_form drops coeff[-1].
• encrypt takes the same pub object reference for every 4-byte chunk (Python passes the reference, and public = public * root_poly inside encrypt only rebinds the local name — it never mutates the caller's pub). So every chunk is encrypted against the identical, known, degree-64 public key, not a cumulative one.
• Each chunk's ciphertext is pub * (x-m0)(x-m1)(x-m2)(x-m3), a degree-68 monic polynomial, again printed with the leading 1 omitted.
• The order value packs, in 2 bits each, the original index of the i-th smallest message byte — i.e. it tells you how to unscramble the sorted roots back into message order.

That's the whole scheme: multiply-in-roots "encryption" with the public key
handed out in full. The private root set (the actual RSA-style "key") is
completely irrelevant to breaking it.

Attempt 1 — just run the script (dead end)

First instinct was to just run pscheme.py locally to see the output format
against a known flag, but the script hardcodes the real flag and errors out
without it:

$ python3 pscheme.py
Traceback (most recent call last):
  File "/home/kali/ctf/easy/pscheme.py", line 95, in <module>
    FLAG = [REDACTED]
            ^^^^^^^^
NameError: name 'REDACTED' is not defined

No local execution path — the only usable artifact is enc.txt, so the
attack has to be purely algebraic against the given ciphertext.

Attempt 2 — polynomial division + root recovery

Step 1: parse enc.txt

enc.txt has two sections:

====PUBLIC KEY====
<64 space-separated coefficients, ascending degree, leading 1 omitted>
====MESSAGE====
<ciphertext chunks, "/"-joined, each "<68 coefficients> <order>">

Step 2: recover the known public key as a polynomial

Reconstruct the monic degree-64 public key by appending the implicit
leading 1:

pub_coeffs_asc = [int(x) for x in re.findall(r'-?\d+', pub_joined)] + [1]
pub_desc = list(reversed(pub_coeffs_asc))

Step 3: divide each ciphertext chunk by the public key

Since both polynomials are monic, exact integer polynomial long division
needs no fractional arithmetic — division by the leading coefficient is
always division by 1:

def poly_divmod_desc(dividend_desc, divisor_desc):
    dividend = dividend_desc[:]
    n = len(divisor_desc)
    quotient = []
    for i in range(len(dividend) - n + 1):
        coef = dividend[i]
        quotient.append(coef)
        if coef != 0:
            for j in range(n):
                dividend[i + j] -= coef * divisor_desc[j]
    remainder = dividend[len(dividend) - n + 1:]
    return quotient, remainder

chunk_poly / pub_poly leaves a degree-4 monic quotient whose roots are
exactly the chunk's 4 plaintext byte values.

Step 4: factor the quartic

The roots are ASCII bytes, i.e. small integers in [0, 255], so brute-force
trial-root + synthetic deflation is fast and exact — no need for a general
quartic formula:

def find_roots(poly_desc, lo=0, hi=256):
    coeffs = poly_desc[:]
    roots = []
    for _ in range(len(coeffs) - 1):
        found = None
        for r in range(lo, hi):
            val = 0
            for c in coeffs:
                val = val * r + c
            if val == 0:
                found = r
                break
        if found is None:
            return None
        roots.append(found)
        new_coeffs = [coeffs[0]]
        for c in coeffs[1:]:
            new_coeffs.append(new_coeffs[-1] * found + c)
        coeffs = new_coeffs[:-1]
    return roots  # ascending

Step 5: undo the order shuffle

order's 2-bit fields give, for each of the 4 sorted roots, the index it
originally occupied in the unscrambled message — so decoding is a direct
scatter:

def decode_chunk(order, sorted_roots):
    message = [None] * len(sorted_roots)
    for i, root in enumerate(sorted_roots):
        idx = (order >> (2 * i)) & 3
        message[idx] = root
    return ''.join(chr(m) for m in message if m is not None)

Putting it together

$ cat > flag.py << 'EOF'
heredoc> [... solver assembled from steps above ...]
heredoc> EOF

$ python3 flag.py enc.txt
bronco{REDACTED}

No brute force of the private key, no factoring 100+ digit RSA-scale
numbers by guesswork — just one exact polynomial division and a quartic
root search per 4-byte chunk.

Attack Chain

enc.txt (public key + per-chunk ciphertext)
        │
        ▼
reconstruct monic public key polynomial (add back implicit leading 1)
        │
        ▼
for each ciphertext chunk:
        │
        ├─► exact polynomial long division by public key  →  degree-4 quotient
        │
        ├─► brute-force integer root search (0-255) + synthetic deflation
        │        →  4 plaintext ASCII bytes (sorted)
        │
        └─► undo `order` bitfield shuffle  →  4 bytes in original order
        │
        ▼
concatenate chunks, strip null padding
        │
        ▼
        FLAG

Key Vulnerabilities

#	Issue	Impact
1	Public key is reused unmodified for every chunk instead of accumulating, and is disclosed in full	Lets an attacker isolate each chunk's added roots via simple polynomial division — private key material is never needed
2	"Encryption" is just multiplying plaintext values in as polynomial roots	Roots of a public polynomial with known factors are trivially recoverable; this is not a hard problem (no hiding, no randomness in the encryption step itself)
3	Root search space is tiny ([0, 255], ASCII bytes)	Even without factoring cleverness, brute-force + deflation solves each quartic in milliseconds
4	order field is a simple deterministic bit-packed permutation with no keying	Trivially invertible once you have the sorted roots