基于多項式擬合頻率重構(gòu)的物理不可克隆函數(shù)優(yōu)化*

黎幫梅，陳懷新，劉小宇，王成剛，李思奇

(1.電子科技大學(xué) 資源與環(huán)境學(xué)院，成都611731；2.中國西南電子技術(shù)研究所，成都610036)

0 引 言

近年來硬件安全不斷受到挑戰(zhàn)，硬件保護(hù)技術(shù)獲得了研究者更多的關(guān)注，例如比特流配置加密技術(shù)[1]。但由于配置比特流需要引入額外的解密單元，所以導(dǎo)致了額外的硬件和功率開銷。此外，解密的密鑰常常被存儲在非易失性存儲器中，在解密過程中容易被竊取，攻擊者可以輕松獲得配置數(shù)據(jù)[2]。在芯片領(lǐng)域，現(xiàn)場可編程門陣列(Field Programmable Gate Array，F(xiàn)PGA)憑借其可編程靈活性高、開發(fā)周期短、并行計算效率高的顯著優(yōu)勢在各領(lǐng)域得到了廣泛應(yīng)用。因此，采用FPGA的物理特性參量進(jìn)行硬件加密算法的設(shè)計是研究硬件安全保護(hù)的有效手段。物理不可克隆函數(shù)(Physical Unclonable Function，PUF)是一種從制造變化中提取信息的電路，可以利用集成電路制造過程的固有變化為各種與安全相關(guān)的應(yīng)用生成安全的密鑰[3]，攻擊方若想篡改密鑰，必須破壞其硬件物理特征，故可以有效防止篡改。PUF大致可分為三類[4]：非電子類、模擬電子類、數(shù)字電路類。在數(shù)字電路PUF中，仲裁器PUF[5]的布局布線要求高對稱性，基于靜態(tài)隨機(jī)存取存儲器(Static Random Access Memory，SRAM)的PUF[6]每次生成響應(yīng)都要求重啟一次電路，而環(huán)形振蕩器(Ring Oscillator，RO) PUF[7]克服了前兩者的缺點，能夠靈活地應(yīng)用于信息安全領(lǐng)域[8]。因此，RO PUF一直是硬件安全領(lǐng)域的研究熱點。

在RO PUF的多個性能指標(biāo)中，隨機(jī)性能夠衡量PUF生成的密鑰是否足夠安全，而熵密度是表征隨機(jī)性好壞的重要度量標(biāo)準(zhǔn)[9]。目前，針對RO PUF隨機(jī)性優(yōu)化的研究主要分為兩個方向：一是在頻率產(chǎn)生后對頻率進(jìn)行處理；二是改進(jìn)RO PUF的結(jié)構(gòu)從而直接改變原始頻率，如使用非線性組合生成器結(jié)構(gòu)[10]，但是這樣的方法對于硬件資源的需求更大，且實現(xiàn)復(fù)雜度更高。因此，本文選擇從第一個方向入手對隨機(jī)性進(jìn)行優(yōu)化。該方向上的典型方法主要有隨機(jī)補丁混合方法(Radom Path Mix,RPM)[11]和基于回歸的熵蒸餾法[12]，但存在不足之處：RPM通過外在添加隨機(jī)矩陣對RO陣列原始頻率分布進(jìn)行改變，因此這種方法過于依賴隨機(jī)矩陣；基于回歸的熵蒸餾法將殘差項作為被比較的對象，雖然表現(xiàn)出了與原始頻率分布相似的分布特征，但隨機(jī)性優(yōu)化能力并不突出。針對以上問題，本文提出一種頻率重構(gòu)的方法，生成具有高隨機(jī)性響應(yīng)的RO PUF，并采用熵密度進(jìn)行評估。

1 RO PUF原理方法

1.1 RO PUF的電路結(jié)構(gòu)及比較策略

RO PUF是一種典型的硅物理不可克隆函數(shù)，由RO 陣列、選擇器組、計數(shù)器組和比較器組四個部分構(gòu)成[13]，RO PUF原理的電路結(jié)構(gòu)如圖1所示[14]。

圖1 RO PUF原理電路結(jié)構(gòu)

