TLS1.3 后量子安全迁移方案、实现和性能评测*

张 枫, 潘天雨, 赵运磊

复旦大学 计算机科学技术学院, 上海200433

1 背景

数字通信是众多关键服务(包括远程医疗、网上银行、电子商务、机器自动化、移动和云计算) 的推动者, 完全渗透到了人们日常生产和生活之中, 使得当今世界越来越依赖于数字通信.数字通信的一个核心需求是安全, 并且这种需求在未来会变得越来越重要.为了给数字通信提供安全保障, 国际互联网工程任务组(Internet Engineering Task Force, IETF) 研发和制定了因特网安全传输层协议(transport layer security,TLS),用于在数字网络上建立加密的通信隧道,为网络数据提供保密性、认证和数据完整性.TLS是实际中部署和应用最为广泛的密码协议, 数据研究表明, 全球每天产生大约230个TLS 链接[1], 超过60% 的互联网数据是通过基于TLS 的安全HTTPS 协议实现的[2,3].而且, 随着互联网用户对加密和隐私需求的增加, 预计作为工业标准的TLS 的使用频率将继续增长[4].

公钥密码学为开放网络上的数字通信提供安全保障, 它是包括TLS 在内的所有互联网协议的安全基石. 这些协议的基本结构是相似的, 首先使用公钥密码算法进行实体认证并建立共享密钥, 然后利用该共享密钥使用对称密码算法提供机密性和数据完整性.然而这种依赖于(椭圆曲线) 离散对数和大整数素因子分解难题的公钥密码算法面临量子计算机强大计算能力的威胁.Shor 量子算法[5,6]可在多项式时间内解决离散对数和素因子分解问题, 使得当前使用的公钥算法不再安全, 给我们的网络安全带来了严重隐患.而且, 作为全球研究热点的量子计算机正在以量子体积每年翻倍的“量子摩尔定律” 向前发展.一旦这种量子霸权(quantum supremacy)[7]成为现实, 现有公钥密码体制将发生颠覆性的崩塌.

量子计算机的发展引起了信息技术和安全研究人员的关注, 研发部署抗量子攻击的新型产品得到了相关组织、机构和企业的广泛关注, 如国际标准化组织ISO、美国国家安全局NSA、美国国家标准与技术研究院NIST、欧洲电信标准化协会ETSI、Google、Amazon 和Microsoft 等都在开展相关研究.2015年, 欧洲电信标准化协会(European Telecommunications Standards Institute, ETSI) 成立了一个量子安全工作组, 旨在对工业界和学术界关于实际应用量子安全密码的各种建议进行评估; 同年, 欧盟启动抗量子密码算法项目PQCRYPTO 和SAFECRYPTO, 致力于后量子密码学研究, 开发新的加密系统, 以防止可能发生的量子计算机攻击; 2016 年, 美国国家标准与技术研究院(National Institute of Standards and Technology, NIST) 正式启动了征集抗量子密码算法的公共项目, 该项目主要关注抗量子算法的安全性, 旨在标准化公钥加密(public key encryption, PKE)、密钥封装(key encapsulation mechanism,KEM) 和数字签名这3 类基本的抗量子公钥密码算法.在国内, 中国密码学会(Chinese Association for Cryptologic Research, CACR) 于2019 年开展了全国密码算法设计竞赛, 征集抗量子密码算法并逐步开展国产密码算法标准化, 加强自主可控的量子密码算法国产化进程.一旦标准机构标准化了抗量子密钥交换和数字签名方案的算法, 后量子密码的采用将取决于将这些算法集成到现有通信协议和互联网基础设施的进展.

然而将这些后量子算法集成到现有协议(如TLS、IKEv2、SSH) 中, 并与当今互联网基础设施共存并不是一件容易的事情, 存在各种各样的挑战.这些挑战包括: 后量子密码算法和传统算法在算法处理逻辑和消息结构上有很大不同; 后量子算法在计算速度上与传统算法有较大差异, 繁重的操作会在通信信道两端增加网络延迟; 后量子算法比传统算法相比要传输的数据量大大增加, 加重了通信开销等.随着后量子算法的发展和标准化, 已经存在各种各样为TLS 生态提供抗量子密码特性的准备工作.我们至少可以看到三条主要的工作路线:

(1) 将后量子算法集成到符合现有协议格式和消息流的规范(草案) 中[8–13].这些工作主要集中在TLS 后量子密钥交换上, 因为确保密钥交换可以抵抗量子攻击的需求更为急迫.一个当前并不具备量子计算能力的攻击者可以先行监控并记录下通信数据, 在具备量子计算能力之后再对它们解密.对于军事、政治和医疗等任何必须长期保密的关键信息来说, 这是一个高度的威胁.

(2) 完成这种集成的原型实现[14–20], 观测它们是否满足协议和软件中的现有限制.相关的一系列工作源于Google 的实验[14,21].随后Google、Cloudflare 和其他公司合作,通过修改客户机浏览器和边缘服务器支持在TLS 1.3 中使用混合密钥交换方案(将后量子密钥交换算法和传统的椭圆曲线Diffie-Hellman 密钥交换组合, 产生混合密钥交换)[20,22].Open quantum safe (OQS)[18]则提供了对于后量子算法以及TLS 1.2 和TLS 1.3 中的混合密钥交换的原型集成.

(3) 在实验室模拟网络环境[16,17]或实际的网络环境[14,19–21]中评估集成了后量子算法(密钥交换和认证) 后TLS 的性能.与传统公钥算法相比, 后量子密钥封装机制(key encapsulation mechanism, KEM) 和数字签名方案较慢的计算速度和超长的公钥/密文长度使得孤立地测量这些算法的性能很容易, 然而在现实的网络环境中准确地测量这些算法在协议上下文中的性能则是非常困难的[22].Braithwaite 和Langley 等[14,15,19–21]在TLS 中使用后量子密钥交换算法的实验非常现实, 但是实验选择使用的后量子算法有限, 没有涉及认证部分, 并且实验结果无法复制, 特别是无法准确反映时延和丢包率等网络属性单独对协议运行造成的影响.

现存这些工作主要集中在建立抗量子机密性的密钥交换.因为一个试图破解机密性的敌手可以监听通讯中加密的敏感数据并保存下来, 等待具备量子计算能力的时候追溯攻击存储的会话记录, 这对于必须长期保密的信息而言是一个很大的威胁.相比较而言, 认证只需要在建立连接的时候是安全的, 不需要在整个数据的生命周期中一直维持这种安全性.这意味着在大规模商用量子计算机出现之前, 身份认证是不易受到攻击的, 因此抗量子的认证不像抗量子的机密性那么迫切, 对后量子认证的研究相对较少.尽管如此, 后量子认证工作逻辑上更加复杂, 而且涉及到公钥认证的核心基础设施PKI, 成本更加高昂, 升级更加耗时, 涉及范围也更广.尤其是互联网的PKI 系统的所有信任都集中在根CA, 一旦该信任点出现故障,后果将是灾难性的.此外, 后量子签名算法较低的计算性能, 较大的公钥和签名, 以及由此产生的数字证书明显变大的事实, 肯定会影响TLS 握手时的性能, 损坏用户体验.因此, 研究后量子签名算法对于TLS的应用也是非常重要的[23], 非常有必要尽早尽快开展对后量子签名算法的研究并开始将PKI 系统向后量子安全迁移的工作.

本文探讨将TLS 1.3 协议向后量子安全迁移的方案, 介绍实现的方法, 比较在TLS1.3 中使用不同后量子密码套件的性能差异. 较之现有国内外进展, 本文的工作更加全面, 同时关注了后量子密钥交换和身份认证, 全面集成NIST 和中国密码算法设计竞赛[24,25]的后量子格基密钥封装算法和签名算法; 较之之前关于后量子TLS 算法的实验片面涉及密钥交换或身份认证, 我们的实验也更加详实, 全面评估了在TLS1.3 协议中同时使用后量子密钥交换和后量子认证在不同网络环境下的性能. 本文的主要工作包括以下4 个方面:

