[博客翻译]量子密码学规模太大了

由 发布于 量子密码学加密密钥交换签名安全性
 收藏

原文地址：https://dadrian.io/blog/posts/pqc-signatures-2024/


大型量子计算机一旦出现，将能破解当前互联网广泛使用的非对称加密算法。目前它们还未存在。2022年，NIST宣布了PQC竞赛中的最终密钥交换和签名方案，标志着互联网向后量子加密的转变开始。关于各种算法和标准化流程的讨论已经很多。

普遍的看法是，向后量子加密的过渡需要很长时间，因此即使量子计算机还未真正出现，我们也要开始标准化并部署相关技术。NIST竞赛的结果将被采用。

然而，关于NIST标准化的方案是否足够在公共网络上部署的问题却没有充分讨论。我们需要更优的算法，特别是那些在网络传输中占用更少字节的：嵌入在TLS ClientHello中的密钥交换方案应小于一个MTU（最大传输单元），与ECDSA性能相当但大小不超过RSA-2048的签名方案，以及可处理大公钥的小于100字节的签名。

我们来探讨一下HTTPS中加密的现状。在公开网络上的HTTPS中，加密主要用于五个方面：

  1. 对称加密/解密：HTTP/2的数据通过TLS连接中的认证密码（如AES-GCM）进行传输，这在很大程度上已能抵御量子计算机。
  2. 密钥协商：对称加密需要密钥，密钥协商是双方共同生成密钥的过程。在TLS 1.3中，通常使用椭圆曲线 Diffie-Hellman进行密钥协商。所有非量子安全的密钥交换机制，包括Diffie-Hellman，都会被量子计算机破解。
  3. 服务器身份验证：服务器通过X.509证书进行身份验证。至少，服务器证书包含公钥和中间证书的签名。中间证书又包含另一个公钥及其根证书的签名。公开Web PKI依赖于受信任的证书颁发机构来验证域名所有权。
  4. 发行透明度：Web PKI依赖于公开记录的证书，服务器确认证书已包含在记录中，这有助于防止恶意证书颁发。服务器通过提供至少两个签名证书时间戳（SCT）来实现透明度。
  5. 握手认证：在TLS握手期间，需要将服务器的身份绑定到连接上。在TLS 1.3中，这通过服务器证书中的公钥在“CertificateVerify”消息中的签名来实现。

当前的量子威胁主要体现在“现在收集，未来解密”的攻击中。为了防御，我们只需确保密钥协商和对称加密是“量子安全”的。幸运的是，对称加密已经足够安全，所以只需要更新密钥交换算法为量子安全版本即可。

HTTPS中剩下的加密用途——服务器身份、发行透明度和握手认证——最终需要转向量子安全版本。在当前TLS架构中，这意味着替换所有签名为量子安全版本。尽管这同样重要，但不如密钥交换紧迫。

浏览器已经开始部署量子安全的密钥交换算法，如X25519（客户端和服务器各传输32字节）和NIST竞赛的密钥交换赢家ML-KEM（客户端发送1,184字节，服务器发送1,088字节）。然而，没有主流浏览器开始部署量子安全签名。

原因在于量子安全签名及其对应的公钥过大。HTTPS握手通常涉及5个签名和2个公钥：

  1. 叶子证书包含1个网站的签名公钥和1个来自中间证书的签名。
  2. 中间证书包含1个用于验证叶证书签名的签名公钥，以及1个验证根证书签名的公钥，用于验证中间证书的真实性。根证书及其嵌入的公钥预分发给客户端。
  3. 握手本身包含由叶证书公钥对应的私钥签署的1个签名。
  4. 每个SCT包含1个签名，验证签名的公钥预分发给客户端。大多数证书有2个SCT，因此额外需要2个签名。

目前TLS中密钥和签名的大小大致如下：

  1. 根证书通常包含RSA密钥，中间证书也如此。根证书预分发，而中间证书由服务器提供，与叶证书一起。一个RSA中间证书的签名是4096位（512字节），公钥是2048位（256字节）。
  2. ECDSA叶证书的公钥是32字节，来自中间的RSA签名是256字节。
  3. 握手包含64字节的ECDSA签名。
  4. 每个SCT包含64字节的ECDSA签名。

总计，一个标准TLS HTTPS握手中的签名和公钥大小约为1,248字节。NIST PQC竞赛的赢家ML-DSA（Dilithium）是唯一适合TLS的签名算法，但其1,312字节的公钥和2,420字节的签名使得单个ML-DSA公钥就比当前HTTPS连接中所有5个签名和2个公钥还要大。直接替换现有签名算法为ML-DSA会导致TLS握手包含14,724字节的签名和公钥，这是当前的10倍多。

在没有大规模量子计算机的情况下，仅为了建立连接就发送如此大量的数据是不可持续的。作为基本的检查，我们不应该仅在签名和公钥中就发送超过3.5英寸软盘的1%。

从实际影响来看，Cloudflare发现服务器响应中每增加1千字节的数据，HTTPS握手的中值延迟会增加约1.5%。而Chrome在部署ML-KEM后，ClientHello的TLS握手延迟增加了4%，因为额外的1千字节超过了互联网标准的MTU（约1400字节），导致ClientHello被分片为两个底层传输层（TCP或UDP）包。

如果ML-KEM成为常态，为了将后量子加密对总延迟的影响控制在10%以下（假设为10%），我们需要服务器响应中额外的认证信息控制在约4千字节内。不幸的是，单个ML-DSA签名/公钥对就大约是4千字节。在量子威胁还未明确的时间线上，ML-DSA太大，无法部署。

有一些积极的进展：