基于哈希樹的度量證據(jù)可信存儲方案設(shè)計

邴丕政 戴紫彬 戴 強

(解放軍信息工程大學(xué)密碼工程學(xué)院 河南 鄭州 450001)

基于哈希樹的度量證據(jù)可信存儲方案設(shè)計

邴丕政 戴紫彬 戴 強

(解放軍信息工程大學(xué)密碼工程學(xué)院 河南 鄭州 450001)

計算平臺的可信性由遠程證明過程中提供的度量證據(jù)進行驗證，驗證程序根據(jù)計算平臺在啟動過程創(chuàng)建的度量證據(jù)建立信任。度量值擴展操作創(chuàng)建的度量證據(jù)和相關(guān)度量記錄是線性的，查找效率較低。提出一種基于平衡二叉哈希樹的構(gòu)建度量證據(jù)的方法。計算平臺上組件的度量值作為樹葉，所有組件的度量值集合的度量值作為樹根。在驗證計算平臺的過程中，使用哈希樹的度量記錄和根寄存器，在度量證據(jù)與標(biāo)準(zhǔn)值比較時顯著提高錯誤組件查找的速度，從而提高效率。實驗結(jié)果表明，平衡二叉哈希樹模型在不增加空間復(fù)雜度的同時，查詢時間開銷顯著減少。

平衡二叉哈希樹 遠程證明 錯誤定位 可信計算

0 引 言

計算平臺啟動期間，BIOS、bootloader、操作系統(tǒng)、應(yīng)用程序等組件都需要經(jīng)過計算平臺的度量，一級信任一級地產(chǎn)生信任鏈。組件度量值由組件代碼和配置數(shù)據(jù)經(jīng)過計算平臺的哈希運算產(chǎn)生，并存儲在平臺配置寄存器PCR(Platform Configuration Register)中，其存儲狀態(tài)受到保護。在對PCR進行擴展的同時，組件在存儲度量日志SML(Storage Measurement Log)中記錄度量中間步驟的度量值和度量事件，不需要保護措施。安全啟動完成后，度量值作為度量證據(jù)唯一確定平臺的可信狀態(tài)。

基于完整性度量架構(gòu)，每個組件均包含一個完整性參考清單RM(Reference Menu)結(jié)構(gòu)，該結(jié)構(gòu)提供組件的完整性參考值。遠程證明中的相關(guān)對象需要加密存儲。平臺上使用身份認證密鑰AIK(Attestation Identity Key)對當(dāng)前存儲的PCR值進行簽名，然后報告平臺狀態(tài)。在進行平臺驗證時，SML與相關(guān)PCR的值同時交給驗證平臺進行驗證，驗證平臺首先根據(jù)PCR的值驗證SML的可信性，再根據(jù)SML查找相應(yīng)的RM結(jié)構(gòu)，通過比較SML提交的平臺度量證據(jù)與RM結(jié)構(gòu)中的參考信息進行評估，得出驗證結(jié)論。SML的線性結(jié)構(gòu)決定了其在靈活性和效率上的局限性。Schmidt等[1]提出的改進默克爾哈希樹模型來進行平臺的遠程證明，其模型的構(gòu)建基于滿二叉樹，空間利用率不高。李俊中[2]提出以默克爾哈希樹模型作為完整性驗證方案，通過數(shù)據(jù)塊簽名及標(biāo)簽綁定，完成動態(tài)的數(shù)據(jù)操作。但是實際應(yīng)用中需要進行頻繁的數(shù)據(jù)填充操作，其滿二叉樹的結(jié)構(gòu)也易造成額外空間開銷。朱毅等[3]提出以非平衡二叉樹為基礎(chǔ)改進哈希樹模型，其節(jié)點數(shù)量動態(tài)增加，空間利用率高。該模型上的節(jié)點查找操作性能不佳。

本文提出一種方案，通過平衡二叉哈希樹構(gòu)造度量證據(jù)的數(shù)據(jù)組織方式，同時擴展SML。該數(shù)據(jù)結(jié)構(gòu)在度量證據(jù)與標(biāo)準(zhǔn)值比較時定位錯誤組件的效率更高，并且允許動態(tài)增加組件以進行更高效的驗證。同時該結(jié)構(gòu)增加了每一點上的可擴展性，其靈活性大大增強。

1 基于線性鏈的度量證據(jù)

1.1 線性鏈及其產(chǎn)生步驟

度量證據(jù)存儲在TPM的PCR中，受到平臺保護，在TPM中僅由授權(quán)指令訪問。TPM通過擴展操作規(guī)定度量證據(jù)的計算方法，其本質(zhì)是構(gòu)造線性順序的內(nèi)嵌哈希值鏈，計算過程如下：

Vi(k)=H(Vi(k-1)‖mk)

其中，Vi表示平臺配置寄存器(i=0,1,…,23)，H是抗碰撞哈希函數(shù)(TPM中以SHA1為例實現(xiàn))，mk的值是數(shù)據(jù)的哈希值，順序啟動過程的第k個度量值。擴展操作在TPM安全執(zhí)行環(huán)境的內(nèi)部執(zhí)行。在原值的基礎(chǔ)上進行擴展操作，如果被度量的數(shù)據(jù)發(fā)生變化，運算出的度量值將會發(fā)生變化。這種機制可判斷并保障平臺狀態(tài)信息是否可信，將PCR結(jié)果和SML一同比較，可驗證平臺是否有新的進程注入，同時也能發(fā)現(xiàn)攻擊者的惡意攻擊。圖1表示平臺配置寄存器的線性鏈結(jié)構(gòu)，由擴展操作產(chǎn)生，最終狀態(tài)由PCR記錄并保護。

圖1 線性鏈擴展

1.2 錯誤定位

驗證程序比較SML的每個度量證據(jù)和相關(guān)組件的標(biāo)準(zhǔn)值，若度量證據(jù)與標(biāo)準(zhǔn)值不同，表示相應(yīng)組件的錯誤。線性鏈度量證據(jù)的錯誤組件定位需要追蹤度量證據(jù)的位置，即當(dāng)SML包含N個度量證據(jù)時，至少需要計算復(fù)雜度為N的擴展操作(PCR值的SHA1操作)和對標(biāo)準(zhǔn)值的N次搜索，以確定被修改的度量證據(jù)的位置。

2 平衡二叉哈希樹度量證據(jù)

線性鏈度量證據(jù)在查找上的局限性，使得由線性鏈擴展操作構(gòu)建的度量證據(jù)對平臺遠程證明和組件修復(fù)等高級管理功能都有局限性。實際的SML存儲空間有大量組件的度量證據(jù)，若是以線性搜索的方法篩選錯誤的組件，代價昂貴且效率較低。

平臺度量證據(jù)的處理需要滿足：(1) 度量證據(jù)包含足夠多的信息，允許計算平臺提供獨立的、受密碼保護的度量證據(jù)，保證度量證據(jù)在傳遞過程中的可信，防止證據(jù)被篡改或者泄露；(2) 計算平臺的標(biāo)準(zhǔn)值對驗證平臺而言是可獲得的，既要保證標(biāo)準(zhǔn)值的機密性，又要保證其授權(quán)訪問。

2.1 哈希樹度量證據(jù)的構(gòu)建

為了使構(gòu)造算法盡可能簡潔高效，提供錯誤組件的快速查詢功能，本解決方案采用平衡二叉哈希樹進行構(gòu)造。樹葉節(jié)點攜帶組件的度量證據(jù)，樹根的度量證據(jù)是整個平臺的度量證據(jù)的集合，存儲于PCR；非樹葉節(jié)點攜帶的度量證據(jù)存儲在SML中。SML組織度量證據(jù)的數(shù)據(jù)結(jié)構(gòu)支持標(biāo)準(zhǔn)樹的操作和遍歷。平臺驗證期間，SML支持新葉子的順序增加并保持左右子樹的關(guān)系。在深度為d的樹的葉子上增加新的度量證據(jù)，需要重新計算所有深度為d-1的樹葉的內(nèi)部節(jié)點的度量證據(jù)。

平衡二叉哈希樹的構(gòu)造必須滿足如下條件：(1) 哈希樹的左子樹和右子樹的深度之差的絕對值不超過1；(2) 哈希樹的左子樹和右子樹也是一顆平衡二叉哈希樹。樹中每個節(jié)點的信息包括節(jié)點的左子樹、結(jié)點的右子樹、節(jié)點的度量證據(jù)、節(jié)點的深度。經(jīng)過分析得出，自下而上構(gòu)造平衡二叉哈希樹的算法如下所示。

node_t insert_node(node_t)

R、B、M newnode();

M->left = R;

M->right = B;

M->data = measure(R->data,B->data);

//構(gòu)造初始最簡二叉樹

While(Vi != NULL)

//度量值成功寫入時向二叉樹中添加節(jié)點

Mi = newnode();

Mi->left = M;

Mi->right = Vi;

Mi->data = HASH(M || Vi);

//新添加節(jié)點的信息填充

if(Height(Mi->left) - Height(Mi->right) ==-2)

//樹出現(xiàn)不平衡，需要左旋轉(zhuǎn)的情況

M = LeftRotate(Mi);

else if(Height(Mi->left) - Height(Mi->right)==2)

//樹出現(xiàn)不平衡，需要右旋轉(zhuǎn)的情況

M = RightRotate(Mi);

M->height = MAX( Height(M->left)，Height(M->right) ) + 1;

//重新計算樹的平衡度

remeasure(M);

//重新計算整棵樹的節(jié)點度量值

return M;

其中，Vi表示存放組件度量證據(jù)的寄存器，初始化為NULL。自下而上地構(gòu)建基于度量證據(jù)的平衡二叉哈希樹的步驟如下。

第一步 每一個組件的度量證據(jù)均存放在PCR中，兩個組件完成度量，將它們的度量證據(jù)進行擴展，動態(tài)添加新的樹節(jié)點并存放其中，令新節(jié)點為兩個組件葉子節(jié)點的父親。因此構(gòu)造出一棵最簡單的基于兩個組件度量證據(jù)的平衡二叉哈希樹。如圖2所示。

圖2 平衡二叉哈希樹的構(gòu)造過程

第二步 當(dāng)有其他組件度量完成時，將其證據(jù)跟最新的擴展證據(jù)進行擴展，生成的擴展證據(jù)作為最新的樹的根。此時需要注意，若破壞了平衡二叉哈希樹的條件之一導(dǎo)致樹的不平衡，需要進行節(jié)點的旋轉(zhuǎn)。涉及到的旋轉(zhuǎn)類型包括左旋轉(zhuǎn)和右旋轉(zhuǎn)。其中右旋轉(zhuǎn)的具體操作如圖3所示。

圖3 調(diào)整樹平衡的右旋轉(zhuǎn)操作

經(jīng)過多次旋轉(zhuǎn)，最終達到構(gòu)造平衡二叉哈希樹的兩個條件即可。

第三步 旋轉(zhuǎn)完成后，重新計算非葉子結(jié)點的中間度量證據(jù)。最終生成的樹中，其樹根是所有組件的度量證據(jù)的集合后的哈希root_hash，中間節(jié)點是組件之間度量證據(jù)的集合后哈希，樹葉是單個組件的度量證據(jù)。

2.2 遠程證明步驟

計算平臺在進行遠程證明行為時，遵循可信計算規(guī)范，加入TPM簽名步驟。流程及步驟如圖4所示。

圖4 遠程身份證明流程

(1) 計算平臺及挑戰(zhàn)者進行挑戰(zhàn)—應(yīng)答。

(2) 挑戰(zhàn)者生成160 bit的隨機數(shù)nonce，用于避免重放攻擊，并將該隨機數(shù)傳給計算平臺。

(3) 計算平臺從TPM產(chǎn)生的受保護的根密鑰SRK中獲取用于簽名的AIK私鑰，并對root_hash和nonce進行加密簽名；獲取SML。計算平臺發(fā)送數(shù)據(jù)包給挑戰(zhàn)者，該數(shù)據(jù)包包含對nonce和SML的簽名和AIK的公鑰。

(4) 挑戰(zhàn)者驗證AIK證書和簽名，獲得root_hash和SML值，處理SML并重新計算接收的PCR值，比較這兩個值是否匹配，檢査SML是否有效并且是否受到攻擊。

(5) 若匹配，說明計算平臺處于可信狀態(tài)；若不匹配，計算平臺驗證身份失敗，需要定位錯誤的組件構(gòu)成的子集。

驗證程序從樹根開始查找。在采用深度優(yōu)先搜索遍歷整棵樹的過程中，會產(chǎn)生度量證據(jù)跟標(biāo)準(zhǔn)值不同的組件的葉子節(jié)點集合。節(jié)點的值跟標(biāo)準(zhǔn)值作比較，不相等則說明其子樹的樹葉代表的組件已經(jīng)被破壞，繼續(xù)針對其子節(jié)點繼續(xù)比較直至樹葉；相等則說明其子樹的樹葉代表的組件完整性經(jīng)過驗證，停止比較。結(jié)果標(biāo)記為g表示一致，標(biāo)記為b表示不符。結(jié)果標(biāo)記用圖5表示。

圖5 錯誤定位標(biāo)記結(jié)果