RO陣列由一定數(shù)量的電路結(jié)構(gòu)完全相同的RO構(gòu)成，RO通常是一個由奇數(shù)個反相器構(gòu)成的振蕩環(huán)路。輸入的激勵信號通過選擇器從RO陣列中選擇一對 RO 連接到兩個計數(shù)器中，兩個計數(shù)器分別統(tǒng)計兩個RO在一定時間間隔內(nèi)的振蕩次數(shù)。計數(shù)結(jié)束后，振蕩次數(shù)被輸入到比較器中，最后由多個比較結(jié)果構(gòu)成一串二進(jìn)制響應(yīng)比特序列，可作為表征硬件身份的物理指紋[15]。

RO PUF比較策略是生成隨機(jī)響應(yīng)的方式，鏈?zhǔn)较噜彵容^[16]是當(dāng)前硬件利用率較高的一種比較策略，也是最常見的一種比較策略。設(shè)有3個相鄰RO，即RO1、RO2、RO3，RO1與RO2相鄰，構(gòu)成一個比較對，RO2與RO3構(gòu)成一個比較對。因此，N個RO構(gòu)成的RO陣列，能夠產(chǎn)生N-1位響應(yīng)[17]。在這種比較策略下，除了鏈?zhǔn)孜驳膬蓚€RO頻率僅被比較1次之外，其他RO的頻率均會被比較2次。響應(yīng)產(chǎn)生的依據(jù)[18]可以表示為

(1)

1.2 熵密度計算

RO PUF產(chǎn)生的響應(yīng)隨機(jī)性可采用熵密度值來定量評估，對RO PUF的攻擊和防護(hù)可以理解為降低和提高響應(yīng)所攜帶熵的過程。因此，計算熵密度[19]通常是在不同的芯片上選擇相同的RO得到的響應(yīng)位為0或1的概率均為0.5。在本文研究中，將區(qū)域中的6列RO等價于6個芯片中的RO陣列。如果相鄰6列RO所產(chǎn)生的響應(yīng)都具備了良好的熵密度，那么在不同芯片上必定會具備更理想的熵密度。

在鏈?zhǔn)较噜彵容^策略中，根據(jù)每列RO的頻率集合生成的密鑰Xl可以表示為

(2)

式中：Xl(r)代表Xl中的第r位，Cntl(m,r)和Cntl(m+1,r)表示生成的Xl中的第r位所使用第m個RO和第m+1個RO的計數(shù)器輸出值。在鏈?zhǔn)较噜彵容^策略中，第m個RO和第m+1個 RO是相鄰的。

對于熵密度計算而言，建立平均響應(yīng)集十分關(guān)鍵。對于每一列第m個RO的平均計數(shù)值Cntavg(m)可以表示為

(3)

式中：M是RO陣列的行數(shù)，N是列數(shù)。

根據(jù)每一列第m個RO的平均計數(shù)值Cntavg(m)生成的平均響應(yīng)集Xavg可以表示為

(4)

式中：Xavg(r)是Xavg的第r位，用于產(chǎn)生Xavg(r)的第m和第m+1個RO的平均計數(shù)值由Cntavg(m,r)和Cntavg(m+1,r)表示。

評估Xl中預(yù)測的每個比特的概率P(r)可以表示為

(5)

式中：P(r)表示X中第r位響應(yīng)可由Xavg成功預(yù)測的概率，⊙為異或操作。

熵密度Hden是隨機(jī)變量統(tǒng)計分布的函數(shù)，表示不確定性大小。熵密度Hden可以表示為

(6)

當(dāng)P(r)接近0.5時，Hden(X)的值將接近最大值0.5，說明PUF更加安全，隨機(jī)性更好。這樣的值將保證在不同F(xiàn)PGA之間相同位置的位之間沒有相關(guān)性[20]。

2 基于多項式擬合的RO頻率重構(gòu)方法

2.1 RO硬宏設(shè)計及其陣列頻率采集分析

本研究在Xilinx Artix 7103 FPGA上進(jìn)行實驗，芯片上共有7 925個可配置邏輯塊(Configurable Logic Blocks，CLB)，1個CLB由2個slice組成，其在芯片上的排列如圖2所示，圖2中的CLB位于CLB資源的左下角。

圖2 CLB與slice的關(guān)系示例圖

