链上后量子签名的编码非规范性

1. 先看一个已经验证过的结果

给定同一个公钥、同一条消息和一份有效签名，一个没有私钥的人，能不能只改动签名的字节，让验证器仍然接受？

在一个部署于 Sepolia 的 ETHFALCON 验证器上，答案是能。把合法签名里的一个系数从 157 改成 12446（也就是加上模数 $q=12289$ ），其余字节不动，链上验证结果仍然是 true：

交易	label	accepted	`keccak(s2)`	coeff₀
`0xa990c588…`	`canonical`	true	`0x390f246f…`	157
`0x3041516d…`	`modq-alias`	true	`0x6bcfe455…`	12446

被测对象是 ZKNOX ETHFALCON V0_0_2，地址 0x328C56D4…de9C；两笔交易的 keccak(s2) 不同，证明喂进去的确实是两条不同的字节串。

在另一个 ML-DSA 验证器上也有同类现象：一条 2420 字节的合法签名，尾部追加 8 个非零字节变成 2428 字节，同一部署仍返回 true（见第 6 节证据表）。

这些实验展示的是特定实现与特定入口的接受行为。 我没有因此获得任何新消息的有效授权，也没有证明资产盗取或重复执行。下面解释这些字节变体是怎么产生的，以及应当如何区分规范文本、源码版本、真实部署、上层应用这四件不同的事。

2. 威胁模型与术语

2.1 攻击者能做什么

本文自始至终固定同一个设定：

攻击者已经持有一份对 $(pk,m)$ 有效的签名 $\sigma$ ；
攻击者不持有私钥，也不试图为新消息 $m^{*}$ 取得授权；
攻击者只修改 $\sigma$ 的字节表示，希望得到 $\sigma'\ne\sigma$ 仍被验证器接受。

得到的 $\sigma'$ 我称为别名签名或字节变体，不称「伪造」——后者容易被误读成取得了新的授权。

2.2 EUF-CMA 与 SUF-CMA

签名方案是三个算法 $(\mathsf{KeyGen},\mathsf{Sign},\mathsf{Verify})$ 。标准安全目标 EUF-CMA（选择消息攻击下的存在性不可伪造）保证：攻击者即使能查询任意消息的签名，也无法对一条从未查询过的新消息造出通过验证的签名。

EUF-CMA 本身并不排除对已签消息构造出另一份有效签名；施加这一约束的是更强的 SUF-CMA（强不可伪造）。

这里必须澄清一个常见的误述：并不是「后量子方案不满足 SUF」。 FIPS 204（ML-DSA）以强不可伪造为设计目标，并在标准正文中直接规定了解码侧的检查——Algorithm 21 的 HintBitUnpack 明确要求对不合规的 hint 编码返回 $\bot$ ，标准也要求拒绝长度不符的公钥与签名。Falcon 的规范同样讨论了唯一编码与相应的解码检查。

因此本文考察的对象不是「标准有漏洞」，而是：部分实现放宽了解析规则，于是接受了标准本不接受的额外字节表示。标准方案的安全保证，不能自动套用到改变了接受规则的实现上。

顺带区分三件容易混淆的事，它们不是一回事：

签名者用私钥对同一消息再签一次，得到不同签名（随机化签名的正常性质，与强不可伪造并不冲突）；
第三方从已有签名算出另一个数学上不同的签名对象——ECDSA 的 $(r,s)\mapsto(r,n-s)$ 就是现成反例，说明「数学对象不同」并不等于「第三方不可利用」；
第三方改变编码，让验证器接受同一个对象的另一种表示。

本文全部案例属于第三类。 Falcon 的随机 salt 属于第一类，只作为背景，不列为缺陷。

2.3 编码非规范性的精确说法

固定参数集、编码格式与语义映射之后，设验证器对固定 $(pk,m)$ 诱导一个接受集

\mathcal{A}_{pk,m}=\{\,b : \mathsf{Verify}(pk,m,b)=1\,\},

并设 $\phi$ 把字节串映到它所代表的抽象签名对象。编码规范性即要求 $\phi$ 限制在接受集上是单射：

\forall b_1,b_2\in\mathcal{A}_{pk,m}:\quad \phi(b_1)=\phi(b_2)\ \Longrightarrow\ b_1=b_2.

