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:

...