一種高效的無證書認(rèn)證密鑰交換協(xié)議*

曾潤智, 王立斌

華南師范大學(xué) 計算機學(xué)院, 廣州510631

1 引言

無證書公鑰密碼學(xué)(Certificateless Public Key Cryptography, CL-PKC) 是基于身份公鑰密碼學(xué)(Identity-based Public Key Cryptography, ID-PKC) 的一個變種, 最初由Al-Riyami 與Paterson 提出[1]以解決ID-PKC 的密鑰托管問題. 在傳統(tǒng)ID-PKC 中, 用戶身份信息(如電子郵箱) 可直接作為用戶公鑰, 因此無需證書與公鑰綁定, 使得ID-PKC 免去與證書相關(guān)的復(fù)雜操作; 而用私鑰鑰完全由可信第三方密鑰生成中心(Key Generation Center, KGC) 負(fù)責(zé)生成, 這導(dǎo)致密鑰托管問題. CL-PKC 通過增加用戶自主生成的本地私密信息來弱化對KGC 的依賴. 在CL-PKC 中, KGC 依然存在并持有系統(tǒng)主密鑰,其負(fù)責(zé)為用戶生成部分私鑰; 用戶在本地生成一個秘密值, 然后根據(jù)部分私鑰和秘密值組成長期私鑰并生成長期公鑰. CL-PKC 用戶在私鑰生成中有一定的自主性, 因此在一定程度上解決ID-PKC 的密鑰托管問題.

無證書認(rèn)證密鑰交換(Certificateless Authencated Key Exchange, CL-AKE) 是在無證書體制下的認(rèn)證密鑰交換, 其主要解決如何在無證書環(huán)境下雙方進行帶認(rèn)證密鑰協(xié)商的問題, 是重要的無證書密碼構(gòu)件之一. 由于CL-PKC 不存在證書, 惡意攻擊者可進行公鑰替換以偽裝合法用戶; 另外, CL-PKC 假設(shè)KGC 不完全可信, 其可能會使用系統(tǒng)主密鑰竊取用戶的某些私密信息. 因此相較于傳統(tǒng)的認(rèn)證密鑰交換協(xié)議, CL-AKE 協(xié)議設(shè)計需要考慮的攻擊更多, 協(xié)議的運算也更復(fù)雜. 本文重點關(guān)注高效、安全CL-AKE協(xié)議的設(shè)計.

1.1 相關(guān)工作

第一種CL-AKE 協(xié)議由Al-Riyami 等人提出[1], 該協(xié)議的安全性未在嚴(yán)格定義的安全模型下證明.為嚴(yán)格定義CL-AKE 協(xié)議的安全性, Swason 提出了e2CK 模型[2], 該模型基于eCK 模型[3]. Lippold等人增強了e2CK 模型[4], 并提出了第一種可證明安全的CL-AKE 協(xié)議. 以上協(xié)議都使用雙線性配對,使得協(xié)議不高效. Yang 等人[5]重新定義e2CK 模型, 使得該模型可更清晰地刻畫公鑰替換攻擊、前向安全等概念. 為了精簡描述CL-AKE 安全模型, 本文對文獻[5] 中的模型進行一定的修改, 并依然稱此模型為e2CK 模型.

無雙線性配對CL-AKE 協(xié)議的一種設(shè)計思路源于Fiore 等人提出的基于身份的認(rèn)證密鑰交換協(xié)議[6]. 在該協(xié)議中, KGC 使用主秘密為用戶身份標(biāo)識構(gòu)造Schnorr 簽名[7]并作為用戶的私鑰. 雖然該協(xié)議存在漏洞[8], 但現(xiàn)有許多無雙線性配對的CL-AKE 協(xié)議[9–12]仍借鑒該設(shè)計思想, 其中部分方案如文獻[9] 也仍然存在類似Fiore 等人協(xié)議的缺陷: 攻擊者可通過特殊構(gòu)造的假公鑰和臨時會話信息, 將密鑰計算中用戶的部分私鑰信息“消元”[10,12], 從而在未知用戶部分私鑰的情況下偽裝任意用戶. 近年來部分CL-AKE 協(xié)議[13,14]依然存在類似漏洞, 其攻擊方式可參考文獻[10].