在圖5(a)中，父節(jié)點及其子樹通過度量證據(jù)的驗證，遍歷該節(jié)點的葉子節(jié)點，表示平臺組件的完整性沒有受到惡意篡改，平臺是可信的。在圖5(b)中，驗證程序計算父節(jié)點與度量證據(jù)比較失敗，向下遍歷到子節(jié)點的值，并比較子節(jié)點的完整性。通過這種方式，驗證過程向下遍歷到下一個樹層，通過錯誤的度量證據(jù)找到子樹的樹葉、左樹葉、右樹葉或者左右樹葉。

3 構(gòu)造樹的復(fù)雜度分析

首先考慮構(gòu)造平衡二叉哈希樹算法的空間復(fù)雜度。平衡二叉哈希樹的構(gòu)造需要考慮兩個關(guān)鍵的因子：樹的深度、樹的葉子節(jié)點數(shù)?？紤]最壞情況，即平衡二叉哈希樹是一個完全填充的深度為h的滿二進制樹，含有2h-1個節(jié)點，均存儲在SML。在這種情況下，哈希樹SML的存儲空間約為兩倍的線性鏈SML存儲空間大小，即符合下列等式：

2h-1≈2h-1×2

考慮到兩種方案的PCR都只存儲樹葉的度量證據(jù)，中間節(jié)點的度量證據(jù)中間值只存儲在SML中，這樣的空間開銷是可接受的。

然后考慮時間復(fù)雜度。在平衡二叉哈希樹上的遍歷工作，其遍歷過程中和給定標(biāo)準(zhǔn)值進行判定的關(guān)鍵字個數(shù)不會超過樹的深度。假設(shè)深度為h的平衡二叉哈希樹含有的最大節(jié)點數(shù)為Nh。顯然有：

N0=0N1=1N2=2

且有下式成立：

Nh=Nh-1+Nh-2+1

利用歸納法和斐波那契序列性質(zhì)容易證明：當(dāng)h≥0時，含有n個節(jié)點的平衡二叉哈希樹的最大深度為：

因此，在平衡二叉哈希樹上進行查找的時間復(fù)雜度為O(logn)。

4 實驗及分析

為在實踐中驗證該方案的可行性，在CentOS6.4系統(tǒng)下搭建以開源項目TPM-Emulator為硬件TPM模擬環(huán)境，IBM開源軟件TrouSerS為軟件基礎(chǔ)環(huán)境的實驗平臺，經(jīng)過源代碼的修改實現(xiàn)計算平臺的TCM軟件棧。實驗環(huán)境如表1所示。

表1 實驗環(huán)境

TPM調(diào)用TPM_TREE_EXTEND作為平衡二叉哈希樹構(gòu)造的命令，其輸入與原構(gòu)造線性鏈的命令TPM_EXTEND相同。TPM利用PCR的標(biāo)記指明當(dāng)前二叉樹的樹根，其值為度量證據(jù)的中間結(jié)果。TPM_TREE_EXTEND命令的返回值為更新過的度量證據(jù)，按序排列。樹構(gòu)造成功時得到的最終的度量證據(jù)代表平臺的可信。

為了測試構(gòu)造平衡二叉哈希樹算法的性能，將任意的160bit的數(shù)據(jù)作為TPM_TREE_EXTEND命令的輸入。我們假定這些人工生成的輸入作為測試用例的度量證據(jù)。使用函數(shù)SystemNanoTime對執(zhí)行時間進行計算。輸入的度量證據(jù)分別為215、217、219，從處理器頻率為2.53GHz的系統(tǒng)開機引導(dǎo)模擬開始執(zhí)行。實驗得出的信任鏈構(gòu)造的時間曲線如圖6所示。

圖6 構(gòu)造時間比較

由圖6的結(jié)果表明，在線性鏈結(jié)構(gòu)的PCR度量值擴展操作過程中，每進行一次擴展，算法只需要進行數(shù)據(jù)的線性變換，所耗時間基于數(shù)據(jù)量的大小呈線性關(guān)系；在二叉樹樹式結(jié)構(gòu)的度量值擴展操作過程中，每進行一次擴展，算法需要進行樹的旋轉(zhuǎn)操作、樹的遍歷操作、重新計算除了樹葉之外的所有非樹葉節(jié)點的中間度量數(shù)據(jù)結(jié)果，因此時間基于數(shù)據(jù)量的大小呈現(xiàn)上升趨勢。

線性鏈的查找時間和平衡二叉哈希樹的遍歷時間的比較如圖7所示。

圖7 查找時間比較

