过渡后量子：签名的混合

鉴于许多国家颁布了新的法律要求，要求软件发行商考虑量子威胁，Synacktiv 已就此主题展开了能力提升。在之前的文章中研究了算法“后量子”与否的决定因素之后，我们现在将剖析混合概念，这是安全过渡的关键机制。本文重点讨论签名方案的混合，而第二篇文章将讨论密钥交换。

简要回顾与定义
组合签名算法
结论

注意：您想提升技能吗？了解我们的培训课程！了解更多

编者注：英文原文见此

密码学混合是安全过渡到后量子时代的首选策略。通过结合现有算法经过验证的稳健性和新标准对抗量子威胁的抵抗力，它能保证最佳保护。然而，这种双重保障是有代价的：更复杂的实现以及对性能的显著影响。本文探讨了实现稳健混合签名的技术考量与最佳实践。

简要回顾与定义

签名方案

尽管数字签名的概念已广为人知，但重温一下也无妨。签名算法是一种用于验证数据真实性、完整性和不可否认性的密码学机制。它基于非对称密码学，涉及一个由两部分组成的密钥：一个用于签名的私钥部分和一个用于验证的公钥部分。它包含三个算法：

KeyGen()，负责生成一个密钥，该密钥由一个私钥部分和一个公钥部分组成。
Sign(Kpriv, m)，输入一个私钥部分和一个消息，并生成该消息的签名。
Verify(Kpub, m, sig)，输入一个公钥部分、一个消息和一个签名，并验证该签名是否确实对应于该消息和该密钥。

当一个数字签名方案在计算上难以让攻击者在不知道关联私钥的情况下伪造签名时，它就被认为是“安全的”。存在不同的对手模型来挑战这一假设，例如“抗选择消息攻击的存在性不可伪造性”（EUF-CMA）。在此模型中，对手可以访问一个能够对任意消息进行签名的预言机，其目标是生成一个先前未被预言机签名过的新消息的签名。因此，如果一个方案不存在任何“高效的”对手（即，其执行的操作少于该签名方案理论稳健性要求），则认为该方案在 EUF-CMA 意义下是安全的。

组合与混合

在密码学中，组合器是一种算法，它将多个相同类型（签名/密钥交换）的算法融合为一个，以期受益于所有单个算法的安全属性。因此，签名组合器接受一定数量的签名算法，并生成一个新的签名方案，该方案包含所有这些算法，并且希望至少与其中任何一个单独使用时一样稳健（至少，这是我们的期望）。

混合是组合的一个特例，其中经典算法与后量子算法相关联。其主要目标是创建一个更具弹性的密码方案，同时抵抗经典计算机和量子计算机。由于后量子方案迄今为止在现实条件下的研究和实践较少，其安全性存在相对不确定性，因此这种方法被法国 ANSSI 等许多机构所要求。

这种预防原则在过去已被证明是有用的。事实上，2019年 Cloudflare 进行的后量子过渡实验评估了在 TLS 协议中使用后量子密钥交换机制的可行性。为此，Cloudflare 依赖了两种后量子算法 SIKE 和 NTRU-HRSS，两者均与经典算法 X25519 混合。不幸的是，2022 年，W. Castryk 和 T. Decru 发现了针对 SIKE 的攻击，该攻击彻底摧毁了该方案的安全属性，即使面对经典计算机也是如此。如果 Cloudflare 没有将此算法与稳健的经典算法混合，那么在 2019 年的那次实验中进行的 SIKE 密钥交换，如今对于一个处于中间人位置且记录了当时 TLS 通信的攻击者来说，将是微不足道可破解的。

这种通用算法构造的另一个优势是密码敏捷性，即能够透明地互换密码原语。这有助于减轻单一密码原语单独使用时可能构成的单点故障。

由于后量子密码学领域目前主要关注密钥建立和数字签名，我们将在本系列文章中专注于这两个领域。本文着眼于混合签名的主题，而下一篇将专门讨论密钥封装机制（KEM）。

尽管理论上可以为组合 n 个算法构建组合器，但我们只覆盖最常见的情况，即 n=2。更具体地说，我们将专注于将单个经典算法与单个后量子算法相结合的混合模型。

组合签名算法

拼接组合器

组合两个签名算法的第一个直观构造可能是：“简单地用两种算法对消息进行签名，发送两个签名，并验证它们所有”。这样的方案确实至少与每个算法单独使用时一样安全。

假设 Alice 使用这个由算法 X 和 Y 组成的组合方案向 Bob 发送一个签名消息，其中至少有一个算法（假设是 X）是 EUF-CMA 安全的。为了在此组合方案中伪造一个消息 m 的签名，攻击者需要为 m 伪造一个使用算法 X 的签名和一个使用算法 Y 的签名。然而，由于 X 是 EUF-CMA 安全的，这个任务对于攻击者来说是不可行的。因此，这个签名组合器在 EUF-CMA 意义上也是安全的。更一般地说，要破坏此组合器的安全属性，需要破坏所有底层算法的该属性，这就保证了“至少与每个组件一样安全”的属性。

