基于HB+協(xié)議的后量子安全認(rèn)證系統(tǒng)*

施雨軒，葛萬成

（同濟(jì)大學(xué)中德學(xué)院，上海 200092）

0 引 言

于1977年在麻省理工提出的RSA加密算法，作為非對稱加密算法中的代表被廣泛應(yīng)用于公開加密與電子商業(yè)。它雖然有著高安全性與難以破解的優(yōu)勢，但是大部分基于RSA加密協(xié)議的認(rèn)證系統(tǒng)不具備輕型的特點，而任何場合泛用的射頻識別技術(shù)（Radio Frequency Identification，RFID）則無法保證可靠的安全性。此外，隨著量子計算機(jī)的飛速發(fā)展，即使是聲稱無法被破解的RSA加密算法也變得岌岌可危。

正因此，LPN問題躍入人們的視線，可以被看作是求解一個非線性方程的數(shù)學(xué)問題。解決LPN問題，等同于在存在噪聲的情況下對隨機(jī)線性碼進(jìn)行譯碼。這種協(xié)議目前被認(rèn)作是一種困難問題，即密鑰很難被破解，能抵御量子計算機(jī)的攻擊。它的衍生協(xié)議HB+在對抗量子計算機(jī)的被動與主動攻擊方面都有良好效果。

本文設(shè)計實現(xiàn)了基于HB+協(xié)議的后量子安全認(rèn)證系統(tǒng)。該系統(tǒng)分為注冊階段和認(rèn)證階段，采用學(xué)習(xí)奇偶噪聲（LPN）的原理，并由物理非克隆函數(shù)和一種與物理隨機(jī)特性有關(guān)的集成電路提供隨機(jī)噪聲，其中引入了哈希函數(shù)作為加密模塊，最后由FPGA實現(xiàn)并仿真考量了其可行性與安全性。

1 LPN問題和HB+協(xié)議

1.1 LPN問題

LPN問題可以被看作是一個數(shù)學(xué)問題。假設(shè)User（U）與Computer（C）之間共享k比特密鑰x，U想向C證明自己的身份，認(rèn)證過程如下：C產(chǎn)生一個隨機(jī)的k比特矢量a發(fā)送給U，U收到后計算c=a·x響應(yīng)給C（其中·表示GF(2)上的點乘），C收到后檢查，如果c=a·x則認(rèn)證通過，反之不通過。在一輪認(rèn)證中，C接受一個假冒用戶的概率是1/2，重復(fù)r輪后，理論上C接受一個假冒用戶的概率是2-r。很不幸的是，被動攻擊者只要觀察o(k)次“挑戰(zhàn)-響應(yīng)”對，就可以通過高斯消元法解出共享密鑰x進(jìn)而偽裝成U。于是，引入了噪聲參數(shù)η∈(0,1/2)，在U的響應(yīng)中參入一些錯誤回答，這樣被動攻擊者就無法簡單利用高斯消元法得到密鑰x，這就是LPN問題，即噪聲存在下的奇偶性問題。LPN問題在不同應(yīng)用環(huán)境中有不同的描述，如MDP問題、Syndrome譯碼問題等都是LPN問題的變型。下面用矩陣運算來定義LPN問題。

假設(shè)D是一個隨機(jī)的q×k比特矩陣，x是一個隨機(jī)的k比特矢量，噪聲參數(shù)η∈(0,1/2)，v是一個隨機(jī)的q比特矢量，其漢明重量v≤η·q。已知D、η以及z=(D·x)⊕v，找一個k比特矢量x′滿足 |(D·x′)⊕v|≤ ηq。

LPN問題已經(jīng)被證明是NP-Hard[1]，同時要找到一個滿足超過一半“挑戰(zhàn)-響應(yīng)”對的x′也是NP-Hard。最著名的解LPN問題的算法是由Blum等提出的BKW算法，即給定2o(k/logk)個等式的情況下，其計算復(fù)雜度為2o(k/logk)。此外，研究表明，現(xiàn)今最好的算法[2]必須在已知o(k)個方程等式的情況下，在2o(k)以內(nèi)的時間范圍內(nèi)才能解決LPN問題。

1.2 基于LPN的認(rèn)證協(xié)議

