植基於双线性配对运算的鉴别式金钥协议协定.ppt

植基於雙線性配對運算的鑑別式金鑰協議協定 An ID-based Authenticated Tripartite Key Agreement Protocol Based on Bilinear Pairings,研 究 生：周世峯 指導教授：王有禮 博士,國立臺灣科技大學 資訊管理系 碩士學位論文口試 中華民國九十五年一月九日,2,Outline,Introduction Bilinear pairings and some assumptions Jouxs protocol LZC protocol Weakness in the LZC protocol Shim-Woos modified protocol Our improved protocol Security and efficiency analysis Conclusion,3,Introduction,Key agreement (key exchange) - allow two or more parties to share a secret over an insecure channel Diffie-Hellmam protocol (1976) - man-in-the-middle attack (MITM attack) Jouxs protocol (2000) - the first one round tripartite key agreement protocol with pairing - MITM attack Boneh and Franklin (2001) - ID-based Encryption from the weil pairing Liu et al. (2003) proposed an ID-based one round authenticated tripartite key agreement protocol (LZC protocol) - to overcome the MITM attack in Jouxs protocol - it can create eight session keys per one instance - Unknown key-share attack Shim et al. (2005) proposed a modified protocol (Shim-Woo protocol) - satisfies all the required security attributes - dose not require any one-way hash functions Our improved protocol - more efficient and suitable for smart card and mobile devices - satisfies all the required security attributes,4,Key agreement How to secure communication in an insecure channel?,Diffie-Hellmam protocol (1976),驗證 Diffie-Hellman 演算法 n = 47, g = 3 為系統公開參數 Alice 選定：x = 8 計算出： gx mod n = 38 mod 47 = 28 mod 47 訊息 (1) = 28 Bob 選定：y =10 , 計算出： gy mod n = 310 mod 47 = 17 mod 47 訊息 (2) = 17 Alice 計算交談金鑰 KA： (gy mod n)x = gxy mod n = 178 mod 47 = 4 mod 47 Bob 計算交談金鑰 KB： (gx mod n)y = gxy mod n = 2810 mod 47 = 4 mod 47 交談鑰匙 KA = 4 = KB,Bob,Alice, confidentiality, data integrity,KA(銀行密碼：5168888) -xxxxxxxxxxx- KB(銀行密碼：5168888),DLP：given x gx mod n is easy, given gx mod n x=? is hard.,5,Man-in-the-middle attack,Bob,Alice,Eva,Authentication: Message authentication code (MAC), Message digest (DS) Digital Signature, Because it does not attempt to authenticate the communicating entities.,written signature: can easily to forge Digital signature: requires huge computational resources,6,Desirable security attributes,Known-Key Security - learned previous session keys cant deduce future session keys Forward Secrecy - lost long-term secrets the secrecy of previous session keys is not affected Key-Compromise Impersonation resilience Unknown Key-Share resilience - A cant be coerced into sharing a key with others without As knowledge AB, BCA, A has a unknown key share with C Key Control - the key should be determined jointly by all communicating entities (Alice and Bob),A,B,C,E,A,7,Elliptic Curve Cryptography (ECC),E: y2 = x3 + ax + b If x3 + ax + b contains no repeated factors, or equivalently if 4a3 + 27b2 is not 0, then the elliptic curve y2 = x3 + ax + b can be used to form a algebraic group. addition: P + Q = R Multiplication: kP = P + + P,8,Elliptic Curve Cryptography,The determination of a point nP in this manner is referred to as Scalar Multiplication of a point. The ECDLP is based upon the intractability of scalar multiplication products. ECDLP：given two points Q, P to determine k such that Q = kP is hard.,9,Bilinear pairing (Weil pairing, Tate pairing),10,Some assumptions,DLP：給定 b, n, g 要求得 x 且滿足 gx = b (mod n),ECDLP：給定橢圓曲線上兩相異點 P, Q 要求得一整數 k 且滿足 Q = kP,DHP：給定 ga mod n, gb mod n 要求得 gc mod n 且滿足 c = ab mod q,BDHP：給定 P, aP, bP, cP 要求得 abc 且滿足 e(P, P)abc,DDHP：給定 P, aP, bP 要決定 abc 且滿足 e(P, P)abc,DBDHP：給定 P, aP, bP, cP 要決定 c = ab mod q 且滿足 e(P, P)c = e(P, P)ab,CDHP：給定 P, aP, bP 要求得 abP,SCDHP：給定 P, aP 要求得 a2P,兩者互為等價關係,11,Jouxs tripartite key agreement protocol,B,A,C,Setup:,Messages exchange:,12,Cryptanalysis on Jouxs protocol Man-in-the-middle attack,13,LZC protocol (1/2),Setup:,Messages exchange:,Private key extraction:,A computes:,A verifies:,SA:identify user A H is a hash function H(PA, PA) is a fingerprint PA, PA H(PA, PA) is easy H(PA, PA) PA, PA is hard aP, aP aPA CDHP,14,LZC protocol (2/2),15,Weakness in the LZC protocol (1/2),16,Weakness in the LZC protocol Unknown Key-Share attack (2/2),B and C compute the same session keys:,A computes the session keys:,A 存 1000到A的帳戶,B E 存 1000到E的帳戶,B 結果B 存了1000給E，而不是給A,17,Shim-Woos protocol (1/2),Setup:,Messages exchange:,Private key extraction:,A computes:,A verifies:,18,Shim-Woos protocol (2/2),19,Our improved protocol,20,Our Ideas,21,Setup:,Messages exchange:,Private key extraction:,A computes:,A verifies:,改變的地方,New protocol (1/2),22,New protocol (2/2),23,Security analysis,Authenticity of broadcast message: Without long-term SA, SB, SC - Implicit key authentication: Without long-term SA, SB, SC cant forge a signature TA - Known-key security: Cant extract a or a from DLP - Forward secrecy: Lost SA, PA, PA, TA TA - SA = aPpub + aPpub given aP, aP, asP + asP, to recover a and a CDHP - Key-compromise impersonation resilience: Lost SA, E(B) A, C : PB, PB, TB E doesnt know b or b corresponding to PB = bP, PB = bP. - Unknown key-share resilience: Only an entity who knows a, a and SA can generate a valid TA. Known aP, sP asP ; aP, sP asP both CDHP,24,Efficiency analysis,LZC Shim-Woo Ours,25,Conclusion,Our further improved protocol is more efficient than all previous protocol that we know. LZC protocol Shim-Woo protocol Its satisfies all the required security attributes and more suitable for smart card and mobile devices.,Thanks for your attention!,References,1 S.S. Al-Riyami and K. G. Paterson. “Tripartite Authenticated Key Agreement Protocols from Pairings,” In proceedings of IMA Conference of Cryptography and Coding, LNCS 2898, 2003, pp. 332-359. Also available at /2002/035. 2 F. Bao, R. Deng, H. Zhu, “Variations of DiffieHellman problem,” in: Proceedings of ICICS 2003, LNCS 2836, Springer-Verlag, 2003, pp. 301312. 3 P.S.L.M. Barreto, H. Y. Kim and M. Scott. “Efficient Algorithms for Pairing Based Cryptosystems,” In proceedings of Crypto 2002, LNCS 2442, pp. 354-368, Springer-Verlag, 2002. Also available at /2002/008. 4 R. Barua, R. Dutta, P. Sarkar. “Extending Joux Protocol to Multi Party Key Agreement,” In proceedings of Indocrypt 2003, LNCS 2904, pp. 205-217, Springer-Verlag, 2003. Also available at /2003/062. 5 S. Blake-Wilson & A. Menezes, “Authenticated Diffie-Hellman key agreement protocols,” Proc. 5th Annual Workshop on Selected Areas in Cryptography (SAC98), Kingston, Canada, 1999, 339-361. 6 S. Blake-Wilson, D. Johason and A. Menezes. “Key Agreement Protocols and Their Security Analysis,” In proceedings of the sixth IMA International Conference on Cryptography and Coding, LNCS 1355, pp. 30-45, Springer-Verlag, 1997. 7 S. Blake-Wilson, D. Johnson, A. Menezes, “Unknown key-share attacks on the station-tostation (STS) protocol,” In proceedings of PKC 1999, LNCS 1560, Springer-Verlag, 1999, pp. 154170. 8 D. Boneh. and M. Franklin. “Identity-based Encryption from the Weil pairing,” SIAM J. of Computing, 32(3):586-615, 2003. Extended abstract in Advances in Crptology-Crypto01, LNCS 2139, pp.213-229, Springer-Verlag, 2001. 9 C. Boyd and J. M. G. Nieto. “Round-optimal Contributory Conference Key Agreement,” In proceedings of PKC 2003, LNCS 2567, pp. 161-174, Springer-Verlag, 2003. 10 E. Bresson and D. Catalano. “Constant Round Authenticated Group Key Agreement via Distributed Computing,” In proceedings of PKC 2004, LNCS 2947, pp. 115-129, Springer-Verlag, 2004. 11 E. Bresson, O. Chevassut, A. Essiari and D. Pointcheval. “Mutual Authentication and Group Key Agreement for Low-power Mobile Devices,” Computer Communication, 27(17), pp. 1730-1737, 2004. A preliminary version appeared in proceedings of the 5th IFIP-TC6/IEEE , MWCN 2003, pp. 59-62, 2003. Full version available at http:/www.di.ens.fr/ bresson.,References,12 E. Bresson, O. Chevassut, and D. Pointcheval. “Provably Authenticated Group Diffie-Hellman Key Exchange - The Dynamic Case,” In proceedings of Asiacrypt 2001, LNCS 2248, pp. 290-309, Springer-Verlag, 2001. 13 W. Diffie, M. Hellman. “New Directions In Cryptography,” IEEE Transaction on Information Theory, IT-22 (6) : 644-654, November, 1976. 14 R. Dutta. and R. Barua. “Overview of Key Agreement Protocols,” Cryptology ePrint Archive, Report 2005/289, Available at /2005/289. 15 S. Galbraith, K. Harrison and D. Soldera. “Implementing the Tate Pairing,” In proceedings of Algorithm Number Theory Symposium - ANTS V, LNCS 2369, pp. 324-337, Springer-Verlag, 2002. 16 F. Hess. “Efficient Identity Based Signature Schemes Based on Pairings,” In proceedings of SAC 2002, LNCS 2595, pp. 310-324, Springer-Verlag, 2002. 17 A. Joux. “A One Round Protocol for Tripartite Diffie-Hellman,” In proceedings of ANTS 4, LNCS 1838, pp. 385-394, Springer-Verlag, 2000. 18 Y. Kim, A. Perrig, and G. Tsudik. “Communication-efficient Group Key Agreement,” In proceedings of the 17th International Information Security Conference, IFIP SEC 2001, pp. 229-244, 2001. 19 Y. Kim, A. Perrig, and G. Tsudik. “Tree Based Group Key Agreement,” Cryptology ePrint Archive, Report 2002/009, Available at /2002/009. 20 L. Law, A. Menezes, M. Qu, J. Solinas, and S. Vanstone. “An Efficient Protocol for Authenticated Key Agreement,” Technical Report CORR 98-05, Department of C & O, University of Waterloo, 1998. Also available at /law98efficient. 21 S. Liu, F. Zhang, K. Chen, “ID-based tripartite key agreement protocol with pairing,” 2003 IEEE International Symposium on Information Theory, 2003, pp. 136143, or available at Cryptology ePrint Archive, Report 2002/122. 22 T. Matsumoto, Y. Takashima and H. Imai. “On Seeking Smart Public-key Distribution Systems,” In Transactions of the IECE of Japan, E69, pp. 99-106, 1986. 23 A. Menezes, T. Okamoto, and S. Vanstone, “Reducing elliptic curve logarithms to logarithms in a finite field,” IEEE Transaction on Information Theory, Vol.39, pp.1639-1646, 1993. 24 D. Nalla and K. C. Reddy. “ID-Based Tripartite Authenticated Key Agreement Protocolsfrom Pairings,” Cryptology ePrint Archive, Report 2003/004, Available at /2003/004.,References,25 D. Nalla and K. C. Reddy. “Identity Based Authenticated Group Key Agreement Protocol,” In proceedings of Indocrypt 2002, LNCS 2551, pp. 215-233, Springer-Verlag, 2002. 26 D. Nalla. “ID-Based Tripartite Key Agreement with Signature,” Cryptology e