幾個無證書簽名方案的偽造攻擊

王菁，李祖猛

幾個無證書簽名方案的偽造攻擊

王菁1，李祖猛2

（1. 廣州市信息工程職業學校基礎部，廣東 廣州 510640；2. 廣東科學技術職業學院計算機工程技術學院（人工智能學院），廣東 珠海 519090）

自2003年Al-Riyami和Paterson首次提出無證書公鑰密碼體制的概念和第一個無證書簽名方案以來，許多無證書簽名方案相繼被提出。湯永利等提出了9個無雙線性對運算的無證書簽名方案，并聲稱這些無證書簽名方案在橢圓曲線離散對數困難性假設下可證明是安全的。通過對這些無證書簽名方案進行安全性分析后，發現其中的5個可證明安全的無證書簽名方案不能抵抗替換公鑰攻擊，并且這5個無證書簽名方案中的3個簽名方案即使在不替換用戶公鑰的情況下，攻擊者也可以利用用戶的原始公鑰對任意消息偽造出有效的簽名。給出了具體的偽造攻擊方法，證明了這5個無證書簽名方案是不安全的。

無證書簽名；橢圓曲線；離散對數；公鑰替換攻擊

1 引言

在2003年亞密會上，Al-Riyami和Paterson[1]首次提出了無證書公鑰密碼體制的概念，并且給出了第一個無證書簽名方案。在無證書公鑰密碼體制中，密鑰生成中心（KGC，key generation center）和用戶一起完成用戶的部分密鑰生成過程，即用戶密鑰的一部分數據由KGC產生，然后KGC將其安全地傳輸給用戶，用戶自己產生密鑰的另外一部分數據，這兩部分密鑰數據組合在一起構成用戶的完整密鑰。這種產生密鑰的方式使KGC不能獲知用戶的完整私鑰，進而解決了基于身份的密碼體制[2]中的密鑰托管問題，而且在無證書公鑰密碼體制中，因為不再需要證書中心（CA）對用戶的證書進行管理和維護，解決了傳統基于PKI公鑰密碼體制[3]的證書管理問題，使無證書公鑰密碼體制受到了廣泛的關注。

無證書簽名是無證書公鑰密碼體制中的研究熱點之一。自Al-Riyami和Paterson在文獻[1]中提出第一個無證書簽名方案以來，很多無證書簽名方案相繼被提出[4-9]。在無證書公鑰密碼體制中，因為用戶的公鑰無法認證，所以無證書公鑰密碼方案的設計必須考慮抵抗替換公鑰攻擊。另外，在無證書公鑰密碼體制中，KGC參與用戶私鑰的部分數據產生，所以必須考慮惡意不誠實KGC的偽造攻擊。Huang等[10]提出的無證書簽名方案的安全模型定義了普通攻擊者、強攻擊者、超級攻擊者。2012年，王圣寶等[11]基于離散對數困難問題，提出了一個不使用雙線性對的無證書簽名方案，并在隨機預言模型中給出了安全性證明。但王亞飛等[12]指出文獻[11]是完全不安全的，即攻擊者可以獲取用戶的私鑰，并且基于橢圓曲線離散對數問題提出了新的方案，同時在隨機預言模型下給出了新方案的安全性證明。但樊愛苑等[13]對文獻[12]中的新方案進行安全性分析后，指出其難以抵抗不誠實KGC下的公鑰替換攻擊，并針對此安全缺陷，改變傳統無證書算法順序，提出了能夠抵抗不誠實KGC公鑰替換攻擊的新方案，且新方案避開了雙線性運算和逆運算，提升了運算效率，聲稱其新方案在自適應選擇消息攻擊下是存在性不可偽造的。2016年，湯永利等[14]給出了針對文獻[13]中新方案的一個偽造攻擊，結論表明第I類強攻擊者[10]能成功偽造任意用戶對任意消息的有效簽名，并基于橢圓曲線離散對數困難性假設提出了9個新的改進方案，聲稱其改進方案中的前兩種方案能夠抵抗第I類超級攻擊者[10]、第II類超級攻擊者[10]的攻擊，改進方案中的第3~9種方案能夠抵抗第I類強攻擊者[10]、第II類超級攻擊者的攻擊。

