電力物聯(lián)網(wǎng)設(shè)備持續(xù)高效批量可信認(rèn)證

趙保華，王志皓，陳連棟，任春卉，余發(fā)江，徐 慶

1.全球能源互聯(lián)網(wǎng)研究院有限公司，北京 102209；

2.電力系統(tǒng)人工智能（聯(lián)研院）國家電網(wǎng)公司聯(lián)合實(shí)驗(yàn)室，北京 102209；

3.北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京100124；

4.國網(wǎng)河北省電力有限公司信息通信分公司，河北石家莊050021；

5.武漢大學(xué) 國家網(wǎng)絡(luò)安全學(xué)院，湖北 武漢430072

0 引言

隨著電力物聯(lián)網(wǎng)的蓬勃發(fā)展，設(shè)備運(yùn)行的環(huán)境越來越復(fù)雜，物聯(lián)網(wǎng)終端設(shè)備越來越多，而終端設(shè)備通常是資源受限的嵌入式設(shè)備，安全投資不足，在充滿不確定性的物聯(lián)網(wǎng)環(huán)境中很容易遭受攻擊［1，2］。2014年，西班牙三大主要供電服務(wù)商超過30%的智能電表被檢測發(fā)現(xiàn)存在嚴(yán)重的安全漏洞，攻擊者可以利用該漏洞進(jìn)行電費(fèi)欺詐，甚至直接關(guān)閉電路系統(tǒng)［3］。2016年，烏克蘭電力公司因惡意軟件入侵造成了長達(dá)數(shù)小時(shí)的大規(guī)模停電，受災(zāi)人口達(dá)到140萬，造成這一事件的原因是惡意軟件利用了保護(hù)繼電器固件程序中的一個(gè)已知漏洞，禁用了這些設(shè)備的自動(dòng)防護(hù)功能［4］。由此可見，物聯(lián)網(wǎng)設(shè)備受到攻擊時(shí)，其可信狀態(tài)發(fā)生了改變。為了實(shí)現(xiàn)對(duì)設(shè)備狀態(tài)的持續(xù)監(jiān)視，保障物聯(lián)網(wǎng)設(shè)備的安全性，需要采取措施持續(xù)性地對(duì)各物聯(lián)網(wǎng)設(shè)備可信狀態(tài)進(jìn)行認(rèn)證，以在設(shè)備不可信時(shí)及時(shí)發(fā)現(xiàn)并采取措施，減少損失。

針對(duì)以上問題，學(xué)者們提出采用遠(yuǎn)程驗(yàn)證（remote attestation，RA）［5.6］機(jī)制確保終端設(shè)備的可信性。目前遠(yuǎn)程驗(yàn)證根據(jù)設(shè)備能力和設(shè)備安全保障方面的不同要求，可以分為基于軟件的驗(yàn)證和基于可信根的驗(yàn)證?；谲浖倪h(yuǎn)程驗(yàn)證［7~9］通常對(duì)攻擊者行為進(jìn)行強(qiáng)假設(shè)以提供設(shè)備安全保證，并且對(duì)設(shè)備幾乎沒有硬件要求。這種驗(yàn)證僅適用于缺乏硬件安全功能的傳統(tǒng)設(shè)備，以及證明者在物理上靠近驗(yàn)證者的情況?；诳尚鸥倪h(yuǎn)程驗(yàn)證［10~12］依賴于可信平臺(tái)模塊（trusted platform module，TPM）［13］，在設(shè)備啟動(dòng)過程中，度量自身的完整性并被記錄到TPM的平臺(tái)配置寄存器（PCR）中，發(fā)送到遠(yuǎn)程驗(yàn)證方進(jìn)行驗(yàn)證。

鑒于物聯(lián)網(wǎng)系統(tǒng)的規(guī)模和復(fù)雜性，傳統(tǒng)的遠(yuǎn)程驗(yàn)證方案只能單獨(dú)對(duì)各設(shè)備進(jìn)行驗(yàn)證，擴(kuò)展性較差，所以學(xué)者們提出了集體遠(yuǎn)程證明（collective re?mote attestation，CRA）［14，15］協(xié)議，允許驗(yàn)證 者 從整個(gè)設(shè)備網(wǎng)絡(luò)中獲得網(wǎng)絡(luò)的整體狀態(tài)和設(shè)備的個(gè)體狀態(tài)，以提高遠(yuǎn)程驗(yàn)證的可擴(kuò)展性。SEDA［16］是一種用于集體證明的可擴(kuò)展協(xié)議，它允許驗(yàn)證者在設(shè)備集群生成樹上有效地執(zhí)行認(rèn)證；SANA［17］解決了SEDA的一些局限性，它依賴于樂觀聚合簽名（OAS）的加密方法，允許沒有安全硬件的設(shè)備聚合網(wǎng)絡(luò)認(rèn)證報(bào)告。DARPA［18］要求每個(gè)設(shè)備通過記錄心跳信息來定期監(jiān)視其他設(shè)備，以發(fā)現(xiàn)攻擊者對(duì)設(shè)備的物理攻擊，從而減少設(shè)備網(wǎng)絡(luò)中的物理攻擊?，F(xiàn)有集體遠(yuǎn)程證明協(xié)議方案沒有針對(duì)電力物聯(lián)網(wǎng)設(shè)備和架構(gòu)特點(diǎn)進(jìn)行適配，而且在實(shí)際情況中，設(shè)備啟動(dòng)后可能會(huì)進(jìn)行固件版本的更新，有可能會(huì)遭受攻擊，這時(shí)設(shè)備的可信狀態(tài)發(fā)生變化，需要提供對(duì)設(shè)備的持續(xù)多次度量，以確認(rèn)設(shè)備的當(dāng)前可信狀態(tài)。

為了適用于電力物聯(lián)網(wǎng)云邊端協(xié)同的架構(gòu)［19，20］和支持持續(xù)性的批量認(rèn)證，本文提出了一種適用于電力物聯(lián)網(wǎng)設(shè)備的持續(xù)高效批量可信認(rèn)證機(jī)制，所做的貢獻(xiàn)如下：

