Abstract
Since its formulation in 1996, the Hidden Number Problem (HNP) plays an important role in both cryptography and cryptanalysis. It has a strong connection with proving security of Diffie-Hellman and related schemes as well as breaking certain implementations of DSA-like signature schemes. We formulate an extended version of HNP (EHNP) and present a polynomial time algorithm for solving its instances. Our extension improves usability of HNP for solving real cryptanalytic problems significantly. The techniques elaborated here can be used for cryptographic strength proving, as well. We then present a practically feasible side channel attack on certain implementations of DSA (e.g. OpenSSL), which emphasizes the security risk caused by a side channel hidden in the design of Pentium 4 HTT processor for applications like SSH. During experimental simulations, having observed as few as 6 authentications to the server, an attacker was able to disclose the server’s private key.
Chapter PDF
Similar content being viewed by others
References
Digital signature standard. National Institute of Standards and Technology, Washington (Note: Federal Information Processing Standard 186-2) (2000), URL: http://csrc.nist.gov/publications/fips/
Secure hash standard. National Institute of Standards and Technology, Washington (Note: Federal Information Processing Standard 180-2) (2002), URL: http://csrc.nist.gov/publications/fips/
Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. In: Mehlhorn, K. (ed.) STACS 1985. LNCS, vol. 182, pp. 13–20. Springer, Heidelberg (1984)
Bellare, M., Goldwasser, S., Micciancio, D.: ”Pseudo-Random” number generation within cryptographic algorithms: The DDS case. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 277–291. Springer, Heidelberg (1997)
Bishop, M.: Computer Security: Art and Science. Addison-Wesley, Reading (2003)
Boneh, D., Halevi, S., Howgrave-Graham, N.: The modular inversion hidden number problem. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 36–51. Springer, Heidelberg (2001)
Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 129–142. Springer, Heidelberg (1996)
Frieze, A.M., Hastad, J., Kannan, R., Lagarias, J.C., Shamir, A.: Reconstructing truncated integer variables satisfying linear congruences. SIAM Journal of Computing 17(2), 262–280 (1988)
Groetschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, 2nd edn. Springer, Heidelberg (1993)
Howgrave-Graham, N.-A., Smart, N.P.: Lattice attacks on digital signature schemes. Design, Codes and Cryptography 23, 283–290 (2001)
Intel Corporation. Intel(R) Pentium(R) 4 Processor supporting Hyper-Threading Technology. URL: http://www.intel.com/products/processor/pentium4/index.htm
Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Ann. 261, 513–534 (1982)
Nguyen, P.Q.: The dark side of the hidden number problem: Lattice attacks on DSA. In: CCNT 1999. Proc. of the Workshop on Cryptography and Computational Number Theory, Basel, CH, pp. 321–330. Birkhäuser (2001)
Nguyen, P.Q., Shparlinski, I.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptology 15(3), 151–176 (2002)
Nguyen, P.Q., Stehlé, D.: Floating-point LLL revisited. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 215–233. Springer, Heidelberg (2005)
Nguyen, P.Q., Stern, J.: The two faces of lattices in cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 146–180. Springer, Heidelberg (2001)
Osvik, D.A., Shamir, A., Tromer, E.: Cache attacks and countermeasures: The case of AES. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 1–20. Springer, Heidelberg (2006)
Percival, C.: Cache missing for fun and profit (2005), URL: http://www.daemonology.net/papers/htt.pdf
OpenBSD project members. OpenSSH Suite. URL: http://www.openssh.com/
Shoup, V.: NTL: A Library for doing Number Theory. URL: http://www.shoup.net/ntl/
Shparlinski, I., Winterhof, A.: A hidden number problem in small subgroups. Mathematics of Computation 74(252), 2073–2080 (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hlaváč, M., Rosa, T. (2007). Extended Hidden Number Problem and Its Cryptanalytic Applications. In: Biham, E., Youssef, A.M. (eds) Selected Areas in Cryptography. SAC 2006. Lecture Notes in Computer Science, vol 4356. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74462-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-74462-7_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74461-0
Online ISBN: 978-3-540-74462-7
eBook Packages: Computer ScienceComputer Science (R0)