李昌婷, 章慶隆, 劉宗斌, 荊繼武中國科學院信息工程研究所, 北京 中國00093 中國科學院大學, 北京 中國 00049

1 引言

FPGA 以其靈活可重配的特性越來越受到開發(fā)設計者的青睞, 被應用于密碼算法的硬件實現(xiàn)。在密碼算法的實現(xiàn)和使用過程中, 密碼運算模塊的安全性是一個很重要的因素。密碼運算的安全有一個必不可缺的條件是密鑰的安全, 包括密鑰生成、存儲、使用、銷毀等整個密鑰生命周期管理的安全性。傳統(tǒng)意義上, 可以用受保護的存儲單元來存儲秘密信息, 防止秘密信息被非法讀取, 但是在實際應用中,這種受保護的存儲單元的實現(xiàn)成本和難度都很大。近年來, 針對密鑰的攻擊手法, 尤其是硬件攻擊手段和工具都得到了飛速的發(fā)展, 傳統(tǒng)的密鑰存儲方案面臨著很大威脅。

在這種趨勢下, 需要一種全新的方法來保證密鑰的安全。物理不可克隆方法(Physically Unclonable Function, 以下簡稱PUF)便可以作為物理信任根, 用于解決密鑰的生成和存儲問題。這種新型方法并不是盡量去隱藏硬件中的密鑰, 而是通過硬件電路的隨機物理特征來提取密鑰信息。因為電路物理特征的固有性, 密鑰可以實時生成, 無需存儲。由于在電路制造過程中隨機因素的干擾, 即使在設計上一模一樣的兩塊電路, 制造出來后也存在微小的物理特性差異。物理不可克隆方法就是利用這些內在的隨機制造差異來提取獨一無二的電路指紋從而解決密鑰生成、存儲等問題。

到目前為止, 研究人員已經提出了多種物理不可克隆方法, 例如 SRAM PUF[1,2]、 Arbiter PUF[3,4]、Butterfly PUF[5]、 Glitch PUF[6,7]、 Ring Oscillator PUF[8-14]等。然而, 其中很多 PUF 難以在現(xiàn)有的商用 FPGA 平臺上部署。目前最大的 FPGA 廠商Xilinx 和 Altera 生產的 FPGA 芯片, 其 SRAM 的上電初始值會被強制設置為復位值, 使得在這些FPGA 平臺上難以構建 SRAM PUF。許多其他的PUF 類型, 比如 Butterfly PUF 和Arbiter PUF 則需要非常精細對稱的布局布線, 而這一要求在 FPGA上也是很難實現(xiàn)的。特別的, 構建 Butterfly PUF 的基礎單元需要帶復位信號和清零信號的鎖存器(LATCH), 這種鎖存器只在 Xilinx 的 Virtex-5 系列中提供, 在新版的 Virtex-6,7 系列已不再提供同時帶這兩個信號的鎖存器。

Suh 和 Devadas 首次提出的振蕩環(huán) PUF(Ring Oscillator PUF, 以下簡稱 RO PUF)以其簡潔的架構和優(yōu)良的屬性, 在 FPGA 以及 ASIC 平臺上得到廣泛應用。在 FPGA 平臺上, 通過硬宏單元(Hard-Macro)技術能夠構造出布局布線一樣的振蕩環(huán)模塊, 這給部署 RO PUF 帶來了很大的便利。按照Suh和Devadas[15]提出的最基本的RO PUF結構是通過比較兩個布局布線完全一樣的振蕩環(huán)的頻率的大小來提取1比特的隨機信息。相比其他PUF結構,RO PUF的資源利用率較低, 因此隨著需要提取的隨機信息的數(shù)量的增加, RO PUF 占用的資源也將成倍增加。

PUF響應的熵是衡量某一PUF結構所能夠提取的實體固有隨機物理特征的標準。無論是用于密鑰生成、隨機數(shù)生成或是其他安全應用, PUF響應能否提供足夠的熵至關重要。為了保證PUF響應的熵滿足應用的安全需求, 相關研究工作主要致力于以下三個方面:

首先由于PUF響應序列的分布是由非常復雜混沌的物理過程所決定, 所以往往難以精確計算其中的熵。一些如文獻[16-18]的研究試圖通過統(tǒng)計特征來建立某一 PUF結構簡化的底層元件模型, 從而推導出該 PUF響應的分布表達式, 進而計算出響應中的熵。

因為PUF響應是帶噪的且分布不一定足夠均勻,所以在PUF的應用中常引入模糊提取器。模糊提取器一般由一個安全概略(Secure Sketching)和一個隨機提取器(Randomness Extractor )組成, 前者用于糾正帶噪的響應, 后者則從糾正后的 PUF響應中提取更為隨機的序列。然而進行模糊提取過程也引入了新的熵損失的風險, 因此有許多研究也致力于對熵損失情況的分析和估計, 或者模糊提取器的性能評價[19-21]。

