强安全零往返时间密钥交换协议分析与设计

黄杰彬，王立斌

(华南师范大学 计算机学院, 广东 广州 510631)

密钥交换(Key Exchange,KE)协议是确保互联网安全的核心构件之一，用于公开不可信的网络信道下通信双方进行会话密钥协商。在保障安全性的前提下，效率一直是该类协议的主要设计目标之一[1-3]。此前，协议主体的加密运算过程是引发通信延迟产生的主要原因，但随着计算设备和相关算法的不断优化，此类影响已大幅降低。进而，有效负载数据发送前建立临时会话密钥所需的往返时间(Round-Trip Time，RTT)成为协议效率考量的重要指标。

传统的认证密钥交换(Authenticated Key Ex-change，AKE)协议设计往往具有较高的RTT时延。如广泛使用的传输层安全(Transport Layer Secu-rity，TLS)协议标准[2]，其旧版(TLS1.0，1.1和1.2)的握手协议需要2-RTT时延进行临时会话密钥协商。即使是经典的高效AKE协议HMQV[4]，其建立临时会话密钥也需要两个报文发送时间，即1-RTT的传输时延。

0-RTT密钥交换协议是确保网络通信安全和高效的重要密码学构件。该类协议允许客户端在会话发起的首个报文时间内建立临时会话密钥，因此，无需任何报文交换便可加密传输有效负载数据，从而最小化通信连接时延。QUIC(Quick UDP Internet Connection)协议[5]是首个实际应用的0-RTT密钥交换协议，得到了学者们的广泛关注并开展了许多相关研究[1-3，5-10]。随后，TLS1.3[2]标准制订明确了当前密钥交换协议的主要设计目标有实现零往返时长的密钥交换协议、协议必须具备前向安全性及旧有协议应迁移至更高效的密码体制等3个方面。

在后量子时代，RSA问题、Diffie-Hellman(DH)问题等传统的数论难题，存在概率性多项式时间的求解算法[11]，导致现有的0-RTT密钥交换协议设计不具备后量子安全性。

强安全的0-RTT密钥交换协议分析与设计的主要工作内容包括以下3个方面。

1)分析总结该领域当前的发展状况，包括协议设计和安全模型定义等，指出若干亟待解决的问题。

2)分析当前存在的问题，给出一种0-RTT密钥交换协议的强安全模型定义。

3)针对后量子安全的0-RTT密钥交换协议设计，在新模型的指导下，给出格密码体制下该协议设计的若干思路。

1 交换协议及问题

1.1 协议设计

根据协议的构造方式不同，现有0-RTT密钥交换协议可分为基于Diffie-Hellman(DH)密钥交换的0-RTT密钥交换协议、基于预共享密钥(Pre-share Key)模式的0-RTT密钥交换协议和基于可穿刺加密(Puncturable Encryption)协议的0-RTT密钥交换协议等3类。

QUIC协议[5]是基于DH密钥交换的0-RTT密钥交换协议。该协议假设客户端在实际的密钥交换进行前，通过之前与服务器发生的会话，已缓存了相关的服务器配置信息。该配置信息实际包含一个由服务器签名认证的半静态DH公钥，并且对应秘密指数在有效期内(通常为两天)存储于服务器本身。通信发生时，客户端基于该半静态DH公钥可实时建立起临时会话密钥K1，用于首轮通信内有效负载数据(payload)的对称认证加密(Authenticated Encrypt，AE)，达到0-RTT通信时延的要求。由于K1的建立未有服务器生成的临时信息参与，不具备前向安全性，攻击者通过后续的服务器秘密指数泄露可计算出该密钥(会话结束后的相当长时间内)，解密监听协议报文。因此，后续协议过程需要将通信会话密钥升级到前向安全的主密钥K2。具体协议过程如图1所示。

图1 QUIC协议

随后，Hale和Jager等人基于非交互式密钥交换(Non-Interactive Key Exchange，NIKE)协议和数字签名，给出了0-RTT密钥交换协议的首个通用构造方案[1]。但该方案使用的NIKE构件在实现上依赖经典密码体制的Paring结构，因此，通用性较差，在其他密码体制下实例化较为困难。

