一種基于PUF的兩方認證與會話密鑰交換協(xié)議

賀章擎，李 紅，萬美琳，吳鐵洲

1.湖北工業(yè)大學 太陽能高效利用湖北省協(xié)同創(chuàng)新中心，武漢 430068

2.湖北工業(yè)大學 計算機學院，武漢 430068

3.湖北大學 物理與電子科學學院，武漢 430062

1 引言

傳統(tǒng)嵌入式設備的安全依賴于公開的加密算法以及存儲在非易失性存儲器（NVM）中的數(shù)字密鑰。然而，隨著各種新型的物理攻擊技術的不斷出現(xiàn)，存儲在NVM中的密鑰已不再安全[1-2]，采用物理不可克隆技術（Physical Unclonable Function，PUF）[3]來產(chǎn)生和存儲密鑰成為一個新的發(fā)展趨勢[4]。另一方面，為了將PUF產(chǎn)生的密鑰與其他通信實體共享以實現(xiàn)安全認證[5-6]、數(shù)據(jù)加密等功能，需要在可信實體之間建立可靠的共享密鑰，這就涉及到密鑰交換（Key Exchange，KE）問題。由于PUF輸出中不可避免會存在噪聲，因此現(xiàn)有密鑰交換協(xié)議中普遍采用了模糊提取器（Fuzzy Extractors）[7]和子串匹配（Substring-matching）[8]等技術來消除PUF噪聲以提取穩(wěn)定密鑰。然而，目前已提出的KE協(xié)議，要么存在安全缺陷，要么開銷較大，難以適用資源受限的嵌入式系統(tǒng)。例如，在基于模糊提取器的協(xié)議中，Brzuska等人[9]提出的協(xié)議只實現(xiàn)了單向認證；Tuyls等人[10]提出的用于銀行ATM機的KE協(xié)議雖然實現(xiàn)了雙向認證和可靠的密鑰交換，但協(xié)議需要用到模糊提取器、散列函數(shù)和對稱加密算法，開銷很大；另外協(xié)議中Bank事先需要對PUF進行注冊，獲取大量的CRP（Challenge-Response Pairs）數(shù)據(jù)，這增加了PUF設備部署的難度。Kocabas等人[11]提出了一種“反向”PUF認證協(xié)議，實現(xiàn)了雙向認證與密鑰交換。但該協(xié)議同樣需要事先提取大量CRPs，同時在每一次認證過程中需要執(zhí)行大量的查找與異或操作，會消耗大量的運算資源。Rostami等人[12]提出的協(xié)議則通過子串匹配的方法來消除PUF的噪聲，有效降低了協(xié)議執(zhí)行開銷。但是，為了避免預先搜集存儲大量的CRPs，Server利用了建模攻擊技術[13]來對Device中的PUF進行建模并進行認證，這種方式存在一定的問題：為了利于建模，協(xié)議中的PUF需要采用高相關性的設計結構，但是這種顯式或者隱式相關性很容易被攻擊者利用從而恢復出索引（Indices）和密鑰，因此很難在這兩者之間取得平衡[14]。

對此，本文提出了一種新型的兩方安全與會話密鑰交換協(xié)議，在擁有一個PUF實體的密碼設備（Device）與服務器（Server）之間進行安全認證并建立共享會話密鑰。本協(xié)議實現(xiàn)了雙向認證與可靠的密鑰交換，同時能夠抵抗物理探測攻擊、建模攻擊與拒絕服務攻擊，具有很好的前向安全性。而且，該協(xié)議中的Device在部署之前，Server并不需要提取并存儲大量的PUF原始數(shù)據(jù)，有效降低了部署難度并提高了安全性。協(xié)議采用了模糊提取器來進行認證和密鑰提取，但是并未采用散列函數(shù)和對稱加密算法，有效降低了執(zhí)行開銷。

2 PUF-based安全認證與會話密鑰交換協(xié)議

2.1 基本概念

為了對協(xié)議進行描述，先給出一些形式化的定義。

如果A是一個確定性的算法，y:=A(x)表示將x輸入到算法A所產(chǎn)生的輸出。

真隨機數(shù)產(chǎn)生器（Truly Random Number Generator）TRNG代表一個真隨機數(shù)序列。

