On authenticated computing and RSA-based authentication

ABSTRACT

This paper presents a novel hardware attack against RSA-based authentication of programs. Like the seminal paper from [10] it exploits the attacker's ability to arbitrarily tamper with a computational device during its data processing. But, contrary to [10] our method targets the RSA signature verification which processes only public data. Surprisingly, we prove how to let the RSA verification process accept signatures (with high probability and assuming the Riemann Hypothesis) of arbitrary code --- signed with our own self-created private key. While our attack is so far only theoretical, its practical feasibility has been already implicitly confirmed, cf. [6]. In fact, through real experiments with tamper-resistant devices [4] discovered the following caveat being at the heart of our vulnerability: the most often observed fault during RSA-computations exposed to glitch attacks is the erroneous modification of the moduli. Moreover, our attack relies only upon the simplest and most easiest practically implementable fault induction method described by [8]. Our idea is somehow inspired by practiced methods circumventing the FLASH Boot ROM authentication mechanism of the Xbox due to F. Lehner, cf[17]. Our attack can be interpreted as the extrapolation of the mathematical foundation underlying those Xbox vulnerabilities.

REFERENCES

• 1: M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. Ann. of Math., 160(2):781--793, 2004.
• 2: R. Anderson. Security Engineering. John Wiley and Sons, 2001.
• 3: W. A. Arbaugh , D. J. Farber , J. M. Smith, A secure and reliable bootstrap architecture, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.65, May 04-07, 1997
• 4: Christian Aumüller , Peter Bier , Wieland Fischer , Peter Hofreiter , Jean-Pierre Seifert, Fault Attacks on RSA with CRT: Concrete Results and Practical Countermeasures, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.260-275, August 13-15, 2002
• 5: Eric Bach , Jeffrey Shallit, Algorithmic number theory, MIT Press, Cambridge, MA, 1996
• 6: H. Bar-El, H. Choukri, D. Naccache, M. Tunstall, and C. Whelan. The sorcerer's apprentice guide to fault attacks. ePrint archive of IACR 2004/100, IACR, 2004.
• 7: D. J. Bernstein. Cache-timing attacks on AES. Technical report, http://cr.yp.to, http://cr.yp.to/papers.html#cachetiming, 2005.
• 8: Johannes Blömer , Martin Otto , Jean-Pierre Seifert, A new CRT-RSA algorithm secure against bellcore attacks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948151]
• 9: D. Boneh and D. Brumley. Remote timing attacks are practical. In Proc. of 12th Usenix Security Symposium, pages 1--14. USENIX, 2003.
• 10: D. Boneh, R. A. DeMillo, and R. Lipton. On the importance of eliminating errors in cryptographic computations. Journal of Cryptology, 14(2):101--120, 2001.
• 11: Jørgen Brandt , Ivan Damgård, On Generation of Probable Primes By Incremental Search, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.358-370, August 16-20, 1992
• 12: Y. Chen, P. England, M. Peinado, and B. Willman. High assurance computing on open hardware architectures. Technical report MSR-TR-2003-20, Microsoft Corporoation, 2003.
• 13: 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]
• 14: 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]
• 15: Paul England , Marcus Peinado, Authenticated Operation of Open Computing Devices, Proceedings of the 7th Australian Conference on Information Security and Privacy, p.346-361, July 03-05, 2002
• 16: TCG. Trusted computing group. http://www.trustedcomputinggroup.org.
• 17: A. "Bunnie" Huang. Hacking the Xbox. No Starch Press, Inc., San Francisco, 2003.
• 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: J. McNamara. The complete, unofficial tempest information page. http://www.eskimo.com/~joelm/tempest.html.
• 20: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 21: D. A. Osvik, A. Shamir, and E. Tromer. Other people's cache: Hyper attacks on hyperthreaded processors. http://www.wisdom.weizmann.ac.il/~tromer/, March 2005.
• 22: Siani Pearson, Trusted Computing Platforms: TCPA Technology in Context, Prentice Hall PTR, Upper Saddle River, NJ, 2002
• 23: A. Selberg. On the normal density of primes in small intervals and the difference between consecutive primes. Arch. Math. Naturvid., 47:87--105, 1943.
• 24: A. Shamir and E. Tromer. Acoustic cryptanalysis. http://www.wisdom.weizmann.ac.il/~tromer/, March 2004.
• 25: Sean W. Smith, Trusted Computing Platforms: Design and Applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1899
• 26: Peter Szor, The Art of Computer Virus Research and Defense, Addison-Wesley Professional, 2005
• 27: Y. Tsunoo, T. Saito, T. Suzaki, M. Shigeri, and H. Miyauchi. Cryptanalysis of DES implemented on computers with cache. In Proc. of CHES 2003, LNCS, pages 62--76. Springer, 2003.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

General Terms:
Security

Keywords:
RSA, authenticated computing, fault attacks, secure boot