TLS1.3的0-RTT握手协议[2-3]基于预共享密钥模式设计，本质上是0-RTT的会话恢复协议。该协议在通信发生时，首先使用1-RTT的密钥交换协议建立会话密钥，以此进一步协商出Pre-share Key。该密钥有效期与会话时长绑定，并在会话重用时直接用于本轮通信数据的加密传输。同样的，该类协议存在前述的0-RTT密钥前向安全性问题，因此，在后续的协议过程中，将根据获取的报文信息升级到前向安全的主密钥K2。

2017年，Günther和Hale等人针对该类协议0-RTT 密钥的前向安全性问题和重放攻击问题，提出了基于可穿刺加密的一次前向安全密钥交换协议(Forward-Secret One-Pass Key Exchange Protocol，FSOPKE)[6]。该协议指出，解决问题的关键在于服务器存储和处理密钥的方式，并基于层次化身份加密(Hierarchical Identity-based En-cryption，HIBE)协议和一次签名(One-Time Sig-nature)方案，提出了实现FSOPKE的通用构造方案。该方案在保持公钥不变的情况下，私钥信息实质上是链式的二叉树，并且在每次密钥协商后更新(舍弃当前解密节点，保留剪枝后的其余节点信息)，使相同报文后续无法重新解密。该方案确实有效解决了0-RTT密钥交换协议首轮通信的重放攻击问题和前向安全性问题，但要求通信双方建立起同步时钟，以避免多次通信后服务器的长期私钥存储过度增长的问题。

2018年，Derler和Jager等人基于布隆过滤器加密(Bloom Filter Encryption)给出了一种效率改进的FSOPKE通用构造方案[7]，但该方案密钥协商失败的概率是不可忽略概率的。

目前，基于可穿刺加密的0-RTT 密钥交换协议仍只是概念上的启发性工作，尽管其明确了完善前向安全性和抗重放攻击是可行的安全目标，但该类协议目前效率较低，并且同步时钟维护在现实计算环境中难以大范围实现。

1.2 安全模型

安全模型是分析协议安全性、指导协议设计的基础理论工具，具体定义了协议的理论运行环境、与攻击者能力匹配的可查询预言机和协议的具体安全目标(通常基于不可区分性安全游戏)。借助安全模型的理论框架，协议安全性可与相关难题求解的困难性建立规约，从而满足现代密码学可证明安全的理论需要。因此，迫切需要通用和面向实践的0-RTT密钥交换安全模型。

2014年，Fischlin和Günther旨在分析QUIC协议的安全性，提出了用于多阶段密钥交换协议安全性分析的安全模型定义[8]。该模型主要考究通信过程中，信道安全属性变化的情况下密钥交换协议和对称加密协议组合的安全性。该模型具有较高的通用性，可用于TLS1.3握手协议的安全性分析。但为描述各类通信阶段，该模型运行环境需要维护大量阶段状态信息，规范细节十分复杂。一方面其安全证明不直观且易于出错；另一方面掩盖了0-RTT密钥交换协议的核心构造思想，不适合指导具体的设计。该模型后续被进一步拓展[9]，用于分析多阶段密钥交换协议的重放攻击问题。

2016年，Krawczyk和Wee针对OPTLS协议定义了新的0-RTT密钥交换安全模型[2]。该模型融合了经典双边认证密钥交换协议的Canetti-Krawczyk安全模型[12](CK模型)，但将安全性分析划分为0-RTT密钥和主密钥两个阶段，不能考究各密钥的相关性，无法整体分析协议的安全性。

2017年，Hale和Jager定义了一个简洁0-RTT 密钥交换安全模型[1]，主要针对现有单边认证形式为主体的0-RTT密钥交换协议。保持结构清晰的前提下，该模型完善地考虑了该类协议的主要安全目标，强调了协议整体安全的强密钥独立性(Strong Key Independence)和主密钥的前向安全性，但在信息泄露安全上刻画较为薄弱，未考虑实践计算环境下存在的中间信息泄露问题。

