格上基于口令的三方認(rèn)證密鑰交換協(xié)議

于金霞，廉歡歡，湯永利，史夢(mèng)瑤，趙宗渠

?

格上基于口令的三方認(rèn)證密鑰交換協(xié)議

于金霞，廉歡歡，湯永利，史夢(mèng)瑤，趙宗渠

（河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454000）

三方口令認(rèn)證密鑰交換協(xié)議允許用戶通過(guò)一個(gè)服務(wù)器在不安全的信道中建立一個(gè)受保護(hù)的會(huì)話密鑰，而現(xiàn)有的格上PAKE協(xié)議絕大多數(shù)都是針對(duì)兩方設(shè)計(jì)的，無(wú)法適用于大規(guī)模的通信系統(tǒng)?；诖?，提出一種新的格上三方PAKE協(xié)議，該協(xié)議主要以可拆分公鑰加密體制及其相應(yīng)的近似平滑投射散列函數(shù)為基礎(chǔ)進(jìn)行構(gòu)造，并通過(guò)在協(xié)議中引入消息認(rèn)證機(jī)制的方式來(lái)防止消息重放攻擊。與同類協(xié)議相比，所提協(xié)議減少了通信輪數(shù)，提高了效率和協(xié)議應(yīng)用的安全性。

三方密鑰交換；口令認(rèn)證；LWE問(wèn)題；可證安全性

1 引言

在基于口令的認(rèn)證密鑰交換（PAKE, password-based authenticated key exchange）協(xié)議中，用戶之間通過(guò)共享一個(gè)普通的低熵口令來(lái)認(rèn)證通信方身份并進(jìn)行密鑰交換，最后建立共享的會(huì)話密鑰。口令具有簡(jiǎn)單易記、操作方便的特點(diǎn)，基于口令的方案可以消除對(duì)公鑰基礎(chǔ)設(shè)施和安全硬件的依賴，且提高了系統(tǒng)的使用便利性。因此，基于口令的認(rèn)證密鑰交換協(xié)議是目前應(yīng)用最為廣泛的一種密鑰交換協(xié)議[1-7]。

兩方PAKE（2PAKE, two-party PAKE）協(xié)議需要每?jī)蓚€(gè)參與者共享一個(gè)口令建立會(huì)話密鑰，但是這種方案在大量的用戶通信中對(duì)口令存儲(chǔ)比較復(fù)雜，需要消耗較高的管理成本。而三方PAKE（3PAKE, three-party PAKE）協(xié)議使每個(gè)用戶只需和服務(wù)器共享一個(gè)口令來(lái)進(jìn)行認(rèn)證，解決了2PAKE的局限性。

第一個(gè)真正意義上的PAKE協(xié)議最早由Bellovin等[1]提出，其安全性的分析采用啟發(fā)式方法。2001年，Katz，Ostrovsky和Yung[2]利用CCA2（adaptive chosen-ciphertext attack）安全的加密體制及相應(yīng)的平滑投射散列（SPH, smooth projection hash）函數(shù)進(jìn)行密鑰交換，提出第一個(gè)標(biāo)準(zhǔn)模型下的高效PAKE協(xié)議，簡(jiǎn)稱KOY協(xié)議。2012年，Zhao等[3]基于CDH假設(shè)給出了一種可證明安全的3PAKE協(xié)議，協(xié)議利用陷門測(cè)試技術(shù)在3eCK模型下給出安全性證明。2015年，F(xiàn)arash等[4]提出了改進(jìn)的PAKE協(xié)議，克服協(xié)議不能抵抗離線字典攻擊的不足，且提供了會(huì)話密鑰的前向保密性。隨后，密碼學(xué)者基于不同密碼學(xué)組件設(shè)計(jì)了不同效率和安全性的PAKE協(xié)議[5-6]。

上述協(xié)議的安全性證明絕大多數(shù)都是依賴于大整數(shù)分解和離散對(duì)數(shù)問(wèn)題的困難性，這些困難問(wèn)題已經(jīng)可以用量子算法在多項(xiàng)式時(shí)間內(nèi)解決。而基于格困難問(wèn)題的公鑰密碼體制在量子計(jì)算下還不存在多項(xiàng)式時(shí)間高效求解算法，并且格上的運(yùn)算是矩陣–向量上的乘法，具備并行計(jì)算、效率高的特點(diǎn)。因此，設(shè)計(jì)一個(gè)基于格困難問(wèn)題的口令認(rèn)證密鑰交換協(xié)議變得尤為重要。