物理不可克隆方程 f:C→R：當輸入一個激勵c∈C,輸出響應r∈R。

偽隨機函數(shù)（Pseudorandom Function）PRF和PRF′:K′×D′→R′以密鑰sk∈K′和信息m∈D′為輸入，得到一個偽隨機數(shù) pr∈R′。

模糊提取器FE:=(FE.Gen,FE.Rec)：密鑰產(chǎn)生函數(shù)FE.Gen以PUF響應r為輸入，輸出密鑰k和輔助數(shù)據(jù)（helper data）hd。密鑰恢復函數(shù)FE.Rec以帶噪音的PUF響應r′和輔助數(shù)據(jù)hd為輸入，在HD(r,r′)足夠小的情況下，可以恢復出密鑰k。

2.2 協(xié)議描述

本文提出的協(xié)議在一個擁有PUF的 Device與Server之間進行，Server擁有FE.Gen函數(shù)、TRNG函數(shù)、PRF函數(shù)和PRF′函數(shù)。而Device擁有 f函數(shù)、FE.Rec函數(shù)、TRNG函數(shù)、PRF函數(shù)和PRF′函數(shù)。其中，偽隨機函數(shù)PRF以L位密鑰sk和L位信息m為輸入，產(chǎn)生4L位的偽隨機數(shù)。而PRF′函數(shù)則以L位密鑰sk和L位信息m為輸入，產(chǎn)生L位的偽隨機數(shù)。

協(xié)議執(zhí)行過程分為兩個階段：設置階段（Setup Phase）和密鑰交換階段（Key-exchange Phase）。

設置階段需要在安全環(huán)境下進行，Server和Device進行安全初始化并建立初始共享秘密。在此階段，Server首先給Device分配一個唯一識別號IDi，然后利用TRNG函數(shù)產(chǎn)生一個隨機的激勵c1，以c1為輸入從Device的PUF實體中獲得響應 r1。Server再利用FE.Gen函數(shù)從r1獲得密鑰k1和輔助數(shù)據(jù)hd1。Server保存密鑰k=k1，以及kold=k1。Device保存激勵c1和輔助數(shù)據(jù)hd1，注冊過程完成，這樣Server和Device建立了初始共享密鑰k。設置階段執(zhí)行過程如圖1所示。

圖1 協(xié)議設置階段執(zhí)行流程

當Server和Device想要進行密鑰更新和交換時，就進入密鑰交換階段，如圖2所示。Server首先發(fā)送一個隨機數(shù)m1給Device，Device收到m1后，再產(chǎn)生一個隨機數(shù)m2。然后，將保存的激勵值c1輸入到PUF中，獲取帶有噪聲的響應值r1，并使用模糊提取函數(shù)FE.Rec和保存的輔助數(shù)據(jù)hd1從r1中提取出密鑰k。再以k為密鑰、m1||m2為輸入，利用PRF函數(shù)產(chǎn)生4個偽隨機數(shù)s1,s2,s3,s4用于后續(xù)的認證和加密。為了進行密鑰更新，Device會隨機產(chǎn)生一個新的激勵值c2，利用Device內(nèi)部的物理不可克隆方程 f獲取對應的PUF響應r2，將s1與r2進行異或得到u1，然后利用PRF′函數(shù)計算u1的消息認證碼（Message Authentication Codes，MAC）v1:=PRF′(s2,m1||u1)。最后，將 IDi、m2、u1和 v1發(fā)送給Server。

圖2 密鑰交換階段執(zhí)行流程