本文對湯永利等的9個無證書簽名方案[14]進行安全性分析后，發現其中的第1、2、5、8、9這5個無證書簽名方案不能抵抗替換公鑰攻擊，并且其中第5、8、9這3個方案即使不替換公鑰，攻擊者也可以利用用戶的原始公鑰對任意消息偽造出有效的簽名。分析結論表明，文獻[14]中的這5個簽名方案是不安全的。

2 預備知識

2.1 困難問題與安全假設

2.2 無證書簽名方案的形式化定義

（1）系統參數建立算法

（2）部分私鑰生成算法

（3）用戶秘密值生成算法

（4）用戶私鑰生成算法

（5）用戶公鑰生成算法

（6）簽名算法

（7）驗證算法

3 湯永利等給出的簽名方案

針對樊愛宛等方案[13]存在的安全漏洞，湯永利等人2016年在文獻[14]中基于橢圓曲線離散對數困難假設提出了一類改進的可證明安全的無證書簽名方案，具體描述如下。

（1）系統參數建立算法

（2）部分私鑰生成算法

（3）用戶秘密值生成算法

（4）用戶私鑰生成算法

（5）用戶公鑰生成算法

（6）簽名算法

（7）驗證算法

表1 簽名與驗證

4 替換公鑰攻擊

4.1 簽名方案1的攻擊

攻擊者Eve執行以下步驟即可成功偽造簽名：

4.2 其他簽名方案的攻擊

根據以上對簽名方案1的替換公鑰攻擊與分析可知，文獻[14]給出的簽名方案2、5、8、9都可以利用類似簽名方案1中的攻擊方法進行替換公鑰攻擊，具體的替換公鑰攻擊過程在此不再贅述。

4.3 替換公鑰攻擊原因分析

具有Rafael-Ricardo無證書一般模式特征的簽名方案，可以抵抗一般用戶的公鑰替換攻擊[15]。所以文獻[14]中給出的3、4、6、7方案可以抵抗前述的替換公鑰攻擊，具體證明過程可以參考文獻[15]。

5 其他類型的偽造攻擊

5.1 簽名方案5的攻擊

5.2 其他簽名方案的攻擊

根據以上對簽名方案5的偽造攻擊與分析可知，文獻[14]中給出的簽名方案8、9的驗證等式分別為

顯然這兩個簽名方案與文獻[14]中簽名方案5存在相同的安全漏洞，可以利用與4.1節中類似的偽造攻擊方法在不替換用戶公鑰的情況下，對任意選擇的消息進行偽造簽名，具體攻擊過程在此不再贅述。

5.3 攻擊原因分析

6 結束語

由于無證書簽名體制不存在密鑰托管問題，同時在驗證簽名過程中無須驗證簽名者公鑰的合法性，所以無證書公鑰密碼體制的研究受到了較高的關注。本文對文獻[14]中的9個無證書簽名方案進行安全性分析后，發現其中的5個方案不能抵抗替換公鑰攻擊，并且其中的3個簽名方案即使在不替換用戶公鑰的情況下，攻擊者也可以對任意選擇的消息偽造出有效的簽名，并給出了具體的攻擊方案。分析結論表明這5個無證書簽名方案是不安全的。

[1] AL-RIYAMI S S, PATERSON K G. Certificateless public key cryptography[C]//Advances in Cryptology-ASIACRYPT 2003. 2013: 452-473.

[2] SHAMIR A. Identity-based cryptosystems and signature schemes[C]// Advances in Cryptology-CRYPTO’84. 1985: 47-58.

[3] DIFFIE W, HELLMAN M E. New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22(6): 664-654.

[4] ISLAM S H, BISWAS G P. Provably secure and pairing-free certificateless digital signature scheme using elliptic curve cryptography[J]. International Journal of Computer Mathematics, 2013, 90(11): 2244-2258.

[5] FENG S R, MO J, FENG S R, et al. An efficient and provably secure certificateless short signature scheme[C]//International Conference on Computer Science & Electronics Engineering. 2013.

