量子就绪：混合密钥交换技术详解

本文深入探讨了混合密钥交换机制，结合经典密码学与后量子密码学的优势，分析不同组合方法的优缺点，并介绍确保IND-CCA安全性的标准化构造方案。

量子就绪：混合密钥交换

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

目录

  • 快速回顾：定义
  • 组合KEM
  • 经验总结

想要提升技能？发现我们的培训课程！了解更多。

比数字签名方案更紧迫的是，我们在互联网上交换共享秘密的方式需要过渡到后量子时代。由于对新的"后量子"密钥交换方案的认识相对不足，大多数机构鼓励使用混合方案，将著名经典方案的鲁棒性与新方案提供的后量子保护相结合。这篇博客文章详细介绍了混合密钥交换主要概念的最新进展。

快速回顾：定义

密钥封装机制

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

密钥封装机制由三个例程定义：

  • KeyGen()：负责生成由私钥部分和公钥部分组成的密钥对。
  • Encaps(Kpub)：负责生成一个秘密值和一个"胶囊"，这是一个只有关联私钥持有者才能转换回秘密值的数据块。
  • Decaps(Kpriv, 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年的一篇研究论文³中深入研究了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的共享秘密，然后对其执行密钥派生操作（例如使用哈希函数）以形成最终的共享秘密。这确保了在熵方面，每个输出位都依赖于每个输入位。然而，在我们理想组合器必须"至少与每个成分KEM一样好"的世界中，这仍然不足够。

为了进一步证明这一点，让我们研究"会话密钥不可区分性"的概念（在两篇IACR论文³⁴中讨论）。它描述了对手在给定相应胶囊的情况下，区分共享秘密与随机数据块的能力。

会话密钥不可区分性可以看作是在给定两个可能答案的情况下猜测"盒子里是什么？"。

我们将在这里涵盖两个级别的会话密钥不可区分性：

  • 选择明文攻击下的不可区分性（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那样具有碰撞的KEM可以通过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

# === 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等人的研究⁵，如果您能证明组件KEM的密文第二原像抵抗性，那么"连接然后哈希"的组合是安全的。在我们的示例中，这个属性显然没有得到尊重，因为KEM_Y是专门设计来提供碰撞的，因此导致了所得KEM的IND-CCA崩溃。

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

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

为了避免这种性能缺点，IETF的Composite ML-KEM草案⁶提出了不同的方法。通过证明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的Composite ML-KEM中使用的组合器函数。Domain是一个常量，用于指示已组合的特定算法对。

经验总结

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

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

  1. 通用构造：不仅将共享秘密，还将每个KEM的胶囊和公钥纳入最终的密钥派生函数。这是更安全的路径，但由于后量子构件的大尺寸，可能会带来显著的性能成本。
  2. 更优化的方法：例如IETF为Composite ML-KEM采取的方法，依赖于证明组件KEM更强的安全属性，如密文第二原像抵抗性。这允许更简化的组合，从哈希中省略庞大的后量子胶囊和密钥，在不牺牲安全性的情况下实现高性能。

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

¹. https://www.synacktiv.com/en/publications/quantum-readiness-lattice-bas… ². https://synacktiv.com/en/publications/quantum-readiness-hybridizing-sig… ³. a. b. https://eprint.iacr.org/2018/024.pdf ⁴. a. b. https://eprint.iacr.org/2020/1364.pdf ⁵. https://eprint.iacr.org/2024/039 ⁶. https://datatracker.ietf.org/doc/draft-ietf-lamps-pq-composite-kem/

comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次