設(shè)計CL-AKE 協(xié)議的關(guān)鍵問題是, 如何在會話密鑰計算中設(shè)計合適的信息糾纏, 使攻擊者無法通過公鑰替換進行偽裝, 同時兼顧效率與可證明安全性. Sun 等人方案[10]和Shan 等人方案[12]在密鑰計算中加入復(fù)雜的信息糾纏來解決公鑰替換導(dǎo)致的消元問題. 然而, 為了使安全證明成功, 這些方案存在冗余的計算. 以Shan 等人的方案[12]為例, 為了使協(xié)議安全性歸約到Gap Diffie-Hellman 假設(shè), 其密鑰計算包括了冗余的臨時信息與用戶長期信息的糾纏, 這制約著協(xié)議的運行效率與優(yōu)化. 本文試圖解決該問題.

預(yù)計算可用于優(yōu)化AKE 協(xié)議的運行效率[15]. 以KEA+協(xié)議[16]、OAKE 協(xié)議族[15]為例, 這些協(xié)議將會話中可離線計算的部分進行預(yù)計算, 從而減少不必要的在線計算, 提高了運行效率. 本文嘗試使用預(yù)計算技巧來提高CL-AKE 協(xié)議的運行效率.

1.2 本文主要工作

本文提出一種高效的無證書認(rèn)證密鑰交換協(xié)議OPPRE, 并在隨機預(yù)言機模型下給出其e2CK 安全性證明. 協(xié)議OPPRE 在確保安全性的同時, 避免冗余的會話臨時信息與用戶長期信息的糾纏, 從而在允許預(yù)計算的前提下, 該協(xié)議有較高的效率. 同時協(xié)議OPPRE 還擁有抗公鑰替換攻擊、前向安全、抗密鑰泄露偽裝、抗未知密鑰共享等安全屬性. 經(jīng)過對比分析, 協(xié)議OPPRE 有較好的安全性和通信、計算效率.

2 預(yù)備知識

設(shè)S 為一個集合, s ←$S 指從集合S 中均勻隨機抽樣一個元素s; 若U 是一個用戶, 則IDU指用戶U 的用戶標(biāo)識符, 以下假定用戶標(biāo)識符和用戶一一對應(yīng).

2.1 無證書密鑰交換

在無證書密鑰交換中, KGC 擁有系統(tǒng)主秘密, 并進行系統(tǒng)參數(shù)的建立; KGC 根據(jù)用戶U 的標(biāo)識符IDU, 使用系統(tǒng)主秘密來生成用戶U 的部分私鑰. 每個用戶在本地生成秘密值, 然后將秘密值和其部分私鑰組合為其長期私鑰, 用戶公鑰根據(jù)長期私鑰生成. 用戶之間根據(jù)公共信息及自身私密信息進行密鑰交換,具體例子可參考本文提出的無證書認(rèn)證密鑰協(xié)議OPPRE (圖1).

2.2 困難性假設(shè)

本文的安全性證明使用到以下難題假設(shè), 設(shè)G 是階為q 的循環(huán)群且其生成元為P:

CDH 問題(Computational Diffie-Hellman Problem): 給定(aP,bP), 求abP. 其中a,b ←$Z?q.

DDH 問題(Decisional Diffie-Hellman Problem): 給定(aP,bP,cP), 判定是否有CDH(aP,bP) =cP(即cP =abP) 成立. 其中a,b,c ←$Z?q.

GDH 問題(Gap Diffie-Hellman Problem): 給定(aP,bP) 和DDH 預(yù)言機, 求解CDH(aP,bP). 其中, a,b ←$Z?q; 給定任意(aP,bP,cP), DDH 預(yù)言機可判定是否有CDH(aP,bP) = cP. GDH 假設(shè)定義為: 對于任意多項式時間攻擊者, GDH 問題可解的概率是可忽略的.

2.3 安全模型

本文對Yang 等人優(yōu)化的e2CK 模型[5]進行一定的修改, 并在修改得到的模型上進行協(xié)議安全性證明. 本節(jié)僅粗略描述e2CK 模型的內(nèi)容并指出修改的部分, 具體細節(jié)請參考文獻[5].

e2CK 安全模型定義為攻擊者與模擬者的安全游戲, 攻擊者控制整個信道, 模擬者負(fù)責(zé)生成公共信息和用戶信息并模擬CL-AKE 協(xié)議的運行. 攻擊者可發(fā)出如下幾種類型的問詢:

? Send: 攻擊者通過該類問詢控制用戶之間的消息傳遞, 并指定用戶在會話中使用的公鑰. 其中,Send0、Send1、Send2分別模擬會話初始方發(fā)送信息、應(yīng)答方接受并應(yīng)答信息、初始方接受信息的行為.

? Reveal: 該問詢允許攻擊者泄露相關(guān)的秘密信息, 如會話臨時秘密、用戶的部分私鑰、秘密值、KGC 主秘密、完整會話的會話密鑰等;

完全泄露與會話新鮮性的定義: CL-AKE 協(xié)議會話包含臨時秘密、用戶部分私鑰和秘密值三種秘密信息, 如果會話中三種秘密全部泄露, 則稱該會話完全泄露; 一個會話是新鮮的, 當(dāng)且僅當(dāng)該會話未完全泄露且未被Reveal 問詢, 同時: 若匹配會話存在, 則要求匹配會話也未完全泄露; 若匹配會話不存在, 則要求會話對等方的部分私鑰及秘密值未同時泄露. 注意, 若用戶的公鑰被替換, 則在會話中認(rèn)為該用戶的秘密值被泄露.

安全游戲分為兩個階段. 在階段1 中, 攻擊者可發(fā)出上述任意問詢, 當(dāng)攻擊者發(fā)出Test 問詢后, 游戲進入階段2; 在階段2 中攻擊者可繼續(xù)進行上述除Test 之外的問詢. 安全游戲結(jié)束時, 攻擊者猜測從Test 問詢返回的密鑰是sid*的會話密鑰還是隨機密鑰. 如果攻擊者猜測成功并且會話sid*是新鮮的, 則稱攻擊者成功攻擊該CL-AKE 協(xié)議.

本節(jié)安全模型通過Send 問詢來刻畫公鑰替換攻擊(詳見第4 節(jié)), 而不是通過提供“公鑰替換問詢”來刻畫, 這是本文安全模型與其原始版本[5]的主要區(qū)別. 兩種刻畫公鑰替換攻擊的能力是等價的, 因為它們都允許攻擊者欺騙合法用戶使用假公鑰進行會話建立. 本文通過Send 問詢刻畫公鑰替換攻擊的好處為: 一方面, 公鑰(來自用戶或來自攻擊者) 包含在Send 問詢的輸入中, 標(biāo)明用戶在本次會話中所使用的公鑰, 攻擊者不再需要額外的問詢來進行公鑰替換, 這簡化了證明過程并清晰地刻畫了公鑰替換攻擊; 另外一方面, 不需要定義額外的事件來判斷攻擊者是否發(fā)出公鑰替換攻擊, 從而簡化證明過程. 原始版本[5]的模型需要定義事件ReplacePK 來判斷是否發(fā)生公鑰替換.

直觀上, e2CK 安全的CL-AKE 協(xié)議要求: 若會話及其匹配會話不被完全泄露, 則會話密鑰不泄露;若不存在匹配會話(對等方不存在對應(yīng)臨時秘密), 則要求在會話不被完全泄露, 且會話對等方部分私鑰及秘密值不同時泄露的情況下, 會話密鑰不泄露.

3 協(xié)議設(shè)計

本節(jié)從抵抗攻擊、效率、可證明安全性等角度給出CL-AKE 協(xié)議設(shè)計思想, 并在此思想基礎(chǔ)上提出一種高效的CL-AKE 協(xié)議.

3.1 設(shè)計思想

設(shè)xU,sU,tU分別是用戶U 的秘密值、部分私鑰、會話臨時秘密, XU,SU,TU分別是對應(yīng)的公開信息, 具體含義可參考OPPRE 協(xié)議1. 以用戶A 與用戶B 的密鑰交換為例:

? 協(xié)議需要保證認(rèn)證密鑰交換的安全屬性, 如認(rèn)證性、抗長期/短期秘密泄露偽裝、前向安全性等. 因此A 的會話密鑰計算必須包含: xA,sA與XB,SB的糾纏、tA與XB,SB的糾纏、tA與TB的糾纏.

? 為抵抗公鑰替換攻擊, 協(xié)議需要確保, 無論攻擊者如何構(gòu)造XB,TB, 會話密鑰始終有tA,sA,xA與SB的糾纏. 否則攻擊者可將SB消元從而在未知sB的情況下向A 偽裝B. 文獻[9,13,14] 中的協(xié)議不能達到該要求, 因此存在漏洞.

? 在保證安全性的前提下, 協(xié)議需要盡量降低計算量. 從上述內(nèi)容知, tA,sA,xA必須都與TB,SB,XB有糾纏. 為提高效率, 可考慮混合糾纏, 比如(tA+xA)(TB+SB). 然而混合糾纏的設(shè)計必須與可證明安全緊密結(jié)合, 以防出現(xiàn)類似文獻[9] 的情況.

根據(jù)上述思想, 本文嘗試從可預(yù)計算的角度來設(shè)計高效、安全的協(xié)議. 考慮如下信息糾纏:

KA1,KA2用以抵抗私鑰泄露偽裝, 同時確保前向安全性; KA3,KA4,KA5一方面確保攻擊者無法將SB完全消元, 另一方面保證可借助隨機預(yù)言機技巧來完成安全性證明, 其中KA3,KA4不包含臨時信息, 因此可進行預(yù)計算降低計算量. 綜上, 本文提出一種高效的無證書認(rèn)證密鑰交換協(xié)議OPPRE (optimal precomputation). 下節(jié)給出協(xié)議OPPRE 的詳細描述.

3.2 協(xié)議描述

系統(tǒng)建立: 給定安全參數(shù), KGC 生成一個階為素數(shù)q 的循環(huán)群G 及其生成元P, 并選擇兩個哈希函數(shù)h:{0,1}l×G →Z?q,H :{0,1}l×{0,1}l×G9→{0,1}n, 其中l(wèi) 是身份標(biāo)識符的長度, n 是會話密鑰的長度, H 作為密鑰導(dǎo)出函數(shù). KGC 隨機抽取s ←$Z?q作為主秘密, 并計算系統(tǒng)公鑰Ppub=sP, 最后公開系統(tǒng)參數(shù)Params=(l,n,q,P,G,Ppub,h,H).

用戶部分私鑰生成: 給定IDU,KGC 隨機抽取rU←$Z?q并計算RU=rUP,sU=rU+h(IDU,RU)s.然后KGC 通過安全信道返回sU,RU給用戶U.

用戶秘密值及公鑰生成: 用戶IDU隨機生成xU←$Z?q作為秘密值, 其公鑰為XU= xUP. 用戶完整的私鑰為(xU,sU).

密鑰交換過程: 設(shè)用戶A 為會話發(fā)起方, B 為應(yīng)答方, 雙方密鑰交換過程如下:

首先A 隨機選擇tA←$Z?q, 計算TA=tAP, 發(fā)送MA=(IDA,XA,RA,TA) 給B.

圖1 OPPRE 協(xié)議Figure 1 OPPRE protocol

由以下等式知A 與B 可建立相同會話密鑰:

4 安全性證明

證明: 給定GDH 問題實例(aP,bP), 現(xiàn)構(gòu)造算法S 求解abP. S 首先生成系統(tǒng)主密鑰, 并生成系統(tǒng)參數(shù)、用戶公私鑰等信息.

我們通過分類A 在游戲中未泄露的信息來完成安全證明. 設(shè)A 選取(Role,IDi,IDj,X?i,X?j,T?i,T?j)為測試會話, 其中, 會話擁有者為i, Xi,Xj是會話中使用的公鑰, T?i,T?j是會話中使用的臨時會話公鑰, Role 標(biāo)識用戶是會話初始方I 還是應(yīng)答方R. 設(shè)x?i,x?j,t?i,t?j,s?i,s?j為i,j 相應(yīng)的秘密信息,K?1,K?2,K?3,K?4,K?5為測試會話的會話主秘密(如圖1), 現(xiàn)分類及難題嵌入方法如下:

? 類型1: x?i,x?j未泄露, 令X?i=aP,X?j=bP.