(1) 聚焦TLS 1.3, 探讨在TLS 1.3 中集成后量子格基密码算法的思想和方法, 给出了TLS 1.3 后量子迁移方案.通过对TLS 1.3 做必要修改, 将适合协议迁移的、标准化可能性大的格密码算法集成到TLS 1.3 中, 实现TLS 1.3 协议向后量子安全平滑过渡, 并且可以与标准协议兼容.这些方案使用了混合模式的密钥交换和混合模式的数字签名(身份认证).

(2) 实现了后量子安全的TLS 1.3 密码库.综合考虑代码架构, 实现上的安全性和使用上的通用性等因素, 我们原型化选定的格密码算法, 并将它们集成到Facebook 的TLS 1.3 实现库fizz 中.集成的算法包括了进入NIST 第二轮的后量子KEM 算法和签名算法以及中国密码算法设计竞赛第二轮优胜算法aigis-enc、aigis-sig、akcn-mlwe 和mulan.利用该库建立的加密隧道在握手阶段可以采用后量子安全的密钥交换算法和签名算法, 用于抵抗具有量子计算能力的敌手.

(3) 构建了一个测试TLS 协议在各种网络条件下性能的实验框架.该框架使用Linux 内核的网络栈能够精确独立地调整链路延迟和丢包率等特性, 允许我们在一台机器上模拟客户机-服务器进行网络实验, 精确量化在建立TLS 连接时因为丢包或者网络延迟产生的影响.

(4) 在一个经典的TLS 1.3 的应用场景下对修改后的fizz 进行大规模全面测试, 保证修改后产品的正确性和兼容性, 并检查各种格密码算法对TLS 握手性能产生的影响.测试结果表明, 尽管后量子算法会对TLS 1.3 的握手开销产生一定影响, 但是考虑到后量子算法微秒级的运行时间, 网络延迟隐藏了这些算法大部分计算性能上的差异, 但在高质量(较小网络延迟和较低丢包率) 的链路上, 算法性能是决定因素; 后量子算法的公钥/密文/签名大幅增加, 尤其是使用后量子算法生成的证书链长度增加较大, 但TCP 分段机制可以保证协议正常运行, 在丢包率较高的链路上, 传输报文少的算法能够体现带宽优势.实验结果也为不同网络条件下如何选择后量子算法提供指导,有助于后量子算法进一步标准化和TLS 1.3 标准向后量子安全迁移和平滑过渡.

2 相关工作

2.1 TLS1.3 协议

TLS 运行在TCP/IP 协议栈上, 提供端到端的身份认证, 并在它们之间建立加密的通信隧道, 提供通信数据的机密性、完整性和真实性保证. 它广泛用于保护web(HTTPS), 文件传输(FTP)、电子邮件(SMTP, POP) 和许多其它应用程序的流量和数据.2018 年8 月, IETF 正式发布了RFC8446[26], 宣布最新版TLS 协议TLS 1.3 标准的建立.TLS 1.3 比前一代TLS 1.2 有了显著改进, 包括消除了不安全或过时的特性、部分加密握手消息、消除往返减少握手延迟等:

(1) 性能提升.握手延迟是影响TLS 性能的最大因素.完整模式的TLS 1.3 只需要一次往返(round trip time, RTT) 就可以完成握手, 并且添加了对0-RTT 的支持.相比TLS 1.2, TLS 1.3 的握手时间减半, 性能得到了极大提升.

(2) 安全性提升.TLS 1.3 删除了之前版本中一些不安全的密码算法, 转而采用现代密码算法和操作模式, 进一步保障了安全性.另外, 在TLS 1.2 协议中握手消息全部是明文传输, TLS 1.3 协议对部分握手内容进行加密传输, 可以应对大规模的监控, 加强了隐私保护.

(3) 全方位简化协议逻辑.TLS 1.3 采用了和TLS 1.2 协议完全不同的设计理念, 一个典型的改变是密码组件(ciphersuites, 包括密钥交换方法、数字签名方案和对称密码方案) 的协商逻辑.TLS 1.2 使用整体密码组件的设计思想, 一次性协商所有使用的密码方法, TLS 1.3 则分别协商密码组件的每个部分.

TLS 1.3 协议逻辑方面的改变使得协商更加灵活, 每一个算法都使用没有内部结构的枚举值标识.如果要在协议中使用一个算法, 只需要让运行协议的双方都理解该算法标识符并将其映射到对应的算法处理逻辑即可.这为不改变TLS1.3 协议的语法、语义和同步而集成后量子算法提供了方便.图1 展示了TLS 1.3 完整1-RTT 握手过程, 该过程主要密包括密钥交换、发送服务器参数和认证三个部分.密钥交换用于选择TLS 协议版本和加密的算法, 协商算法所需的参数, 这些消息是明文传输; 发送服务器参数用于协商握手协议的其它通信参数, 例如是否需要认证客户端, 支持何种应用层协议等, 这些消息是密文传输; 认证用于对服务器进行认证(包括可选的客户端认证), 提供密钥确认和验证握手完整性, 这些消息加密传输.

图1 完整1-RTT 模式TLS1.3 握手协议Figure 1 Full 1-RTT TLS1.3 handshake

首先, 客户端生成用于密钥交换的临时公私钥对, 并向服务器发送ClientHello 消息, 该消息携带了随机数、客户端支持的协议版本、密码组件等重要信息和一些可能存在的扩展(extension).这些扩展包括: signature_algorithms, 用于指示支持的签名算法列表; supported_groups, 用于指示支持的椭圆曲线类型; key_share, 用于表示supported_groups 中每一个椭圆曲线的公钥信息等.

第二步, 服务器响应ClientHello 消息, 它计算自己的临时密钥对, 确定所需的加密参数, 产生包含服务器随机数和key_share 扩展的ServerHello 消息并将该消息发送给客户端.其中key_share 扩展包含了协商的椭圆曲线和服务器的公钥信息.此时, 通过组合ClientHello 和ServerHello 消息, 两个实体生成共享密钥, 此后的消息使用此密钥加密.

第三步, 服务器继续加密发送EncryptedExtension 消息、Certificate 消息和CertificateVerify 消息.其中, EncryptedExtensions 消息携带了无关密钥交换的其它扩展, Certificate 消息携带了服务器证书链;CertificateVerify 消息携带的是服务器对到当前为止的所有消息的签名, 该签名使用的私钥和签名算法同Certificate 消息携载的服务器证书公钥和签名算法对应.最后, 服务器发送Finished 消息来结束握手, 该消息包含了迄今为止交换的所有消息的消息认证码.

最后, 客户端用加密的Finished 消息回复ServerHello.如果服务器需要客户端认证, 客户端需要在Finished 消息之前发送Certificate 消息和CertificateVerify 消息.另外, 出于兼容性的目的, 双方可以在交互期间发送Change Cipher Spec 消息指示自此开始发送的消息都是加密过的.

RFC8446[26]完整说明了TLS 1.3 的握手流程和消息格式, 文献[27] 详细描述了TLS1.3 的计算逻辑和处理步骤.

2.2 PKI 和X.509 证书

身份认证确保信息和数据的来源是正确的, 即数据或消息来自它声称的信源.如果没有身份认证, 接收者收到的消息可能已经被恶意实体篡改, 发送者也可能将消息发送到错误一方, 从而导致机密信息的泄漏.大部分互联网安全通信协议需要在连接建立阶段使用数字证书进行单向或双向的身份认证.数字证书的核心是使用数字签名技术保证源数据(被签名数据) 的真实性和完整性, 杜绝数据在网络传输过程中被伪造篡改.数字证书的格式遵循ITU-T(国际电信联盟电信标准局)X.509 标准[28,29], 该标准规定了数字证书须遵循的格式以保证使用数字证书的系统间的互操作性.目前通用的X.509 版本是X.509 V3.符合X.509 标准的证书称为X.509 证书, 它通过数字签名技术绑定实体身份和公钥.数字通信中的许多协议的身份认证都是通过X.509 数字证书来进行的.X.509 数字证书经常使用PEM 或DER 格式编码, 它们的大小可以根据属性值、算法和其中的扩展高度可变.目前Internet 上最常见的证书大小在0.5–1.5 KB 之间.

