基于可信硬件的隱私數據可搜索加密加速方法研究

楊光遠 楊大利 張 羽 馬利民 張 偉

1(北京信息科技大學計算機學院 北京 100101)

2(國家信息中心信息網絡安全部 北京 100045)

(guangyuany86@163.com)

可搜索加密(searchable encryption, SE)[1-2]的設計是使用戶能夠將自己的數據安全地外包到服務器，同時保留查詢和搜索功能.SE被認為是建立加密數據庫，防止隱私數據泄露最有前途的解決方案.通用的解決方案如全同態加密、安全多方計算等，雖然增強了數據的安全性，但增加了大量的計算和通信開銷.屬性保留加密，如確定性加密是有效的，但這些解決方案在實際應用[3]中并不安全.近年來，SE方案的快速發展具備了更多的功能和更高的安全性[4-5].

在動態SE中，前向隱私的概念是指新添加的數據和之前發布的搜索查詢之間的鏈接應該隱藏在服務器上，后向隱私的概念是指刪除的數據和刪除后的搜索查詢之間的鏈接應該隱藏.現有的前向和后向隱私SE方案[6-7]在客戶端和服務器端都引入了大量的存儲和計算開銷，增加了客戶端和服務器之間的交互.為了提高SE的效率，一種方法是采用硬件輔助的方案，例如Intel SGX，它可以在受信任且隔離的執行環境中執行本機代碼和數據，從而減輕客戶端存儲和計算的開銷，并減少客戶端和服務器之間的通信成本.

Amjad等人[8]提出了第1個使用SGX的前向和后向隱私SE方案.方案中數據的添加和刪除對服務器是完全不知情的.但是，由于SGX和服務器之間的高I/O復雜性，這種方法仍然是低效的.后來他們在安全性和更高的效率之間進行權衡，提出了Bunker-B[8].文獻[8]中給出了Bunker-B的理論構造，但是它是不可擴展的，尤其是在處理大型數據集時.首先，刪除操作是通過插入操作實現的，這將導致2個問題：1)導致SGX與服務器之間的通信成本較高；2)由于所有刪除的數據都需要從搜索結果中檢索、解密和過濾掉，這就會增加搜索延遲.

為了避免SGX的引入而導致的潛在性能瓶頸， 本文利用SGX enclave充分發揮客戶端的作用,enclave將同時緩存關鍵字狀態和刪除操作，以減少SGX與服務器之間在搜索、添加和刪除操作中的通信成本和往返次數，并使客戶端幾乎沒有任何計算和存儲上的額外消耗.1)本文設計并實現了前向和后向隱私SE方案，稱為TSE.TSE利用SGX套件跟蹤關鍵字狀態和數據刪除，以最大程度地減少SGX和不受信任的內存之間的通信開銷.2)我們在數據集上進行實驗并對數據進行了分析，結果表明提出的技術相較于之前的技術降低了通信成本，查詢效率有所提高.向數據庫中插入106條數據時的ecall/ocall調用次數僅為Bunker-B方案的10%.

1 相關工作

可搜索加密:Song等人[1]提出了第1個可搜索加密(SE)，可以對加密的數據進行搜索.古宜平等人[2]和Kamara等人[9]分別對靜態和動態SE的安全定義進行相關研究，并提出了具有次線性搜索時間的方案.自從SE研究以來，一系列的相關研究開始致力于提高查詢效率[10]和支持表達性查詢[11].

可信執行環境中的密文搜索: 文獻[8,12-14]的研究是利用可信執行環境(TEE).通常，TEE(例如Intel SGX)可以減少客戶端和服務器之間的網絡通信，并增加加密數據庫功能.Fuhry等人[14]提出了HardIDX，它以B+樹結構構建數據庫索引，并利用enclave遍歷樹節點的子集進行搜索.文獻[8]提出了3種方案來啟用具有不同搜索泄露(即服務器可以從中獲悉有關查詢和數據的信息)的單關鍵字查詢.但是，他們尚未研究這些方案的實際性能.同時，Ren等人[15]提出了一種通過SGX的隱藏范圍查詢方案.

2 相關知識

2.1 Intel SGX

Intel SGX是一組x86指令集，旨在提高應用程序代碼和數據的安全性[16-17].在啟用SGX的平臺上，需要將應用程序劃分為受信任部分和不受信任部分.受信任的部分稱為enclave，位于物理RAM的專用內存部分中，由SGX實施強保護.不受信任的部分作為普通進程執行，并且只能通過名為ecall的明確定義的接口調用enclave，而enclave可以加密明文數據并通過名為ocall的接口發送給不受信任的代碼.此外，當將數據加載到enclave內時，將執行解密和完整性檢查.所有其他軟件，包括操作系統、特權軟件、虛擬機管理程序和固件，都無法訪問enclave的內存.在enclave中用于存儲數據的實際內存最多只有96 MB[18].在此之上，SGX將自動應用頁面交換. SGX還具有遠程認證功能，該功能允許在遠程服務器上驗證enclave的創建，并創建與enclave的安全通信通道.

2.2 動態搜索對稱加密

動態SE中的前向和后向隱私：按照文獻[4-5]中的表達，DB代表數據庫，每條具有唯一標識符id的數據是一個可變長度的唯一關鍵字集.我們使用DB(w)來顯示出現關鍵字w的數據集. 關鍵字-數據對的總數用N表示，W是DB中不同關鍵字的總數.indexMI是一種字典結構，用來存儲所有N個關鍵字-數據對，將每個唯一關鍵字w映射到DB(w)中的匹配列表.名為EDB的加密數據庫是加密數據的集合.動態SE方案Σ=(Setup，Search，Update)由客戶端和服務器之間的3個協議組成，如下所示:

1) Setup(1λ,DB).協議輸入1個安全參數λ，輸出1個密鑰K，1個客戶端狀態ST和1個加密數據庫EDB.

2) Search(K,w,ST;EDB).協議允許在客戶端根據狀態ST、密鑰K和狀態ST查詢w，在服務器端根據加密數據庫EDB查詢w.然后輸出搜索結果Res.

3) Update(K,(op,in),ST;EDB).該協議接收K、ST、一個與客戶端操作op相關的輸入以及EDB，其中op∈{add,del}，in由數據標識符id和該數據中的一組關鍵字組成.然后，協議執行op操作時從EDB插入或刪除數據.

3 問題分析及算法設計

3.1 問題分析

Amjad等人[8]提出了3種采用SGX支持的向后隱私的方案:Type-I方案Fort，Bunker-B和Bunker-A.Fort是最安全的，但是由于其開銷較大，本文不對其進行研究.Bunker-A不執行重新加密和重新插入，只實現向后隱私.因此，本文主要分析Bunker-B的局限性，Bunker-B協議總結如下所示.

協議1.Bunker-B: update和search協議.

① Update(op,in):

/*op∈{add,del},in=(w,id)*/

② client從st檢索stw=(version,

count);

③ 發送(w,version,count,op,id)到

enclave;

④ client更新st中的stw=(version,

count+1);

⑤ enclave生成update令牌utk=(u,v):

uFK1(w‖version‖count+1),

vEnc(K2,id‖op);

⑥ enclave發送sutk到server;

⑦ server從enclave中檢索sutk=(u,v);

⑧ server更新mapMI[u]=v

⑨ Search(w):

⑩ client從st檢索stw=(version,count);

enclave的st;

count);

count);

qtk=(u1,u2,…,ui,…,ucount),其中:

v2),…,(uc,vc)}到enclave;

鍵字-數據對；

∈L}過濾未刪除的ids;