HB[3]協(xié)議是Hopper和Blum基于LPN問題提出的。一個完整的HB協(xié)議包括r輪，其中r是一個安全參數(shù)，服務(wù)器與設(shè)備共享k比特密鑰x。設(shè)備擁有一個噪聲發(fā)生器，以η∈(0,1/2)的概率生成噪聲v={0,1|prob[v=1]=η}。一輪協(xié)議中，服務(wù)器隨機(jī)生成k比特序列a發(fā)給設(shè)備，設(shè)備收到后計算z=(a·x)⊕v發(fā)回去，服務(wù)器檢驗是否z=a·x，其中·為矢量內(nèi)積。這樣進(jìn)行r輪后，如果設(shè)備響應(yīng)錯誤的輪數(shù)小于ηx，認(rèn)證通過。具體的一輪協(xié)議流程如圖1所示。

圖1 單輪HB認(rèn)證協(xié)議

HB協(xié)議可以抵抗在線竊聽等被動攻擊，但它對于主動攻擊的抗性非常差。為了解決HB協(xié)議的這個缺點，由HB協(xié)議衍生出了HB+協(xié)議。HB+協(xié)議采用類似于HB協(xié)議的“挑戰(zhàn)-響應(yīng)”認(rèn)證模式，不同的是，HB+協(xié)議中服務(wù)器與設(shè)備之間增加了一個共享的k比特密鑰y，相應(yīng)地，z的計算也有所不同；另外HB+協(xié)議中需要設(shè)備首先產(chǎn)生k比特盲因子b發(fā)給服務(wù)器。同HB協(xié)議一樣，r輪后如果設(shè)備回答錯誤的次數(shù)小于ηr，服務(wù)器就能認(rèn)證設(shè)備。具體流程如圖2所示。

圖2 單輪HB+認(rèn)證協(xié)議

HB協(xié)議執(zhí)行過程簡單，計算z只需要AND和XOR兩個操作。Tag收到a后不用緩存可以直接計算，節(jié)省存儲空間。而相比HB協(xié)議，HB+協(xié)議僅需要多產(chǎn)生一個k比特隨機(jī)向量，增加k比特存儲空間，多計算2r次AND和XOR，能夠有效抵抗主動攻擊。綜合考量可靠性與成本，在后文中選取HB+協(xié)議。

2 新型認(rèn)證系統(tǒng)設(shè)計

基于HB+協(xié)議的新型認(rèn)證系統(tǒng)的設(shè)計思想源自于Charles Herder的模糊提取器[4]。它采用真隨機(jī)數(shù)生成器（TRNG）生成隨機(jī)密鑰，然后采用編碼理論和哈希函數(shù)保證系統(tǒng)的安全性。本設(shè)計中，鑒于CRC運算的可逆性，容易被破解。因此，本文使用Toeplitz函數(shù)構(gòu)建哈希模塊。加密過程如下：一個長度為m，期望輸出長度為n比特的消息M，構(gòu)成一個維數(shù)為m×n的Toeplitz矩陣，再由1×m的消息序列與矩陣相乘，得到的新序列模2后，即該消息的哈希值。

此外，密鑰型PUF也被引進(jìn)，用作加入編碼模塊[5]和譯碼模塊的隨機(jī)噪聲。本文是在這種結(jié)構(gòu)的基礎(chǔ)上，重新設(shè)計了一個新型的認(rèn)證系統(tǒng)。該系統(tǒng)包括兩個階段：注冊階段和認(rèn)證階段。

2.1 注冊階段

注冊階段由4個部分組成：真隨機(jī)數(shù)發(fā)生器（TRNG）、編碼器、PUF和哈希函數(shù)模塊，如圖3所示。

圖3 注冊階段結(jié)構(gòu)

TRNG是指利用物理方法實現(xiàn)的隨機(jī)數(shù)發(fā)生器。與偽隨機(jī)數(shù)發(fā)生器（PRNG）不同的，它是自然界隨機(jī)的物理過程的反映。即使TRNG的所有信息都被暴露，都無法猜測其結(jié)果。用TRNG生成k位隨機(jī)二進(jìn)制向量s=(0,1)k作為編碼器的輸入，即信息字。文獻(xiàn)[6]建議安全等級為128，以防御暴力算法或其他能解決LPN問題的算法解出密鑰s。