RO的硬宏設(shè)計是實現(xiàn)RO電路的第一步。1個slice內(nèi)部有4個邏輯函數(shù)發(fā)生器(或查找表)。1個3階RO由3個反相器組成的回路構(gòu)成，1個反相器將占用1個查找表，那么在同一CLB內(nèi)，1個3階RO的分布主要是兩種情況，即3個反相器均位于1個slice和3個反相器分別以2∶1的比例分布在2個slice中。

3個反相器同在一個slice中，可能出現(xiàn)頻率過高無法正確測量頻率的情況，如圖3所示。在Xilinx Artix 7103 FPGA上進(jìn)行實例化時，實驗數(shù)據(jù)表明占用1個slice的3階RO頻率可達(dá)1 000 MHz，超過了FPGA的最高工作頻率，同時在示波器上跳變范圍較大，難以得到一個穩(wěn)定的頻率值。

圖3 3階RO占用一個slice的硬宏設(shè)計

相反地，占用2個slice的3階RO頻率始終在FPGA的工作頻率內(nèi)，且在示波器上顯示較為穩(wěn)定，因此選擇占用2個slice的3階RO作為本文研究的頻率來源。1個3階RO占用2個slice中的硬宏設(shè)計如圖4所示。

圖4 3階RO占用兩個slice的硬宏設(shè)計

在CLB資源中實現(xiàn)一個50行×6列的3階RO陣列，實測陣列頻率均值分布如圖5所示。

圖5 50行×6列的3階RO頻率分布圖

圖5的RO陣列可拆分為獨立的6列，每一列RO在鏈?zhǔn)较噜彵容^策略下，可得到6×49位響應(yīng)。RO PUF的隨機(jī)性好壞最直接的表現(xiàn)為響應(yīng)中的0和1分布是否均勻，而影響響應(yīng)比特的直接原因就是頻率，相鄰RO的頻率大小比較結(jié)果在鏈?zhǔn)较噜彵容^策略下總是為“1”或者“0”導(dǎo)致了響應(yīng)均勻性較差，進(jìn)而表現(xiàn)為隨機(jī)性較差。6×49位響應(yīng)的均勻性如表1所示。

表1 50行×6列的RO陣列的響應(yīng)均勻性

由表1最后一列中的平均值可以看到，在6組響應(yīng)中，“1”平均占比為53.74%，“0”平均占比為46.26%。這說明了在相鄰RO的頻率進(jìn)行比較時，偏向“1”的可能性更大，并不滿足隨機(jī)性的初步條件。

觀察圖5可以看出，RO的頻率存在一定系統(tǒng)特性，高頻率總是出現(xiàn)在下方，低頻率總是出現(xiàn)在上方，因此推測RO的頻率與所處的物理位置存在一定關(guān)系。若將所選矩形區(qū)域左下方看作坐標(biāo)零點，那么RO的頻率大體上沿y坐標(biāo)軸呈下降趨勢。對于x坐標(biāo)軸，無明顯變化趨勢，但對于不同的x，相同y坐標(biāo)位置的RO的頻率也是不相同的。因此，從行列方向上對頻率進(jìn)行重構(gòu)是我們的著力點。

2.2 基于多項式擬合的頻率重構(gòu)方法

針對相鄰RO頻率具有嚴(yán)重偏向性而帶來的RO PUF隨機(jī)性低的問題，本文提出一種基于多項式擬合的頻率重構(gòu)方法，關(guān)鍵步驟是對每一個RO實測頻率與行列方向的頻率中值的差值進(jìn)行多項式擬合，從而構(gòu)建重構(gòu)項。具體算法處理如下：

首先計算各行RO的頻率中值fmedi和各列RO的頻率中值fmedj。中值的計算公式如下：

(7)

式中：f(1),f(2),…,f(s)以從小到大的順序排列。選擇中值的原因是不受偏大或偏小數(shù)據(jù)的影響，均值則容易受到影響。而硬件實驗中會因為芯片長時間工作或外在環(huán)境的突發(fā)狀況而出現(xiàn)頻率值過高的情況，從而導(dǎo)致某個RO的頻率均值明顯高于實際頻率，所以用它代表全體數(shù)據(jù)的一般水平更合適。

