分组密码工作模式攻击讲义 Part 3：Nonce Misuse Resistance 与 Synthetic IV

Note: Vol.2 已经把 AEAD 的认证方程和 nonce-based 边界讲清了。Vol.3 的问题不是再追加两个模式名词，而是继续追问：如果 “nonce never repeats” 这条前提自己坏了，安全定义应该怎样升级，失败模式又该怎样被重新组织。

SIV 与 GCM-SIV 的价值，不在于它们让 misuse 没有代价，而在于它们改变了失败的几何形状。对 GCM 而言，repeated nonce 会直接复用 keystream 和 tag mask，把攻击者送进关于 \(H\) 的代数恢复问题。对 SIV / GCM-SIV 而言，外部 nonce 不再直接选中 keystream，而是先进入一个 synthetic IV 的计算，于是 repeated nonce 不再自动等于 two-time pad。

这一卷真正要区分的，不是“谁更先进”，而是四种完全不同的退化：keystream reuse、tag collapse、equality leakage、deterministic repetition。把这些退化混成一句“nonce misuse 很危险”，反而会掩掉攻击者到底得到了什么。

0. Threat Model 与目标切换

本卷默认读者已经接受 Vol.2 的接口：

$$ \mathcal{E}_K(N, A, P) = (C, T), \qquad \mathcal{D}_K(N, A, C, T)\in\{P,\bot\}. $$

Vol.2 已经说明，这样的 nonce-based AEAD 在 nonce 唯一时可以同时提供：

• confidentiality
• ciphertext integrity
• associated-data binding

但这一类安全定理把一个条件埋得很深：

$$ N_i \neq N_j \qquad \text{for all encryption queries under one key.} $$

这不是一个实现小贴士，而是定义的一部分。Vol.3 的目标就是考察当该条件被破坏时，安全性如何退化。

这里先固定三种不同的失败形态：

1. catastrophic break 攻击者一旦得到 repeated nonce transcript，就能直接把保密性或认证性改写成显式可利用的代数对象。
2. bounded degradation 重复 nonce 仍然导致泄漏，但泄漏被约束成某种可描述对象，例如等值关系。
3. deterministic repetition 对相同输入得到相同输出，这是一种设计允许的泄漏，而不是 misuse 才触发的崩塌。

把这三者分开，是理解 SIV / GCM-SIV 的前提。

1. 从 Vol.2 到 Vol.3：nonce-based AEAD 的边界在哪里结束

Vol.2 中最硬的一章其实是 GCM。因为 repeated nonce 不只是让

$$ C \oplus C' = P \oplus P' $$

成立，而且还让认证项退化成关于

$$ H = E_K(0^{128}) $$

的多项式根问题。这就是典型的 catastrophic break：攻击者不需要恢复 AES key，只需要恢复足以伪造 tag 的中间对象。

如果把这一点抽象掉，Vol.2 真正留下的问题其实是：

有没有一种构造，使外部 nonce 的重复不再直接等于“同一明文异或流”和“同一 tag mask 消元”？

SIV 与 GCM-SIV 的回答都是否定了“外部 nonce 直接驱动 keystream”这个做法。它们先计算一个依赖消息与上下文的 synthetic IV，再用该 IV 驱动流层。

这一步的含义非常大。它不是微调一个 counter format，而是把安全边界从

$$ N \mapsto \text{keystream selector} $$

改成

$$ (N, A, P) \mapsto S \mapsto \text{keystream selector}. $$

于是攻击者若只重复外部 nonce，而不能让 \((A,P)\) 也重复，就不再自动复用内部状态。

2. 从 AEAD 到 DAE：安全定义为什么必须升级

2.1 标准 AEAD 的接口依赖 unique nonce

标准 AEAD 的对象是带 nonce 的随机化加密：

$$ \mathcal{E}_K(N,A,P) = (C,T). $$

在这个接口里，攻击者通常把 \(N\) 当作：

• public value
• unique value
• not necessarily unpredictable value

也就是说，标准 AEAD 接受 nonce can be public，但不接受 nonce can repeat。

因此标准 AEAD 的安全断言本质上是一个条件句：

$$ \text{if nonce discipline holds, then confidentiality and integrity hold.} $$

2.2 deterministic authenticated encryption 的接口

