Interesting Signing: One Byte Into the Modulus, Then an Orthogonal Lattice Factors It

Interesting Signing was a crypto challenge at WannaGame Championship 2025, where our team blackpinker took first place in the international division. It opens looking like a memory-safety bug and closes as a lattice problem: the overflow is real, but all it buys is one byte of the modulus, and the work is in seeing what that byte is worth. This write-up first appeared on HackMD; the explanation of the lattice step is the one I owed my notes.

The service

The server holds an RSA key whose modulus $N$ is the product of three 1024-bit primes, so $N$ is 3072 bits, and it signs with the CRT. Everything on the wire is a custom base85 encoding; a signature is 384 bytes, which is 480 characters.

Per connection you get 21 rounds. In each round you either ask it to sign a message you supply, or ask it to verify one. The goal is a valid signature on a fixed 64-byte challenge string that the server will never sign for you:

1_d4r3_y0u_70_519n_7h15_3x4c7_51x7y_f0ur_by73_57r1n9_w17h_my_k3y

So you need the private key, which means factoring $N$.

The overflow, and what it is actually worth

The message buffer holds 64 bytes, and the modulus sits immediately after it. A 65-byte message writes one byte past the end, into the most significant byte of $N$. In the base85 encoding 65 bytes is 85 characters, so the last character of an 85-character payload is the one that lands on the modulus.

That sounds like a disaster for the server and it is, but not in the obvious way. It does not leak a prime and it does not let you choose a convenient modulus: the private primes are stored separately and are untouched, and so are the CRT coefficients, which this implementation precomputes once from the real $N$. The corrupted $N$ is used for one thing only, the final reduction.

A CRT signature is assembled as

Call the sum before the reduction $H$. Each $a_i$ is below its prime, so below $2^{1024}$; each $y_i$ is below $N$, so below $2^{3072}$; and $H<3\cdot 2^{4096}$, comfortably under $2^{4100}$. The reduction by $N\approx 2^{3072}$ throws away about a thousand bits of it, and normally those bits are gone.

With the overflow they are not. Sign the same message twice, once with the modulus byte set to one value and once to another:

$H$ is identical in both, because it depends only on the message and the untouched primes. Two residues under two coprime moduli whose product is about $2^{6144}$ determine $H$ exactly, since $H$ is far smaller than that:

recovered = crt(sigs, moduli)   # the exact integer, no reduction left

Two signatures, one equation over the integers. That is the whole value of the overflow.

Ten equations, and the shape of the unknowns

Repeat with ten different messages, two signatures each. Twenty rounds, and the twenty-first is the one that submits the forgery.

or $\mathbf{b}=A\mathbf{y}$, where $\mathbf{b}$ is the ten recovered integers, $A$ is $10\times 3$ with unknown entries below $2^{1024}$, and $\mathbf{y}$ holds the three secret CRT coefficients, each near $2^{3072}$.

Ten equations, thirty-three unknowns: hopeless as linear algebra. What makes it tractable is the size gap. The entries of $A$ are a thousand bits; the entries of $\mathbf{y}$ are three thousand. A lattice can see that difference even though an equation solver cannot.

TIP

I first tried this with nine equations and got nothing usable. The attack needs enough rows that the orthogonal lattice has room: with $n$ equations and three unknown columns, the vectors orthogonal to $\mathbf{b}$ that are also orthogonal to all of $A$'s columns form a sublattice of rank $n-3$, and that margin is what lets LLL separate them from the rest. At nine it was too tight; at ten it fell out.

The orthogonal lattice, step by step

Find vectors orthogonal to $\mathbf{b}$. Build a lattice whose vectors are $(⟨\mathbf{u},\mathbf{b}⟩,\mathbf{u})$ and weight the first coordinate enormously, so that LLL will pay almost any price in the other coordinates to drive it to zero:

b = matrix(recovered_sigs).T                      # 10 x 1
M = block_matrix([[b, identity_matrix(10)]])
W = diagonal_matrix([2**4000] + [1]*10)
L = ((M * W).LLL()) / W                            # rows: (0, u) with u . b = 0

