量子就绪：密钥交换的混合化技术

量子就绪：混合化密钥交换

继我们之前关于签名混合化的文章之后，本文涵盖了混合化密钥交换的基础知识，以确保数据的最大安全性。

与数字签名方案相比，我们在互联网上交换共享秘密的方式更迫切需要过渡到后量子时代。由于对新的“后量子”密钥交换方案的了解相对不足，大多数机构鼓励使用混合方案，将知名经典方案的稳健性与新方案提供的后量子保护相结合。这篇博文详细介绍了混合密钥交换的主要概念现状。

快速回顾：定义

密钥封装机制

将某物称为密钥封装机制（KEM）只是一种花哨的说法，指的是您已经知道的一个通用解决方案：Alice 和 Bob 如何通过公共渠道共享秘密？在经典密码学中，这个问题是通过 Diffie-Hellman 密钥交换解决的：Alice 和 Bob 发布各自的公钥，并将自己的私钥与对方的公钥混合，最终得到只有他们自己知道的相同秘密值。在后量子密码学中，存在各种技术来建立这个共享秘密，其中一些技术在我们之前关于基于格的方案的文章中讨论过。密钥封装机制由三个例程定义：

KeyGen()：负责生成由私钥部分和公钥部分组成的密钥对。
Encaps(K_pub)：负责生成一个秘密值和一个“胶囊”，这个“胶囊”是一个数据块，只有持有相关私钥的人才能将其转换回秘密值。
Decaps(K_priv, caps)：通过使用相应的私钥从胶囊中恢复秘密值。

例如，经典的 Diffie-Hellman（DH）密钥交换可以视为一个 KEM，通过如下定义三个例程： DH 公共参数： 生成器 g

KeyGen()：选择一个随机整数 s。返回 K_priv = s 和 K_pub = g ** s。
Encaps(K_pub)：Encaps 可以看作是一个短暂的 Diffie-Hellman 密钥交换。首先选择一个随机整数 x，然后计算将作为您的胶囊的相关公钥 caps = g ** x，以及共享秘密 secret = K_pub ** x。
Decaps(caps, K_priv)：Decaps 简单地计算短暂公钥与我们自己私钥之间的密钥交换。secret = caps ** K_priv。

混合化

混合化是将后量子和经典方案相结合的做法，以获得一种能同时抵御经典攻击和量子攻击的、更具弹性的新方案。有关更详细的定义，请参阅我们之前关于混合化签名的博客文章。如果您还没有阅读，我们鼓励您阅读。

组合KEM

F. Giacon、F. Heuer 和 B. Poettering 在 2018 年的一篇研究论文3中深入研究了 KEM 组合器。在本文中，他们介绍了一种组合器的通用构造，其中所有密钥交换并行执行。实际的组合工作最后进行，作为所有共享秘密、胶囊和公钥的函数 W，输出组合后的共享秘密。

在接下来的部分中，我们将研究此类函数，并说明它们可能或可能不成为相关选择的原因。

拼接共享秘密

当需要将多个秘密组合成一个时，可能采取的第一个方法就是简单地将它们全部拼接起来。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


- CombiKEM.KeyGen():
    S_X, P_X <= KEM_X.KeyGen()
    S_Y, P_Y <= KEM_Y.KeyGen()
    S <= S_X, S_Y
    P <= P_X, P_Y
    return S, P

- CombiKEM.Encaps(P):
    P_X, P_Y <= Split(P)
    ss_X, caps_X <= KEM_X.Encaps(P_X)
    ss_Y, caps_Y <= KEM_Y.Encaps(P_Y)
    ss <= ss_X || ss_Y                 <--- W
    caps <= caps_X, caps_Y
    return ss, caps

- CombiKEM.Decaps(caps, S):
    caps_X, caps_Y <= Split(caps)
    S_X, S_Y <= S
    ss_X <= KEM_X.Decaps(caps_X, S_X)
    ss_Y <= KEM_Y.Decaps(caps_Y, S_Y)
    ss <= ss_X || ss_Y                 <--- W
    return ss

但是，有几点原因说明这可能不是最好的做法：