在基于格理論的密碼體制中，對(duì)PAKE的研究比較缺乏，直到2009年Katz等[7]才構(gòu)造出了首個(gè)基于格的CCA安全的加密體制及其相應(yīng)的近似平滑投射散列（ASPH, approximate smooth projection hash）函數(shù)，將這些組件與KOY協(xié)議[2]以及Gennaro-Lindell協(xié)議[8]相結(jié)合，提出第一個(gè)基于格的2PAKE協(xié)議。2011年，Ding等[9]將Katz等[8]提出的加密體制和近似平滑投射函數(shù)應(yīng)用于Groce-Katz框架[10]，提出了一種基于格困難問(wèn)題假設(shè)且效率較高的協(xié)議，并且在標(biāo)準(zhǔn)模型下給出此協(xié)議安全性證明。2013年，葉茂等[11]利用Katz等[8]提出的公鑰加密體制以及ASPH函數(shù)組件，基于LWE問(wèn)題設(shè)計(jì)了第一個(gè)基于格的3PAKE協(xié)議，提高了安全性并滿足大規(guī)模通信系統(tǒng)的應(yīng)用需求，但仍存在通信效率較低的缺陷。2014年，Peiker[12]提出一種基于環(huán)上帶誤差學(xué)習(xí)（RLWE, ring learning with error）的簡(jiǎn)單低帶寬調(diào)和函數(shù)，利用這種技術(shù)構(gòu)造密鑰封裝機(jī)制，實(shí)現(xiàn)了密鑰交換。2015年，Zhang等[13]基于RLWE困難問(wèn)題提出2PAKE協(xié)議，并給出安全性證明，但不適用于大規(guī)模的通信系統(tǒng)。2016年，趙秀鳳等[14]利用格困難問(wèn)題提出一種密鑰交換協(xié)議，但該協(xié)議需要密鑰生成中心生成長(zhǎng)期私鑰和臨時(shí)私鑰，成本花銷大。2017年，Xu等[15]利用DH思想，基于環(huán)上LWE（learning with error）問(wèn)題提出了可證明安全的3PAKE協(xié)議，但該協(xié)議存在效率低等局限。

2017年，Zhang等[16]將拆分的公鑰加密體制應(yīng)用于Katz等[7]的3次通信的框架中，提出了基于格困難問(wèn)題且僅需兩輪通信、效率較高的PAKE協(xié)議，但該方案是兩方的口令密鑰交換協(xié)議。由于三方PAKE協(xié)議建立最終的會(huì)話密鑰需要融合所有用戶的信息，那么需要添加函數(shù)對(duì)用戶端信息進(jìn)行計(jì)算，因此文獻(xiàn)[16]提出的2PAKE協(xié)議無(wú)法直接應(yīng)用于三方協(xié)議中。另外，三方協(xié)議在引入可信服務(wù)器后，用戶端與服務(wù)器進(jìn)行通信時(shí)會(huì)存在消息重放的可能性。

為解決上述協(xié)議存在的問(wèn)題，本文提出一種新的基于LWE問(wèn)題的三方PAKE協(xié)議。主要貢獻(xiàn)有以下兩個(gè)方面：1) 在文獻(xiàn)[16]的基礎(chǔ)上，添加偽隨機(jī)函數(shù)來(lái)融合所有用戶端的信息，并且在協(xié)議中引入消息認(rèn)證機(jī)制，通過(guò)添加會(huì)話序列號(hào)的方式達(dá)到抵抗消息重放的目的，使本文所提三方協(xié)議更具有可行性；2) 利用拆分的公鑰加密體制及相應(yīng)的ASPH函數(shù)這兩個(gè)組件構(gòu)造協(xié)議，從而提高了通信效率。本文所提協(xié)議解決了2PAKE的局限，避免了消息重放攻擊的弱點(diǎn)，具備抗量子攻擊的特點(diǎn)，有較少的通信輪數(shù)和更高的通信效率。

2 背景知識(shí)

2.1 格的相關(guān)知識(shí)

2.2 安全模型

本節(jié)是在Bellare等[18]所提出模型（簡(jiǎn)稱為BPR模型）基礎(chǔ)上給出的本文協(xié)議的安全性分析模型。該協(xié)議依賴于一個(gè)假設(shè)：在協(xié)議執(zhí)行之前，可信第三方制定公共參考串（CRS, common reference string）和其他公共參數(shù)。

2.3 基于格的公鑰加密體制

基于格的公鑰加密體制具體如下。

