Non-Canonical Encodings in On-Chain Post-Quantum Signatures

1. Start from a result that has already been verified

Fix a public key, a message and one valid signature. Can someone who does not hold the private key change only the bytes of that signature and have the verifier still accept it?

For an ETHFALCON verifier deployed on Sepolia, yes. Take one coefficient of a legitimate signature, change it from 157 to 12446 (that is, add the modulus $q = 12289$), leave every other byte alone, and the on-chain verification still returns true:

The object under test is ZKNOX ETHFALCON V0_0_2 at 0x328C56D4…de9C. The two transactions carry different keccak(s2) values, which is the proof that two genuinely different byte strings went in.

An ML-DSA verifier shows the same family of behaviour: a legitimate 2420-byte signature with eight non-zero bytes appended, 2428 bytes in total, is still accepted by the same deployment (section 6 has the evidence table).

What these experiments show is the acceptance behaviour of specific implementations at specific entry points. I did not obtain a valid authorization for any new message, and I did not demonstrate theft or repeated execution. The rest of this post explains where these byte variants come from, and why four different things — the specification text, a source-code version, a real deployment, and the application on top — have to be kept apart.

2. Threat model and terminology

2.1 What the attacker can do

One setting holds throughout:

• the attacker already holds a signature $\sigma$ that is valid for $(pk, m)$;
• the attacker does not hold the private key, and is not trying to obtain authorization for any new message $m^{*}$;
• the attacker modifies only the byte representation of $\sigma$, hoping to find $\sigma' \ne \sigma$ that the verifier still accepts.

I call such a $\sigma'$ an alias signature or a byte variant, and deliberately not a “forgery”, because that word is too easily read as “obtained a new authorization”.

2.2 EUF-CMA and SUF-CMA

A signature scheme is three algorithms, $(\mathsf{KeyGen}, \mathsf{Sign}, \mathsf{Verify})$. The standard security target, EUF-CMA (existential unforgeability under chosen-message attack), promises that an attacker who can request signatures on messages of their choosing still cannot produce a verifying signature on a new message they never queried.

EUF-CMA on its own does not rule out producing a second valid signature on an already-signed message. That constraint comes from the stronger notion, SUF-CMA (strong unforgeability).

A common misstatement needs correcting here: it is not the case that “post-quantum schemes lack SUF”. FIPS 204 (ML-DSA) is designed for strong unforgeability and puts the decoding-side checks directly in the standard text — Algorithm 21, HintBitUnpack, is required to return $\bot$ on a malformed hint encoding, and the standard requires public keys and signatures of the wrong length to be rejected. The Falcon specification likewise discusses unique encodings and the corresponding decoding checks.

So the subject of this post is not “the standards have a hole”. It is this: some implementations relaxed the parsing rules and therefore accept extra byte representations that the standards do not. The security guarantee of a standardized scheme does not carry over automatically to an implementation that changed what it accepts.

Three things are easy to conflate and are not the same:

1. The signer signs the same message again with the private key and gets a different signature (the ordinary behaviour of a randomized scheme; no conflict with strong unforgeability).
2. A third party derives a mathematically different signature object from an existing one. ECDSA’s $(r, s) \mapsto (r, n - s)$ is the ready-made example, and it shows that “a different mathematical object” is not the same as “unusable by a third party”.
3. A third party changes the encoding, so that the verifier accepts a different representation of the same object.

Every case in this post is of the third kind. Falcon’s random salt belongs to the first kind; it appears only as background and is not listed as a defect.

2.3 Encoding non-canonicality, stated precisely

Fix a parameter set, an encoding format and the semantic map. For a fixed $(pk, m)$ the verifier induces an acceptance set

and let $\phi$ send a byte string to the abstract signature object it represents. Encoding canonicality is the requirement that $\phi$, restricted to the acceptance set, be injective:

Violate it and you have an alias signature. Note that this is not a hardness question. Hardness assumptions constrain whether one can produce a valid signature on a new message; here the attacker produces no new signature, only a different spelling of an old one. A plain EUF-CMA reduction is therefore silent about this operation — which is exactly why the standards spell out the decoding checks separately instead of expecting them to fall out of hardness.

(The converse does not hold either: injectivity of the encoding does not imply strong unforgeability. They are separate properties that need separate arguments, not a tidy “orthogonal” pair.)

3. A small lattice toolbox

Falcon and ML-DSA are both lattice-based signatures. The examples in this post need only the following.

Polynomial rings. Both schemes compute in $R_q = \mathbb{Z}_q[x]/(x^n + 1)$. Falcon-512: $n = 512$, $q = 12289$. ML-DSA-44: $n = 256$, $q = 8380417 = 2^{23} - 2^{13} + 1$. A polynomial is a coefficient vector of length $n$, and the step “pack the coefficient vector into bytes” is precisely where encoding aliases breed.