2018年，Günther和Hale等人针对FSOPKE协议的提出建立了新的安全模型[6]。该模型针对性较强，主要面向基于可穿刺加密的完善前向安全性0-RTT密钥交换协议设计。

综合以上，现阶段的0-RTT密钥交换安全模型定义或过度考虑适用性，存在模型定义过于复杂的问题；或针对性过强，仅适合某单一类型的0-RTT密钥交换协议分析。Hale和Jager等人提出的安全模型[1]尽管已有较好的通用性并适合指导具体的协议设计，但该模型没有很好地对攻击者信息泄露能力进行刻画，其存在对攻击者能力限定过强，与实践攻击情形不匹配的问题，仍具有改进的空间。

2 安全模型改进

2.1 模型回顾

首先给出服务器单边认证形式下，0-RTT密钥交换协议的概念定义。

定义1服务器单边认证的0-RTT密钥交换协议由以下4个算法构成。

1)Gen(1λ)→(Kpj,Ksj)。该算法为概率性多项式时间算法，用于生成服务器Sj的公私钥对，输入安全参数λ，输出公私钥对(Kpj,Ksj)。

针对0-RTT密钥交换协议，Hale和Jager等人定义了简洁0-RTT密钥交换安全模型[1](以下简称HJ模型)，其本质是传统的一轮AKE安全模型的变体。该模型描述了该类协议的主要安全目标，并强调了强密钥独立性，即0-RTT临时会话密钥K1和K2相互独立，其中一个密钥泄露不影响另一密钥的安全性，以及主密钥K2的前向安全性。

不同于传统AKE安全模型，HJ模型的会话标识单独使用客户端预言机或服务器预言机表示，从而使会话归属方清晰且会话标识更加简单。但是在模拟执行环境时，客户端预言机需要维持相关的中间状态信息以记录当前的匹配服务器，而且仅能保存当前会话状态，之前的会话信息将丢失，不便于匹配会话的概念表达。该种标识方式在HJ模型中是合理的，因为其安全定义中明确攻击者挑战服务器密钥时，必须有真实客户端预言机的会话信息与之匹配。这意味着攻击者仅能对首轮协议报文进行被动攻击，否则是无意义的。实际上，0-RTT密钥交换协议首轮报文信息内包含有加密的负载数据，攻击者通过部分篡改报文的主动攻击方式存在获取该数据的可能。因此，该定义不能很好地刻画攻击者在现实环境下的攻击能力。

在信息泄露安全定义上，HJ模型未完善考虑现实环境中存在的信息泄露问题，攻击者不具备State Reveal的预言机查询功能，与现实环境中攻击者通过木马病毒等方式入侵实体监听内存信息的攻击方式不匹配。除此之外，该模型在攻击者挑战服务器密钥信息时，安全定义上未考虑攻击者是否对服务器发起过Corrupt查询，在会话新鲜性的定义上不严谨。

新安全模型旨在解决上述HJ模型存在的相关问题，以指导更面向实践的强安全0-RTT密钥交换协议设计。

2.2 改进原则

针对信息泄露安全的形式化定义，首先明确现实计算环境中主要存在的信息泄露方式，即实践网络环境下，攻击者通过木马病毒等方式入侵通信实体可监听内存获取协议中间计算信息，或通过边信道攻击等方式获取当前会话密钥，或攻击者为内部人员，具有某一实体的长期公私钥信息。

指导抗信息泄露的0-RTT密钥交换协议设计，需要精确刻画该类威胁的强安全模型，明确信息泄露安全的形式化定义。传统双边认证密钥交换协议的CK模型[12]在给予攻击者通信链路控制能力的同时，还定义了攻击者获取信息泄露的3种预言机查询能力。

1)StateReveal。攻击者指定某未完成会话的会话标识，获得该会话的中间状态信息(不包括长期密钥信息)。该预言机匹配攻击者入侵通信实体，监听内存协议中间状态信息过程。

2)KeyReveal。攻击者指定某完成会话的会话标识，获得该会话达成的临时协商密钥。该预言机匹配现实场景下的会话密钥泄露。