還有部分研究則是改造已有的 PUF結構, 甚至提出新型的 PUF結構, 通過提高硬件利用率來保證在一定的資源消耗下 PUF響應能夠提供足夠的熵[22-25]。就RO PUF來說, 如果可以提高振蕩環(huán)的隨機信息的提取率, 那么提取等量的隨機信息消耗的資源就能有效減少。針對這個問題, Habib[22]提出了一種基于可配置 LUT 延遲的RO PUF 來提高從振蕩環(huán)提取的隨機信息的方案, 并在 Xilinx 的Spartan-3E 平臺上, 驗證了該方案的可行性。然而Majzoobi 等人[26,27]指出在 Xilinx Virtex-5 中對可配置 LUT 延遲的分析與 Habib 的實驗現(xiàn)象不符,根據Habib 所說, 由于 FPGA的型號不一樣導致了可配置 LUT 延遲的分布的不同, 這就導致了Habib 方案的局限性。

本文通過可配置的 LUT 搭建振蕩環(huán), 然后利用差分的計算方法提取更細粒度的制造差異, 從而提高兩個振蕩環(huán)所能提取的隨機信息數(shù)量, 同時有效地消除局部環(huán)境噪聲等影響。我們將這種基于差分計算的新型的振蕩環(huán) PUF 命名為深度振蕩環(huán)PUF(Further RO PUF, 簡稱 FROPUF)。為了驗證所提出的方案的有效性, 我們通過仿真計算和實驗測試評估了FROPUF, 評估結果表明 FROPUF 具有良好的可靠性和隨機性。總的來說, 我們在本文中的主要工作如下:

1. 提出了一種簡潔有效的基于高階差分的提取算法來提取隨機信息, 同時該算法可以降低局部噪聲影響提高提取的隨機信息的可靠性。

2. FROPUF 可以從兩個振蕩環(huán)中提取 31 比特的隨機信息, 是Habib方案能夠提取的熵的6倍, 大大提高了單位硬件資源所能提取的響應信息的數(shù)量。

3. 仿真計算和實際測試的結果的一致性表明了FROPUF 的有效性。在常溫27℃ 下, 平均片間距離為49.92%, 平均片內距離為5.10%。

2 RO PUF架構

2.1 RO PUF的概念和基本結構

RO PUF是一種基于傳播延遲的電子PUF。目前最常用的RO PUF的基本架構是Suh 和Devadas[15]提出的, 如圖1所示。在這個架構中RO PUF 由 n個完全一樣的振蕩環(huán)組成, 編號為RO1到ROn, 他們的振蕩頻率分別為fi到fn, 其中 MUX1 和MUX2 是兩個選通器, 通過 挑戰(zhàn)信號, 選出一對振蕩環(huán)ROi和ROj(i1j), 由于內在的制造差異使得fi和fj之間存在隨機差異, 所以在相同時間間隔內計數(shù)器1和計數(shù)器2的計數(shù)值會有所差別, 通過(1)式便能計算得到RO PUF關于挑戰(zhàn)(i,j)的響應rij:

圖1 基本RO PUF原理圖Figure 1 Schematic diagram of basic RO PUF

2.2 PUF的評估體系

評價一個PUF的性能, 需要考慮以下三個性質:不可預測性(Unpredictability), 獨特性(Uniqueness)和可靠性(Reliability)。

? 不可預測性是指即使在觀測了PUF一定數(shù)量的挑戰(zhàn)-響應對的情況下, 敵手猜測未觀測過的挑戰(zhàn)所對應的響應值的難易程度。為保證不可預測性, 一方面 PUF的挑戰(zhàn)-響應集應足夠大, 另一方面, PUF的挑戰(zhàn)-響應行為應該難易被建模和模仿。

? 獨特性是指一個PUF實體與其他同類PUF實體的區(qū)別度。一個好的PUF, 其不同實體對于同一挑戰(zhàn)產生的響應值的區(qū)別應該越大越好。

?可靠性是指在不同次測量中, 同一PUF實體對于同一挑戰(zhàn)所產生的響應差異。由于噪聲的影響,PUF實體對于同一挑戰(zhàn)的每一次響應并不是完全一樣的。為了保證 PUF的可用性, 其可靠性應該越高越好。

2.2.1 可靠性

可靠性可以通過片內距離(intra-distance)來衡量。簡單來說, 片內距離的計算是多次將同一個挑戰(zhàn)信息作用于同一個PUF實體得到的多次響應之間的漢明距離的平均值。雖然我們希望 PUF 的響應是穩(wěn)定不變的, 但是環(huán)境因素, 例如溫度變化、供電電壓浮動等, 都會導致響應出現(xiàn)錯誤。為了評估 PUF的穩(wěn)定性, 設有Npuf個 PUF實體, 對于每個實體分別輸入Nchal個挑戰(zhàn)測量其響應, 每個挑戰(zhàn)測量Nmeas次。如此, 我們便得到Npuf′Nchal′Nmeas個響應序列, 并計算平均片內距離如下:

其中ck表示第k個挑戰(zhàn),(ck)則代表 PUF第i個實體輸入第k個挑戰(zhàn), 在第j次測量時的響應值;HD(g)代表計算兩個響應序列的漢明距離函數(shù)。

2.2.2 獨特性

獨特性可以通過片間距離(inter-distance)來衡量。片間距離就是使用一個相同的挑戰(zhàn)信息作用于不同的 PUF 實體獲得的響應之間的漢明距離。按照2.2.1中的參數(shù)定義, 平均片間距離可按照下式計算:

