一种基于PUF的两方认证与会话密钥交换协议

贺章擎，李 红，万美琳，吴铁洲

1.湖北工业大学 太阳能高效利用湖北省协同创新中心，武汉 430068

2.湖北工业大学 计算机学院，武汉 430068

3.湖北大学 物理与电子科学学院，武汉 430062

1 引言

传统嵌入式设备的安全依赖于公开的加密算法以及存储在非易失性存储器（NVM）中的数字密钥。然而，随着各种新型的物理攻击技术的不断出现，存储在NVM中的密钥已不再安全[1-2]，采用物理不可克隆技术（Physical Unclonable Function，PUF）[3]来产生和存储密钥成为一个新的发展趋势[4]。另一方面，为了将PUF产生的密钥与其他通信实体共享以实现安全认证[5-6]、数据加密等功能，需要在可信实体之间建立可靠的共享密钥，这就涉及到密钥交换（Key Exchange，KE）问题。由于PUF输出中不可避免会存在噪声，因此现有密钥交换协议中普遍采用了模糊提取器（Fuzzy Extractors）[7]和子串匹配（Substring-matching）[8]等技术来消除PUF噪声以提取稳定密钥。然而，目前已提出的KE协议，要么存在安全缺陷，要么开销较大，难以适用资源受限的嵌入式系统。例如，在基于模糊提取器的协议中，Brzuska等人[9]提出的协议只实现了单向认证；Tuyls等人[10]提出的用于银行ATM机的KE协议虽然实现了双向认证和可靠的密钥交换，但协议需要用到模糊提取器、散列函数和对称加密算法，开销很大；另外协议中Bank事先需要对PUF进行注册，获取大量的CRP（Challenge-Response Pairs）数据，这增加了PUF设备部署的难度。Kocabas等人[11]提出了一种“反向”PUF认证协议，实现了双向认证与密钥交换。但该协议同样需要事先提取大量CRPs，同时在每一次认证过程中需要执行大量的查找与异或操作，会消耗大量的运算资源。Rostami等人[12]提出的协议则通过子串匹配的方法来消除PUF的噪声，有效降低了协议执行开销。但是，为了避免预先搜集存储大量的CRPs，Server利用了建模攻击技术[13]来对Device中的PUF进行建模并进行认证，这种方式存在一定的问题：为了利于建模，协议中的PUF需要采用高相关性的设计结构，但是这种显式或者隐式相关性很容易被攻击者利用从而恢复出索引（Indices）和密钥，因此很难在这两者之间取得平衡[14]。

对此，本文提出了一种新型的两方安全与会话密钥交换协议，在拥有一个PUF实体的密码设备（Device）与服务器（Server）之间进行安全认证并建立共享会话密钥。本协议实现了双向认证与可靠的密钥交换，同时能够抵抗物理探测攻击、建模攻击与拒绝服务攻击，具有很好的前向安全性。而且，该协议中的Device在部署之前，Server并不需要提取并存储大量的PUF原始数据，有效降低了部署难度并提高了安全性。协议采用了模糊提取器来进行认证和密钥提取，但是并未采用散列函数和对称加密算法，有效降低了执行开销。

2 PUF-based安全认证与会话密钥交换协议

2.1 基本概念

为了对协议进行描述，先给出一些形式化的定义。

如果A是一个确定性的算法，y:=A(x)表示将x输入到算法A所产生的输出。

真随机数产生器（Truly Random Number Generator）TRNG代表一个真随机数序列。

物理不可克隆方程 f:C→R：当输入一个激励c∈C,输出响应r∈R。

伪随机函数（Pseudorandom Function）PRF和PRF′:K′×D′→R′以密钥sk∈K′和信息m∈D′为输入，得到一个伪随机数 pr∈R′。

模糊提取器FE:=(FE.Gen,FE.Rec)：密钥产生函数FE.Gen以PUF响应r为输入，输出密钥k和辅助数据（helper data）hd。密钥恢复函数FE.Rec以带噪音的PUF响应r′和辅助数据hd为输入，在HD(r,r′)足够小的情况下，可以恢复出密钥k。

2.2 协议描述

本文提出的协议在一个拥有PUF的 Device与Server之间进行，Server拥有FE.Gen函数、TRNG函数、PRF函数和PRF′函数。而Device拥有 f函数、FE.Rec函数、TRNG函数、PRF函数和PRF′函数。其中，伪随机函数PRF以L位密钥sk和L位信息m为输入，产生4L位的伪随机数。而PRF′函数则以L位密钥sk和L位信息m为输入，产生L位的伪随机数。

协议执行过程分为两个阶段：设置阶段（Setup Phase）和密钥交换阶段（Key-exchange Phase）。