3)Corrupt。攻击者指定某一通信实体，获得长期密钥信息在内的所有会话信息，并可伪装成该用户。该预言机描述现实中攻击者为内部人员的攻击方式。

区别于传统密钥交换协议的双边认证形式，现有0-RTT密钥交换协议主要是服务器单边认证形式，客户端不具备长期的公私密钥信息。因此，引入以上的信息泄露安全定义时，应根据单边认证的协议形式适应性修改。如果定义太强，则难以构造满足安全定义的协议设计；反之太弱，则无法指导抵抗实践攻击类型的协议设计。因此，需遵循原则：会话密钥泄露不影响其他会话安全：包括0-RTT临时密钥K1和主密钥K2；中间状态值泄露不影响到其他会话安全，如临时密钥信息和部分中间计算值；服务器长期私钥泄露不影响其泄露之前发生会话的安全性。

基于HJ模型，给出一种新的0-RTT 密钥交换强安全模型。新模型沿用CK模型的符号标记以便于匹配会话等相关概念表述，在保留强密钥独立性和主密钥前向安全性的属性刻画前提下，允许攻击者通过StateReveal预言机查询获取服务器的中间计算信息。此外，新模型允许攻击者主动攻击客户端发送的首轮协议报文，以更精确地刻画实际攻击情形。

2.3 强安全模型定义

运行环境令λ为安全参数，将客户端和服务器模拟为概率性多项式时间图灵机。假设客户端数量d=poly(λ)，标记为Ci，i∈[d]。服务器数量l=poly(λ)，标记为Sj，j∈[l]。各服务器均拥有一对长期的公私钥(Kpj,Ksj)，j∈[l]。客户端不具有长期公私钥。客户端可获取各服务器的长期公钥Kp1,…,Kpl。

会话客户端Ci被初始化执行一个0-RTT协议实例，称为会话。

会话标识使用四元组(Pa,Pb,Mout,Min)标识会话，其中，P分别表示客户端Ci和服务器Sj，Pa是会话的拥有者，Pb为对等方，Mout表示Pa发送给Pb的报文，Min表示Pa接收到来自Pb的报文。每个会话由唯一的会话标识确定。

匹配会话会话sid=(Pa,Pb,Mout,Min)和会话sid*=(P′b,P′a,Mout′,Min′)为匹配会话，当且仅当以下条件成立

Pa=P′a且Pb=P′b

Mout=Min′且Min=Mout′

攻击者基本能力对概率性多项式时间攻击者A，使用查询Send预言机的方式形式化定义攻击者控制通信链路的能力。

1)Send(Ci,Sj)。攻击者在客户端Ci处激活会话初始化，Sj为该会话对等方，客户端Ci根据协议生成首轮的协议报文，返回客户端Ci发出的报文信息或错误信号“⊥”。

2)Send(Sj,Ci,Mout)。攻击者在服务器端Sj激活会话，其中，Mout是客户端Ci发出的协议报文，根据协议执行过程，返回服务器Sj发出的报文信息或错误信号“⊥”。

3)Send(Ci,Sj,Mout,Min)。攻击者激活客户端Ci处会话，其中，Min和Mout分别是服务器Sj的接收报文和响应报文。根据协议定义，客户端Ci完成会话或返回错误信号“⊥”。

攻击者获取信息泄露此处形式化定义概率性多项式时间攻击者A获取信息泄露预言机，具体如下。

1)KeyReveal(sid,tmp)。依攻击者发起查询，检查该阶段会话sid拥有者是否生成临时会话密钥K1。若是则返回K1，否则返回错误信号“⊥”。

2)KeyReveal(sid,main)。依攻击者发起查询，检查该阶段会话sid拥有者是否生成主密钥K2。若是则返回K1，否则返回错误信号“⊥”。

3)StateReveal(sid)。返回会话sid拥有者协议执行过程中的中间状态信息，包括临时随机数和中间计算值。

4)Corrupt(Sj)。根据输入的服务器身份标识Sj，返回该服务器的长期私钥KSj。

与此同时，攻击者A为区分随机密钥和真实会话密钥，进行以下某一查询，且攻击者仅能选择其中一种查询。