? 類型2: x?i,t?j未泄露, 令X?i=aP,T?j=bP.

? 類型3: x?i,s?j未泄露, 令X?i=aP,S?j=bP.

? 類型4: t?i,x?j未泄露, 令T?i=aP,X?j=bP.

? 類型5: t?i,t?j未泄露, 令T?i=aP,T?j=bP.

? 類型6: t?i,s?j未泄露, 令T?i=aP,S?j=bP.

? 類型7: s?i,x?j未泄露, 令S?i=aP,X?j=bP.

? 類型8: s?i,t?j未泄露, 令S?i=aP,T?j=bP.

? 類型9: s?i,s?j未泄露, 令S?i=aP,S?j=bP.

為完美模擬協(xié)議的運行, S 需要維護5 個表hlist,Hlist,Slist,Clist,NClist. 其中表hlist 用于存儲A與隨機預(yù)言機h 的交互, 表Hlist 用于存儲A 與隨機預(yù)言機H 的交互, 表Slist 表用于存儲Send0的內(nèi)容, 表Clist 用于存儲所有會話主秘密完整的會話及其會話密鑰, 表NClist 用于存儲會話主秘密缺失的會話及其會話密鑰.

以下我們僅給出類型6 下的安全性證明, 該類型的規(guī)約最復(fù)雜. 其它8 種類型的證明類似.

類型 6: S 從 p 個用戶中隨機抽取兩個用戶 i,j, 并猜測它們的第 k 次會話 (Role,IDi,IDj,X?i,X?j,T?i,T?j) 作為挑戰(zhàn)會話. 不失一般性, 假設(shè)i 作為測試會話的初始方.

在類型6 下, S 無t?i,s?j(分別為a,b), 因此需要以如下方式構(gòu)造S?j對應(yīng)的R?j: 首先隨機選擇l?j←$Z?q, 計算R?j= S?j(即bP)?l?jPpub, 并令h(IDj,R?j) = l?j. 然后將s?j作為測試會話參與方j(luò) 的部分私鑰, R?j作為j 的部分私鑰對應(yīng)的公共信息. A 問詢的模擬如下:

Send0(IDU,IDV): 此問詢下IDU作為初始方. 如果(IDU,IDV) = (IDi,IDj), 且該會話是i 與j 的第k 次會話, 即測試會話, 則S 在表Slist 中存入(IDi,IDj,⊥,T?i(= aP)) 并返回T?i; 否則, 隨機選取tU←$Z?q, 計算TU=tUP 并返回給A, 然后S 在表Slist 中存入(IDU,IDV,tU,TU).

Send1(IDU,IDV,XV,TV): 此問詢下IDU作為應(yīng)答方. S 檢查表Clist、表NClist 中是否已存在相關(guān)會話, 存在則返回⊥, 否則S 隨機選取tU←$Z?q, 計算TU= tUP 并返回給A. 然后分成多個情況來繼續(xù)模擬:

(3) 其它情況: 類似上述情況進行處理.

Send2(IDU,IDV,XU,XV,TU,TV): 該問詢的模擬與Send1類似. 以情況(IDU,IDV,XU,XV,TU,TV) = (IDi,IDj,X?i,X?j,T?i,T?j) 為例, S 無 t?i,s?j,x?j,t?j, 無法計算 K?1,K?2,K?5中的 t?i(T?j+X?j),t?i(T?j+S?j),t?iT?j. S 可類似Send1的情況2 進行處理.

H 問詢:(IDV,IDU,XV,XU,TV,TU,K′1,K′2,K′3,K′4,K′5): 隨機預(yù)言機H 的模擬需要與Send 問詢、SessionKeyReveal 問詢的模擬一致. 當(dāng)A 發(fā)出了問詢, S 首先檢查該問詢在表Hlist 中是否已存在應(yīng)答,如果有則返回; 否則S 按如下情況處理:

(1) 情況1: 表Clist 不存在會話(IDV,IDU,XV,XU,TV,TU,?,?,?,?,?,?), 且表NClist 也不存在該會話. 此時S 隨機選取SK ←${0,1}n, 返回SK 并在表H 中記錄該問詢.

