D-Side — uiuc2026

Description

You find a strange cassette tape...

The generator performs a 64-edge walk between normalized rank-two Drinfeld modules over a Laurent-series field. It serializes the initial destination and every later vertex, hashes the resulting 64 strings with SHA-256, and uses that digest as an AES-CTR key. The challenge publishes only the final truncated j-invariant, IV, and ciphertext.

The goal is therefore not merely to find one predecessor of the endpoint. We must reconstruct the complete ordered path exactly, including the coefficient serialization used by the generator.

Challenge Structure

The relevant definitions are

q = 4
T = u^-1

def _target_g(g, a):
    return (g + a*(T^q - T))*a^(q - 1)

def j_invariant(g):
    return g^(q + 1)

def _serialize_j(j):
    v = ZZ(j.valuation())
    return b",".join(f"{e}:{j[e]}".encode() for e in range(v, v + 12))

The challenge starts with a fixed edge, then makes 32 constrained choices and 31 ordinary choices. Including the first destination, this gives exactly 64 serialized vertices:

g, a = initial_edge()
path = [_serialize_j(j_invariant(g))]

for i in range(32):
    edges = sorted(forward_edges(g, a, True), key=lambda e: str(j_invariant(e[0])))
    g, a = edges[secrets.randbelow(q - 1)]
    path.append(_serialize_j(j_invariant(g)))

    if i + 1 < 32:
        g, a = secrets.choice(forward_edges(g, a))
        path.append(_serialize_j(j_invariant(g)))

key = hashlib.sha256(b"".join(path)).digest()

Thus even one wrong vertex changes the key completely.

Analysis

Why local reversal is insufficient

Eliminating the source coefficient from the edge equations gives