若完全移除外部 nonce，一个自然对象是 deterministic authenticated encryption。它的接口更接近：

$$ \mathcal{E}_K(A,P) = Z, \qquad \mathcal{D}_K(A,Z)\in\{P,\bot\}. $$

这里没有随机化输入，所以对同一 \((A,P)\)：

$$ \mathcal{E}_K(A,P)=\mathcal{E}_K(A,P). $$

这句看起来像废话，但它意味着一个 unavoidable leakage：

$$ (A,P)=(A',P') \Longrightarrow Z=Z'. $$

也就是说，deterministic construction 必然泄漏等值关系。攻击者无法从 deterministic security 中被承诺“相同输入得到不同输出”。

因此 deterministic AE 从来就不是“完美隐藏所有结构”，而是：

在承认 equality leakage 的前提下，继续保持认证与对不等输入的高层隐藏性。

2.3 misuse-resistant AE 的目标

misuse-resistant AE 想实现的是一种中间态：接口看起来仍可接受外部 nonce，但 repeated nonce 不应立即造成 GCM 式灾难。

它真正追求的是：

• 若 \((N,A,P)\) 与 \((N',A',P')\) 完全相同，则允许泄漏相等性。
• 若只重复 nonce，但 \(A\) 或 \(P\) 不同，则不应直接复用 keystream。
• 对新鲜 tuple 的伪造能力仍应被压到可忽略范围。

因此 Vol.3 的核心比较不是“随机 AE vs deterministic AE”，而是：

退化类型	攻击者得到什么
GCM repeated nonce	\(P \oplus P'\) 以及 tag-related algebraic collapse
deterministic repetition	只知道 two transcripts 是否完全相等
misuse-resistant AE under repeated nonce	目标是尽量只退化到上面第二种

2.4 等值泄漏和 two-time pad 泄漏不是一个量级

这点必须单独强调。若攻击者只得到

$$ \mathbf{1}\big[(A,P)=(A',P')\big], $$

它知道的是一位 equality information。若攻击者得到

$$ P \oplus P', $$

它得到的是整条消息差分结构。后者能被已知明文、格式约束、低熵字段、自然语言冗余或 parser 结构继续放大，前者则不能直接还原线性差分。

因此把 SIV 的 equality leakage 和 GCM 的 two-time pad 泄漏放在同一句“都会泄漏信息”里，是严重淡化了失败程度差异。

3. SIV：synthetic IV 如何改变失败模式

3.1 SIV 的最小结构

SIV 的核心接口可以先抽象写成：

$$ S = \operatorname{PRF}_{K_1}(A_1,\ldots,A_d,P), $$$$ C = P \oplus \mathsf{KS}_{K_2}(S), $$

最终输出为

$$ Z = S \,\|\, C. $$

这里 \(A_1,\ldots,A_d\) 是一组 associated data components，plaintext \(P\) 作为最后一个输入进入 PRF。RFC 5297 中的具体 PRF 构造叫做 S2V，使用 CMAC 和 doubling 链实现。

这条方程已经体现了与 Vol.2 的根本差异：

• GCM 中，外部 nonce 直接决定 \(J_0\)
• SIV 中，真正驱动 CTR 流的是 synthetic IV \(S\)

于是 repeated external nonce 不再自动意味着 repeated internal counter origin。

3.2 S2V：为什么 synthetic IV 是一个“消息摘要式”的状态，而不是随机 nonce

RFC 5297 的 S2V 可以抽象成下面的链。设

$$ D_0 = \operatorname{CMAC}_{K_1}(0^{128}). $$

对前 \(d\) 个 associated-data components 递推：

$$ D_i = \operatorname{dbl}(D_{i-1}) \oplus \operatorname{CMAC}_{K_1}(A_i). $$

然后把 plaintext 作为最后一个输入。如果 \(|P| \ge 128\)，则做尾部异或：

$$ S = \operatorname{CMAC}_{K_1}\big(\operatorname{xorend}(P, D_d)\big). $$

若 \(|P| < 128\)，则做一次额外 doubling 再与 padding 后的 \(P\) 异或：

$$ S = \operatorname{CMAC}_{K_1}\big(\operatorname{dbl}(D_d) \oplus \operatorname{pad}(P)\big). $$

所以 \(S\) 不是“外部给的一个 number used once”，而是：

把所有需要认证的对象一起压缩出来的 synthetic state。

这也意味着，只要 \(A\) 或 \(P\) 改变，\(S\) 通常就会改变。

3.3 nonce-based SIV 与 deterministic SIV

SIV 同时支持两种视角：

1. deterministic AE 把 associated data vector 写成 \((A_1,\ldots,A_d)\)，不额外给 nonce。
2. nonce-based misuse-resistant AE 把外部 nonce \(N\) 也作为一个 associated-data component 放进向量。

后一种做法可写成：

$$ S = \operatorname{PRF}_{K_1}(N, A, P). $$

这一步至关重要。外部 nonce 在 SIV 里不是直接用来选中 keystream，而是被吸收到 PRF 输入里。因此：

$$ N=N' \not\Rightarrow S=S'. $$

只有当

$$ (N,A,P)=(N',A',P') $$

时，才会必然有

$$ S=S'. $$

3.4 为什么 repeated external nonce 不等于 repeated keystream

比较一下 GCM 与 SIV：

GCM 中，

$$ N \Longrightarrow J_0 \Longrightarrow \text{counter stream}. $$

SIV 中，

$$ (N,A,P) \Longrightarrow S \Longrightarrow \text{counter stream}. $$

因此 repeated nonce 但不同消息时：

$$ N=N', \quad (A,P)\neq(A',P') $$

在 GCM 下会直接重用 keystream；而在 SIV 下通常导致

$$ S \neq S', $$

所以不会自动出现

$$ C \oplus C' = P \oplus P'. $$

这正是 SIV 把 repeated nonce 的灾难性失败降级掉的机制。

3.5 SIV 仍然会泄漏什么

SIV 并不是零代价方案。它会显式泄漏：

$$ (N,A,P)=(N',A',P') \Longrightarrow Z=Z'. $$

也就是说，攻击者知道两次输入是否完全相同。这就是 equality leakage。

从 deterministic design 角度看，这个泄漏几乎是不可避免的：没有外部随机性，完全相同的输入只能给出完全相同的输出，除非额外引入状态或随机源，而那又会回到 standard AEAD 的世界。

因此 SIV 的代价可以概括成两条：

• equality leakage
• two-pass processing

第二条是工程代价，第一条是安全代价。本卷只关心第一条。

3.6 SIV 没有解决什么

把外部 nonce 变成 associated-data input，并不意味着一切攻击面都消失。SIV 仍然没有自动解决：

• replay
• application-level state confusion
• side-channel visible \(\bot\) 分支
• message equality as a privacy signal

因此更准确的说法不是 “SIV is safe under nonce reuse”，而是：

repeated nonce 不再把系统推入 two-time pad 或 tag-collapse，而只把它推入 deterministic equality leakage 的边界。

4. GCM-SIV：保留 GCM 轮廓下的 bounded degradation

4.1 目标不是“修补 GCM 一个 corner case”

GCM-SIV 的定位非常精确。它不是在 GCM 外面补一个告警，也不是简单把 GCM 的 nonce 换个格式。它要做到三件事：

1. 尽量保留 GCM 类实现与硬件优势。
2. 避免 repeated nonce 直接复用 keystream。
3. 保持输出仍然是 AEAD 风格，而不是回到纯 deterministic wrapping。

RFC 8452 对这一点说得很清楚：其目标是在 nonce 重复时“不发生 catastrophic failure”，而退化到是否相等这一最小信息。

4.2 GCM-SIV 的最小方程组

GCM-SIV encryption 接受：

• key-generating key \(K\)
• 96-bit nonce \(N\)
• associated data \(A\)
• plaintext \(P\)

它先用 \(K\) 与 \(N\) 派生一组 per-nonce keys：

$$ (K_{\mathrm{auth}}, K_{\mathrm{enc}}) = \operatorname{Derive}_K(N). $$

然后定义长度块

$$ L = [|A|]_{64}^{\mathrm{le}} \,\|\, [|P|]_{64}^{\mathrm{le}}, $$

并对 padded associated data 与 padded plaintext 做 POLYVAL：

$$ S_s = POLYVAL_{K_{\mathrm{auth}}}(A^\star \,\|\, P^\star \,\|\, L). $$

接着把 nonce 混入 \(S_s\)，并清掉最后一个字节的最高位，得到一个 pre-tag state：

$$ S' = \operatorname{mix}(S_s, N). $$

最后用 AES 在 \(K_{\mathrm{enc}}\) 下加密 \(S'\) 得到 tag：

$$ T = E_{K_{\mathrm{enc}}}(S'). $$

再把 tag 改成 counter origin，对 plaintext 做 CTR：

$$ C = P \oplus \mathsf{KS}_{K_{\mathrm{enc}}}(\operatorname{ctr}(T)). $$

输出为

$$ Z = C \,\|\, T. $$

这条结构和 GCM 的最重要差异是：

• GCM 认证的是 \(A\) 与 ciphertext \(C\)
• GCM-SIV 认证的是 \(A\) 与 plaintext \(P\)

也就是说，GCM-SIV 先通过认证层生成 synthetic IV/tag，再让该 tag 反过来驱动加密层。

4.3 POLYVAL 与 GHASH：相似，但角色被重新安排了

POLYVAL 与 GHASH 都是 \(GF(2^{128})\) 上的多项式认证器。RFC 8452 甚至明确说明二者可通过 byte order 和域元素变换联系起来。

但在安全边界上，真正关键的不是 “POLYVAL 和 GHASH 都是 polynomial hash”，而是：

• GCM 中，counter origin 先由 nonce 确定，然后再去认证 ciphertext
• GCM-SIV 中，tag 先由 \((N,A,P)\) 的认证计算确定，然后再去驱动 CTR

因此 repeated nonce 时，即使 per-nonce keys 会重复，攻击者也不会仅凭 nonce 相等就得到相同 counter origin。还需要 \((A,P)\) 的认证结果一起相等。

4.4 为什么 repeated nonce 不再直接重用 keystream

GCM-SIV 中的 keystream origin 本质上是

$$ \operatorname{ctr}(T), $$

而 \(T\) 本身来自

$$ T = E_{K_{\mathrm{enc}}}(\operatorname{mix}(POLYVAL_{K_{\mathrm{auth}}}(A^\star \,\|\, P^\star \,\|\, L), N)). $$

所以 repeated nonce 只给出：

$$ N=N' \Longrightarrow (K_{\mathrm{auth}},K_{\mathrm{enc}})=(K'_{\mathrm{auth}},K'_{\mathrm{enc}}). $$

但这并不推出

$$ T=T'. $$

因为还需要

$$ POLYVAL_{K_{\mathrm{auth}}}(A^\star \,\|\, P^\star \,\|\, L) = POLYVAL_{K_{\mathrm{auth}}}(A'^\star \,\|\, P'^\star \,\|\, L'). $$

在正常安全边界下，这通常要求 \((A,P)\) 本身也相同或发生极罕见碰撞。因此 GCM-SIV 避免了 GCM 中那种

$$ N=N' \Longrightarrow \text{same keystream} $$

的直接灾难。

4.5 GCM-SIV 仍然泄漏什么

RFC 8452 对 repeated nonce 的目标非常克制：若同一 nonce 下两条消息重复加密，泄漏的应该主要是它们是否相等。

形式化地说，若

$$ (N,A,P)=(N',A',P'), $$

则必然有

$$ Z=Z'. $$

因此 GCM-SIV 的退化边界并不是“啥也不泄漏”，而是：

$$ \text{same input} \Longrightarrow \text{same output}. $$

这和 SIV 一样，是 deterministic component 不可避免的痕迹；不同的是 GCM-SIV 仍然保留显式的外部 nonce 接口，并尽量贴近 GCM 的性能轮廓。

4.6 为什么未认证明文绝不能提前释放

RFC 8452 对解密流程有一句非常硬的要求：plaintext 在 tag confirmation 完成前 MUST NOT be output。

这不是实现洁癖，而是理论边界的组成部分。原因在于 GCM-SIV 的 decrypt 先会基于 tag 驱动 CTR 还原一个候选明文：

$$ \widetilde{P} = C \oplus \mathsf{KS}_{K_{\mathrm{enc}}}(\operatorname{ctr}(T)). $$

然后再检查该 \(\widetilde{P}\) 与 \(A\) 是否重新生成相同 tag。若系统在这一步确认前就把 \(\widetilde{P}\) 暴露给 parser、日志或上层应用，那么攻击者又重新获得了一个“先解密、后认证”的 side channel 接口。

因此 GCM-SIV 的安全性不只依赖 synthetic IV 结构，也依赖 decrypt semantics 真正保持：

$$ \mathcal{D}_K(N,A,C,T)\in\{P,\bot\}, $$

而不是

$$ \widetilde{P} \to \text{parse} \to \text{later decide whether to reject}. $$

5. 统一比较：GCM、SIV、GCM-SIV 在 misuse 下分别退化成什么

现在把三者放到同一个框架里。

构造	repeated nonce / repeated input 后首先复用的对象	直接退化
GCM	keystream 与 tag mask	\(P \oplus P'\) 与认证崩塌
SIV	synthetic IV 仅在完整输入相等时复用	equality leakage
GCM-SIV	per-nonce keys 可重复，但 counter origin 仍受 \((A,P)\) 约束	bounded equality-style degradation

换一种问法：攻击者究竟能推出什么？

5.1 GCM

若 nonce 重复，攻击者很快得到：

$$ C \oplus C' = P \oplus P' $$

并进一步把 tag 关系压成关于 hash subkey 的多项式约束。它得到的是整条线性差分和认证代数入口。

5.2 SIV

攻击者看到的不是 \(P \oplus P'\)，而是：

$$ Z=Z' \Longleftrightarrow (A,P)=(A',P') $$

或在 nonce-based 用法下

$$ Z=Z' \Longleftrightarrow (N,A,P)=(N',A',P'). $$

这是一种 equality oracle，而不是 linear-difference oracle。

5.3 GCM-SIV

GCM-SIV 的目标与 SIV 类似：repeated nonce 时，攻击者至多获得近似 equality-style 的退化，而不是 GCM 式 catastrophe。与 SIV 相比，它额外保留了显式 nonce 接口和 GCM-like performance profile；与 GCM 相比，它牺牲的是“单遍高效随机化 AE 的简洁性”。

5.4 认证保留与保密退化必须分开看

很多介绍在这里会说“GCM-SIV 更安全”。更准确的说法应该是：

• 在 standard nonce discipline 下，三者都可以给出很强的 AE 边界。
• 在 repeated nonce 下，GCM 会出现 catastrophic confidentiality/integrity failure。
• SIV / GCM-SIV 试图保留认证边界，同时把保密退化限制到等值泄漏级别。

这比“更安全”这种空泛判断更接近攻击者真正关心的问题。

6. 三卷收束：nonce discipline、认证边界、misuse 退化

到这里，这条讲义线的前三卷其实已经形成三层结构：

6.1 Vol.1

Vol.1 讲的是：如果模式根本不认证，那么攻击者总能在解密方程里找到一个可控项。

6.2 Vol.2

Vol.2 讲的是：AEAD 通过 reject 语义和认证方程切断这些主动攻击面，但代价是安全边界严重依赖 unique nonce。

6.3 Vol.3

Vol.3 讲的是：若必须面对 nonce misuse，那么唯一可行的方向不是继续假装 repeated nonce 不会发生，而是把外部 nonce 从“直接选流”改成“先进入 synthetic IV 认证层”，从而把灾难性崩塌降级为 deterministic equality leakage 或其他 bounded degradation。

所以这三卷真正建立起来的，不是一个“模式名词表”，而是三条连续边界：

1. malleability boundary
2. authentication boundary
3. misuse boundary

而这三条边界都还没有碰到 storage encryption 的问题。消息加密里的 misuse-resistant AE 依然不等于 authenticated storage，也不等于 tweakable enciphering。若继续往后走，下一卷自然就该切到：

• tweakable block ciphers
• XTS
• replay / rollback / sector relocation
• storage confidentiality vs authenticated storage

References

• RFC 5116, An Interface and Algorithms for Authenticated Encryption
• RFC 5297, Synthetic Initialization Vector (SIV) Authenticated Encryption Using the Advanced Encryption Standard (AES)
• RFC 8452, AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption
• Phillip Rogaway and Thomas Shrimpton, Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem