一種面向PUF的模糊提取器設計與實現*

宋敏特,侯凱,茹占強,王爭光,宋賀倫?

(1 中國科學技術大學納米技術與納米仿生學院, 合肥 230026; 2 中國科學院蘇州納米技術與納米仿生研究所, 江蘇 蘇州 215123) (2022年3月11日收稿; 2022年5月9日收修改稿)

硅PUF(silicon physical unclonable function)是指可以響應已有的二進制輸入序列,獲得一個與集成電路物理結構相關的獨立二進制序列的基于硅基集成電路實現的PUF。輸入PUF的二進制序列稱為挑戰,PUF輸出的二進制序列稱為響應,二者合稱為PUF的挑戰-響應對(challenge-response pairs, CRP)。通常使用片內漢明距離(intra-chip hamming distance)衡量PUF對于同一個挑戰信號的可重現性,片間漢明距離(inter-chip hamming distance)衡量PUF之間的差異性。理想的PUF片內漢明距離為0,片間漢明距離是響應二進制序列長度的50%。相比于傳統的efuse等OTP方案存儲密鑰的方式,硅PUF具有不可預測、不可克隆和即時生成等CRP特性,使得搭載PUF的芯片或終端在設備認證、密鑰生成等過程中能夠更有效地抵抗外部攻擊[1-2]。

硅PUF具有多種實現方式。由于制造過程產生的微觀不確定性,相同的電路單元在電路結構上存在微小差異。典型的硅PUF通過耦合具有競爭關系的微觀差異性,使得競爭輸出的數值具有芯片間隨機的特性?；陔娐费舆t特性的硅PUF最為常見的類型是仲裁PUF[3-4]和環形振蕩器PUF[5-6],通過仲裁器判定2個競爭信號抵達的先后順序,獲得PUF的響應。SRAM-PUF[7-8]、DRAM-PUF[9]和觸發器PUF[10]等屬于基于存儲器的PUF。這些方式實現的PUF借助存儲器的電路結構,產生了電壓或者電流的競爭關系,作為直接獲得的二進制響應數據。隨著PUF技術受到的關注度逐漸提高,一些新類型的PUF也開始出現在芯片設計中,比如改進結構的SRAMPUF[11]和基于新型存儲器的RRAM-PUF[12]等。

然而,基于競爭電路參數差異實現的PUF方案中,因為PUF陣列中一些競爭參數差異過小的電路單元,存在一定數量的不穩定位[13]。對于同一個挑戰信號的反復請求,PUF很難做到100%的響應可重現性,極大限制了其在密鑰生成、數據掩碼生成等需要精確重復二進制序列的場景中的應用。對此,Dodis等[14]在2004年提出一種模糊提取器(fuzzy extractor)方案有效解決了這一問題。模糊提取器早期應用于從噪聲隨機源中提取均勻且穩定的隨機字符串,后來被逐步引入指紋、虹膜、人臉識別等生物信息識別的場景中[15-17],也可以用于還原PUF的不穩定位[18]。另一方面,模糊提取器被證明對被動攻擊者具有較好的抵御作用[19-20],可以保障其與PUF結合的整體安全性。模糊提取器還原數據的核心算法是基于糾錯碼(error correction code, ECC)完成的。BCH碼(Bose-Chaudhuri-Hocquenghem Codes)是線性分組碼中循環碼的子類,能夠糾正碼字中的多位錯誤,實現精確譯碼[21]。BCH碼可以對二進制碼進行糾錯,便于在計算機系統中實現,常用于中短碼通信編碼和Flash存儲等場景。因此,PUF的模糊提取方案中也經常借助BCH碼精確譯碼、多位還原、長度可選擇的特性進行實現。

在完成相關RTL(register transfer level)設計后,通常需要對其進行功能驗證。通用驗證方法學(universal verification methodology, UVM)是一種以SystemVerilog語言為工具的驗證平臺開發方法學,其功能特色是具有可重用的組件,搭建的驗證環境具有標準化的層次結構和接口,更適合于大規模驗證[22]。

課題組的前期工作[23]測試了華虹宏力0.11 μm CMOS平臺SRAM PUF不穩定度約為20%,需要搭載大容量的糾錯碼后處理算法保持PUF的可重現性。本文參考了前期工作和類似結構的文獻[24-26]中的測試結果,設計并驗證了一種面向PUF的大糾錯容量模糊提取器。該設計使用最大值冒泡算法,優化了BCH碼譯碼算法中Berlekamp-Massey(BM)算法臨時數據存儲開銷過大的問題,通過對數/反對數表的方案完成BCH碼中的指數計算,可以實現約21.25%的糾錯容量。該芯片在華虹宏力0.11 μm CMOS工藝下制造。測試結果表明,該模糊提取器可以實現預期糾錯能力,維持穩定的PUF挑戰響應功能。