Server收到上述信息之后，在數(shù)據(jù)庫中查找IDi所對應的密鑰k和kold，并以k為密鑰、m1||m2為輸入，利用相同的 PRF 函數(shù)產(chǎn)生 4 個偽隨機數(shù) 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利用模糊提取函數(shù)FE.Gen從r2中提取出新的密鑰k2和輔助數(shù)據(jù) hd2，并將密鑰 k、kold更新為 k2和 k 。最后，將 s′3與hd2異或得到u2并計算其MAC值v2，再將u2、v2發(fā)送給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是否相等。如果相等，則同樣通過認證，并執(zhí)行如前所述的操作；否則，認證失敗，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邏輯形式化分析方法對本文所提出的協(xié)議進行安全性證明。在本協(xié)議執(zhí)行過程中，Server（S）或Device（D）分別利用相同的偽隨機函數(shù)PRF分別生成4個偽隨機數(shù) s′1,s′2,…,s′4將與 s1,s2,…,s4用于后續(xù)的認證和加密。由于PRF是以雙方的共享密鑰k和實時產(chǎn)生的隨機數(shù)m1和m2為輸入產(chǎn)生，因此s′1,s′2,…,s′4將與 s1,s2,…,s4相同。因此設定Server或Device事先共享了四個密鑰，分別用kab1,kab2,kab3,kab4表示。另外，由于協(xié)議采用了PUF和模糊提取器來實時產(chǎn)生最后的密鑰k，實際上協(xié)議雙方交換的共享秘密信息分別為r2和hd2。因此為了簡化分析，將r2和hd2作為雙方最終交換的密鑰信息來進行安全性分析。在PUF函數(shù)和模糊提取器可信的情況下，若r2和hd2滿足安全性需求，那么最終產(chǎn)生的密鑰k也將滿足安全性需求。

本文用到的BAN邏輯推理規(guī)則如下：

（1）協(xié)議理想化

（2）初始化假設

（3）注釋協(xié)議

（4）安全目標

（5）推導過程

由 P1、P3、P13和 R1可得：

由P9和R2可知：

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

由式（3）和 R4可得：

由式（2）和 R2可知：

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

安全目標①得證。

同理可以證明安全目標②，過程與上述類同，此處不再贅述。

4 協(xié)議安全特性

（1）雙向認證

本協(xié)議在密鑰交換之前，Server和Device分別利用v1和v2對對方進行認證。對惡意第三方來說，由于未知共享密鑰k，不可能以不可忽略的概率預測 s′1,s′2,…,s′4與 s1,s2,…,s4，因此不可能通過認證。另外，由于隨機數(shù)m1或m2的加入，攻擊者也無法通過重放攻擊進行假冒。

（2）數(shù)據(jù)加密

為了保護信道上傳輸?shù)年P鍵數(shù)據(jù)，r2和hd2分別與偽隨機數(shù)s1和s′3異或之后再傳輸。Shannon理論證明，如果在異或操作中至少有一項是隨機的，那么一個簡單的異或加密能很好地保證安全。對惡意第三方來說，s1和s′3完全是隨機的，因此協(xié)議利用簡單的異或加密技術有效確保了傳輸數(shù)據(jù)的機密性，同時降低了實現(xiàn)開銷。

（3）消息認證

為了抵抗篡改攻擊、中間人攻擊等攻擊技術，協(xié)議對信道上傳輸?shù)募用苄畔1和u2進行了MAC消息認證。以s2和s4為密鑰，利用偽隨機函數(shù)PRF′生成消息認證碼。消息碼中加入了Server或Device實時產(chǎn)生的隨機值m1或m2，保證了消息認證碼的新鮮性。

（4）抗物理探測攻擊

在傳統(tǒng)的密鑰交換協(xié)議中，由于密鑰直接保存在非易失性存儲器中，因此容易受到侵入式探測攻擊和非侵入式圖像攻擊的破解。在本協(xié)議中，Device中只存儲了激勵c1和hd1，即使攻擊者破解了c1和hd1，且知道了PUF的結構，由于PUF的不可克隆性，攻擊者仍舊無法獲取密鑰k的值。另外，由于新的密鑰值k2由隨機產(chǎn)生的激勵c2決定，因此，c1和hd1的泄露也不會對新密鑰產(chǎn)生影響。

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

協(xié)議中所產(chǎn)生的新密鑰k2=FE.Gen(f(c2))，因此k2由激勵信息c2所決定。由于每次密鑰更新時，c2是隨機產(chǎn)生的，這就確保了協(xié)議中每一次更新的密鑰值具有獨立性。即使攻擊者知道了某次的會話密鑰值，也無法推算出前一次的會話密鑰。但是，若敵手已知某一時刻的會話密鑰k，由于隨機數(shù)m1與m2是明文傳輸?shù)?，那么敵手也可以計算?個偽隨機數(shù)s1,s2,…,s4。由此可見，往后的密鑰協(xié)商過程，對于敵手是透明的，因此，本協(xié)議并不具有后向安全性。但前面已經(jīng)分析過，本協(xié)議可以抵抗物理攻擊，能有效地保證密鑰k不被攻擊者破解。

