基于多項式擬合頻率重構的物理不可克隆函數優化*

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

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

0 引 言

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

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

1 RO PUF原理方法

1.1 RO PUF的電路結構及比較策略

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

圖1 RO PUF原理電路結構

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

RO PUF比較策略是生成隨機響應的方式，鏈式相鄰比較[16]是當前硬件利用率較高的一種比較策略，也是最常見的一種比較策略。設有3個相鄰RO，即RO1、RO2、RO3，RO1與RO2相鄰，構成一個比較對，RO2與RO3構成一個比較對。因此，N個RO構成的RO陣列，能夠產生N-1位響應[17]。在這種比較策略下，除了鏈首尾的兩個RO頻率僅被比較1次之外，其他RO的頻率均會被比較2次。響應產生的依據[18]可以表示為

(1)

1.2 熵密度計算

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

在鏈式相鄰比較策略中，根據每列RO的頻率集合生成的密鑰Xl可以表示為

(2)

式中：Xl(r)代表Xl中的第r位，Cntl(m,r)和Cntl(m+1,r)表示生成的Xl中的第r位所使用第m個RO和第m+1個RO的計數器輸出值。在鏈式相鄰比較策略中，第m個RO和第m+1個 RO是相鄰的。

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

(3)

式中：M是RO陣列的行數，N是列數。

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

(4)

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

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

(5)

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

熵密度Hden是隨機變量統計分布的函數，表示不確定性大小。熵密度Hden可以表示為

(6)

當P(r)接近0.5時，Hden(X)的值將接近最大值0.5，說明PUF更加安全，隨機性更好。這樣的值將保證在不同FPGA之間相同位置的位之間沒有相關性[20]。

2 基于多項式擬合的RO頻率重構方法

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

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

圖2 CLB與slice的關系示例圖

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

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

圖3 3階RO占用一個slice的硬宏設計

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

圖4 3階RO占用兩個slice的硬宏設計

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

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

圖5的RO陣列可拆分為獨立的6列，每一列RO在鏈式相鄰比較策略下，可得到6×49位響應。RO PUF的隨機性好壞最直接的表現為響應中的0和1分布是否均勻，而影響響應比特的直接原因就是頻率，相鄰RO的頻率大小比較結果在鏈式相鄰比較策略下總是為“1”或者“0”導致了響應均勻性較差，進而表現為隨機性較差。6×49位響應的均勻性如表1所示。

表1 50行×6列的RO陣列的響應均勻性

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

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

2.2 基于多項式擬合的頻率重構方法

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

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

(7)

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

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

(8)

(9)

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

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

(10)

(11)

(12)

3 實驗與結果分析

3.1 定性比較分析

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

選擇圖5中的50行6列區域的3階RO陣列，設置1～5階的擬合階數，對頻率進行重構，結果如圖6所示。

圖6 應用1～5階擬合的頻率重構方法后的頻率分布

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

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

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

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

對同一RO陣列進行1～5階的熵蒸餾處理，結果如圖8所示。

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

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

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

3.2 定量比較分析

對RO陣列的頻率采用不同階數的多項式擬合的頻率重構方法進行處理，再經過鏈式相鄰比較得到響應并進行熵密度計算，結果如表2所示。

表2 原始響應與1～5階頻率重構后的響應熵密度

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

對任意5次處理后的RO陣列經過鏈式相鄰比較得到的響應進行熵密度計算，結果如表3所示。

表3 原始響應與應用RPM方法后的響應熵密度

由表3可以看出，應用RPM方法并不能百分百提高熵密度，甚至會出現熵密度降低的情況，5次的熵密度均值為0.46。

對經過1～5階回歸熵蒸餾處理的RO陣列通過鏈式相鄰比較得到的響應進行熵密度計算，結果如表4所示。

表4 原始響應與應用1～5階熵蒸餾后的響應熵密度

由表4可以看出，熵蒸餾法對于響應的熵密度提高僅為2個百分點，均為0.48。同樣地，不同階數的熵蒸餾并不會導致熵密度呈現對應的變化。5個不同階數的熵蒸餾法得到的熵密度均值為0.48。

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

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

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

3.3 復雜度對比

對本文中的三種算法的復雜度進行仿真，結果如表5所示。

表5 三種算法的復雜度仿真結果

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

4 結束語

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

接下來將著重研究硬宏設計中的不同布線布局下的頻率變化，并設計新的比較策略，從多個方面對隨機性優化進行研究。