On the power of simple branch prediction analysis

ABSTRACT

Very recently, a new software side-channel attack, called Branch Prediction Analysis (BPA) attack, has been discovered and also demonstrated to be practically feasible on popular commodity PC platforms. While the above recent attack still had the flavor of a classical timing attack against RSA, where one uses many execution-time measurements under the same key in order to statistically amplify some small but key-dependent timing differences, we dramatically improve upon the former result. We prove that a carefully written spy-process running simultaneously with an RSA-process, is able to collect during one single RSA signing execution almost all of the secret key bits. We call such an attack, analyzing the CPU's Branch Predictor states through spying on a single quasi-parallel computation process, a Simple Branch Prediction Analysis (SBPA) attack --- sharply differentiating it from those one relying on statistical methods and requiring many computation measurements under the same key. The successful extraction of almost all secret key bits by our SBPA attack against an openSSL RSA implementation proves that the often recommended blinding or so called randomization techniques to protect RSA against side-channel attacks are, in the context of SBPA attacks, totally useless. Additional to that very crucial security implication, targeted at such implementations which are assumed to be at least statistically secure, our successful SBPA attack also bears another equally critical security implication. Namely, in the context of simple side-channel attacks, it is widely believed that equally balancing the operations after branches is a secure countermeasure against such simple attacks. Unfortunately, this is not true, as even such "balanced branch" implementations can be completely broken by our SBPA attacks. Moreover, despite sophisticated hardware-assisted partitioning methods such as memory protection, sandboxing or even virtualization, SBPA attacks empower an unprivileged process to successfully attack other processes running in parallel on the same processor. Thus, we conclude that SBPA attacks are much more dangerous than previously anticipated, as they obviously do not belong to the same category as pure timing attacks.

REFERENCES