3 相關工作

3.1 震蕩環(huán)延遲模型

在 J.Cryptology. 2011 上, Maiti等人[28]提出了一種延遲模型來對振蕩環(huán)進行建模分析。振蕩環(huán)的一個環(huán)路延時可以按下式建模:

其中,dAVG對于相同結構的振蕩環(huán)來說是一個相同的延遲數(shù)值;dRAND表示由制造差異導致的隨機延遲;dSYST表示系統(tǒng)差異, 系統(tǒng)差異表示同一芯片上的振蕩環(huán)由位置不同導致的延遲差異。根據(4)式,兩個振蕩環(huán)a和b之間的環(huán)路延時差異可以按照(5)式計算。

從上式可以看出, 1比特響應rab不僅僅和制造差異dRAND有關, 還和系統(tǒng)差異dSYST有關。 Maiti等人指出, 系統(tǒng)差異dSYST是由于振蕩環(huán)的物理位置不同而導致的一種現(xiàn)象: 某一局部的振蕩環(huán)的環(huán)路延時普遍高于或低于另外一個局部的振蕩環(huán)的環(huán)路延時。這種系統(tǒng)差異的存在會降低RO PUF的獨特性。文獻[28]中給出了一種應對措施: 通過比較盡可能相鄰的振蕩環(huán)頻率來提取響應。因為相鄰的振蕩環(huán)具有幾乎相同的dSYST, 這樣就可以保證(5)式計算得到的環(huán)路延時差異由制造差異 DdRAND主導。

3.2 可配置延遲線

在 FPGA 平臺上, 查找表(Look-Up Table, LUT)是主要的可配置延遲單元, 圖2是一個 3 輸入 LUT的示意圖。 LUT 由 SRAM 單元和樹形結構的選通器組成。SRAM 單元用來存儲預設功能值, 樹形結構的選通器用來選擇特定 SRAM 單元到輸出口。

圖2 可配置延遲單元——LUTFigure 2 Programmable delay lines of LUT

一個 LUT 可以例化成一個反相器, 它的輸出端 O 是輸入端A1的取反值, 另外兩個輸入端A2和A3配置的值對輸入端A1和輸出端 O 的邏輯關系沒有影響。在 CHES 2011 中, Majzoobi等人[27]利用 LUT 的延遲配置來實現(xiàn)超細粒度的路徑延遲控制。該方案通過改變 LUT 的輸入信號來調節(jié)路徑傳播延遲。在圖 2中, 雖然輸入端A2和A3不會改變這個反相器的邏輯值, 但是他們的取值會改變信號從輸入端A1到輸出端 O 的延遲。Majzoobi 等人指出圖 2中, 當A2A3= 00 時,A1到 O 的延時最短, 當A2A3= 11 時,A1到 O的延時最長。

圖3 延遲可配置的五級振蕩環(huán)示例Figure 3 Example of 5-stage delay-configurable ring oscillator

在這個結構基礎上, Habib等人[22]提出了一種基于4輸入LUT的RO PUF結構。這種結構的RO PUF通過比較兩個振蕩環(huán)在相同LUT配置下的頻率,可以由兩個振蕩環(huán)得到8比特響應, 提取到約5比特的熵。但是Habib的方案有一個非常重要的前提, 那就是隨著LUT輸入的變化, 不同振蕩環(huán)的頻率變化應該完全不同, 使得兩個振蕩環(huán)的頻率變化曲線隨機交叉, 如圖(4) 所示。根據 Habib等人的在Spartan-3e上的實驗結果來看, 這個前提是滿足的,該方案的有效性也得到了印證。但是在 Xilinx最新的基于6輸入LUT的FPGA系列(如Virtex-5, Virtex-6,Kintex-7, Zynq-7000等), 這個條件已經不再滿足。根據我們的實驗, 對于不同的震蕩環(huán), 隨著 LUT輸入的變化, 其頻率的變化趨勢趨于一致, 加之不同振蕩環(huán)的系統(tǒng)差異較大, 使得不同震蕩環(huán)的頻率變化曲線很少有交叉, 如圖(5)所示(以 Zynq-7000為例)。也就是說, 如果我們知道在 LUT某個輸入下RO1比RO2的頻率大, 那么在 LUT其它輸入情況下RO1的頻率也總是大于RO2的。在這種情況下, Habib等人的方案便不再有效。

4 RO PUF建模分析

結合 Majzoobi等人[26,27]提出的振蕩環(huán)的延遲模型以及LUT可配置延遲模型, 本章提出了一種可配置延遲振蕩環(huán)PUF模型。首先, 我們根據(6)式來對振蕩環(huán)l的環(huán)路延時進行建模。

圖4 Habib方案中不同振蕩環(huán)在不同LUT配置下的頻率變化趨勢Figure 4 Frequency’s changing pattern of different ring oscillators in Habib’s scheme

圖5 Zynq-7000評估板上的不同振蕩環(huán)在不同LUT配置下延時變化趨勢示例Figure 5 Frequency’s changing pattern of different ring oscillators on Znyq-7000 evaluation boards