Two conventions for representatives (the crucial one). A residue class mod $q$ contains infinitely many integer representatives, and practice uses two conventions:

• the standard representative, taken from $\{0, 1, \dots, q - 1\}$;
• the centred representative, taken from $(-q/2,\, q/2]$.

Example, with $q = 12289$: the value $-5$ has standard representative $12284$ and centred representative $-5$. The two are congruent mod $q$ and name the same ring element. This is the whole point of the next section’s bug: reducing mod $q$ changes no algebra, but “which convention do you measure size under” changes the result.

Norms. Take the centred representative $\tilde s_i$ of each coefficient and set $\|\mathbf{s}\|_2^2 = \sum_i \tilde s_i^2$ and $\|\mathbf{s}\|_\infty = \max_i |\tilde s_i|$. Verification in both schemes includes a “the solution is short enough” step (Falcon bounds $\ell_2$, ML-DSA bounds $\ell_\infty$), though full verification is more than that — ML-DSA also recomputes and compares the challenge hash. Only the norm step matters below.

The NTT is a bijection $R_q \cong (\mathbb{Z}_q)^n$ used purely to speed up polynomial multiplication; it introduces no encoding ambiguity of its own.

4. The main case: how a missing range check in a compact encoding produces mod-q aliases

4.1 Scope

This section is about the custom 16-bit compact representation used by ZKNOX ETHFALCON, and about the specific Sepolia deployment above. It is not a general property of standard Falcon compressed signatures — ETHFALCON’s hashing path also differs from standard Falcon.

Falcon is built on NTRU lattices, with public key $h = g f^{-1} \bmod q$. A signature is a pair of short polynomials $(s_1, s_2)$ satisfying

and only $(\text{salt}, s_2)$ is transmitted; the verifier recomputes $s_1$. Verification is roughly three steps: ① compute $\mathbf{c}$; ② $s_1 = \mathbf{c} - s_2 h \bmod q$; ③ check that $\|s_1\|_2^2 + \|s_2\|_2^2$ is within bound. The implementation under test uses the criterion norm < 34034726.

4.2 The missing line

The compact path reads each coefficient of $s_2$ as a 16-bit field $a \in [0, 2^{16})$. A correct parser must check $a < q$. The deployment above does not.

The per-coefficient logic the implementation uses to accumulate the norm is, in mathematical form,

I am calling this “the value folded for squaring” and deliberately not “the centring function”: for an in-range coefficient in the upper half, $q - a$ is exactly the negation of the centred value, and the squares agree, so on canonical input the logic is correct. It is not equal to centring for arbitrary integers, though. That property — “correct only on canonical input” — is exactly what breaks once the check is missing.

4.3 Constructing the alias

Take a valid signature, pick a coefficient $a$, and replace it by $a' = a + q$. For every canonical coefficient $0 \le a < q$ we have $a' = a + q \le 24577 < 65536$, so it always fits in the 16-bit field. Two invariants follow.

① The linear relation is unchanged. $a' \equiv a \pmod q$, and step ② is computed entirely mod $q$, so $s_2 h$ is unchanged, so $s_1$ is unchanged, so $\|s_1\|_2^2$ is unchanged.

② The norm contribution is unchanged — when $a \le 6144$. In that case $a' > q > 6144$ lands in the second branch:

