Email this article A Small Subgroup Attack for Recovering Ephemeral Keys in Chang and Chang Password Key Exchange Protocol
Abstract
Three-party authenticated key exchange protocol is an important cryptographic technique in the secure communication areas. Recently Chang and Chang proposed a novel three party simple key exchange protocol and claimed the protocol is secure, efficient and practical. Unless their claim, a key recovery attack is proposed on the above protocol by recovering the ephemeral keys. One way of recovering the ephemeral key is to solve the mathematical hard Discrete Logarithm Problem (DLP). The DLP is solved by using a popular Pohlig-Hellman method in the above key recovery attack. In the present study, a new method based on the small subgroup attack to solve the DLP is discussed to recover the ephemeral keys. Computation of DLP is carried out by two stages, such as the prior-computation and DLP computation. The prior-computation is performed on off-line and the DLP computation is performed on on-line. The method is analyzed on a comprehensive set of experiments and the ephemeral keys are recovered in reduced time. Also, the key recovery attack on Chang and Chang password key exchange protocol is implemented by using the new method to recover the ephemeral key.
Keywords
References
[1] M. Abdella and D. Pointcheval, “Simple passwordbased encrypted key exchange protocols”, CT-RSA 2005, Springer-Verlag, p191-208, 2005.
[2] SM. Bellovin and M. Merrit, “Encrypted key exchange: password-based protocols secure against dictionary attacks”, IEEE symposium on research in security and privacy, p72-84, 1992.
[3] CC. Chang and YF. Chang, “A novel three party encrypted key exchange protocol”, Computer Standards and Interfaces, v26(5), p471-6, 2004.
[4] Y. Ding and P.Hoster, “Undetectable Online password guessing attacks”, ACM operating systems review, v29(4), p77-86, 1995.
[5] H. Guo, Z. Li, Y. Mu and X. Zhang “Cryptanalysis of simple three-party key exchange protocol”, Computers and Security, v27, p16-21, 2008.
[6] D. E Knuth, The Art of computer programming, vol.3:Sorting and Searching, Addison-Wesley, 1973.
[7] CL. Lin, HM. Sun, M. Steiner, T. Hwang “Three-party encrypted key exchange without server public keys” IEEE Communications letters, v5(12), p497-499, 2001.
[8] R. Lu and Z. Cao, “Simple three-party key exchange protocol”, Computers and Security, v26, p94-97, 2007.
[9] McCurely, “The Discrete logarithm problem”, Cryptology and computational number theory proceeding of symposia in Applied Mathematics, v42, pp 49-74.
[10] A. Menezes, and U. Berkant, “On Reusing Ephemeral Keys in Diffie-Hellman Key Agreement Protocols”, preprint, 2008.
[11] R. Padmavathy, and Chakravarthy Bhagvati, “A Key Recovery Attack on Chang and Chang Password Key Exchange Protocol”, International Conference on Computer and Network Technology, pp176-181, 2009.
[12] R. Padmavathy, and Chakravarthy Bhagvati, “Methods to Solve Discrete Logarithm Problem for Ephemeral Keys”, ARTCOM, pp704-708, 2009.
[13] R. Padmavathy, and Chakravarthy Bhagvati, “Ephemeral Key Recovery using Index Calculus Method”, Journal of Discrete Mathematical Sciences and Cryptography, v13(1), pp29-43, 2009.
[14] R. Padmavathy, and Chakravarthy Bhagvati, “Improved Random Method for Index Calculus Method”, National Workshop on Cryptology, pp71-91, 2008.
[15] RCW. Phan, WC. Yau and BM. Goi “Cryptanalysis of simple three-party key exchange protocol (S-3PAKE)”, Information sciences, v178(2), p849-856, 2008.
[16] J. M Pollard, “Monte Carlo methods for index computation (mod p)”, Mathematics of Computation., v32(143), pp.106-110, 1978.
[17] S. Pohlig, and M. Hellman, “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance”, IEEE Transaction on Information Theory, v24, pp 106-110, 1978.
[18] M. Steiner and G. Tsudik, M. Waidner “Refinement and extention of encrypted key exchange”, ACM Operating Systems Review, v29(3), p22-30, 1995.
[19] EJ. Yoon and KY. Yoo, “Improving the novel three-party encrypted key exchange protocol”, Computer Standards and Interfaces, v30 p309-314, 2008.Full Text: PDF