其中,dAVG是振蕩環(huán)的理論環(huán)路延時, 對于所有相同結構的振蕩環(huán)來說是一樣的;表示第l個振蕩環(huán)的 LUT 為配置j時, 由于制造因素導致的延遲差異;表示系統(tǒng)差異導致的延遲差

異。對于一個振蕩環(huán), 當使用兩個不同的 LUT配置時候, 會產生兩個系統(tǒng)差異參數(shù)和,由于是同一個振蕩環(huán), 這兩個系統(tǒng)差異參數(shù)極其接近, 因此在(6)式中,和可以簡化為dSYST(l), (6)式就可寫成:

假如總共有L個振蕩環(huán), 當每個振蕩環(huán)的 LUT配置都為j時, 由于制造因素導致的延遲差異就有L個值:在HOST 2011 和 ReConFig 2008中, 文獻 [14,29]通過實驗表明這些值的分布接近高斯分布。圖6展示了 3000個振蕩環(huán)在不同LUT輸入下的頻率分布圖。可見其分布形狀也類似一個高斯分布的形狀, 且對于不同的LUT輸入, 分布的均值略有差異, 方差相似。在第4小節(jié), 將詳細描述我們的實驗過程。因此, 在我們的建模分析中, 我們假設所有振蕩環(huán)在同一LUT輸入下的延遲服從均值不同, 方差相等的高斯分布,如(8)式所示:

圖6 不同LUT輸入下3000個振蕩環(huán)的頻率分布圖Figure 6 Frequency’s distribution of 3000 ring oscillators with different input values of LUT

也就是說, 隨機變量dRAND(j)服從一個均值分別為mj, 標準差為s的正太分布。在6輸入的LUT基礎上構建振蕩環(huán), 有5個輸入與邏輯無關但可以影響環(huán)路延時, 因此共有 25= 32種不同的配置, 我們將每種配置下振蕩環(huán)的制造差異延時分別看作一個隨機變量, 則共有32個服從(8)式正太分布的隨機變量。

4.1 二階差分算法概述

根據上述描述, 對于L個振蕩環(huán), 配置信息從“00000”變化到 “11111”, 總共有 32′L不同的, 可以寫成式子(9)。本章首先提出了一種簡潔的基于二階差分算法的方法來提取 PUF 響應。

基于二階差分的提取算法可以分為以下兩步,以L個振蕩環(huán)為例進行說明:

1) 計算振蕩環(huán)延時的一階差分: 對于振蕩環(huán)l,依次計算相鄰配置的延時的差值:

2) 計算振蕩環(huán)延時的二階差分: 對于兩個振蕩環(huán)A和B(A1B), 計算二階差分值:

最后根據二階差分值得到響應 :

圖7 二階差分計算示意圖Figure 7 Skeleton diagram of the second-order difference method

經過這兩步, 可以從 2 個振蕩環(huán)中獲得 31 比特的響應。基于式子 (9), 一階差分可以按照下面的式子計算得到。

從式子(13)中可以看出, 一階差分計算能夠有效消除系統(tǒng)差異因素dSYST(l)的影響。根據式(9),和都服從高斯分布:

因為這種基于可配置 LUT的振蕩環(huán)中, 其振蕩回路其實是多條延遲路徑的線性組合, 所以同一振蕩環(huán)中對于不同的j, 隨機變量是存在相關性的, 我們假設同一振蕩環(huán)中任意的兩個隨機變量和(1 ≤i1j≤ 3 2)之間的相關系數(shù)是R, 我們可以獲得隨機變量的分布如下式所示。

設是,是。根據隨機變量, 對于不同的振蕩環(huán), 我們假設兩個隨機變量和之間沒有相關性, 因此經過第二步二階差分的計算之后, 我們可以獲得隨機變量的分布如下。

根據式 (17),大于零和小于零的概率相等,所以取 “0” 或者 “1” 的概率相等, 都是 50%。

4.2 二階差分算法分析

從兩個振蕩環(huán)提取更多隨機熵的關鍵就是如何提取更多的制造差異, 而這些制造差異的數(shù)量級往往很小, 甚至小到接近噪聲的。因此, 提取更多熵的方法需要盡最大限度地減小噪聲的影響。

在傳統(tǒng)的 RO PUF 的架構中, 一個 LUT 僅僅被例化成一個反相器, 這樣的反相器只有一個傳播路徑。在可配置延遲線模型中, 當 LUT 被例化成反相器的時候, 對于 LUT 輸入的精細控制使得反相器具有多個傳播延遲。Habib等人[22]想通過控制LUT 的配置信息來提取更多的響應。然而在 Xilinx Virtex-5, 6, 7 系列 FPGA 中, 由于系統(tǒng)差異較大且LUT 不同配置信息導致的不同傳播延遲變化趨勢趨于一致, 在這些 FPGA 平臺上比較兩個振蕩環(huán)的不同配置信息下的傳播延遲, 雖然可以獲得 32 比特的響應, 但是能夠提取到的熵卻遠小于32比特。

