cryptofreehard

sporadiclogarithms

b01lersc

Task: black-box 'twisted' discrete log in the holomorph G ⋊ <c> over GL(3, 65537), where the inner automorphism phi(a)=c*a*c^-1 has small order m ∈ {2,4,8}; server deduplicates equal matrices to equal handles. Solution: factor x = q*m + r, reduce to ordinary DLP of the m-fold cycle product P in size 2^18/m, and run BSGS using handle equality as a matrix hash — no eq queries, no knowledge of the group needed.

$ ls tags/ techniques/

discrete_log bsgs sagemath holomorph semidirect_product black_box_group gl_n matrix_group

baby_step_giant_stepholomorph_dlp_reductionhandle_dedup_as_hashsmall_order_automorphism_twist

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

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 — th3_m0n5t3r_gr0up_w45_t0_1mpr4ct1c4l_:( — 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

...