值得注意的是，此组合器是 ANSSI 在其 Real-World PQC 2023 演示中为签名组合推荐的唯一通用构造。

可分割性

尽管前面的方案在完全混合的背景下很有趣，但恶意行为者可能会提取单一签名（无论是算法 X 还是 Y 的签名），并在没有任何证据证明其最初是混合签名一部分的情况下单独使用它，从而偏离 Alice 最初的混合意图。如果验证者出于兼容性等原因，也接受仅使用 X 或 Y 以及混合密钥的一部分进行的签名，这种情况就可能发生。此属性称为“可分割性”，并在 2023 年 N. Bindel 和 B. Hale 的文章中进行了详细讨论。

研究人员强调了两个级别的不可分割性：第一个是弱不可分割性，其中签名总是独立执行，并且“混合证明”在协议级别实现。此类证明的示例可能包括：

使用 IETF 关于复合签名的草案规范，这基本上等同于使用拼接组合器对 "HYBRIDSIG"||m 进行签名。
使用专门为混合签名发布的密钥（例如，在证书中使用特定的密钥用途属性）。

还提出了第二个级别的不可分割性（称为强不可分割性）。这一次，工件在算法级别实现。一个强不可分割方案的示例（为简单起见，根据 N. Bindel 和 B. Hale 的文章进行了调整），该方案结合了基于 Fiat-Shamir 的方案（如 ML-DSA）和 RSA，如下所示：

这里，RSA 签名并不直接与消息关联，并且本身没有意义；而没有 RSA 数据，Fiat-Shamir 签名也是不完整的。因此，该方案是强不可分割的，因为不可能在不涉及另一个算法的情况下验证某个组件的签名。此外，它仍然“至少与各个签名算法一样稳健”。有关此类方案的更多细节，原始文章非常有趣且易于理解。

除了防止攻击者分离子签名外，强不可分割性还可以帮助避免实现错误。例如，想象以下代码：

 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
30


import threading

def verify_X(key, message, signature):
    global valid
    isXValid = True # placeholder pour la vérification de signature avec X
    valid &= isXValid

def verify_Y(key, message, signature):
    global valid
    isYValid = True # placeholder pour la vérification de signature avec Y
    valid &= isYValid

key = "aaa"
message = "bbb"
signature = "ccc"

# Variable globale "valid"
valid = True

thread_x = threading.Thread(target=verify_X, args=(key, message, signature))
thread_y = threading.Thread(target=verify_Y, args=(key, message, signature))

# Démarrage des threads de vérification
thread_x.start()
thread_y.start()
# Attente de la fin des deux threads
thread_x.join()
thread_y.join()

print(f"Hybrid signature validity is: {valid}")

乍一看，这段代码似乎是正确的（除了可能存在一个与此处无关的竞态条件），它并行验证签名以获得更好的性能：

1
2


$ python3 hybrid_parallel.py
Hybrid signature validity is: True

然而，假设 verify_Y 由于某种原因引发了异常：

1
2
3
4
5


def verify_Y(key, message, signature):
    global valid
    raise Exception() # crash during Y verification
    isYValid = False
    valid &= isYValid

代码将表现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


$ python3 hybrid_parallel.py
Exception in thread Thread-2 (verify_Y):
Traceback (most recent call last):
  File "/usr/lib/python3.11/threading.py", line 1038, in _bootstrap_inner
    self.run()
  File "/usr/lib/python3.11/threading.py", line 975, in run
    self._target(*self._args, **self._kwargs)
  File "/tmp/hybrid_parallel.py", line 10, in verify_Y
    raise Exception()
Exception
Hybrid signature validity is: True

尽管在线程 Y 中引发了异常，但它对程序来说不是致命的，并且签名被视为有效。在强不可分割的混合方案中，这种情况不可能发生，因为签名在数学上是相互依赖的。

然而，强不可分割性伴随着密码敏捷性方面的挑战。所涉及的两个算法的纠缠程度意味着签名/验证例程不能再被视为并行运行的黑盒，并且使组合具有强不可分割性所需的调整与所选算法对的具体特性密切相关。因此，必须在安全性与密码敏捷性需求之间进行权衡。

结论

尽管拼接组合器为创建混合签名提供了一种相当安全的方法，但可以通过在不可分割性方面进行改进来达到签名安全性的最新水平。然而，对于大多数用例，拼接方法辅以弱不可分割性保护（例如使用专门为混合签名标记的专用密钥），足以实现安全过渡。

还值得注意的是，签名的混合可能不是今天的优先事项，因为在足够强大的量子计算机出现之前，它们并未受到威胁。但是，如果出于某种原因，您今天就想迁移，并且对于性能不那么关键的应用，基于哈希的签名方案（如 SLH-DSA）已经能够抵抗量子威胁。尽管它们速度较慢且资源消耗更大，但这些方案目前提供了适当的安全性，并且信任度相当高，这使得在这些情况下无需通过混合方案过渡。

总而言之，理论是不够的；实现的安全性在于细节。如果您正在开发这些新的密码原语，我们强烈建议您提交您的工作进行评估：Synacktiv 将很乐意在此过程中为您提供支持。

参考文献