1 算法原理

1.1 模糊提取器

模糊提取器(fuzzy extractor, FE)主要包含生成算法(generation algorithm, GA)和再生算法(regeneration algorithm, RA)2個部分,在使用的時候需要經歷注冊和工作2個階段。如圖1所示,在注冊階段,FE讀取初始二進制序列w輸入GA,獲得輸出數據R和幫助文件H;在工作階段,FE仍然從數據源讀取二進制序列,讀出的數據相比注冊階段的數據可能出現誤差,記為w′,將w′和H輸入RA,可以獲得輸出R′。當w和w′的距離足夠接近的時候,R=R′,從而在工作階段實現數據的再生。模糊提取器在密鑰協商、對稱密鑰生成等場景中均有應用。圖1(b)展示了面向硅PUF的模糊提取器模塊示意圖。在注冊階段,外部輸入挑戰信號x到PUF模塊中,模糊提取器由此獲得PUF的響應信號y進行GA計算,產生幫助文件H在其外部保存;當芯片復位或重新上電以后,PUF模塊可能會產生少量數據的翻轉,這時重新輸入x獲取相同位置的PUF響應y′,同時向RA中導入幫助文件H進行計算,可以將這部分PUF數據還原回初始的數值y。在GA計算時,借助熵源中的部分隨機數據m,糾錯碼通過編碼計算會生成和PUF響應信號y相等長度的數據C,模糊提取器將C和y進行模2加法計算,其結果為幫助文件H;在RA計算時,y′和H模2加計算的結果為包含有一定數量錯誤的C′,由糾錯碼的計算可以還原回C,再和H重新模2加,獲得原始響應y。

圖1 模糊提取器的原理框圖Fig.1 Schematic diagram of fuzzy extractor

1.2 BCH碼

1959年Hocquenghem、1960年Boss和Ray-Chaudhuri分別提出能夠糾正碼字中多個隨機錯誤的循環碼,這種糾錯碼一般以3人名字的首字母合稱為BCH碼。二進制BCH碼的碼字長度通常用n表示,其中包含kbit的信息位和(n-k) bit的校驗位;糾錯的位數用t表示;碼字之間的漢明距離用d表示。

參考團隊此前工作中對于SRAM陣列不穩定位的測試結果和類似結構的測試文獻,我們選用了本源BCH碼并配置其參數為(n,k,t)=(127,15,27),即在信息位為15 bit的時候,通過增加冗余到碼字長度127 bit,可以糾正全碼字中最多27 bit的錯誤。如1.1所述,BCH碼同樣包含編碼和譯碼2個算法,其中編碼計算可以由下式描述：

c(x)=m(x)·xn-k+m(x)·xn-kmodg(x).

(1)

其中：c(x)是以多項式的形式表示糾錯碼的碼字;m(x)在模糊提取器中是來源于熵源的隨機二進制序列,簡稱信息位;g(x)是BCH碼的生成多項式;x的乘積表示二進制序列的移位操作。

對于二進制序列,BCH譯碼算法主要包含3個步驟：計算伴隨式S(x);計算錯誤位置多項式σ(x);求解σ(x)獲得錯誤位置并糾正。在工作模式中重新獲得c′(x)后,需要對其伴隨式S(x)進行求解,將生成多項式的根αi代入接收多項式中進行計算：