数字证书的管理是通过公钥基础设施(public key infrastructure, PKI) 进行的.通过PKI 管理密钥和数字证书, 网络实体之间可以建立一个可信的通信环境.PKI 基础设施由多个部分组成, 证书颁发机构(certificate authority, CA) 是它的核心.CA 负责颁发数字证书, 绑定实体的身份和相关公钥.实体身份包含在证书的Subject 字段中, 实体的公钥与颁发者所用的签名算法存储在证书的subjectPublicKeyInfo字段.证书还包含有证书有效期(validity) 和用于指示其它一些功能的扩展(extension) 字段.CA 使用自己的私钥和指定的签名算法对证书进行签名, 并将签名添加到证书的签名字段中.

在X.509 PKI 的顶部有一些可信的CA, 它们用自己的私钥签署自己的证书, 称为根CA (root CA).根CA 可以直接颁发证书给服务器,更一般的情况是根CA 颁发证书给中间CA(intermediate CA,ICA).之后, 出于安全目的根CA 保持脱机状态, 由ICA 为服务器或其它ICA 颁发证书, 由此形成PKI 树形管理结构.由此过程创建的证书信任链可以包含任意多个证书, 但一般情况下该证书链由两到四个证书组成,并把CA 或ICA 签署给服务器的证书称为叶子证书.在会话建立阶段, 需要认证的实体需要将证书链发送给认证端, 认证端读取叶子证书获取其颁发机构(issuer) 的信息, 去系统查找该机构的证书; 如果该证书不是根证书就继续递归查找直到获取根证书; 如果根证书是可信任的, 则用根证书的公钥验证下一级证书的有效性并回溯进行, 直到通过叶子证书颁发者的公钥验证叶子证书的合法性.

2.3 格密码算法

由于目前使用的公钥密码体制会被量子计算机在多项式时间攻破, 为保护关键基础设施和敏感资产,需要寻找能够抵抗这种攻击的替代方案.这些研究的目标是确定无法在多项式时间内通过量子算法解决的NP 困难问题或子问题[30].其中, 为传统计算机部署一套新的公钥密码系统, 以抵御量子计算机攻击的方法因为可以更好地兼容现有的计算机体系结构和网络基础设施, 便于实现抗量子算法向现有应有和协议迁移过渡, 具备较强的竞争力.这种新的密码系统被称为后量子密码(post quantum cryptography).目前, 已经存在很多后量子密码算法, 业界认为以下五种类型的后量子算法是有希望的替代方案:

· 基于hash 的(hash-based cryptosystems)

· 基于编码的(code-based cryptosystems)

· 基于多变量的(multivariate cryptosystems)

· 基于同源的(supersingular isogeny cryptosystems)

· 基于格的(lattice-based cryptosystems)

其中, 基于格的密码算法简单并且可以高度并行化, 在安全性、公私钥尺寸、计算速度上达到了更好的平衡, 甚至可以在某些情况下表现出比传统基于数论构造的密码算法更快的计算速度[31].与其它几种后量子密码实现相比, 在相同的安全强度下, 它更适用于实际应用.尤其是近年来, 基于格的LWE (learning with errors) 问题和RLWE (ring-LWE) 问题的密码学构造发展迅速, 被认为是最有希望被标准化的技术路线之一.本文, 我们关注于将最具竞争力的格密码算法集成到TLS 1.3 使其向后量子安全迁移.

3 方案设计

将后量子密码算法集成到TLS 1.3 协议中有替换模式和混合模式两种方案.替换模式(drop-in replacement) 直接将协议中原有的传统公钥算法替换为后量子密码算法.混合模式(hybrid mode) 则保留协议中原有的传统公钥算法, 同时再集成一个后量子密码算法.混合模式的密钥交换分别使用传统密钥交换算法和后量子密钥交换算法, 然后将通过这些算法得到的信息组合在一起用于推演密钥; 混合模式的签名算法使用传统公钥算法产生一个签名, 再使用后量子签名算法产生一个签名, 验签时需要两个签名值都通过验证.

3.1 混合模式

替换模式的安全性完全依赖于替换进来的后量子密码算法.然而, 当用户对新兴的后量子密码假设缺乏信心时, 或者因为被强制要求遵循现行行业规范, 必须在使用后量子密码算法的同时使用传统公钥算法时, 替换模式不能工作.为了适应这种需求, 出现了混合模式.混合模式在保留协议原有公钥算法的同时加入了后量子密码算法, 并确保只要其中一个密码算法是安全的, 则组合算法就是安全的.对于混合模式密钥交换, 只要其中一个密钥交换算法未被攻破, 就可以保持混合密钥交换算法会话密钥的安全, 应用程序数据的机密性就能得到保证.对于混合模式数字签名, 只要在会话建立时其中一个数字签名方案未被攻破, 协议就可以提供安全认证.这种混合模式有利于实现后量子密码安全算法的渐进式部署, 使得现存协议及其应用向后量子安全的过渡更加平滑.当然, 混合模式也可能使协议的网络通信量更大, 迁移方案设计更复杂.对于混合模式的使用应该满足以下3 个需求:

(1) 混合模式方案的计算代价不能过于高昂.一般来说, 混合模式的计算性能取决于它所包含的单个密码算法的性能, 组合使用应该不会实质性地影响整个算法的性能.

(2) 低延迟.使用混合模式不应显著增加建立连接所需要的延迟.影响延迟的因素主要包括所用特定算法的计算性能和要传输的消息的大小.后量子算法的公钥/密文/签名大小从数百字节到几千字节不等, 而传统密码算法的对应值仅仅在一百字节上下, 我们必须考察权衡由此带来的改变是否满足TLS 在延迟方面的设计需求.

(3) 混合模式的使用不会增加额外的消息流, 改变算法原有的消息结构和处理逻辑.很难说明改变了协议消息结构和处理逻辑后的协议还是原有的协议.

尽管混合模式给我们带来了积极的因素, 但是也存在不少挑战.那么, 在使用混合模式的时候需要考虑以下几个关键问题:

(1) 混合模式组合的算法数量是固定的还是可变的？如果是固定的话, 那么应该是多少？这个问题上似乎没有共识, 一些互联网草案[9,10,12]将用于TLS 混合模式的密钥协商中使用的算法数目固定为两个, 另外一些草案[8,11]则认为混合模式可以具有更多的可变数目的算法.

(2) 如何协商混合模式使用的算法和参数？包括TLS 在内的很多协议的算法协商都采用以下步骤:一方按照其意愿向另一方发送其支持的算法列表, 另一方根据自己的支持算法列表从收到的列表中选择单个算法进行响应.如果找不到相互支持的算法, 则引发错误或协议重启事件.使用混合模式的时候一个主要的抉择是选择协商方法, 是单独协商混合模式中的每一个算法还是把混合模式的算法作为一个整体进行协商？

(3) 如何选择混合模式要组合的算法以及如何安全组合算法数据？在使用混合模式的时候只要其中一个算法是安全,则可以保证算法的组合是安全的.那么,应该如何确定要组合的算法以及如何组合来自多个算法的共享密钥,异或、级联还是通过密钥推导函数？在机密性方面,Even 和Goldreich探索了多个对称加密方案的组合[32].文献[33–35] 研究了组合多个公钥加密方案, Harnik 等人构建了“健壮组合器”(roust combiner), 可以在保留每个方案安全属性的同时将多个方案编译成为一个混合方案[34].最近, Giacon[36]和Bindel[37]等人探讨对密钥封装机制的组合.在数字签名方面, Bindel 等考察了数字签名方案的合并方法[38].特别需要注意的是在进行组合的时候,应该确保选择的算法具有匹配的安全级别.