2.4 近似平滑投射散列函數(shù)

平滑投射散列函數(shù)是由Cramer等[21]為實(shí)現(xiàn)CCA安全的公鑰加密體制首次提出來(lái)的，后來(lái)在PAKE協(xié)議方面的一些研究[7,22]延伸了這個(gè)概念。本文采用文獻(xiàn)[16]構(gòu)造的基于格的PAKE協(xié)議的ASPH函數(shù)，此構(gòu)造[16]根據(jù)文獻(xiàn)[7]進(jìn)行了修改。

3 基于格的三方PAKE協(xié)議

3.1 協(xié)議描述

本節(jié)基于文獻(xiàn)[16]提出的可拆分公鑰密碼體制，利用ASPH函數(shù)簇這個(gè)組件設(shè)計(jì)一種格上的基于口令的三方認(rèn)證密鑰交換協(xié)議。協(xié)議中的符號(hào)說(shuō)明如表1所示。

表1 基于格的三方協(xié)議PAKE協(xié)議中的符號(hào)說(shuō)明

圖1 基于格的三方PAKE協(xié)議

基于格的三方PAKE協(xié)議的兩輪消息認(rèn)證中，第一輪用戶向服務(wù)器發(fā)送的密文中包含帶標(biāo)簽的密文，服務(wù)器通過(guò)檢驗(yàn)密文的有效性實(shí)現(xiàn)服務(wù)器對(duì)用戶的顯示認(rèn)證，在第二輪中實(shí)現(xiàn)了用戶對(duì)服務(wù)器的顯示認(rèn)證，因此本文協(xié)議實(shí)現(xiàn)了用戶與服務(wù)器的雙向認(rèn)證。

3.2 安全性證明

本節(jié)在2.2節(jié)所述的安全模型證明了協(xié)議的安全性。

目前已完成與用戶相關(guān)的send詢問(wèn)的修改，同樣地，與用戶相關(guān)的send詢問(wèn)的修改類似于此方式。

4 性能分析

在安全性方面，本文協(xié)議在方案中添加會(huì)話序列號(hào)，提供了更強(qiáng)的消息認(rèn)證機(jī)制，由表2可以看出，與其他協(xié)議[11,15-16]相比，本文協(xié)議可以抵抗重放攻擊，安全性能更高。

在效率方面，本文協(xié)議利用改進(jìn)的基于格的CCA安全的公鑰加密體制，減少了加密參數(shù)，降低了計(jì)算代價(jià)。由表2可以看出，與其他協(xié)議相比[11,15-16]，本文協(xié)議的服務(wù)器計(jì)算開銷和用戶計(jì)算開銷都較低。此外，本文協(xié)議只需要兩輪通信，通信開銷主要由密文和投射密鑰的大小來(lái)決定，而投射密鑰只依賴于散列密鑰，這使本文協(xié)議的通信效率提高。

X-PAKE協(xié)議提出基于格的3PAKE協(xié)議，通信輪數(shù)為3輪，消息傳輸量為6條，通信代價(jià)主要取決于多項(xiàng)式環(huán)和多個(gè)散列函數(shù)計(jì)算得出的值，由于協(xié)議需要傳輸?shù)南⒘枯^多，造成通信開銷增大。根據(jù)分析和表2數(shù)據(jù)可得，X-PAKE協(xié)議的通信開銷比本文協(xié)議大。

Z-PAKE協(xié)議是基于格的2PAKE協(xié)議，是針對(duì)兩方設(shè)計(jì)的，不適用于大規(guī)模的通信系統(tǒng)，協(xié)議需要兩輪通信，通信代價(jià)主要取決于密文和投射密鑰的大小，本文協(xié)議和Z-PAKE協(xié)議相比，除了多一個(gè)用戶同樣的開銷之外，并沒(méi)有增加其他較大的開銷。但是Z-PAKE協(xié)議按照傳統(tǒng)的方式實(shí)現(xiàn)為3PAKE協(xié)議，至少需要4輪通信，即8條消息傳輸量，而本文三方協(xié)議只需2輪通信即4條傳輸量。根據(jù)分析和表2可得，本文協(xié)議的通信開銷較低，還可以抵抗重放攻擊。

以上分析結(jié)果表明，本文協(xié)議適用于大規(guī)模的通信系統(tǒng)，不僅具有抵抗重放攻擊的安全性，還具有較低的通信和計(jì)算開銷。因此，本文協(xié)議更具有可行性。

表2 4種協(xié)議性能比較

