Monodromy

Monodromy (ISFCR CTF 2026) hands you a MONOVM3 capsule, two 8x8 matrices, and a stripped ELF that demands "the lost rotation index" before it will say anything useful. The rotation index is a discrete logarithm in a ~2^49 subgroup, and the capsule's Argon2id-hardened seal only opens once that index is known. I recovered it with a parallel Pollard-rho solver in C, then opened the seal with a Python script.

Files

Capsule Layout

seal.py's parse function defines the header. The magic is MONOVM3\0, then little-endian fields, then the seal, then the tape:

n0, n1 = struct.unpack_from("<II", blob, 32)
memory_mib, iterations, lanes = struct.unpack_from("<III", blob, 56)
seal_len = struct.unpack_from("<I", blob, 80)[0]

The capsule I parsed has a 32-byte order field at offset 24 equal to 714595551230081 (~2^49.3), a 3,072 MiB / 500-iteration Argon2id setup, seal_len = 57, and a tape of 600,064 + 600,064 records of 19 bytes. The integrity binding covers the outer header and the whole tape:

artifact_hash = hashlib.sha256(blob[:80] + blob[tape_start:]).digest()

The order is public data in the header — the intended work is not guessing which index, but computing it.

Discrete Log in GF(p²)

solve.c implements the field GF(p²) as pairs (a, b) of 128-bit values reduced mod p = 0x270ef8360b0d6589e14828a83b6de4c1, with squaring relation i² = delta0 = 0x77a6c6a7159e7b1·2^64 + 0x941c2a81edc3f387. Multiplication is the classic schoolbook form using _BitInt(256) temporaries:

u256 term1 = (a1a2 + b1b2_delta) % (u256)p;
u256 term2 = (a1b2 + a2b1) % (u256)p;

Any 8x8 matrix whose characteristic polynomial splits over this field acts on eigenvectors as multiplication by its eigenvalues — two of which are public constants baked into the solver: g = (lam_a, lam_b) and h = (mu_a, mu_b). Because the roles of g and h in M0 → M1 are known, and the group generated by g has order q = 714595551230081, finding the rotation index is precisely h = g^x mod q over the field.

Parallel Pollard Rho with Distinguished Points

solve.c builds 32 shared random walk steps per worker (srand(1337) for reproducibility), each step adding fixed exponents u_i, v_i:

u_step[i] = (rand64() % q);
v_step[i] = (rand64() % q);
Fp2 gu = fp2_pow(g, u_step[i]);
Fp2 hv = fp2_pow(h, v_step[i]);
R[i] = fp2_mul(gu, hv);

Each thread starts from a random g^a0 · h^b0 (seeded 1337 + tid*10007), takes steps indexed by the low bits of the current value, and records distinguished points (13 low zero bits) in a 2^20-entry hash table under an OpenMP lock, with linear probing for collisions:

if (((uint32_t)cur.a & DP_MASK) == 0) {
    uint32_t hidx = ...;
    if (fp2_eq(dp_table[hidx].pt, cur) && different exponents) {
        // alpha + beta*log  collision
        cand = d_alpha * mod_inv(d_beta, q) % q;
    }
}

A collision between two walks with exponents (alpha1, beta1) and (alpha2, beta2) satisfies alpha1 - alpha2 = (beta1 - beta2)·x mod q, giving the candidate directly. Threads re-seed a new walk after every distinguished-point insertion, so the table stays small and lock contention is brief. Runs on this class of problem land in minutes on consumer hardware rather than the 2^49 John the Ripper brute force.

Verifying the Candidate

The rho output is only a candidate exponent. It gets checked directly against the matrices, with the negative also tried since the subgroup orientation is ambiguous:

Mat8 res1 = mat_pow(M0, cand1);
if (memcmp(&res1, &M1, sizeof(Mat8)) == 0) { /* rotation index */ }

The compiled solve binary in the folder is the built version of solve.c.

Opening the Capsule

seal.py derives the work seed from the index and the artifact hash:

return hashlib.sha256(b"monodromy-v3-work\0" + index.to_bytes(8, "little") + artifact_hash).digest()

then stretches it with Argon2id (3072 MiB, 500 iterations, lanes=1), runs HKDF-SHA256 with salt=artifact_hash and info=b"monodromy-v3-flag", and decrypts:

ChaCha20Poly1305(key).decrypt(blob[68:80], blob[84:84+seal_len], b"monodromy-v3" + artifact_hash)

The seal is a short payload (57 bytes of ciphertext+tag), so the answer is a single line rather than a long message. Note the cost asymmetry — a wrong index still pays the full Argon2id work, so the correctness of the rho result matters before you invoke seal.py.

Flag

Flag: not recovered in the writeup. The decrypted seal text is not preserved in any artifact on disk.