Improving Brumley and Boneh timing attack on unprotected SSL implementations

ABSTRACT

Since the remarkable work of Kocher [7], several papers considering different types of timing attacks have been published. In 2003, Brumley and Boneh presented a timing attack on unprotected OpenSSL implementations [2]. In this paper, we improve the efficiency of their attack by a factor of more than 10. We exploit the timing behavior of Montgomery multiplications in the table initialization phase, which allows us to increase the number of multiplications that provide useful information to reveal one of the prime factors of RSA moduli. We also present other improvements, which can be applied to the attack in [2].

REFERENCES

• 1: Daniel Bleichenbacher, Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.1-12, August 23-27, 1998
• 2: D. Brumley, D. Boneh: Remote Timing Attacks are Practical. In: Proceedings of the 12th Usenix Security Symposium, 2003.
• 3: B. Canvel, A. Hiltgen, S. Vaudenay, M. Vuagnoux: Password Interception in a SSL/TSL Channel. In: D. Boneh (ed.): Crypto 2003, Lecture Notes in Computer Science 2729, Springer, Heidelberg (2003), 583--599.
• 4: D. Coppersmith: Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. J. Cryptology 10 (no. 4) (1997) 233--260.
• 5: Jean-François Dhem , François Koeune , Philippe-Alexandre Leroux , Patrick Mestré , Jean-Jacques Quisquater , Jean-Louis Willems, A Practical Implementation of the Timing Attack, Proceedings of the The International Conference on Smart Card Research and Applications, p.167-182, September 14-16, 1998
• 6: W. Feller: Introduction to Probability Theory and Its Applications (Vol. 1). 3rd edition, revised printing, New York, Wiley (1970).
• 7: Paul C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.104-113, August 18-22, 1996
• 8: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 9: W. Schindler: Optimized Timing Attacks against Public Key Cryptosystems. Statist. Decisions 20 (2002), 191--210.
• 10: Werner Schindler, A Timing Attack against RSA with the Chinese Remainder Theorem, Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, p.109-124, August 17-18, 2000
• 11: Werner Schindler , François Koeune , Jean-Jacques Quisquater, Improving Divide and Conquer Attacks against Cryptosystems by Better Error Detection / Correction Strategies, Proceedings of the 8th IMA International Conference on Cryptography and Coding, p.245-267, December 17-19, 2001
• 12: W. Schindler: On the Optimization of Side-Channel Attacks by Advanced Stochastic Methods. In: S. Vaudenay (ed.): Public Key Cryptography --- PKC 2005, Springer, Lecture Notes in Computer Science 3386, Berlin 2005, 85--103.
• 13: GNU Project: GMP: http://www.swox.com/gmp/.
• 14: OpenSSL Project: OpenSSL: http://www.openssl.org.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
RSA, side-channel cryptanalysis, timing attacks