Bunker-B的性能分析:對于每個(w,id),Bunker-B讓enclave遵循相同的例程來生成用于添加和刪除的令牌，并使用生成的令牌來更新服務器上的MI(協議1中的⑤).然而,它會導致高計算復雜度,并且在搜索過程中涉及到大量的數據傳輸.在Search協議中，Bunker-B的核心思想是讓enclave讀取MI中與關鍵字對應的所有記錄(與add或del相關).然后，enclave對它們進行解密，并根據操作過濾被刪除的id.查詢之后，enclave重新加密未刪除的id，并將新生成的令牌發送到服務器進行更新.這些步驟總結在協議1的第～行中.本文復現了Bunker-B(見第4節的實驗)，發現該方案在實踐中還存在以下局限性:1)密集ecall/ocall調用.將具有標識符id和M條唯一關鍵字的數據提供給服務器，Bunker-B通過使用M次ecall，然后使用相同數量的ocall重復執行更新協議，以將令牌插入索引映射MI.2)搜索延遲.每次搜索都會對未刪除的id重新加密，這使得Bunker-B效率降低.

3.2 系統概述

通過分析Bunke-B具有的一些限制，我們設計了TSE，TSE的整體架構如圖1所示:

圖1 TSE系統整體架構及工作流程

TSE方案涉及3個實體:客戶端(數據所有者，因此是受信任的)、不受信任的服務端和服務器內受信任的SGX enclave，系統工作流程包括11個步驟.

在步驟1中，客戶端使用SGX認證功能對enclave進行身份驗證，并與enclave建立安全通道. 然后，客戶端通過此通道將密鑰K提供給enclave. 這樣就完成了協議中的Setup協議.

在步驟2中，為客戶提供具有唯一標識符id的數據，客戶端管理器使用密鑰K加密數據，并將數據的加密版本發送到服務器管理器(步驟3).然后將帶有id的加密版本插入到EDB中.客戶管理器通過安全通道將原始數據發送到位于enclave的狀態管理器(步驟4).在此步驟中，狀態管理器執行加密操作以生成將被發送到服務端管理器的更新令牌(步驟5).令牌用于更新位于服務端管理器中的動態SE的加密索引.動態SE MI的索引位于服務器管理器中，而加密數據存儲于加密數據庫EDB中.要刪除具有給定id的數據(步驟6)，客戶端管理器直接將數據id發送給狀態管理器(步驟7).

在步驟8中,客戶端想要搜索包含給定查詢關鍵字w的數據.客戶端管理器將關鍵字w發送給狀態管理器(步驟9).然后,狀態管理器計算查詢令牌并排除標記為刪除數據.之后，狀態管理器將它們發送到服務器管理器(步驟10).服務器管理器將搜索接收到的令牌，并將加密的匹配數據列表返回給客戶端管理器，并用K解密加密的數據.

3.3 系統的假設和威脅模型分析

對Intel SGX的假設:本文假設SGX是可信的(即沒有硬件錯誤或后門)，并且enclave內的預置代碼和數據是受到保護的.此外，客戶端和enclave之間的通信依賴于SGX認證期間創建的安全通道.和其他SGX應用程序[19]一樣，對SGX的[20]的側邊通道攻擊不在我們的范圍內.拒絕服務(DoS)攻擊也不在我們的關注范圍之內，也就是說，enclave總是在客戶端調用或查詢時可用.最后，我們假設SGX使用的所有加密原語和庫都是可信的.

威脅模型:根據文獻[17],我們認為服務器端有一個半誠實但強大的攻擊者.盡管攻擊者不會偏離協議，但可以通過enclave之外的軟件堆棧、操作系統和管理程序，以及服務器中的硬件組件(處理器包除外)獲得完全訪問權.攻擊者可以在內存總線上、內存中或EDB中觀察內存地址和(加密的)數據，以生成數據訪問模式.此外，攻擊者可以記錄這些內存操作發生時的時間.

3.4 TSE算法思想及偽代碼