在二階差分算法中, 將相同的振蕩環(huán)的不同延遲配置的延遲做一階差分計算, 計算結果可以很大程度上消除系統(tǒng)差異導致的負面影響。因為同一個振蕩環(huán)在不同配置下, 其系統(tǒng)差異是非常接近的。一階差分的計算結果可以看成是進行比較的兩個傳播路徑的制造差異組合, 二階差分計算的結果就表示兩個振蕩環(huán)之間的這個制造差異組合的差異。按照第 4.1節(jié)中二階差分算法概述的兩步計算, 響應由(16) 式的正負號決定。A,B表示不同振蕩環(huán)的序號,j表示LUT的配置。

式(16)可以改寫成下面這個形式:

從式子(19)中可以看出二階差分算法本質上是提取 LUT配置為j時振蕩環(huán)A、B的制造差異與LUT配置為j+1 時振蕩環(huán)A、B的制造差異的差異,也就是制造差異的差異。從圖(8)中可以看出, 不同振蕩環(huán)對的二階差分值的變化與圖(5)中的不同振蕩環(huán)的延時變化相比更加散亂隨機, 因此可以比Habib等人提出的方法提取更多的熵。

圖8 Virtex-6上不同振蕩環(huán)延時的二階差分變化趨勢Figure 8 Changing patterns of the second-order difference of different ring oscillators on Virtex-6

除此之外二階差分算法還能從一定程度上增強PUF 響應的可靠性。為了降低環(huán)境變化對響應可靠性的負面影響, Gassend[30]提出了通過比較兩個振蕩環(huán)的頻率來產生 1 比特響應的方法。二階差分算法不僅繼承了這種方法的優(yōu)點, 降低環(huán)境變化帶來的影響, 還能很有效的消除系統(tǒng)差異導致的負面作用。

4.3 高階差分方法

我們通過二階差分的方法可以提取兩個振蕩環(huán)更細粒度的制造差異, 那推廣到更高階差分是否可以提取更多的差異呢？將二階差分方法推廣到高階差分, 有兩個問題必須解決: 第一個是同一階響應相鄰比特的相關性問題; 第二個問題是上一階的響應會泄露下一階響應的熵。

4.3.1 消除相鄰響應比特的相關性

為了簡化說明我們假設有兩個相同的有三種環(huán)路延時的振蕩環(huán), 按照二階差分算法我們可以從這兩個振蕩環(huán)提取2比特的響應和。根據(11)式:

同樣地有:

忽略Dd1, Dd2, Dd3相等的情況, 結合(12)式,我們來討論為不同取值時, Dd1, Dd2, Dd3的大小所有可能的組合情況。

當= 0 0時, 有 Ddd且 Ddd,1223此時的大小排列只有(小, 中, 大)一種可能;

當= 1 1時, 有 Ddd且 Ddd, 此時1223的大小排列只有(大, 中, 小)一種可能;

當= 1 0時, 有 Ddd且 Ddd, 此時1223的大小排列可能有(大, 小, 中)和(中,小, 大)兩種可能;

圖9 高階差分計算示意圖Figure 9 Skeleton diagram of the proposed high-order difference method

因此按照4.1所述二階差分算法得到的31比特響應, 其香農熵低于31比特。

從直觀上我們很容易理解這種相關性的來源。=1 說明 Dd1d2, 從直覺上這意味著 Dd2很可能是一個比較小的值, 所以使得 Dd2d3的概率更有可能大于 Dd2>Dd3的概率, 反之亦然。這種直觀的推理與我們上面具體的數(shù)值分析也是相一致的。正是因為計算二階相鄰差分值和都用到了同一個因子Dd2, 所以無論知道了還是, 都多少泄露了另一個響應比特的信息。所以為了消除這種相關性, 同一個因子就不能用于計算兩個或兩個以上的響應比特。

4.3.2 消除鄰階響應的信息泄露

顯然, 我們不能像(22)式那樣直接將 4.1的二階差分方法推廣到高階差分計算, 這會使得相鄰兩階的響應泄露對方的信息。

其中abs(·)表示取絕對值運算。再結合之前消除相鄰比特相關性的方法, 我們提出了新的利用高階差分方法計算響應的方案如下:

1) 對于兩個振蕩環(huán)A和B(A1B), 先計算它們的1一階差分值:

2) 計算二階差分:

3) 計算其3到6階差分值:

4) 計算2階到6階響應值:

其中, 2≤i≤6, 1 ≤ j ≤ 6 4/2i。最后我們將每一階的響應值合在一塊作為最終的響應值, 共計31比特:

4.4 高階差分算法分析

令 Z = X1-X2, 則Z的分布有:

代入(28)式得:

所以 X1-X2和 X3-X4是獨立同分布的。

因為X和Y同分布, 所以有:

代入(29)式, 有:

因為 P (X = Y )很小, 所以忽略X=Y的概率, 有:

5 評估實驗

5.1 仿真

為了驗證整體方案的正確性和有效性, 我們在4.1中提到的延時模型的基礎上進行了一系列的仿真和實驗。需要指出的是仿真參數(shù)的采集和實驗均是在約27℃下的室溫進行。

所謂的制造差異一般可以分成系統(tǒng)差異和隨機制造差異。系統(tǒng)差異主要受到芯片上的位置的影響。例如, 在 RO PUF 的架構中, 系統(tǒng)差異導致的是一個區(qū)域的振蕩環(huán)的頻率平均要比另一個區(qū)域的要高,我們設系統(tǒng)差異造成的環(huán)路延時差異dSYST服從高斯分布:

