Custom Cipher

Platform: Broncoctf2026 | Category: Cryptography | Type: Challenge | Difficulty: Medium | OS: NA | Author: D3v0o0Nu11 | Date: 2026-07-11 | Status: Solved Techniques: bounded_integer_root_recovery, exact_polynomial_division, permutation_recovery, synthetic_division

Summary

Task: a homemade polynomial 'public-key' scheme where the public polynomial is a literal factor of every ciphertext polynomial and message bytes are appended as linear factors (x - m). Solution: exact monic polynomial division of ciphertext by public key yields the degree-4 message polynomial, then bounded integer root search (0..255) plus the packed order integer recovers the plaintext bytes.

Recon

Port scan

 bash read-only • copy allowed Copy
nmap -p- -sV -sC <TARGET> --min-rate 1000 -Pn

Enumeration highlights

• Event: broncoctf2026 | ID: 20260711_broncoctf2026_custom_cipher
• Tags: factoring, polynomial_cryptography, public_key, small_message_space, permutation_recovery
• Indicators: public key is a monic polynomial with secret integer roots, ciphertext is a higher-degree monic polynomial, message bytes packed as extra linear factors, order integer packs 2 bits per index, challenge joke: factoring is free
• Source: 20260711_broncoctf2026_custom_cipher.md

Foothold

Vulnerability / Misconfiguration

1. bounded_integer_root_recovery
2. exact_polynomial_division
3. permutation_recovery
4. synthetic_division

 bash read-only • copy allowed Copy
<command>

Exploitation

• See original writeup content for detailed exploitation.

Privilege Escalation

Enumeration

 bash read-only • copy allowed Copy
sudo -l
find / -perm -4000 2>/dev/null
getcap -r / 2>/dev/null
cat /etc/crontab
ps aux

Exploitation

1. N/A for challenge-type writeup; see exploitation above.
2. Flag obtained via challenge solve.

 bash read-only • copy allowed Copy
<command>

Flags

Key Takeaways / Lessons

• bounded_integer_root_recovery
• exact_polynomial_division
• permutation_recovery
• synthetic_division
• Tags: factoring, polynomial_cryptography, public_key, small_message_space, permutation_recovery

Original Writeup

<details><summary>Click to expand original content</summary>

Custom Cipher — broncoctf2026

Description

I've finally made the perfect public-key encryption algorithm! Its security is rivaled only by it's message space efficiency. In fact, I'm so confident that I'll send you the flag along with my public key, and there's nothing you can do to read it.

We are given pscheme.py (the encryption scheme) and enc.txt (the public key and the encrypted flag). The goal is to recover the flag from the public key and ciphertext alone.

Analysis

The scheme is a homemade polynomial-based "public-key" cipher:

• keygen(root_bits=8, key_degree=64) picks 64 random secret integer roots in [1, 255] and builds the public polynomial as the monic product of linear factors ∏ (x - root). So the public key is a degree-64 monic polynomial whose roots are the private key.
• encrypt(public, message) takes a message of 4 integers (the ord() values of 4 plaintext chars, zero-padded). It multiplies the public polynomial by four more linear factors (x - m_i), producing a degree-68 monic polynomial. It also returns an order integer that packs the permutation needed to restore the original byte positions after the message was sorted — 2 bits per index, order = sum(idx << (2*i)).
• encrypt_string processes the flag in 4-char blocks. For each block it emits the ciphertext polynomial coefficients (space-separated, via to_distrib_form, which drops the leading monic 1) followed by the packed order integer. Blocks are joined with /.

Why it is trivially breakable

The whole scheme collapses because of the multiplicative structure:

1. The public polynomial is literally a factor of every ciphertext polynomial. The ciphertext is public(x) · (x - m0)(x - m1)(x - m2)(x - m3). Dividing the ciphertext by the public key with exact monic polynomial division yields the degree-4 message polynomial (x - m0)(x - m1)(x - m2)(x - m3).
2. The message-polynomial roots are just the plaintext byte values, bounded in [0, 255]. Enumerating candidate roots 0..255 with synthetic division (preserving multiplicity) recovers the 4 bytes per block (in sorted order).
3. The packed order integer restores the original ordering of the sorted roots, so the plaintext bytes go back to their correct positions.

No private key, no factoring of large integers — just polynomial division plus a bounded root search over 256 values. That is the challenge's joke: "factoring is free."

Solution

1. Parse enc.txt: line 2 is the public key coefficients. Append the implicit leading 1 (the scheme drops it) to make it a monic degree-64 polynomial. Line 4 is the message: 7 blocks separated by /, each with 68 coefficients + 1 order integer.
2. For each block, reconstruct the monic degree-68 ciphertext polynomial (append the implicit 1) and divide it exactly by the monic public polynomial → degree-4 message polynomial.
3. Enumerate integer roots 0..255 via synthetic division, preserving multiplicity → 4 sorted plaintext byte values.
4. Use order: for i, root in enumerate(sorted(roots)): original[(order >> (2*i)) & 3] = root. Then bytes(original).rstrip(b"\0").decode().
5. Concatenate all blocks.

Coefficients are little-endian (index i = coefficient of x^i), matching the scheme's Poly.coeff layout.

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from pathlib import Path

lines = Path("enc.txt").read_text().splitlines()
# Public key: append the implicit leading monic 1 -> monic degree-64 polynomial
public = list(map(int, lines[1].split())) + [1]

def divide_monic(product, divisor):
    """Exact monic polynomial division (little-endian coeffs). Asserts zero remainder."""
    rem = product[:]
    degree = len(product) - len(divisor)
    quotient = [0] * (degree + 1)
    for k in range(degree, -1, -1):
        quotient[k] = rem[k + len(divisor) - 1]
        for j, coefficient in enumerate(divisor):
            rem[k + j] -= quotient[k] * coefficient
    assert all(x == 0 for x in rem)
    return quotient

plaintext = ""
for block in lines[3].split("/"):
    values = list(map(int, block.split()))
    encrypted, order = values[:-1] + [1], values[-1]  # re-add implicit monic 1
    message_poly = divide_monic(encrypted, public)      # degree-4 message polynomial

    # Every plaintext byte is an integer root in [0, 255]. Preserve multiplicity.
    roots = []
    poly = message_poly
    for candidate in range(256):
        while len(poly) > 1 and sum(c * candidate**i for i, c in enumerate(poly)) == 0:
            roots.append(candidate)
            synthetic = [0] * (len(poly) - 1)
            synthetic[-1] = poly[-1]
            for i in range(len(poly) - 2, 0, -1):
                synthetic[i - 1] = poly[i] + candidate * synthetic[i]
            assert poly[0] == -candidate * synthetic[0]
            poly = synthetic
    assert len(roots) == 4 and poly == [1]

    # Restore original byte order using the packed permutation (2 bits per index)
    original = [0] * 4
    for i, root in enumerate(sorted(roots)):
        original[(order >> (2 * i)) & 3] = root
    plaintext += bytes(original).rstrip(b"\0").decode()

print(plaintext)

Running it prints the flag.

</details>

---

signed by XESXOR