TSE的基本思想是讓enclave存儲關鍵字的最新狀態ST，并保留已刪除數據的數據id的列表d，方便后期搜索使用.然后，enclave僅在2次刪除操作之間加載用于第1次搜索的被刪除的數據，以便于更新刪除的id和查詢的關鍵字之間的映射.在2次刪除更新之間的后續搜索不需要再次加載刪除的數據.我們注意到，enclave在第1個查詢中檢索到d后顯然需要刪除d，以保存enclave的存儲.一旦enclave知道查詢關鍵字和已刪除數據之間的映射，它就會推斷查詢關鍵字與其余未刪除數據的映射，以便生成查詢令牌. 之后，服務器根據接收到的令牌檢索數據，并將數據結果列表返回給客戶端.接下來將結合協議偽代碼進一步解釋協議，Setup協議如下所示:

協議2.Setup(1λ).

client:

①kΣ,kf←{0,1}λ；

② 啟動遠程認證；

③ 建立安全的渠道;

④ 發送K=(kΣ,kf)到enclave;

enclave:

⑤ 初始化ST和D:

⑥ 初始化一個列表d;

⑦ 初始化T1和T2;

⑧ 接收K=(kΣ,kf);

server:

⑨ 初始化MI和Mc;

⑩ 初始化存儲庫R.

在Setup過程中，客戶端在建立的安全通道上與enclave通信，以提供K=(kΣ,kf)，其中kΣ使enclave域能夠生成更新/查詢令牌，而kf是用于數據加密/解密的對稱密鑰.enclave維護映射ST和D以及列表d，其中ST存儲關鍵字的狀態，D表示關鍵字和已刪除數據之間的映射，d是已刪除id的數組.服務器保存1個加密索引MI、加密狀態Mc的映射、帶有R[id]的存儲庫R存儲數據標識符id的加密數據.

如下為TSE的Update協議流程：

協議3.Update(op,in).

client:

① ifop=add then

②f←Enc(kf,data);

③ 發送(id,f)到server;

④ end if

⑤ 發送(op,id)到enclave;

enclave:

⑥ ifop=add then

⑦f←R[id];

⑧ {(w,id)}←Parse(Dec(kf,f));

⑨ foreach (w,id) do

⑩kw‖kc←F(kΣ,w);

server:

如下為TSE的Search流程：

協議4.Search(w).

client:

① 發送w到enclave;

enclave:

②stwc←{?},Qw←{?};

③kw‖kc←F(kΣ,w);

④ foreachidiinddo

⑤fi←R[idi];

⑥datai←Dec(kf,fi);

⑦ ifwindataithen

⑧D[w]←idi∪D[w];

⑨ 刪除R[idi];

⑩ end if

server:

client:

4 實驗及數據分析

4.1 實驗設置

實驗設置與實現:本文選擇了Enron電子郵件數據集(1.4 GB)，使用C++和Intel SGX SDK4構建了TSE原型，此外，實現了Bunker-B的原型作為比較的基準，因為其實現是不公開的，原型利用SGX SDK中的內置加密原語進行相關加密操作.它還使用SDK中的設置和API來創建、管理和訪問為SGX設計的應用程序(enclave).實驗環境部署在具備SGX功能的Intel i7 1.8 GHz和8 GB內存的主機.

圖2 Bunker-B與TSE查詢時間對比(刪除25%的數據)

4.2 實驗數據分析

插入和刪除:首先，比較在Bunker-B和TSE方案下插入和刪除的時間，如表1所示.測量在不同方案的加密數據庫中添加關鍵字-數據對的運行時間.如表1所示，Bunker-B需要21 μs插入1對，當關鍵字-數據對的數量等于數據數量時，這比我們的方案(23 μs)要快.原因是上述3種方案的插入時間受到不受信任的應用程序和enclave之間的I/O(ecall/ocall)的限制.對于Bunker-B,I/O成本與關鍵字-數據對的數量成線性關系，而TSE的I/O成本與數據數量成線性關系.當插入1×106個數據時,我們的方案只需要7 μs來插入1對關鍵字-數據對,速度比Bunker-B (12 μs)快了近2倍.