• 1: O. Aciiçmez, J.-P. Seifert, and Ç. K. Koç. Predicting secret keys via branch prediction. Topics in Cryptology - CT-RSA 2007, The Cryptographers' Track at the RSA Conference 2007, to appear.
• 2: D. J. Bernstein. Cache-timing attacks on AES. Technical Report, 37 pages, April 2005. Available at: http://cr.yp.to/antiforgery/cachetiming-20050414.pdf
• 3: David Brumley , Dan Boneh, Remote timing attacks are practical, Proceedings of the 12th conference on USENIX Security Symposium, p.1-1, August 04-08, 2003, Washington, DC
• 4: Y. Chen, P. England, M. Peinado, and B. Willman. High Assurance Computing on Open Hardware Architectures. Technical Report, MSR-TR-2003-20, 17 pages, Microsoft Corporation, March 2003. Available at: ftp://ftp.research.microsoft.com/pub/tr/tr-2003-20.ps
• 5: Benoît Chevallier-Mames , Mathieu Ciet , Marc Joye, Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity, IEEE Transactions on Computers, v.53 n.6, p.760-768, June 2004 [doi>10.1109/TC.2004.13]
• 6: Jean-Sebastien Coron , David Naccache , Paul Kocher, Statistics and secret leakage, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.3, p.492-508, August 2004 [doi>10.1145/1015047.1015050]
• 7: 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
• 8: Paul England , Butler Lampson , John Manferdelli , Marcus Peinado , Bryan Willman, A Trusted Open Platform, Computer, v.36 n.7, p.55-62, July 2003 [doi>10.1109/MC.2003.1212691]
• 9: S. Gochman, R. Ronen, I. Anati, A. Berkovits, T. Kurts, A. Naveh, A. Saeed, Z. Sperber, and R. Valentine. The Intel Pentium M processor: Microarchitecture and performance. Intel Technology Journal, volume 7, issue 2, May 2003.
• 10: D. Grawrock. The Intel Safer Computing Initiative: Building Blocks for Trusted Computing, Intel Press, 2006.
• 11: N. A. Howgrave-Graham , N. P. Smart, Lattice Attacks on Digital Signature Schemes, Designs, Codes and Cryptography, v.23 n.3, p.283-290, August 2001 [doi>10.1023/A:1011214926272]
• 12: Jim Handy, The cache memory book (2nd ed.): the authoritative reference on cache design, Academic Press, Inc., Orlando, FL, 1998
• 13: G. Hinton, D. Sager, M. Upton, D. Boggs, D. Carmean, A. Kyker, and P. Roussel. The Microarchitecture of the Pentium 4 Processor. Intel Technology Journal, volume 5, issue 1, Feb. 2001.
• 14: Wei-Ming Hu, Lattice Scheduling and Covert Channels, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.52, May 04-06, 1992
• 15: Marc Joye , Karine Villegas, A protected division algorithm, Proceedings of the 5th conference on Smart Card Research and Advanced Application Conference, p.8-8, November 21-22, 2002, San Jose, CA
• 16: Marc Joye , Sung-Ming Yen, The Montgomery Powering Ladder, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.291-302, August 13-15, 2002
• 17: H. Kahl. SPA-based attack against the modular reduction within a partially secured RSA-CRT implementation. Cryptology ePrint Archive, Report 2004/197, 2004, http://eprint.iacr.org/197.pdf.
• 18: 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
• 19: Rita Mayer-Sommer, Smartly Analyzing the Simplicity and the Power of Simple Power Analysis on Smartcards, Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, p.78-92, August 17-18, 2000
• 20: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 21: Milena Milenkovic , Aleksandar Milenkovic , Jeffrey Kulick, Microbenchmarks for determining branch predictor organization, Software—Practice & Experience, v.34 n.5, p.465-487, April 2004 [doi>10.1002/spe.v34:5]
• 22: M. Neve and J.-P. Seifert. Advances on Access-driven Cache Attacks on AES. Proceedings of Selected Area of Cryptology (SAC 2006), Montreal, Canada, August 2006, to appear at Springer LNCS.
• 23: P. Q. Nguyen and I. E. Shparlinski. The Insecurity of the Digital Signature Algorithm with Partially Known Nonces. Journal of Cryptology, vol. 15, no. 3, pp. 151176, Springer, 2002.
• 24: Phong Q. Nguyen , Igor E. Shparlinski, The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces, Designs, Codes and Cryptography, v.30 n.2, p.201-217, September 2003 [doi>10.1023/A:1025436905711]
• 25: Openssl: the open-source toolkit for ssl / tls. Available online at http://www.openssl.org/.
• 26: D. A. Osvik, A. Shamir, and E. Tromer. Other People's Cache: Hyper Attacks on HyperThreaded Processors. Presentation available at: http://www.wisdom.weizmann.ac.il/~tromer/.
• 27: D. A. Osvik, A. Shamir, and E. Tromer. Cache Attacks and Countermeasures: The Case of AES. Topics in Cryptology - CT-RSA 2006, The Cryptographers' Track at the RSA Conference 2006, D. Pointcheval, editor, pages 1--20, Springer-Verlag, LNCS vol. 3860, 2006.
• 28: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 29: Siani Pearson, Trusted Computing Platforms: TCPA Technology in Context, Prentice Hall PTR, Upper Saddle River, NJ, 2002
• 30: C. Percival. Cache missing for fun and profit. BSDCan 2005, Ottawa, 2005. Available at: http://www.daemonology.net/hyperthreading-considered-harmful/
• 31: Charles P. Pfleeger , Shari Lawrence Pfleeger, Security in Computing, Prentice Hall Professional Technical Reference, 2002
• 32: Eric Rotenberg , Steve Bennett , James E. Smith, Trace cache: a low latency approach to high bandwidth instruction fetching, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.24-35, December 02-04, 1996, Paris, France
• 33: 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
• 34: Tom Shanley, The Unabridged Pentium 4: IA32 Processor Genealogy, Pearson Education, 2004
• 35: Abraham Silberschatz, Operating Systems Concepts, John Wiley & Sons, 2005
• 36: J. Shen and M. Lipasti. Modern Processor Design: Fundamentals of Superscalar Processors. McGraw-Hill, 2005.
• 37: O. Sibert , P. A. Porras , R. Lindell, The Intel 80x86 Processor Architecture: Pitfalls for Secure Systems, Proceedings of the 1995 IEEE Symposium on Security and Privacy, p.211, May 08-10, 1995
• 38: Sean W. Smith, Trusted Computing Platforms: Design and Applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1899
• 39: Trusted Computing Group, http://www.trustedcomputinggroup.org.
• 40: Rich Uhlig , Gil Neiger , Dion Rodgers , Amy L. Santoni , Fernando C. M. Martins , Andrew V. Anderson , Steven M. Bennett , Alain Kagi , Felix H. Leung , Larry Smith, Intel Virtualization Technology, Computer, v.38 n.5, p.48-56, May 2005 [doi>10.1109/MC.2005.163]
• 41: C. D. Walter. Montgomery Exponentiation Needs No Final Subtractions. IEE Electronics Letters, volume 35, number 21, pages 1831--1832, October 1999.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
RSA, branch prediction analysis, modular exponentiation, side channel analysis