对于第一个问题, 本文倾向于使用将混合模式的算法固定为2, 其中一个是经典算法, 一个是后量子算法.一方面, 这是最简洁最方便的处理方式; 另一方面, 在混合模式中使用多个算法是在对所有算法的安全性都没有足够信心时寄希望至少其中一个是安全的无奈之举.而在我们的方案中, 经典算法使用的是原有协议中的算法, 后量子算法使用的是经过NIST 评估或者是在中国密码算法竞赛获胜的后量子算法, 可以确信这种组合能够达到我们期望的安全性能.对于第二个问题, 我们倾向于将混合模式的算法作为一个整体进行协商.因为单独协商混合模式的每一个算法需要修改协议的消息格式和逻辑.对于一个改变了协议消息格式和交互逻辑的协议, 很难说它还是原协议或者保持原协议的特性.对于TLS 1.3 来说, 我们需要为混合模式定义新的算法标识符(NamedGroups 或SignatuerSchemes 中的条目), 并将新的算法标识符映射到混合模式的处理逻辑上.此时, 协议双方在协商的时候仍然可以使用原有的协议逻辑和消息格式,保证协议在语法、语义和同步上同原协议的一致性.在确定混合模式使用的算法固定为一个经典算法和一个后量子算法且作为整体来进行协商的时候, 我们倾向于选择安全级别匹配的算法进行组合, 然后按照经典密钥和后量子密钥的顺序对共享密钥进行级联操作.这不仅是因为这种操作方式简单且易于理解, 更是因为传统密码算法结构一般是对称的, 双方接发的消息具有相同的长度, 而后量子KEM 算法通常没有对称结构, 接收和发送的消息长度并不一样.先处理传统算法的做法方便我们对算法数据进行解析.这种设计方案简化了操作流程, 保证了协议的完整性和安全性, 同时避免了组合爆炸大量占用TLS 协议算法标识预留位的现象.

3.2 后量子密钥交换

在标准TLS 1.3 中, 密钥协商使用的是椭圆曲线上的Diffie-Hellman (ECDH) 算法.客户端发送ClientHello 请求, 并在该消息中携带supported_groups 扩展(extension) 来指示客户端支持的椭圆曲线类型; 同时, 客户端需要提供key_share 扩展发送每一个其所支持的椭圆曲线对应的公钥(椭圆曲线上的点).服务器收到ClientHello 消息得到了supported_groups 值并依据自己支持的椭圆曲线类型选择双方共同接受的椭圆曲线参数, 计算自己的公私钥, 提取ClientHello 消息key_Share 扩展中相应的值(公钥),计算共享密钥(此时为handshake_traffic_key), 并用ServerHello 消息回复客户端, 同时在ServerHello消息的key_share 扩展中存放其选择的椭圆曲线和相应的公钥.客户端在接收到ServerHello 消息之后根据服务器的公钥和自己的私钥计算共享密钥(此时为handshake_traffic_key).因为使用不同的盐值, 服务器和客户端生成的handshake_traffic_key 并不相同, 但彼此可以计算对方的handshake_traffic_key,保证通讯正常进行.

TLS 协议规范要求服务器先使用客户端的公钥和自己的私钥生成共享密钥, 再发送自己的公钥给客户端, 这为我们使用后量子KEM 算法提供可能.另外, TLS 1.3 中key_share 扩展的最大容量是216-1=65 535 字节, 这一容量可以支持大部分(混合模式)后量子KEM 算法的消息, 但是考虑到client的key_share 可以同时包含多个算法和算法公钥, 我们需要关注这一点, 确保TLS 的上下文配置不会导致key_share 超出该值的限制.

由于标准TLS 协议的密钥交换运行过程采用了对称的DH 算法, 客户端和服务器的消息结构、计算逻辑和处理步骤完全一致, 作用对等, 因此密钥交换算法无需标识身份.但NIST 和中国密码算法设计竞赛规定可用于密钥交换的是密钥封装算法, 它具有不同于DH 密钥交换的消息结构和处理逻辑.在协议的实现中必须注意到这种变化.为了在TLS 1.3 中可以使用后量子密钥交换算法或者混合模式密钥交换算法, 首先需要扩展NamedGroup 中定义的椭圆曲线枚举值, 将它们伪装成为一个新的椭圆曲线, 并将其映射到对应的执行逻辑和处理流程.

混合模式要在协议双方协商出两个密钥交换算法, 一个是传统的ECDH 算法, 一个是后量子KEM算法.如3.1 节所述, 我们是把混合模式的两个算法作为一个整体进行协商.但是使用这种协商方式可能会存在组合爆炸的情况, 也就是说传统密码和后量子密码的组合形式太多, 增加了双方在密钥交换过程的处理负担, 缺乏抽象化和泛化能力, 也增加了实现部署的工作量.考虑到TLS 1.3 标准中, 在握手中进行密钥交换可供选择的椭圆曲线数量是有限的, 而且不同密钥交换方法可提供的安全级别也并不一样, 我们按照安全级别匹配经典算法和后量子算法, 不会产生组合大爆炸的问题.此外, 我们的方案设计将混合模式的每一种组合都伪装成为一个新的椭圆曲线进行处理, 将算法的处理细节限制在crypto 层, 保证TLS 1.3 协议本身的逻辑没有改变.

3.3 后量子认证

在TLS 协议中, 密钥交换用来生成对称加密算法的共享密钥以建立机密性, 数字签名用于身份认证,这里主要涉及到两个扩展和一个消息.扩展signature_algorithms_cert 用来告知对方自己可以支持的证书签名方案; 扩展signature_algorithms 用来告知对方自己可以支持的对协议数据进行签名的方案.这两个扩展都是算法标识符列表.如果没有signature_algorithms_cert 扩展, signature_algorithms 扩展也可以用于实现signature_algorithms_cert 的指示功能.加密传输的消息CertificateVerify 则携带了对当前transcript 数据的签名.

如同对密钥交换混合模式的讨论, 后量子混合签名算法仍然按照单个签名算法进行处理, 其包含的每一个算法都应该作用于要处理的消息, 公钥是单个算法公钥的级联, 签名是单个算法签名的级联.在集成后量子签名算法的时候我们需要在SignatureScheme 中添加后量子签名算法或者其混合模式的枚举值,并将该值映射到对应的处理过程.证书链的接收者应该按照TLS 1.3 协议规范, 在signature_algorithms或signature_algorithms_cert 列表中加入该枚举值以支持新的算法.

因为TLS 协议中需要认证的一方的公钥通常是通过X.509 证书来传递, 另外一个和签名算法密切相关的是识别、解析和处理X.509 证书.在TLS 1.3 中, X.509 证书或证书链的最大默认值为224-1 字节,签名大小限制为216-1 字节.这些长度允许我们在TLS 1.3 协议中传输超长的后量子证书和签名.但是大多数后量子签名方案的公钥和签名大小为10–200 KB, 这比今天典型的0.5 KB 左右的密钥和签名长度要大得多, 就造成了传输证书和处理证书的巨大开销.这些开销包括消息本身规模造成的传播时延、传输时延, 处理时延和IP 分片造成的包含少量数据的MTU 带来的开销. 另外, 为了使用后量子签名算法, 新的算法OID(object identifier, 对象标识符又称为物联网域名) 需要定义, 至少在协议通讯方之间达成共识.X.509 证书中使用算法OID 标识使用的签名算法, 通过对X.509 算法OID 进行扩充, 定义新的算法标识符, 将它们对应于后量子签名方案参数和结构, 可以在X.509 中添加对新的后量子签名方案的支持.