(2) 情況2: 表Clist 中存在會話(IDV,IDU,XV,XU,TV,TU,?,?,?,?,?,SK). S 取出分量K1,···,K5, 若K′1=K1,··· ,K′5=K5, 則S 直接返回SK; 否則類似情況1 處理.

(3) 情況3: 表NClist 存在會話(IDV,IDU,XV,XU,TV,TU,?,?,?,?,?,SK). 此時S 取出該會話的K#值(# 代表有缺失). S 通過DDH 預(yù)言機, 判斷A 此次問詢中是否含有K#中缺失的值,如果有則更新NCL 列表中的這些K#值, 如果所有的缺失值都獲得, 則將該會話從表NClist 中刪除, 在表Clist 中記錄該會話.

特別地, 當(dāng)(IDV,IDU,XV,XU,TV,TU) = (IDi,IDj,X?i,X?j,T?i,T?j), S 可通過類似Send1、Send2的處理方式, 獲得s?jX?i,t?iT?j等缺失值. 如果S 獲得t?iS?j或者s?jT?i, 可直接返回該值作為GDH 解并停止模擬.

協(xié)議的認(rèn)證性: 協(xié)議OPPRE 具有隱式認(rèn)證性, 即僅建立會話的雙方(長期秘密未完全泄露) 擁有相同的會話密鑰, 其中“隱式” 指雙方無法確定對方是否已建立相同會話密鑰. 由上述證明知, 若攻擊者不同時擁有用戶的部分私鑰與秘密值(對應(yīng)攻擊類型1、3、7、9), 則攻擊者無法計算會話密鑰. 因此, 協(xié)議OPPRE 具有隱式認(rèn)證性. 在消息交換中加入報文認(rèn)證碼的發(fā)送可使OPPRE 協(xié)議達到顯式認(rèn)證[17].

5 協(xié)議性能分析

本節(jié)給出對協(xié)議OPPRE 的優(yōu)化及效率分析, 與相關(guān)協(xié)議在效率、消息長度、安全性等方面作對比.對比時使用橢圓曲線群來對G 進行實例化, 并對所有協(xié)議進行同等的預(yù)計算優(yōu)化. 對比如表1.

表1 協(xié)議效率對比Table 1 Comparison of protocols efficiency

表1 符號解釋: Em指橢圓曲線群G 上一次點乘運算的開銷, Ea指G 上一次點加運算的開銷, Th指一次哈希運算的開銷, |G| 指一個G 元素的大小, |Z?q| 指一個Z?q元素的大小. RA和TA作為消息的一部分進行考慮.

CL-AKE 協(xié)議的預(yù)計算.在實際運行中, CL-AKE 用戶需要從公共目錄中獲取對方的公鑰, 其中目錄中的公鑰可能過時或被替換, 但這不影響CL-AKE 協(xié)議的預(yù)計算, 因為協(xié)議會話的建立是在線的, 而公鑰的獲取、更新、替換等操作都是離線的, 用戶可在未建立會話的期間進行公鑰的更新、預(yù)計算等. 另外,SU作為長期信息可被緩存.

協(xié)議OPPRE 的效率優(yōu)化: 以用戶A 與用戶B 的密鑰交換為例. (xA,sA)是A 的長期私鑰, XB,SB作為B 的長期信息可被A 緩存, 因此KA3,KA4可被預(yù)計算. KA1,KA2,KA5的構(gòu)造需要3 次點乘法, 2 次點加法.

由表1 的對比可知, 與其它協(xié)議相比, 協(xié)議OPPRE 在安全和效率上達到更好的平衡.

6 結(jié)束語

本文根據(jù)e2CK 模型特點, 給出CL-AKE 協(xié)議的設(shè)計思路, 并根據(jù)該思路提出了一種高效的無證書密鑰交換協(xié)議OPPRE, 該協(xié)議在隨機預(yù)言機模型下具有e2CK 安全性. 協(xié)議OPPRE 避免冗余的會話臨時秘密與長期秘密的糾纏, 從而在保證可證明安全性的前提下, 協(xié)議可通過預(yù)計算提高運行效率. 因此,協(xié)議OPPRE 在效率、安全性需求較高的實際場景中(如Ad-Hoc 網(wǎng)絡(luò))有較好的應(yīng)用價值.