土法炼钢兴趣小组的算法知识备份

【密码学百科】对称密码的可证明安全：PRP/PRF 范式与工作模式证明

2026-04-11 · cryptography · #PRF #PRP #switching-lemma #CBC-security #CTR-security #GCM-proof #AEAD-security #Luby-Rackoff #Feistel

目录

在本系列第 50 篇中，我们介绍了可证明安全（Provable Security）的基本方法论：通过精确的安全定义、计算不可区分性和归约论证，将密码方案的安全性建立在可度量的数学基础之上。那篇文章主要从公钥密码学的视角展开讨论，但事实上，对称密码学有着自己同样严格且独立发展的可证明安全体系。

许多人以为对称密码学只是”工程上的经验构造”，缺乏公钥密码学那样的理论深度。这是一种严重的误解。从 Luby 和 Rackoff 在 1988 年证明三轮 Feistel 网络是伪随机置换开始，对称密码的可证明安全理论已经发展了近四十年，形成了一套以伪随机函数（Pseudorandom Function，PRF）和伪随机置换（Pseudorandom Permutation，PRP）为核心原语、以安全性归约为基本方法的完整框架。现代分组密码工作模式（如 CTR、CBC、GCM）的设计，无一不是在这套框架下被严格分析和证明的。

本文将系统地梳理对称密码可证明安全的核心理论。我们从理想密码模型和 PRP 的定义出发，引入 PRF 的概念和 PRP/PRF 切换引理，回顾 Luby-Rackoff 定理这一奠基性结果，然后逐一分析 CTR 模式、CBC 模式和 GCM 模式的安全性证明思路，讨论 Encrypt-then-MAC 的 CCA 安全性，最后给出 AEAD 安全性定义的现代视角和对称密码安全性的前沿边界。

一、理想密码模型与 PRP

分组密码的抽象：从 AES 到理想置换

一个分组密码（Block Cipher）是一族以密钥 K 索引的置换。形式化地，对于密钥空间 K 和消息空间 {0,1}^n，分组密码 E: K × {0,1}^n → {0,1}^n 满足：对于每个固定的密钥 k ∈ K，映射 E(k, ·) 是 {0,1}^n 上的一个置换（即双射），其逆映射记为 D(k, ·)。例如，AES-128 的密钥空间是 {0,1}^128，消息空间是 {0,1}^128，它定义了 2^128 个不同的置换。

然而，AES 定义的 2^128 个置换只是 {0,1}^128 上全部 (2^128)! 个置换中极其微小的一个子集。这引出了一个根本性问题：如果 AES 定义的置换族在”某种意义上”与”随机选取的置换”不可区分，那么我们就可以用随机置换来作为 AES 安全性分析的理想化替代品——这正是可证明安全的核心思路。

伪随机置换的形式化定义

设 Perm(n) 表示 {0,1}^n 上所有置换的集合。一个分组密码 E: K × {0,1}^n → {0,1}^n 是一个伪随机置换（Pseudorandom Permutation，PRP），如果任何计算资源有界的区分者（Distinguisher）D 都无法有效地区分以下两种情况：

区分者 D 可以对预言机进行至多 q 次自适应查询（Adaptive Query），每次查询一个 n 比特的输入并获得 n 比特的输出，最终输出一个比特 b ∈ {0,1}，表示他认为自己在哪个世界中。D 的 PRP 优势（PRP Advantage）定义为：

Adv_E^prp(D) = |Pr[D^{E(k,·)} = 1] - Pr[D^{π(·)} = 1]|

如果对于所有计算资源有界的区分者 D，这个优势都是可忽略的（Negligible），则称 E 是一个安全的 PRP。

强伪随机置换

上述定义中，区分者只能进行正向查询（给定输入，获得输出）。如果我们进一步允许区分者进行反向查询（给定输出，获得输入），则得到强伪随机置换（Strong Pseudorandom Permutation，SPRP）的定义。形式化地，SPRP 要求区分者同时拥有 E(k, ·) 和 D(k, ·)（或 π(·) 和 π^{-1}(·)）的访问权限时，仍然无法区分真实世界和理想世界。

SPRP 是比 PRP 更强的安全概念。在分析需要解密操作的密码方案（如 CCA 安全的加密模式）时，SPRP 假设是必要的。

理想密码模型

理想密码模型（Ideal Cipher Model，ICM）更进一步，假设分组密码 E 本身就是一个从所有可能的密钥化置换族中均匀随机选取的元素。换言之，对于每个密钥 k，E(k, ·) 是一个独立的随机置换。理想密码模型类似于随机预言机模型（Random Oracle Model）在哈希函数中的地位——它是一种理想化假设，在实际中用具体的分组密码（如 AES）来实例化。在理想密码模型下进行的安全性证明被称为”信息论安全”（Information-Theoretic Security），因为它对区分者的计算能力没有限制，安全性仅依赖于查询次数的有界性。

二、伪随机函数

PRF 的定义

与 PRP 关注置换不同，伪随机函数（Pseudorandom Function，PRF）关注的是一般的函数。设 Func(m, n) 表示从 {0,1}^m 到 {0,1}^n 的所有函数的集合。一个带密钥的函数族 F: K × {0,1}^m → {0,1}^n 是一个伪随机函数，如果任何计算资源有界的区分者 D 都无法有效地区分以下两种情况：