尽管TLS 1.3 标准规定Certificate 消息可以传输实体对应与不同算法的多个证书, 也即通过两个证书链来传输混合签名算法的公钥和签名.但这种处理方式需要大量时间开销检查证书列表以匹配混合模式签名算法, 一种更简单的方法是让一个X.509 证书包含多个算法的公钥和多个算法的签名.通过为每一个要使用的混合算法添加新的OID, 然后向上映射到X.509 证书的生成和管理, 添加PKI 对新的混合签名方案的支持并用于TLS 身份认证.一个完全遵循X.509 证书数据结构和编码规范的后量子证书如图2 所示, 该证书使用级联的方法容纳混合模式后量子签名方案的公钥和签名, 并需要在证书使用者之间就后量子签名方案或者其混合模式的OID 之间达成共识.

图2 后量子证书Figure 2 Post quantum certificate

4 实现和实验设置

4.1 TLS 1.3 后量子集成实现

我们的目标聚焦在TLS 1.3, 从安全性、性能、可维护、兼容性和开放等原则以及模块化设计的需要考虑, 我们选择改造Facebook 的TLS 1.3 协议实现库fizz 进行后量子安全迁移.因为目前普遍认为量子计算机对对称密码的影响有限, 迁移方案主要体现在握手过程的密钥交换和认证阶段.需要注意的是fizz仅仅是TLS 1.3 协议的实现, 它并不涉及密码算法和证书处理的细节, 对密码算法和证书的处理依赖于其它算法库, 如OpenSSL 和libsodium 等.为在fizz 中增加对NIST 后量子算法的支持, 我们使用了Open Quantum Safe 项目提供的开源库liboqs, 该库已经提供了使用后量子密码算法的统一接口; 为在fizz 中增加对中国密码算法设计竞赛算法的支持, 我们首先需要将相应代码原型化, 然后在fizz 中使用统一接口进行调用.另外, 因为要生成、解析和处理X.509 证书, 我们需要在OpenSSL 库中加入(混合) 后量子签名算法, 并将其映射到对X.509 证书的处理.以上的操作均被视为是在crypto 层完成, 没有涉及TLS 协议本身.下面简述设计方案的具体实现.

密钥交换. TLS 1.3 密钥交换没有提供KEM 风格的接口.标准TLS 1.3 的密钥交换使用的是基于椭圆曲线上的Diffie-Hellman 算法, 客户端和服务器在握手阶段密钥生成、公钥交换和共享秘密的计算处理完全一样.但是NIST 提供的可用于密钥交换的后量子KEM 算法和DH 密钥交换完全不同, 客户端和服务器具有不同的处理逻辑和消息结构.为了让TLS 1.3 可以处理这种接口, 需要将KEM 伪装成为DH 椭圆曲线上的密钥交换, 适配标准TLS 1.3 的处理逻辑和消息结构.Fizz 中用KeyExchange 类抽象了密钥交换算法, 为了能够使用后量子KEM, 需要在该类中增加bool IsServer() 接口, 用于标记在KEM形式密钥协商过程中参与者的身份(客户端还是服务器), 使得计算过程差异化.而传统的DH 密钥交换可以忽略这个过程(函数体为空).

统一了不同密钥交换算法的接口, 我们就可以将后量子密钥算法视作是对crypto 层函数的调用, 同样的接口根据密码算法的来源可以有不同的实现.从KeyExchange 派生出的HybridKeyExchange 类用于实现混合模式密钥交换, 利用组合设计模式(composition design pattern), 该类一方面可以重用原有代码,简化实现, 另一方面可以隐藏混合方案的实现细节, 让混合方案和非混合方案, 经典算法和后量子KEM算法都可以具有相同的调用接口.这种抽象、继承、派生和组合的设计与实现把所有关于算法的处理逻辑都放置在crypto 层, SSL 层仅仅需要扩展NamedGroup 并建立NamedGroup 枚举值和类实体之间的映射关系即可.此时, 在TLS 1.3 中加入后量子KEM 算法及其混合模式时, 只是考虑如何合适地组合经典算法和后量子算法生成混合方案, 不会涉及到复杂的TLS 执行逻辑, 没有改变协议的语法、语义和同步,也不会改变协议复杂并脆弱的状态机而影响到协议的安全.这种实现方式也让我们在选择后量子算法的时候具有更大的自由度和灵活性, 代码的可维护性、可扩展性和灵活性也更强.图3 展示了密钥协商类图结构.其中OpenSSLKeyExchange 类实现了标准TLS1.3 协议中密钥交换算法, 即secp256r1、secp384r1和secpr521 椭圆曲线群上的DH 密钥交换, 调用的是OpenSSL 中的代码; X25519KeyExchange 类实现的是x25519 椭圆曲线群上的DH 密钥交换, 调用的是libsodium 中的代码; AKCNKeyExchange 类提供了对中国密码算法设计竞赛中aigis-enc 和akcn-mlwe 的实现.HybridKeyExchange 是透明处理混合模式密钥协商算法的类, 该类采用设计模式中的“composition pattern” 隐藏混合模式算法内部的实现结构,可以重用KeyExchange 其它派生类的代码.

图3 组合模式的扩展密钥交换类图Figure 3 Extended key exchange class diagram of composite pattern

认证. 与使用继承和多态机制处理密钥交换算法的方式不同, 我们使用泛化来处理不同签名方案的不同处理逻辑.为了在TLS 1.3 中增加(混合) 后量子签名算法, 我们需要扩展SignatureScheme, 增加(混合) 后量子签名算法的枚举值, 并在SSL 层中通过模板偏特化(partial specialize) 和类型萃取(trait) 技术, 建立不同签名算法和处理逻辑之间的映射关系.需要注意的是, 如2.2 节所述, TLS 的认证环节包含了证书识别和处理, 而fizz 中的证书识别和处理是通过OpenSSL 进行的, 我们需要修改标准OpenSSL,在其中为每一个要使用的(混合) 后量子签名算法增加可以在PKI 中唯一标识该算法的OID, 确保该对象标识符能够被PKI 和TLS 通信双方理解, 然后添加算法到OpenSSL 的通用信封公钥对象(general envelop public key, EVP_PKEY), 并向上映射到X.509 证书的解析和管理.尽管过程非常复杂繁琐, 在OpenSSL 中实现一个新的签名方案并不困难, 处理流程主要集中在实现OpenSSL 高层密码函数抽象接口EVP (high level cryptographic functions) 上.

如3.1 节讨论那样, 使用混合模式将TLS 1.3 向后量子安全迁移, 可能会存在组合爆炸的情况, 也就是说传统密码算法和后量子密码算法的组合形式太多, 增加了实现部署的工作量.为避免这种现象, 也从安全实现的角度考虑, 我们将安全强度匹配的经典算法和后量子算法进行组合.具体而言, 混合模式将安全强度为I 和II 的后量子算法和椭圆曲线secp256r1 上的经典算法绑定, 安全强度为III 和IV 的后量子算法和椭圆曲线secp384r1 的经典算法绑定, 安全强度为V 的后量子算法和椭圆曲线secp521r1 上的算法绑定.表1 和表2 展示的是我们网络仿真实验中使用的混合算法的组合方案和混合方案的消息长度, 这些后量子算法包括KEM 算法kyber[39]、saber[40]和ntru[41], 签名算法dilithium[42]和falcon[43].其中有关长度的列中每一项的单位是字节, + 前面代表经典方案的长度, + 后面代表后量子方案的长度.表1 中msg1 是客户端发送给服务器端的消息, 其包含了经典密钥交换算法的公钥和后量子KEM 算法的公钥; msg2 是服务器返回给客户端的消息, 其包含了经典密钥交换算法的公钥和后量子KEM 算法的密文.所谓经典算法是指对应椭圆曲线上的DH 算法.表2 中没有包含私钥信息, 因为签名算法的私钥无需传输, 不会产生运载负荷.其中经典算法是指对应椭圆曲线上的ECDSA 算法.同前面的约定一样, + 前面代表经典方案的长度, + 后面代表后量子方案的长度.为了描述方便, 我们使用算法的简称, 如用p256代表椭圆曲线secp256r1, 用ntru 算法最后三个数字代表其全称, 省去中间算法参数的描述, 如用ntru509替代ntruhps2048509.在涉及混合模式算法名称时, 我们经常省去经典算法的名字, 如用kyber512 代表p256_kyber512, 用falcon1024 代表p521_falcon1024.需要说明的是: 第一, falcon 算法的签名长度是可变的, 表中显示的是平均长度; 第二, 后量子算法尤其是后量子签名算法运行并不稳定, 运行时间经常会有较大的变化.参考4 和表5 中相关算法运行时间的标准差数值, 后量子算法运行时间的标准差都比较大,甚至可以达到几十或者几百; 第三, 通过数字证书传输的签名和公钥通常使用DER 编码或BASE64 编码, 长度上会有增加, 表中的数据并没有考虑因为这些额外的处理细节而发生的改变.