Hence $\mathrm{fold}(a')^2 = (-a)^2 = a^2 = \mathrm{fold}(a)^2$. Both invariants hold at once, so $a'$ yields a signature with different bytes and the same verdict.

On the EVM: in unsigned 256-bit arithmetic $-a$ is represented as $2^{256} - a$, and

because the first two terms are multiples of $2^{256}$. That explains why the unsigned assembly “quietly” computes $a^2$ rather than failing or producing something else, but it is not a necessary ingredient of the alias — in ordinary signed integers $(-a)^2 = a^2$ holds just the same.

The root cause is not overflow. It is that the input range was never checked, so norm-handling logic that was only ever correct on canonical input was fed an out-of-range representation.

4.4 The boundary: why the upper half does not work

If $a \ge 6145$ (upper half, representing a small negative), the original contribution is $(q - a)^2$ while $a' = a + q$ contributes $a^2$, and the two differ. But “different contribution” does not yet give “rejected”; one more step is needed:

so this single term already exceeds the acceptance bound, and in the full-accumulation model the variant is rejected. (This is reasoning about the criterion under test, not a claim that every upper-half alias has been rejected empirically on the vendor deployment.)

4.5 How many

If a signature has $k$ coefficients satisfying the condition above, each can independently take either of $\{a, a + q\}$, giving $2^k$ accepted encodings, the original included. This is a combinatorial count, not an exhaustive test; the actual $k$ depends on the coefficient distribution of the particular signature, and I did not measure it. One correct line, require(a < q), closes all of them at once, upper half or lower.

4.6 The runnable mathematical core

1
Q = 12289
2
def fold_sq(x, q=Q):                          # the per-coefficient logic shown above (unsigned 256-bit)
3
    c = (q - x) % (2**256) if x > (q >> 1) else x
4
    return (c * c) % (2**256)
5

6
a = 5                                          # lower half
7
assert a % Q == (a + Q) % Q                    # ① congruent → s1 unchanged
8
assert fold_sq(a) == fold_sq(a + Q) == 25      # ② same folded square → contribution unchanged
9

10
b = Q - 5                                      # 12284, upper half (represents −5)
11
assert fold_sq(b) != fold_sq(b + Q)            # boundary: fails in the upper half
12
assert (6145 ** 2) > 34034726                  # and the new single term already exceeds the bound

The corresponding source fragment (this coefficient range check is present in the source version I compared against; the older deployment above lacks it):

1
// ZKNOX_falcon_core.sol (pinned source version)
2
let s2i := and(shr(shl(4, j), ai), 0xffff)          // take the 16-bit coefficient a
3
outOfRange := or(outOfRange, iszero(lt(s2i, q)))    // ← require a < q
4
let cond := gt(s2i, qs1)
5
let centered := add(mul(cond, sub(q, s2i)), mul(sub(1, cond), s2i))
6
norm := add(norm, mul(centered, centered))

5. Two more places: the container layer, and hints

5.1 The container layer: truncating division

The ERC-7913 entry point slices the salt (the first 40 bytes) and $s_2$ out of the signature, computing the word count of $s_2$ with integer division:

1
mstore(s2LengthSlot, div(sub(mload(sig), 40), 32))   // len = ⌊(sig.len − 40)/32⌋

The layer above requires len == 32, which solves to

In other words, append 1 to 31 arbitrary bytes to a legitimate 1064-byte signature: the truncating division discards them, $s_2$ is unchanged, the verdict is unchanged, and $\mathrm{keccak256}(\text{sig})$ is different. Local tests against the pinned source version confirm it: with 1, 7 and 31 bytes appended, the returned magic value is accept in every case, and the keccak differs each time.

The evidence boundary has to be stated plainly. This item was not run end to end against the vendor’s deployed ERC-7913 entry point. The vendor’s V0_0_2 setKey returns a uint256[] rather than a 20-byte pointer, which does not match that entry point’s public-key convention, and a direct call reverts. What I did instead was deploy the same wrapper myself on Sepolia (the div/32 logic identical byte for byte) for the on-chain demonstration. The strength of that evidence is “measured on an equivalent deployment”, not the vendor’s literal bytecode.

5.2 Hint encoding in ML-DSA-44

ML-DSA (module-lattice digital signatures, with security resting on module-lattice problems) has to reconstruct the high bits of a commitment during verification. To save bandwidth the signature carries a sparse hint $\mathbf{h}$ that corrects $\pm 1$ carries. For ML-DSA-44: $k = 4$ polynomials, at most $\omega = 80$ ones in total, encoded as a “position list” of $\omega + k = 84$ bytes — the first 80 bytes are the indices set to 1, the last 4 are a cumulative cursor per polynomial.

FIPS 204 Algorithm 21, HintBitUnpack, specifies the decoding checks and returns $\bot$ on a malformed encoding:

1
OMEGA, K = 80, 4                            # ML-DSA-44
2
def hint_bit_unpack(y):                     # y: 84 bytes
3
    h = [[0]*256 for _ in range(K)]
4
    idx = 0
5
    for i in range(K):
6
        end = y[OMEGA + i]
7
        if end < idx or end > OMEGA:        # check ③: cursors non-decreasing and ≤ ω
8
            return None
9
        first = idx
10
        while idx < end:
11
            if idx > first and y[idx] <= y[idx-1]:   # check ①: strictly increasing within a polynomial
12
                return None
13
            h[i][y[idx]] = 1
14
            idx += 1
15
    for j in range(idx, OMEGA):
16
        if y[j] != 0:                       # check ②: trailing padding all zero
17
            return None
18
    return h

The source of aliases is this: the semantics of a hint is just “which positions are set” — a set — and a position list can spell the same set in more than one way. But different relaxations admit different shapes, and they have to be kept apart. This is the point I got wrong in an earlier draft:

That is, turning the <= in check ① into < admits duplicates only; it does not admit descending order. The table covers only the ordering condition; the length, cursor and padding constraints still each have to be met, and to build a real duplicate-index variant you also need spare capacity, have to shift the following indices, and have to update the cumulative cursor to keep the total length. The $t!$ permutation count holds only in the model where the order check is absent altogether, and non-zero padding is governed separately by check ② — none of these belong to a single defect.

The difference between these shapes is measurable in real implementations. RustCrypto’s ml-dsa had a duplicate-hint-index defect (GHSA-5x2r-hc65-25f9, first fixed in 0.1.0-rc.4). With one set of vectors I measured: 0.1.0-rc.3 accepts the duplicate variant but rejects the out-of-order and non-zero-padding variants; 0.1.1 rejects all three. That matches the table exactly.

6. The evidence table, by object and entry point

Every row is pinned to “which implementation, which entry point, what strength”. Do not assemble these into an inherent property of an algorithm family.

Two things must be said precisely:

1. “The source fix is not on chain” is to be restricted to: “the particular older deployment I examined still lacks this check, while the source version I compared against includes it.” It does not license conclusions about every deployment or about the current latest state.
2. ML-DSA’s trailing bytes should not be blamed on a generic slice that uses >=. A slice requiring its input to be “at least long enough” is normal; what is missing is an equality check on the total length at the verification entry point.

On “delete one check” experiments

I ran a class of ablation experiments: in a pinned source version, remove one check and watch whether the verdict on the same input flips, to confirm that the check really does the rejecting in that version.

That is not a reproduction of the on-chain deployment. The saved source diff shows other differences between the two versions — the loop bound of the $s_1$ norm, the implementation of the $s_2$ norm loop. So the ablation answers “does this line do anything in this version”; the vendor deployment’s acceptance behaviour needs its own independent verification. The two experiments answer different questions, and neither licenses a claim that the two versions are equivalent. The ML-DSA delete-a-check version in particular must be labelled a synthetic control: the deployment source I checked carries all three checks to begin with.

7. What this means for applications

Whether an encoding alias matters to an application depends on how the application identifies an authorization. If a system uses the raw signature bytes, or their hash, as a deduplication key, then different representations of the same signature object can get different identities. But different bytes do not automatically mean repeatable execution: a nonce, the message contents, or already-consumed state may each block it.

Take ERC-4337: the standard userOpHash does not include the signature field, so changing only the signature bytes does not change that hash. What this post has verified is that some entry points accept byte variants; whether those variants affect a particular bundler, cache or account requires a separate experiment against that consumer, and cannot be inferred from the verifier’s acceptance behaviour.

At least four identities need separate discussion: the hash of the raw signature bytes, the hash of the full transaction that contains the signature, the UserOperation’s identifier, and any application-defined deduplication key.

The historical precedent is EIP-2. In 2016 Ethereum imposed the low-$s$ rule on transaction signatures, removing the $(r, s)$ versus $(r, n - s)$ ambiguity. Notably, the behaviour of the ecrecover precompile on high $s$ was not changed alongside it, and EIP-2 did not equate “a variant transaction hash appears” with “a duplicated transfer”.

A layered checklist

Placing each phenomenon at the stage “between bytes and verification” where it occurs gives a checklist. Its use is to say where to look; it is not a general theorem, and the parties responsible for the stages can overlap:

Where it earns its keep is discrimination: on the same ML-DSA deployment, the L2 (hint) checks are present while the L3 (total length) check is absent — without separating the stages it is easy to conclude, too broadly, that “this implementation is fine”.

8. Closing

What these cases keep telling me is that checking the mathematical relation is not enough. Which bytes the verifier accepts, whether the framing pins the length exactly, and how the application uses signatures and hashes, each need checking on their own. A strict inner decoder does not make the outer entry point strict — the ML-DSA case in this post has exactly that shape.

On cost, I want to write down one idea, but it has to be marked as an uncalibrated bookkeeping sketch, not a conclusion. The cost of one on-chain verification can be roughly split as

where XOF is the number of absorb and squeeze operations of the extendable-output function (SHAKE / Keccak) used to stretch a message or seed into a challenge polynomial or to expand a public key; mulmod is the number of modular multiplications, mostly from the NTT / inverse NTT and matrix-vector products; bytes is the volume of bytes that must be read, copied and hashed; canonical_check is the extra work of enforcing encoding canonicality, that is, the handful of lines this post keeps returning to — range checks, ordering and padding checks, length-equality assertions; and $\alpha, \beta, \gamma, \delta$ are the coefficients that turn each into gas.

The limits of the formula must be stated: the terms may overlap, a single $\delta$ cannot summarize checks of such different shapes, and I have not measured the incremental gas of any of these checks. So this post does not claim that canonicality checks are necessarily expensive for lattice schemes and near-free for hash-based ones, and it certainly does not claim that the missing checks were a deliberate gas trade-off by the implementers — I have no cost data and no evidence about motive. Fixed-length structures need strict validation of lengths, field ranges and outer framing just the same; parsing canonicality cannot be inferred from the signature family. Leaving “how much gas do these checks actually cost” as a measurable follow-up question is more honest than concluding now.

The evidence supports exactly two conclusions: whether a check exists must be settled per version and per entry point; and a fix in source has to be verified against the actual deployment, separately.