PRF 优势的定义与 PRP 类似：

Adv_F^prf(D) = |Pr[D^{F(k,·)} = 1] - Pr[D^{f(·)} = 1]|

PRF 与 PRP 的关系

PRP 和 PRF 之间有一个微妙但重要的差异：PRP 要求输出是置换（双射），而 PRF 没有这个约束。一个随机置换和一个随机函数之间的区别在于：置换不会产生碰撞（两个不同的输入不会映射到相同的输出），而随机函数会。

这个差异在查询次数较少时几乎不可察觉，但当查询次数接近生日界（Birthday Bound）时变得显著。直觉上，如果区分者进行了 q 次查询，观察到没有碰撞，那么他可以据此推断自己更可能在与置换交互而非与随机函数交互——因为随机函数在 q 次查询中产生碰撞的概率约为 q^2 / 2^{n+1}。

PRP/PRF 切换引理

PRP/PRF 切换引理（PRP/PRF Switching Lemma）精确量化了上述差异。这一引理的陈述非常优美：

对于任何区分者 D，如果他最多进行 q 次查询，且底层的置换/函数作用在 {0,1}^n 上，则：

|Adv^prf(D) - Adv^prp(D)| ≤ q(q-1) / 2^{n+1}

换言之，PRF 优势和 PRP 优势之间的差异被一个生日界项 q^2 / 2^{n+1} 所上界。当 q 远小于 2^{n/2} 时，这个差异可以忽略不计。

这一引理的实用意义是巨大的。在安全性证明中，我们经常需要将分组密码视为 PRF 来使用（因为许多工作模式的安全性归约更自然地以 PRF 为起点），但实际上分组密码是 PRP。PRP/PRF 切换引理告诉我们，只要查询次数不超过生日界，这种替换只引入一个可控的额外安全性损失。

对于 AES-128（n = 128），生日界约为 2^64 次查询。这意味着在同一密钥下加密不超过约 2^64 个分组时，将 AES 视为 PRF 是安全的。但对于 64 比特分组的旧密码（如 3DES，n = 64），生日界仅为 2^32 次查询（约 32 GB 数据），这正是 Sweet32 攻击得以成功的根本原因。

PRF/PRP 区分游戏的 Python 模拟

下面的 Python 代码实现了一个 PRF/PRP 区分游戏的模拟，帮助读者直观地理解区分者如何利用碰撞来区分 PRF 和 PRP：

"""
PRF/PRP 区分游戏模拟
演示区分者如何通过检测碰撞来区分伪随机函数和伪随机置换
"""

import os
import hashlib
import struct
from typing import Callable