[6] GONG P, LI P. Further improvement of a certificateless signature scheme without pairing[J]. International Journal of Communication Systems, 2014, 27(10): 2083-2091.

[7] ISLAM S H, OBAIDAT M S. Design of provably secure and efficient certificateless blind signature scheme using bilinear pairing[J]. Security and Communication Networks, 2015, 8(18): 4319-4332.

[8] ALLAM A M, ALI I A, MAHGOUB S M. A provably secure certificateless organizational signature schemes[J]. International Journal of Communication Systems, 2017, 30(5): 1760-1768.

[9] KYUNG-AH S. A new certificateless signature scheme provably secure in the standard model[J]. IEEE Systems Journal, 2018:1-10.

[10] HUANG X, MU Y, SUSILO W, et al. Certificateless signature revisited[J]. Lecture Notes in Computer Science, 2007, 4586: 308-322.

[11] 王圣寶, 劉文浩, 謝琪. 無雙線性配對的無證書簽名方案[J]. 通信學報, 2012, 33(4): 93-98.

WANG S B, LIU W H, XIE Q. Certificateless signature scheme without bilinear pairings[J]. Journal on Communications, 2012, 33(4): 93-98.

[12] 王亞飛, 張睿哲. 強安全無對的無證書簽名方案[J]. 通信學報, 2013, 34(2): 94-99, 108.

WANG Y F, ZHANG R Z. Strongly secure certificateless signature scheme without pairings[J]. Journal on Communications, 2013, 34(2): 94-99, 108.

[13] 樊愛宛, 楊照鋒, 謝麗明. 強安全無證書簽名方案的安全性分析與改進[J]. 通信學報, 2014, 35(5): 118-123.

FAN A W, YANG Z F, XIE L M. Security analysis and improvement of strongly secure certificate less signature scheme[J]. Journal on Communications, 2014, 35(5): 118-123.

[14] 湯永利, 王菲菲, 葉青, 等. 改進的可證明安全無證書簽名方案[J].北京郵電大學學報, 2016, 39(1): 112-116.

TANG Y L, WANG F F, YE Q, et al. Improved provably secure certificateless signature scheme[J]. Journal of Beijing University of Posts and Telecommunications, 2016, 39(1): 112-116.

[15] RAFAEL C, RICARDO D. Two notes on the security of certificate- less signatures[C]//International Conference on Provable Security. Springer-verlag, 2007. 2007: 85-102.

Forgery attacks on several certificateless signature schemes

WANG Jing1，LI Zumeng2

1. Foundation Department, Guangzhou Information Engineering Vocational School, Guangzhou 510640, China 2. Computer Engineering Technical College(Artificial Intelligence College), Guangdong Polytechnic of Science and Technology, Zhuhai 519090, China

Since Al-Riyami and Paterson proposed the novel concept of certificateless cryptography and the first certificateless signature scheme in 2003, a lot of certificateless signature schemes were proposed one after another. Recently, Tang et al proposed nine certificateless signature schemes without bilinear pairing. Although they demonstrated that their schemes were unforgeable under the assumption of elliptic curve discrete logarithmic problem, it can be found that five of their schemes could not resist the public key substitution attack, the attacker could use the user's original public key to forge a valid signature for three of these schemes. The attack methods are to demonstrate that prove five certificateless signature schemes are insecure.

certificateless signature, elliptic curve, discrete logarithm problem, public key replacement attack

TP309.7

A

10.11959/j.issn.2096?109x.2020039

2019?05?09；

2019?07?29

李祖猛，zumengli@126.com

王菁, 李祖猛. 幾個無證書簽名方案的偽造攻擊[J]. 網絡與信息安全學報, 2020, 6(3): 108-112.

WANG J, LI Z M. Forgery attacks on several certificate lesssignature schemes[J]. Chinese Journal of Network and Information Security, 2020, 6(3): 108-112.

王菁（1983? ），女，山西運城人，碩士，主要研究方向為最優化理論與方法、網絡算法及其在通信網中的應用。

李祖猛（1984? ），男，山東臨清人，碩士，主要研究方向為密碼學與信息安全。