违反它，就得到一个别名签名。要注意这不是一个困难性问题：困难性假设约束的是「能否产生新消息的有效签名」，而这里攻击者不产生新签名，只是换个写法。所以单纯的 EUF-CMA 归约对这类操作是沉默的——这正是为什么标准要另行明文规定解码检查，而不是指望它从困难性里自动导出。

（反过来也不能推：编码单射本身并不蕴含强不可伪造，两者是需要分别论证的性质，不是简单的「正交」关系。）

3. 一点格密码工具箱

Falcon 与 ML-DSA 都是格基签名。看懂本文的例子只需要下面几件工具。

多项式环。 两者都在 $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$ 。一个多项式就是长度 $n$ 的系数向量——「把系数向量打包成字节」这一步，正是编码别名的滋生地。

两套代表元约定（关键）。 一个模 $q$ 剩余类含无穷多个整数代表，实践中常用两套约定：

标准代表元：取 $\{0,1,\dots,q-1\}$ ；
中心化代表元：取 $(-q/2,\,q/2]$ 中的那个。

例（ $q=12289$ ）：值 $-5$ 的标准代表元是 $12284$ ，中心化代表元是 $-5$ ；二者模 $q$ 同余，指向环里同一个元素。这正是下一节漏洞的要害：约化 mod $q$ 不改变代数，但「按哪套约定测量大小」会改变结果。

NTT 是 $R_q\cong(\mathbb{Z}_q)^n$ 的双射，纯粹用于加速多项式乘法，本身不引入编码歧义。

4. 主案例：紧凑编码里缺失的范围检查，如何产生 mod-q 别名

4.1 研究对象的限定

本节研究的是 ZKNOX ETHFALCON 使用的自定义 16-bit 紧凑表示，以及上文那个具体的 Sepolia 部署。这不是标准 Falcon 压缩签名的普遍性质——ETHFALCON 的哈希路径与标准 Falcon 也有区别。

Falcon 建在 NTRU 格上，公钥 $h=g f^{-1}\bmod q$ 。签名是一对短多项式 $(s_1,s_2)$ 满足

s_1+s_2 h=\mathbf c \pmod q,\qquad \mathbf c=\mathsf{HashToPoint}(\text{salt}\|m),

签名只传 $(\text{salt},s_2)$ ， $s_1$ 由验证端反算。验证大致三步：① 算 $\mathbf c$ ；② $s_1=\mathbf c-s_2h \bmod q$ ；③ 检查 $\|s_1\|_2^2+\|s_2\|_2^2$ 未超界。所测实现使用的判据是 norm < 34034726。

4.2 缺失的那一行

紧凑路径把 $s_2$ 的每个系数当作一个 16-bit 字段 $a\in[0,2^{16})$ 读入。正确的解析必须检查 $a<q$ 。 上面那个部署缺这个检查。

实现中用于累加范数的逐系数逻辑，写成数学是：

\mathrm{fold}(a)=\begin{cases}a & a\le\lfloor q/2\rfloor=6144\\[2pt] q-a & a>6144\end{cases},\qquad \text{贡献}(a)=\mathrm{fold}(a)^2 \bmod 2^{256}.

我特意把它叫作「用于平方的折叠值」而不是「中心化函数」：对规范范围内的上半区系数， $q-a$ 恰是中心化值的相反数，平方后相同，所以在规范输入下这个逻辑是对的；但它对任意整数并不等于中心化。这个「只对规范输入成立」的性质，就是缺检查之后出问题的地方。

4.3 别名的构造

取一个合法签名，挑一个系数 $a$ ，替换成 $a'=a+q$ 。对所有规范系数 $0\le a<q$ ，都有 $a'=a+q\le 24577<65536$ ，所以永远塞得进 16-bit 字段。两个不变量：

① 线性关系不变。 $a'\equiv a \pmod q$ ，而第 ② 步整条在 mod $q$ 下计算，故 $s_2h$ 不变 ⇒ $s_1$ 不变 ⇒ $\|s_1\|_2^2$ 不变。

② 范数贡献不变——当 $a\le 6144$ 时。 此时 $a'>q>6144$ ，落入第二分支：