[ g' = T^4a^4+a^{-1}. ]

Consequently, a target coefficient g' gives candidate edge parameters from

[ T^4a^5-g'a+1=0, ]

and each candidate source is

[ g=Ta+a^{-4}. ]

This exact inverse is not unique: the supplied endpoint has five adjacent candidates. Worse, the first inversion reduces the available precision from O(u^76) to approximately O(u^56). Repeating this operation cannot recover 63 predecessors.

Other direct path attacks also fail:

• Enumeration: the numbers of distinct endpoints at depths one through six are 3, 12, 36, 144, 432, 1728. There is no useful early collision or small quotient state space.
• Greedy decoding: completing candidate prefixes canonically and scoring agreement with the endpoint already ties or selects the wrong path at depth three. Laurent coefficients do not encode one edge at a time in this ordering.
• Normalized monic Ore reconstruction: the full map is a monic Ore polynomial F=L_64*...*L_1. Although its intertwining recurrence is correct and factoring a known F is easy, its coefficients require exponents on the scale of 4^64. Sage's Puiseux backend overflows, and more importantly the top-down recurrence destroys the limited endpoint precision after only a few coefficients. Changing the backend would not cure that conditioning problem.

The endpoint must instead be interpreted globally as a lattice.

Recovering a period ratio

Choose any fifth root g of the published value because j=g^(q+1)=g^5. The five choices are related by constant-field conjugation and represent isomorphic normalized targets, so any one yields the needed lattice vertex.

For the rank-two Drinfeld module

[ \phi_T(X)=TX+gX^q+X^{q^2}, ]

first find two independent nonzero T-torsion points. Repeatedly take the unique small compatible preimage under phi_T; after enough levels, the quotient of the two towers converges to a period ratio

[ z=\omega_2/\omega_1. ]

The fixed-point update in the good-reduction disk is

[ y \leftarrow \frac{x+gy^q+y^{q^2}}{T}. ]

Laurent continued fractions and rational reconstruction

Apply the ordinary continued-fraction algorithm, but take polynomial parts in T=u^-1. At convergent 30, the expansion reconstructs

[ z=P/Q, \qquad \deg P=\deg Q=32. ]

Write both polynomials over the Frobenius-fixed F_4 basis (1,c):

[ P=P_0+cP_1,\qquad Q=Q_0+cQ_1. ]

The endpoint lattice relative to the starting basis (1,c) is represented by

[ M= \begin{pmatrix} Q_0 & P_0\ Q_1 & P_1 \end{pmatrix}. ]

The recovered determinant is the decisive check:

[ \det M=(c^2+c+1)T^{64}. ]

This says that the endpoint is a cyclic index-T^64 sublattice, precisely matching the published isogeny degree.

The unique cyclic filtration

Set

[ r=(Q_1,Q_0). ]

In characteristic two, r annihilates the first endpoint generator exactly, while its pairing with the second is the determinant. Hence it annihilates the endpoint lattice modulo T^64.

The complete path is the unique filtration

[ L_i={v:r\cdot v=0\pmod{T^i}},\qquad 0\le i\le64. ]

Suppose the columns of B_i form a basis of L_i. The coefficient of T^i in rB_i is a nonzero row (s_1,s_2). Its kernel over the constant field is the next one-dimensional isogeny kernel. In characteristic two, (s_2,s_1) spans that line. If v is this kernel period and w is a complement, update the lattice basis as

[ B_{i+1}=(v,Tw). ]

This extracts one edge at a time without guessing.

Transporting division points

A kernel point determines the normalized edge parameter by

[ a=\text{kernel}^{1-q}. ]

Shallow torsion points become ambiguous at bad-reduction vertices. The solver therefore carries compatible depth-16 division points. These deep points remain in the contraction disk, so they preserve the period-consistent branch. For an edge with parameter a, transport points using

[ L(x)=x^q+x/a. ]

After every step, compute g_next, append j(g_next), and update both the shallow torsion basis and deep compatible points. The last recovered j agrees with all 12 published serialized coefficients.

Solution

Place the following solver beside the supplied util.sage and out, then run sage lattice_solve.sage. This is the final working solver used for recovery.

"""Recover the 64-edge path through the period lattice and decrypt D-Side."""

load("util.sage")
# Rebuild the same global rings at lower precision for the 1 GiB solver host.
# The loaded helper functions resolve these globals dynamically.
prec = 100
k = GF(q^2, "c")
R = PuiseuxSeriesRing(k, "u", default_prec=prec)
u = R.gen()
T = u^-1
S.<A> = PolynomialRing(R)
B.<C> = PolynomialRing(k)
import hashlib
try:
    from Crypto.Cipher import AES
except ImportError:
    AES = None

c = k.gen()
lines = open("out").read().splitlines()
j_end = sage_eval(next(x[4:] for x in lines if x.startswith("j = ")),
                  locals={"c": c, "u": u, "O": O})
iv = bytes.fromhex(next(x[5:] for x in lines if x.startswith("iv = ")))
ct = bytes.fromhex(next(x[5:] for x in lines if x.startswith("ct = ")))


def small_division(x, g, rounds=12):
    """The high-valuation solution y of phi_T(y)=x."""
    y = x/T
    for _ in range(rounds):
        y = (x + g*y^q + y^(q^2))/T
    return y


def period_division(x, g):
    """Solve phi_T(y)=x and select the unique root nearest zero.

    The fixed-point contraction used by small_division only works in the
    good-reduction disk. Along this path some vertices have negative g
    valuation, so use the Newton polygon and select the maximal-valuation
    preimage, which is e(log(x)/T).
    """
    roots = _puiseux_roots(A^(q^2) + g*A^q + T*A + x)
    vals = [y.valuation() for y in roots]
    m = max(vals)
    print("division valuations", sorted(vals), flush=True)
    assert vals.count(m) == 1
    return roots[vals.index(m)]


def period_ratio(g, levels=80):
    """Recover a ratio of a period basis from compatible T-division towers."""
    roots = _puiseux_roots(A^(q^2) + g*A^q + T*A)
    nz = [x for x in roots if not x.is_zero()]
    x1 = nz[0]
    x2 = next(x for x in nz if (x/x1)^q != x/x1)
    for _ in range(levels):
        x1 = small_division(x1, g)
        x2 = small_division(x2, g)
    return x2/x1


KT.<t> = PolynomialRing(k)


def polynomial_part(x):
    return R.sum(x[e]*u^e for e in x.exponents() if e <= 0)


def as_T_polynomial(x):
    return KT.sum(x[e]*t^(-e) for e in x.exponents() if e <= 0)


def split_poly(f):
    """Write f=f0+c*f1 with f0,f1 in the Frobenius-fixed F4[T]."""
    den = c + c^q
    f1 = KT.sum(((cc + cc^q)/den)*t^i for i, cc in enumerate(f))
    f0 = f + c*f1
    assert all(cc^q == cc for cc in f0)
    assert all(cc^q == cc for cc in f1)
    return f0, f1


def rational_reconstruct(z):
    """Laurent continued fraction; stop at the degree-64 lattice determinant."""
    pm2, pm1 = KT.zero(), KT.one()
    qm2, qm1 = KT.one(), KT.zero()
    x = z
    for idx in range(80):
        aa = polynomial_part(x)
        ap = as_T_polynomial(aa)
        pp, qq = ap*pm1 + pm2, ap*qm1 + qm2
        pm2, pm1, qm2, qm1 = pm1, pp, qm1, qq

        p0, p1 = split_poly(pp)
        q0, q1 = split_poly(qq)
        det = q0*p1 + q1*p0
        if det and det.degree() == 64 and all(det[i] == 0 for i in range(64)):
            print("period convergent", idx, "degrees", pp.degree(), qq.degree())
            print("determinant", det)
            return pp, qq, (q0, q1, p0, p1)

        rr = x-aa
        if rr.is_zero() or rr.valuation() >= x.precision_absolute():
            break
        x = 1/rr
    raise ValueError("no degree-64 T-power lattice determinant found")


# Any fifth root gives an isomorphic normalized target and hence the same lattice vertex.
g_lift = _puiseux_roots(A^(q+1)-j_end)[0]
z = period_ratio(g_lift)
P, Q, (q0, q1, p0, p1) = rational_reconstruct(z)

# L_64=<Q,P> inside L_0=<1,c>. A primitive row annihilating L_64
# modulo T^64 is r=(q1,q0), since r.Q=0 and r.P=det.
r0, r1 = q1, q0

# Current lattice basis columns, in fixed coordinates relative to (1,c).
b00, b10 = KT.one(), KT.zero()
b01, b11 = KT.zero(), KT.one()

# T-torsion basis corresponding to periods (1,c) of phi_0=T+tau^2.
x1 = (u^(-QQ(1)/(q^2-1))).add_bigoh(prec)
x2 = c*x1
g = R.zero()
path = []

# Keep compatible deep T-division points. At bad-reduction vertices the
# shallow equation phi_T(y)=x has several equally large roots, while the deep
# point lies in the contraction disk and therefore picks the period-consistent
# root without ambiguity.
deep_level = 16
deep1, deep2 = x1, x2
for _ in range(deep_level):
    deep1 = small_division(deep1, g)
    deep2 = small_division(deep2, g)

for i in range(64):
    # L_{i+1}/T L_i is the kernel of r/T^i modulo T.
    n1 = r0*b00 + r1*b10
    n2 = r0*b01 + r1*b11
    assert all(n1[j] == 0 and n2[j] == 0 for j in range(i))
    s1, s2 = n1[i], n2[i]
    alpha, beta = s2, s1
    assert alpha or beta

    # Pick a complementary period w, so (v,w) is a basis.
    if beta:
        gamma, delta = k.one(), k.zero()
    else:
        gamma, delta = k.zero(), k.one()

    kernel = alpha*x1 + beta*x2
    a = kernel^(1-q)
    xw = gamma*x1 + delta*x2
    deep_v = alpha*deep1 + beta*deep2
    deep_w = gamma*deep1 + delta*deep2
    divided_deep = small_division(deep_v, g)

    def edge_map(x):
        return x^q + x/a

    g_next = _target_g(g, a)
    deep1_next = edge_map(divided_deep)
    deep2_next = edge_map(deep_w)
    x1_next = deep1_next
    for _ in range(deep_level):
        x1_next = T*x1_next + g_next*x1_next^q + x1_next^(q^2)
    x2_next = edge_map(xw)

    # Sanity checks: the transported points form a target T-torsion basis.
    tor1 = x1_next^(q^2) + g_next*x1_next^q + T*x1_next
    tor2 = x2_next^(q^2) + g_next*x2_next^q + T*x2_next
    if i == 0:
        g0_test, a0_test = initial_edge()
        print("first a diff", a-a0_test, "g diff", g_next-g0_test, flush=True)
        print("torsion residuals", tor1, tor2, flush=True)
    # Pure big-O residuals are expected; PuiseuxSeries.is_zero() is strict and
    # deliberately returns false for an inexact zero.
    assert (x2_next/x1_next)^q != x2_next/x1_next

    # Descending representative: L_{i+1}=<v,T*w>.
    v0, v1 = alpha*b00 + beta*b01, alpha*b10 + beta*b11
    w0, w1 = gamma*b00 + delta*b01, gamma*b10 + delta*b11
    b00, b10, b01, b11 = v0, v1, t*w0, t*w1

    g, x1, x2 = g_next, x1_next, x2_next
    deep1, deep2 = deep1_next, deep2_next
    path.append(j_invariant(g))
    print("edge", i+1, "j valuation", path[-1].valuation(), flush=True)

assert len(path) == 64
v_end = ZZ(j_end.valuation())
assert all(path[-1][e] == j_end[e] for e in range(v_end, v_end+12))
key = hashlib.sha256(b"".join(_serialize_j(j) for j in path)).digest()
print("key =", key.hex())
if AES is not None:
    pt = AES.new(key, AES.MODE_CTR, nonce=b"", initial_value=iv).decrypt(ct)
    print("plaintext =", pt)
    assert pt.startswith(b"uiuctf{") and pt.endswith(b"}")

The decisive output was

period convergent 30 degrees 32 32
determinant (c^2 + c + 1)*t^64
...
edge 64 j valuation 6
key = 8fd3109dd1fc1a29f584987b779a3a50d1f90153bed4dd2ab42a104dee29711e
plaintext = uiuctf{REDACTED}

AES-CTR decryption with that key and the supplied IV yields a correctly formatted plaintext and completes the challenge.

Why the Failed Approaches Failed

1. Local reverse walking: each endpoint has five algebraic neighbors, with no local marker selecting the true predecessor. Every inversion also consumes too much Laurent precision.
2. Path enumeration: the graph exhibits the expected exponential growth and no early endpoint collisions; the full path has roughly 113 bits of branching entropy.
3. Greedy coefficient decoding: candidate branches can tie in endpoint-prefix agreement, and the best-looking local branch need not belong to the global path.
4. Normalized monic Ore reconstruction: coefficient equations are valid, but huge Frobenius exponents and catastrophic precision loss make endpoint-to-intertwiner reconstruction numerically unusable. The period lattice is the stable global representation.