1）使用一棵非平衡哈希樹存儲(chǔ)設(shè)備度量信息，相較于傳統(tǒng)默克爾哈希樹，減少了樹構(gòu)建和節(jié)點(diǎn)加入的時(shí)間和空間消耗，同時(shí)減少了節(jié)點(diǎn)驗(yàn)證時(shí)傳輸驗(yàn)證所需信息量，提高了驗(yàn)證效率。當(dāng)樹達(dá)到存儲(chǔ)上限時(shí)，采用最近最少使用的方法對(duì)樹中已有節(jié)點(diǎn)進(jìn)行替換，借助一個(gè)哈希表和具有多個(gè)支鏈的雙向鏈表快速找到待替換的樹節(jié)點(diǎn)。

2）提出了一種基于多版本的設(shè)備持續(xù)度量認(rèn)證機(jī)制，將設(shè)備各個(gè)歷史版本的度量信息同時(shí)保存在非平衡哈希樹中，使得設(shè)備在進(jìn)行版本更新后，驗(yàn)證方仍能正確對(duì)其可信狀態(tài)進(jìn)行驗(yàn)證，同時(shí)樹中存儲(chǔ)的設(shè)備多版本度量信息便于對(duì)同一設(shè)備的歷史可信狀態(tài)變化進(jìn)行評(píng)估。

3）采用一種高效的稀疏哈希樹多值認(rèn)證［21，22］方法實(shí)現(xiàn)設(shè)備的批量認(rèn)證。當(dāng)待驗(yàn)證設(shè)備有多個(gè)時(shí)，相較于單值驗(yàn)證，提高了驗(yàn)證所需信息生成效率，減少了傳輸驗(yàn)證所需信息量，同時(shí)提高了設(shè)備驗(yàn)證效率。

1 系統(tǒng)模型和安全威脅

1.1 系統(tǒng)模型

本文提出的電力物聯(lián)網(wǎng)設(shè)備持續(xù)高效批量可信認(rèn)證機(jī)制的系統(tǒng)模型涉及終端設(shè)備E、邊緣代理A和云端平臺(tái)P三類實(shí)體。三類實(shí)體的證書cdk由證書權(quán)威機(jī)構(gòu)進(jìn)行頒發(fā)。終端設(shè)備與邊緣代理均采用一種輕量的可信度量架構(gòu)［23，24］進(jìn)行自身可信度量并向邊緣代理和云端平臺(tái)報(bào)告度量狀態(tài)，邊緣代理使用一棵非平衡哈希樹DAT、一條多鏈L和一個(gè)哈希表HT存儲(chǔ)終端設(shè)備的度量狀態(tài)信息，云端平臺(tái)對(duì)邊緣代理進(jìn)行身份和可信狀態(tài)認(rèn)證，對(duì)終端設(shè)備的可信狀態(tài)進(jìn)行驗(yàn)證。實(shí)體間的交互過程可以分為兩部分：持續(xù)性認(rèn)證和批量認(rèn)證。該機(jī)制系統(tǒng)模型如圖1所示。

圖1 系統(tǒng)模型Fig.1 System model

1）持續(xù)性認(rèn)證過程。①終端設(shè)備可信度量。終端設(shè)備由設(shè)備標(biāo)識(shí)di和不可更改的可信根代碼tr生成復(fù)合設(shè)備標(biāo)識(shí)cdiE，然后根據(jù)cdiE生成設(shè)備密鑰dkE，用作與邊緣代理通信時(shí)的簽名密鑰，再根據(jù)應(yīng)用固件的實(shí)際度量值和cdiE生成認(rèn)證密鑰akE，用于描述設(shè)備當(dāng)前的可信狀態(tài)。②終端設(shè)備度量值報(bào)告。邊緣代理向終端設(shè)備發(fā)送一個(gè)隨機(jī)數(shù)r1作為挑戰(zhàn)信息，終端設(shè)備對(duì)認(rèn)證密鑰的公鑰pakE和r1簽名，將證書cdkE、公鑰pakE和簽名報(bào)告給邊緣代理。③邊緣代理度量值存儲(chǔ)。邊緣代理對(duì)簽名進(jìn)行驗(yàn)證以確認(rèn)設(shè)備身份，驗(yàn)證通過則將pakE的哈希值存儲(chǔ)在非平衡哈希樹中。實(shí)際情況中，一個(gè)邊緣代理會(huì)管理多個(gè)終端設(shè)備的度量信息，上述過程會(huì)進(jìn)行多次，以存儲(chǔ)記錄設(shè)備的多個(gè)版本度量信息，實(shí)現(xiàn)對(duì)設(shè)備持續(xù)性的認(rèn)證。

2）批量認(rèn)證過程。①邊緣代理可信度量。云端平臺(tái)作為驗(yàn)證者向邊緣代理發(fā)起認(rèn)證請求，發(fā)送待驗(yàn)證的設(shè)備集合S和一個(gè)隨機(jī)數(shù)r2作為挑戰(zhàn)信息，邊緣代理首先由輕量級(jí)可信度量架構(gòu)進(jìn)行自身可信度量，生成akA，過程與終端設(shè)備可信度量類似。②邊緣代理證明信息報(bào)告。邊緣代理根據(jù)待驗(yàn)證集合S，從非平衡哈希樹中生成其對(duì)應(yīng)的驗(yàn)證所需證明信息w（w是驗(yàn)證路徑上所需樹節(jié)點(diǎn)的哈希值集合），對(duì)r2、w、pakA和待驗(yàn)證設(shè)備的版本信息簽名并報(bào)告給云端平臺(tái)。③云端平臺(tái)批量認(rèn)證。云端平臺(tái)先對(duì)簽名進(jìn)行驗(yàn)證，驗(yàn)證通過后對(duì)邊緣代理的可信狀態(tài)進(jìn)行驗(yàn)證，然后根據(jù)w和設(shè)備基準(zhǔn)度量值sv對(duì)所有終端設(shè)備的可信狀態(tài)進(jìn)行批量認(rèn)證。

1.2 安全威脅

根據(jù)攻擊者具有的能力和攻擊策略，可以將攻擊者的行為分為兩種類型［25，26］。

1）對(duì)終端設(shè)備與邊緣代理、邊緣代理與云端平臺(tái)間的通信過程進(jìn)行攻擊。攻擊者具有對(duì)通信信道的完全控制權(quán)，可以對(duì)實(shí)體間通信信息進(jìn)行竊聽、修改和重放等操作；

