Small ROS: Eighty-One Random-Oracle Equations That Collapse Into One Subset-Sum

Small ROS was a crypto challenge in the m0leCon 2026 finals. Its flag gives away the intended solution — Wait_its_all_Wagner?_Always_has_been — and Wagner's generalised birthday algorithm is indeed the classical way to attack a ROS instance. I did not use it. The route I took reduces the whole verifier to a single modular subset-sum and hands that to a lattice, which turns out to be enough because the challenge hands the attacker more free bits than the modulus has.

What the verifier wants

The service fixes a prime $p=23546938480736113$, a dimension $d=80$, and a hash $H$ that is a salted random oracle reachable through a query endpoint, with a budget of 250 queries. It then asks for $81$ distinct rows ${\rho }_i$ and a vector $c\in {\mathbb{F}}_p^{80}$ such that

with every entry of every row reduced mod $p$ and at most $2$. That restriction to $\{0,1,2\}$ is what the "small" in the title means.

This is the ROS problem: find Random inhomogeneities in an Overdetermined Solvable system of linear equations. It is not a decorative setting. The hardness of ROS is exactly what the unforgeability of blind Schnorr signatures rests on, so a construction that makes ROS easy is a construction that makes blind signatures forgeable.

The system is overdetermined — 81 equations, 80 unknowns — and the right-hand sides are random oracle outputs, so it looks like nothing can be solved. What makes it tractable is one detail: the rows are not given to us. We choose them.

Eighty equations that are not really equations

Pick a row with a single nonzero coordinate. Then that equation touches one unknown and nothing else. Since $p$ is odd, $2$ is invertible, so there are two useful choices per coordinate:

Query the oracle on all $e_i$ and all $2e_i$ — 160 queries, leaving 90 of the budget — and every coordinate of $c$ now has exactly two legal values. Eighty of the verifier's equations have stopped being constraints and become a menu: 80 free binary choices.

The rows are required to be distinct, which costs nothing here, since $e_i$ and $2e_j$ are distinct for all $i,j$.

The one equation that couples them

Only the 81st row touches more than one coordinate. Take it binary, $w\in \{0,1{\}}^{80}$, and call its support $S$. Writing $x_i\in \{0,1\}$ for the choice at coordinate $i$ — $0$ keeps $a_i$, $1$ takes $b_i$ — the last equation

expands to

which rearranges into a modular binary subset-sum:

Solve for the bits and everything else is determined: the bits fix $c$, and $c$ fixes which of $e_i$ or $2e_i$ each row must be.

Why a solution exists, and how large to make the support

This is the part my contest notes recorded only as an observation — support sizes near 58 worked, 56 did not — and it is worth doing the arithmetic, because it explains the whole shape of the search.

The modulus is $54.39$ bits. A support of size $n$ gives $2^n$ candidate bit vectors whose sums are spread over $p$ residues, so the expected number that land on $T$ is $2^n/p$. The lattice difficulty, meanwhile, is governed by the density $n/{\log }_{2}p$, which classical analysis puts in easy territory below about $0.94$ and hard territory around $1$.

The two columns pull against each other. Below about 55 coordinates there is usually no solution to find, however good the solver. Above that, solutions become plentiful but each instance sits further into the dense regime where a single lattice reduction is less likely to return one. Fifty-eight is where both are comfortable: a dozen expected solutions, density just past 1. That the empirical schedule converged on 58, with 57 and 59 as neighbours, is not luck — it is the only place the two curves overlap.

TIP

Density above the classical threshold does not mean a lattice cannot help. The usual bounds assume a unique solution and ask the lattice to find it; here there are a dozen, and finding any one of them is a much easier target. When an instance is denser than the textbook says is solvable, check how many solutions it has before concluding the approach is wrong.

Solving the subset-sum

Exact formulations were the first thing I tried and the wrong tool: a Z3 encoding over finite-domain booleans returned unknown under short timeouts, a Sage/GLPK route was not usable in my environment, and OR-Tools CP-SAT imported cleanly but still returned UNKNOWN inside the time budget. Eighty-bit coefficients with a modular wrap are not what those solvers are good at.

What worked was a lattice embedding. For a support of size $n$, build an $(n+1)\times (n+1)$ basis with $2$ on the diagonal, the scaled weights down the last column, a row of ones, and the scaled target in the final entry. Reduce with LLL and then BKZ, and scan the short rows — and small combinations of them — for vectors whose entries are all $\pm 1$ with a zero in the last coordinate. Those decode straight back into the binary indicator.

The modular equation has to be lifted to an exact one first:

for some integer wrap $k$. Scanning $k$ upward from zero wastes nearly all of the work: since the ${\mathrm{\Delta }}_i$ are uniform in $[0,p)$, the sum of a weight-$m$ subset is concentrated near $mp/2$, so the plausible wraps cluster around $m/2$. Searching outward from the statistically likely value rather than from zero is what made the solver finish in seconds.

Running it against the service

Each connection is a fresh instance: the oracle's salt is session-specific, so the same row queried on a new connection returns a different value. That makes reconnecting part of the strategy rather than a fallback. The exploit loop is:

1. query all $e_i$ and $2e_i$ to build $a$ and $b$ — 160 of 250 queries;
2. try a schedule of random supports at sizes 58, 57, 59, 56, 60, 55;
3. for each, lift and solve the subset-sum;
4. on success, reconstruct the 81 rows and $c$, and submit;
5. if a session yields nothing quickly, drop it and open a new one.

One protocol detail cost me more time than the mathematics: after each JSON reply the server printed its next prompt without a newline, so a wrapper that read only the reply line drifted out of step and died on a JSONDecodeError several exchanges later. Reading the reply and then consuming up to the prompt fixed it. On the successful run the first support tried was enough:

[+] connection attempt 1
[+] support attempt 1: size=58
{"msg": "Congratulations! Here is your flag: ptm{Wait_its_all_Wagner?_Always_has_been}"}

What the challenge is really about

The verifier looks like it is asking for something hard, and the random oracle is genuinely out of reach: nothing here inverts $H$, finds a collision, or predicts an output. The break comes entirely from who chooses the rows.

Three properties combine, and removing any one of them closes it:

• The attacker picks the query points. Rows with a single nonzero entry turn equations into lookups. A ROS instance where the rows are fixed by the protocol, or derived from a commitment made before the hashes are seen, has no such structure.
• Each coordinate gets more than one legal value. Allowing entries in $\{0,1,2\}$ rather than $\{0,1\}$ is what makes $2e_i$ a second query for the same coordinate, and so what turns each coordinate into a free bit. Restricting rows to $\{0,1\}$ removes the menu entirely.
• The dimension exceeds the modulus in bits. With $d=80$ free bits against a $54.4$-bit prime there are about $2^{25}$ expected solutions overall, so one is guaranteed to exist long before any clever search begins. This is the same threshold that governs the known polynomial-time attacks on ROS when the dimension passes ${\log }_{2}p$, and it is why a production parameter set must keep the dimension well below it.

That last point is the one worth carrying away from a challenge into a real design. For blind Schnorr signatures the dimension is the number of concurrent signing sessions an attacker may open. "How many sessions may run at once" reads like a capacity question and is actually the security parameter.