对一种多重密钥共享认证方案的分析和改进

1、 对一种多重密钥共享认证方案的分析和改进王贵林 卿斯汉Infocomm Security Department, Institute for Infocomm Research21 Heng Mui Keng Terrace, Singapore 119613中国科学院信息安全技术工程研究中心 北京 100080Email: wangguilin, qsihan摘 要: 在(t, n)密钥共享方案中, 密钥管理者将一个秘密密钥分成 n 个子密钥, 然后让n 个成员中的每个成员保存一个子密钥. 当需要恢复秘密密钥时, 任意t 个成员拿出他们持有的子密钥后, 就可按既定的公开算法恢复出所需密钥.

2、而多重密钥共享使得密钥管理者可以安全且有效地共享多个密钥. 最近, Shi 给出了一种高效率的多重密钥共享认证方案. 在他的方案中, 不仅成员持有的子密钥能重复使用, 而且管理者分发的子秘钥和成员提供的影子子秘钥都是可认证的. 本文对Shi 方案的安全性进行了分析. 首先指出该方案的一个设计错误, 然后给出两个攻击以表明该方案中的子密钥和影子子秘钥认证方法实际上都是不安全的. 准确地说, 利用我们的攻击, 不诚实的管理者可以将假的子秘钥分发给成员; 而不良成员可以很容易地伪造假的但能满足认证等式的影子子密钥, 从而欺骗诚实成员, 使得诚实成员误以为他们恢复出的密钥是正确的. 另外, 我们还给出

3、了改进方法以避免上述设计错误和攻击.关键词: 密钥共享；多重密钥共享；密码学; 信息安全Analysis and Improvement of a Multisecret Sharing Authenticating SchemeGuilin Wang Sihan QingInfocomm Security Department, Institute for Infocomm Research21 Heng Mui Keng Terrace, Singapore 119613Engineering Research Center for Information Security Technol

4、ogy,Chinese Academy of Sciences, Beijing 100080Abstract: In a ( t, n) secret sharing scheme, a dealer splits a secret into n shares and sends ashare to each of n participants. If necessary, any t members can provide their secret sharestogether and recover the secret by using a publicly specified alg

5、orithm. Multisecret sharingschemes allow a dealer to share multiple secrets among a group of participants securely andefficiently. In recent, Shi proposed an efficient multisecret sharing authenticating scheme. Inhis scheme, not only the shares held by the participants are reusable, but also the sha

6、resdistributed by the dealer and the shadow shares provided by the participants are verifiable.This paper analyzes the security of Shis scheme. We first point out a design error in hisscheme, and then demonstrate an attack to show that both of his share-authenticating andshadow-key-authenticating me

7、thods are insecure. Specifically, using our attacks, a dishonestdealer can distribute false shares to participants, and malicious participants can easily forgefalse shadow shares such that the authenticating equality is satisfied. The result is that honestparticipants will be cheated and misled to b

8、elieve that the recovered secret is correct. Inaddition, improvements are provided to avoid the identified design error and attacks.Keywords: secret sharing, multisecret sharing, cryptography, information security.1 1 引 言密钥共享(Secret Sharing)是一种分发、保存、恢复秘密密钥(或其它秘密信息)的方法：密钥管理者将秘密密钥拆分成一系列相互关联的秘密信息(称为子密钥

9、)，然后将子密钥分发给某群体中的各个成员；使得某些小组(授权集)中的各成员拿出他们的子密钥后，就可利用既定的方法恢复该秘密密钥，而其他小组(非授权集)则无法恢复该密钥。密钥共享也称为密钥分存, 秘密共享或秘密分存。在现实环境下的信息系统中使用密钥共享，可以防止系统密钥的遗失、损坏和来自敌方的攻击，减小密钥持有者(个人或服务器)的责任，同时还可以降低敌手破译密钥的成功率。密钥共享首先由著名密码学家Shamir 1和Blakley 2提出。Shamir 的方案简单、实用，得到了广泛的应用和重视。Shamir 的方案属于(t, n) 门限密钥共享方案，即任何不少于t 个成员的小组都可以恢复秘密密钥。