r1(αi)n-1=(…(((rn-1(αi)+rn-2)αi+

rn-3)αi+…+r1)αi+r0.

(2)

其中：rj表示c′(x)多項式系數,α表示二元擴展域本原多項式的根。第2個等號后面的合并計算稱為Homer迭代,是一種適合硬件電路迭代計算的公式變形。當所有的伴隨多項式均為0時,說明響應信號y′相比注冊時的y沒有發生變化,若存在非0的伴隨多項式,則需要進行第2步譯碼計算。

第2步計算中最常用的是BM算法。這是一種有限次迭代的算法,其算法步驟如圖2所示,最終計算出錯誤位置多項式σ(x)。每次迭代需要計算關鍵方程的差值d,當d為0時直接進入下一輪迭代判定,d不為0時需要將其代入迭代中進行計算。

圖2 BM算法流程圖Fig.2 Flow chart of BM algorithm

BM算法的L(i)表示在第i次迭代過程中d的階數。在獲得完整的σ(x)后,需要逐位代入c′(x)的多項式系數求解σ(x)的根,這種算法由工程師錢天聞最早提出,故稱為錢搜索算法。當c(x)的第n-l位存在錯誤的時候,代入σ(x)滿足

1+σ1αl+σ2α2l+…+σtαtl=0.

(3)

此時對該位的二進制數據進行翻轉。當c′(x)所有的位都完成上述計算以后,BCH算法完成,得到c(x),經過第2次和幫助文件H(x)模2加后得到PUF的注冊響應數據y。

2 大糾錯容量模糊提取器的實現

2.1 對數/反對數表模塊

在上述方程(1)～(3)中,主要的計算為加法和乘法,在BM算法的迭代計算中有一處除法運算。對于(127,15,27)BCH碼來說,上述計算均為GF(27)有限域的計算。對于加法而言,計算過程和布爾計算的異或邏輯等效,容易在RTL設計中實現;對于有限域乘法和除法,經典的NAND flash譯碼器需要根據BCH碼的本原多項式,設計專用的有限域乘法器和不進行求逆運算的iBM算法實現[26],這些處理方法會在伴隨式求解、BM算法迭代和錢搜索求和中使用。當BCH碼糾錯容量較大時,需要更多數量的乘法器,顯著增加了伴隨式S(x)和BM算法所使用的硬件資源。為解決這一問題,需要將有限域計算轉換到實數域進行處理。α作為本原多項式的根,α及其高次冪構成了有限域中的所有元素。其中α、冪指數(十進制)和α對應的向量(二進制)對照表如表1所示。向量和冪指數的一一對應關系稱為對數/反對數表。在BCH的譯碼器計算過程中涉及有限域乘除法的時候,但對于大糾錯容量的BCH碼而言,由于PUF在實際使用時上位機或系統的挑戰請求少,不需要模糊提取器做流水線處理,因此可以設計對數/反對數表模塊在上述3個譯碼計算模塊之間共享而不會產生沖突。

表1 (127,15,27)的BCH碼對數/反對數表Table 1 (127,15,27) BCH code logarithm/opposition table

如圖3(a)所示,將乘數αm發送到對數表/反對數表模塊中進行處理,其后返回一個可以在實數域中計算的冪指數m,將返回的數值進行實數域計算(m+m=2m),再將計算后的數值送入mod模塊求余數(p=2mmodn),將返回值(result=p)重新輸入對數表/反對數表模塊進行反編譯,重新得到與乘數αm相同格式的最終結果αp。另外,對數/反對數表中向量一列中含有數字0,該值無法用α的正整數次冪表示。此處借助補碼的思想對該行進行處理,令向量0用十進制的127表示,實現了對數/反對數表的補全。對數/反對數表模塊實際上采用組合邏輯電路定義了下述函數

圖3 BCH譯碼算法的框圖Fig.3 Block diagram of BCH decoder

index[alpha[i]]=i.

(4)

其中index函數執行向量轉換為指數的操作,alpha函數表示由指數轉換為向量的操作。在RTL設計過程中,由于BCH算法的參數固定,可以直接采用固定值查表的方法實現。如在BCH譯碼階段求伴隨式計算,方程(2)可以轉換為

(5)

由于r的數值為0或1,上式中的r后第1個“×”在實際電路中為邏輯判斷,r=0時表示此項的乘積不參與求和,對應的電路流程圖如圖3(b)所示。

2.2 BM算法的優化

如圖3所示,在BM算法中需要進行多次迭代計算,當第j次迭代計算的差值結果dj不為0時,需要查找歷史數據中,滿足i-L(i)最大且d不為0兩個條件的第i次,將di和dj代入錯誤位置多項式迭代方程獲得新的錯誤位置多項式。然而,在RTL實現時,如果BCH碼的糾錯能力很強,使用寄存器保存歷史數據d和L會消耗大量的寄存器。

借用冒泡排序的思想可以有效地解決這一矛盾。通過聲明少數寄存器作為臨時存儲池,每當新的dj產生,若此時的j-L(j)更大,則保留此dj,作為下一次d不為0時迭代的di。特殊地,當BM迭代處于第1次時,由于i的初始值為0,則i-L(i)也為0。這種方式極大地減少了寄存器的消耗,在大容量糾錯碼的實現中極為有效。

2.3 頂層接口

經過上述優化,本文實現了一種面向PUF的大糾錯容量模糊提取器,由于芯片設計的需求未搭載AMBA總線,為保證IP后續拓展的易用性,本設計的接口協議采用私有接口協議,使用簡單的valid-ready協議完成127 bit長度的模糊提取器。其接口命名如表2所示。

表2 模糊提取器頂層接口與功能描述Table 2 Fuzzy extractor interface and function description

3 模糊提取器的UVM驗證與結果

3.1 待測模塊基本結構及驗證環境框架

本部分借助UVM驗證框架,面向上述待測模塊(design under test,DUT),構建必要的前處理模塊并搭建完善的驗證環境。如圖4(a)所示,由于模糊提取器模塊主要包括注冊和工作2種功能,借助systemverilog設置了虛線框內的前處理模塊,主要包括5 bit地址譯碼器、臨時存儲(保存幫助文件H)和PUF等。在前處理模塊的基礎上,搭建的驗證環境框架如圖4(b)所示。

驗證框架同樣基于systemverilog搭建,主要由代理模塊(agent)、覆蓋率模塊(coverage)、參考模型(reference model)、計分板(scoreboard)及DUT構成。該驗證環境中agent主要用于模擬上游master的行為推進驗證流程,agent中的驅動(driver)只關注底層邏輯實現,監視器(monitor)監控采樣底層數據組(transaction),傳遞給其他模塊。coverage主要針對DUT中描述的各個工作模式進行覆蓋率檢測,側重不同挑戰信號和響應信號的覆蓋支持。用回調函數(callback)和命令序列列表(command sequence list)進行采樣,整個環境的覆蓋率收集結果寫入同一個日志文件中。參考模型用C語言實現,模擬模糊提取器中各個狀態的行為,將輸出傳遞給scoreboard和DUT響應信號進行比較。本環境使用應用程序接口(application programming interface,API)實現C語言函數在UVM中的調用。Scoreboard主要負責接收agent獲得的DUT響應信號以及參考模型提供的期望響應,并進行比較,得到驗證結果。

3.2 驗證功能點分解

對DUT的功能點分解,需要進行驗證的分項包含：時鐘復位(Clock &Reset)、工作模式驗證和異常檢驗。具體分解如表3所示。

表3 DUT驗證功能點分解列表Table 3 Function list of DUT verification

Clock &Reset主要驗證DUT常規功能點,檢驗該DUT時鐘和復位是否正常。模式驗證的目的是驗證實際場景驗證相關狀態是否可以正常工作(具體分為注冊、工作和debug3種狀態),仿真可能產生的各種真實使用場景,進行隨機狀態驗證。異常檢驗主要模擬實際工作時可能發生的異常狀態,進行檢驗。

3.3 測試用例設計

針對功能點設計測試用例,具體測試用例覆蓋功能點情況如表4所示。通過9個測試樣例對10個功能點進行了全覆蓋。通過查看代碼覆蓋率和功能覆蓋率,改進分析過程,完善RTL代碼,保證語句、狀態機、路徑、信號切換、分支覆蓋率達到標準,功能點全覆蓋。

表4 UVM樣例及覆蓋功能點列表Table 4 List of UVM case and function

3.4 UVM驗證和覆蓋率檢測

此次驗證使用VCS工具對模糊提取器模塊進行UVM驗證,驗證通過后進行覆蓋率收集,其結果在本部分進行展示。

對于UVM回歸驗證,需要對模糊提取器的單個樣例波形示意圖進行描述。圖5(a)對應表3功能點4,在bch_vld和bch_cfg接口同時為高電平時,模糊提取器進入注冊模式;與此同時PUF數據和BCH碼信息位視為有效,進入算法內部進行計算;在Ts時刻產生持續時長為1時鐘周期的bch_ack脈沖信號,此周期中bch_data_out端輸出的helpdata數據有效;外部邏輯在任意Ts’時刻拉低,結束樣例。圖5(b)對應功能點5,bch_cfg保持低電平時,bch_vld拉高使得模糊提取器進入工作模式,此時輸入端的PUF’數據(可能產生變化的PUF數據)和helpdata為有效;在Td時刻產生持續時長為1時鐘周期的bch_ack脈沖信號,此時bch_data_out端輸出的PUF數據有效,該數據的輸出實現了對PUF’數據的還原;外部邏輯在任意Td’時刻拉低,結束樣例圖5(c)對應功能點10。相比較于圖5(b),若模糊提取器計算過程中出現錯誤或者識別到錯誤的位數超出了BCH碼的糾錯能力,則err_num_ovc端口在Te時刻與bch_ack同時輸出1時鐘周期的脈沖,且此時外部邏輯認為bch_data_out數據無效?；谏鲜鰳永采w的UVM回歸驗證的結果表明,模糊提取器的設計能夠滿足預期的功能需求。

圖5 模糊提取器在多種模式下的接口時序圖Fig.5 Interface sequence diagram of fuzzy extractor in multiple modes

代碼覆蓋率主要包括語句覆蓋率、信號切換覆蓋率、狀態機覆蓋率、條件覆蓋率和分支覆蓋率5種類型。語句覆蓋率用于度量代碼行是否執行,所添加的可忽略部分(exclusion)為正常情況下case塊中不會執行的default語句;信號切換覆蓋率主要度量單位變量的01切換是否執行,所添加的exclusion為忽略常數的01切換、忽略設計基于其他考慮使用的多余單位變量等部分。狀態機覆蓋率度量狀態機中訪問過的狀態和切換,添加的exclusion為忽略正常狀態下不會執行的其他狀態與IDLE/DEFAULT狀態之間的跳轉;條件覆蓋率度量條件表達式中所有條件是否都有成立與否發生,通常要求完成全覆蓋;分支覆蓋率度量所有判定的分支是否執行,添加的exclusion主要為忽略default代碼塊所包含的分支。圖6(a)為直接統計的不添加exclusion的代碼覆蓋率,基于設計的可預期情況添加exclusion后的代碼覆蓋率如圖6(b)所示。添加必要的exclusion后,代碼覆蓋率達到100%。

圖6 模糊提取器的UVM覆蓋率報告Fig.6 UVM coverage reports for fuzzy extractor

4 流片及測試

4.1 芯片后端設計與流片

除模糊提取器外,測試芯片還搭載了UART接口邏輯、控制模塊和研究團隊設計的SRAM PUF,所有數字邏輯處于單一時鐘域,設計時鐘頻率為SS_1.35V_125C@16.7 MHz,綜合結果顯示,模糊提取器部分占用芯片面積306 267 μm2,以標準單元NAND2HD1X計算得消耗邏輯門數量約為50 609。

該設計在華虹宏力110 nm CMOS平臺流片,最終全芯片含IO尺寸為1 140 μm×1 140 μm,芯片頂層版圖如圖7(a)側所示。該芯片搭載了課題組自研的SRAM PUF模塊、模糊提取器和UART接口邏輯,芯片外圍為電源、地、GPIO和IO filler。圖7(b)右側展示了芯片裸片在SOP16塑料管殼中打線的實物圖,裸片厚度480 μm。

圖7 PUF測試片版圖和實拍圖Fig.7 PUF test chip layout and photo

4.2 芯片測試與結果

根據芯片的管腳定義,我們設計了如圖8(a)所示的測試板,測試板上搭載SOP16燒錄座,方便進行芯片的更換。文獻[27]展示了對于該芯片的SRAM PUF模塊的測試。同時,我們也進行了模糊提取器的功能測試。測試環境使用STM32F407ZGT6開發板做上位機控制PUF芯片的工作狀態,并將讀取到的數據通過串口轉USB上傳到PC進行整理。圖8(b)和8(c)展示了測試系統和連接關系示意圖。

圖8 PUF芯片的測試系統Fig.8 PUF chip test system

測試結果表明,模糊提取器在PUF數據發生波動的情況下具有數據還原能力,可以滿足PUF芯片穩定的挑戰-相應關系。功耗方面,在典型工作狀態中實測全芯片功耗為1.79 mW,靜態電流為11 nA。

4.3 性能比較

PUF模塊在實際測試之前無法預估和仿真不穩定位的數量,因此相比較于其他場景的糾錯碼實現,面向PUF的模糊提取器糾錯容量通常會設置一定的冗余以保證穩定的數據還原能力。表5中NAND Flash數據糾錯和短極化碼算法優化的場景中,使用的BCH碼糾錯容量均小于本設計方案。除此以外,在不使用冒泡存儲方案的情況下,大糾錯容量的參數選擇會顯著提升邏輯單元數量,因此常規的PUF模糊提取器會對該參數做出取舍,通過降低一定的糾錯容量換取更小的芯片面積或FPGA資源消耗。

表5 相似功能實現的參數對比表Table 5 Comparison of parameters of similar implementations

5 結 論

本文設計了一種面向PUF的大糾錯容量的模糊提取器,該模糊提取器兼容的碼長為127 bit,糾錯容量為27 bit。通過向模糊提取器中的BCH碼算法引入對數/反對數表避免了大量使用有限域乘法器和求逆運算;借助冒泡存儲的方式減少了BM算法中歷史數據的寄存器占用。UVM驗證的結果顯示,本設計在滿足功能點的同時,具有良好的代碼風格,可以達到100%的覆蓋率。經過流片及測試,結果表明,該模糊提取器設計可以滿足SRAM PUF不穩定位的糾錯需求,穩定實現其挑戰相應功能。