Abstract
Consider the well-known oracle attack: somehow one gets a certain computation result as a function of a secret key from the secret key owner and tries to extract some information on the secret key. This attacking scenario is well understood in the cryptographic community. However, there are many protocols based on the discrete logarithm problem that turn out to leak many of the secret key bits from this oracle attack, unless suitable checkings are carried out. In this paper we present a key recovery attack on various discrete log-based schemes working in a prime order subgroup. Our attack may reveal part of, or the whole secret key in most Diffie-Hellman-type key exchange protocols and some applications of ElGamal encryption and signature schemes.
This work was done while the first author was in POSTECH Information Research Laboratories, POSTECH, Pohang, Korea and the second author was in NEC Research Institute, Princeton, NJ, during his sabbatical leave.
Chapter PDF
References
R.Anderson and R.Needham, Robustness principles for public key protocols, In Advances in Cryptology — CRYPTO'95, LNCS 963, Springer-Verlag, 1995, pp.236–247.
R.Anderson and S.Vaudenay, Minding your p's and q's, In Advances in Cryptology — ASIACRYPT'96, LNCS 1163, Springer-Verlag, 1996, pp.15–25.
A.Aziz, T.Markson and H.Prafullchandra, Simple key-management for Internet protocols (SKIP), draft-ietf-ipsec-skip-07.txt, Aug. 1996. (see also the SKIP home page http: //skip.incog.com/ for more information.)
D.Bleichenbacher, Generating ElGamal signatures without knowing the secret, In Advances in Cryptology — EUROCRYPT'96, LNCS 1070, Springer-Verlag, 1996, pp.10–18.
C.Boyd and W.Mao, Design and analysis of key exchange protocols via secure channel identification, In Advances in Cryptology — ASIACRYPT'94, LNCS 917, Springer-Verlag, 1995, pp.171–181.
S.Brands, Untraceable off-line cash in wallet with observers, In Advances in Cryptology — CRYPTO'93, LNCS 773, Springer-Verlag, 1994, pp.302–318.
S.Brands, An efficient off-line electronic cash system based on the representation problem, Technical Report CS-R9323, CWI, Amsterdam, 1993.
J.Boyar, D.Chaum, I.Damgard and T.Pedersen, Convertible undeniable signatures, In Advances in Cryptology — CRYPTO'90, LNCS 537, Springer-Verlag, 1991, pp.189–205.
M.Burmester, A remark on the efficiency of identification schemes, In Advances in Cryptology — EUROCRYPT'90, LNCS 473, Springer-Verlag, 1991, pp.493–495.
M.Burmester, On the risk of opening distributed keys, In Advances in Cryptology — CRYPTO'94, LNCS 839, Springer-Verlag, 1994, pp.308–317.
A.Chan, Y.Prankel and Y.Tsiounis, Mis-representation of identities in E-cash schemes and how to prevent it, In Advances in Cryptology — ASIACRYPT'96, LNCS 1163, Springer-Verlag, 1996, pp.276–285.
D.Chaum, Zero-knowledge undeniable signatures, In Advances in Cryptology — EUROCRYPT90, LNCS 473, Springer-Verlag, 1991, pp.458–464.
D.Chaum and T.Pedersen, Wallet databases with observers, In Advances in Cryptology — CRYPTO'92, LNCS 740, Springer-Verlag, 1993, pp.89–105.
R.Cramer and T.Pedersen, Improved privacy in wallets with observers, In Advances in Cryptology — EUROCRYPT'93, LNCS 765, Springer-Verlag, 1994, pp.329–343.
Y.Desmedt and Y.Prankel, Threshold cryptosystems, In Advances in Cryptology — CRYPTO'89, LNCS 435, Springer-Verlag, 1990, pp.307–315.
W.Diffie and M.E.Hellman, New directions in cryptography, IEEE Trans. Info. Theory, 22(6), 1976, pp.644–654.
W.Diffie, P.vanOorschot and M.Wiener, Authentication and authenticated key exchange, Designs, Codes and Cryptography, 2, 1992, pp.107–125.
T.ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory, IT-31, 1985, pp.469–472.
M.Jakobsson and M.Yung, Proving without knowing: on oblivious, agnostic and blindfolded provers, In Advances in Cryptology — CRYPTO'96, LNCS 1109, Springer-Verlag, 1996, pp.186–200.
M.Just and S.Vaudenay, Authenticated multi-party key agreement, In Advances in Cryptology — ASIACRYPT'96, LNCS 1163, Springer-Verlag, 1996, pp.36–49.
H.Krawczyk, SKEME: A versatile secure key exchange mechanisms for Internet, In Proc. of 1996 Symp. on Network and Distributed Systems Security.
A.K.Lenstra, P.Winkler and Y.Yacobi, A key escrow system with warrant bounds, In Advances in Cryptology — CRYPTO'95, LNCS 963, Springer-Verlag, 1995, pp.197–207.
C.H.Lim and P.J.Lee, Several practical protocols for authentication and key exchange, Information Processing Letters, 53, 1995, pp.91–96.
C.H.Lim and P.J.Lee, Directed signatures and application to threshold cryptosystems, In Pre-Proc. of 1996 Cambridge Workshop on Security Protocols, The Isaac Newton Institute, Cambridge, April 1996.
C.H.Lim and P.J.Lee, Generating efficient primes for discrete log cryptosystems, submitted for publication (also presented at ASIACRYPT'96 Rump Session).
T.Matsumoto, Y.Takashima and H.Imai, On seeking smart public-key distribution systems, The Transactions of the IEICE of Japan, E69, 1986, pp.99–106.
A.J.Menezes, M.Qu and S.A.Vanstone, Some new key agreement protocols providing implicit authentication, In Proc. SAC'95, Carleton Univ., Ottawa, Ontario, May 1995, pp.22–32.
M.Michels, H.Petersen and P.Horster, Breaking and repairing a convertible undeniable signature scheme, Proc. of 3rd ACM Conference on Computer and Communications Security, Mar. 1996.
T.Okamoto, Designated confirmer signatures and public-key encryption are equivalent, In Advances in Cryptology — CRYPTO'94, LNCS 839, Springer-Verlag, 1995, pp.61–74.
C.S.Park, K.Itoh and K.Kurosawa, Efficient anonymous channel and all/nothing election scheme, In Advances in Cryptology — EUROCRYPT'93, LNCS 765, Springer-Verlag, 1994, pp.248–259.
T.Pedersen, Distributed provers with applications to undeniable signatures, In Advances in Cryptology — EUROCRYPT'91, LNCS 547, Springer-Verlag, 1991, pp.221–242.
B.Pfitzmann, Breaking an efficient anonymous channel, In Advances in Cryptology — EUROCRYPT'94, LNCS 950, Springer-Verlag, 1995, pp.332–340.
S.C.Pohlig and M.E.Hellman, An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Trans. Inform. Theory, IT-24 (1), 1978, pp.106–110.
D.Pointcheval and J.Stern, Security proofs for signature schemes, In Advances in Cryptology — EUROCRYPT'96, LNCS 1070, Springer-Verlag, 1996, pp.387–398.
J.M.Pollard, Monte Carlo methods for index computation (mod p), Math. Comp., 32(143), 1978, pp.918–924.
K.Sako and J.Kilian, Receipt-free mix-type voting scheme, In Advances in Cryptology — EUROCRYPT'95, LNCS 921, Springer-Verlag, 1995, pp.pp.393–403.
A.Shamir, How to share a secret, Commun. ACM, 22, 1979, pp.612–613.
C.P.Schnorr, Efficient identification and signatures for smart cards, In Advances in Cryptology — CRYPTO'89, LNCS 435, Springer-Verlag, 1990, pp.235–251.
J.Stern, The validation of cryptographic algorithms, In Advances in Cryptology — ASIACRYPT'96, LNCS 1163, Springer-Verlag, 1996, pp.301–310.
P.C.van Oorschot and M.J.Wiener, Parallel collision search with applications to hash functions and discrete logarithms, In Proc. 2nd ACM Conference on Computer and Communications Security, Fairfax, Virginia, Nov. 1994, pp.210–218.
P.C.van Oorschot and M.J.Wiener, On Diffie-Hellman key agreement with short exponents, In Advances in Cryptology — EUROCRYPT'96, LNCS 1070, Springer-Verlag, 1996, pp.332–343.
S.Vaudenay, Hidden collisions on DSS, In Advances in Cryptology — CRYPTO'96, LNCS 1109, Springer-Verlag, 1996, pp.83–88.
Y.Yacobi, A key distribution paradox, In Advances in Cryptology — CRYPTO'90, LNCS 537, Springer-Verlag, 1991, pp.268–273.
ISO/IEC JTC1/SC27, Information technology — Security techniques — Key management — Part 3: Mechanisms using asymmetric techniques.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Lim, C.H., Lee, P.J. (1997). A key recovery attack on discrete log-based schemes using a prime order subgroup. In: Kaliski, B.S. (eds) Advances in Cryptology — CRYPTO '97. CRYPTO 1997. Lecture Notes in Computer Science, vol 1294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052240
Download citation
DOI: https://doi.org/10.1007/BFb0052240
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63384-6
Online ISBN: 978-3-540-69528-8
eBook Packages: Springer Book Archive