 Software Engineering and Applications 软件工程与应用, 2013, 2, 55-61 http://dx.doi.org/10.12677/sea.2013.23010 Published Online June 2013 (http://www.hanspub.org/journal/sea.html) Cryptanalysis of an Identity-Based Group-Oriented Signcryption Scheme in the Standard Model Lequn Mo1,2, Guoxiang Yao3, Feng Li1 1Department of Computer Science, Guangdong Communication Polytechnic, Guangzhou 2Management School, Jinan University, Guangzhou 3College of Information Science, Jinan University, Guangzhou Email: jason.mok.gz@gmail.com Recei ved: Ap r . 1st, 2013 revised: Apr. 15th, 2013; accepted: Apr. 24th, 2013 Copyright © 2013 Lequn Mo et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: Group-oriented signcryption is a very useful primitive in the network communication field, which simultaneously provides the functionalities of encryption and signature. Recently, Zhang, Xu, et al. [1] proposed an identity-based group-oriented signcryption scheme and claimed that their scheme is provably secure in a strengthened security model. Unfortunately, by giving concrete attacks, we indicate that this signcryption scheme is not secure under either choose ciphertext attack or choose message attack, in this strengthened security model. Keywords: Identity-Based; Group-Oriented; Signcryption; Choose Message Attack; CCA 标准模型下一种基于身份的面向群组签密方案的安全性分析 莫乐群 1,2，姚国祥 3，李 锋1 1广东交通职业技术学院计算机工程学院，广州 2暨南大学管理学院，广州 3暨南大学信息科学技术学院，广州 Email: jason.mok.gz@gmail.com 收稿日期：2013 年4月1日；修回日期：2013 年4月15 日；录用日期：2013 年4月24 日 摘 要：面向群组的签密方法在现今的网络通信中是一种很有效的数据安全保护手段，它可以在对信息进行个 人数字签名的同时对数据进行加密。本文针对 Zhang 和Xu 等人提出的一种基于身份的面向群组签密方案[1]进行 了安全分析，指出该方案存在严重的安全漏洞，并在标准模型下证明该方案无法抵抗择密文攻击以及选择消息 攻击的攻击。 关键词：基于身份；面向群组；签密；抗择密文攻击；选择消息攻击 1. 引言 在现今的网络通信中，经常会出现将同一份信息 向多个实体发送的情况，如何保证群体中一对多的数 据传输安全是一个很重要的研究课题，一种简单的方 式就是发送者分别使用各个接受者的公钥进行加密， 然后进行点对点传送，显然，这种方法在接收群组规 模较大时效率是非常低的，而且发送端的计算压力相 当大。 1997 年，Zheng[2]等人首次提出了签密的概念， 它指的是在同一个逻辑步骤内同时实现签名和加密 Copyright © 2013 Hanspub 55  标准模型下一种基于身份的面向群组签密方案的安全性分析 两项功能，是一种同时实现数据保密及信息认证的理 想方法。在 2001 年Boneh 和Franklin 等人利用双线 性对的特点提出了基于身份加密方案[3]之后，基于身 份的密码体制得到了迅速的发展和应用，将基于身份 密码学与签密进行结合的构造[4]是其中的一个发展方 向。2007 年，Duan 等人提出了首个多接收者的基于 身份签密方案[5]，他结合 Zheng 等人提出的多接收者 签密方案[6]与Bellare等人提出的多接收者公钥加密方 案[7]相结合，实现仅通过一个对运算就可向多个接收 者发送消息，随后出现了大量的基于身份的广播签密 方案[8-11]。Zhang 等人为了改善上述方案中出现的一些 问题，例如：签密前必须建立专门的接受群体组；必 须知道群体各成员的私钥；必须知道接受成员的身份 等等，利用双线性映射特点提出了一种基于身份的面 向群组签密方案[1]，在该方案中签密者只需对群身份 进行信息签密即可让所有接受成员通过各自的私钥 进行独立的解签密，另外其参数选择及加密长度可以 有效提高计算效率，是一种高效、便捷的安全通信方 案。然而，尽管Zhang 等人对所提出方案在基于 Gentry 等人[12]提出的标准模型下可证安全性进行了论证，但 我们发现该方案依然存在严重的安全漏洞，它在基于 身份选择密文攻击以及选择消息攻击下是不安全的， 并在标准模型下给出了具体的攻击方案。 本文组织如下：第 2节介绍作为基础知识的双线 性对和方案涉及的模型定义；第3节是对基于身份的 面向群组签密方案的回顾；第4节在安全模型下分别 给出基于身份选择密文攻击的安全性分析以及基于 选择消息攻击安全性分析；第5节是结束语；第6节 是致谢。 2. 预备知识 2.1. 双线性映射(Bilinear Mapping) 设G和G为2个大素数阶p的循环群，存在 1 2 : 一个双线性映射 eG ，满足以下特性： 11 2 G G 1 ,, 双线性： , 12 p g gG 12 1 ,, ab eggeg g abZ ，有 2 ab ； 非退化性：存在 121 , g gG使得 2 ,1 G g，其 中2 1G为群组 2 G的标识； 12 eg 可计算性：存在一个有效算法计算 12 ,eg g其中 121 , g gG 。 2.2. 困难问题及其假设 定义 1：q-ABDHE (augmented bilinear Diffie-Hell manexponent assumption)困难问题[12]：设 和 为 2个大素数阶 p的循环群，存在一个双线性映射 1 G2 G 11 2 :eG GG 121 ,，给定生成元 g gG22q及 个 元素 222 2 112 22222 ,,,,,,, ,, qq q q ggg ggggg 22 1q G 1 12 ,q eg g 1 G2 11 2 :G G 121 , ，则计算 困难。 定义 2：q-SDH (q-S trong Diffie-Hellm anassumption) 困难问题[13]：设和 G为2个大素数阶p的循环群， 存在一个双线性映射 eG ，给 定生成 元 g gG 2q 个元素 及 22 211222 ,,,,, qq gggggG 21 g g ， ，其中 则计算元组 1 1 ,r rg 困难，其中 p r。 Z 0, 1M 2.3. 基于身份的面向群组签密方案[1]的标准模型 在本章节，我们对基于身份的面向群组签密方案 [1](以下简称 IBGSC 方案)的签密模型及安全模型的定 义进行说明。 2.3.1. 签密模型的定义 IBGSC 方案由以下四个模块组成： Setup (k)：系统建立，输入一个安全参数 k，生 成 系统的运行参数 params 及系统密钥 master-key。算法 由PKG 运行，所生成的系统参数params 包含消息空 间 0, 1 ID G 被公开，而系统密钥 master-key 则被系 统保存。 KeyGen (params, master-key, GID, ID)：私钥提取， 输入系统参数 params、系统密钥 master-key、群组身 份 0, 1以及该群组的成员身份 ID ，其 中 I D G以及 ID均为任意的字符串，算法由PKG运行 并计算返回群组成员对应的私钥 I D d mM 。 Signcrypt (params, m, di ,Gj)：签密，输入系统参 数params、消息原文 、消息接受者所在的群组 身份 j G及发送者私钥，算法计算密文 i d Signacrypt, , ij md G 并广播给接收群组中的所有 成员。 Copyright © 2013 Hanspub 56  标准模型下一种基于身份的面向群组签密方案的安全性分析 Unsigncrypt (params, m, Gi, di)：解签密，输入系 统参数 params，密文 及密文接受者所在的群组身份 及私钥 ，计算得到原文 i i Un ncrypt G d , ,sig I DID dG m m M ，若满足正确性约束条件 返回 ，否则输出⊥。 2.3.2. 安全模型 IBGSC 方案的安全模型由以下两个模型组成： 1) 基于身份选择密文匿名不可区分安全模型 (ANON-IND-IBGSC-CCA) 选择密文匿名不可区分是指敌手不能区分同一 密文加密者的身份，即敌手不能判断同一个密文是由 所选择的特定身份加密还是由某一随机选择的身份 加密的，也就是说密文不会泄露接受者的身份。 Game 1：一个IBGSC方案在以下挑战者 C和敌 手A的游戏中，若敌手A不能在多项式时间内以一个 不可忽略的概率 赢得游戏，则该方案满足基于身份 选择密文匿名不可区分安全。 Setup：挑战者C输入一个特定安全参数k运行算 法，并将所产生的系统参数 params 给敌手，同时 保密系统密钥 master-key。 Phase 1：在该阶段敌手发起询问 1,, m qq，其 中 为以下询问： i q ① KeyGen询问，敌手 A 发送群组消息 I D G及成 员消息 ID 给挑战者 C，C运行 KeyGen 算法，并将产 生的对应 I D G的私钥 I D d i q 1 A d 返回给 A 。这些询问是适应性 的，即每个询问都可以依赖于 C对在此之前询问 的响应。 1 ,,qi q ② Unsigcrypt 询问，敌手A将用私钥 签密的 密文 及接受群组信息 I D G发送给挑战者C，C选择 身份 B I D计算 , B BI GD en IDd pt , KeyG Unsigncry , ，并将解密结果 B ID dG 返回给 A，如果 是一个不合 法的密文，输出结果为符号⊥。 Challenge：敌 手A结束询问后，发送所要挑战的2 个等长的明文01 , M MM，身份0 I D G及1 I D G，并 且0 I D G及1 I D G不能在任何 KeyGen 询问中出现过。 挑战者 C随机选择比特值 ,0,1bc，并计算密文 Sig nacrypt , , cAb ，并将mdG 返回给敌手 A。 Guess：继续重复 Phase 1，但不能做关于 0 I D G及1 I D G 的私钥提取询问及签密密文 的解签密询问，最 后，敌手 A猜测结果 ,0,1bc 。如果 bb ,cc 则敌手赢得游戏。 2) 自适应选择消息存在性不可伪造安全模型 (EUF-IBGSC-CMA) 自适应选择消息存在性不可伪造是指抵抗适应性 选择消息攻击下的存在性伪造安全，即若除了签名之 外的任何消息的都是伪造的，则不会有任何有效的输 出。 Game 2：一个IBGSC方案在以下挑战者 C和敌 手A的游戏中，若敌手A不能在多项式时间内以一个 不可忽略的概率 赢得游戏，则该方案是满足自适应 选择消息攻击下存在性不可伪造的。 Setup：挑战者C输入一个特定安全参数k运行算 法，并将所产生的系统参数 params 给敌手，同时 保密系统密钥 master-key。 Phase 1：在该阶段敌手发起询问 1,, m qq，其 中 为以下询问： i q ① KeyGen询问，敌手 A 发送群组消息 I D G及成 员消息 ID 给挑战者 C，C运行 KeyGen 算法，并将产 生的对应 I D G的私钥 I D d 11 ,, i qq 返回给 A.这些询问是适应性 的，即每个询问qi都可以依赖于 C对在此之前询问 A 的响应。 ② Sigcrypt询问，敌手A 发送签密者身份 I D与 明文信息 m给挑战者 C，C运行 Sigcrypt 计算 ,A AAID dKeyGenGID及 Signacrypt ,, AA ID ID mdG ，并将签密结果 返回给 A 。 Fake：继续重复 Phase 1至询问结束，最后，敌手 发送签密 (签密者密钥 B d没有被询问过，密文也 没有在签密询问中出现过)给挑战者 C，如果解签 密结果 Unsigncrypt ,, B ID dG 不为符号⊥，则称 敌手赢得游戏。 3.基于身份的面向群组签密方案介绍 本章节，我们将回顾基于身份的面向群组签密方 案的各个算法。 3.1. 各算法回顾 基于身份的面向群组签密方案的具体实现，主要 包含以下 4个算法： Copyright © 2013 Hanspub 57  标准模型下一种基于身份的面向群组签密方案的安全性分析 Copyright © 2013 Hanspub 58 11 2 G G Setup (k)：系统建立，设 G和G为2个大素数阶 p的循环群，并存在一个双线性映射 eG， PKG 随机选择生成元 T : , g hG Z ，令无碰撞的散列函数 H满足 ，然后PKG 随机选择系统密钥 :0,1H key p masker - p Z ，计算 1 g g G，并公布系统 参数 1 p arams, , g gh。 KeyGen (params, master-key, GID, ID)：私钥提取， PKG 接收群组身份 I D G和成员个体身份ID，随机选择 I Dp rZ ，并计算 ，然后输出个体私钥 ID ID RrHID , I DIDID drh ，其中 1ID ID ID HG R hhg 。该算法 可以在任何时间执行，以适应发送/接收群组成员的动 态变化。不失一般性，设群组 I D A G成员 I D为消息发 送者 A，成 员 1, , i Bin ID i B 为接收者 ，他们的私钥分 别为： 1 1 1 1 ,, , ,, , ID ID AA A ID ID BB Bii i i ii HG HG rH ID R A AA HG HG rHID R B BB drh rhgrhg h rhgrhg mM ii AA BB dr Signcrypt (params, m,di ,Gi)：签密，签密者A为将明文消息 发送给接收群组 I D G中的所有成员， 随机选择 p s Z，并如下计算签密密文 ,,,,uvw ,, m AA r ： 1,,,, ID ss sH GH s uggvegg wmeghh Unsigncrypt (params, m, Gi, di)：解签密，信息接 受群组 I D G 1, , i Bin 成员 要解密签密密文 ID ,, ,,uvw ，只需计算 , B B ii rHID euhv , H m HIDHmHm vw m eu m成立，输出信息 ，否则输出⊥。 3.2 算法正确性[1] i B mw 即 可，若约束条件验证等式 通过下面的推导可以得出签密方案是正确的： 1 ,, , ,,, ,, ,, ,,,, ID ID AA AA AAA AA Hm sHG sH GH mR sHID A Hm RHmHmRHm sss sH msR H msH msH mr HID sH mr H IDsH m H m HIDHmHmHm euegghe ghg eg hgeg hegg egh eggegh egg eu eggmeghm eu v w IBGSC-CCA)下是语义安全的，但实际上却存在敌手 A 可以通过以下方式一直赢得 Gam e 1： 4.对Zhang 和Xu 等人方案的安全性分析 Zhang和Xu 等人认为他们所提出的方案对于 身份选择密文攻击以及选择消息攻击下是可证安全 的，但在本章节中，我们将会在标准模型下证明这两 种攻击依然可行。 Setup：挑战者 C输入一个特定安全参数 k运行算 法，将所产生的系统参数params 给敌手A，同时 保密系统密钥 master-key。 Phase 1：敌手A不做任何询问。 Challenge：敌 手A结束询问后，发送所要挑战的2 个等长的明文 01 , 4.1. 基于身份选择密文攻击的安全性分析 M MM ，身份 0 I D G及1 I D G，并 且0 I D G及1 I D G不能在任何 KeyGen 询问中出现过。 挑战者 C随机选择比特值 ,0,1，并计算密文 Zhang 和Xu 等人认为他们所提出的方案在基于 身份选择密文匿名不可区分安全模型(ANONIND- bc  标准模型下一种基于身份的面向群组签密方案的安全性分析 Signacryp tmd ,, ,,uvw , , cAb G，并将 返回给敌手 A，其中 ,,,,,, ss H m AA vegg wmeghhr 1ID sH G s ugg Guess ：敌手A随机选择 p s Z 构造密文 ,,uv ,,w ,,uv 及,,w ，其中： 1 11 00 , ,, ,. ,, ID ID ssH G ssHG sss ss ss sssss ss AA uu ggg vv eggwwMmeghM r 11 01 ,Hm ss s s ww M megh Mh 构造完成后，敌手 A发出关于 及 的 Unsigcrypt 询问，由于 且 C , 所以，挑战者 首先根据公式 A A rH ID A mweuhv 进行解签密， 可得 的解签密明文为： 1 1 0 ,, , ,,, , AA A ID A AA A rH ID A ssss r HID ssH GR ss HID ssssssr HIDss r H ID ss ss mw mM eeghgegg mM eegheggeggmM 1 0 1 0 ,eu hv gh gh 同理， 的解签密明文为： 1 1 ,A rHID ss A mw euhvmM C , 然后，挑战者 会根据约束条件 H m HIDHmHm eu vwm 0 mM 进行检验，检验结果如下： , H m A mm h m 并且1) 若 ，则 可以通 过下面约束条件的检验： , ,, , AA Hm HIDHm ssHmr H IDssHm H mHmHm eu vw eu eggmeghmm H 2) 若，则 1 Mm,m A h mm 并且 m通过下面约束条件的检验： 可以 , ,, , A Hm HIDHm Hm Hm ssHm rHIDssHm H m eu vw eggm eghmm eu 所以对于敌手 A的两个解签密请求 , ，挑 战者 C将会返回结果 ,m或者 ,m ，则 敌手A可 以根据解签密结果猜测出 0, 1 cc mm c，使得 。 然后敌手 A再次构造签密密文 ,, ,,uvw 及 ,, ,,uvw ，其中： 构造完成后，敌手 A再次发出关于 及 的解 0 01 ,,,, ID ID ID sHG sH GsH G sss 1 11 , ,, , , , ID ID ID s ss sss ss Hm AA sHG sH GsH G sss gg wwegh meghegh megh hr uugggg g ss ss uugggg g vveggeggegg eggg e Copyright © 2013 Hanspub 59  标准模型下一种基于身份的面向群组签密方案的安全性分析 签密询问，由于 且 ,AA rH ID A uhv 所以，挑战者 C首 先根据公式 进行解签密： mwe 1) 若0 I DID G，则 并且可得 G 1ID ID ssHG ssHG ss uggg 的解 签密明文： 1 ,, , AA A ID A rHID A ssss rHID ss HGRHID mw hv meghe ghgeggm ,eu 这里显然 , H m HIDHmHm eu vwm 1 2) 若 I DID GG 1ID ssH G ss ugg ，则 并且可得 ID ss HG g 的 解签密明文： 1 , ,,, A A ID A rH ID A ssssrHID ss HGRHID mweuhv he ghgeggm meg 这里显然 ,HIDHm Hm H m eu vwm 所以对于敌手 A的两个解签密请求 , ，挑 战者 C将会返回结果 ,m或者 ,m，则敌 手A可 以根据解签密结果猜测出 0, 1bbb GG ，使得 。 综上，敌手 A将赢得 Game 1。 4.2. 选择消息攻击的安全性分析 Zhang 和Xu 等人认为他们所提出的方案在自适 应选择消息存在性不可伪造安全模型(EUF-IBG- SC-CMA)下是语义安全的，但实际上却存在敌手 A可 以通过以下方式一直赢得Game 2： Setup：挑战者C输入一个特定安全参数k运行算 法，并将所产生的系统参数params 给敌手 A，同 时保密系统密钥 master-key。 Phase 1：敌手 A做一次 KeyGen询问及关于明文信 息mM 的Sigcrypt 询问，得到私钥 1 ,, A R AA A A drhrhg ID HG 及签密密文 ,, ,,wuv ，其中： ,,,,,, ID 1 s s GH m AA vegg wmeghhr sH s ugg Guess：敌手A进行 KeyGen 询问,得到 ,, ,,uvw p r Z 构造密文 1 ,, ID BHG R BBB B drhrhg ， 并随机选择 ，其 中： 1 , , , ID ID srH G srH G rsr sr r sr rr Hm BB uu ggg vv egg ww megh hr 构造完成后，敌手A发出关于 的解签密询问， 由于 , 所以，挑战者 C首先根据公式 A B rH ID B mweuhv 进行解签密，可得 的解签密 明文为： 1 , ,,, AB BB ID BID rH ID B srsr rHID srHGRr HG mweuhv megh eghgeggm r Copyright © 2013 Hanspub 60  标准模型下一种基于身份的面向群组签密方案的安全性分析 对于约束条件 , H m HID eu v HmHm w m 检验，显然有： ,, , ,, BB B ID BID srHmr H IDsrH m Hm Hm srR sr srHG , , Hm HIDHm H m H mHm eu vw m RHG eu eggmegh eghgegg megh r m r m 所以挑战者C将返回明文给敌手A，并且 。 综上，根据安全模型，敌手 A将会赢得 Game 2。 综合上述在标准模型下对两个安全模型进行挑战 的结果，敌手可以轻易赢得 Game，该面向群组的签 密方案是不安全的，并由于安全模型已经被攻破，所 以也已没有改进方案的必要了，除非是提出一个完全 全新的方案。 5. 结束语 本文中，我们指出了Zhang 和Xu 等人所提出的 基于身份的面向群组签密方案存在严重的安全隐患， 他们对于基于身份选择密文攻击以及选择消息攻击 是不安全的。根据该方案的所提出的安全模型，我们 还给出了具体的攻击方案。 6. 致谢 这里，我们要感谢各位审稿专家认真的审阅及各 种帮助性的建议。本文获得了国家自然科学基金项目 (61272415 ，61272413 ，61133014) ，广东省自然科学 基金项目(S2011010002708)，广东省科技计划项目 (2010A011200038，2011B090400324)，广东省工程研 究中心专项(GCZX-A1103)，广州市科技计划项目 (2011J4300047)的资助。 参考文献 (References) [1] 张波, 徐秋亮. 基于身份的面向群组签密方案[J]. 通信学报, 2009, 30(11): 23-28. [2] Y. L. Zheng. Digital signcryption or how to achieve cost (signature & encryption) << cost (signature) + cost (encryption ). Lecture Notes in Computer Science 1294, Berlin: Springer- Verlag, 1997: 165-179. [3] D. Boneh, M. Franklin. Identity based encryption from the weilpairing. Lecture Notes in Computer Science 2139, Berlin: Springer-Verlag, 2001: 213-229. [4] J. Malone. Identity based Signcryption Cryptology ePrint Archive. Report 2002/098, 2002. [5] S. S. Duan, Z. F. Cao. Efficient and provably secure multi- receiveridentity-based signcryption. ACISP 2006. Lecture Notes in Computer Science 4058, Berlin: Springer-Verlag, 2006: 195- 206. [6] Y. L. Zheng. Signcryption and its applications in efficient public keysolutions. ISW 1997. Lecture Notes in Computer Science 1396, Berlin: Springer-Verlag, 1998: 291-312. [7] M. Bellare, A. Boldyreva and S. Micali. Public-key encryption ina multi-user setting: Security proofs and improvements. Advancesin Cryptology-EUROCRYPT 2000. Lecture Notes in Computer Science 1807, Berlin: Springer-Verlag, 2000: 259- 274. [8] Y. Yu, B. Yang, X. Y. Huang, et al. Efficient identity-based signcryptionscheme for multiple receivers. ATC 2007. Lecture Notes in Computer Science 4610. Berlin: Springer-Verlag, 2007: 13-21. [9] M. J. Bohio, A. Miri. An authenticated broadcasting scheme for wirelessad hoc network. 2nd Annual Conference on Com- munication Networks and Services Research (CNSR). 2004: 69-74. [10] Y. Mu, W. Susilo and Y. X. Lin. Identity-based authenticated broadcast encryption and distributed authenticated encryption. Advances in Computer Science—ASIAN 2004: Proceedings of the 9th Asian Computing Science Conference. Lecture Notes in Computer Science 3321. Berlin: Springer-Verlag, 2004: 169- 181. [11] F. G. Li, X. G. Xin and Y. P. Hu. Identity based broadcast signcryption. Computer Standards and Interfaces, 2008, 30(1-2): 89-94. Copyright © 2013 Hanspub 61 |