表1 混合模式密钥交换算法消息长度Table 1 Message length of hybrid-mode key exchange scheme

表2 混合模式签名算法消息长度Table 2 Message length of hybrid-mode signature scheme

更多细节和处理请参考方案的代码实现https://github.com/gudengxia/PQTLS1_3.git.

4.2 实验设置

为了在实验中控制网络特性, 依赖于Linux 内核中流量控制(traffic control, TC) 和网络虚拟化命名空间(net namespace, netns), 我们开发实现了一个网络仿真框架.

Linux 内核提供了创建网络命名空间的能力, 这些命名空间相当于内核网络堆栈的一个副本.每个命名空间都有自己的路由、网络地址、防火墙规则、端口和网络设备, 这意味着使用netns 创建的网络空间相互独立.因此, 使用netns 网络空间可以在本地虚拟化出多个独立网络, 使得我们可以在单个系统上模拟复杂的协议运行环境.

我们使用虚拟以太网设备(virtual device, veth-pair)连接两个不同命名空间.内核网络仿真(netem)模块可以控制这些虚拟以太网设备上的数据传输, 指示内核对通过以太网设备的数据包进行分类、管理、检测拥塞和处理拥塞, 控制从以太网设备发出的数据包的网络延迟和丢包率等.为了给链路一个xms 的往返时间, netem 指示内核对网络虚拟设备(veth-pair) 的每个传出包应用x/2 ms 的延迟, 为了给链路一个期望的丢包率y%, netem 指示内核以y% 的概率丢弃链路两端设备上的传出包.使用netns 建立模拟网络环境并利用netem 控制网络特性, 我们能够隔离出不同网络特性对TLS 1.3 的握手性能产生的影响.

实验中, 我们创建了三个网络命名空间, 并使用veth 连接它们, 第一个网络命名空间ns1 表示客户机所在网络, 第二个命名空间ns2 表示服务器所在网络, 第三个命名空间ns-router 表示连接客户端和服务器的路由网络.客户端网络ns1 通过虚拟网卡veth1 连接到路由网络ns-router 的虚拟网络接口veth1-router, 服务器网络ns2 通过虚拟网卡veth2 连接到路由网络ns-router 的虚拟网络接口veth2-router.通过开启linux 内核ip 转发功能, 处于不同网络的客户端和服务器实现互联.图4 显示了我们实验使用的模拟网络环境.

图4 实验模拟网络Figure 4 Simulated network in experiments

我们通过网络延迟来模拟客户端距离服务器的物理距离和经过的路由器和网关数量, 低延迟代表距离较近, 数据包传输需要经过的网关或路由器较少, 高延迟代表距离较远, 数据包传输需要经过的网关或路由器较多.丢包率用来模拟网络质量, 低丢包率用来模拟高质量的有线以太网, 高丢包率用来模拟低质量的网络或者高负载的wifi 网络.对于每组网络延迟, 我们考察丢包率在0% 到10%(概率独立地应用于每个分组) 之间变化时对TLS 1.3 握手的影响.根据Mozilla 在2019 年9 月和10 月对Firefox (nightly 71) 中丢弃的数据包进行的监测显示, 在台式计算机上, 数据包丢失率高于5% 的情况并不多见: 例如,在WEBRTC_AUDIO_QUALITY_OUTBOUND_PACKETLOSS_RATE 的分布中, 所收集的3550万个样本中, 67% 的数据包丢失率低于0.1%, 89% 的数据包丢失率小于1%, 95% 的数据包丢失率小于4.3%, 97% 的数据包丢失率小于20%[22,24].

在服务器的命名空间, 我们运行修改版本的fizz 服务器, 它可以依次处理来自客户端的网络请求.在客户端命名空间中, 我们批量运行fizz 修改版本的客户端, 记录每一次握手所需时间并在握手完成后立即关闭, 开始运行下一次握手.对于延迟和丢包率的每一对组合, 实验运行6000 次测试.更详细的实验测试平台的设置和实验代码可以参考https://github.com/gudengxia/TestPlatform.git.这些实验是在一台安装Linux 操作系统(Ubuntu Server 20.04.1 LTS) 的台式电脑上进行的, 该电脑拥有一个4 核CPU, 其型号为Intel(R) Core(TM) i5-7400T CPU @ 2.40 GHz, 拥有8 GB 内存.

5 实验结果与分析

我们的网络仿真实验仅测试TLS 1.3 1-RTT 模式握手所需的时间.大部分情况下后量子密码算法性能差距在几十微秒, 对比网络传播时延和传输时延, 建立TLS 连接时因为密码算法的处理时延造成的性能差距并不明显.一般情况下, 网络上一个数据包的往返时间(round trip time, RTT) 大概在几毫秒甚至于几百毫秒, 建立TLS 握手则需要更大的开销, 可以预见后量子算法性能上的差距对TLS 握手造成的影响有限, 网络延迟越大, 这种差异的可见性(被感知的可能性) 越小.

在我们的大规模实验基本结束并开始撰写本文之际, NIST 的评估过程已经从第二轮转向第三轮, 而在第三轮中选择的5 种格基后量子算法都在我们的测试之列.我们重点介绍了对这些算法的评估和测试,尽管使用的是第二轮的代码, 我们也正在逐步将我们的代码向NIST 第三轮的算法迁移.实验中, 我们假设一个经典的TLS 应用场景, 身份认证是单向的, 也即服务器需要传输X.509 证书链向客户端认证身份, 客户端保持匿名, 不需要向服务器传输证书链认证身份.所有TLS 1.3 握手都使用完整1-RTT 模式的握手, 并且客户端发送的supported_groups 中只包含一个混合密钥交换算法和其公钥, 以尽可能减少ClientHello 消息的长度, 隔离后量子算法产生报文长度差异对握手连接带来的影响.在实验中, 我们使用的证书链长度为2, root CA 使用混合后量子签名算法生成自签证书(CA 证书), 并负责签署ICA 的证书;ICA 负责签署服务器的证书.服务器需要传输包含了ICA 的证书和自身证书的证书链到客户端, 客户端使用CA 的公钥验证ICA 的证书, 使用ICA 的公钥认证服务器的证书.因为证书的私钥和CA 对证书的签名在线下进行, 所以, 在我们的实验场景中, TLS 握手需要一次密钥交换、一次签名和三次验签.另外,我们按照安全级别绑定使用的混合后量子密钥交换算法和混合后量子签名算法.对于NIST Level 1 的每一个后量子密钥交换算法拥有两种选择dilithium2 和falcon512, 而对于Level 3 和Level 5 的后量子密钥交换算法只能有一种选择.我们测试了每一种组合其发送的ClientHello 和ServerHello 报文的大小.尽管在TLS 1.3 中集成格基后量子算法大大增加了握手过程需要传输的数据量, 但是TCP/IP 协议的分段机制可以保证协议的正常运行.表3 描述了在TLS 1.3 中使用NIST 第2 轮密码算法的混合模式产生的ClientHello 报文和ServerHello+ 报文的长度, 长度的单位是字节.ServerHello+ 表示了ServerHello消息和随其发送的EncrytedExtentions、CertificateRequest、Certificate、CertificateCerify 和Finished等消息.因为在实验中, 对于确定安全级别的后量子算法, 其绑定的经典算法已经确定, 所以表中用后量子算法的名字简称混合模式的名字.注意这些长度并不是确定值, 它们会随着TLS 链接上下文参数以及证书的不同而高度可变, 实验尽可能采用相同的配置参数和极简的扩展结构抑制这种变化.