Why those $\mathbf{u}$ are orthogonal to $A$'s columns too. If $⟨\mathbf{u},\mathbf{b}⟩=0$ then $⟨\mathbf{u},A\mathbf{y}⟩=⟨A^T\mathbf{u},\mathbf{y}⟩=0$. Now $A^T\mathbf{u}$ is a 3-vector whose entries are small, because both $A$ and the reduced $\mathbf{u}$ are small, while $\mathbf{y}$'s entries are around $2^{3072}$. A short integer combination of huge numbers cannot vanish unless the coefficients are all zero, so $A^T\mathbf{u}=0$. This is the standard orthogonal-lattice argument, and it is a heuristic that depends on the gap being wide enough: it is exactly why nine rows were not enough.

Take the first seven. The vectors orthogonal to $\mathbf{b}$ form a lattice of rank 9; those also orthogonal to all three columns of $A$ form a sublattice of rank $10-3=7$, and they are the shortest, so LLL puts them first:

O = matrix(ZZ, [row[1:] for row in L[:7]])

Now invert the relation. The columns of $A$ lie in the orthogonal complement of $O$'s row space, a 3-dimensional space. Build the orthogonal lattice of $O$ the same way, reduce, and the first three rows span it:

M = block_matrix(ZZ, [[O.T, identity_matrix(O.ncols())]])
W = diagonal_matrix([2**2000]*O.nrows() + [1]*O.ncols())

Enumerate a small box. The columns of $A$ are short vectors in that 3-dimensional space, and after LLL the basis is already nearly as short as they are. A vector that is itself close to the successive minima is a combination of reduced basis vectors with small coefficients, which is why an enumeration over $-3\le c_i\le 3$ finds them:

for coord in product(range(-3, 4), repeat=3):
    v = vector(ZZ, coord) * M_reduced[:3]
    if all(abs(i) < 2**1024 for i in v):
        candidates.append(v)

I did not understand this bound when I used it, and the honest version is that it is a heuristic, not a theorem: LLL in dimension three returns a basis within a small factor of the shortest vectors, so the coefficients needed are small, and $\pm 3$ is a box that is cheap to search ($7^3=343$ points) and wide enough in practice. If it comes up empty, widen it; the cost grows as the cube.

From $A$ to the primes. Any three independent candidates let you solve for $\mathbf{y}$, and each $y_i$ carries the factorisation with it, because $y_i$ is a multiple of $N/p_i$ by construction:

for cols in combinations(candidates, 3):
    try:
        y = column_matrix(cols).solve_right(b)
    except (ValueError, ArithmeticError):
        continue
    primes = [N // gcd(int(yi[0]), N) for yi in y]
    if prod(primes) == N:
        break

The check prod(primes) == N is what makes the enumeration safe: wrong candidates simply fail it.

Forging the signature

With three primes in hand the rest is bookkeeping:

phi = prod(p - 1 for p in primes)
d = pow(65537, -1, phi)
sig = pow(bytes_to_long(sha256(target).digest()), d, N)
payload = b85_encode(long_to_bytes(sig).rjust(384, b"\x00"))   # 480 characters

Then the twenty-first round verifies it and the server gives up the flag. (My notes kept the method and the script but not the flag string, so it is not reproduced here.)

What to take from it

The bug is not the overflow; it is what the overflow reaches. One byte of a public value looks harmless, and in a sense it is: the attacker learns nothing from $N$ changing. What changes is that the same secret quantity gets reduced two different ways, and two reductions of one number are an equation. Any implementation that lets an attacker vary the modulus while holding the private parameters fixed has this shape, and signing is only the most convenient place to notice it.

Fault attacks on CRT-RSA are an old family, and this is a gentle member of it. The classic one (Boneh, DeMillo and Lipton) needs only a single faulty signature to factor $N$ by a gcd, because the fault lands in the arithmetic. Here the fault lands in the final reduction instead, so no single signature is wrong in a useful way, and it takes ten pairs and a lattice. The defence is the same either way: verify the signature with the public exponent before returning it, and refuse to emit one that does not check out. A verification step would have caught every one of the twenty signatures this attack depends on.

And bound the buffer. The reason the modulus was reachable at all is a 64-byte write into a 64-byte buffer followed by one more. Everything above is downstream of that single missing length check.