2）攻擊物聯(lián)網(wǎng)設(shè)備。攻擊者可以利用漏洞入侵物聯(lián)網(wǎng)設(shè)備，讀取其未受保護(hù)的內(nèi)存區(qū)域，操控軟件狀態(tài)，但無法偽造邊緣代理和終端設(shè)備的設(shè)備證書cdk。對(duì)物聯(lián)網(wǎng)設(shè)備的攻擊可以分為對(duì)終端設(shè)備和邊緣代理的攻擊。攻擊者入侵終端設(shè)備，可能修改固件層的代碼；攻擊者入侵邊緣代理，可能修改其非平衡哈希樹、多鏈和哈希表結(jié)構(gòu)，

安全假設(shè)：假設(shè)1，非平衡哈希樹采用的哈希函數(shù)是抗碰撞的；假設(shè)2，云端平臺(tái)作為驗(yàn)證方是安全的；假設(shè)3，終端設(shè)備和邊緣代理具有的設(shè)備標(biāo)識(shí)di和可信根代碼tr不會(huì)被攻擊者篡改。

2 結(jié)構(gòu)與操作

本文將邊緣代理用于設(shè)備度量信息存儲(chǔ)的結(jié)構(gòu)中，非平衡哈希樹用于存儲(chǔ)設(shè)備的認(rèn)證密鑰信息，多鏈結(jié)構(gòu)用于樹達(dá)到存儲(chǔ)上限時(shí)尋找待替換節(jié)點(diǎn)，哈希表用于根據(jù)設(shè)備id檢索其對(duì)應(yīng)的多鏈節(jié)點(diǎn)。

2.1 設(shè)備認(rèn)證密鑰非平衡哈希樹

傳統(tǒng)默克爾哈希樹是一棵滿二叉樹，在樹的構(gòu)建和節(jié)點(diǎn)添加過程中，當(dāng)處理的當(dāng)前層節(jié)點(diǎn)數(shù)目為奇數(shù)時(shí)，通常會(huì)將該層節(jié)點(diǎn)中的其中一個(gè)復(fù)制一份湊成偶數(shù)，這樣會(huì)導(dǎo)致樹中存在大量重復(fù)的中間節(jié)點(diǎn)，在樹的構(gòu)建和節(jié)點(diǎn)加入時(shí)會(huì)有額外的時(shí)間和空間消耗。同時(shí)在生成多值路徑的過程中，由于添加的額外節(jié)點(diǎn)增大了默克爾哈希樹右側(cè)葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長度，使得這部分葉子節(jié)點(diǎn)的認(rèn)證路徑較長，生成的多值路徑空間較大，影響云端平臺(tái)的認(rèn)證效率。所以本文采用了非平衡哈希樹，彌補(bǔ)默克爾哈希樹的不足。

非平衡哈希樹是一棵二叉樹，其節(jié)點(diǎn)表示為Ni，j，i為節(jié)點(diǎn)所在層號(hào)，j為節(jié)點(diǎn)在該層的序號(hào)，層號(hào)從葉子節(jié)點(diǎn)層到根從0開始編號(hào)，每層的節(jié)點(diǎn)從左到右從0開始編號(hào)。樹中葉子節(jié)點(diǎn)N0，j（j=0，1，…，n）存儲(chǔ)一個(gè)設(shè)備的度量認(rèn)證密鑰pakE的哈希值及設(shè)備id和 固 件 版 本 號(hào)ver，即N0，j= id，ver，val，其 中val=Hash(pakid，ver)。而中間節(jié)點(diǎn)Ni，j（i>0）的val值是其左右子節(jié)點(diǎn)哈希值鏈接后的哈希變換，即val=Hash(Nleft||Nright)。

非平衡哈希樹每次添加設(shè)備度量信息時(shí)，會(huì)增加一個(gè)葉子節(jié)點(diǎn)和一個(gè)中間節(jié)點(diǎn)。由此種方式構(gòu)建的樹，除葉子節(jié)點(diǎn)外的任意節(jié)點(diǎn)的左子樹都是一棵滿二叉樹，而右子樹也是一棵非平衡哈希樹。

節(jié)點(diǎn)添加過程append操作和樹的變化如圖2所示，圖中實(shí)線圓圈節(jié)點(diǎn)為樹節(jié)點(diǎn)，虛線方框內(nèi)是葉子節(jié)點(diǎn)存儲(chǔ)的對(duì)應(yīng)認(rèn)證密鑰信息。

圖2 非平衡樹節(jié)點(diǎn)添加示意圖Fig.2 The diagram of adding unbalanced tree nodes

2.1.1 樹未達(dá)到存儲(chǔ)上限時(shí)加入

Append（算法1）完成非平衡樹未達(dá)存儲(chǔ)上限時(shí)認(rèn)證密鑰加入到非平衡樹的操作，過程如下：首先生成兩個(gè)節(jié)點(diǎn)，分別是中間節(jié)點(diǎn)Nmid以及葉子節(jié)點(diǎn)Nleaf。根據(jù)待加入的設(shè)備度量值信息pakE，計(jì)算出相應(yīng)葉子節(jié)點(diǎn)Nleaf的值val(=Hash(pakE))。然后從根節(jié)點(diǎn)開始，判斷以每層最右邊節(jié)點(diǎn)為根節(jié)點(diǎn)的樹是否為滿樹，找到第一個(gè)為滿樹的節(jié)點(diǎn)Nfull，將節(jié)點(diǎn)Nmid作為該節(jié)點(diǎn)和節(jié)點(diǎn)Nleaf的父節(jié)點(diǎn)，更新節(jié)點(diǎn)Nleaf到非平衡樹根節(jié)點(diǎn)路徑上各節(jié)點(diǎn)的哈希值。Append具體過程如算法1。

?

2.1.2 樹達(dá)到存儲(chǔ)上限時(shí)加入

邊緣代理的存儲(chǔ)能力通常有限，需要給該樹結(jié)構(gòu)定義一個(gè)存儲(chǔ)閾值cap，以表示該非平衡樹可以存儲(chǔ)的最大認(rèn)證密鑰數(shù)目，并用n記錄當(dāng)前樹中已存儲(chǔ)的度量值數(shù)目。當(dāng)n=cap時(shí)，樹已達(dá)到存儲(chǔ)上限，需要通過策略尋找并更新樹中已有的某個(gè)葉子節(jié)點(diǎn)，本文采用的策略將在2.2節(jié)中介紹。