设置阶段需要在安全环境下进行，Server和Device进行安全初始化并建立初始共享秘密。在此阶段，Server首先给Device分配一个唯一识别号IDi，然后利用TRNG函数产生一个随机的激励c1，以c1为输入从Device的PUF实体中获得响应 r1。Server再利用FE.Gen函数从r1获得密钥k1和辅助数据hd1。Server保存密钥k=k1，以及kold=k1。Device保存激励c1和辅助数据hd1，注册过程完成，这样Server和Device建立了初始共享密钥k。设置阶段执行过程如图1所示。

图1 协议设置阶段执行流程

当Server和Device想要进行密钥更新和交换时，就进入密钥交换阶段，如图2所示。Server首先发送一个随机数m1给Device，Device收到m1后，再产生一个随机数m2。然后，将保存的激励值c1输入到PUF中，获取带有噪声的响应值r1，并使用模糊提取函数FE.Rec和保存的辅助数据hd1从r1中提取出密钥k。再以k为密钥、m1||m2为输入，利用PRF函数产生4个伪随机数s1,s2,s3,s4用于后续的认证和加密。为了进行密钥更新，Device会随机产生一个新的激励值c2，利用Device内部的物理不可克隆方程 f获取对应的PUF响应r2，将s1与r2进行异或得到u1，然后利用PRF′函数计算u1的消息认证码（Message Authentication Codes，MAC）v1:=PRF′(s2,m1||u1)。最后，将 IDi、m2、u1和 v1发送给Server。

图2 密钥交换阶段执行流程

Server收到上述信息之后，在数据库中查找IDi所对应的密钥k和kold，并以k为密钥、m1||m2为输入，利用相同的 PRF 函数产生 4 个伪随机数 s′1,s′2,…,s′4。如果Device是可信的，s′1,s′2,…,s′4将与 s1,s2,…,s4相同。此时，Server将以s′2为密钥，计算接收到的u1的MAC值 PRF′(s′2,m1||u1)并验证与接收的v1是否相等，若相等则通过对Device的认证，同时也证明u1未被篡改，然后将u1与s′1异或获取r2。最后，Server利用模糊提取函数FE.Gen从r2中提取出新的密钥k2和辅助数据 hd2，并将密钥 k、kold更新为 k2和 k 。最后，将 s′3与hd2异或得到u2并计算其MAC值v2，再将u2、v2发送给Device。

若Server计算的 u1的MAC值 PRF′(s′2,m1||u1)与接收的v1不相等，Server将使用kold替代k再次计算 s′1,s′2,…,s′4，并再次验证 PRF′(s′2,m1||u1)与 s1与接收的v1是否相等。如果相等，则同样通过认证，并执行如前所述的操作；否则，认证失败，Server返回一些随机值给Device。

Device接收到u2、v2信息之后，利用s4计算u2的MAC值PRF′(s4,m2||u2)，并验证其与收到的v2是否相等。若想等，则Device通过对Server的认证，同时证明u2未被篡改。此时Device将u2与s3异或得到hd2，并将c1、hd1更新为c2和hd2。至此，密钥交换过程完成，Server和Device建立了新的会话密钥k。

3 BAN逻辑形式化分析

本文采用BAN逻辑形式化分析方法对本文所提出的协议进行安全性证明。在本协议执行过程中，Server（S）或Device（D）分别利用相同的伪随机函数PRF分别生成4个伪随机数 s′1,s′2,…,s′4将与 s1,s2,…,s4用于后续的认证和加密。由于PRF是以双方的共享密钥k和实时产生的随机数m1和m2为输入产生，因此s′1,s′2,…,s′4将与 s1,s2,…,s4相同。因此设定Server或Device事先共享了四个密钥，分别用kab1,kab2,kab3,kab4表示。另外，由于协议采用了PUF和模糊提取器来实时产生最后的密钥k，实际上协议双方交换的共享秘密信息分别为r2和hd2。因此为了简化分析，将r2和hd2作为双方最终交换的密钥信息来进行安全性分析。在PUF函数和模糊提取器可信的情况下，若r2和hd2满足安全性需求，那么最终产生的密钥k也将满足安全性需求。

本文用到的BAN逻辑推理规则如下：

（1）协议理想化

（2）初始化假设

（3）注释协议

（4）安全目标

（5）推导过程

由 P1、P3、P13和 R1可得：

由P9和R2可知：

由式（1）、（2）和 R3可得：

由式（3）和 R4可得：

由式（2）和 R2可知：

由 P11、式（5）和 R5可得：

安全目标①得证。

同理可以证明安全目标②，过程与上述类同，此处不再赘述。

4 协议安全特性

（1）双向认证

本协议在密钥交换之前，Server和Device分别利用v1和v2对对方进行认证。对恶意第三方来说，由于未知共享密钥k，不可能以不可忽略的概率预测 s′1,s′2,…,s′4与 s1,s2,…,s4，因此不可能通过认证。另外，由于随机数m1或m2的加入，攻击者也无法通过重放攻击进行假冒。

（2）数据加密