而隨機制造差異則和振蕩環(huán)的空間位置無關,如4中分析, 我們假設所有振蕩環(huán)在LUT相同配置下的延遲服從均值不同, 方差相等的高斯分布, 如(8)式所示。

除此之外, 因為電路噪聲的影響, 每次測量同一振蕩環(huán)在同一LUT輸入下的計數(shù)值也是不相同的,我們設電路噪聲服從高斯分布:

仿真所需要的這些參數(shù)值都是通過在 Zynq-7000系列評估板進行實驗并統(tǒng)計得到的, 獲取的參數(shù)值在表1中列出。

表1 實驗獲取的參數(shù)列表Table 1 Parameters acquired from experiment

下面將用一個示例程序來說明我們的模擬生成不同振蕩環(huán)實體環(huán)路延時并生成響應比特串的過程。首先, 我們需要設置幾個參數(shù):

表2 設置參數(shù)列表Table 2 Parameter settings

代入參數(shù), 通過下面這個程序, 我們便可以模擬生成用于仿真分析的振蕩環(huán)環(huán)路延時d(i,j,k), 并根據提出的高階差分方法計算得到各階響應比特其中2≤order≤ 6 。

5.2 實驗

我們在20塊Virtex-6和30塊 Zynq-7000 系列FPGA評估板上分別進行了實驗。這兩款FPGA尤其是 Zynq-7000系列, 均是Xilinx較新的商用 FPGA,且因為3.2中所述原因, Habib的方案在這兩個系列的FPGA上均不能有效地提取熵。

我們在每一塊FPGA上分別例化了56個振蕩環(huán)。每一個振蕩環(huán)包含 15個反相器和一個作為使能開關的與門, 其理論環(huán)路延時為 9.70ns。所有的反相器和與門都是由6輸入的LUT實現(xiàn)的。圖(10)展示了我們整個實驗數(shù)據采集系統(tǒng)的結構。每一個振蕩環(huán)都有一個對應的計數(shù)器與參考計數(shù)器同步進行計數(shù)。所有的計數(shù)結果都會通過 UART發(fā)送給電腦進行進一步的處理和分析。方便起見, 所有的響應計算和分析過程都是在電腦上離線處理, 硬件只是負責采集數(shù)據。

圖10 實驗系統(tǒng)架構Figure 10 Experimental structure

為了盡可能排除其他干擾使得制造差異來主導振蕩環(huán)的環(huán)路延時差別, 我們利用 Xilinx開發(fā)套件提供的XDC Macro技術, 來保證例化的振蕩環(huán)的結構和布線完全一致。XDC Macro是一個物理約束對象, 可以在電路實現(xiàn)階段進行相對布局布線。通過這一技術, 我們輕松實現(xiàn)了56個振蕩環(huán)中15個反相器和一個與門的相對布局。在Xilinx的FPGA中有兩種邏輯單元 SLICEL和 SLICEM, 其區(qū)別在于SLICEM型LUT可以被用作分布式RAM和移位寄存器。為了保證所有振蕩環(huán)都是一樣的, 我們將振蕩環(huán)都用SLICEL型LUT實現(xiàn)。我們使用的FPGA中每個單元有4個 LUT, 每個振蕩環(huán)需要 16個LUT,占4個單元。圖(11)是我們進行布局時的截圖。表3列出了我們的硬件占用情況。

圖11 振蕩環(huán)在FPGA上的實現(xiàn)和布局Figure 11 Layout of ring oscillators on FPGA

表3 硬件資源消耗情況Table 3 Hardware consumption

5.3 仿真和實驗結果

利用表 1中實驗采集得到的參數(shù), 我們仿真生成了840對振蕩環(huán), 我們假設對每個振蕩環(huán)測量了200次,然后根據提出的高階差分算法來計算響應序列。我們將一對振蕩環(huán)看做一個FROPUF實體, 也就是令Npuf=80, 所以對于這個PUF只有一個挑戰(zhàn)Nchal=1。將設置的參數(shù)和仿真結果分別代入(1)式和(2)式, 我們得到平均片內距離是4.46%, 平均片間距離是50.08%。片內和片間距離的分布分別如圖(12)和圖(13)所示:

圖12 根據Zynq-7000評估板上獲取參數(shù)仿真所得片內距離分布圖Figure 12 Intra-distance distribution of simulation data based on parameters acquired on Zynq-7000

圖13 根據Zynq-7000評估板上獲取參數(shù)仿真所得片間距離分布圖Figure 13 Inter-distance distribution of simulation data based on parameters acquired on Zynq-7000

根據Zynq-7000系列評估板上的實驗結果, 我們得到平均片內距離為 5.10%, 平均片間距離為49.92%。片內和片間距離的分布分別如圖(14)和圖(15)所示, 其中紅色曲線為仿真結果的擬合, 可以看到實驗結果和仿真結果基本一致, 從而驗證了所提出的模型的正確性。