表1 Bunker-B與TSE插入數據時間對比

對于刪除，Bunker-B的性能與插入(12 μs)是一樣的，因為刪除運行相同的算法只是操作不同.對于我們的方案，刪除過程只將數據id插入到列表中，并且在查詢階段通過排除已刪除的id來執行刪除操作.因此，我們的方案在刪除階段只需要4 μs就可以處理1個數據.

查詢延遲：為了測量關鍵字頻率和刪除操作帶來的查詢延遲，我們選擇在刪除部分數據后查詢前25個關鍵字，如圖2所示，當插入2.5×105條數據、刪除25%的數據后.對于最頻繁的關鍵字，Bunker-B需要1.3 s的查詢時間.雖然TSE執行第1次搜索需要5 s，但它也會在enclave中緩存已刪除的關鍵字-數據對，并在第1次查詢期間對數據執行刪除.因此，接下來的查詢速度要快得多，因為調用的次數大大減少.即使是第25個最常見的關鍵字，TSE(159 ms)仍然比Bunker-B(221 ms)快40%.

通信成本:接下來展示了I/O操作(ocall/ecall)對不同方案性能的影響.如表2所示，Bunker-B比本文方案多需要10倍的ecall/ ocall操作.因此，盡管Bunker-B和本文方案都在最后生成并存儲加密的關鍵字-數據對，但是本文方案可以實現更好的插入性能，因為本文方案依賴較少的I/O操作.在刪除操作上，Bunker-B比本文方案多了將近30倍的I/O操作(如表3所示).而且本文方案的刪除操作只需要插入已刪除的id，不涉及任何加密操作，而Bunker-B執行的過程和插入數據是一樣的.這表明本文方案比Bunker-B通信成本更低.

表2 Bunker-B與TSE插入數據通信成本對比

表3 Bunker-B與TSE刪除數據通信成本對比

內存消耗:因為與服務器和enclave相比，客戶機的內存消耗可以忽略不計(即小于1 MB).如圖3所示，TSE的加密數據庫始終保持不變，因為它們在添加1×106條數據后保持相同的關鍵字-數據對.另一方面，當我們刪除更多的數據時，Bunker-B的內存使用量會持續增加，因為它應該在服務器上維護已刪除的關鍵字-數據對.在enclave中，Bunker-B不維護任何持久的數據結構，而TSE需要存儲刪除所需的信息.對于TSE，它會緩存enclave中的所有數據id，這將導致非常高的內存使用量，刪除25%的數據時是304 MB.

圖3 Bunker-B與TSE內存占用對比(刪除25%的數據)

5 總 結

為了解決傳統SE降低加密數據的查詢效率，增加了客戶端和服務器之間通信成本的問題，本文引入了硬件輔助解決方案——Intel SGX來解決這2個問題.本文通過分析當前解決方案，發現當前的解決方案存在密集ecall/ocall調用和搜索延遲的問題，提出利用Intel SGX的enclave來緩存關鍵字的狀態，并且保留已刪除數據的id的列表d，為后期的數據查詢提供方便.本文的方案存在如下優點：

1) 由于在enclave中緩存了已刪除數據的關鍵字-數據對，查詢效率相較于Bunker-B更高；

2) 數據查詢過程中依賴較少的I/O操作，因此通信開銷更低.

雖然本文的方案在查詢效率和通信開銷方面有所優化，但是可以看到方案對enclave的內存占用還較高，這將觸發enclave的自動分頁機制，這個過程也會影響查詢效率，同時本文方案在大數據量時的處理表現還不好.因此接下來的研究工作將著力于提高方案的批處理能力，減少enclave的內存占用，進一步提高數據查詢效率.