RO的原始頻率值與對應(yīng)行或列的頻率中值的頻率差值矩陣計算公式如下：

(8)

(9)

式中：1≤i≤M,1≤j≤N，M是RO陣列的行數(shù)，N是列數(shù)。

再將行編號和列編號分別作為自變量，將差值矩陣作為因變量進(jìn)行多項式擬合，計算公式如下：

(10)

(11)

(12)

3 實驗與結(jié)果分析

3.1 定性比較分析

3階RO的實例化在軟件ISE 14.7中完成，每個RO的頻率均被測量5次，取其平均值，其平均頻率分布如圖5所示。響應(yīng)采集則在串口程序中實現(xiàn)，在上位機(jī)中存儲起來，便于后續(xù)分析。

選擇圖5中的50行6列區(qū)域的3階RO陣列，設(shè)置1～5階的擬合階數(shù)，對頻率進(jìn)行重構(gòu)，結(jié)果如圖6所示。

圖6 應(yīng)用1～5階擬合的頻率重構(gòu)方法后的頻率分布

由圖6可看出，從1階開始，上半部分的頻率明顯增大，有效減緩了頻率“上低下高”的分布特性。需要注意的是，對于5階而言，得到的新的頻率矩陣雖直觀上看來與原始頻率矩陣相似，但是色度條范圍并不一致，因此基于5階擬合的RO頻率矩陣，相鄰RO頻率差異必然大于原始頻率矩陣。盡管色度條范圍大小不一致造成了這樣的視覺效果，但是從頻率變化趨勢而言，與未重構(gòu)之前的RO陣列的頻率相比仍然相似。通常情況下，攻擊方在獲得多個未經(jīng)重構(gòu)的同一型號芯片后，可掌握芯片上的RO陣列的分布規(guī)律。但是，對于重構(gòu)以后的RO陣列，由于都具有“上低下高”的分布規(guī)律，攻擊方很有可能會誤把重構(gòu)過后的RO陣列當(dāng)做原始RO陣列，從而降低了被攻擊的風(fēng)險。

對比隨機(jī)補丁方混合法和基于回歸的熵蒸餾法，對同一RO陣列任意進(jìn)行5次RPM方法處理，結(jié)果如圖7所示。

圖7 任意5次應(yīng)用RPM方法后的RO陣列頻率分布

由圖7可以看出，RO頻率的分布規(guī)律被打破，甚至呈現(xiàn)“上高下低”的分布規(guī)律?？梢钥吹?，RPM方法使原始RO陣列中的低頻區(qū)域變換為高頻區(qū)域，將高頻區(qū)域換為低頻區(qū)域。若攻擊方在掌握多個原始RO陣列后，觀察其分布規(guī)律為“上低下高”，再觀察RPM方法處理后的RO陣列，得出“上高下低”的分布規(guī)律，顯然與原始分布規(guī)律不同，那么很有可能對RPM方法進(jìn)行建模學(xué)習(xí)，從而實現(xiàn)有效的攻擊。

對同一RO陣列進(jìn)行1～5階的熵蒸餾處理，結(jié)果如圖8所示。

圖8 經(jīng)過1～5階回歸熵蒸餾后的殘差頻率分布

由圖8可以看出，基于回歸的熵蒸餾法有效減緩了原始RO陣列“上低下高”的分布頻率。因為熵蒸餾法得到的是殘差頻率，結(jié)果有正有負(fù)，絕對值大小僅為個位數(shù)，而對應(yīng)位置的RO原始頻率均在400 MHz以上，因此與原始RO陣列頻率比較并無意義。由圖8(b)～(f)對比發(fā)現(xiàn)，不同階數(shù)的熵蒸餾對于分布規(guī)律并無顯著影響。

對于RO PUF響應(yīng)的隨機(jī)性而言，需要經(jīng)過計算熵密度來定量評估。

3.2 定量比較分析

對RO陣列的頻率采用不同階數(shù)的多項式擬合的頻率重構(gòu)方法進(jìn)行處理，再經(jīng)過鏈?zhǔn)较噜彵容^得到響應(yīng)并進(jìn)行熵密度計算，結(jié)果如表2所示。

