一種基于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協議相比安全性更好且實現開銷更低。