假設(shè)已通過2.2節(jié)策略找到了樹中待替換的節(jié)點(diǎn)對(duì)應(yīng)的多鏈節(jié)點(diǎn)lnode。然后執(zhí)行update（算法2）完成樹已滿時(shí)認(rèn)證密鑰加入到非平衡樹的操作。

?

首先由節(jié)點(diǎn)lnode得到樹中待替換的節(jié)點(diǎn)Nleaf，將id和ver更新到該節(jié)點(diǎn)，然后更新Nleaf到根節(jié)點(diǎn)路徑上所有節(jié)點(diǎn)值。

2.1.3 多路徑生成

非平衡哈希樹與默克爾哈希樹一樣可以提供多值路徑mp以證明樹中特定節(jié)點(diǎn)存在于節(jié)點(diǎn)集合中，本節(jié)先以一個(gè)例子說明mp的生成過程，然后將過程歸納為算法3。以云端平臺(tái)驗(yàn)證設(shè)備S={E1，1，E2，1，E3，1，E3，2}為例，假設(shè)此時(shí)非平衡哈希樹如圖3所示（圖中陰影是待驗(yàn)證的設(shè)備對(duì)應(yīng)樹中結(jié)點(diǎn)）。

圖3 非平衡哈希樹Fig.3 Unbalanced Hash tree

mp的生成過程從樹的葉子節(jié)點(diǎn)層一直迭代到根節(jié)點(diǎn)，具體步驟如下。

1）0層

設(shè) 備E1，1，E2，1，E3，1，E3，2對(duì) 應(yīng) 的 第0層 的 節(jié) 點(diǎn) 編號(hào)分別為0、1、2、6，分別為這些編號(hào)添加一個(gè)相鄰編號(hào)生成編號(hào)對(duì)，且編號(hào)對(duì)第一個(gè)元素為偶數(shù)，第二個(gè)元素為奇數(shù)，得到的編號(hào)對(duì)為［0，1］、［0，1］、［2，3］、［6，7］，將這些編號(hào)對(duì)去重得到［0，1］、［2，3］、［6，7］，該編號(hào)對(duì)中除去0、1、2、6編號(hào)后剩余的節(jié)點(diǎn)編號(hào)為3、7，由于第0層中沒有7號(hào)節(jié)點(diǎn)，所以將去除無效節(jié)點(diǎn)7后的編號(hào)對(duì)應(yīng)的節(jié)點(diǎn)添加到mp中，此時(shí)mp={N0，3}，將各編號(hào)對(duì)的左端點(diǎn)除以2得到第1層對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)0、1、3。

2）1層

第1層對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)為0、1、3。為這些節(jié)點(diǎn)生成編號(hào)對(duì)并去重得到［0，1］、［2，3］，將該編號(hào)對(duì)中除去0、1、3編號(hào)后的剩余節(jié)點(diǎn)編號(hào)2對(duì)應(yīng)的節(jié)點(diǎn)添加到mp中，此時(shí)mp={N0，3，N1，2}，將各編號(hào)對(duì)的左端點(diǎn)除以2得到第2層對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)0、1。

3）2層

第2層對(duì)應(yīng)的節(jié)點(diǎn)編號(hào)為0、1。為這些節(jié)點(diǎn)生成編號(hào)對(duì)并去重得到［0，1］，此時(shí)該編號(hào)對(duì)中除去0和1后已無節(jié)點(diǎn)，迭代結(jié)束。最終生成的mp={N0，3，N1，2}。

上述過程可用算法3描述。

2.2 歷史版本設(shè)備多鏈與哈希表

當(dāng)樹達(dá)到存儲(chǔ)上限時(shí)，為了快速找出樹中待替換的節(jié)點(diǎn)，本文采用了一種最近最少使用的方法，即最不經(jīng)常更新版本度量信息的設(shè)備就是最不活躍的，被認(rèn)為是較為穩(wěn)定的，替換時(shí)就替換該設(shè)備對(duì)應(yīng)的最舊版本度量信息，同時(shí)需要注意，應(yīng)該為每個(gè)id的設(shè)備至少保留一個(gè)最新版本的度量值，以支持對(duì)該設(shè)備的驗(yàn)證。要實(shí)現(xiàn)該方案，本文采用了一個(gè)多鏈和一個(gè)哈希表。多鏈和哈希表結(jié)構(gòu)如圖4所示。

圖4 多鏈和哈希表Fig.4 Multichain and Hash table

多鏈由一條主鏈和主鏈上節(jié)點(diǎn)延伸的支鏈組成，主鏈?zhǔn)且粭l雙向鏈表，主鏈節(jié)點(diǎn)m_ln=id，tree_node，num ，其中，id為設(shè)備id，tree_node為設(shè)備在非平衡樹中最舊版本的節(jié)點(diǎn)信息，num為以該節(jié)點(diǎn)為頭節(jié)點(diǎn)的支鏈長度。支鏈b_ln=id，tree_node ，其中存儲(chǔ)的是與主鏈節(jié)點(diǎn)同屬一個(gè)設(shè)備id的后續(xù)度量值在非平衡樹中的節(jié)點(diǎn)信息。為了便于根據(jù)設(shè)備id檢索多鏈節(jié)點(diǎn)，本文為主鏈節(jié)點(diǎn)建立了一個(gè)哈希表，哈希表中節(jié)點(diǎn)鍵為設(shè)備id，值為該設(shè)備id在多鏈結(jié)構(gòu)中對(duì)應(yīng)的主鏈節(jié)點(diǎn)信息。

在進(jìn)行設(shè)備度量信息加入非平衡哈希樹操作時(shí)，多鏈和哈希表執(zhí)行算法4將添加的葉子節(jié)點(diǎn)信息同步更新到多鏈和哈希表結(jié)構(gòu)，當(dāng)樹達(dá)到存儲(chǔ)上限后，多鏈和哈希表執(zhí)行算法5找到并刪除樹中待替換的節(jié)點(diǎn)對(duì)應(yīng)的多鏈節(jié)點(diǎn)。

?

2.2.1 加入和更新

Apd Mov（算法4）完成非平衡哈希樹增加節(jié)點(diǎn)時(shí)多鏈和哈希表的更新操作。首先根據(jù)設(shè)備id查找哈希表中是否有該id設(shè)備的節(jié)點(diǎn)，分為兩種情況操作：