（6）抗建模攻擊

建模攻擊（Modeling attack）是Strong PUF面臨的一個主要威脅[13]。但建模攻擊的前提是獲取足夠多的CPRs。在其他協(xié)議中，攻擊者可以通過監(jiān)聽通信信道，或者進行物理攻擊來獲取CPRs[15]。然而，在本協(xié)議中，攻擊者通過探測Device的NVM只能獲取部分激勵c和輔助數(shù)據(jù)hd。而響應值r在信道傳輸時利用偽隨機數(shù)進行了異或加密。因此，攻擊者通過上述攻擊手段是無法獲取所需的CPRs來進行建模攻擊。

（7）抵抗去同步攻擊

去同步攻擊是認證和密鑰交換協(xié)議面臨的一個主要威脅。攻擊者通過各種手段使認證雙方的密鑰更新不同步從而產(chǎn)生失配。本協(xié)議中，當Server完成對Device進行認證后，將會首先更新其保存的密鑰k。如果此時攻擊者發(fā)動去同步攻擊，使Device在后面無法正確接收到Server發(fā)送的數(shù)據(jù)，那么Device將不會更新密鑰k，從而發(fā)生密鑰失配現(xiàn)象。為了應對該威脅，協(xié)議在Server中保存了舊密鑰kold，一旦雙方發(fā)現(xiàn)出現(xiàn)了不同步情況，就使用舊密鑰kold來進行認證和密鑰更新。

5 協(xié)議對比分析

表1給出了本協(xié)議與目前幾種主流的PUF密鑰交換協(xié)議在安全性和實現(xiàn)開銷方面的對比分析。

從中可以看出，本文提出的協(xié)議與現(xiàn)有協(xié)議相比具有更好的安全性。協(xié)議實現(xiàn)了雙向認證與可靠的密鑰交換，能夠抵抗物理探測攻擊與拒絕服務攻擊，具有很好的前向安全性。由于加入了消息認證碼，可以有效抵抗篡改和欺騙攻擊等。又由于PUF的激勵響應對(c,r)經(jīng)過了加密傳輸，可以防止建模攻擊。更重要的是，協(xié)議中的Device在部署之前，Server只需要獲取并存儲Device中PUF電路的一條激勵-響應信息，用于后續(xù)的密鑰更新與交換，避免了因采集大量的激勵-響應信息而帶來的存儲資源的消耗問題。另外，傳統(tǒng)PUF協(xié)議由于服務器端由于存儲了大量的PUF數(shù)據(jù)，一旦信息發(fā)生泄露，會給系統(tǒng)帶來致命的威脅。而本協(xié)議大大減少了服務器端用戶相關數(shù)據(jù)泄露所帶來的風險。此外，本協(xié)議內(nèi)部采用了模糊提取器、真隨機數(shù)產(chǎn)生器和偽隨機函數(shù)，在一次密鑰交換過程中，Device內(nèi)部需要執(zhí)行1次模糊提取運算和3次PRF偽隨機函數(shù)運算，雙方通信量為6L。而Tuyls等人[10]提出的協(xié)議在一次密鑰交換中要執(zhí)行1次模糊提取運算、1次對稱加密運算、2次散列Hash運算和1次消息認證碼MAC運算，通信量也為6L。因此本文提出的協(xié)議在實現(xiàn)成本和計算效率上具有更大的優(yōu)勢。

表1 本文提出協(xié)議與其他幾種協(xié)議的對比分析

6 結束語

本文提出了一種新型的安全認證與會話密鑰交換協(xié)議，實現(xiàn)了雙向認證與可靠的密鑰交換，能夠抵抗物理探測攻擊、建模攻擊與拒絕服務攻擊，具有很好的前向安全性。而且，該協(xié)議中的Device在部署之前，Server并不需要提取并存儲大量的PUF原始數(shù)據(jù)，有效降低了部署難度并提高了安全性，與現(xiàn)有PUF協(xié)議相比安全性更好且實現(xiàn)開銷更低。