为了保护信道上传输的关键数据，r2和hd2分别与伪随机数s1和s′3异或之后再传输。Shannon理论证明，如果在异或操作中至少有一项是随机的，那么一个简单的异或加密能很好地保证安全。对恶意第三方来说，s1和s′3完全是随机的，因此协议利用简单的异或加密技术有效确保了传输数据的机密性，同时降低了实现开销。

（3）消息认证

为了抵抗篡改攻击、中间人攻击等攻击技术，协议对信道上传输的加密信息u1和u2进行了MAC消息认证。以s2和s4为密钥，利用伪随机函数PRF′生成消息认证码。消息码中加入了Server或Device实时产生的随机值m1或m2，保证了消息认证码的新鲜性。

（4）抗物理探测攻击

在传统的密钥交换协议中，由于密钥直接保存在非易失性存储器中，因此容易受到侵入式探测攻击和非侵入式图像攻击的破解。在本协议中，Device中只存储了激励c1和hd1，即使攻击者破解了c1和hd1，且知道了PUF的结构，由于PUF的不可克隆性，攻击者仍旧无法获取密钥k的值。另外，由于新的密钥值k2由随机产生的激励c2决定，因此，c1和hd1的泄露也不会对新密钥产生影响。

（5）前向安全性与后向安全性

协议中所产生的新密钥k2=FE.Gen(f(c2))，因此k2由激励信息c2所决定。由于每次密钥更新时，c2是随机产生的，这就确保了协议中每一次更新的密钥值具有独立性。即使攻击者知道了某次的会话密钥值，也无法推算出前一次的会话密钥。但是，若敌手已知某一时刻的会话密钥k，由于随机数m1与m2是明文传输的，那么敌手也可以计算出4个伪随机数s1,s2,…,s4。由此可见，往后的密钥协商过程，对于敌手是透明的，因此，本协议并不具有后向安全性。但前面已经分析过，本协议可以抵抗物理攻击，能有效地保证密钥k不被攻击者破解。

（6）抗建模攻击

建模攻击（Modeling attack）是Strong PUF面临的一个主要威胁[13]。但建模攻击的前提是获取足够多的CPRs。在其他协议中，攻击者可以通过监听通信信道，或者进行物理攻击来获取CPRs[15]。然而，在本协议中，攻击者通过探测Device的NVM只能获取部分激励c和辅助数据hd。而响应值r在信道传输时利用伪随机数进行了异或加密。因此，攻击者通过上述攻击手段是无法获取所需的CPRs来进行建模攻击。

（7）抵抗去同步攻击

去同步攻击是认证和密钥交换协议面临的一个主要威胁。攻击者通过各种手段使认证双方的密钥更新不同步从而产生失配。本协议中，当Server完成对Device进行认证后，将会首先更新其保存的密钥k。如果此时攻击者发动去同步攻击，使Device在后面无法正确接收到Server发送的数据，那么Device将不会更新密钥k，从而发生密钥失配现象。为了应对该威胁，协议在Server中保存了旧密钥kold，一旦双方发现出现了不同步情况，就使用旧密钥kold来进行认证和密钥更新。

5 协议对比分析

表1给出了本协议与目前几种主流的PUF密钥交换协议在安全性和实现开销方面的对比分析。

从中可以看出，本文提出的协议与现有协议相比具有更好的安全性。协议实现了双向认证与可靠的密钥交换，能够抵抗物理探测攻击与拒绝服务攻击，具有很好的前向安全性。由于加入了消息认证码，可以有效抵抗篡改和欺骗攻击等。又由于PUF的激励响应对(c,r)经过了加密传输，可以防止建模攻击。更重要的是，协议中的Device在部署之前，Server只需要获取并存储Device中PUF电路的一条激励-响应信息，用于后续的密钥更新与交换，避免了因采集大量的激励-响应信息而带来的存储资源的消耗问题。另外，传统PUF协议由于服务器端由于存储了大量的PUF数据，一旦信息发生泄露，会给系统带来致命的威胁。而本协议大大减少了服务器端用户相关数据泄露所带来的风险。此外，本协议内部采用了模糊提取器、真随机数产生器和伪随机函数，在一次密钥交换过程中，Device内部需要执行1次模糊提取运算和3次PRF伪随机函数运算，双方通信量为6L。而Tuyls等人[10]提出的协议在一次密钥交换中要执行1次模糊提取运算、1次对称加密运算、2次散列Hash运算和1次消息认证码MAC运算，通信量也为6L。因此本文提出的协议在实现成本和计算效率上具有更大的优势。

表1 本文提出协议与其他几种协议的对比分析

6 结束语

本文提出了一种新型的安全认证与会话密钥交换协议，实现了双向认证与可靠的密钥交换，能够抵抗物理探测攻击、建模攻击与拒绝服务攻击，具有很好的前向安全性。而且，该协议中的Device在部署之前，Server并不需要提取并存储大量的PUF原始数据，有效降低了部署难度并提高了安全性，与现有PUF协议相比安全性更好且实现开销更低。