最终共享秘密的长度随组合的 KEM 数量及其输出大小而变化。
如果其中一个 KEM 被攻破，攻击者将部分获知最终的共享秘密。因此，它将不再完全是“秘密”。

理想情况下，攻破我们组合器中除一个以外的所有 KEM，都不应提供足够的信息来猜测最终共享秘密的部分内容。直觉上，我们希望我们的 KEM 能将每个 KEM 带来的熵扩散到最终共享秘密的所有比特上。

拼接共享秘密，然后哈希

借鉴了之前关于熵扩散的经验教训，可以将以下组合器视为下一个迭代方案：该组合器先将组件 KEM 的共享秘密拼接起来，然后对其执行密钥派生操作（例如使用哈希函数），以形成最终的共享秘密。这确保了在熵方面，每个输出比特都依赖于每个输入比特。然而，在一个理想组合器必须“至少与每个成分 KEM 一样好”的世界里，这仍然是不够的。为了进一步证明这一点，让我们研究一下“会话密钥不可区分性”的概念（在两篇 IACR 论文3和4中讨论过）。它描述了对手在给定相应胶囊的情况下，区分共享秘密和随机数据块的能力。

可以将会话密钥不可区分性想象成给定两个可能的答案来猜测“盒子里是什么？”。这里我们将介绍两个级别的会话密钥不可区分性：

抗选择明文攻击的不可区分性（IND-CPA）：挑战者提供一个公钥、一个胶囊、其关联的共享秘密和一个随机数据块。对手可以访问一个 Encaps 预言机，他们可以根据需要任意次调用该预言机，输入任何他们选择的公钥。在某个时刻，对手必须确定提供的两个数据块中哪个是由所提供胶囊包装的共享秘密。
抗选择密文攻击的不可区分性（IND-CCA）：挑战者仍然提供一个公钥、一个胶囊、其关联的共享秘密和一个随机数据块。对手现在可以访问一个 Encaps(P) 预言机和一个 Decaps(caps) 预言机（使用与挑战相同的密钥进行解封装），他们可以根据需要任意次调用这些预言机，输入任何内容，除了提供的胶囊。在某个时刻，对手必须确定提供的两个数据块中哪个是由所提供胶囊包装的共享秘密。

根据我们的“盒子里是什么？”的比喻，您可以将 IND-CPA 想象成可以访问一个礼品包装机，在您猜测原始盒子里是什么之前，可以包装任意数量的物品。IND-CCA 则让您访问一个包装机和一个拆包装机，您可以询问任何事情，但不能要求拆开原始盒子。

一个 KEM 的安全性可以根据这些安全特性来评定，我们希望我们的组合器能达到与最佳成分 KEM 相同的会话密钥不可区分性级别。

遗憾的是，“拼接后哈希”组合器在一般情况下不符合我们的期望。事实上，让我们考虑两个 KEM，KEM_X 和 KEM_Y。进一步假设 KEM_X 是 IND-CCA 安全的，但 KEM_Y 被攻破，其方式是可以为一个固定的（但秘密的）私钥 k 找到胶囊/共享秘密碰撞，即对于某个 caps，找到 caps' ≠ caps 使得 Decaps(caps, k) == Decaps(caps', k)。我们注意到 KEM_Y 不是 IND-CCA 安全的；给定一个挑战 (caps, sA, sB)，对手可以生成一个与 caps 碰撞的胶囊 caps'，然后用 Decaps(caps') 查询解封装预言机。然后，对手可以利用预言机返回的共享秘密赢得游戏。

确实，当提供挑战 (caps, sA, sB)（其中 caps 由来自 KEM_X 的 X_caps 和来自 KEM_Y 的 Y_caps 组成）时，对手能够制作 Y_caps' ≠ Y_caps，该胶囊用 KEM_Y 解封装得到相同的共享秘密。因此，对手有两个不同的胶囊 caps = X_caps, Y_caps 和 caps' = X_caps, Y_caps'，它们用我们组合的 KEM 解封装得到相同的共享秘密。使用与论证 KEM_Y 不是 IND-CCA 相同的理由，复合 KEM 不是 IND-CCA，而 KEM_X 是 IND-CCA。