10、虽然Shamir 门限方案是完善的密钥共享，但该方案有两个问题3,4：(1) 管理者的诚实性问题：为防止管理者将假的子密钥分发给部分或全部成员，各成员如何验证管理者发送来的子密钥是正确的(即与其他密钥一致，从而可用来恢复秘密密钥)？(2) 成员的诚实性问题：在恢复秘密密钥阶段，若某些恶意成员提供了假的子密钥，其他成员如何鉴别？多重密钥共享研究的主要内容是密钥管理者如何安全且有效地共享多个密钥5,6,7. 最近, Shi在文献8中给出了一种高效率的多重密钥共享认证方案. 在他的方案中, 不仅密钥管理者能够方便地共享多个密钥, 成员拥有的子密钥可以重复使用, 而且管理者分发的子秘钥和成员提供的影子

11、子秘钥都是可认证的. 本文对Shi 方案的安全性进行分析, 首先指出该方案的一个设计错误,然后给出两个攻击以表明该方案中所给出的子密钥和影子子秘钥认证方法实际上都是不安全的.准确地说, 利用我们的攻击, 不诚实的管理者可以将假的子秘钥分发给成员; 而不良成员可以很容易地伪造假的但能满足认证等式的影子子密钥, 从而欺骗诚实成员, 使得诚实成员误以为他们恢复出的密钥是正确的. 另外, 我们还给出了改进方法以避免上述设计错误和攻击.文章的组织如下：第 2 节回顾Shi 的多重密钥共享认证方案；第 3 节给出安全性分析并提出改进方法以避免我们所发现的设计错误和攻击.2 Shi 方案简介Shi 的多重密

12、钥共享认证方案 分四个阶段: 初始化、子密钥的生成、密钥分存和密钥恢复.8前三个阶段由密钥管理者完成, 而第四个阶段由n 个成员中的任意t 个合作完成.(1) 初始化阶段: 密钥的管理者D 拥有一个电子公告牌 NB, 用于公开信息、存储和认证影子子密钥.公告牌NB 中的内容每个系统成员都可读取, 但只有管理者D 可以修改、删除或添加.D 选取两个安全大素数 p = 2p +1 和q = 2q +1,其中 p 和q 也是素数; 置 N = pq ,R = pq ;选取Z 的R 阶生成元g ; 产生 RSA 密钥对(e,d) 使得ed =1 mod (N) . 最后, D 在 NB 中公N开(N,

13、g,e), 将(d,R) 作为秘密保存, 同时删除素数 p 和q .(2)子密钥的生成阶段: 假定S =S |i =1, 2,L,m是要共享的密钥集, 而共享S 中m 个密钥i的n 个成员所构成的集合是G =U | j A =1, 2,L, n,ID 是成员U 的标志符(一个公开的数jjj值). 管理者D 随机选取一个(t 1) 阶的多项式 f (x) = a + a x +L+ a xt 1 Z x(即随机选取01t1R各个系数a 使得a Z , k = 0,1,L, t 1.). 随后, D 在NB 中公开对各系数a 的承诺V :kkRkkV = g mod N ，k = 0,1,L, t

14、 1.(1)akk另外, 对每个 j1, 2,L, n,D 计算如下的x 和y :jjx = f (ID ) P mod R, y = g mod N .(2)1xjjjjj2 其中的P = (ID ID ) mod R .jjkkA j这之后, 管理者D 经安全信道将g mod N, x 发送给U ,而将y 作为公开信息放入NB.Pjjjj为了检验管理者是否进行了欺骗, U 可以根据下面的子密钥认证等式来验证x 的正确性:jjt1(g ) (V ) mod N.(3)PxIDkjjkjk=0(3)密钥分存阶段: 为了将密钥集S 中的m 个密钥在n 个成员中分存, D 选取2m 个随机数r Z