①未找到。生成多鏈節(jié)點(diǎn)ln，將其插入到多鏈的首部，num字段置為1，更新哈希表HT[id]=ln；

②找到。根據(jù)查到的結(jié)果找到其所在多鏈中的節(jié)點(diǎn)，生成一個(gè)代表En，m的多鏈節(jié)點(diǎn)ln并鏈在該節(jié)點(diǎn)下支鏈的尾部，再將支鏈頭節(jié)點(diǎn)num字段加1，并將整條支鏈移動(dòng)到多鏈?zhǔn)撞俊?/p>

?

假設(shè)當(dāng)前哈希表和多鏈結(jié)構(gòu)如圖5（a）所示，當(dāng)有新度量值E4，1加入時(shí)，首先查詢哈希表，由于哈希表中沒有設(shè)備id為4的設(shè)備的度量值版本，所以生成一個(gè)多鏈節(jié)點(diǎn)E4，1，將其添加到多鏈?zhǔn)撞?，同時(shí)生成一個(gè)哈希表節(jié)點(diǎn)，其鍵為4，值為對(duì)應(yīng)的多鏈節(jié)點(diǎn)E4，1信息，如圖5（b）所示。

2.2.2 查找并刪除

當(dāng)非平衡哈希樹中的葉子節(jié)點(diǎn)達(dá)到閾值時(shí)，執(zhí)行FindDel（算法5）找到樹中待替換的節(jié)點(diǎn)。

由于樹已滿，需要找到樹中待換出的節(jié)點(diǎn)。首先從多鏈主鏈的鏈尾向鏈?zhǔn)走M(jìn)行遍歷，找到第一個(gè)子鏈數(shù)目大于2的節(jié)點(diǎn)head_lni，該節(jié)點(diǎn)即為需替換的節(jié)點(diǎn)，將其從鏈表中移除，其子鏈取代它的位置。若子鏈數(shù)目均不大于2，則查找子鏈節(jié)點(diǎn)數(shù)為2的節(jié)點(diǎn)作替換，若所有子鏈中節(jié)點(diǎn)數(shù)目均為1，則該邊緣代理負(fù)荷較重，相應(yīng)待添加的設(shè)備應(yīng)轉(zhuǎn)移到另外的負(fù)荷較小的邊緣代理管理。

?

以度量值E4，2加入時(shí)為例，假定樹的存儲(chǔ)能力為8，此時(shí)樹已滿。首先執(zhí)行算法4，根據(jù)設(shè)備id查找哈希表中id為4的設(shè)備，找到其所在多鏈中的節(jié)點(diǎn)，將該節(jié)點(diǎn)的num字段加1，生成一個(gè)代表E4，2的多鏈節(jié)點(diǎn)并鏈在該節(jié)點(diǎn)支鏈的尾部，將該支鏈移動(dòng)到多鏈?zhǔn)撞?。然后?zhí)行算法5從鏈尾向鏈?zhǔn)走M(jìn)行遍歷，找到第一個(gè)子鏈數(shù)目大于2的節(jié)點(diǎn)E1，1，該節(jié)點(diǎn)即為需替換的節(jié)點(diǎn)，將其從鏈表中移除，其支鏈中下一個(gè)節(jié)點(diǎn)E1，2取代它的位置，更新后的結(jié)構(gòu)如圖5（c）所示。

圖5 哈希表和多鏈變化Fig.5 The change of Hash table and multichain

3 設(shè)備持續(xù)批量認(rèn)證機(jī)制

借助第2節(jié)的非平衡哈希樹、多鏈和哈希表結(jié)構(gòu)可實(shí)現(xiàn)終端設(shè)備的持續(xù)性和批量認(rèn)證。本節(jié)對(duì)設(shè)備的持續(xù)性和批量認(rèn)證機(jī)制分別進(jìn)行說明。

3.1 基于多版本的設(shè)備持續(xù)性認(rèn)證

終端設(shè)備啟動(dòng)時(shí)進(jìn)行自身可信度量，根據(jù)自身底層標(biāo)識(shí)和核心層代碼度量值計(jì)算得到復(fù)合設(shè)備標(biāo)識(shí)符，然后生成用于與邊緣代理之間通信的設(shè)備密鑰dkE，再根據(jù)應(yīng)用固件的度量值和復(fù)合設(shè)備標(biāo)識(shí)符生成認(rèn)證密鑰akE并報(bào)告給邊緣代理。邊緣代理向終端設(shè)備發(fā)送隨機(jī)數(shù)r1，設(shè)備用dkE私鑰對(duì)挑戰(zhàn)消息r1和akE公鑰進(jìn)行簽名得到σE并發(fā)送回邊緣代理。邊緣代理對(duì)簽名進(jìn)行驗(yàn)證，驗(yàn)證通過則執(zhí)行算法6，將akE公鑰以哈希值形式保存在非平衡哈希樹中。

?

邊緣代理的存儲(chǔ)資源是有限度的，通常一個(gè)邊緣代理只負(fù)責(zé)管理適量的終端設(shè)備，但是要對(duì)這些設(shè)備進(jìn)行持續(xù)性度量，設(shè)備固件更新時(shí)，其度量值認(rèn)證密鑰也會(huì)更新，這將導(dǎo)致非平衡樹中的節(jié)點(diǎn)數(shù)目不斷增多，當(dāng)樹中已有度量值數(shù)目n

3.2 批量認(rèn)證

各個(gè)邊緣代理管理的終端設(shè)備眾多，單獨(dú)認(rèn)證各設(shè)備效率低下，所以本文采取稀疏哈希樹多值認(rèn)證的方法對(duì)終端設(shè)備進(jìn)行批量認(rèn)證，減少了傳輸多路徑信息的數(shù)據(jù)量。

批量認(rèn)證的過程在1.1節(jié)進(jìn)行了簡要描述，其關(guān)鍵過程可以分為兩個(gè)部分：①邊緣代理證明信息w生成；②云端認(rèn)證平臺(tái)認(rèn)證。當(dāng)云端認(rèn)證平臺(tái)需要 對(duì) 設(shè) 備S={E1，1，E1，2，…，E1，j，…，E2，1，E2，2，…，Ei，j}進(jìn)行認(rèn)證時(shí)，先將隨機(jī)數(shù)r2和需認(rèn)證設(shè)備集合S發(fā)送給邊緣代理，邊緣代理執(zhí)行算法7生成待認(rèn)證設(shè)備認(rèn)證所需的證明信息w，用其私鑰sdkA對(duì)w和待驗(yàn)證設(shè)備版本信息簽名后發(fā)送給云端認(rèn)證平臺(tái)，云端平臺(tái)先對(duì)簽名進(jìn)行驗(yàn)證，然后執(zhí)行算法8對(duì)設(shè)備度量值進(jìn)行驗(yàn)證，得到驗(yàn)證結(jié)果。

?

3.2.1 邊緣代理證明信息w的生成

邊緣代理執(zhí)行witGen生成待驗(yàn)證設(shè)備的證明信息w。w包含一個(gè)位圖bm和一個(gè)哈希表map，bm是待驗(yàn)證設(shè)備所有版本對(duì)應(yīng)的非平衡哈希樹中葉子節(jié)點(diǎn)序號(hào)，哈希表是由算法3生成的多值路徑信息，哈希表的鍵是一個(gè)二元組，包含節(jié)點(diǎn)在非平衡哈希樹中的層號(hào)和在該層的序號(hào)，值是該節(jié)點(diǎn)對(duì)應(yīng)的哈希值。witGen根據(jù)待驗(yàn)證設(shè)備對(duì)應(yīng)的非平衡樹中節(jié)點(diǎn)編號(hào)，將bm的相應(yīng)位置為1，然后根據(jù)mp Gen（算法3）填充map。

3.2.2 云端認(rèn)證平臺(tái)批量認(rèn)證

假設(shè)云端認(rèn)證平臺(tái)已從邊緣代理獲取到認(rèn)證設(shè) 備S={E1，1，E1，2，…，E1，j，…，E2，1，E2，2，…，Ei，j}所需的證明信息w，然后根據(jù)邊緣代理發(fā)送過來的待驗(yàn)證設(shè)備版本獲取相應(yīng)設(shè)備標(biāo)準(zhǔn)度量值sv和復(fù)合設(shè)備標(biāo)識(shí)符cdiE，重構(gòu)出設(shè)備的ak密鑰akE=KeyGen(cdiE，Hash(sv))。對(duì)設(shè)備對(duì)應(yīng)的葉子節(jié)點(diǎn)，由重構(gòu)的ak公鑰重構(gòu)葉子節(jié)點(diǎn)的值Nleaf=Hash(pakE)。從第0層開始向高層迭代，通過已計(jì)算出的葉子節(jié)點(diǎn)值與w中的節(jié)點(diǎn)信息，不斷計(jì)算出下一層節(jié)點(diǎn)值，運(yùn)算過程一直持續(xù)到計(jì)算出根節(jié)點(diǎn)，通過比較得到的根節(jié)點(diǎn)值和邊緣代理傳過來的w中根節(jié)點(diǎn)是否一致，判斷認(rèn)證路徑上的節(jié)點(diǎn)是否是可信、未被篡改的。認(rèn)證過程如算法8所示。

?

4 安全性分析與性能分析

4.1 安全性分析

4.1.1 防止攻擊者對(duì)傳輸消息的竊聽、修改和重放

實(shí)體間的通信主要發(fā)生在終端設(shè)備與邊緣代理間、邊緣代理與云端平臺(tái)間。當(dāng)攻擊者對(duì)實(shí)體間傳輸?shù)南⑦M(jìn)行竊聽后，由于傳輸?shù)南⑹窃O(shè)備的認(rèn)證公鑰pakE、pakA，證明信息w和簽名信息σ是無需保密的內(nèi)容，所以不會(huì)造成影響。當(dāng)攻擊者進(jìn)一步對(duì)竊聽到的消息進(jìn)行修改后，由于消息用發(fā)送方的私鑰進(jìn)行了簽名，接收方會(huì)首先用發(fā)送方的公鑰對(duì)簽名進(jìn)行驗(yàn)證，而發(fā)送方的公鑰證書是安全的，所以攻擊者的修改行為總是會(huì)被發(fā)現(xiàn)。當(dāng)攻擊者進(jìn)行重放攻擊時(shí)，由于每次通信都采用了一個(gè)隨機(jī)數(shù)，該隨機(jī)數(shù)也一同被簽名，有效防止了攻擊者的重放攻擊。

4.1.2 防止攻擊者對(duì)終端設(shè)備和邊緣代理的攻擊

攻擊者攻擊終端設(shè)備并修改其固件層代碼時(shí)，由于終端設(shè)備采用了一種輕量的可信度量架構(gòu)進(jìn)行自身可信度量，修改其固件層代碼C1會(huì)導(dǎo)致度量時(shí) 生 成 的ak′E=KeyGen(cdiE，Hash(C′1))，其 公 鑰部分pak′E會(huì)存儲(chǔ)在邊緣代理的非平衡哈希樹中。當(dāng)云端平臺(tái)進(jìn)行認(rèn)證時(shí)，根據(jù)設(shè)備固件層代碼的基準(zhǔn) 值 重 構(gòu) 出akE=KeyGen(cdiE，Hash(C1))，顯 然akE≠ak′E，認(rèn)證失敗，云端平臺(tái)可以就此發(fā)現(xiàn)設(shè)備可信狀態(tài)的變化并采取防護(hù)措施。

攻擊者攻擊邊緣代理并修改其非平衡哈希樹、多鏈和哈希表結(jié)構(gòu)。當(dāng)云端平臺(tái)發(fā)起認(rèn)證請求后，邊緣代理會(huì)為其偽造的樹節(jié)點(diǎn)val′=Hash(pak′E)生成一個(gè)證明信息w′并傳回，然而云端平臺(tái)會(huì)用設(shè)備的基準(zhǔn)度量值重構(gòu)pakE，并計(jì)算葉子節(jié)點(diǎn)值val=Hash(pakE)。攻擊者有兩種情況可達(dá)成攻擊目的，①使val′=val，此 時(shí) 有Hash(pak′E)=Hash(pakE)，而pak′E≠pakE，所以需要找到哈希函數(shù)的碰撞；②val′≠val，此時(shí)需要偽造w′使驗(yàn)證時(shí)計(jì)算出的根節(jié)點(diǎn)值保持不變。由于非平衡哈希樹中間節(jié)點(diǎn)是其左右子節(jié)點(diǎn)值鏈接后的哈希變換，此種情況也必須找到哈希函數(shù)的碰撞。

綜上所述，在1.2節(jié)的安全假設(shè)前提下，該電力物聯(lián)網(wǎng)設(shè)備的持續(xù)高效批量可信認(rèn)證機(jī)制是安全的。

4.2 性能分析

本節(jié)對(duì)多值認(rèn)證的性能進(jìn)行分析。假設(shè)非平衡哈希樹中葉子節(jié)點(diǎn)數(shù)目為n，待驗(yàn)證設(shè)備數(shù)目為i。對(duì)于單值認(rèn)證而言，每個(gè)設(shè)備版本都需要單獨(dú)進(jìn)行一次證明信息w生成，每次生成的時(shí)間復(fù)雜度與非平衡哈希樹的高度有關(guān)，為O（logn），總生成時(shí)間復(fù)雜度為O（ilogn）。每個(gè)w的大小相等，它包含節(jié)點(diǎn)哈希值數(shù)目與待驗(yàn)證設(shè)備數(shù)目，和非平衡哈希樹的高度有關(guān)。假設(shè)單個(gè)節(jié)點(diǎn)哈希值大小為b，則w占用存儲(chǔ)空間大小為iblogn。驗(yàn)證時(shí)，對(duì)每個(gè)設(shè)備版本都要單獨(dú)進(jìn)行驗(yàn)證，每次單獨(dú)驗(yàn)證時(shí)間復(fù)雜度為O（logn），單值驗(yàn)證總驗(yàn)證時(shí)間復(fù)雜度為O（ilogn）。

對(duì)于多值認(rèn)證而言，所有待驗(yàn)證設(shè)備只需生成一個(gè)w，其生成和驗(yàn)證過程只需進(jìn)行一次，時(shí)間復(fù)雜度和w占用空間大小均與待驗(yàn)證設(shè)備的數(shù)目及其在非平衡哈希樹中的分布有關(guān)。①當(dāng)i=1時(shí)，生成和驗(yàn)證時(shí)間復(fù)雜度為O（logn），與待驗(yàn)證設(shè)備數(shù)為1的單值認(rèn)證相同，w占用存儲(chǔ)空間大小為blogn。②當(dāng)i=n/2時(shí)，生成和驗(yàn)證時(shí)間復(fù)雜度和w占用存儲(chǔ)空間大小與待驗(yàn)證節(jié)點(diǎn)在樹中的分布有關(guān)，當(dāng)所有的待驗(yàn)證葉節(jié)點(diǎn)都集中在非平衡哈希樹根節(jié)點(diǎn)的左子樹時(shí)，消耗的時(shí)間和空間最少，生成和驗(yàn)證時(shí)間復(fù)雜度為O（n），占用空間為2b；當(dāng)所有的待驗(yàn)證葉子節(jié)點(diǎn)在葉子節(jié)點(diǎn)層的節(jié)點(diǎn)序號(hào)都為偶數(shù)時(shí)，消耗的時(shí)間和空間最多，生成和驗(yàn)證時(shí)間復(fù)雜度為O（3n/2），占用空間為bn/2。③當(dāng)i=n時(shí)，生成和驗(yàn)證時(shí)間復(fù)雜度為O（2n），此時(shí)需要的w只包含根節(jié)點(diǎn)的哈希值，占用空間大小為b。多值認(rèn)證和單值認(rèn)證的性能比較如表1所示。

表1 多值認(rèn)證和單值認(rèn)證性能比較Table 1 Performance comparison between multi value authentication and single value authentication

對(duì)于w生成和驗(yàn)證的時(shí)間復(fù)雜度，情況①時(shí)，多值認(rèn)證與單值認(rèn)證相同。情況②時(shí)，取時(shí)間復(fù)雜度最高的情況，多值認(rèn)證為O（3n/2），而此時(shí)單值認(rèn)證為O（n/2logn），當(dāng)n>8時(shí)，多值認(rèn)證就優(yōu)于單值認(rèn)證，而實(shí)際使用中，n會(huì)遠(yuǎn)大于8。情況③時(shí)，當(dāng)n>4時(shí)，多值認(rèn)證會(huì)優(yōu)于單值認(rèn)證，實(shí)際使用中，n會(huì)遠(yuǎn)大于4。

對(duì)于w占用空間大小，情況①時(shí)，多值認(rèn)證和單值認(rèn)證w占用空間相同；情況②時(shí)，取多值認(rèn)證w空間復(fù)雜度最高的情況，為bn/2，此時(shí)單值認(rèn)證w空間大小為bn/2logn，當(dāng)非平衡哈希樹葉子節(jié)點(diǎn)數(shù)大于2時(shí)，多值認(rèn)證更優(yōu)；情況③時(shí)，單值認(rèn)證的w占用空間大小為nblogn，顯然多值認(rèn)證更優(yōu)。

綜上所述，多值認(rèn)證相較于單值認(rèn)證而言，充分利用了各待驗(yàn)證設(shè)備的度量信息，極大限度地減少了所需的中間節(jié)點(diǎn)哈希值數(shù)目和w生成及驗(yàn)證時(shí)間。下面以一個(gè)例子說明，當(dāng)樹中有設(shè)備S={E1，1，E2，1，…，E3，2}時(shí)，要 認(rèn) 證 設(shè) 備 版 本E3，1，w應(yīng) 該含有的 節(jié)點(diǎn)經(jīng) 哈希變 換后為［N0，3，N1，0，N2，1，N3，0］；要認(rèn)證設(shè)備版本E2，2，w應(yīng)該含有的節(jié)點(diǎn)經(jīng)哈希變換后為［N0，2，N1，0，N2，1，N3，0］，單值認(rèn)證兩個(gè)設(shè)備時(shí)，w共需要存儲(chǔ)8個(gè)節(jié)點(diǎn)的哈希值，而當(dāng)批量認(rèn)證兩個(gè)設(shè)備時(shí)，w為［N1，0，N2，1，N3，0］，只需存儲(chǔ)3個(gè)值即可，如圖6所示（葉子節(jié)點(diǎn)的陰影是上文例子中要驗(yàn)證的設(shè)備對(duì)應(yīng)樹中的節(jié)點(diǎn)，中間節(jié)點(diǎn)的陰影是驗(yàn)證葉子節(jié)點(diǎn)所需要的中間節(jié)點(diǎn)）。