1) Test(sid,tmp)。攻击者仅能发起一次该查询。若会话sid拥有者的临时会话密钥K1为空，或会话sid拥有者为服务器且与对等方临时会话密钥K1不等，返回错误信号“⊥”；否则，随机选取b←{0,1}，当b=0时，返回会话拥有者根据协议执行计算得到的临时会话密钥K1。当b=1时，则返回与临时会话密钥K1等长同分布的随机比特串K′1。

2)Test(sid,main)。攻击者只能发起一次该询问。若会话sid拥有者的主密钥K2为空，返回错误信号“⊥”；否则，随机选取b←{0,1}，当b=0时，返回会话拥有者根据协议执行计算得到的主密钥K2。当b=1时，则返回与临时会话密钥K1等长同分布的随机比特串K′2。

现实中的攻击行为可通过上述预言机查询的组合和限制进行描述。下面先给出会话新鲜性的形式化定义。

2)如果攻击者A发起Test(sid,main)查询，则有：攻击者A未查询KeyReveal(sid,main)，或sid*存在且未查询KeyReveal(sid*,main)；攻击者A未查询StateReveal(sid)，或sid*存在且未查询KeyReveal(sid*)；攻击者A在Test(sid,main)查询发起前，未对会话sid的服务器端Sj发起过Corrupt(Sj)查询。

定义攻击者获得该安全游戏胜利的优势为

0-RTT密钥交换安全对0-RTT密钥交换协议∏，若任意的概率性多项式时间攻击者A，获得上述安全游戏胜利的概率为关于安全参数λ的可忽略函数negl(λ)，即

则称协议∏是0-RTT密钥交换安全的。

3 协议设计关键技术

针对现有通用构造过度依赖经典密码体制Paring结构的问题，基于强安全模型，提出一种新的通用构造方案，以期具有更好的通用性和高效实例化可能，用于指导后量子安全的强安全0-RTT密钥交换协议设计。

3.1 通用构造分析

基于Hale和Jager等人的0-RTT密钥交换通用构造[1]，提出一种新的通用构造方案。

Hale与Jager等人的通用构造方案使用了“NIKE+数字签名”的协议构件进行设计，并且在HJ模型[1]下可证明安全。然而，该方案使用的NIKE构件在实现上依赖经典密码体制的Paring结构，存在效率较低、难以实例化的问题[13]。其次，在该协议中，服务器的签名信息未与客户端发送的临时公钥绑定，在强安全模型下存在平行会话攻击：攻击者通过StateReveal查询可获取服务器端的中间计算信息，包括本次通信中服务器生成的临时私钥、临时公钥和认证该临时公钥的服务器签名，借此可伪装为服务器与其他客户端建立通信。该种攻击方式一方面难以发现，另一方面泄露了后续会话长期使用的主密钥，因而危害性较大。

针对NIKE构件通用性较差的问题，并且考虑该类协议在客户端不具备长期公私钥情况下，通过单个协议报文协商0-RTT会话密钥的协议需求，新构造将使用各密码体制下均易于构造的密钥封装机制(Key Encapsulation Mechanism，KEM)作为首轮通信协议的主要设计构件。

在新协议中，由服务器返回的通信报文需要服务器进行身份认证并建立前向安全的主密钥，因此，新构造将使用文献[14]的密钥封装机制(Signcryption KEM，SC-KEM)作为该轮协议的主要设计构件，原因是上述讨论的平行会话攻击实质上与签密方案(Signcryption Scheme)的多方安全问题[15-16]一致，可通过加密过程引入通信双方身份标识解决。但是，广义密码学定义的KEM仅可封装随机的临时会话密钥，不能指定加密内容，严格意义上无法满足该条件，而SC-KEM在安全模型定义上已考虑了多方安全[17-19]，可用于解决该问题。

新模型允许客户端对首轮会话发起主动攻击，为避免攻击者通过部分修改首轮协议信息(简单替换客户端临时生成的公钥)构造出新鲜会话并查询KeyReveal预言机直接获取0-RTT会话密钥，新构造将使用抗碰撞的哈希函数对首轮报文信息进一步绑定。