5 結(jié)束語(yǔ)

本文提出三方的口令認(rèn)證密鑰交換協(xié)議，協(xié)議中使用的密碼機(jī)制是基于格上的LWE困難問(wèn)題，在后量子時(shí)代具有重要意義。三方的PAKE協(xié)議是客戶端–客戶端–服務(wù)器的形式，大量用戶只與服務(wù)器共享一個(gè)口令即可建立共享會(huì)話密鑰，因此更符合用戶端到端安全通信的需求。除此之外，本文協(xié)議可以有效抵抗攻擊者重放之前的消息，提高了協(xié)議應(yīng)用的安全性。在隨機(jī)預(yù)言模型下，本文給出了嚴(yán)格的安全性證明。相比已有的同類協(xié)議，本文協(xié)議在通信效率和安全性上均有所提高。本文所設(shè)計(jì)的格上基于口令的認(rèn)證密鑰交換協(xié)議，口令以明文的形式存儲(chǔ)在服務(wù)器上，一旦服務(wù)器信息泄露，攻擊者獲得口令后會(huì)偽裝成合法用戶與服務(wù)器通信，這將對(duì)用戶和服務(wù)器的數(shù)據(jù)安全帶來(lái)危害。因此，構(gòu)造一個(gè)不讓服務(wù)器直接存儲(chǔ)明文口令的格上3PAKE協(xié)議是未來(lái)的研究方向。

[1] BELLOIN S M, MERRITT M. Encrypted key exchange: password-based protocols secure against dictionary attacks[C]//IEEE Symposium on Research in Security and Privacy. 1992: 72-84.

[2] KATZ J, OSTROVSKY R, YUNG M. Efficient password-authenticated key exchange using human-memorable passwords[M]. Advances in Cryptology-EUROCRYPT. 2001: 475-494.

[3] ZHAO J, GU D. Provably secure three-party password-based authenticated key exchange protocol[J]. Information Sciences, 2012, 184(1): 310-323.

[4] FARASH M S, ISLAM S H, OBAIDAT M S. A provably secure and efficient two-party password‐based explicit authenticated key exchange protocol resistance to password guessing attacks[J]. Concurrency & Computation Practice & Experience, 2015, 27(17): 4897-4913.

[5] ABLALLA M, BENHAMOUDA F, MACKENZIE P. Security of the J-PAKE password-authenticated key exchange protocol[C]//IEEE Symposium on Security and Privacy. 2015: 571-587.

[6] 魏福山, 馬建峰, 李光松, 等. 標(biāo)準(zhǔn)模型下高效的三方口令認(rèn)證密鑰交換協(xié)議[J]. 軟件學(xué)報(bào), 2016, 27(9): 2389-2399.

WEI F S, MA J F, LI G S, et al. Efficient three-party password-based authenticated key exchange protocol in the standard model[J]. Journal of Software, 2016, 27(9): 2389-2399.

[7] KATZ J, VAIKUNTANATHAN V. Smooth projective hashing and password-based authenticated key exchange from lattices[M]. Advances in Cryptology-ASIACRYPT. 2009: 636-652.

[8] GENNARO R, LINDELL Y. A framework for password-based authenticated key exchange[C]//International Conference on the Theory and Applications of Cryptographic Techniques. 2003: 524-543.

[9] DING Y, FAN L. Efficient password-based authenticated key exchange from lattices[C]//Seventh International Conference on Computational Intelligence and Security. 2012: 934-938.

[10] GROCE A, KATZ J. A new framework for efficient password-based authenticated key exchange[C]//Proceedings of the 17th ACM conference on Computer and communications security. 2010: 516-525.

[11] 葉茂, 胡學(xué)先, 劉文芬. 基于格的三方口令認(rèn)證密鑰交換協(xié)議[J]. 電子與信息學(xué)報(bào), 2013, 35(6): 1376-1381.

YE M, HU X X, LIU W F. Password authenticated key exchange protocol in the three party setting based on lattices[J]. Journal of Electronics & Information Technology, 2013, 35(6): 1376-1381

[12] PEIKERT C. Lattice cryptography for the internet[M]. Post-Quantum Cryptography. 2014: 197-219.

[13] ZHANG J, ZHANG Z, DING J, et al. Authenticated key exchange from ideal lattices[M]. Advances in Cryptology - EUROCRYPT. 2015: 719-751.

[14] 趙秀鳳, 高海英, 王愛(ài)蘭. 基于RLWE的身份基認(rèn)證密鑰交換協(xié)議[J].計(jì)算機(jī)研究與發(fā)展, 2016, 53(11): 2482-2490.