信息字送入編碼模塊，由設(shè)定好的生成矩陣G[7]、隨機(jī)二進(jìn)制向量s被編碼成長度為n的帶有一定錯誤位的編碼字hd=G·s。本文采用Reed-Muller碼作為糾錯碼，編碼過程中信息字是由4個RM(1,7)和1個RM(4,7)組成。該信息序列首先使用外碼進(jìn)行編碼，然后對該碼字使用內(nèi)碼進(jìn)行編碼。

PUF因其本身的物理特性，產(chǎn)生了一個長度為n的特定的、唯一的比特流e=(0,1)n，其中ei=Ber(η)，i∈[1,n]，作為注冊階段中的編碼器的噪聲輸入。正如前文所提，這里采用的是密鑰型PUF（弱PUF），用來生成輔助數(shù)據(jù)hd*=G·s+e。本文中設(shè)定PUF的最小錯誤概率為14%，熵為99%，則PUF正確響應(yīng)需要不小于130位，以生成極小錯誤概率的k=128位密鑰。

注冊階段的最后一步由哈希函數(shù)構(gòu)造編碼字hd和信息字s的聯(lián)合哈希值H(s,hd)。該值作為重要的對比參數(shù)需要被存儲在數(shù)據(jù)庫中，用于后續(xù)的系統(tǒng)認(rèn)證。

2.2 認(rèn)證階段

認(rèn)證階段對比存儲的數(shù)據(jù)參數(shù)與激勵信號，由PUF、譯碼器、哈希函數(shù)和乘法器組成，如圖4所示。

圖4 認(rèn)證階段結(jié)構(gòu)

長度為n的hd被用作這個階段的激勵信號。

與注冊階段不同，PUF模塊在認(rèn)證階段產(chǎn)生的隨機(jī)比特 e′=(0,1)n略有不同，其中 ei′=Ber(η)，i∈[1,n]。隨后，把(hd⊕e′)的計算結(jié)果送給譯碼器的輸入端。該過程中，給定已知的生成矩陣G和輸入值hd，然后利用譯碼器和糾錯算法可提取出正確的隨機(jī)數(shù)s。

哈希模塊將隨機(jī)數(shù)s和碼字hd轉(zhuǎn)換為對應(yīng)的唯一的聯(lián)合哈希值H(s,hd)。

Toeplitz哈希值H(s,hd)被看作是HB+認(rèn)證協(xié)議中總長度為128位的密鑰，然后被分為兩個64位的密鑰Hleft(s,hd)和Hright(s,hd)。二者被視為HB+協(xié)議中的兩個密鑰x和y。為了構(gòu)建HB+認(rèn)證協(xié)議，還需要引進(jìn)兩個乘法器和兩個隨機(jī)矩陣A和B。同時，為了保證系統(tǒng)的安全性，噪聲v也應(yīng)考慮在內(nèi)。綜上，響應(yīng)則為：

在注冊階段，服務(wù)器會收集大量的H(s,hd)和hd的值。給定已知的隨機(jī)矩陣A和B，它能計算出響應(yīng)：

之后將這些值存儲在數(shù)據(jù)庫中，當(dāng)作參考響應(yīng)值。

在認(rèn)證階段，服務(wù)器給定hd值，然后設(shè)備返回一個帶有一定誤差的響應(yīng)r，并計算r。如果r′和r之間的漢明距離小于參數(shù)t，則此過程通過認(rèn)證。由于Hleft(s,hd)和Hright(s,hd)的長度都為64，那么可選取維度都為64×64的隨機(jī)二進(jìn)制矩陣A和B。對于“錯誤率”，文獻(xiàn)[6]中已經(jīng)證明，對于任意的ε，只要ε滿足0＜ε＜1/2的情況下，HB+協(xié)議就能防御主動攻擊。這里ε可以設(shè)為1/8，則t=ε×n=8。

3 仿真與實驗結(jié)果