表2 原始響應(yīng)與1～5階頻率重構(gòu)后的響應(yīng)熵密度

由表2可以看出，在應(yīng)用多項式擬合方法之后的響應(yīng)熵密度都更接近0.5，而1階擬合就可以達(dá)到0.50，而未應(yīng)用隨機(jī)性優(yōu)化方法的響應(yīng)熵密度為0.46，有了明顯的改善。熵密度的大小與多項式擬合時的階數(shù)并無線性關(guān)系，重構(gòu)的頻率并不會因為階數(shù)上升而進(jìn)行同方向的增加或者減少。5個不同階數(shù)的頻率重構(gòu)法得到的熵密度均值為0.50，達(dá)到熵密度的理想值。

對任意5次處理后的RO陣列經(jīng)過鏈?zhǔn)较噜彵容^得到的響應(yīng)進(jìn)行熵密度計算，結(jié)果如表3所示。

表3 原始響應(yīng)與應(yīng)用RPM方法后的響應(yīng)熵密度

由表3可以看出，應(yīng)用RPM方法并不能百分百提高熵密度，甚至?xí)霈F(xiàn)熵密度降低的情況，5次的熵密度均值為0.46。

對經(jīng)過1～5階回歸熵蒸餾處理的RO陣列通過鏈?zhǔn)较噜彵容^得到的響應(yīng)進(jìn)行熵密度計算，結(jié)果如表4所示。

表4 原始響應(yīng)與應(yīng)用1～5階熵蒸餾后的響應(yīng)熵密度

由表4可以看出，熵蒸餾法對于響應(yīng)的熵密度提高僅為2個百分點，均為0.48。同樣地，不同階數(shù)的熵蒸餾并不會導(dǎo)致熵密度呈現(xiàn)對應(yīng)的變化。5個不同階數(shù)的熵蒸餾法得到的熵密度均值為0.48。

比較表2與表3、表4，三種方法的熵密度對比如圖9所示。

圖9 三種方法的熵密度比較

對于基于多項式擬合的頻率重構(gòu)和基于回歸的熵蒸餾法而言，橫坐標(biāo)表示多項式階數(shù)，而對于RPM方法而言，則表示實驗編號?？梢钥闯霰疚奶岢龅姆椒ǖ玫降撵孛芏仁冀K大于其他兩種方法，更接近甚至等于理想值0.5。產(chǎn)生這種結(jié)果的原因在于，本文方法對頻率的重構(gòu)是利用原始頻率來進(jìn)行頻率重構(gòu)的，而RPM方法的頻率改變是基于外在產(chǎn)生的隨機(jī)矩陣的，因此這種方法的隨機(jī)性優(yōu)化能力并不穩(wěn)定?；诨貧w的熵蒸餾法通過對殘差項進(jìn)行比較來獲得響應(yīng)，殘差項完全代替原始頻率值進(jìn)行比較。而不管是幾階多項式，使用本文方法得到的響應(yīng)都具有更高的熵密度。

3.3 復(fù)雜度對比

對本文中的三種算法的復(fù)雜度進(jìn)行仿真，結(jié)果如表5所示。

表5 三種算法的復(fù)雜度仿真結(jié)果

顯然RPM的復(fù)雜度最低，但是 RPM技術(shù)會導(dǎo)致隨機(jī)性更低的響應(yīng)，得不償失。而基于多項式擬合的頻率重構(gòu)方法和基于回歸的熵蒸餾法的仿真時間之比為4∶3，差值僅為1 ms，而前者具有更好的隨機(jī)性優(yōu)化效果，因此在兩者中為最佳選項。

4 結(jié)束語

本文提出了一種利用RO陣列的原始頻率對頻率進(jìn)行重構(gòu)的方法，實驗結(jié)果表明，頻率重構(gòu)之后的RO PUF的熵密度值比原始RO PUF提高了3～4個百分點，熵密度均值為理想值0.50。與RPM方法和基于回歸的熵蒸餾法相比，響應(yīng)熵密度更高，對隨機(jī)性的優(yōu)化效果更好。

接下來將著重研究硬宏設(shè)計中的不同布線布局下的頻率變化，并設(shè)計新的比較策略，從多個方面對隨機(jī)性優(yōu)化進(jìn)行研究。