ZHAO X F, GAO H Y, WANG A L. An identity-based authenticated key exchange protocol from RLWE[J]. Journal of Computer Research and Development, 2016, 53(11): 2482-2490.

[15] XU D Q, HE D B, CHOO K K R. Provably secure three-party password authenticated key exchange protocol based on ring learning with error[C]//IACR Cryptology ePrint Archive. 2017: 360.

[16] ZHANG J, YU Y. Two-round PAKE from approximate SPH and instantiations from lattices[C]//International Conference on the Theory and Application of Cryptology and Information Security. 2017: 37-67.

[17] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]//ACM Symposium on Theory of Computing. 2005: 84-93.

[18] BELLARE M, POINTCHEVAL D, ROGAWAY P. Authenticated key exchange secure against dictionary attacks[M]. Advances in Cryptology-EUROCRYPT. 2000: 139-155.

[19] ABE M, CUI Y, IMAI H, et al. Efficient hybrid encryption from ID-based encryption[J]. Designs Codes & Cryptography, 2010, 54(3): 205-240.

[20] RAN C, HALEVI S, KATZ J. Chosen-ciphertext security from identity-based encryption[C]//International Conference on the Theory and Applications of Cryptographic Techniques. 2004: 207-222.

[21] CRAMER R, SHOUP V. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[C]// International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology. 2002: 45-64.

[22] KATZ J, VAIKUNTANATHAN V. Round-optimal password-based authenticated key exchange[M]. Theory of Cryptography. 2011: 293-310.

Password-based three-party authenticated key exchange protocol from lattices

YU Jinxia, LIAN Huanhuan, TANG Yongli, SHI Mengyao, ZHAO Zongqu

College of Computer Science and Technology, Henan Polytechnic University, Jiaozuo 454000, China

Password-based three-party authenticated key exchange protocol allow clients to establish a protected session key through a server over insecure channels. Most of the existing PAKE protocols on lattices were designed for the two parties, which could not be applied to large-scale communication systems, so a novel three-party PAKE protocol from lattices was proposed. The PAKE protocol was constructed by using a splittable public-key encryption scheme and an associated approximate smooth projective Hash function, and message authentication mechanism was introduced in the protocol to resist replay attacks. Compared with the similar protocols, the new protocol reduces the number of communication round and improves the efficiency and the security of protocol applications.

three-party key exchange, password authentication, LWE problem, provable security

TP309

A

10.11959/j.issn.1000-436x.2018237

于金霞（1974–），女，河南博愛(ài)人，博士，河南理工大學(xué)教授，主要研究方向?yàn)槿斯ぶ悄?、信息安全?/p>

廉歡歡（1993–），女，河南沁陽(yáng)人，河南理工大學(xué)碩士生，主要研究方向?yàn)樾畔踩?、密碼學(xué)。

湯永利（1972–），男，河南孟州人，博士，河南理工大學(xué)教授、碩士生導(dǎo)師，主要研究方向?yàn)樾畔踩?、密碼學(xué)。

史夢(mèng)瑤（1998–），女，河南許昌人，河南理工大學(xué)碩士生，主要研究方向?yàn)樾畔踩?、密碼學(xué)。

趙宗渠（1974–），男，河南沁陽(yáng)人，博士，河南理工大學(xué)講師，主要研究方向?yàn)槊艽a學(xué)、網(wǎng)絡(luò)安全、惡意代碼分析。

2018–02–05；

2018–06–09

趙宗渠，zhaozong_qu@hpu.edu.cn

國(guó)家密碼管理局“十三五”國(guó)家密碼發(fā)展基金資助項(xiàng)目（No.MMJJ20170122）；河南省科技廳基金資助項(xiàng)目（No.142300410147）；河南省教育廳基金資助項(xiàng)目（No.16A520013）；河南理工大學(xué)博士基金資助項(xiàng)目（No.B2014-044, No.B2016-39）；河南理工大學(xué)自然科學(xué)基金資助項(xiàng)目（No.T2018-1）

The “13th Five-Year” National Crypto Development Foundation (No.MMJJ20170122), The Project of Science and Technology Department of Henan Province (No.142300410147), The Project of Education Department of Henan Province (No.16A520013), The Doctoral Fund of Henan Polytechnic University (No.B2014-044, No.B2016-39), The Natural Science Foundation of Henan Polytechnic University (No.T2018-1)