5.1 密钥交换

总体而言, 在NIST 的三种KEM 算法中, kyber 和saber 具有相似的时间性能, 但是kyber 公钥较大, saber 公钥较短; ntru 算法具有较短的公钥和密文, 但是其性能较之其它两种算法相差较大.表4 是关于NIST 第二轮密钥封装算法消息长度和算法单独运行时性能相关信息的描述, 其中长度相关数据的单位是字节, mean 是算法的平均运行时间, 单位是μs, St.Dev. 是运行时间的标准差.从时间上比较, 在相同安全级别下saber 算法的运行效率最高, kyber 次之, 但这种差距一般在十个微秒左右, 相较于TLS 握手的整体开销并不明显; ntru 算法的效率同以上两者差距很大, 运行也最不稳定, 尤其是密钥生成算法, 其耗时是前两者的几十倍.从带宽角度考虑, ntru 最优, saber 次之, kyber 最差.考虑到以太网中MTU 值一般为1500 字节, 也即TCP 分段可以容纳的数据为1460 字节, 不同后量子密钥封装算法公钥之间的差值最多只会导致ClientHello 消息增加一个TCP 报文(IP 包).表3 中的数据也表明, 除了安全级别Level II 中p384_kyber768 和p384_dilithium4 组合, 以及安全级别Level V 中p521_kyber1024 和p521_falcon1024 组合, TLS 1.3 在使用混合模式的密钥交换算法时运载它们产生的ClientHello 消息只需要1 个TCP 报文, 运载p384_kyber768 和521_kyber1024 的公钥则需要一个额外的TCP 报文.三个算法密文长度的差距也在1460 字节范围内, 至多会产生一个额外的报文, 而且ServerHello+ 消息的容量主要来自证书链, 密文长度的差距带来实质性的影响并不大, 在我们的实验中也没有出现因为密文长度的差别而导致产生额外TCP 报文的现象.根据这种分析, 我们认为密钥交换算法公钥和密文长度给TLS 1.3 的握手性能带来的影响极小, 相应的实验结果也证实了这种推论, 因此实验主要关注在TLS 1.3 中使用后量子密钥封装算法计算性能对握手造成的影响.

表3 ClientHello 和ServerHello+ 消息长度Table 3 Message length of clientHello and serverHello

表4 NIST 第二轮密钥封装算法单独运行的性能Table 4 Performace of KEM scheme moved on to NIST round 2 running separately

图5 是我们在TLS1.3 协议中使用相同签名算法和不同密钥交换算法时握手时间随丢包率上升而产生的变化曲线.每一幅子图中横坐标代表丢包率, 纵坐标是握手时间, 单位是ns.子图文字中的RTT 值是实验所用模拟网络的round trip time, Signature 说明的是握手所使用的作为基线的后量子签名算法.图中算法使用的混合模式的简称.对每一组算法的每一个丢包率, 我们运行6000 次握手并计算其平均运行时间, 曲线代表平均握手时间随丢包率的变化情况.

为了比较 NIST Level 1 的后量子混合密钥交换算法, 我们分别使用 p256_dilithium2 和p256_falcon512 作为基线. 图5(a) 是使用p256_falcon512 签名算法, RTT 为5.5 ms 时, 使用三种不同密钥交换算法握手所需平均时间随丢包率的变化; 图5(b) 是使用p256_dilithium2 签名算法, RTT为30 ms 时, 使用三种不同密钥交换算法握手所需平均时间随丢包率的变化. 图5(c) 和图5(d) 分别是比较NIST Level 3 和NIST Level 5 的混合密钥交换算法时平均握手时间随丢包率的变化. 其中图5(c) 中的实验使用p384_dilithium4 作为基线; 图5(d) 中的实验使用p521_falcon1024 作为基线. 这两组实验使用的RTT 值都为1 ms. 使用不同基线的实验结果表明, (混合模式)kyber 和saber 算法在TLS 握手时间开销上几乎不可区分, 在延迟较小和丢包率较低的链路上, 仍然可以清晰看到以上两者体现出来的对ntru 的优势, 这和单个算法的评测一致. 也就是说, 在高质量(具有较小延迟和较低丢包率) 链路上, 公钥和密文大小对握手完成时间影响极小, 影响握手性能的主要是密码算法的计算时间. 随着网络延迟的增加和丢包率的上升, TLS 的握手开销会逐渐增大, TLS 握手几十毫秒甚至更多的开销使得后量子算法几十微秒的差距变得不是那么明显, 网络延迟会完全隐藏算法性能的差异.

图5 TLS1.3 中使用不同后量子密钥交换算法握手性能随丢包率的变化Figure 5 Performances of handshake in TLS1.3 using different PQ key exchange algorithms associated with packet loss

5.2 认证

如本节开始所述, 在我们实验场景中证书链的结构是CA→ICA→Server, 为了认证证书需要二次验签操作; 服务器生成CertificateVerify 消息需要使用与证书中公钥相对应的私钥对整个握手进行签名, 客户端需要使用服务器证书的公钥验证该签名.因此在整个握手阶段需要进行一次签名和三次验签操作.因为不同参数dilithium 提供的安全级别为I、II 和III, 不同参数falcon 提供的安全级别为I 和V, 考虑到需要在相同安全级别下比较算法的性能, 实验中对签名算法的比较只能集中在Level 1 安全级别的算法p256_dilithium2 和p256_falcon512.表5 是关于NIST 第二轮签名算法消息长度和运行性能相关信息,其中关于长度相关数据的单位是字节, 时间相关数据的单位是μs, 需要注意的是falcon512 的签名长度并不固定, 表中列出的是平均长度.表中数据可以看出, 尽管falcon512 在带宽方面具有较大的优势, 可以使得其在TLS 握手中可以少传递2–3 个报文(依赖于证书的大小和证书链的长度).但是其计算性能同dilithium2 有相当差距, 可以预见在丢包率较低的链路上, 其带宽优势并不能充分发挥.实验结果也同预先分析相符.

表5 NIST 第二轮签名算法单独运行的性能Table 5 Performace of signature scheme moved on to NIST round 2 running separately

和密钥交换类似, 网络延迟会隐藏签名算法性能上的差距.但在延迟较小的链路上, p256_dilithium2的计算性能优势能够得到体现, 如图6 所示. 图中横坐标代表丢包率, 纵坐标是握手时间, 单位是ns, 图中文字的RTT 值是实验链路中round trip time,KEX 说明的是使用的作为基线的后量子密钥封装算法.图中可以看出,随着丢包率的增加,p256_falcon512 的性能劣势会慢慢消减,甚至体现出对p256_dilithium2的优势.参考表3 中的数据,使用dilithium2 的握手需要8 个报文传递其ServerHello 消息,使用falcon512的握手仅需要5 个报文传递其ServerHello 消息, 少传递的三个报文会使其随着丢包率的增长掩盖其计算性能上劣势. 一方面, 因为要传递的报文较少, 需要重传的报文相应减少, 会减少TLS 握手时的传播时延; 另一方面, 随着丢包率的增加握手开销也会增长, 从而淹没了算法计算性能上的差异.图6(a) 具体展示了使用ntru509 作为基线的两种不同签名算法TLS 平均握手时间随丢包率的变化.在10% 丢包率左右, dilithium2 相对于falcon512 的性能优势消失殆尽. 此后, 随着丢包率的上升, falcon512 的带宽优势越来越明显.图6(b) 是握手时间的差值随丢包率的变化.该图清晰表明了使用p256_dilithium2 较使用p256_falcon512 的优势在10% 丢包率左右反转的现象.数据的抖动一方面是因为丢包是概率事件, 另一方面是因为后量子算法尤其是后量子签名算法运行并不稳定, 经常具有较大的方差(标准差).尽管如此,该实验结果表明了在丢包率较高的链路上, 具有较短公钥/签名的falcon512 算法拥有优势.