本文在Xilinx的Vivado編譯環(huán)境中實現(xiàn)硬件仿真。FPGA選型為賽靈思Zynq-7000現(xiàn)場可編程門陣列7z010clg225-3。出于方便檢查結(jié)果是否正確的目的，PUF響應(yīng)被置為全零向量，即錯誤響應(yīng)為“1”。圖5顯示的是注冊階段的硬件仿真結(jié)果。其中，，in_key為TRNG發(fā)生的隨機(jī)數(shù)s=“d37fcc0740ffc330 9c98e43dfa101360”，k=128；out_encoded_reference為編碼器模塊的正確的參考碼字；reconstructed_response_s為編碼器輸出值的實際仿真結(jié)果；out_hash_vector為哈希模塊的輸出，哈希值H(s,hd)。

圖5 注冊階段的硬件仿真結(jié)果

根據(jù)仿真結(jié)果圖5可知，out_encoded_reference和reconstruct_response_s的值相等，說明TRNG產(chǎn)生的隨機(jī)數(shù)s被正確編碼，編碼結(jié)果無誤。s和hd的聯(lián)合哈希值out_hash_vector被分為兩個相同長度的碼字，各64比特，分別與隨機(jī)矩陣A和隨機(jī)矩陣B進(jìn)行矩陣乘法運算。之后，服務(wù)器可以自行計算無錯誤的參考響應(yīng)：

而在認(rèn)證過程中中，隨機(jī)矩陣A和隨機(jī)矩陣B的取值是相同的。最初，它們被存儲在文本文件中，通過接口把它們讀取到測試臺中，并存在Block RAM中，然后在仿真環(huán)境下進(jìn)行處理。下面給出本文中隨機(jī)選取的一個例子，隨機(jī)矩陣A的取值如圖6所示。在這個階段，為了更簡單方便地驗證譯碼模塊是否正常工作，本文將hd設(shè)置為全零序列，而PUF響應(yīng)則設(shè)置為注冊階段的hd值，即此時的PUF取值被定為注冊階段中帶有一定錯誤的碼字，譯碼過程的仿真結(jié)果如圖7所示。

圖6 隨機(jī)矩陣A

圖7 譯碼器的仿真結(jié)果

在圖7中，out_key_reference表示正確的參考隨機(jī)數(shù)，helper_data_2_i是通過譯碼器譯碼后的信息字。經(jīng)對比，兩者結(jié)果一致，說明該譯碼過程正確無誤。

圖8中，output_reference表示服務(wù)器在注冊階段計算的無噪聲的參考響應(yīng)。而output_vector是設(shè)備返回的一個帶有一定錯誤比特位的響應(yīng)。在測試臺，誤差向量的漢明重量比率如之前所設(shè)定ε=1/8，t=8。在這個參數(shù)的設(shè)置情況下，如果服務(wù)器檢測到無噪聲的參考響應(yīng)與設(shè)備返回的帶有一定錯誤比特位的響應(yīng)之間的漢明距離不超過t=8，那么這個設(shè)備是合法的，通過認(rèn)證。圖9顯示此認(rèn)證過程是成功的。

圖8 認(rèn)證階段的硬件仿真結(jié)果

圖9 整個認(rèn)證系統(tǒng)的運行結(jié)果

表1顯示了認(rèn)證階段消耗的總資源情況。與編碼器模塊和控制器模塊相比，哈希模塊消耗的資源最少，消耗的LUT（Look Up Tabel）在7.9%左右。

表1 認(rèn)證階段的資源利用率

4 結(jié) 語

本文基于HB+協(xié)議提出了一種新型的安全認(rèn)證系統(tǒng)，在構(gòu)建過程中選擇了密鑰型物理非克隆函數(shù)引入隨機(jī)噪聲和Toeplitz矩陣進(jìn)行加密。仿真結(jié)果表明，在設(shè)定漢明距離后，系統(tǒng)在帶有錯誤比特位的情況下亦能區(qū)分認(rèn)證或是非法設(shè)備，具有很高的安全性。此外，HB+協(xié)議屬于輕量級算法，仿真階段顯示其耗費的資源較少。換言之，本文設(shè)計的新型安全認(rèn)證系統(tǒng)應(yīng)用場合較為廣泛，硬件配置上易于實現(xiàn)。