需要注意的是，像前面演示中那样具有碰撞的 KEM_Y 可以通过 Diffie-Hellman 密钥交换来实例化，前提是参数选择不当：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


# === DH params
p=1277723 # p = 2*q + 1, with q=638861 also prime
g=3       # order(g) = q


# === KeyGen()
# Alice privkey
a = 130376
# Alice pubkey
A = pow(g, a, p)


# === Encaps(A)
# Bob ephemeral private key
b = 644734
# Bob ephemeral public key
B = pow(g, b, p)
# Shared secret and capsule
ss, caps = pow(A, b, p), B


# === Decaps(caps, a)
assert pow(caps, a, p) == ss

# === Collision !
# Other capsule, colliding (using the fact that `a` is even)
v = 1277722    # order(v) = 2
caps_coll = (caps*v) % p
assert caps != caps_coll and pow(caps_coll, a, p) == ss

如您所见，对于给定的胶囊和选择不当的私钥，可以在该方案中瞬间找到碰撞的胶囊。尽管如此，根据 M. Barbosa 等人的论文5，如果您能证明组件 KEM 的密文第二原像抵抗性，那么“拼接后哈希”的组合是安全的。在我们的示例中，这一特性显然没有得到遵守，因为 KEM_Y 是专门设计来提供碰撞的，因此导致了所得 KEM 的 IND-CCA 失效。

拼接共享秘密和胶囊，然后哈希

对于一般情况，M. Campagna 和 A. Petcher 在 2020 年的论文4中提出将每个 KEM 的胶囊和公钥也加入混合中。这一增加允许防御前一段中介绍的攻击，因为碰撞胶囊的最终共享秘密现在将不同。然而，后量子算法的胶囊和密钥比经典算法要大得多。因此，这种构造带来了不可忽视的开销，即对密钥派生函数调用的输入更大。

为了避免这种性能缺陷，IETF 的复合 ML-KEM 草案6提出了不同的方法。通过证明 ML-KEM 具有密文第二原像抵抗性，他们可以安全地从 KDF 输入中省略庞大的 ML-KEM 胶囊和公钥。这种方法在无需性能损失的情况下保持了所需的 IND-CCA 安全性。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


KemCombiner<KDF>(mlkemSS, tradSS, tradCT, tradPK, Domain) -> ss
[...]
    if KDF is "SHA3-256":
        ss = SHA3-256(mlkemSS || tradSS || tradCT || tradPK || Domain)

    else if KDF is "HMAC-{Hash}":
        ss = HMAC-{Hash}(key={0}, text=mlkemSS || tradSS || tradCT || tradPK || Domain)
        ss = truncate(ss, 256)
    
    return ss

IETF 复合 ML-KEM 中使用的组合器函数。Domain 是一个常量，用于指示具体组合了哪对算法。

经验教训

混合化密钥交换提供了一条审慎的前进道路，融合了经典算法经过时间考验的安全性和后量子方案的未来适应性。然而，本文表明，用于组合这些方案的方法与方案本身同样关键。我们已经看到，简单地拼接共享秘密是不够的，甚至更直观的“拼接后哈希”方法也可能引入细微的漏洞。

要构建真正有弹性的混合 KEM，主要有两条路径：

一个通用构造，不仅将每个 KEM 的共享秘密，还将它们的胶囊和公钥都纳入最终的密钥派生函数中。这是更安全的路径，但由于后量子组件体积庞大，可能会带来显著的性能成本。
更优化的方法，例如 IETF 为复合 ML-KEM 所采用的方法，依赖于证明组件 KEM 更强的安全属性，例如密文第二原像抵抗性。这使得可以省略庞大的后量子胶囊和密钥进行更精简的组合，在不牺牲安全性的情况下实现高性能。

总之，设计安全的混合机制是一项细致入微的任务，无论是对于签名还是密钥交换。开发人员应依赖标准化且经过严格分析的构造，例如 IETF 提出的那些，而不是依赖直觉发明自定义解决方案。这些标准为实现高安全性和实际性能提供了可信的蓝图，确保我们的加密通信对所有对手（无论是现在的还是未来的）都保持机密性。