15、 ,T Z ,i =1, 2,L, m . 然后, 针对每个许可证T ,按下面的式子计算一个凭证 C 和一iRiNiih :个变换值iC = g (T )mod N,2d+r +1(4)(5)d+riiiih = (T S ) (C ) mod N.aa0iiii0最后, D 把所有四元对r ,T ,C ,h 放入NB.iiii(4) 密钥恢复阶段: 若有t 个成员U (jw, w A 且| w|= t )想恢复密钥S S, 则每个成ji员U w先从 NB 中获得r ,T ,C ,h , 然后利用他的秘密子密钥x 按如下公式计算影子子密钥jiiiijA 和相应的认证信息B :ijijA = (

16、T )x mod N,B = (C )x mod N.(6)ijijijij随后, U 将(A , B ) 送给w中的其他成员. 利用NB 中的公开信息y ,w中的任何成员都可jijijj用下面的影子子密钥认证等式来验证(A , B ) 的有效性:ijij(B ) (y ) (A ) mod N .2+e(r +1)(7)(8)eer 1ijjiiji若t 个(A , B ) 对都被认证, 则w 中的成员可利用下式恢复出密钥S :iijijS = (A ) h (B ) mod N.iijjiijjjwjw在整数环 计算, 指标集A =1, 2, , n .):Z上式中的 由下式给出(注:Lj

17、j( ID ) (ID ID )=.(9)jkjkkw jkAw3 Shi 方案的安全性分析及改进文献8声称Shi方案不仅可以防止密钥管理者分发假的子密钥, 还可以防止不良成员在密钥恢复阶段提供假的影子子密钥. 进一步, 文献还得出结论: Shi 方案的安全性取决于整数因子分解和离散对数两大数学难题的困难性. 但我们发现, 在Shi 方案中, 无论是管理者还是成员都可以轻而易举地进行作弊, 以欺骗诚实成员. 换句话说, 子密钥认证等式(3)和影子子密钥认证等式(7)实际上都是不安全的. 另外, 我们还发现, 即使管理者和所有成员都是诚实的, t 个成员仍然可能无法按(8)式恢复出正确的密钥.

18、这说明Shi 方案有设计错误, 原因在于: 管理者不能将Ti取为Z 中的随机数, 而应将其取为循环群 中的随机数. 下面分三个小节来详细分析这些安N全缺陷,并给出改进.3.1 Shi 方案的设计错误利用Lagrange 插值公式, Shi 方案中证明了如下结果:a = (x ) modR .(10)0jjjw由此, 文献8认为下面的两个式子成立, 从而根据(5)式即知密钥恢复公式(8)成立:(A ) = (T ) = (T ) mod N.ja(x )(11)(12)jijjijwi0jw(B ) = (C )(x ) = (C ) mod N.j jajwijjii0jw3 我们发现, 虽然

19、(10)式是正确的, 但对于随机选取的 T Z ,(11)式和(12)式却不一定成iN x立.为方便起见, 记a = . 也就是说,a 是所x ( jw) 作为整数相加的结果. 那jjjjjw么,由(10)式成立知, 存在整数l 使得a = l R + a .所以我们有(T ) = (T )alR+a0mod N.这说明,0ii(11)式成立当且仅仅当(T )l R =1 mod N. 由于gcd(T ,N) 1的概率可以忽略, 所以可以认为随ii. 但T 的阶可以是1, 2, p, q 2p, 2q, pq 2pq中的任何一个(参考文献9中的,和机数T Z*iNiProposition 1

20、). 所以当T 的阶含有因子 2 而l 又是奇数时, 等式(T ) =1 mod N不成立. 在这lRii种情况下, 即使所有成员诚实地拿出他们所持有的影子子密钥, 也无法按(8)式恢复出密钥 S .i改进的方法很简单, 密钥管理者随机选取一个数 t Z , 然后置T = g mod N 即可. 经过这一*tiRii改进后, T 的阶是R (= pq ), 于是有T = (g ) =1 mod N , 从而(11)式成立. 同理, 由(4)R R tiii式知C=1 mod N , 所以(12)式也成立.Ri3.2 密钥管理者的欺骗文献8声称: 只要Shi 方案中的密钥管理者D 给成员U 分发

21、假的子密钥x x , U 就可jjjj以通过子密钥认证等式(3)发现D 的欺骗行为. 实际上D 仍可欺骗各个成员, 方法如下. D 先按(2)式计算出x 和P , 然后选取随机数xZ 并计算如下的x , y 和P :*jjRjjjx = x x mod R , y = g mod N , P = P x mod R .(13)xj1jjjjj这之后, 管理者D 将g mod N, x 安全地发送给U , 而将y 作为公开信息放入NB. 容易看Pjjjj出, 由于P x = P x 1x x mod R = P x mod R , 所以g mod N, x 满足(3)式, 故U 不能检Pjjjj

22、jjjjj验出他收到的x 实际是假的子密钥. 这样, 当某个或某些持有假子密钥的成员参加密钥恢复时,j即使所有人都诚实地按照(6)式计算(A , B ) , 他们按(8)式恢复出来的密钥将不是S 而是某个假ijijiS . 其原因在于, 此时(10)式不再成立(因为某些x 被替换成了x ).下面的方法可以克服上述管理者欺骗问题. D 仍按(2)式计算 x 和 y , 并将x 秘密传送给的密钥ijjjjjU 而将y 公开. U 在接到x 后, 先在整数环中计算P =(ID ID ) , 然后检查:jjjjjjkkA jt1y g mod N, (g ) (V ) mod N.(14)xxPIDk

23、jjjjkjk=0若上面的两个恒等式都成立, 则认为D 是诚实的, 否则U 提出抱怨.j3.3 成员的欺骗文献8声称: 不良成员U 想要提供假的影子子密钥 A 和相应的认证信息B 使得(A , B )jijijijij满足影子子密钥认证等式(7), 取决于他知道 d 或R , 而要获取d 或R 就得求解因子分解问题.但我们发现, U 根本不必知道 d 或 R 的值, 更不必分解 N , 就可以轻松地伪造一对假的j(A , B ) 使得(7)式满足. 方法如下. U 首先按(6)式计算出正确的(A , B ) , 然后选取一个随机ijijjijij数r Z , 并按下式计算(A , B ) :N

24、ijijA = A r mod N, B = B rmod N.2+e(r +1)(15)(16)eijijijiji由于(A , B ) 满足(7)式, 因此我们有ijij(B ) = (B ) (r)2+e(r +1) ei= (y ) (A ) (r )2+e(r +1) e 2+e(r +1)er 1jiijii= (y ) (A r )er 1e 2+e(r +1)jiiji= (y ) (A )mod N.2+e(r +1)er 1jiiji这说明U 按(15)式伪造出的 (A , B ) 也满足影子子密钥认证等式(7). 所以当 U 提供了假的jijijj(A , B ) 时,

25、其他合作者无法根据(7)式检查出U 是作弊者. 由此导致的结果是, 诚实成员恢复ijijj4 出的是假的密钥S . 而利用诚实成员提供的正确的影子子密钥和自己的影子子密钥(A , B ) , 不iijij良成员U 却可以恢复出正的密钥S .ji现在, 我们可以给出一个非交互式的知识证明协议, 以确保不良成员U 无法作弊.我们所给j出的协议使得U 能向其他成员证明: 他知道一个秘密x 满足以下三个离散对数等式, 但不泄漏jjx 的值到底是多少:jlog y = log A = log B (= x ) .(17)giTijCijjii先引入几个记号. 记l =| R | , 即g 的阶R 是一l

26、 比特长的整数(若取N 为 1024 比特长的整gg数, 则l =| R |=1022.).假设安全参数k 是 Hash 函数的输出长度, 而 控制统计零知识证明的紧g度(一般可取k =160, = 9/8 .). 又设H() 是一公开的安全 Hash 函数H(): 0, 1* 0, 1k .定义 1. 一个满足 c H(g |T |C | y | A | B | g ycij |T sij Acij |Csij Bcij | M ) 的二元对sijiijijijijjiijiij(c ,s )0, 1 0 ,1对称为三个离散对数log y , log A 和log B 相等的、依赖于消k(l

27、 +k)+1ij ijggiTijCijii息M 的知识签名(Signature of Knowledge ).对于知道秘密x 的成员U , 他可以先选取一个随机数t 0 ,1, 然后按如下公式计算(l +k)jjg出知识签名 (c ,s ) :c = H(g |T |C | y | A | B | g y |T A |C B | M ) s = t c x .,cijjsijcijsijcijsij ijijiijijijijiijiijijijj这里的s 是在整数环Z 中计算的. 容易验证, 如此产生的(c ,s ) 满足定义 1. 另外, (18)式中ijij ij的消息M 可以包含产生

28、知识签名的日期, 时间, 要恢复密钥的S 的序列号等, 甚至也可以将Mi取为空消息.实际上, 上述的知识协议只是文献9中Definition 5 的简单推广. 采用文献9, 10的记号, 可以将这一知识签名协议简记为SPK(x ): y = g A = T B = C (M )xxi.(18)xjjjjjijiij根据文献9, 10, 11 的研究结果, 在强 RSA 假设下, 上述知识签名协议在随机预言模型下(the random oracle model) 是安全的, 即该协议既是可模拟的(simulatable), 又是对于适应性选择12消息攻击存在性不可伪造的(existentiall

29、y unforgeable against adaptive chosen message attacks). 这说明, 对于不知道秘密x 的攻击者, 即使他知道U 所产生的多个知识签名对, 他能产生新的、满jj足定义 1 的知识签名的成功概率是可以忽略的. 同时, 对于不满足等式(17)的对(A , B ) , U 想ijijj要产生一个知识签名对(c ,s ) 满足定义 1 的概率也是可以忽略的. 也就是说, 在我们给出的上ij ij述影子子秘钥认证协议中, 任何一个提供了假的影子子秘钥的成员, 在现实中一定会被其他成员(验证者)发现.事实上, 知识签名是一种具有广泛应用范围的知识证明协议

30、, 可用于构造可公开可验证密钥共享13,14, 群签名9,10, 门限签名 以及门限不可否认签名方案 等.1516参考文献12Shamir A. How to share a secret. Communications of the ACM, 1979, 22(11): 612-613.Blakley G R. Safeguarding Cryptographic Keys. In: Proceedings of the National Computer Conference. AFIPS,1979. Vol. 48: 313-317.34Tompa M. and Woll H. How

31、to share a secret with cheaters. Journal of Cryptology, 1988,1: 133-138.Stadler M. Publicly verifiable secret sharing. In: Advance in Cryptography - EUROCRYPT96, LNCS 1070. Berlin:Springer-Verlag, 1996. 190-199.5He J. and Dawson E. Multistage secret sharing based on one-way function. Electronics Let

32、ters, 1994, 30:1591-1592.67He J. and Dawson E. Multisecret-sharing scheme based on one-way function. Electronics Letters, 1995, 31: 93-95.Harn L. Efficient sharing (broadcasting) of multiple secrets. IEE Computers and Digital Techniques, 1995, 142(3):5 237-240.89Shi Rong-Hua. A multisecret sharing a

33、uthenticating scheme. Chinese Journal of Computers, 2003, 26(5): 452-456(in Chinese). (施荣华. 一种多重秘钥共享认证方案. 计算机学报, 2003, 26(5): 452-456.)Ateniese G., Camenisch J., Joye M., and Tsudik G. A practical and provably secure coalition-resistant groupsignature scheme. In: Advances in Cryptology - CRYPTO00, L

34、NCS 1880. Berlin: Springer-Verlag, 2000. 255-270.10 Camenisch J. and Stadler M. Efficient group signature schemes for large groups. Advances in Cryptology -CRYPTO97, LNCS 1294. Berlin: Springer-Verlag, 1997. 410-424.11 Pointcheval D. and Stern J. Security arguments for digital signatures and blind s

35、ignatures. Journal of Cryptology,2000, 13(3): 361-396.12 Bellare M. and Rogaway P. Random oracles are practical: a paradigm for designing efficient protocols. In:Proceedings of the 1st ACM conference on Computer and communications Security. ACM press, 1993. 62-73.13 Schoenmakers B. A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic V oting. In:Ad