同時作為比較, 我們在Virtex-6系列評估板上進行實驗得到的平均片內距離為8.39%, 平均片間距離為49.40%。其分布圖如圖(16)和(17)所示。

圖14 Zynq-7000評估板上實驗所得片內距離分布Figure 14 Intra-distance distribution of experimental data acquired on Zynq-7000

圖15 Zynq-7000評估板上實驗所得片間距離分布Figure 15 Inter-distance distribution of experimental data acquired on Zynq-7000

圖16 Virtex-6評估板上實驗所得片內距離分布Figure 16 Intra-distance distribution of experimental data acquired on Virtex-6

圖17 Virtex-6評估板上實驗所得片間距離分布Figure 17 Inter-distance distribution of experimental data acquired on Virtex-6

通過比較我們看到, 所提出的高階差分方法在Xilinx不同系列的 FPGA上得到的結果差別并不是很大。Virtex-6系列上得到的響應序列的穩(wěn)定性相比Zynq-7000系列的差一些, 但隨機性基本相當。

6 進一步討論

基于實驗數(shù)據, 我們還統(tǒng)計了實驗所得響應序列中每個比特為0和為1的概率, 并代入(31)式計算得到響應的香農熵為30.85比特

表4 與其他RO PUF結構的性能比較Table 4 Performance comparison with other RO PUFs

與現(xiàn)有的其他方案相比, 我們的方案大大提高了從單位振蕩環(huán)中提取熵的效率, 具體對比情況如表4所示。

觀察表 4會發(fā)現(xiàn), 我們的方案相比其他方案的平均片內距離較高, 其原因可以由圖(18)加以說明。圖(18)分別統(tǒng)計了各階響應的平均片內距離, 可見平均片內距離幾乎隨響應的階數(shù)呈線性增長。這是因為隨著差分階數(shù)越來越高, 我們所提取的環(huán)路延時的差異的粒度越來越細, 這也意味著制造差異的數(shù)量級越來越小, 以至于電路噪聲的影響逐漸占了主導。所以, 通過這種高階差分的方法來計算RO PUF的響應也不是階數(shù)越高越好。當能夠提取到的制造差異粒度與電路噪聲相當時, 得到的響應比特更多的是隨機的電路噪聲的反映, 所以穩(wěn)定性難以保證。

不過就我們當前的方案來說, 通過結合 6階差分結果得到的響應序列, 其平均片內距離都低于10%, 這在目前已有的糾錯技術下是完全能夠接受的。如R. Maes在文獻[16]中提出的軟決策糾錯方案, 就能夠在較小的硬件消耗下以低于 1 0-6的失敗率糾正平均比特錯誤率為15%的PUF響應序列中所有的出錯比特位。

圖18 平均片內距離與差分階數(shù)的關系Figure 18 The relationship between average intra-distance and differential orders

7 結論

本文基于 LUT 的細粒度控制提出了一種新型的基于振蕩環(huán)的物理不可克隆方法來提取更多的制造差異。同時, 利用高階差分提取計算方法, 可以很巧妙地降低系統(tǒng)差異和環(huán)境波動帶來的負面影響。根據 Zynq-7000評估板上的實驗結果, 在 27℃環(huán)境下, 從兩個振蕩環(huán)中提取到的31比特響應的平均香農熵為30.85比特, 平均片間距離為49.92%, 平均片內距離為5.10%, 證明了這種高階差分算法提取熵的有效性。同時, 仿真結果與實驗結果的一致性也證明了我們所提出的模型和高階差分算法的正確性。

[1]Pol Van Aubel, Daniel J. Bernstein, and Ruben Niederhagen. “ Investigating SRAM PUFs in large CPUs and GPUs”. In5th International Conference on Security, Privacy, and Applied Cryptography Engineering(SPACE), pp. 228–247, 2015.

[2]Mafalda Cortez, Said Hamdioui, and Ryoichi Ishihara. “Design dependent SRAM PUF robustness analysis”. In16th Latin-American Test Symposium(LATS), pp. 1–6, 2015.

[3]Takanori Machida, Dai Yamamoto, Mitsugu Iwamoto, and Kazuo Sakiyama. “Implementation of double arbiter PUF and its performance evaluation on FPGA”. In20th Asia and South Pacific Design Automation Conference(ASP-DAC), pp. 6–7, 2015.

[4]Cheng Wei Lin and Swaroop Ghosh. “A family of Schmitt- Trigger-based arbiter-PUFs and selective challenge-pruning for robustness and quality”. InIEEE International Symposium on Hardware Oriented Security and Trust(HOST), 2015.

[5]Kumar S., Guajardo J., Maes R., Schrijen G., and Tuyls P. The Butterfly PUF Protecting IP on Every FPGA. In IEEE International Symposium on Hardware-Oriented Security and Trust (HOST),2008.

[6]Anderson J. “A PUF Design for Secure FPGA-based Embedded Systems”. InAsia and South-Pacific Design Automation Conference(ASP-DAC), pp. 1–6, 2010.

[7]Shimizu K., Suzuki D., and Kasuya T. “Glitch PUF:Extracting Information from Usually Unwanted Glitches”. InIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2012.

