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

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

0 引 言

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

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

1 RO PUF原理方法

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

RO PUF是一種典型的硅物理不可克隆函數(shù)，由RO 陣列、選擇器組、計(jì)數(shù)器組和比較器組四個(gè)部分構(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通常是一個(gè)由奇數(shù)個(gè)反相器構(gòu)成的振蕩環(huán)路。輸入的激勵(lì)信號(hào)通過(guò)選擇器從RO陣列中選擇一對(duì) RO 連接到兩個(gè)計(jì)數(shù)器中，兩個(gè)計(jì)數(shù)器分別統(tǒng)計(jì)兩個(gè)RO在一定時(shí)間間隔內(nèi)的振蕩次數(shù)。計(jì)數(shù)結(jié)束后，振蕩次數(shù)被輸入到比較器中，最后由多個(gè)比較結(jié)果構(gòu)成一串二進(jìn)制響應(yīng)比特序列，可作為表征硬件身份的物理指紋[15]。

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

(1)

1.2 熵密度計(jì)算

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

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

(2)

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

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

(3)

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

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

(4)

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

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

(5)

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

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

圖5的RO陣列可拆分為獨(dú)立的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%。這說(shuō)明了在相鄰RO的頻率進(jìn)行比較時(shí)，偏向“1”的可能性更大，并不滿(mǎn)足隨機(jī)性的初步條件。

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

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

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

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

(7)

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

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

(8)

(9)

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

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

(10)

(11)

(12)

3 實(shí)驗(yàn)與結(jié)果分析

3.1 定性比較分析

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

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

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

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

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

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

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

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

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

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

對(duì)于RO PUF響應(yīng)的隨機(jī)性而言，需要經(jīng)過(guò)計(jì)算熵密度來(lái)定量評(píng)估。

3.2 定量比較分析

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

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

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

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

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

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

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

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

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

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

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

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

3.3 復(fù)雜度對(duì)比

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

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

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

4 結(jié)束語(yǔ)

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

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