量子就绪：混合签名技术

随着多国立法要求软件提供商采用混合后量子密码学，Synacktiv已启动对这些新型密码算法的研究。在先前文章探讨了后量子密码学的本质后，我们现在剖析混合化概念——安全过渡的关键机制。本文重点讨论签名方案的混合化，后续文章将涉及密钥交换。

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

快速回顾

签名方案

数字签名算法是用于验证数据真实性、完整性和不可否认性的密码机制。它使用非对称密码学，涉及密钥对：用于签名的私钥和用于验证的公钥。包含三个例程：

KeyGen()：负责生成由私钥部分和公钥部分组成的密钥
Sign(Kpriv, m)：接收私钥和消息，生成该消息的签名
Verify(Kpub, m, sig)：接收公钥、消息和签名，检查签名是否对应该消息和密钥

当攻击者在不知道相关私钥的情况下伪造签名在计算上不可行时，数字签名方案被称为"安全"。存在多种对抗模型来挑战这一假设，如选择消息攻击下的存在不可伪造性(EUF-CMA)，其中攻击者可以访问能够对任意消息签名的预言机，并需要为先前未被预言机签名的新消息生成签名。

组合与混合化

在密码学中，组合器是将多个同类型算法（签名/密钥交换）合并为一个的算法，期望受益于各个算法的所有安全属性。签名组合器接收若干签名算法作为输入，生成新的签名方案，包装所有输入签名算法，并至少与每个单独算法一样强大。

混合化是组合的特殊情况，用户将经典算法与后量子算法结合。主要目标是创建单一、更具弹性的密码方案，能同时抵御经典和量子计算机的攻击。由于后量子方案现场测试和研究相对较少的安全性不确定性，法国ANSSI等许多机构要求采用此方法。

实际上，这种预防原则在过去已被证明有用且高效。2019年，Cloudflare关于后量子过渡的实验评估了在TLS协议中使用后量子密钥交换机制的可行性。他们依赖两个后量子算法SIKE和NTRU-HRSS，两者都与经典X25519混合。后来在2022年，W. Castryk和T. Decru发现了对SIKE的经典攻击，完全破坏了该方案的安全性。如果Cloudflare没有将该算法与稳健的经典算法混合，2019年实验期间执行的SIKE密钥交换今天将被中间人位置记录当时TLS通信的攻击者轻易破解。

这种通用算法构造的主要优势是其密码敏捷性，意味着能够无缝切换密码原语。这有助于缓解单独使用密码原语可能导致的单点故障。

组合签名算法

在我们开始研究真实世界的签名组合器之前，先问自己一个问题：如何组合两个数字签名算法，使得组合体至少与最强算法一样安全（在不可伪造性方面）？

连接组合器

对于上述问题，你的直觉可能是：“只需用两种算法对消息进行签名，发送两个签名并全部验证”。你是对的！这样的方案确实至少与每个单独算法一样安全。

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

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

关于可分离性

虽然先前的方案在完全混合上下文中很有趣，但恶意行为者可能提取单个签名（无论是X还是Y的签名）并单独使用此签名，而没有任何证据表明它最初是混合签名的一部分，从而偏离Alice最初的混合意图。如果验证者出于兼容性原因也接受仅使用混合密钥部分仅使用X或Y的签名，则可能发生这种情况。此属性称为"可分离性"，在N. Bindel和B. Hale 2023年的论文中有详细讨论。

研究人员强调了两个级别的不可分离性：首先是弱不可分离性，其中签名仍然彼此独立执行，“混合证据"在协议级别实现。此类证据的示例可能包括：

使用IETF的复合签名草案，大致相当于使用连接组合器对"HYBRIDSIG”||m进行签名
使用专用于混合签名的专用密钥（例如证书中具有特定密钥使用属性）

还提出了更强级别的不可分离性（称为强不可分离性）。这次，构件在算法级别实现。为简单起见，从论文改编的强不可分离方案示例（将基于Fiat-Shamir的方案（如后量子方案ML-DSA）与RSA结合）如下：

在此方案中，RSA签名不直接与消息相关且本身无意义，而Fiat-Shamir签名没有RSA数据则不完整。因此，该方案是强不可分离的，因为在不涉及其他算法的情况下无法验证组件签名。此外，它仍然保持"至少与单个签名算法一样强大"。有关此类方案的更多细节，请参阅原始论文。

除了阻止攻击者隔离子签名外，强不可分离性还可能使您免于以下实现错误：

 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 # 使用X验证签名的操作
    valid &= isXValid

def verify_Y(key, message, signature):
    global valid
    isYValid = True # 使用Y验证签名的操作
    valid &= isYValid

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

# 全局"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))

# 启动验证线程
thread_x.start()
thread_y.start()
# 等待两个线程返回
thread_x.join()
thread_y.join()

print(f"混合签名有效性为: {valid}")

此代码表面看起来不错（除了可能存在的竞争条件，此处不相关），并行化签名验证以提高性能：

1
2


$ python3 hybrid_parallel.py 
混合签名有效性为: True

但是，想象由于某种原因，verify_Y引发异常：

1
2
3
4
5


def verify_Y(key, message, signature):
    global valid
    raise Exception() # 在Y验证期间崩溃
    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
混合签名有效性为: True

在这种情况下，虽然Y线程中抛出异常，但对程序不是致命的，签名仍被计算为有效。在使用强不可分离混合方案的情况下，这不可能发生，因为签名在数学上是相互依赖的。

然而，强不可分离性带来了密码敏捷性挑战。所涉及两种算法的纠缠水平意味着签名/验证例程不能再被视为并行运行的黑盒，使组合强不可分离所需的调整与所选算法对的具体细节密切相关。因此，必须在安全性与密码敏捷性需求之间取得平衡。

结论

虽然连接组合器为创建混合签名提供了相当安全的方法，但可以在不可分离性方面进行改进以达到最先进的签名安全性。尽管如此，对于大多数用例，连接方法辅以弱不可分离性保护措施（如使用专门标记用于混合签名的专用密钥）对于安全过渡已经足够。

还值得注意的是，混合签名可能不是您最紧迫的优先事项。对于性能不太关键的应用，您已经可以使用后量子且高度可信的基于哈希的签名（如SLH-DSA）。尽管它们速度较慢且资源密集，但它们今天提供了稳健的安全性，在这些上下文中无需立即转向混合方案。

总之，理论是不够的；应用程序的安全性在于其实现的细节。如果您实现这些新的密码原语，我们强烈建议您提交工作以进行评估：Synacktiv将非常乐意在此过程中为您提供陪伴。

后量子密码时代：混合签名技术深度解析

本文深入探讨后量子密码学中的混合签名技术，分析签名组合器的安全原理与实现方式，包括连接组合器和强不可分离性方案，为安全过渡到后量子时代提供技术指导。