sporadiclogarithms — b01lersCTF 2026

Description

"I heard the discrete logarithm problem can be solved efficiently in all sporadic groups without even knowing the group. Can you prove it to me?"

Server: ncat --ssl sporadiclogarithms.opus4-7.b01le.rs 8443

English summary: the server runs a SageMath black-box group. Each round it picks a secret x ∈ [0, 2^18] and publishes opaque integer handles for 1, a random invertible matrix g, the conjugator c, and h = s_{g,φ}(x) (defined below). You can call mul a b, inv a, phi a (applies a ↦ c·a·c⁻¹), and eq a b on handles, with a budget of 10 000 queries per round. Pass 5 rounds to get the flag.

The name is a pun on the 26 sporadic finite simple groups (Monster, Baby Monster, …). The flag — REDACTED — admits that DLP in sporadic groups is actually hard; this challenge only dresses up as a sporadic-group problem and is really about a small-order automorphism twist on GL(3, 65537).

Analysis

Setup — server internals

Relevant parts of chall.py:

# GL(n, p) with p = 65537, n = 3
F = GF(params.p); M = MatrixSpace(F, params.n)

def choose_small_order_conjugator(F, n, max_order):
    # divisors of p-1 = 2^16, restricted to 1 < d <= 8  =>  m ∈ {2, 4, 8}
    divs = [d for d in divisors(F.order() - 1) if 1 < int(d) <= max_order]
    m = int(random.choice(divs))
    g = F.multiplicative_generator()
    d = g ** ((F.order() - 1) // m)
    c = identity_matrix(F, n)
    c[0, 0] = d              # c is diagonal with a single non-trivial entry of order m
    return c, m

def hol_mul(x, y):
    a, c1 = x; b, c2 = y
    return a * (c1 * b * c1.inverse()), c1 * c2     # semidirect product multiplication

def hol_pow(base, e, F, n):
    one = identity_matrix(F, n)
    result = (one, one); cur = base; k = e
    while k > 0:
        if k & 1: result = hol_mul(result, cur)
        cur = hol_mul(cur, cur); k >>= 1
    return result

The black box itself is a list of matrices with a dedup index:

def _add_elem(self, x) -> int:
    k = mat_key(x)                 # tuple of entries
    if k in self.index:
        return self.index[k]       # <-- equal matrices => SAME handle
    self.table.append(x)
    h = len(self.table)
    self.index[k] = h
    return h

That last block is the whole game.

The math: holomorph DLP reduction

We are in the holomorph G ⋊ Aut(G) where G = GL(n, p) and the automorphism is φ(a) = c·a·c⁻¹. Multiplication is (a, c₁)·(b, c₂) = (a · c₁·b·c₁⁻¹, c₁·c₂). By induction,

(g, c)^x = ( s_{g,φ}(x),  c^x ),

where

s_{g,φ}(x) = g · φ(g) · φ²(g) · … · φ^(x-1)(g).

The published h is exactly s_{g,φ}(x).

Key reduction. Because c has order m in GL(n, p), the automorphism φ also has period m. Let g_i = φⁱ(g); then g_{i+m} = g_i. Write x = q·m + r with 0 ≤ r < m:

s_{g,φ}(x) = (g_0 · g_1 · … · g_{m-1})^q  ·  (g_0 · g_1 · … · g_{r-1})
           = P^q · T_r

where P = g_0 · … · g_{m-1} is the full cycle product and T_r = g_0 · … · g_{r-1} is a partial prefix (with T_0 = e).

Since m ∈ {2, 4, 8}, there are at most 8 prefixes. For each candidate r, define y_r = h · T_r⁻¹. If r is the correct residue, then y_r = P^q — an ordinary DLP in GL(n, p) with q < 2^18 / m ≤ 2^17.

√(2^17) ≈ 363, so BSGS is well within the 10 000-query budget.

The black-box trick: handles as matrix hashes

We cannot look at matrix entries. But _add_elem guarantees: two matrices are equal iff they get the same handle. So BSGS table lookup can be done by integer equality of handles — we do not need a single eq call. We also never need to know p, n, or anything about GL — the attack works for any group with this kind of dedup-keyed black box.

Solution

Algorithm

For each round:

1. Parse the banner to get c_order = m, bound = 2^18, and the handles one, g, c, h.
2. Compute g_0, g_1, …, g_{m-1} via phi.
3. Compute prefixes T_0 = one, T_{i+1} = T_i · g_i. The final one is P = T_m.
4. BSGS with step = ⌈√(bound/m)⌉ + 2:
   • Baby steps: handles P^0, P^1, …, P^(step-1); store {handle: i}.
   • Giant step: G = P^(-step) = inv(P^step).
5. For each r ∈ [0, m):
   • Compute y_r = h · T_r⁻¹ (or y_0 = h directly when T_0 = one).
   • Iterate z_0 = y_r, z_{j+1} = z_j · G. If z_j's handle is in the baby-step table with index i, we have found q = j·step + i. Submit x = q·m + r.

Query cost per round ≈ m + (m+1) + 2·step + (step × m) ≈ 1500 for m=8, well under the 10k limit.

Solver (solve.py)

#!/usr/bin/env python3
"""
Solver for sporadiclogarithms (b01lersCTF 2026).

In the holomorph G ⋊ <c>, (g, c)^x = (s_{g,φ}(x), c^x) where
  s_{g,φ}(x) = g · φ(g) · … · φ^(x-1)(g)  and  φ(a) = c a c^-1.

Since ord(c) = m ∈ {2,4,8}, φ has period m. Writing x = q*m + r:
  h = P^q · T_r      with  P = g_0 g_1 … g_{m-1},  T_r = g_0 … g_{r-1}.

For each r: y_r = h · T_r^-1; if r is correct, y_r = P^q.
Solve with BSGS. No eq queries — handle equality is matrix equality
(SageBlackBox._add_elem deduplicates).
"""

import math, re, sys
from pwn import remote, context

HOST = "sporadiclogarithms.opus4-7.b01le.rs"
PORT = 8443
context.log_level = "info"


class BB:
    def __init__(self, r):
        self.r = r
        self.queries = 0

    def cmd(self, line):
        self.r.sendline(line.encode())
        data = self.r.recvuntil(b"bb> ", drop=True)
        return data.decode().strip()

    def _handle(self, resp):
        for ln in reversed(resp.splitlines()):
            ln = ln.strip()
            if ln.isdigit():
                return int(ln)
        raise ValueError(f"No handle in: {resp!r}")

    def mul(self, a, b): self.queries += 1; return self._handle(self.cmd(f"mul {a} {b}"))
    def inv(self, a):    self.queries += 1; return self._handle(self.cmd(f"inv {a}"))
    def phi(self, a):    self.queries += 1; return self._handle(self.cmd(f"phi {a}"))


def solve_round(r, round_idx, rounds):
    banner = r.recvuntil(b"bb> ").decode()
    cord = int(re.search(r"c order=(\d+)", banner).group(1))
    one, g_h, c_h, h_h = map(int,
        re.search(r"one=(\d+) g=(\d+) c=(\d+) h=(\d+)", banner).groups())
    bound = int(re.search(r"Find any x in \[0, (\d+)\]", banner).group(1))

    print(f"[round {round_idx}/{rounds}] c_order={cord} bound={bound} "
          f"one={one} g={g_h} c={c_h} h={h_h}")

    bb = BB(r)

    # g_i = φ^i(g)
    g_seq = [g_h]
    for _ in range(1, cord):
        g_seq.append(bb.phi(g_seq[-1]))

    # T_r = g_0 … g_{r-1},  P = T_m
    T = [one]
    for i in range(cord):
        T.append(bb.mul(T[-1], g_seq[i]))
    P = T[cord]

    # Baby steps
    Q_max = bound // cord + 2
    step  = int(math.isqrt(Q_max)) + 2

    babies = [one]
    for _ in range(1, step):
        babies.append(bb.mul(babies[-1], P))
    baby_lookup = {}
    for i, hnd in enumerate(babies):
        baby_lookup.setdefault(hnd, i)

    # Giant step: G = P^{-step}
    P_step = bb.mul(babies[-1], P)
    G = bb.inv(P_step)

    print(f"[round {round_idx}] step={step}, baby_lookup size={len(baby_lookup)}, "
          f"queries so far={bb.queries}")

    for rr in range(cord):
        T_r = T[rr]
        y = h_h if T_r == one else bb.mul(h_h, bb.inv(T_r))

        z = y
        for j in range(step + 1):
            if z in baby_lookup:
                i = baby_lookup[z]
                q = j * step + i
                x = q * cord + rr
                print(f"[round {round_idx}] FOUND: r={rr} q={q} x={x} "
                      f"(queries={bb.queries})")
                r.sendline(f"submit {x}".encode())
                verdict = r.recvline().decode().strip()
                print(f"[round {round_idx}] verdict: {verdict}")
                return "correct" in verdict
            if j < step:
                z = bb.mul(z, G)

    print(f"[round {round_idx}] FAILED: no match found, queries={bb.queries}")
    r.sendline(b"submit 0")
    r.recvline()
    return False


def main():
    r = remote(HOST, PORT, ssl=True)
    banner0 = r.recvline().decode().strip()
    rounds = int(re.search(r"Pass (\d+) rounds", banner0).group(1))
    for i in range(1, rounds + 1):
        if not solve_round(r, i, rounds):
            return 1
    print(r.recvall(timeout=5).decode())
    return 0


if __name__ == "__main__":
    sys.exit(main())

Run log

[banner] Pass 5 rounds to get the flag.
[round 1/5] c_order=2 bound=262144 one=1 g=2 c=4 h=3
[round 1] step=364, baby_lookup size=364, queries so far=368
[round 1] FOUND: r=1 q=46074 x=92149 (queries=860) -> correct
[round 2/5] c_order=2 ... FOUND: r=0 q=21713 x=43426  (queries=427)  -> correct
[round 3/5] c_order=2 ... FOUND: r=0 q=7450  x=14900  (queries=388)  -> correct
[round 4/5] c_order=8 ... FOUND: r=1 q=413   x=3305   (queries=386)  -> correct
[round 5/5] c_order=8 ... FOUND: r=6 q=27686 x=221494 (queries=1460) -> correct
bctf{REDACTED}