圖7結(jié)果表明，當(dāng)驗證失敗，需要定位錯誤的時候，線性鏈結(jié)構(gòu)的查找采用順序查找，時間消耗基于數(shù)據(jù)量的大小逐漸升高；平衡二叉哈希樹的遍歷采用先序遍歷，遍歷的時間跟樹的高度相關(guān)。隨著數(shù)據(jù)量的增加，樹的高度較好地維持在O(logn)，查找時間也相對穩(wěn)定。因此組件的度量證據(jù)數(shù)據(jù)量越龐大，平衡二叉哈希樹表現(xiàn)出來的查找優(yōu)勢越明顯。

5 結(jié) 語

本文在總結(jié)了度量證據(jù)生成過程中線性鏈機制錯誤組件查找效率不佳的基礎(chǔ)上，利用二叉樹搜索時間復(fù)雜度為對數(shù)級的特性，構(gòu)造了以平衡二叉哈希樹為數(shù)據(jù)組織形式的度量證據(jù)可信存儲方案，實現(xiàn)了查找效率上的提升。最后搭建實驗平臺，給出鏈?zhǔn)胶蜆涫降亩攘孔C據(jù)構(gòu)造和查詢的時間對比。結(jié)果顯示該方案的空間復(fù)雜度保持在O(n)情況下，查找時間大大減少，性能大大提升。

[1]AndreasUSchmidt,AndreasLeicher,AndreasBrett,etal.Tree-formedVerificationDataforTrustedPlatforms[J].ComputersandSecurity,2012,4(18):1-15.

[2] 李俊中.云存儲環(huán)境下數(shù)據(jù)完整性驗證方法研究[D].重慶:重慶郵電大學(xué),2013.

[3] 朱毅,李清寶,鐘春麗,等.用于細粒度完整性度量的非平衡二叉哈希樹模型[J].小型微型計算機系統(tǒng),2014,7(35):1604-1609.

[4]SchmidtAU,LeicherA,ChaI,etal.Trustedplatformvalidationandmanagement[J].InternationalJournalofDependableandTrustworthyInformationSystems,2010,1(2):1-31.

[5] 王防修,周康.一種構(gòu)建嚴(yán)格平衡二叉搜索樹的非遞歸算法[J].武漢工業(yè)學(xué)院學(xué)報,2013,32(4):32-34.

[6]SchmidtAU,LeicherA,ChaI.Scalingconceptsbetweentrustandenforcement,in:Z.Yan(Ed.),TrustModelingandManagementinDigitalEnvironments:FromSocialConcepttoSystemDevelopment[J].IGIGlobal,Hershey,2010,2(54):20-57.

[7] 中國國家密碼管理局.可信計算密碼支撐平臺功能接口與規(guī)范[EB/OL].[2011-02-19].http://www.oscca.gov.cn/Doc/6/News_1132.htm.

[8] 王江,少余綜,李光.可信計算之信任鏈技術(shù)研究[J].計算機工程與設(shè)計,2008,29(9):2195-2198.

[9]SailerR,ZhangX,JaegerT,etal.DesignandimplementationofaTCG-basedintegritymeasurementarchitecture[J].Proceedingsofthe13thUSENIXSecuritySymposium,2004,7(31):223-238.

[10]ElbazR,ChampagneD,GebotysC,etal.Hardwaremechanismsformemoryauthentication:Asurveyofexistingtechniquesandengines[J].TransactionsonComputationalScience,2009,4(5430):1-22.

THE DESIGN OF CREDIBLE STORAGE SCHEME ON MEASUREMENT EVIDENCE BASED ON HASH TREE

Bing Pizheng Dai Zibin Dai Qiang

(InstituteofCryptographicEngineering,People’sLiberationArmyInformationEngineeringUniversity,Zhengzhou450001,Henan,China)

The credibility of computing platform is verified by the measurement evidence provided in the process of remote attestation procedure, and the verification procedures build trust according to the measurement evidence which is created in the startup process of the computing platform. However, the measurement evidence and the associated measurement record which are created by extended operation of measurement are linear, with a low researching efficiency. Thus, a method of creating measurement evidence is proposed based on balanced binary hash tree. On the computing platform, the component measurement values are represented as leaves, and the set of measurement value of all components are represented as the roots of a hash tree. In the process of verifying computing platform, the hash tree measurement records and the root registers are used to increase the searching speed of fault component when the measurement evidence is compared with the standard value. The experimental results show that the proposed model reduces time cost without increasing space complexity.

Balanced binary hash tree Remote attestation Fault localization Trusted computing

2015-11-04。邴丕政，碩士生，主研領(lǐng)域：信息安全。戴紫彬，教授。戴強，博士。

TP309

A

10.3969/j.issn.1000-386x.2017.01.057