1)Gen(1λ)→(Kp,Ks)。给定安全参数1λ，服务器使用KEM以及SCKEM的密钥生成算法，按以下方式生成长期公私钥，即

Ktmp←KDEC(KKEMsj,Ctmp)

注意，如果Ktmp=⊥，即协商报文不合法，服务器Sj则终止该会话，不生成会话密钥。

注意，如果Kmain=⊥，即协商报文不合法，客户端Ci则终止该会话，不生成会话密钥。

相比于Hale和Jager等人的构造，新方案使用的KEM和SCKEM均是易于构造的。其中，SCKEM可直接通过任意的签密方案进行实例化，如简单的“公钥加密+数字签名”朴素构造，此外也可通过“Tag-KEM+数字签名”方案[19]进行实现。

3.2 基于格密码的后量子安全协议设计

结合通用构造方案，提出格密码体制下后量子安全的0-RTT密钥交换协议的若干设计思路。

格密码(Lattice Cryptography)作为近年发展成熟的基础密码理论，有成为后量子密码技术标杆的趋势。在计算上，格密码通常仅涉及简单的整数加法乘法运算，数学概念简单直观，计算效率优势明显。安全层面上，格上的相关难题尚不存在可预见的结构弱点，量子计算下也是求解困难的。

经典格密码体制下的主流协议，主要基于平均情况困难问题的短整数解问题(Short Integer Solution Problem，SIS)和带误差学习问题(Learn-ing with Errors Problem，LWE)设计，均可量子规约到格上最坏情况困难问题的最短线性无关向量问题，安全性基础完备，但存在通信数据和密钥体积较大的先天性劣势。目前，高效格密码协议设计主要基于模短整数解问题(Module-SIS Problem，MSIS)和模带误差学习问题[20-21](Module-LWE Problem，MLWE)。该类难题尽管暴露了更多的结构特征，但仍未有多项式时间的量子求解算法，存储和运算上的解决方案也更加高效。

根据前文讨论，实例化格密码体制的0-RTT密钥交换协议需重点关注该体制下KEM和SC-KEM协议的具体实现。其中，SC-KEM可通过公钥加密方案、KEM和数字签名等构件实现，并且在格密码体制下已有一些高效方案被提出[22-26]。参考当前由美国国家标准和技术研究所(National Institute of Stan-dards and Technologies)推进的后量子密码标准竞选，目前在格密码体制下已有多种高效的KEM和数字签名方案，如基于LWE的实用Frodo KEM[27]，基于MLWE设计的Kyber[28](包含公钥加密方案和KEM)，基于MSIS及MLWE的高效签名方案CRYSTALS-Dilithium[26]等，均可用于通用构造的实例化。

实例化格密码体制下的数字签名方案时，可参考基于格陷门算法的Hash and Sign通用构造[29]。此外，新型的Gadget陷门算法[30-31]由于具有多种效率优化策略并且适配多项式环结构格，可用于上述的算法优化。

4 结语

分析和总结了现有0-RTT 密钥交换协议的研究工作，设计了一种0-RTT 密钥交换安全模型，相对于现有的模型，该模型对攻击者的能力刻画更精确。在该模型的指导下，提出了一种0-RTT密钥交换协议的通用构造，并给出了格密码体制下协议设计的若干思路。基于此，该领域仍存在一些问题有待解决，将是今后工作推进的重点，总结如下。

1)后量子安全协议设计。目前仅提出了格密码体制下的若干协议设计思路，仍未具体实例化。在确保高效和安全性的基础上，应进一步考虑其他后量子安全密码体制下的具体设计策略，并给出紧致的安全性规约证明。

2)量子计算下的安全模型设计。现有安全模型未考虑量子环境下的攻击者能力，应通过引入量子随机预言机[32]等方式进一步强化0-RTT 密钥交换协议的安全模型形式化定义。

以上研究对后量子时代的网络通信安全具有重要影响和实践意义，相关工作有必要适时展开，为量子时代的网络通信提供更强而有力的理论保障。