一種適用於嵌入式處理器的數據完整性驗證方法

2023-07-16 08:15:01

專利名稱：一種適用於嵌入式處理器的數據完整性驗證方法
技術領域：
本發明屬於數字集成電路領域，具體涉及一種適用於嵌入式處理器的數據完整性 驗證方法，該方法的核心是多粒度存儲器散列計算，是一種具有高性能，少相關訪問，低初 始化時間的數據完整性校驗方法。由於在設計時就考慮了性能與開銷等因素，該方法完全 適用於嵌入式系統，也適用於計算機系統，能夠為其提供可靠的數據完整性驗證。
背景技術：
數據完整性驗證是解決篡改攻擊的有效手段。基於這一點，出現了散列函數， 消息認證碼(MAC :Memory Authentication Code)禾口 AREA(AddedRedundancy Explicit Authentication)等方法。其中，散列函數(即Hash函數)是現代密碼技術與應用的一個重要基礎。在本文 中，散列函數對於數據機密性保護和完整性校驗而言，是基礎性的密碼類運算。散列函數計 算一個任意長度的輸入而得到一個定長的輸出，該輸出稱為原始輸入的散列值，或簡稱散 列值。散列函數之所以在密碼學中扮演重要的角色，在於其具有如下的特性單向性已知散列函數的輸出，欲求其輸入是困難的，即已知c = Hash(m)，求m是 困難的。m代表原始輸入數據，c為該輸出的散列值，Hash 表示散列函數。Hash(m)表示 對原始數據m進行散列計算。快速性已知m，計算Hash (m)是容易的。Hash函數不屬於強計算密集型算法。抗碰撞性已知cl = Hash (ml)，知道cl的值，而ml (原始輸入數據)的值不知。 構造一個輸入數據m2使cl = Hash(m2)是困難的(指計算不可行)。雪崩性若c = Hash (m)，那麼c的每一比特都與m的每一比特有關，並有高度敏 感性即每改變的一比特，都將對c產生明顯影響(比如導致c中一半以上的位發生變化)。接受的輸入數據m沒有長度限制，對輸入任何長度的數據都能夠生成固定長度的 輸出。有統計計算表明，如Hash (m)的長度為128位時，則任意兩個分別為ml和m2的輸 入數據具有完全相同Hash (m)的概率為10_24即接近於零的重複概率。若Hash (m)為512位 乃至1024位，則更是不大可能重複了。因此，散列函數可以用於數據完整性驗證、數字籤名、生成隨機數等多種目的。目 前，常用的散列函數主要是MD5，SHA-1, SHA-2等。現存的數據完整性驗證方法依賴於散列樹結構，如Merkle樹， PAT (Parallelizable Authentication Tree)禾口 TEC-Tree (Tamper-Evident CounterTree)。其中，PAT與TEC-tree是基於Merkle樹的兩種改進型。Merkle 散列樹驗證思想在文獻(Jose L. Munoz, Jordi Forne, OscarEsparza, Man el Rey. Efficient Certificate Revocation System Implementation:Huffman Merkle Hash Tree. Trust, Privacy and Security in Digital Business. Berlin Springer-Verlag, 2005, 3592 :119-127)中被詳細闡述，給定一組數據 Y = Yl，Y2.......Yn，現在需要對這組數據進行完整性驗證證。為了驗證Yi (l^i^ n)，一棵二叉
樹被構造，該二叉樹被稱之為Merkle散列樹。如圖1所示，節點8,9,10，11，12，13，14屬於 同一層，即葉節點層，也就是最低層。節點4，5，6，7屬於同一層，節點2，3屬於同一層。節 點1，即根節點，單獨屬於一層。二叉樹中的每個節點從根節點開始以層遍歷的方式被編號， 即同一層被編號完才對下一層進行編號，根節點為節點1，任何中間節點i的子節點為節點 2i和節點2i+l。同時，節點i稱為節點2i和節點2i+l的父節點。同一層中具有同一個父 節點的節點稱為彼此的兄弟節點，如節點8是節點9的兄弟節點，節點9也稱為節點8的兄 弟節點。二叉樹中的每個節點都有一個散列函數值與之對應，葉節點的散列函數值是對需 要認證的數據進行散列運算得到的，而中間節點的散列函數值由其子節點的散列函數值聯 合進行散列運算得到。二叉樹構造過程如下首先計算葉節點的值。葉節點的值由Yi的值得到。如圖1所示，c8 = Hash (Y1)， c9 = Hash (Y2)等。然後計算中間節點及根節點i的值由節點2i和節點2i+l的值得到。如，c4 = Hash(c8,c9), (c8,c9)表示把數據c9放在c8的後面，兩者連接成一個數據。c5 = Hash(c 10，c 11)，c 1 = Hash(c2, c3)。由二叉樹節點對應的值的構造過程可知，節點1的值與整棵二叉樹的每個葉子節 點的值都是相關聯的。中間節點i的值與以節點i為根的子樹的所有葉節點對應的值有關。 如節點2的值與節點4，5，8，9，10，11對應的值有關。這種方法能夠提高處理器的安全性。但是這種方法產生的散列樹層數、節點較 多，缺失代價大，驗證時資源開銷也較大，因此不能夠滿足嵌入式系統應用的要求。PAT與 TEC-tree是對Merkle樹的節點值進行了改進，但是沒有對Merkle樹本身進行改進，因此兩 者產生的節點也較多，同樣有缺失代價、驗證時資源開銷大的缺點。

發明內容
本發明的目的在於提供一種適用於嵌入式處理器的數據完整性驗證方法，該方法 與現有技術相比具有更小的硬體開銷，卻能達到更優的性能，能夠真正應用於對設計要求 較高的嵌入式系統中。本發明提供的一種適用於嵌入式處理器的數據完整性驗證方法，包括初始化操作 過程中的數據完整性驗證及讀、寫操作過程中的數據完整性驗證；其特徵在於，初始化操作過程中的數據完整性驗證包括下述步驟(A1)計算待建立的多粒度散列樹的層數；(A2)對物理內存中數據塊進行散列計算，按照步驟(A1)中計算的層數建立多粒 度散列樹，並將多粒度散列樹存儲在散列緩存中；(A3)從可信存儲區讀取安全信息，並與多粒度散列樹的根節點的值進行比較，如 果兩者相等，說明內存中的數據未遭篡改，則將驗證標誌位置為1 ；兩者不等，則置標誌位 為0，表示內存中的數據已遭篡改；讀操作過程的數據完整性驗證過程為(B1)計算物理內存中兩個相鄰數據塊的散列值；(B2)在散列緩存中查找是否有與步驟(B1)所述的兩個相鄰數據塊的相應葉節點的值，如果有，進入步驟(B3)，否則，該相應葉節點缺失，稱之為當前缺失節點，用步驟(B1) 中計算出的散列值代替當前缺失節點值，然後轉入步驟(B4)；(B3)讀散列緩存中相應葉節點的值，並與步驟(B1)中計算出的散列值進行比較， 若兩值相等，說明數據塊是完整的，則將驗證標誌位置為1，否則，將驗證標誌位置為0，表 示數據塊不是完整的；最後均進入步驟(B9)；(B4)對當前缺失節點按照下面過程進行處理(B41)在散列緩存中查找當前缺失節點的兄弟節點，如果兄弟節點的值缺失，稱該 兄弟節點為當前缺失節點，進入步驟(B42)，否則，進入步驟(B5)；(B42)處理步驟如下(B421)判斷當前缺失節點是否為葉節點，如果是，則由缺失節點對應的物理內存 中數據塊計算出散列值，用計算出的散列值代替當前缺失節點值，然後進入步驟(B422)； 如果不是，直接轉入步驟(B422)；(B422)計算當前缺失節點的子節點的地址；(B423)在散列緩存中查找是否有當前缺失節點的子節點的值，若所有子節點都 不缺失，則由子節點的值計算出散列值，並用該散列值代替缺失節點的值，然後進入步驟 (B5)；若有子節點缺失，則稱缺失的子節點為當前缺失節點，然後轉入步驟(B42)；(B5)判斷是否所有的兄弟節點都被查找到了，如果是，則進入步驟(B6)，否則跳 到步驟(B41)；(B6)讀出步驟(B4)中當前缺失節點的兄弟節點的散列值並計算父節點的散列 值；(B7)在散列緩存中查找是否有父節點的值；如果父節點的值缺失，則稱該父節點 為當前缺失節點，轉入步驟(B8)；否則，讀出父節點的值，並跳到(B9)；(B8)判斷步驟(B6)中的當前缺失節點是否為根節點；如果不是，用步驟(B6)中 計算出的散列值代替當前缺失節點值，然後轉入步驟(B4)；如果是，則從可信存儲區中讀 出根節點的值，用之代替父節點的值，然後進入步驟(B9)；(B9)比較讀出的父節點值和步驟(B6)中計算出的父節點值；若兩值相等，說明 數據塊是完整的，則將驗證標誌位置為1 ；否則，將驗證標誌位置為0，表示數據塊不是完整 的；(B10)讀操作驗證過程結束；寫操作過程的數據完整性驗證過程為(C1)計算待改寫數據塊對應的散列節點的地址，該散列節點稱之為當前缺失節點。(C2)在散列緩存中查找是否有當前缺失節點的值；如果有，則轉入步驟(C3)；如 果沒有，則計算待改寫的數據塊的散列值，並用該散列值代替當前節點值，然後進入步驟 (C3)；(C3)查找該當前缺失節點兄弟節點；如果兄弟節點缺失，則稱缺失的兄弟節點為 當前缺失節點，進入步驟(C4)；如果不缺失，則進入步驟(C5)；(C4)處理步驟如下(C41)判斷當前缺失節點是否為葉節點，如果不是，轉入步驟(C42)；如果是，則由缺失節點對應的物理內存中數據塊計算出散列值，並用計算出的散列值代替當前缺失節點 值，然後進入步驟(C5)；(C42)計算當前缺失節點的子節點的地址；(C43)在散列緩存中查找是否有當前缺失節點的子節點的值，若所有子節點都 不缺失，則由子節點的值計算出散列值，並用該散列值代替缺失節點的值，然後進入步驟 (C5)；若有子節點缺失，則稱缺失的子節點為當前缺失節點，然後轉入步驟(C4)；(C5)判斷是否步驟(C3)所有的兄弟節點都被查找到了，如果是，則進入步驟 (C6)，否則跳到步驟(C3)；(C6)讀步驟(C3)中第一個當前缺失節點及其兄弟節點的散列值並計算它們的父 節點的散列值；(C7)在散列緩存中查找是否有父節點的值；如果父節點的值缺失，則稱該節點為 當前缺失節點，轉入步驟(C8)；否則，讀出父節點的值，並跳到(C9)；(C8)判斷步驟(C7)中的當前缺失節點是否為根節點；如果不是，用步驟(C6)中 計算出的散列值代替當前缺失節點的值，然後轉入步驟(C3)；如果是，則從可信存儲區中 讀出根節點的值，用之代替父節點的值，然後進入步驟(C9)；(C9)比較讀出的父節點值和步驟(C6)中計算出的父節點值；若兩值相等，說明數 據塊是完整的，則將驗證標誌位置為1，然後轉入步驟(C10)；否則，將驗證標誌位置為0，表 示數據塊不是完整的，跳到(C11)；(C10)更新當前節點和它的父節點值；(C11)寫操作驗證過程結束。本發明提供了一種適用於嵌入式處理器的數據完整性驗證方法，它包括多粒度散 列計算和散列訪問控制，其中散列訪問控制包括地址的轉換，散列節點的訪問。多粒度散列 計算用於產生多粒度Merkle樹，該樹緩存在散列cache中，同時在樹的節點缺失時，此算法 負責計算內存中數據塊的散列值。地址轉換為每個節點提供了一個唯一對應的地址。散列 節點訪問主要負責訪問各個散列樹的節點，特別是在讀缺失和寫操作時採取不同的對策。 讀缺失時，首先訪問子節點，計算出當前節點，再遞歸地追蹤父節點。在執行寫操作時，先驗 證當前節點的安全性。再更新當前節點和父節點。由於採用多粒度散列算法，本發明產生 的散列樹節點少，層數少，因而減少了存儲空間，硬體面積開銷和初始化時間，提高了性能。本發明針對自然Merkle樹的缺點，採用了多粒度算法，即對不同層的節點採用不 同的粒度(用來進行散列運算的數據塊的數目稱為粒度)進行散列計算。對於Merkle樹 來說，低層節點特別是葉節點，訪問得最頻繁。所以，我們對這些節點使用較少數目的數據 塊(即較小的粒度)進行散列計算，我們稱之為細粒度散列算法。與此同時，對於擁有大缺 失代價的高層節點，我們使用較多數據塊來進行散列計算，我們稱之為粗粒度散列算法。細 粒度散列算法通過使散列開銷最小化來提高存儲器校驗的性能，而粗粒度散列算法通過一 次對多個節點進行散列計算來節省存儲空間，增大了高層節點的命中率。


圖1為Merkle散列樹的示意圖；圖2為本發明提供的數據完整性校驗方法的結構模型示意圖3為本發明提供的方法的內部結構及數據流向示意圖；圖4為本發明的多粒度Merkle樹結構示意圖，其中，(a)為自然Merkle樹，(b)為 多粒度Merkle樹；圖5為本發明的節點地址轉換算法示意圖；圖6為本發明的粒度索引示意圖；圖7為本發明的初始化操作流程；圖8為本發明的多粒度Merkle節點計算示意圖；圖9為本發明的讀操作驗證流程；圖10為本發明的寫操作驗證流程；
具體實施例方式下面結合附圖和實例對本發明作進一步詳細的說明。圖2為本發明提供的數據完整性校驗方法在處理器整體架構中位置的示意圖，即 實現此方法需要在現有的處理器中額外增加一個完整性驗證模塊。圖2中非可信存儲區是 指處理器晶片外部的存儲器，可信存儲區是指處理器晶片內部的存儲器。如圖3所示，完整性驗證模塊中引入了一個高速緩衝存儲器，用於存儲散列樹的 節點值，下稱散列緩存。此外，完整性驗證模塊還包括兩大部分，分別為多粒度散列計算模 塊和散列訪問控制模塊。多粒度散列計算模塊，是實現散列函數的電路模塊，主要功能是對 不同粒度的(即不同個數的)數據塊進行散列計算，得到一個具有固定位數的散列值。對 於寫操作(即把第二級高速緩衝存儲器中的數據寫入非可信存儲區)，在執行這一操作之 前，待寫的數據要先流入散列計算模塊，得到散列值，然後用此值更新散列cache中相應的 節點散列值。對於讀操作，非可信區的數據在讀入第二級高速緩衝存儲器之前，待寫的數據 先要流入散列計算模塊，計算出的散列值與從散列cache中取出的值進行比較，兩值相等 則非可信區的數據可以讀入第二級高速緩衝存儲器，不相等則說明數據已遭篡改，不可以 讀入第二級高速緩衝存儲器。圖4表示的是一個2元(2-ary)的多粒度散列樹和一個自然Merkle樹的對比。 第三層是多粒度Merkle樹的葉節點。它的粒度固定為2。第二層定義為多粒度Merkle樹 的基本層。它的粒度可以被配置為2，那麼這時候它就是2-ary的多粒度Merkle樹。多粒 度Merkle樹的粒度從這層開始變化。上一層的粒度由下層的粒度乘二得到。所以第1層 的散列粒度為4，第零層的粒度為8。採用這樣的方式，對於一個總層數為j的Merkle樹， 第i層的粒度為A」 A, = Abasi。X2j-H (Abasic為基本層的粒度)。多粒度Merkle樹的上層節 點擁有粗散列粒度，這使得一個上層節點能夠驗證更多的下層節點。這不僅節省了散列樹 的存儲空間，還減少了加載程序時的初始化延遲。如圖5所示，對於葉層的節點，層數為i，它的地址是將相應的存儲器地址右移 logA位隊是第i層的粒度)，最左端位空位用0補足。同樣地，將節點地址右移 Io^Ah位能夠得到它在第i_l層的父節點地址。通過這種移位操作，散列訪問控制模塊能 夠快速地計算出從i層到0層(散列樹的最高層)的散列節點的地址。每個散列樹的節點 對應唯——個地址。如圖6所示，該結構使得散列cache可以通過索引一個節點的層數，快速取得該節點的粒度。此外，為了利用cache結構，被訪問節點的地址映射成三個欄位標籤，cache地 址，字節偏移量。這簡化了訪問節點的搜索。本發明方法包括散列樹初始化操作過程中的數據完整性驗證及讀寫操作過程中 的數據完整性驗證。下面分別予以具體說明。為了使強制缺失最小化，必須在驗證數據完整性之前初始化Merkle樹。由於數據 是從片外存儲器上載入的，所以多粒度散列計算模塊計算每兩個數據塊的散列值，這些散 列值稱為葉節點，以這些葉節點值按照不同的粒度算出上層節點的散列值，重複計算上層 節點的散列值，最終算出根節點的散列值，至此，構造散列樹的工作就結束了。散列計算的 最終結果被稱作根節點，需要與安全信息進行比較，該安全信息在初始化操作前已經存入 可信區。如果根節點與安全信息一致，說明被訪問的數據是安全的，沒有被篡改。否則，就 意味著非可信存儲區遭到篡改攻擊，數據的完整性被破壞。初始化完成後，部分散列樹節點 存儲在散列緩存中，供運行期間的讀寫非可信存儲區驗證使用。如圖7所示，初始化操作過程中的數據完整性驗證包括下述步驟(A1)計算多粒度散列樹的層數。設i表示層的序號，j表示總層數，i的取值範圍為0至j_l，其中，第0層表示 根節點層，Abasic表示預先設定的基本層的粒度(通常取值為2和4)，根據粒度關係Ai =
以及待散列計算的數據塊的塊數，計算出多粒度散列樹的層數j。如圖4，有 128塊數據，葉節點層和基本層的粒度為2，往上的層的粒度分別為4、8、16，32等等，用128 分別除以這些粒度，結果為1時即結束，此時所作的除法的次數就是層數。對於128塊數 據，128 + 2 + 2 + 4 + 8 = 1，即總層數為4。對於129塊數據，129 + 2 + 2 + 4 + 8 = 1餘1，則 總層數為5，即對於無法整除的數，總層數為所作除法次數加1。(A2)對物理內存(即圖2中的非可信存儲區)中數據塊進行散列計算，建立散列 樹，並將散列樹存儲在散列緩存中。如圖8所示，假設物理內存中的數據為Y1，Y2，......Y16，節點6，7，8，9......,13
為葉節點，具體計算步驟如下(A21)以2為粒度，計算葉節點的散列值。如圖8所示，葉節點6的值為c6 = Hash(Yl,Y2),cn表示節點n的散列值，n為一 個大於1的整數，則c6表示節點6的散列值。HashO表示採用一種散列函數對括號內的數 進行散列計算，在本方法中，任取現有的一種散列函數即可。(P，q)表示把數P與數q首尾 相連成一個數，若 P = 10001，q = 0011，則(p，q) = 100010011，則 c6 = Hash (100010011)。 同樣，c7 = Hash (Y3, Y4)，c8 = Hash (Y5, Y6)，c9 = Hash (Y7, Y8)，以此類推。每計算出一 個散列值，就存儲在散列緩存中，以供計算上一層節點的散列值使用，在步驟(A22)，(A23) 中，這點同樣適用；(A22)同樣以2為粒度(也可以取4或8為粒度，這可以人為地確定，但根據作者 的研究發現，取2或4的時候性能會更好)，計算基本層節點的散列值；如圖8所示，計算基本層節點2，3，4，5的散列值，c2 = Hash(c6, c7), c3 = Hash(c8, c9)，c4 = Hash(cl0, ell)，c5 = Hash(c12, cl3)；(A23)從基本層開始，以下一層節點的粒度，乘2得出上一層節點的粒度，並以計 算出的粒度，計算上一層節點的散列值，重複這一操作，直至計算出最高層中根節點的散列值；如圖8所示，基本層的上一層為層0，則用基本層粒度乘以2得出層0的粒度為4， 因此，節點值 cl = Hash(c2，c3，c4，c5)。(c2，c3，c4，c5)表示把 c2，c3，c4，c5 四個數首 尾相連。在這一例子中，到這裡散列樹就已經建立完成了，節點1就是根節點。對於那些數 據塊多於16的，在這一步沒有到達最後一層，重複乘2算上一層粒度，計算散列值這一步 驟，直至到達最後一層；(A3)讀取安全信息，並與根節點進行比較。從處理器內的可信存儲區中讀出安全信息，並將之與上一步驟計算出的根節點散 列值cl進行比較。若兩者相等，說明內存中的數據未遭篡改，則將驗證標誌位置為1 ；若兩 者不等，則置標誌位為0，表示內存中的數據已遭篡改。如圖9所示，讀操作過程的數據完整性驗證過程包括下列步驟(B1)計算物理內存中兩個相鄰數據塊的散列值；散列值由多粒度散列計算模塊計算而得，散列值為c = Hash(Yi,Yi+1)。Yi，Yi+1表 示物理內存中兩個相鄰的數據塊。(B2)在散列緩存中查找是否有與步驟(B1)所述的兩個相鄰數據塊的相應葉節點 的值，如果有，進入步驟(B3)，否則，該相應葉節點缺失，稱之為當前缺失節點，用步驟(B1) 中計算出的散列值代替當前缺失節點值，然後轉入步驟(B4)；查找過程為設兩個相鄰數據塊中的任意一個數據塊的編號為s，該數據塊為Ys， 其地址為adds，則相應葉節點的地址Addk由adds右移log2Ni位得到，Ni是層i的粒度， 移位後，最左端的log2Ni位空位由0來補足，k為葉節點的編號，根據葉節點的地址Addk， 查找散列緩存相應葉節點的值。用步驟(B1)中計算出的散列值代替當前缺失節點值，是指將上一步驟計算出的c 寫入散列緩存的地址Addk中。(B3)讀散列緩存中相應葉節點的值，並與步驟(B1)中計算出的散列值進行比較， 若兩值相等，說明數據塊是完整的，則將驗證標誌位置為1，否則，將驗證標誌位置為0，表 示數據塊不是完整的；最後均進入步驟(B9)；(B4)對當前缺失節點按照下面過程進行處理(B41)查找當前缺失節點的兄弟節點，如果兄弟節點的值缺失，稱該兄弟節點為當 前缺失節點，進入步驟(B42)，否則，進入步驟(B5)；查找過程為設當前缺失節點的地址為adds，則當前缺失節點的基本地址Adds由 adds右移log2Ni位，然後再左移log2Ni位得到，Ni是當前缺失節點所在層i_l的上一層i 的粒度，移位後，最右端的log2Ni位空位由0來補足。Adds,Adds+l,……,Adds+(Ni-l)中 包括當前缺失節點地址，去掉該地址，剩餘的Ni-2個地址即為缺失節點的兄弟節點地址。 根據兄弟節點的地址，查找散列緩存中相應兄弟節點的值。(B42)處理步驟如下(B421)判斷當前缺失節點是否為葉節點，如果是，則由缺失節點對應的物理內存 中數據塊計算出散列值，用計算出的散列值代替當前缺失節點值，轉入步驟(B5)。如果不 是，轉入步驟(B422)；初始化過程中，已經計算出了總層數j，如果當前缺失節點所在的層數i等於j_l，則缺失節點是葉節點。否則，當前缺失節點不是葉節點。如果當前缺失節點為葉節點，且地址為add，則缺失節點對應的物理內存中數據塊 的基本地址為Addb，Addb由add左移lo&2位得到，最右端的lo&2位空位用0補足，Addb， Addb+1是缺失節點對應的物理內存中的兩個數據塊的地址。假設讀出地址Addb，Addb+1 中的數據為Yi，Yi+1，則計算出的散列值為c = Hash(t，Yi+1)，然後將c寫入散列緩存的地址 add 中。(B422)計算當前缺失節點的子節點的地址；
設缺失節點的地址為Add，則子節點的基本地址Addb由Add左移log2Ni位 (Ni是當前節點層的粒度)，移動後，最右端的log2Ni位空位用0補足。Add，Add+1， Add+2，......Add+(Ni-l)，就是所有子節點的地址；(B423)在散列緩存中查找是否有當前缺失節點的子節點的值，若所有子節點都 不缺失，則由子節點的值計算出散列值，並用該散列值代替缺失節點的值，然後進入步驟 (B5)。若有子節點缺失，則稱缺失的子節點為當前缺失節點，然後轉入步驟(B42)；按照步驟(B422)計算出的地址去散列緩存中查找相應的子節點散列值。如果 所有子節點都不缺失，則按照步驟(B422)計算出的子節點地址讀出所有子節點的散列 值，假設讀出的子節點散列值為，cl，c2, c3……，cNi，則由子節點的值計算出散列值c = Hash(cl, c2, c3……，cNi)，然後將計算出的散列值寫到散列緩存的地址Add中。(B5)判斷是否所有的兄弟節點都被查找過了，如果是，則進入步驟(B6)，否則跳 到步驟(B41)；設置一個計數器，每進入步驟(B41) —次，計數器加一，若計數器的結果counter 等於步驟(B41)中的Ni減一，則說明所有的兄弟節點都被查找過了。若不相等，則說明還 有兄弟節點未查找過。(B6)讀出步驟(B4)中當前缺失節點及其兄弟節點的散列值並計算父節點的散列 值；設讀出的當前缺失節點及其兄弟節點的散列值分別為cl，c2，c3，c4……，ci，則計 算父節點的散列值為:Hash(cl, c2, c3, c4……，ci)。(B7)在散列緩存中查找是否有父節點的值。如果父節點的值缺失，則稱該父節點 為當前缺失節點，轉入步驟(B8)；否則，讀出父節點的值，並跳到(B9)；查找過程設當前缺失節點的地址為Add，則父節點的地址Addf由Add右移lo&Ni 位(Ni是父節點所在層的粒度)得到，最左端log2Ni位用0補足。根據父節點的地址，查 找散列緩存父節點的值。(B8)判斷步驟(B7)中的當前缺失節點是否為根節點。如果不是，用步驟(B6)中 計算出的散列值代替當前缺失節點值，然後轉入步驟(B4)；如果是，則從可信存儲區中讀 出根節點的值，用之代替父節點的值；如果當前缺失節點所在的層數i等於0，則缺失節點是根節點。否則，當前缺失節 點不是根節點。(B9)比較讀出的父節點值和步驟(B6)中計算出的父節點值。若兩值相等，說明 數據塊是完整的，則將驗證標誌位置為1。否則，將驗證標誌位置為0，表示數據塊不是完整 的；
11
這裡的讀出的父節點值，可能是步驟(B7)中讀出的父節點值，也可能是步驟(B8) 中從可信存儲區中讀出的根節點值。(B10)讀操作驗證過程結束；如圖10所示，寫操作過程的數據完整性驗證過程包括下列步驟(C1)計算待改寫數據塊對應的散列節點(稱之為當前缺失節點)的地址；設待改寫數據塊的地址為adds，則當前缺失節點的地址Add由adds右移log2Ni 位得到，Ni是層i的粒度，移位後，最左端的log2Ni位空位由0來補足。(C2)在散列緩存中查找是否有當前缺失節點的值。如果有，則直接轉入步驟 (C3)；如果沒有，先計算待改寫的數據塊的散列值，再用該散列值代替當前節點值，然後進 入步驟(C3)；根據步驟(C1)計算出的當前缺失節點的地址Addk，查找散列緩存中當前缺失節 點的值。如果散列緩存中沒有當前缺失節點的值，則由步驟(C1)中數據塊地址adds右移 一位，再向左移一位，最右端一位用0補足，得到數據塊的基本地址addb，讀取物理內存地 址addb,addb+l中的值Yi，Yi+1計算散列值c = Hash Yi+1)，將c寫入散列緩存地址Addk 中。(C3)查找該當前缺失節點兄弟節點。如果兄弟節點缺失，則稱缺失的兄弟節點為 當前缺失節點，進入步驟(C4)；如果不缺失，則進入步驟(C5)；查找過程為設當前缺失節點的地址為adds，則當前缺失節點的基本地址Adds由 adds右移log2Ni位，然後再左移log2Ni位得到，Ni是當前缺失節點所在層i_l的上一層i 的粒度，移位後，最右端的log2Ni位空位由0來補足。Adds,Adds+l,……,Adds+(Ni-l)中 包括當前缺失節點地址，去掉該地址，剩餘的Ni-2個地址即為缺失節點的兄弟節點地址。 根據兄弟節點的地址，查找散列緩存相應兄弟節點的值。(C4)處理步驟如下(C41)判斷當前缺失節點是否為葉節點，如果不是，轉入步驟(C42)；如果是，則由 缺失節點對應的物理內存中數據塊計算出散列值，並用計算出的散列值代替當前缺失節點 值，然後進入步驟(C5)；初始化過程中，已經計算出了總層數j，如果當前缺失節點所在的層數i等於j_l， 則缺失節點是葉節點。否則，當前缺失節點不是葉節點。如果當前缺失節點為葉節點，且地址為add，則缺失節點對應的物理內存中數據塊 的基本地址為Addb，Addb由add左移lo&2位得到，最右端的lo&2位空位用0補足，Addb， Addb+1是缺失節點對應的物理內存中的兩個數據塊的地址。假設讀出地址Addb，Addb+1 中的數據為Yi，Yi+1，則計算出的散列值為c = Hash(t，Yi+1)，然後將c寫入散列緩存的地址 add 中。(C42)計算當前缺失節點的子節點的地址；設缺失節點的地址為Add，則子節點的基本地址Addb由Add左移log2Ni 位(Ni是當前節點層的粒度)，移動後，最的低位log2Ni用0補足。Add，Add+1， Add+2，......Add+(Ni-l)，就是所有子節點的地址；(C43)在散列緩存中查找是否有當前缺失節點的子節點的值，若所有子節點都不缺失，則由子節點的值計算出散列值，並用該散列值代替缺失節點的值。若有子節點缺失， 則稱缺失的子節點為當前缺失節點，然後轉入步驟(C4)；按照步驟(C42)計算出的地址去散列緩存中查找相應的子節點散列值。如果所有 子節點都不缺失，則按照步驟(C42)計算出的子節點地址讀出所有子節點的散列值，假設 讀出的子節點散列值為，cl，c2, c3……，cNi，則由子節點的值計算出散列值c = Hash(cl, c2,c3……，cNi)，然後將計算出的散列值寫到步驟(B422)中當前缺失節點的地址Add中。(C5)判斷是否步驟(C3)所有的兄弟節點都被查找到了，如果是，則進入步驟 (C6)，否則跳到步驟(C3)；設置一個計數器，每進入步驟(C3) —次，計數器加一，若計數器的結果counter， 等於步驟(C3)中的Ni減一，則說明所有的兄弟節點都被查找過了。若不相等，則說明還有 兄弟節點未被查找過。(C6)讀步驟(C3)中第一個當前缺失節點的及其兄弟節點的散列值並計算它們的 父節點的散列值；設讀出的當前缺失節點及其兄弟節點的值分別為cl，c2，c3，c4……，ci，則計算父 節點的散列值為:Hash(cl, c2，c3，c4……，ci)。(C7)在散列緩存中查找是否有父節點的值。如果父節點的值缺失，則稱該節點為 當前缺失節點，轉入步驟(C8)；否則，讀出父節點的值，並跳到(C9)；查找過程設當前缺失節點的地址為Add，則父節點的地址Addf由Add右移lo&Ni 位(Ni是父節點所在層的粒度)得到，最左端log2Ni位用0補足。根據父節點的地址，查 找散列緩存父節點的值。(C8)判斷步驟(C7)中的當前缺失節點是否為根節點。如果不是，用步驟(C6)中 計算出的散列值代替當前缺失節點的值，然後轉入步驟(C3)；如果是，則從可信存儲區中 讀出根節點的值，用之代替父節點的值；如果當前缺失節點所在的層數i等於0，則缺失節點是根節點。否則，當前缺失節 點不是根節點。(C9)比較讀出的父節點值和步驟(C6)中計算出的父節點值。若兩值相等，說明數 據塊是完整的，則將驗證標誌位置為1，然後轉入步驟(C10)。否則，將驗證標誌位置為0，表 示數據塊不是完整的，跳到(C11)；這裡的讀出的父節點值，可能是步驟(C7)中讀出的父節點值，也可能是步驟(C8) 中從可信存儲區中讀出的根節點值。(C10)更新當前節點和它的父節點值；更新當前節點，即是由即將寫入非可信存儲區中的數據計算出散列值，然後將該 散列值寫入步驟(C1)中計算出的地址中。更新父節點，即是由更新的當前節點及其兄弟節 點計算出他們的父節點的散列值，然後將新父節點散列值寫入散列緩存中。(C11)寫操作驗證過程結束；使用這種驗證算法，能夠有效的發現被篡改的數據並發現被破壞的程序。此外，用 來檢查根節點的關鍵安全信息存儲在片內存儲器中的。節點的散列值只有初始化或是散列 節點缺失時才被緩存和計算。所以，多粒度Merkle樹不需要額外的存儲空間來保存散列 值。這不僅減少了硬體開銷，還改善了嵌入式處理器的安全性。
此外，本方法使處理器能夠把散列計算的時間隱藏在內存的訪問過程中。這就有 效地減少了多粒度Merkle樹安全計算的性能開銷。對本發明採用Mibench進行性能測試，由實驗結果可以看到，本發明所提出的多 粒度Merkle樹相比自然Merkle樹具有性能上的優越性，更適用於嵌入式系統。本發明不應該局限於附圖所公開的內容。所以凡是不脫離本發明所公開的精神下 完成的等效或修改，都落入本發明保護的範圍。
權利要求
一種適用於嵌入式處理器的數據完整性驗證方法，包括初始化操作過程中的數據完整性驗證及讀、寫操作過程中的數據完整性驗證；其特徵在於，初始化操作過程中的數據完整性驗證包括下述步驟(A1)計算待建立的多粒度散列樹的層數；(A2)對物理內存中數據塊進行散列計算，按照步驟(A1)中計算的層數建立多粒度散列樹，並將多粒度散列樹存儲在散列緩存中；(A3)從可信存儲區讀取安全信息，並與多粒度散列樹的根節點的值進行比較，如果兩者相等，說明內存中的數據未遭篡改，則將驗證標誌位置為1；兩者不等，則置標誌位為0，表示內存中的數據已遭篡改；讀操作過程的數據完整性驗證過程為(B1)計算物理內存中兩個相鄰數據塊的散列值；(B2)在散列緩存中查找是否有與步驟(B1)所述的兩個相鄰數據塊的相應葉節點的值，如果有，進入步驟(B3)，否則，該相應葉節點缺失，稱之為當前缺失節點，用步驟(B1)中計算出的散列值代替當前缺失節點值，然後轉入步驟(B4)；(B3)讀散列緩存中相應葉節點的值，並與步驟(B1)中計算出的散列值進行比較，若兩值相等，說明數據塊是完整的，則將驗證標誌位置為1，否則，將驗證標誌位置為0，表示數據塊不是完整的；最後均進入步驟(B9)；(B4)對當前缺失節點按照下面過程進行處理(B41)在散列緩存中查找當前缺失節點的兄弟節點，如果兄弟節點的值缺失，稱該兄弟節點為當前缺失節點，進入步驟(B42)，否則，進入步驟(B5)；(B42)處理步驟如下(B421)判斷當前缺失節點是否為葉節點，如果是，則由缺失節點對應的物理內存中數據塊計算出散列值，用計算出的散列值代替當前缺失節點值，然後進入步驟(B422)；如果不是，直接轉入步驟(B422)；(B422)計算當前缺失節點的子節點的地址；(B423)在散列緩存中查找是否有當前缺失節點的子節點的值，若所有子節點都不缺失，則由子節點的值計算出散列值，並用該散列值代替缺失節點的值，然後進入步驟(B5)；若有子節點缺失，則稱缺失的子節點為當前缺失節點，然後轉入步驟(B42)；(B5)判斷是否所有的兄弟節點都被查找到了，如果是，則進入步驟(B6)，否則跳到步驟(B41)；(B6)讀出步驟(B4)中當前缺失節點的兄弟節點的散列值並計算父節點的散列值；(B7)在散列緩存中查找是否有父節點的值；如果父節點的值缺失，則稱該父節點為當前缺失節點，轉入步驟(B8)；否則，讀出父節點的值，並跳到(B9)；(B8)判斷步驟(B6)中的當前缺失節點是否為根節點；如果不是，用步驟(B6)中計算出的散列值代替當前缺失節點值，然後轉入步驟(B4)；如果是，則從可信存儲區中讀出根節點的值，用之代替父節點的值，然後進入步驟(B9)；(B9)比較讀出的父節點值和步驟(B6)中計算出的父節點值；若兩值相等，說明數據塊是完整的，則將驗證標誌位置為1；否則，將驗證標誌位置為0，表示數據塊不是完整的；(B10)讀操作驗證過程結束；寫操作過程的數據完整性驗證過程為(C1)計算待改寫數據塊對應的散列節點的地址，該散列節點稱之為當前缺失節點；(C2)在散列緩存中查找是否有當前缺失節點的值；如果有，則轉入步驟(C3)；如果沒有，則計算待改寫的數據塊的散列值，並用該散列值代替當前節點值，然後進入步驟(C3)；(C3)查找該當前缺失節點兄弟節點；如果兄弟節點缺失，則稱缺失的兄弟節點為當前缺失節點，進入步驟(C4)；如果不缺失，則進入步驟(C5)；(C4)處理步驟如下(C41)判斷當前缺失節點是否為葉節點，如果不是，轉入步驟(C42)；如果是，則由缺失節點對應的物理內存中數據塊計算出散列值，並用計算出的散列值代替當前缺失節點值，然後進入步驟(C5)；(C42)計算當前缺失節點的子節點的地址；(C43)在散列緩存中查找是否有當前缺失節點的子節點的值，若所有子節點都不缺失，則由子節點的值計算出散列值，並用該散列值代替缺失節點的值，然後進入步驟(C5)；若有子節點缺失，則稱缺失的子節點為當前缺失節點，然後轉入步驟(C4)；(C5)判斷是否步驟(C3)所有的兄弟節點都被查找到了，如果是，則進入步驟(C6)，否則跳到步驟(C3)；(C6)讀步驟(C3)中第一個當前缺失節點及其兄弟節點的散列值並計算它們的父節點的散列值；(C7)在散列緩存中查找是否有父節點的值；如果父節點的值缺失，則稱該節點為當前缺失節點，轉入步驟(C8)；否則，讀出父節點的值，並跳到(C9)；(C8)判斷步驟(C7)中的當前缺失節點是否為根節點；如果不是，用步驟(C6)中計算出的散列值代替當前缺失節點的值，然後轉入步驟(C3)；如果是，則從可信存儲區中讀出根節點的值，用之代替父節點的值，然後進入步驟(C9)；(C9)比較讀出的父節點值和步驟(C6)中計算出的父節點值；若兩值相等，說明數據塊是完整的，則將驗證標誌位置為1，然後轉入步驟(C10)；否則，將驗證標誌位置為0，表示數據塊不是完整的，跳到(C11)；(C10)更新當前節點和它的父節點值；(C11)寫操作驗證過程結束。
2.根據權利要求1所述的方法，其特徵在於，步驟(A2)中，建立多粒度散列樹的過程 為首先以2為粒度，計算葉節點的散列值，然後同樣以2為粒度，計算基本層節點的散列 值，從基本層開始，以下一層節點的粒度，乘2得出上一層節點的粒度，並以計算出的粒度， 計算上一層節點的散列值，重複這一操作，直至計算出根節點的值。
3.根據權利要求1所述的方法，其特徵在於，步驟(B2)中，查找過程為設二個相鄰數 據塊中的一個數據塊的編號為s，該數據塊為Ys，其地址為adds，則相應葉節點的地址Addk 由adds右移log2Ni位得到，Ni是層i的粒度，移位後，最左端的空位由0來補足，k為葉節 點的編號，根據葉節點的地址Addk，查找散列緩存相應葉節點的值。
全文摘要
本發明公開了一種適用於嵌入式處理器的數據完整性驗證方法，它包括多粒度散列計算方法，地址轉換方法以及散列節點訪問控制方法。多粒度散列計算方法用於產生多粒度Merkle樹，該樹緩存在散列cache中，同時在樹的節點缺失時，此算法負責計算內存中數據塊的散列值。地址轉換方法為每個節點提供了一個唯一對應的地址。散列節點訪問控制方法主要負責訪問各個散列樹的節點，特別是在讀缺失和寫操作時採取不同的對策。由於採用多粒度散列算法，本發明產生的散列樹節點少，層數少，因而減少了存儲空間，硬體面積開銷和初始化時間，提高了性能。
文檔編號G06F11/00GK101853190SQ20101019155
公開日2010年10月6日 申請日期2010年6月4日 優先權日2010年6月4日
發明者劉政林, 郭超, 陳天山, 霍文捷 申請人:華中科技大學