[發明專利]一種適用于嵌入式處理器的數據完整性驗證方法

有效

• 申請號: 201010191552.7
• 申請日: 2010-06-04
• 公開（公告）號: CN101853190A
• 公開（公告）日: 2010-10-06
• 發明（設計）人: 劉政林;霍文捷;陳天山;郭超
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F11/00
• 分類號: G06F11/00
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 曹葆青

技術領域

本發明屬于數字集成電路領域，具體涉及一種適用于嵌入式處理器的數據完整性驗證方法，該方法的核心是多粒度存儲器散列計算，是一種具有高性能，少相關訪問，低初始化時間的數據完整性校驗方法。由于在設計時就考慮了性能與開銷等因素，該方法完全適用于嵌入式系統，也適用于計算機系統，能夠為其提供可靠的數據完整性驗證。

背景技術

數據完整性驗證是解決篡改攻擊的有效手段?；谶@一點，出現了散列函數，消息認證碼(MAC：Memory?Authentication?Code)和AREA(AddedRedundancy?Explicit?Authentication)等方法。

其中，散列函數(即Hash函數)是現代密碼技術與應用的一個重要基礎。在本文中，散列函數對于數據機密性保護和完整性校驗而言，是基礎性的密碼類運算。散列函數計算一個任意長度的輸入而得到一個定長的輸出，該輸出稱為原始輸入的散列值，或簡稱散列值。散列函數之所以在密碼學中扮演重要的角色，在于其具有如下的特性：

單向性：已知散列函數的輸出，欲求其輸入是困難的，即已知c＝Hash(m)，求m是困難的。m代表原始輸入數據，c為該輸出的散列值，Hash()表示散列函數。Hash(m)表示對原始數據m進行散列計算。

快速性：已知m，計算Hash(m)是容易的。Hash函數不屬于強計算密集型算法。

抗碰撞性：已知c1＝Hash(m1)，知道c1的值，而m1(原始輸入數據)的值不知。構造一個輸入數據m2使c1＝Hash(m2)是困難的(指計算不可行)。

雪崩性：若c＝Hash(m)，那么c的每一比特都與m的每一比特有關，并有高度敏感性即每改變的一比特，都將對c產生明顯影響(比如導致c中一半以上的位發生變化)。

接受的輸入數據m沒有長度限制，對輸入任何長度的數據都能夠生成固定長度的輸出。

有統計計算表明，如Hash(m)的長度為128位時，則任意兩個分別為m1和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，Manel?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＝Y1，Y2.......Yn，現在需要對這組數據進行完整性驗證證。為了驗證Yi(1≤i≤n)，一棵二叉樹被構造，該二叉樹被稱之為Merkle散列樹。如圖1所示，節點8，9，10，11，12，13，14屬于同一層，即葉節點層，也就是最低層。節點4，5，6，7屬于同一層，節點2，3屬于同一層。節點1，即根節點，單獨屬于一層。二叉樹中的每個節點從根節點開始以層遍歷的方式被編號，即同一層被編號完才對下一層進行編號，根節點為節點1，任何中間節點i的子節點為節點2i和節點2i+1。同時，節點i稱為節點2i和節點2i+1的父節點。同一層中具有同一個父節點的節點稱為彼此的兄弟節點，如節點8是節點9的兄弟節點，節點9也稱為節點8的兄弟節點。二叉樹中的每個節點都有一個散列函數值與之對應，葉節點的散列函數值是對需要認證的數據進行散列運算得到的，而中間節點的散列函數值由其子節點的散列函數值聯合進行散列運算得到。二叉樹構造過程如下：

首先計算葉節點的值。葉節點的值由Yi的值得到。如圖1所示，c8＝Hash(Y1)，c9＝Hash(Y2)等。