[8]Filip Kodytek and Robert Lorencz. “Proposal and Properties of Ring Oscillator-Based PUF on FPGA”.Journal of Circuits, Systems, and Computers, 25, 2016.

[9]Yuan Cao, Le Zhang, Chip-Hong Chang, and Shoushun Chen. “A Low Power Hybrid RO PUF with Improved Thermal Stability for Lightweight Applications”.IEEE Trans. on CAD of Integrated Circuits and Systems, 34:1143–1147, 2015.

[10]Robert Lorencz Filip Kodytek. “A Design of Ring Oscillator Based PUF on FPGA”. In18th IEEE International Symposium on Design and Diagnostics of Electronic Circuits & Systems(DDECS), 2015.

[11]Md. Tauhidur Rahman, Domenic Forte, Fahim Rahman, and Mark Tehranipoor. “A pair selection algorithm for robust RO-PUF against environmental variations and aging”. InIEEE InternationalConference on Computer Design(ICCD), 2015.

[12]Phuong Ha Nguyen and Durga Prasad Sahoo and Rajat Subhra Chakraborty and Debdeep Mukhopadhyay. “Efficient attacks on robust ring oscillator PUF with enhanced challenge-response”. InProceedings of the Design, Automation & Test in Europe Conference & Exhibition(DATE), pp. 641–646, 2015.

[13]Chi-En Daniel Yin and Gang Qu. “LISA: Maximizing RO PUF’s Secret Extraction”. In Proceedings ofthe 2010 IEEE International Symposium on Hardware-Oriented Security and Trust(HOST),pages 100–105, 2010.

[14]Abhranil Maiti, Jeff Casarona, Luke McHale, and Patrick Schaumont. “A Large Scale Characterization of RO-PUF”. In Proceedings ofthe 2010 IEEE International Symposium on Hardware-Oriented Security and Trust(HOST), 2010.

[15]G.E. Suh, S. Devadas, “Physical Unclonable Functions for Device Authentication and Secret Key Generation”,Asia and South Pacific Design Automation Conference(ASP-DAC), pp. 9-14, 2007.

[16]R. Maes, “Physically Unclonable Functions: Constructions, Properties and Applications”, Springer Publishing Company, Incorporated, 2013.

[17]R.V.D. Berg, “Entropy analysis of Physical Unclonable Functions”,white paper, available on line at: http://alexandria.tue.nl/extra1/afstversl/wsk-i/vandenberg2012.pdf

[18]R.V.D Berg, B. Skoric, V.V.D. Leest, “Bias-based modeling and entropy analysis of PUFs”,Acm Trusted, 2013, pp. 13-20.

[19]P. Koeberl, J. Li, A. Rajan, W Wu, “Entropy Loss in PUF-based Key Generation Schemes: The Repetition Code Pitfall”, IEEE 2014, pp. 44-49, 2014.

[20]H. Kang, Y. Katashita, M. Hagiwara, K. Lwamura, “Performance A nalysis for PUF Data Using Fuzzy Extractor”, Lecture Notes in Electrical Engineering, pp.277-284, 2014.

[21]D. Merli, D. Schuster, F. Stumpf, G. Sigl, “Side-Channel Analysis of PUFs and Fuzzy Extractors”, Lecture Note in Computer Science,pp. 33-47, 2011.

[22]B. Habib, K.Gaj, J.P. Kaps, “FPGA PUF Based on Programmable LUT Delays”,Euromicro Conference on Digital System Design(DSD), pp. 697-704, 2013.

[23]Q. Chen, G. Csaba, P. Lugli, U Schichtmann, U. Ruhrmair, “The Bistable Ring PUF: A New Architecture for Strong Physical Unclonable Functions”, IEEE International Symposium onHardware-oriented Security & Trust, pp. 134-141, 2011.

[24]D.E. Holcomb, K. Fu, “Bitline PUF: Building Native Challenge-Response PUF Capability into Any SRAM”, Springer Berlin Heidelberg, pp. 510-526, 2014.

[25]C.E. Yin, G. Qu, “LISA: Maximizing RO PUF's Secret Extraction”,IEEE International Symposium onHardware-oriented Security &Trust, pp. 100-105,2010.

[26]Majzoobi Mehrdad, Koushanfar Farinaz, and Devadas Srinivas.“FPGA PUF using programmable delay lines”. InIEEE International Workshop on Information Forensics and Security(WIFS), pp.1–6, 2010.

[27]Majzoobi Mehrdad, Farinaz Koushanfar, and Srinivas Devadas. “FPGAbased true random number generation using circuit metastability with adaptive feedback control”. InCryptographic Hardware and Embedded Systems(CHES),pages 17–32, 2011.

[28]Maiti A. and Schaumont P. “Improved Ring Oscillator PUF: An FPGA friendly Secure Primitive”.Journal of Cryptology, pp. 24:375–397, 2011.

[29]Knut Wold and Chik How Tan. “Analysis and Enhancement of Random Number Generator in FPGA Based on Oscillator Rings”.InInternational Conference on Reconfigurable Computing and FPGAs, 2008.

[30]Gassend B., Clarke D., van Dijk M., and Devadas S. Silicon“Physical Random Functions”. InACM Conference on Computer and Communications Security(CCS), pp. 148–160, 2002.