圖6 w需包含的節(jié)點(diǎn)Fig.6 Nodes to be included in w

5 實(shí)驗(yàn)分析

5.1 實(shí)驗(yàn)系統(tǒng)

為了方便說明，我們將系統(tǒng)涉及的三類實(shí)體終端設(shè)備E、邊緣代理A和云端認(rèn)證平臺(tái)P抽象為三個(gè)服務(wù)器，使用C++語言實(shí)現(xiàn)了各實(shí)體間的交互。

實(shí)驗(yàn)系統(tǒng)使用openssl生成CA的證書，然后用CA分別為三個(gè)實(shí)體生成自己的證書，這些證書保存在本地。三個(gè)實(shí)體間通過TCP建立連接并傳輸信息，通過SSL協(xié)議相互驗(yàn)證各自的證書以確定通信對(duì)方的身份，隨后實(shí)體間交互的信息均在該信道內(nèi)傳輸。

實(shí)驗(yàn)使用C++代碼模擬了終端設(shè)備E和邊緣代理A的輕量級(jí)可信認(rèn)證的過程，使用隨機(jī)數(shù)分別模擬設(shè)備的度量值和設(shè)備標(biāo)識(shí)cdiE，當(dāng)A請求獲取度量值時(shí)，E生成多個(gè)不同的設(shè)備度量信息pakE，簽名并發(fā)送給A。當(dāng)P請求批量認(rèn)證時(shí)，A生成w與自身的pakA，簽名并發(fā)送給P?？紤]到云端平臺(tái)與邊緣代理網(wǎng)絡(luò)環(huán)境的復(fù)雜性，信息傳輸時(shí)間差異較大，為了簡便，實(shí)驗(yàn)中的批量認(rèn)證效率僅考慮邊緣代理w生成過程和云端平臺(tái)w驗(yàn)證過程，忽略w在網(wǎng)絡(luò)中傳輸所耗時(shí)間。

實(shí)驗(yàn)在邊緣代理定義了非平衡哈希樹及其節(jié)點(diǎn)的結(jié)構(gòu)，該非平衡哈希樹被用來存儲(chǔ)設(shè)備的度量信息pakE，同時(shí)該樹會(huì)以xml的格式持久化存儲(chǔ)到邊緣代理的磁盤中。該非平衡哈希樹實(shí)現(xiàn)了第2節(jié)中介紹的幾種功能。

5.2 認(rèn)證效率分析

本節(jié)通過實(shí)驗(yàn)比較了電力物聯(lián)網(wǎng)持續(xù)批量認(rèn)證機(jī)制在使用多值認(rèn)證和單值認(rèn)證時(shí)的效率。實(shí)驗(yàn)運(yùn)行的物理機(jī)為Windows10專業(yè)版64位操作系統(tǒng)，處理器為Intel（R）Core（TM）i5-7200U CPU@2.50 GHz，系統(tǒng)內(nèi)存8 GB，虛擬機(jī)為VMware Workstation 15 Pro下的Ubuntu18.04，系統(tǒng)內(nèi)存2 GB?？紤]到邊緣代理的資源限制，實(shí)驗(yàn)將單個(gè)邊緣代理管理的終端設(shè)備數(shù)目設(shè)置為212個(gè)，將非平衡樹中葉子節(jié)點(diǎn)數(shù)目n固定為214個(gè)，分別選取待驗(yàn)證節(jié)點(diǎn)集合S數(shù)目為｛1，2，4，8，16，32，48，64，80，96，112，128｝。本文分別比較了多值認(rèn)證和單值認(rèn)證在進(jìn)行w生成和驗(yàn)證時(shí)消耗的時(shí)間，以及w的大小，w大小用其包含的節(jié)點(diǎn)哈希數(shù)目來表示。實(shí)驗(yàn)對(duì)每組待驗(yàn)證集合測試了100次取平均值，得出的數(shù)據(jù)如圖7所示。從圖7中可以看出，多值認(rèn)證在w生成和驗(yàn)證時(shí)明顯優(yōu)于單值認(rèn)證，且隨著待驗(yàn)證節(jié)點(diǎn)數(shù)目的增加，多值認(rèn)證的優(yōu)勢越來越明顯，符合第4.2節(jié)中的分析。同時(shí)w包含的驗(yàn)證所需節(jié)點(diǎn)哈希數(shù)目也明顯優(yōu)于單值認(rèn)證。

圖7 單值認(rèn)證和多值認(rèn)證效率分析Fig.7 Efficiency analysis of single value authentication and multivalue authentication

綜上所述，采用多值認(rèn)證性能獲得很大的提升。另外，我們也注意到，當(dāng)待驗(yàn)證節(jié)點(diǎn)數(shù)目不斷增大時(shí)，多值認(rèn)證盡管優(yōu)于單值認(rèn)證，但其所耗時(shí)間的增長幅度也較大。所以實(shí)際應(yīng)用中，應(yīng)當(dāng)控制非平衡哈希樹中的葉子節(jié)點(diǎn)數(shù)目，不讓一個(gè)邊緣代理負(fù)載過多終端設(shè)備，以保證云端平臺(tái)在可接受的驗(yàn)證時(shí)間內(nèi)進(jìn)行批量認(rèn)證。

6 結(jié)語

本文針對(duì)電力物聯(lián)網(wǎng)設(shè)備特點(diǎn)，提出了一種設(shè)備持續(xù)高效批量可信認(rèn)證機(jī)制。該機(jī)制使用一棵非平衡哈希樹存儲(chǔ)設(shè)備各個(gè)歷史度量信息，當(dāng)樹達(dá)到存儲(chǔ)上限時(shí)，借助一個(gè)特殊的多鏈和哈希表快速找到待替換的樹節(jié)點(diǎn)。度量信息認(rèn)證時(shí)，采用一種更高效的稀疏哈希樹多值認(rèn)證的方法實(shí)現(xiàn)，提高了多路徑信息的生成效率。本文模擬了該機(jī)制并進(jìn)行了實(shí)驗(yàn)比較分析，實(shí)驗(yàn)表明，本方案采用的稀疏哈希樹多值認(rèn)證方法可以使性能得到很大的提升。