图6 TLS1.3 中使用不同签名算法握手性能随丢包率的变化Figure 6 Handshake of performances in TLS1.3 using different PQ signature algorithms associated with packet loss

另一种分析方法是分析握手时间的跃迁.一般情况下, 一个算法的运行时间虽然会有变化, 但如同自然界的大部分现象, 这种变化会比较平缓.基于这种认识, 可以认为导致握手时间发生突然跃迁的事件极有可能是丢包.通过将相同丢包率下的6000 次握手时间排序, 我们选择几个不同丢包率下发生跃迁的片段查看TLS 握手时间的变化.图7 的两张子图分别是我们在使用p256_kyber512 作为密钥交换算法时,在RTT 为2.5 ms 的链路上使用不同签名算法握手时间的跃迁图.图中纵坐标是握手时间, 单位是ns.图7(a) 是丢包率在10% 时发生在第5760–5800 个数据之间的片段, 图7(b) 是丢包率在6% 时发生在第5900–5995 个数据之间的片段.图中可以看出, dilithium2 比falcon512 更早发生跃迁, 因为它需要传递更多的报文; 随着丢包率的增长, 跃迁发生的也越早.实验结果符合我们的推理.

图7 TLS1.3 中使用不同签名算法平均握手时间的跃迁Figure 7 Transition of average handshake time for different signature algorithms in TLS1.3

5.3 国产后量子密码算法

除了集成和测试NIST 第二轮中的格基密码算法, 我们也原型化了中国密码算法设计竞赛获奖的后量子KME 算法aigis-enc 和akcn-mlwe、后量子签名算法aigis-sig 和mulan, 并集成到fizz 中在TLS1.3握手时使用它们或者它们的混合模式, 测试它们的性能并和其NIST 等价算法进行了比较.为了描述方便, 我们仍然只使用后量子算法的名称代表其混合模式, 并且简称akcn-mlwe 为akcn, 有时也把aigis-enc和aigis-sig 统称为aigis.这些算法中, akcn 对比kyber768, mulan 对比dilithium3, 使用的是C 语言版本; aigis-enc 对比kyber768-90s, aigis-sig 对比dilithium3, 使用的是avx2 代码.算法的实际性能评测如表6、表7 和表8 所示, 表中关于长度相关数据的单位是字节, 时间相关数据的单位是μs.表6 是密钥封装算法的评测对比, 比较可以得出中国密码算法设计竞赛的akcn 在性能比kyber768 的参考实现略有提升, aigis-enc 比较kyber768-90s 的avx2 实现性能些许下降; 国产的两种后量子KEM 算法具有较短的公钥和密文.表7 是签名算法的评测对比, 比较可以得出mulan 性能优于dilithium3 的参考实现, aigis-sig的性能优于dilithium3 的avx2 实现.表中数据表明所有的差距都在数十微秒之间, 可以预见计算性能对TLS 握手产生的影响几乎可以忽略.但KEM 算法akcn 和aigis-enc 的公钥长度的减少恰好可以使TLS的ClientHello 消息少产生一个TCP 报文(IP 包), mulan 和aigis-sig 较短的公钥/签名使ServerHello+消息少产生一个TCP 报文, 在握手过程共节省2 个报文.具体TLS 消息长度参考表8 中的数据.

表6 国产后量子KEM 算法和对应NIST 后量子KEM 算法性能比较Table 6 Comparison of performance between Chinese KEM and referential NIST’s KEM

表7 国产后量子签名算法和对应NIST 后量子签名算法性能比较Table 7 Comparison of performance between Chinese signature and referential NIST’s signature

表8 TLS1.3 握手阶段报文长度Table 8 Length of packets in TLS1.3’s handshake

实测性能如图8 所示, 不管是 p384_akcn-mlwe 和 p256_mulan 的组合对比 p384_kyber768和 p256_dilithium3 的 (C 参考实现) 组合, 还是 p384_aigis-enc 和 p256_aigis-sig 的组合对比p384_kyber768-90s 和p256_dilithium3 的(avx2 实现) 组合都表现出非常接近的性能.然而, 随着丢包率的上升,中国密码算法竞赛的算法由于较小的带宽产生的优势会有所体现.其中,图8(a)是aigis-enc 和aigis-sig 的组合比较kyber768-90s 和dilithium3 的组合,图8(b)是akcn 和mulan 的组合比较kyber768和dilithium3 的组合.因为在计算性能上和NIST 的算法没有明显差距而拥有带宽优势, 中国密码算法竞赛的算法更加适于实际应用.

图8 国产后量子密码算法在TLS1.3 中的性能Figure 8 Performances of Chinese post quantum algorithms in TLS1.3

6 总结

量子算法可以攻破目前使用的公钥密码体制, 对我们的网络安全构成重大威胁.为保护关键基础设施和机密资产, 必须尽快开展将后量子安全等价产品取代现有密码系统的工作, 公钥密码替换的任务更加紧迫.本文我们分析了NIST 后量子密码项目和中国密码算法设计竞赛的格基后量子密码算法, 并从性能、安全级别和公钥/密文/签名大小等方面对它们进行了比较; 探讨了将这些算法集成到TLS 1.3 的可行性和方法, 介绍了将后量子密钥封装和签名算法及其混合模式添加到TLS 1.3 时需要对标准草案做出的必要修改, 并在Facebook 的fizz 库上实现了后量子安全的TLS 1.3 协议, 能够使其与当今的互联网基础设施共存.此外, 我们还构建了一个测试TLS 协议在各种网络条件下性能的实验框架, 可以在一台机器上模拟客户机-服务器网络实验, 精确量化仅仅由网络延迟或路由上的丢包对建立TLS 连接产生的影响.测试结果表明, TCP/IP 的分段机制可以保证具有超长报文的后量子TLS 1.3 协议正常运行; 网络延迟是影响握手时间的主要因素, 它隐藏了大部分后量子算法计算性能上的差异; 对于密钥交换算法, 公钥和密文长度的差异并没有给在TLS 中使用它们带来实质性的影响; 在高质量的链路上, dilithium 签名算法因为计算性能的优势有具有较强的竞争力, 而在丢包率较大的链路上, falcon 会体现出它的带宽优势.我们的实验结果也为在不同网络条件下对后量子算法的使用提供指导, 有助于后量子算法进一步标准化和TLS 1.3向后量子发展和迁移.

我们将继续扩展我们的实验, 建模不同条件下在TLS 1.3 中使用后量子密码算法带来的影响.同时,我们正在将我们的后量子TLS 1.3 库从NIST 第二轮的代码向NIST 第三轮的代码进行迁移, 并在我们的模拟网络架构下测试升级后各种算法组合的实际运行性能.下一步的工作方向还包括建立高性能后量子算法原型库, 提供调用后量子算法的统一API, 简化对NIST 和中国密码算法竞赛后量子算法的使用,这是因为我们发现liboqs 中实现的后量子算法的性能和单独测试单个算法的性能经常有较大的出入, 会在一定程度上影响测量的准确性.除此之外, 我们也正在逐步开展在Nginx Web 服务器中配置并使用我们修改后的后量子TLS 1.3 库的工作, 并尝试在实际网络中建立后量子安全的TLS 1.3 加密信道.