def random_function(domain_bits: int, range_bits: int) -> Callable:
    """构造一个真正的随机函数（惰性求值）"""
    table: dict[int, int] = {}
    mask = (1 << range_bits) - 1

    def evaluate(x: int) -> int:
        if x not in table:
            table[x] = int.from_bytes(os.urandom(range_bits // 8), "big") & mask
        return table[x]

    return evaluate


def random_permutation(n_bits: int) -> callable:
    """构造一个真正的随机置换（惰性求值，拒绝采样）"""
    forward: dict[int, int] = {}
    used_outputs: set[int] = set()
    mask = (1 << n_bits) - 1

    def evaluate(x: int) -> int:
        if x not in forward:
            while True:
                y = int.from_bytes(os.urandom(n_bits // 8), "big") & mask
                if y not in used_outputs:
                    break
            forward[x] = y
            used_outputs.add(y)
        return forward[x]

    return evaluate


def keyed_prf(key: bytes, n_bits: int) -> callable:
    """用 HMAC-SHA256 截断构造带密钥的 PRF"""
    mask = (1 << n_bits) - 1

    def evaluate(x: int) -> int:
        data = struct.pack(">Q", x)
        h = hashlib.sha256(key + data).digest()
        return int.from_bytes(h[: n_bits // 8], "big") & mask

    return evaluate


def collision_distinguisher(oracle: callable, q: int, n_bits: int) -> int:
    """
    基于碰撞的区分者：
    查询 oracle q 次，若发现输出碰撞则猜测"随机函数"（返回 1），
    否则猜测"随机置换"（返回 0）。

    原理：随机函数允许碰撞，随机置换不允许。
    """
    outputs = []
    for i in range(q):
        y = oracle(i)
        outputs.append(y)

    # 检查是否存在输出碰撞
    if len(outputs) != len(set(outputs)):
        return 1  # 猜测：随机函数（PRF 世界）
    else:
        return 0  # 猜测：随机置换（PRP 世界）


def run_experiment(n_bits: int = 16, q: int = 300, trials: int = 2000):
    """
    运行 PRF/PRP 区分实验。
    n_bits=16 意味着值域大小为 2^16 = 65536，
    生日界约为 sqrt(65536) = 256。
    当 q > 256 时，区分者应有明显优势。
    """
    prf_accepts = 0  # 区分者在 PRF 世界中输出 1 的次数
    prp_accepts = 0  # 区分者在 PRP 世界中输出 1 的次数

    for _ in range(trials):
        # PRF 世界
        f = random_function(64, n_bits)
        prf_accepts += collision_distinguisher(f, q, n_bits)

        # PRP 世界
        pi = random_permutation(n_bits)
        prp_accepts += collision_distinguisher(pi, q, n_bits)

    prf_rate = prf_accepts / trials
    prp_rate = prp_accepts / trials
    advantage = abs(prf_rate - prp_rate)

    print(f"参数: n={n_bits} bits, q={q} queries, {trials} trials")
    print(f"  PRF 世界中区分者输出 1 的比例: {prf_rate:.4f}")
    print(f"  PRP 世界中区分者输出 1 的比例: {prp_rate:.4f}")
    print(f"  区分优势 (实测): {advantage:.4f}")

    # 理论生日碰撞概率（PRF 世界）
    birthday_prob = 1.0
    N = 1 << n_bits
    for i in range(q):
        birthday_prob *= (N - i) / N
    birthday_prob = 1.0 - birthday_prob
    switching_bound = q * (q - 1) / (2 * N)
    print(f"  碰撞概率 (理论): {birthday_prob:.4f}")
    print(f"  PRP/PRF 切换引理上界: {switching_bound:.4f}")
    print()


if __name__ == "__main__":
    print("=== PRF/PRP 区分游戏模拟 ===\n")

    # 实验 1：q 远小于生日界，区分者几乎没有优势
    run_experiment(n_bits=16, q=50, trials=2000)

    # 实验 2：q 接近生日界，区分者开始获得优势
    run_experiment(n_bits=16, q=256, trials=2000)

    # 实验 3：q 超过生日界，区分者有显著优势
    run_experiment(n_bits=16, q=400, trials=2000)

这段代码中，random_function 和 random_permutation 分别实现了真随机函数和真随机置换的惰性求值。区分者 collision_distinguisher 采用最简单的策略：查询预言机 q 次，如果发现输出碰撞则猜测自己在 PRF 世界中，否则猜测在 PRP 世界中。当 q 远小于 2^{n/2}（生日界）时，PRF 世界也很少出现碰撞，区分者的优势接近零；当 q 接近或超过生日界时，PRF 世界中碰撞频繁出现而 PRP 世界中永远不会出现碰撞，区分者的优势变得显著。运行结果会清晰地展示 PRP/PRF 切换引理所预测的生日界行为。

三、Luby-Rackoff 定理

从 PRF 到 PRP：Feistel 构造

前面我们定义了 PRF 和 PRP 两个核心概念，并通过切换引理建立了二者之间的定量关系。一个自然的问题是：能否从 PRF 构造 PRP？换言之，如果我们拥有一个安全的伪随机函数，能否用它来构建一个安全的伪随机置换？

这个问题的重要性在于：PRF 在概念上比 PRP 更基础（任何 PRP 在生日界内都是 PRF，但反之不然），而且 PRF 的构造通常比 PRP 更简单。如果我们能从 PRF 构造 PRP，就建立了一种”以简驭繁”的理论路径。

Luby 和 Rackoff 在 1988 年的开创性工作给出了肯定的回答。他们证明了 Feistel 网络（Feistel Network）——这一在 DES 设计中被广泛使用的结构——可以将 PRF 转化为 PRP。

Feistel 网络的结构

Feistel 网络的基本思想是：将 2n 比特的输入分为左右两半各 n 比特，记为 (L_0, R_0)，然后通过多轮迭代来构造一个 2n 比特上的置换。每一轮的操作如下：

L_i = R_{i-1}
R_i = L_{i-1} ⊕ f_i(R_{i-1})

其中 f_i 是第 i 轮使用的轮函数（Round Function）。关键观察是：无论 f_i 是什么函数（甚至不需要是可逆的），上述变换都是可逆的——给定 (L_i, R_i)，可以恢复 (L_{i-1}, R_{i-1})：

R_{i-1} = L_i
L_{i-1} = R_i ⊕ f_i(L_i)

这种”不可逆函数构造可逆置换”的特性是 Feistel 网络最优美的性质。

三轮 Feistel 是 PRP

Luby-Rackoff 定理的核心结论是：如果 f_1, f_2, f_3 是三个独立的伪随机函数（从 {0,1}^n 到 {0,1}^n），那么三轮 Feistel 网络 Ψ(f_1, f_2, f_3) 是一个从 {0,1}^{2n} 到 {0,1}^{2n} 的伪随机置换。

更精确地，对于任何进行至多 q 次查询的区分者 D：

Adv_Ψ^prp(D) ≤ 3 · Adv_f^prf(D’) + O(q^2 / 2^n)

其中 D’ 是从 D 构造出的针对 PRF f 的区分者。这个归约告诉我们：如果底层的 PRF 是安全的，且查询次数 q 远小于 2^{n/2}，则三轮 Feistel 构造是一个安全的 PRP。

证明思路

Luby-Rackoff 定理的证明采用混合论证（Hybrid Argument）。首先，利用 PRF 的安全性，将三个伪随机函数 f_1, f_2, f_3 逐一替换为真随机函数 g_1, g_2, g_3，每一步的安全性损失为 Adv^prf。然后，证明使用三个独立真随机函数的 Feistel 网络 Ψ(g_1, g_2, g_3) 与真随机置换 π 之间的区别是信息论意义上可忽略的（上界为 O(q^2 / 2^n)）。

第二步是证明的技术核心。直觉上，三轮 Feistel 的安全性来源于以下观察：在真随机函数的设定下，第一轮的作用是”随机化”右半部分，第二轮在这个随机化的基础上”随机化”左半部分，第三轮则消除了前两轮可能留下的结构性痕迹。两轮不够的原因是：对于两轮 Feistel，存在一种区分攻击——区分者可以构造两个特定的查询，使得输出的某些位之间存在可检测的线性关系。

四轮 Feistel 是 SPRP

Luby 和 Rackoff 进一步证明了：如果使用四个独立的伪随机函数，则四轮 Feistel 网络是一个强伪随机置换（SPRP）——即使区分者同时拥有正向和反向查询的能力，也无法区分。

Adv_Ψ^sprp(D) ≤ 4 · Adv_f^prf(D’) + O(q^2 / 2^n)

这个结果在理论上解释了为什么 DES 和许多基于 Feistel 结构的密码使用了远超三轮或四轮的迭代——额外的轮次提供了更大的安全余量（Security Margin），以抵御不在 PRF 安全性中被捕获的结构性攻击（如差分分析和线性分析）。

后续发展

Luby-Rackoff 定理的影响深远。后续工作中，Patarin 使用 H-coefficient 技术（系数 H 技术）给出了更紧致的安全性界，Maurer 和 Pietrzak 使用不可区分性框架给出了更模块化的证明，而 Hoang 和 Rogaway 则将结果推广到了密钥交替密码（Key-Alternating Cipher）等更广泛的结构。

四、CTR 模式的 IND-CPA 证明

CTR 模式回顾

计数器模式（Counter Mode，CTR）是最简单也最优雅的分组密码工作模式之一。给定一个分组密码 E: K × {0,1}^n → {0,1}^n、一个 nonce N 和一个明文 P = P_1 || P_2 || … || P_l（每个 P_i 为 n 比特），CTR 模式的加密过程为：

C_i = P_i ⊕ E(k, N || ctr_i)    对于 i = 1, 2, ..., l

其中 ctr_i 是一个递增的计数器值。密文为 C = C_1 || C_2 || … || C_l。

CTR 模式的核心特性是：它将分组密码当作 PRF 使用（而非 PRP）。每个分组的加密只需要一次分组密码的正向调用，解密操作与加密完全相同，且不同分组可以并行处理。

安全性定理

定理：如果 E 是一个安全的 PRF，则 CTR 模式在 IND-CPA（选择明文攻击下的不可区分性）安全概念下是安全的。具体地，对于任何 IND-CPA 攻击者 A，存在一个 PRF 区分者 B，使得：

Adv_{CTR[E]}^{ind-cpa}(A) ≤ 2 · Adv_E^prf(B) + σ^2 / 2^n

其中 σ 是攻击者所有查询中涉及的分组密码调用的总次数。

证明思路

证明分为两步：

第一步：用真随机函数替换 PRF。 利用 E 的 PRF 安全性，将 E(k, ·) 替换为一个真随机函数 f(·)。这一步的安全性损失恰好是 Adv_E^prf(B)。替换后，CTR 模式的密文变为 C_i = P_i ⊕ f(N || ctr_i)，其中 f 是真随机函数。

第二步：证明使用真随机函数的 CTR 模式是安全的。 这一步是信息论证明。关键观察是：只要所有加密查询中使用的计数器输入 N || ctr_i 两两不同，真随机函数的输出 f(N || ctr_i) 就是独立均匀随机的比特串——因为真随机函数对不同输入的输出是独立的。用这些独立均匀随机的比特串来异或明文，得到的密文就是均匀随机的，与明文无关——这正是 IND-CPA 安全性所要求的。

计数器输入两两不同的条件在什么情况下会被违反？有两种情况：（1）同一消息内的不同分组使用不同的计数器值，所以不会碰撞；（2）不同消息之间，如果 nonce 不同，则计数器输入自然不同。因此，nonce 的唯一性是 CTR 模式安全性的根本保障。如果 nonce 重复，两条不同消息的密钥流相同，攻击者可以通过异或两条密文来直接获得两条明文的异或——这是灾难性的安全失败。

Nonce 碰撞的生日界

在某些实现中，nonce 不是由计数器生成的，而是随机选取的。如果 nonce 的长度为 r 比特，则在加密 q 条消息后，发生 nonce 碰撞的概率约为 q^2 / 2^{r+1}。对于 AES-GCM 中常用的 96 比特 nonce，这意味着在同一密钥下加密约 2^48 条消息后，nonce 碰撞的概率就达到了不可忽略的水平。这一生日界限制是 nonce-based AEAD 方案的固有约束。

如果使用 PRF 的安全性加上 PRP/PRF 切换引理来分析（因为实际使用的是分组密码而非 PRF），总的安全性界变为：

Adv_{CTR[E]}^{ind-cpa}(A) ≤ 2 · Adv_E^prp(B) + σ^2 / 2^n + σ(σ-1) / 2^{n+1}

后两项都是生日界项，在 σ 远小于 2^{n/2} 时可以忽略。

五、CBC 模式的安全性分析

CBC 模式回顾

密码分组链接模式（Cipher Block Chaining，CBC）是历史上使用最广泛的工作模式。给定初始化向量 IV 和明文 P = P_1 || P_2 || … || P_l，CBC 模式的加密过程为：

C_0 = IV
C_i = E(k, P_i ⊕ C_{i-1})    对于 i = 1, 2, ..., l

CBC 模式的安全性分析比 CTR 模式复杂得多，因为密文分组之间存在链式依赖关系——每个分组的加密输入依赖于前一个分组的密文输出。

IND-CPA 安全性证明

定理（Bellare, Desai, Jokipii, Rogaway, 1997）：如果 E 是一个安全的 PRP，且 IV 是均匀随机选取的，则 CBC 模式在 IND-CPA 安全概念下是安全的。具体地：

Adv_{CBC[E]}^{ind-cpa}(A) ≤ 2 · Adv_E^prp(B) + σ^2 / 2^n

其中 σ 是所有查询中涉及的分组密码调用的总次数。

注意这里直接使用了 PRP 假设，而非 PRF 假设。原因是 CBC 模式将分组密码的输出直接作为密文（而非作为密钥流），因此分组密码的置换特性（无碰撞）在分析中起到了关键作用。

证明思路

证明的核心步骤如下：首先将 E(k, ·) 替换为真随机置换 π，然后证明使用真随机置换的 CBC 模式的安全性。

在真随机置换的设定下，关键观察是：只要所有分组密码调用的输入 X_i = P_i ⊕ C_{i-1} 两两不同，则 π(X_i) 的输出（即密文分组）就是均匀随机且与明文无关的。现在问题变为：这些输入两两不同的概率是多少？

这里出现了一个与 CTR 模式的根本区别：在 CTR 模式中，分组密码的输入是确定性的（nonce 加计数器），因此只要 nonce 唯一就不会碰撞。但在 CBC 模式中，分组密码的输入 X_i = P_i ⊕ C_{i-1} 取决于前一个密文分组 C_{i-1}，而 C_{i-1} 是通过随机置换产生的随机值——因此，X_i 本身也是随机的，不同 X_i 之间可能发生碰撞。通过生日界分析，σ 次调用中发生碰撞的概率约为 σ^2 / 2^{n+1}。

这一分析揭示了 CBC 模式的一个固有弱点：其安全性严格受限于生日界 2^{n/2}。对于 128 比特分组的 AES-CBC，这意味着在同一密钥下加密约 2^64 个分组（约 2^68 字节，即 256 EB）后安全性开始降低。但对于 64 比特分组的 3DES-CBC，生日界仅为 2^32 个分组（约 32 GB）。

Sweet32 攻击

2016 年，Bhargavan 和 Leurent 提出了 Sweet32 攻击，成功地将 CBC 模式的生日界弱点从理论转化为实际攻击。他们证明，对于使用 64 比特分组密码（如 3DES 或 Blowfish）的 CBC 模式，攻击者可以在收集约 2^32 个密文分组后检测到碰撞，从而恢复明文信息。

攻击原理如下：如果两个密文分组 C_i = C_j（即发生碰撞），则必有 P_i ⊕ C_{i-1} = P_j ⊕ C_{j-1}（因为置换是双射），从而 P_i ⊕ P_j = C_{i-1} ⊕ C_{j-1}。攻击者知道所有密文分组，因此可以直接计算 C_{i-1} ⊕ C_{j-1}，进而得到两个明文分组的异或 P_i ⊕ P_j。如果攻击者知道其中一个明文（或明文有可预测的结构），就可以恢复另一个。

Sweet32 攻击的实际影响导致了 TLS 中 3DES 套件的弃用，也是推动密码学社区从 64 比特分组密码全面转向 128 比特分组密码的关键催化剂。

六、Encrypt-then-MAC 的 CCA 安全性

通用组合问题

在 AEAD 成为标准原语之前，实践中常将独立的加密方案和 MAC 方案组合使用来同时提供机密性和完整性。Bellare 和 Namprempre 在 2000 年系统地分析了三种通用组合（Generic Composition）方式的安全性。

三种组合方式

Encrypt-and-MAC（E&M）：对明文 P 同时加密和计算 MAC：C = Enc(K_1, P)，T = MAC(K_2, P)，输出 (C, T)。这种方式被 SSH 协议采用。其问题在于 MAC 标签 T 是对明文计算的，而 MAC 不保证保密性（MAC 的安全定义只要求不可伪造性），因此 T 可能泄露关于 P 的信息，破坏机密性。

MAC-then-Encrypt（MtE）：先计算 MAC，再将明文和 MAC 一起加密：T = MAC(K_2, P)，C = Enc(K_1, P || T)，输出 C。这种方式被 TLS（1.0 至 1.2 的 CBC 套件）采用。其问题在于接收方必须先解密才能验证 MAC，解密过程中可能产生侧信道信息（如 padding oracle），使得安全性证明无法顺利进行。Krawczyk 在 2001 年证明了 MtE 在某些条件下是安全的，但条件较为苛刻。

Encrypt-then-MAC（EtM）：先加密，再对密文计算 MAC：C = Enc(K_1, P)，T = MAC(K_2, C)，输出 (C, T)。这种方式被 IPsec 采用。

EtM 的安全性定理

定理（Bellare-Namprempre, 2000）：如果 Enc 是 IND-CPA 安全的加密方案，MAC 是强不可伪造的（Strongly Unforgeable）消息认证码，且 K_1 和 K_2 是独立的密钥，则 Encrypt-then-MAC 组合是 IND-CCA 安全的。

证明的关键洞察是：在 EtM 中，解密时首先验证 MAC。由于 MAC 是强不可伪造的，攻击者无法伪造一个新的有效 (C, T) 对。因此，攻击者对解密预言机的任何查询（除了提交自己从加密预言机获得的密文之外）都会被 MAC 验证拒绝，返回 ⊥。这意味着解密预言机对攻击者实际上是”无用的”，IND-CCA 游戏退化为 IND-CPA 游戏。

形式化地，安全性界为：

Adv_{EtM}^{ind-cca}(A) ≤ Adv_{Enc}^{ind-cpa}(B_1) + Adv_{MAC}^{suf}(B_2)

其中 B_1 是针对 Enc 的 IND-CPA 攻击者，B_2 是针对 MAC 的伪造攻击者，suf 表示强不可伪造性（Strong Unforgeability）。

为什么 EtM 优于其他组合

EtM 的优越性来源于一个结构性的原因：MAC 标签保护的是密文而非明文。这有两个重要后果：

第一，接收方在解密之前就可以验证密文的完整性。如果 MAC 验证失败，接收方直接拒绝，永远不会触碰加密方案的解密操作。这从根本上消除了 padding oracle 等解密侧信道攻击的可能性。

第二，MAC 的安全性定义不要求保密性，因此 MAC 标签可以泄露关于其输入的信息。在 EtM 中，MAC 的输入是密文（而非明文），密文本身已经受到加密方案的保护，因此即使 MAC 标签泄露了关于密文的信息，也不影响明文的机密性。

七、GCM 的安全性证明

GCM 的构造回顾

Galois/Counter Mode（GCM）是当今最广泛部署的 AEAD 方案。它由两个组件构成：CTR 模式提供加密，GHASH 提供认证。具体而言，GCM 的加密过程可以概括为：

  1. 使用 CTR 模式加密明文，得到密文 C。
  2. 使用 GHASH 对关联数据 A 和密文 C 计算一个认证标签的中间值。
  3. 将 GHASH 的输出与一个额外的密钥流分组 E(K, N || 0^{31} || 1) 异或，得到最终的认证标签 T。

GHASH 是一个基于有限域 GF(2^128) 上多项式求值的通用哈希函数（Universal Hash Function）。其哈希密钥 H = E(K, 0^{128}) 是通过加密全零分组得到的。对于输入序列 X_1, X_2, …, X_m，GHASH 计算：

GHASH_H(X_1, ..., X_m) = X_1 · H^m ⊕ X_2 · H^{m-1} ⊕ ... ⊕ X_m · H

其中乘法在 GF(2^128) 中进行。

安全性定理

定理（McGrew-Viega, 2004；Iwata-Ohashi-Minematsu, 2012 改进）：GCM 的安全性界为：

Adv_{GCM}^{ae}(A) ≤ Adv_E^prp(B) + (σ + q + 1)^2 / 2^{128} + q · l_max / 2^{128} + 1/2^τ

其中 q 是查询次数，σ 是总分组数，l_max 是单条消息的最大分组数，τ 是认证标签的比特长度。

证明思路

GCM 的安全性证明可以分为两个独立的部分：

机密性部分：GCM 的加密本质上就是 CTR 模式，因此机密性归约到底层分组密码的 PRF/PRP 安全性。这部分的分析与第四节完全一致。

完整性部分：这部分归约到 GHASH 的差分概率（Differential Probability）上界。具体地，我们需要证明攻击者无法伪造一个新的有效 (N, A, C, T) 元组。

GHASH 是一个 ε-almost-XOR-universal（ε-AXU）哈希函数，其中 ε = l_max / 2^{128}。这意味着对于任何两个不同的输入 (A, C) 和 (A’, C’)，以及任何目标差值 δ：

Pr_H[GHASH_H(A, C) ⊕ GHASH_H(A', C') = δ] ≤ l_max / 2^{128}

这个上界来自于一个代数事实：GHASH_H(A, C) ⊕ GHASH_H(A’, C’) = δ 等价于一个关于 H 的非零多项式方程，该多项式的次数至多为 l_max，因此在 GF(2^128) 中至多有 l_max 个根。由于 H 是均匀随机的（在用真随机置换替换 E 之后），碰撞概率至多为 l_max / 2^{128}。

攻击者的伪造尝试可以被归约为：在不知道 H 的情况下，找到一个新的 (A’, C’) 使得 GHASH_H(A’, C’) ⊕ E(K, N || 0^{31} || 1) 等于某个特定值。由于 E(K, N || 0^{31} || 1) 对攻击者来说是未知的随机值（假设 nonce 不重复），每次伪造尝试的成功概率至多为 l_max / 2^{128}。

Nonce 重用的灾难

GCM 的安全性证明中，nonce 唯一性假设是至关重要的。如果 nonce 被重用，灾难性的后果包括：

机密性完全丧失：与 CTR 模式相同，相同的 nonce 产生相同的密钥流，两条密文的异或暴露两条明文的异或。

认证密钥泄露：更严重的是，如果攻击者知道两条使用相同 nonce 加密的明文中的一条，他可以恢复 GHASH 密钥 H。原因是：给定明文和密文，攻击者可以计算 GHASH 的输入和输出，从而将问题转化为一个关于 H 的多项式方程的求解问题——而在 GF(2^128) 中求解多项式方程是高效的。一旦 H 泄露，攻击者可以对该密钥下的所有后续消息进行伪造。

这一灾难性的脆弱性是 GCM 最受批评的特性，也是推动 nonce-misuse resistant 方案（如 GCM-SIV）研发的直接动因。

八、AEAD 安全性定义

基于 Nonce 的 AEAD（nAEAD）

现代密码学中，AEAD 的安全性定义已经高度标准化。一个基于 nonce 的 AEAD 方案 Π = (Enc, Dec) 的安全性通过一个单一的”全有或全无”（All-in-One）安全游戏来定义，该游戏同时捕获机密性和完整性。

游戏中，攻击者 A 可以访问两个预言机：加密预言机和解密预言机。在真实世界中，加密预言机执行真正的加密操作，解密预言机执行真正的解密操作。在理想世界中，加密预言机返回随机比特串（长度与真实密文相同），解密预言机总是返回 ⊥。攻击者的目标是区分这两个世界。

形式化地，AEAD 优势定义为：

Adv_Π^{aead}(A) = |Pr[A^{Enc(K,·,·,·), Dec(K,·,·,·)} = 1] - Pr[A^{$(·,·,·), ⊥(·,·,·)} = 1]|

其中 $(·,·,·) 是返回随机比特串的预言机，⊥(·,·,·) 是总返回拒绝的预言机。这个定义将 IND-CPA（机密性）和 INT-CTXT（完整性）统一为一个优势度量。

抗 Nonce 误用的 AEAD（Misuse-Resistant AEAD）

标准的 nAEAD 定义假设 nonce 绝不重复。但在实际系统中，nonce 管理错误时有发生（例如虚拟机克隆导致随机数生成器状态重复、分布式系统中的协调失败等）。抗 nonce 误用的 AEAD（Misuse-Resistant AEAD，简称 MRAE）提供了更强的安全保障。

MRAE 的安全性定义修改了攻击者的能力：允许攻击者在加密查询中重复使用 nonce。在这种设定下，方案需要满足：

这种”优雅降级”（Graceful Degradation）的安全性由 Rogaway 和 Shrimpton 在 2006 年形式化为 SIV（Synthetic IV）范式。GCM-SIV 和 AES-GCM-SIV 是这一范式的代表性实例化方案，它们通过先使用 PRF 从 (N, A, P) 派生出一个合成 IV，再用这个 IV 作为 CTR 模式的 nonce 来加密，从而在 nonce 重复时仍保持安全。

提交式 AEAD（Committing AEAD）

近年来，密码学界意识到标准的 AEAD 安全性定义遗漏了一个重要的安全属性：密钥提交性（Key Commitment）。标准定义不要求 AEAD 方案对密钥具有绑定性——即同一密文可能在不同密钥下解密为不同的有效明文。

这种特性导致了密钥多义性攻击（Key-Commitment Attack）：攻击者可以构造一个密文 (C, T)，使得在密钥 K_1 下解密为明文 P_1，在密钥 K_2 下解密为完全不同的明文 P_2。这种攻击在许多实际场景中具有安全影响，例如在加密文件共享系统中，恶意用户可以上传一个密文，使得不同的接收者（使用不同的密钥）看到不同的内容。

提交式 AEAD（Committing AEAD）要求方案具有密钥提交性：不存在两个不同的密钥使得同一密文都能通过验证。形式化地，要求对于任何高效的攻击者 A：

Pr[A 输出 (K_1, K_2, N, A, C, T) 使得 K_1 ≠ K_2 且 Dec(K_1, N, A, C, T) ≠ ⊥ 且 Dec(K_2, N, A, C, T) ≠ ⊥] ≤ negl

AES-GCM 本身不具备密钥提交性。构造提交式 AEAD 的方法包括在标签计算中引入密钥的哈希值，或使用专门设计的方案如 AEGIS 等。这是 AEAD 安全性定义演进中的一个活跃研究方向。

九、对称密码安全性的边界

多密钥安全性

前面的分析都是在单密钥设定（Single-Key Setting）下进行的：攻击者针对一个固定的密钥进行攻击。但在实际系统中（如 TLS 服务器同时与数百万客户端通信），攻击者面对的是大量不同的密钥。

多密钥安全性（Multi-Key Security）考虑以下场景：系统中有 u 个用户，每人使用独立的密钥 K_1, …, K_u。攻击者的目标是攻破其中任意一个用户的安全性。通过简单的混合论证，多密钥安全性的退化为：

Adv^{multi-key} ≤ u · Adv^{single-key}

这意味着安全性界乘以用户数 u。对于 u = 2^40（约一万亿个密钥），安全性损失为 40 比特。这一退化在实践中可能是显著的，特别是当底层方案的安全余量较小时。

一些方案在多密钥设定下有更好的安全性。例如，如果分组密码在理想密码模型下分析，则多密钥安全性不会退化——因为每个密钥定义了一个独立的随机置换，攻击者对一个密钥的查询不会帮助他攻击另一个密钥。

超越生日界的构造

我们已经多次看到，对称密码方案的安全性界通常包含一个生日界项 σ^2 / 2^n。对于 128 比特分组密码，这给出了约 2^64 个分组的安全性上限。虽然这在大多数实际场景中已经足够，但在某些高吞吐量或长寿命密钥的应用中，这个限制可能成为瓶颈。

超越生日界（Beyond Birthday Bound，BBB）构造旨在将安全性界提高到 2^{2n/3} 甚至更高。代表性方案包括：

宽分组密码

另一种克服生日界的思路是直接使用更大分组的密码——即宽分组密码（Wide Block Cipher）。宽分组密码作用于远大于 128 比特的分组上，从而将生日界推到一个实际上不可达到的水平。

代表性构造包括：

理论边界与开放问题

对称密码可证明安全理论中仍有许多重要的开放问题。例如：

紧致归约问题：许多安全性证明中的归约是”松弛的”（Loose）——安全性界比直觉上应有的水平差了若干个数量级。寻找紧致归约（Tight Reduction）是一个重要的理论目标。例如，CTR 模式的多用户安全性归约是否可以做到紧致？

标准模型下的安全性：理想密码模型和随机预言机模型都是理想化假设。在标准模型（Standard Model）下——即仅假设底层原语（如 PRF）的安全性——对称密码方案的安全性证明往往更弱或更复杂。缩小标准模型与理想模型之间的差距是长期的研究方向。

量子安全性：在量子计算模型下，区分者可以对预言机进行量子叠加查询（Superposition Query）。Zhandry 和 Boneh 等人已经开始研究量子安全的 PRF/PRP 定义及其安全性证明，但这一领域仍处于早期阶段。

组合安全性：在复杂系统中，多个密码组件可能以非平凡的方式交互。通用可组合性（Universal Composability，UC）框架提供了一种处理组合安全性的方法，但其在对称密码设定下的应用仍不够成熟。

对称密码的可证明安全理论为我们提供了一种严格评估密码方案安全性的方法论。从 Luby-Rackoff 定理到现代 AEAD 的安全性分析，每一个结果都揭示了安全性与效率之间的精微平衡。理解这些理论不仅有助于正确地使用现有的密码方案，更为设计新的密码原语提供了可靠的理论指导。在安全性攸关的系统设计中，可证明安全不是可选的学术装饰，而是不可或缺的工程基石。

十、符号与记号速查表

在阅读对称密码可证明安全的相关文献时，以下符号和记号频繁出现。为便于读者查阅，此处汇总为速查表。

符号 / 记号 含义
\(E_K(M)\) 分组密码 \(E\) 在密钥 \(K\) 下对明文 \(M\) 的加密
\(\mathrm{Adv}^{\mathrm{prf}}_F(A)\) 攻击者 \(A\) 对函数族 \(F\) 的 PRF 优势（Pseudorandom Function Advantage）——区分 \(F_K\) 与真随机函数的能力
\(\mathrm{Adv}^{\mathrm{prp}}_E(A)\) 攻击者 \(A\) 对分组密码 \(E\) 的 PRP 优势（Pseudorandom Permutation Advantage）——区分 \(E_K\) 与随机置换的能力
\(\mathrm{Adv}^{\mathrm{sprp}}_E(A)\) 强 PRP 优势（Strong PRP Advantage）——攻击者可同时访问加密和解密预言机
\(\$\) 真随机函数或随机置换预言机的简写符号，表示理想化的随机对象
\(\mathrm{negl}(n)\) 可忽略函数（Negligible Function）——以安全参数 \(n\) 的任意多项式倒数为上界的函数
\(q, t, \mu\) 安全性界中的常用参数：\(q\) 为查询次数，\(t\) 为攻击者运行时间，\(\mu\) 为查询的总数据量
\(2^n\) 分组长度为 \(n\) 比特时的分组空间大小
\(O(q^2 / 2^n)\) 生日界（Birthday Bound）——多数基于分组密码的构造在约 \(2^{n/2}\) 次操作后安全性开始退化
PRP/PRF 转换引理 当查询次数 \(q\) 远小于 \(2^{n/2}\) 时，PRP 与 PRF 之间的区分优势不超过 \(q^2/2^{n+1}\)

笔者认为，PRP/PRF 转换引理（Switching Lemma）是可证明安全理论中最具实践价值的结论之一。它的意义在于：现实中我们使用的 AES 等分组密码本质上是置换（Permutation），而安全性证明中更自然的建模对象是随机函数（Function）。转换引理在两者之间架起了桥梁——只要数据量远低于生日界，我们就可以放心地将分组密码当作随机函数来分析。从工程实践来看，这意味着密码方案的设计者可以先在 PRF 模型下完成安全性证明（通常更简洁），再通过转换引理将结论”搬运”到 PRP 模型（即真实的分组密码），中间只损失一个可以精确计算的极小误差项。这种”先证简单模型，再转换到现实模型”的方法论，贯穿了几乎所有基于分组密码的 AEAD、MAC 和加密模式的安全性分析，是理论与实践对接的典范。

密码学百科系列 · 第 51 篇

← 上一篇：可证明安全 | 系列目录 | 下一篇：公钥密码的可证明安全 →

By .