skip to main content
10.1145/2382196.2382230acmconferencesArticle/Chapter ViewAbstractPublication PagesccsConference Proceedingsconference-collections
research-article

Cross-VM side channels and their use to extract private keys

Published:16 October 2012Publication History

ABSTRACT

This paper details the construction of an access-driven side-channel attack by which a malicious virtual machine (VM) extracts fine-grained information from a victim VM running on the same physical computer. This attack is the first such attack demonstrated on a symmetric multiprocessing system virtualized using a modern VMM (Xen). Such systems are very common today, ranging from desktops that use virtualization to sandbox application or OS compromises, to clouds that co-locate the workloads of mutually distrustful customers. Constructing such a side-channel requires overcoming challenges including core migration, numerous sources of channel noise, and the difficulty of preempting the victim with sufficient frequency to extract fine-grained information from it. This paper addresses these challenges and demonstrates the attack in a lab setting by extracting an ElGamal decryption key from a victim using the most recent version of the libgcrypt cryptographic library.

References

  1. O. Aciiçmez. Yet another microarchitectural attack: Exploiting I-cache. In ACM Workshop on Computer Security Architecture, pages 11--18, October 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. O. Aciiçmez, B. B. Brumley, and P. Grabher. New results on instruction cache attacks. In Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, pages 110--124, August 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. O. Aciiçmez, Ç. K. Koç, and J.-P. Seifert. On the power of simple branch prediction analysis. In 2nd ACM Symposium on Information, Computer and Communications Security, pages 312--320, March 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. O. Aciiçmez, W. Schindler, and Ç. K. Koç. Cache based remote timing attack on the AES. In Topics in Cryptology -- CT-RSA 2007, The Cryptographers' Track at the RSA Conference 2007, pages 271--286, February 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. O. Aciiçmez and J.-P. Seifert. Cheap hardware parallelism implies cheap security. In Workshop on Fault Diagnosis and Tolerance in Cryptography, pages 80--91, September 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. H. Katz, A. Konwinski, G. Lee, D. A. Patterson, A. Rabkin, I. Stoica, and M. Zaharia. A view of cloud computing. Commun. ACM, 53(4):50--58, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Celera Assembler. http://wgs-assembler.sourceforge.net/.Google ScholarGoogle Scholar
  8. E. Bangerter, D. Gullasch, and S. Krenn. Cache games -- bringing access-based cache attacks on AES to practice. In 32nd IEEE Symposium on Security and Privacy, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield. Xen and the art of virtualization. In 19th ACM Symposium on Operating Systems Principles, pages 164--177, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. L. E. Baum, T. Petrie, G. Soules, and N. Weiss. A maximization technique occurring in the statistical analysis of probabilistic functions of markov chains. The Annals of Mathematical Statistics, 41(1):164--171, 1970.Google ScholarGoogle ScholarCross RefCross Ref
  11. D. J. Bernstein. Cache-timing attacks on AES, 2005.Google ScholarGoogle Scholar
  12. C. M. Bishop. Pattern Recognition and Machine Learning. Springer, October 2007.Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. D. Brumley and D. Boneh. Remote timing attacks are practical. Computer Networks, 48(5):701--716, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. J. Callas, L. Donnerhacke, H. Finney, and R. Thayer. Openpgp message format. Technical report, RFC 2440, November, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. C. C. Chang and C. J. Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):27, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. D. Chisnall. The Definitive Guide to the Xen Hypervisor (Prentice Hall Open Source Software Development Series). Prentice Hall PTR, November 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. ClustalW2. http://www.clustal.org/clustal2/.Google ScholarGoogle Scholar
  18. Intel Corporation. Intel 64 and IA-32 architectures software developer's manual, vol 1--3. http://www.intel.com/products/processor/manuals/.Google ScholarGoogle Scholar
  19. T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, IT-31(4), July 1985. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. P. England and J. Manferdelli. Virtual machines for enterprise desktop security. Information Security Technical Report, 11(4):193 -- 202, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. K. Gandolfi, C. Mourtel, and F. Olivier. Electromagnetic analysis: Concrete results. In Cryptographic Hardware and Embedded Systems -- CHES 2001, volume 2162 of LNCS, pages 251--261, May 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. T. Garfinkel, B. Pfaff, J. Chow, M. Rosenblum, and D. Boneh. Terra: a virtual machine-based platform for trusted computing. In ACM Symposium on Operating Systems Principles, pages 193--206. ACM, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. N. Gautham. Bioinformatics: Databases and Algorithms. Alpha Science International Ltd., 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. Gnu Privacy Guard. www.gnupg.org, 2012.Google ScholarGoogle Scholar
  25. P. Kocher, J. Jaffe, and B. Jun. Differential power analysis. In Advances in Cryptology -- CRYPTO '99, volume 1666 of LNCS, pages 388--397, August 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. P. C. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In N. Koblitz, editor, Advances in Cryptology -- Crypto'96, volume 1109 of LNCS, pages 104--113. Springer-Verlag, 1996. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. D. Magenheimer. TSC mode HowTo. Available: http://mirror.choon.net/xen/xen-unstable.hg/docs/misc/tscmode.txt.Google ScholarGoogle Scholar
  28. Andrew Marshall, Michael Howard, Grant Bugher, and Brian Harden. Security best practices for developing windows azure applications, June 2010.Google ScholarGoogle Scholar
  29. R. Meushaw and D. Simard. A network on a desktop. NSA Tech Trend Notes, 9(4), 2000. http://www.vmware.com/pdf/TechTrendNotes.pdf.Google ScholarGoogle Scholar
  30. P. L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Math. Comp, 48(177):243--264, January 1987.Google ScholarGoogle ScholarCross RefCross Ref
  31. S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443--453, March 1970.Google ScholarGoogle ScholarCross RefCross Ref
  32. M. Neve and J.-P. Seifert. Advances on access-driven cache attacks on AES. In Selected Areas in Cryptography, 13th International Workshop, SAC 2006, pages 147--162, August 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. D. A. Osvik, A. Shamir, and E. Tromer. Cache attacks and countermeasures: the case of AES. In Topics in Cryptology -- CT-RSA 2006, pages 1--20. Springer-Verlag, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. R. Owens and W. Wang. Non-interactive OS fingerprinting through memory de-duplication technique in virtual machines. In IEEE International Performance Computing and Communications Conference, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. D. Page. Partitioned cache architecture as a side-channel defence mechanism, 2005.Google ScholarGoogle Scholar
  36. C. Percival. Cache missing for fun and profit. In BSDCon 2005, 2005.Google ScholarGoogle Scholar
  37. M. Piotrowski and A. D. Joseph. Virtics: A system for privilege separation of legacy desktop applications. Technical Report EECS-2010-70, U.C. Berkeley, 2010.Google ScholarGoogle Scholar
  38. J.-J. Quisquater and D. Samyde. Electromagnetic analysis (EMA): Measures and counter-measures for smart cards. In Smart Card Programming and Security, International Conference on Research in Smart Cards, E-smart 2001, volume 2140 of LNCS, pages 200--210, September 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. T. Ristenpart, E. Tromer, H. Shacham, and S. Savage. Hey, you, get off of my cloud: Exploring information leakage in third-party compute clouds. In 16th ACM Conference on Computer and Communications Security, pages 199--212, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  40. R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), February 1978. Google ScholarGoogle ScholarDigital LibraryDigital Library
  41. J. Rutkowska and R. Wojtczuk. Qubes OS architecture. http://qubes-os.org, 2012.Google ScholarGoogle Scholar
  42. Xen 4.2: New scheduler parameters. http://blog.xen.org/index.php/2012/04/10/xen-4-2-new-scheduler-parameters-2/.Google ScholarGoogle Scholar
  43. E. Tromer, D. A. Osvik, and A. Shamir. Efficient cache attacks on AES, and countermeasures. Journal of Cryptology, 23(1):37--71, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  44. D. Tsafrir, Y. Etsion, and D. G. Feitelson. Secretly monopolizing the CPU without superuser privileges. In 16th USENIX Security Symposium, pages 1--18, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  45. A. J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inform. Theory, IT-13:260-269, April 1967. Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. M. Weiß, B. Heinz, and F. Stumpf. A cache timing attack on AES in virtualization environments. In 16th International Conference on Financial Cryptography and Data Security, February 2012.Google ScholarGoogle ScholarCross RefCross Ref
  47. Can I dedicate a cpu core (or cores) only for dom0? http://wiki.xen.org/wiki/XenCommonProblems#Can_I_dedicate_a_cpu_core_.28or_cores.29_only_for_dom0.3F.Google ScholarGoogle Scholar
  48. Y. Xu, M. Bailey, F. Jahanian, K. Joshi, M. Hiltunen, and R. Schlichting. An exploration of L2 cache covert channels in virtualized environments. In ACM Cloud Computing Security Workshop, pages 29--40, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  49. Y. Zhang, A. Juels, A. Oprea, and M. K. Reiter. Homealone: Co-residency detection in the cloud via side-channel analysis. In 2011 IEEE Symposium on Security and Privacy, pages 313--328, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  50. F. Zhou, M. Goel, P. Desnoyers, and R. Sundaram. Scheduler vulnerabilities and coordinated attacks in cloud computing. In IEEE International Symposium on Networking Computing and Applications, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Cross-VM side channels and their use to extract private keys

      Recommendations

      Reviews

      Andre C. M. Marien

      The discovery of a high-impact side-channel attack is bad news for vulnerable systems, as it affects their design in an unexpected way. Side channel-attacks have been studied for virtual machines with very limited success up to now. Co-hosting servers with different security requirements does not feel right (it's better to be safe than sorry: just don't do it!). Still, extracting keys across such a side channel is intuitively highly unlikely. Even so, this paper shows how it can be done. The side channel the authors use is neither new nor unexpected: the processor cache. A first hurdle is that the cache channel only leaks information if very short time intervals can be inspected. They needed to reduce the observation granularity down to what is required for meaningful measurements. Using inter-processor interrupts makes that possible. Even then, there is significant noise as the attack is executed on real-life software and operating systems. The authors assume knowledge of the software on the victim virtual machine (VM), so that they can train a classification engine that will detect the interesting parts and at the same time eliminate noise. In this study, a private key is the target. Using the private key leads to recognizable and different code sequences whether the key has a 0 or a 1 in a given position: square for a 0, and square and multiply for a 1. Analyzing a code fragment via its cache use results in a sequence of multiply, square, or unknown operations. This is the raw data that is collected multiple times and is used to construct the key. The first component in the chain producing the key from the basic trace data is a multiclass support vector machine. The next component uses hidden Markov models. Finally, the results are post-processed using domain knowledge. The outcome can best be described as strings with known elements and unknown positions. These strings are then aligned to form the full sequence of interest. In this paper, that result is a sequence of 1, 0, or unknown bits. The remaining unknowns are detected via brute force. The authors succeeded in ending with a very limited search space (less than 10,000 tries), with data obtained from just a few hours of data collection. The paper highlights the risks of shared environments convincingly. It also provides novel ideas for exploiting side channels and other partial, unreliable data leaks. Online Computing Reviews Service

      Access critical reviews of Computing literature here

      Become a reviewer for Computing Reviews.

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in
      • Published in

        cover image ACM Conferences
        CCS '12: Proceedings of the 2012 ACM conference on Computer and communications security
        October 2012
        1088 pages
        ISBN:9781450316514
        DOI:10.1145/2382196

        Copyright © 2012 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 16 October 2012

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article

        Acceptance Rates

        Overall Acceptance Rate1,261of6,999submissions,18%

        Upcoming Conference

        CCS '24
        ACM SIGSAC Conference on Computer and Communications Security
        October 14 - 18, 2024
        Salt Lake City , UT , USA

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader