一種基于自更新哈希鏈的雙向認證簽名方案

摘 要:目前，哈希鏈技術已被廣泛地應用于信息安全領域中的實體認證和數據源認證，但是哈希鏈有限的長度限制了它的應用。為此，提出一種基于自更新哈希鏈的雙向認證簽名方案。新方案采用自更新哈希鏈技術進行認證簽名，避免了傳統公鑰算法的復雜運算，并且實現了哈希鏈在認證過程中自動平滑更新，達到無限使用的目的，從而顯著提高了執行速度。同時，結合雙向認證機制，能夠有效地抵抗重放攻擊和中間人攻擊，大大增強了新方案的安全性。

關鍵詞:數字簽名; 哈希鏈; 自更新; 雙向認證

中圖分類號:TP309.7 文獻標識碼:A

文章編號:1004-373X(2010)09-0087-04

Two-way Authentication Signature Scheme Based on Self-updating Hash Chains

WENG Li-ping， SHI Rong-hua， WANG Guo-cai

(Central South University， Changsha 410075， China)

Abstract: Hash chains are widely used for entity authentication or data-origin authentication in the field of information safety. However， finite length of a Hash chain limits its implementation. A two-way authentication signature scheme based on self-updating Hash chains is proposed. To avoid the computing complexity of the traditional public key algorithm， the scheme adopts Hash function to perform the authentication signature and significantly improves the speed of execution. The scheme achieves the automatic and smooth self-updating of Hash chain during the authentication process， and realizes the purpose of infinite utilization. In combination with the two-way authentication mechanism， the scheme can effectively resist the attack of replay and go-between， and enhance the security of the scheme.

Keywords: digital signature; Hash chain; self-updating; two-way authentication

0 引 言

數字簽名[1-2]是密碼學中的重要問題之一，它是對傳統文件手寫簽名的模擬，是提供認證性、完整性和不可否認性的重要技術。目前用于數字簽名的加密算法[3-4]主要有對稱加密算法(如DES)、非對稱加密算法(如RSA，DSA)和哈希函數(如MD5，SHA-1)三類。其中，非對稱加密算法的保密性較好，消除了對稱加密算法中用戶交換密鑰的需要，但加密和解密的算法復雜，花費時間長，速度慢。哈希函數能使非對稱簽名算法得到相對較短的輸入，并且能夠在驗證數字簽名的同時，驗證簽名消息或文件的完整性，大大提高數字簽名的效率和安全性。

目前，哈希鏈技術[5]已被廣泛應用于信息安全領域中的實體認證和數據源認證。哈希鏈具有單向可認證性，公開其鏈尾，依次逆序出示鏈節點充當驗證材料，這些節點可以被鏈尾所驗證。在實際應用中，傳統哈希鏈有長度限制，哈希鏈過長則效率低，并且由于攻擊窗口更大，其安全性也隨之降低。另一方面，如果鏈的長度過短，則需要經常更新，需要產生一條新鏈，并重新簽發或安全傳遞鏈尾，更新操作繁瑣。

針對這一問題，采用張浩軍于2006年提出的自更新哈希鏈機制[6](Self-Updating Hash Chains，SUHC)，結合雙向認證[7-8]，提出一種基于自更新哈希鏈的雙向認證簽名方案，并對新方案的效率和安全性進行了分析。

1 預備知識

1.1 基本定義

定義1 密碼學安全哈希函數[9]。

稱一個函數h為密碼學安全哈希函數，其具有屬性:給定函數h及安全參數k，輸入為任意長度二進制串，輸出為k位二進制串，記為h:{0，1}*|→{0，1}k。

(1) 給定x，計算h(x)容易;但給定h(x)，求x計算上不可行;

(2) 對于任意x，找到一個y，且y≠x，使得h(x)=h(y)，計算上不可行;同時發現一對(x，y)，且x≠y，使得h(x)=h(y)，計算上也不可行。

定義2 哈希鏈[5]。

按定義1選擇一個密碼學安全哈希函數h，選擇一個秘密種子s，迭代h共N次，生成一個哈希鏈，鏈尾hN(s)記為w，即:

w=hN(s)=h(hN-1(s))=h(h(h…hN(s)))

(1)

定義3 核心斷言[10]。

一個核心斷言是一個函數f:{0，1}*|→{0，1}*的一個布爾斷言B:{0，1}*|→{0，1}，使其對任何概率多項時間算法A′、任意多項式p(#8226;)和所有足夠大的n有:

Pr[A′(f(Un))=B(Un)]≤12+1p(n)

(2)

式中:Un代表一個均勻分布在{0，1}n上的隨機變量。

1.2 自更新哈希鏈(SUHC)機制

張浩軍等人提出的SUHC機制是一種“肩扛式”更新機制，無需額外協議或過程，在哈希鏈使用過程中攜帶更新鏈的驗證錨信息。當舊的哈希鏈消耗完，新的哈希鏈開始工作，從而達到哈希鏈無限使用的目的。具體包括初始化、示證和驗證三個過程。

1.2.1 初始化

示證者和驗證者協商一個安全哈希函數h，其安全參數為k。哈希函數h輸出k比特字符串。選擇一個布爾斷言函數B:{0，1}*|→{0，1}為h的硬核，初始化i=1。示證者做以下步驟:

(1) 從空間{0，1}k中隨機選擇一個安全種子s(假設s的長度為k比特)，按照定義2生成一個哈希鏈，鏈尾為w=hk(s)。

(2) 選擇另一個安全種子s′∈{0，1}k，構造下一個哈希鏈，其鏈尾為w′=hk(s′)，本地安全存儲s′和w′。

(3) 比特位承諾。選擇一個隨機數SK1，使得B(SK1)=w′[i]，計算PK1=h(SK1)，安全存儲SK1。

(4) 計算g1=h(k-1)(s)，ζ0=h(g1，PK1)，存儲g1。

(5) 安全分發(w，ζ0)。

1.2.2 示證

示證者產生并釋放用于認證的證據。第i次示證者做以下步驟:

(1) 計算gi+1=h(k-i-1)(s);

計算或恢復值gi=h(k-i)(s)=h(gi+1)。

(2) 計算下一個比特位承諾。選擇一個隨機數SKi+1，使得B(SKi+1)=w′[i+1]。

計算PKi+1=h(SKi+1)，安全存儲SKi+1。

(3) 計算消息完整性驗證ζi=h(gi+1，PKi+1)。

(4) 構造并釋放認證幀(gi，PKi，ζi，SKi)。

1.2.3 驗證

驗證者從示證者處接收到認證幀(gi，PKi，ζi，SKi)后做:

(1) 計算并檢查h(gi)=gi-1是否成立，其中:

gi-1是在上一次示證會話中發送并被記錄下來的鏈節點值。

(2) 驗證消息完整性，計算h(gi，PKi)并檢查是否等于ζi-1。

(3) 獲得比特承諾位，如果PKi=h(SKi)成立，那么簽名有效，計算并記錄比特位值B(SKi);否則報錯。

(4) 如果通過所有有效性驗證，驗證者成功驗證了示證者。

經過k次成功示證-驗證后，哈希鏈被消耗完，同時驗證者剛好獲得下一個哈希鏈k比特的鏈尾值w′。示證者將w替換為w′，s替換為s′，并產生下一個哈希鏈包括秘密種子s″和對應鏈尾w″，從而使哈希鏈可以連續無限地工作。

2 方案的實現

下面提出一種基于上述自更新哈希鏈機制的雙向認證簽名方案。方案由初始化、身份認證和簽名驗證三個階段組成。假設用戶A和用戶B需要進行信息交互，且用戶A要發送簽名的消息為M。

2.1 初始化

用戶A和用戶B協商一個安全哈希函數h，其安全參數為k(哈希函數h輸出k比特字符串)。選擇一個斷言函數B:{0，1}*|→{0，1}為h的硬核。

用戶A和用戶B分別根據1.2.1節步驟進行初始化，各自產生兩條哈希鏈。用戶A將(wA，ζA0)安全地傳遞給用戶B，同時用戶B將(wB，ζB0)安全地傳遞給用戶A。

令IDA為用戶A的惟一身份標識，IDB為用戶B的惟一身份標識。

2.2 身份認證

方案利用單向哈希鏈進行雙向身份認證，這里以第i次認證為例，過程如下:

(1) 用戶A首先發送下列消息給B:

messageA1=(IDA，M，h(k-i)(sA)，PKAi，MACA1);其中，MACA1=h(IDA，M，h(k-i-1)(sA))。

(2) 用戶B收到這條消息后對A進行身份驗證。

B使用與A協商的安全哈希函數h計算h(h(k-i)(sA))，如果h(h(k-i)(sA))=h(k-i+1)(sA)，則根據式(1)可知，h(k-i)(sA)和h(k-i+1)(sA)是同一條哈希鏈上相鄰鏈節點值，可以確認為用戶A使用的單向哈希鏈，所以可以確認對方為A用戶。其中，h(k-i+1)(sA)指上一次認證中用戶A發送并被用戶B記錄下來的鏈節點值。

用戶B通過對用戶A的身份驗證后，向A發送接收成功的回執:

messageB1=(IDB，h(k-i)(sB)，PKBi，MACB1)

其中，MACB1=h(IDB，h(k-i-1)(sB)，MACA1)。

(3) 用戶A收到回執后對B進行身份驗證。

A使用和B協商的哈希函數h計算h(h(k-i)(sB))，如果h(h(k-i)(sB))=h(k-i+1)(sB)，則認證通過，表明h(k-i)(sB)和h(k-i+1)(sB)是同一條哈希鏈上的相鄰鏈節點值，所以可以確認用戶B收到該消息。

2.3 簽名驗證

當用戶A和B都通過對方的身份認證后，用戶A向B發送簽名部分，用戶B驗證A的簽名并發送回執，用戶A驗證整個簽名過程是否有效。以第i次簽名驗證為例，過程如下:

(1) 用戶A向B發送簽名部分:

messageA2=(h(k-i-1)(sA)，SKAi，MACA2)

其中，MACA2=h(IDA，MACB1，i，h(k-i-1)(sA)，SKAi)，i表示進行的第i次簽名。

(2) 用戶B收到A的簽名消息后，利用收到的SKAi計算h(SKAi)。如果h(SKAi)=PKAi，則簽名有效，計算并記錄B(SKAi)。其中，PKAi是用戶B從messageA1中得到的。因為只有用戶A知道SKAi，所以可以驗證是用戶A的簽名。

同時用戶B利用收到的h(k-i-1)(sA)和從messageA1中得到的IDA和M用哈希函數h計算h(IDA，M，h(k-i-1)(sA))。

如果h(IDA，M，h(k-i-1)(sA))的值和第一次收到的MACA1相等，則說明通信道正常，A發送的消息正確，B發送接收成功的回執:

messageB2=(h(k-i-1)(sB)，SKBi，MACB2)

其中，MACB2=h(IDB，MACA2，i，h(k-i-1)(sB)，SKBi)，i表示進行的第i次簽名。

如果計算出的h(IDA，M，h(k-i-1)(sA))與第一次收到的MACA1不相等，則停止協議。

(3) 用戶A接收到B的回執后，利用收到的SKBi計算h(SKBi)。如果h(SKBi)=PKBi，則簽名有效，計算并記錄B(SKBi)。其中，PKBi是用戶A從messageB1中得到的。因為只有用戶B知道SKBi，所以可以確定用戶B收到簽名。

同時用戶A利用收到的h(k-i-1)(sB)和從messageB1中得到的IDB及MACA1用哈希函數h計算h(IDB，h(k-i-1)(sB)，MACA1)。

如果h(IDB，h(k-i-1)(sB)，MACA1)的值與第一次收到的MACB1相等，則完成了一次雙向認證的簽名過程。相反，如果未收到回執，或利用h(k-i-1)(sB)計算的MACB1與第一次收到的MACB1不相等，則請求仲裁者作廢簽名。

整個過程如圖1所示。

圖1 第i次認證簽名過程

經過k次認證簽名后，用戶A和B正好獲得對方的下一次(新)哈希鏈的k位鏈尾

w′B和

w′A。當舊的哈希鏈消耗完，新的哈希鏈開始工作。上述過程可以無限、持續地進行。

3 方案分析

3.1 效率分析

本文提出的簽名方案，只涉及哈希函數和核心斷言函數的運算，核心斷言函數可以配置計算速度較快的函數，意味著具有較高的效率。

方案中，一次簽名使用兩個哈希值，所以每次簽名需要的平均運算次數為(k+1)/2。假設IDA為8 B，使用SHA-1算法，則M和h(k-i-1)(sA)均為20 B，則計算MACA1需要一個哈希運算時間。同理，計算MACA2需要計算一個IDA(8 B)，一個計數值i(設為5 B)和三個哈希值(60 B)，即總共為73 B，需要兩個哈希運算時間。此外，用戶A還需要進行兩次哈希運算對B進行驗證和一次斷言函數運算，進行新鏈的比特位承諾。

同理，對用戶B也一樣，總共需要4次哈希運算和1次核心斷言函數運算。

此外，哈希鏈在認證的過程中，得到平滑更新，無需額外過程，更新所需的計算和存儲量被均勻地分攤到哈希鏈的工作過程中，消耗很小。

因此，新方案的最大優勢在于只需進行哈希運算，無需傳統對稱、公鑰密碼運算，驗證效率高，特別適合應用到對計算速度要求高，設備處理能力和電池容量有限的移動環境中。

3.2 安全性分析

本文提出的簽名方案，只涉及哈希函數和核心斷言函數，其安全性完全依賴所配置的哈希函數和核心斷言函數。當哈希函數的構造或配置為一個強單向、抗碰撞函數時，即在發現翻轉哈希函數或尋找哈希函數碰撞計算上是不可行的。如果強單向函數存在，則核心斷言存在[10]。哈希函數用于實現認證的同時也起到了消息完整性保護的作用。核心斷言函數用于實現位承諾，保證新哈希鏈鏈尾比特位的安全傳遞。因此，方案的安全性得到了保證，此外方案還具有以下安全性:

(1) 抗重放攻擊。若用戶A發送了消息messageA1，但未到達用戶B(可能敵手干擾)。敵手可能觀察到了此消息，但敵手仍然無法提供消息messageA2，因為敵手不知道h(k-i-1)(sA)和SKAi。敵手只能根據已知h(k-i)(sA)和PKAi，通過翻轉哈希函數或發現哈希碰撞來偽造h(k-i-1)(sA)和SKAi。而方案配置的哈希函數是一個強單向、抗碰撞的函數，即在發現翻轉哈希函數或尋找哈希函數碰撞計算上是不可行的。

(2) 抗中間人攻擊。用戶A和B的消息都是以明文形式傳輸的，容易遭受中間人攻擊。本文采用雙向身份認證機制抵抗中間人攻擊，不僅需要用戶B認證用戶A的合法性，同時也需要用戶A認證用戶B的合法性。具體使用哈希鏈技術，敵手想要進行攻擊就要打破哈希函數的強單向性和抗碰撞性，而這個在計算上是不可行的。

4 結 語

詳細描述了一個基于自更新哈希鏈的雙向認證簽名方案，并對該方案進行了效率和安全性分析。新方案使用自更新哈希鏈機制，使哈希鏈達到無限使用的目的，從而代替公鑰算法，避免了公鑰算法的復雜運算，提高簽名認證的效率，適用于設備處理能力和電池容量有限的移動環境。此外，新方案結合雙向認證，能夠有效抵抗重放攻擊和中間人攻擊，大大增強了方案的安全性。

參考文獻

[1]ATREYA Mohun.數字簽名[M].賀軍，譯.北京:清華大學出版社，2003.

[2]RIVEST R J， SHAMIR A L. A method for obtaining digi-tal signature and public-key cryptosystem[J]. Communications of the ACM， 1978， 21(2):120-126.

[3]徐茂智，游林.信息安全與密碼學[M].北京:清華大學出版社，2007.

[4][美]梅尼斯.應用密碼學手冊[M].胡磊，王鵬，譯.北京:電子工業出版社，2005.

[5]LAMPORT L. Password authentication with insecure co-mmunication[J]. Communications of the ACM， 1981， 24(11): 770-772.

[6]ZHANG Hao-jun， ZHU Yue-fei. Self-updating Hash chains and their implementations[J]. IEEE Lecture Notes in Computer Science， 2006， 42(55): 387-397.

[7]施榮華.一種基于Harn數字簽名的雙向認證訪問控制方案[J].計算機學報，2001，24(4):400-404.

[8]蔡滿春，趙海洋，郭代飛.移動環境下的一種基于雙向認證的哈希鏈簽名方案[J].計算機應用研究，2008，25(5):1532-1533.

[9]施榮華.一種基于單向函數的雙重認證存取控制方案[J].電子科學學刊，1997，19(2):278-281.

[10]ODED G. Foundations of cryptography: basic tools[M]. Cambridge: Cambridge University Press， 2001.