\mathrm{fold}(a')=q-a'=q-(a+q)=-a .

于是 $\mathrm{fold}(a')^2=(-a)^2=a^2=\mathrm{fold}(a)^2$ 。两个不变量同时成立 ⇒ $a'$ 给出一个字节不同、验证结果相同的签名。

关于 EVM：在无符号 256 位算术里 $-a$ 表示为 $2^{256}-a$ ，而

(2^{256}-a)^2=2^{512}-2\cdot 2^{256}a+a^2\equiv a^2 \pmod{2^{256}},

因为前两项都是 $2^{256}$ 的整数倍。这解释了无符号汇编为什么会「安静地」算出 $a^2$ 而不是报错或给出别的值，但它不是这个别名现象的必要条件——在普通有符号整数里 $(-a)^2=a^2$ 同样成立。

根因不是溢出，而是：输入范围没有被检查，使原本只对规范输入成立的范数处理逻辑，接收了越界的表示。

4.4 边界：为什么上半区不行

若 $a\ge 6145$ （上半区，代表小负数），原贡献是 $(q-a)^2$ ，而 $a'=a+q$ 给出贡献 $a^2$ ，二者不等。但「贡献不同」还推不出「被拒绝」——要补一步：

a\ge 6145\ \Longrightarrow\ a^2\ge 6145^2=37{,}761{,}025\ >\ 34{,}034{,}726,

单这一项就已超过接受界，因此在完整累加的模型中该变体会被拒。（这是对所测判据的推理，不等于「原厂所有上半区别名都已被实测拒绝」。）

4.5 数量

若一份签名里有 $k$ 个满足上述条件的系数，每个可独立取 $\{a,a+q\}$ ，即可构造 $2^{k}$ 个通过验证的编码（含原编码）。这是组合计数，不是穷举实测；具体 $k$ 取决于该签名的系数分布，本文未做统计。而一行正确的 require(a < q) 一次性堵死全部，无论上下半区。

4.6 可运行的数学核

1
Q = 12289
2
def fold_sq(x, q=Q):                          # 对应所展示的逐系数逻辑（无符号 256 位）
3
    c = (q - x) % (2**256) if x > (q >> 1) else x
4
    return (c * c) % (2**256)
5

6
a = 5                                          # 下半区
7
assert a % Q == (a + Q) % Q                    # ① 同余 → s1 不变
8
assert fold_sq(a) == fold_sq(a + Q) == 25      # ② 折叠平方相同 → 贡献不变
9

10
b = Q - 5                                      # 12284，上半区（代表 -5）
11
assert fold_sq(b) != fold_sq(b + Q)            # 边界：上半区不成立
12
assert (6145 ** 2) > 34034726                  # 且新单项已超接受界

对应的源码片段（该系数范围检查已存在于所比较的源码版本中，而上文那个旧部署缺少它）：

1
// ZKNOX_falcon_core.sol（固定源码版本）
2
let s2i := and(shr(shl(4, j), ai), 0xffff)          // 取 16-bit 系数 a
3
outOfRange := or(outOfRange, iszero(lt(s2i, q)))    // ← 要求 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. 容器层与 hint：另外两处

5.1 容器层：整除截断

ERC-7913 入口从签名里切出 salt（前 40 字节）与 $s_2$ ， $s_2$ 的字数用整除算：

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

上层要求 len == 32，解出

\text{sig.len}\in[\,40+32\cdot 32,\ 40+32\cdot 33-1\,]=[1064,\ 1095].

即在 1064 字节的合法签名后追加 1–31 个任意字节，整除截断把它们丢弃， $s_2$ 不变、裁决不变，但 $\mathrm{keccak256}(\text{sig})$ 变了。本地对固定源码版本的测试确认：追加 1 / 7 / 31 字节，返回的 magic 值均为接受，keccak 各不相同。

证据边界要说清楚：这一项没有在原厂部署的 ERC-7913 入口上跑通。原厂 V0_0_2 的 setKey 返回 uint256[] 而非 20 字节指针，与该入口的公钥约定不同，直接调用会 revert。我最终是在 Sepolia 上自行部署了同一份 wrapper（div/32 逻辑逐字相同）来做链上演示，强度为「等价部署实测」，不是原厂 literal 字节码。

5.2 ML-DSA-44 的 hint 编码

ML-DSA（模块格数字签名，安全性建立在模块格问题上）的验证需要重建承诺的高位。为省带宽，签名传一个稀疏的提示 $\mathbf h$ 用于修正 $\pm1$ 的进位。以 ML-DSA-44 为例： $k=4$ 个多项式、总共最多 $\omega=80$ 个 1，用「位置列表」编码成 $\omega+k=84$ 字节——前 80 字节是被置 1 的索引，后 4 字节是每个多项式的累计游标。

FIPS 204 Algorithm 21 HintBitUnpack 规定了解码检查，对不合规编码返回 $\bot$ ：

1
OMEGA, K = 80, 4                            # ML-DSA-44
2
def hint_bit_unpack(y):                     # y: 84 字节
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:        # 检查③：游标非降且 ≤ ω
8
            return None
9
        first = idx
10
        while idx < end:
11
            if idx > first and y[idx] <= y[idx-1]:   # 检查①：同多项式内索引严格递增
12
                return None
13
            h[i][y[idx]] = 1
14
            idx += 1
15
    for j in range(idx, OMEGA):
16
        if y[j] != 0:                       # 检查②：尾部填充全 0
17
            return None
18
    return h

别名的来源是：hint 的语义只是「哪些位置被置 1」（一个集合），而位置列表能用多种字节表示同一个集合。 但不同的松弛会放行不同的形态，必须分开讲——这是我上一稿弄错的地方：

输入形态	严格递增（`<=` 拒绝）	仅拒降序（`<` 拒绝）	完全不检查顺序
`[1, 3]`	接受	接受	接受
`[1, 1, 3]`（重复）	拒绝	接受	接受
`[3, 1]`（降序）	拒绝	拒绝	接受

也就是说，把检查①的 <= 写成 <，只会放行「重复」，不会放行「降序」。上表只涉及顺序条件，长度、游标、填充等约束仍需分别满足；构造真实的重复索引变体时，还要有剩余容量、移动后续索引并更新累计游标以保持总长。 $t!$ 种排列只在「顺序检查完全缺失」的模型下才成立，非零填充则由检查②单独决定——不能把这些都归给同一个缺陷。

这些形态在实现中的差异是可以实测的。RustCrypto 的 ml-dsa 曾有一个重复 hint 索引的缺陷（GHSA-5x2r-hc65-25f9，首个修复版本 0.1.0-rc.4）。我用同一组向量实测：0.1.0-rc.3 接受重复变体，但拒绝乱序与非零填充；0.1.1 三者全拒。这与上表完全吻合。

6. 证据表：按对象与入口分开

每一行都限定「哪个实现、哪个入口、什么强度」。不要把这些拼成算法家族的固有属性。

现象	实验对象与入口	证据	可以写的结论
ETHFALCON mod-q 别名	原厂 Sepolia V0_0_2 `0x328C…de9C`，四参数入口；runtime keccak 与锚定快照一致	只读调用 + 两笔链上探针交易（见第 1 节）	原签名与一个 `157→12446` 别名均被该部署接受
Falcon 尾部截断	本地固定源码 wrapper；自行部署的 Sepolia wrapper，ERC-7913 入口	本地追加 1 / 7 / 31 字节；自部署链上追加 7 字节（1064 与 1071 均 accepted）	截断机制已复现；不能写成已在原厂 ERC-7913 入口动态成功
ML-DSA hint 检查	两份已验证部署源码的本地测试；RustCrypto 历史版本对照	部署源码保留三类检查，本地测试拒绝所列变体；rc.3 单独接受重复	已知库缺陷与所测链上实现行为不同，不能归为 ML-DSA 固有缺陷
ML-DSA 尾随字节	原厂 Sepolia mldsaeth V0_0_3 `0xA7D6…1C34`，四参数 `verify(bytes,bytes,bytes,bytes)`	交易 `0x117d07dd…`（2420 字节，accepted=true）与 `0xfdcd3d5f…`（追加 `deadbeefcafebabe` 后 2428 字节，accepted=true），`keccak(sig)` 不同	该入口接受所展示的尾随字节变体；不能推广为已跑通有效 ERC-7913 / UserOp 利用

两点必须写清：

「源码修复未上链」应限定为：「所检查的那个旧部署仍缺少该项检查，而所比较的源码版本已包含它。」不能据此推断所有部署或当前最新状态。
ML-DSA 的尾随字节不应归罪于通用 slice 用了 >=。切片要求输入「至少够长」是正常的；缺的是验证入口的总长度相等检查。

关于「删掉一行检查」这类实验

我做过一类消融实验：在固定的源码版本里移除某一项检查，观察同一输入的接受结果是否翻转，以确认该检查在这一版本中确实承担了拒绝作用。

这不等于复刻了链上部署。 已保存的源码差异显示，两版之间还存在 $s_1$ 范数循环边界、 $s_2$ 范数循环实现等其他差异。所以：消融实验回答的是「这一行在这一版本里起不起作用」，对原厂部署的接受行为则要另做独立验证。两组实验回答不同问题，不能据此宣称两个版本等价。ML-DSA 的删检查版本尤其要标为人为构造的对照版——所核对的部署源码本来就带着那三条检查。

7. 这对应用意味着什么

编码别名是否影响应用，取决于应用如何识别一份授权。如果系统直接把原始签名字节或其哈希当作去重键，同一签名对象的不同表示就可能得到不同标识。但字节不同不自动意味着能够重复执行：nonce、消息内容与已消费状态都可能挡住它。

以 ERC-4337 为例：标准的 userOpHash 不包含 signature 字段，因此单独改变签名字节不会改变该哈希。本文已经验证的，是部分入口接受字节变体；这些变体是否影响某个 bundler、某个缓存或某个账户，需要针对该消费方式另做实验，不能从验证器的接受行为直接推出。

需要分别讨论的至少有四种标识：原始签名字节的哈希、包含签名的完整交易哈希、UserOperation 的标识、以及应用自定义的去重键。

历史上的先例是 EIP-2：以太坊在 2016 年对交易签名施加了低 $s$ 限制，消除 $(r,s)$ 与 $(r,n-s)$ 的二义性。值得注意的是，ecrecover 预编译对高 $s$ 的行为并未同步改变；EIP-2 也没有把「交易哈希出现变体」等同于「重复转账」。

分层检查清单

把上面的现象按「发生在从字节到验证的哪一环」归位，可以得到一份检查清单。它的用处是提示该去哪儿看，而不是一个通用定理；各环的责任主体可以重叠：

环节	要检查什么	本文实例
L1 数学（背景）	同一 $(m,pk)$ 是否存在多个合法签名对象	Falcon 随机 salt——第三方无陷门，不属于本文攻击模型
L2 内部对象解码	系数 / 索引的范围、顺序、填充是否被严格约束	mod-q 范围检查缺失；hint 三条检查
L3 外层长度与定界	入口是否精确限定总长，是否存在截断或忽略	`div/32` 尾部字节；签名总长不校验
L4 上层字节／哈希用途（本文未实测）	上层如何消费签名字节与哈希	去重键、交易哈希、`userOpHash` 的消费方式

它有判别力的地方在于：同一个 ML-DSA 部署，L2（hint）的检查存在，而 L3（总长）缺失——不分环节就容易笼统得出「这个实现没问题」的结论。

8. 一点收尾

这些案例提醒我：核对数学关系还不够。验证器接受哪些字节、封装是否精确限定长度、应用怎样使用签名和哈希，需要分别检查。一个内部解码器严格，并不保证外层入口同样严格——本文里 ML-DSA 恰好就是这个形状。

关于成本，我想把一个想法记下来，但必须标明它现在只是一个未经标定的记账示意，不是结论。可以把一次链上验证的开销粗略拆成

C=\alpha\cdot\text{XOF}+\beta\cdot\text{mulmod}+\gamma\cdot\text{bytes}+\delta\cdot\text{canonical\_check},

其中：XOF 指可扩展输出函数（SHAKE / Keccak）的吸收与挤出次数，用于把消息或种子拉伸成挑战多项式乃至展开公钥；mulmod 指模乘次数，主要来自 NTT / 逆 NTT 与矩阵-向量乘；bytes 指需要读入、复制、哈希的字节量；canonical_check 指强制编码规范性所需的额外操作，也就是本文反复出现的那几行——范围检查、顺序与填充检查、长度相等断言； $\alpha,\beta,\gamma,\delta$ 是各项换算成 gas 的系数。

必须说明这个式子的局限：各项之间可能重叠， $\delta$ 也不足以用单一系数概括形态各异的检查，而且我没有测量过任何一项检查的增量 gas。 因此本文不主张「格基的规范检查必然昂贵、哈希基趋近于零」，更不主张缺检查是实现者为省 gas 主动取舍的结果——我没有成本数据，也没有关于动机的证据。定长结构同样需要严格校验长度、字段范围与外层封装，不能仅凭签名家族推断解析是否规范。把「这些检查到底值多少 gas」留作一个可测量的后续问题，比现在就下结论诚实。

现有证据能支持的结论只有两条：检查是否存在，要以具体版本和具体入口为准；源码中的修复，需要与实际部署分别核对。