Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

MemJam: A False Dependency Attack Against Constant-Time Crypto Implementations

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

Cache attacks exploit memory access patterns of cryptographic implementations. Constant-time implementation techniques have become an indispensable tool in fighting cache timing attacks. These techniques engineer the memory accesses of cryptographic operations to follow a uniform key independent pattern. However, the constant-time behavior is dependent on the underlying architecture, which can be highly complex and often incorporates unpublished features. The CacheBleed attack targets cache bank conflicts and thereby invalidates the assumption that microarchitectural side-channel adversaries can only observe memory with cache line granularity. In this work, we propose MemJam, which utilizes 4K Aliasing to establish a side-channel attack that exploits false dependency of memory read-after-write events and provides a high quality intra cache line timing channel. As a proof of concept, we demonstrate the first key recovery attacks on constant-time implementations of all symmetric block ciphers supported in the current intel integrated performance primitives (Intel IPP) cryptographic library: triple DES, AES and SM4. Further, we demonstrate the first intra cache level timing attack on SGX by reproducing the AES key recovery results on an enclave that performs encryption using the aforementioned constant-time implementation of AES. Our results show that we can not only use this side channel to efficiently attack memory dependent cryptographic operations but also to bypass proposed protections. Compared to CacheBleed, which is limited to older processor generations, MemJam is the first intra cache level attack applicable to all major Intel processors including the latest generations and also applies to the SGX extension.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19

Similar content being viewed by others

Notes

  1. LD_BLOCKS_PARTIAL.ADDRESS_ALIAS Performance Monitoring Unit (PMU) event counts the number of times reads were blocked.

  2. Top-Down Characterization is a hierarchical organization of event-based metrics that identifies the dominant performance bottlenecks in an application.

  3. Patents investigated by Intel verify the importance of SM4 [32, 72, 75].

  4. EMVCo is an industry consortium managing a payment system standard that was originally created by EuroPay, MasterCard and Visa (resulting in the EMV trademark). Current members include American Express, MasterCard, Visa and UnionPay [26].

References

  1. Acıiçmez, O., Brumley, B.B., Grabher, P.: New results on instruction cache attacks. In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer (2010)

  2. Acıiçmez, O., Gueron, S., Seifert, J.P.: New Branch Prediction Vulnerabilities in OpenSSL and Necessary Software Countermeasures. In: Galbraith, S.D. (eds.) Cryptography and Coding. Cryptography and Coding 2007. Lecture Notes in Computer Science, vol. 4887, pp. 185–203. Springer, Berlin, Heidelberg (2007)

  3. Acıiçmez, O., Koç, Ç.K., Seifert, J.P.: Predicting secret keys via branch prediction. In: Cryptographers Track at the RSA Conference. Springer (2007)

  4. Aciicmez, O., Seifert, J.P.: Cheap hardware parallelism implies cheap security. In: FDTC 2007. Workshop on Fault Diagnosis and Tolerance in Cryptography, 2007. IEEE (2007)

  5. Agner: The microarchitecture of Intel, AMD and VIA CPUs: An optimization guide for assembly programmers and compiler makers. http://www.agner.org/optimize/microarchitecture.pdf

  6. Allan, T., Brumley, B.B., Falkner, K., van de Pol, J., Yarom, Y.: Amplifying side channels through performance degradation. In: Annual Computer Security Applications Conference (ACSAC) (2016)

  7. Almeida, J.B., Barbosa, M., Barthe, G., Dupressoir, F., Emmi, M.: Verifying constant-time implementations. In: USENIX Security Symposium, pp. 53–70 (2016)

  8. Andrysco, M., Kohlbrenner, D., Mowery, K., Jhala, R., Lerner, S., Shacham, H.: On subnormal floating point and abnormal timing. In: 2015 IEEE Symposium on Security and Privacy (SP). IEEE (2015)

  9. Aweke, Z.B., Austin, T.: Ozone: efficient execution with zero timing leakage for modern microarchitectures. Preprint. arXiv:1703.07706 (2017)

  10. BearSSL: BearSSL constant-time crypto. https://www.bearssl.org/constanttime.html

  11. Benger, N., Van De Pol, J., Smart, N.P., Yarom, Y.: Ooh Aah... just a little bit: a small amount of side channel can go a long way. In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer (2014)

  12. Bhargavan, K., Leurent, G.: On the practical (in-) security of 64-bit block ciphers: collision attacks on HTTP over TLS and OpenVPN. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 456–467. ACM (2016)

  13. Bonneau, J., Mironov, I.: Cache-collision timing attacks against AES. In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer (2006)

  14. Brasser, F., Müller, U., Dmitrienko, A., Kostiainen, K., Capkun, S., Sadeghi, A.R.: Software grand exposure: SGX cache attacks are practical. In: 11th USENIX Workshop on Offensive Technologies (WOOT 17). USENIX Association, Vancouver (2017). https://www.usenix.org/conference/woot17/workshop-program/presentation/brasser

  15. Brickell, E., Graunke, G., Neve, M., Seifert, J.P.: Software mitigations to hedge AES against cache-based software side channel vulnerabilities. In: IACR Cryptology ePrint Archive (2006)

  16. Brickell, E., Graunke, G., Seifert, J.P.: Mitigating cache/timing based side-channels in AES and RSA software implementations. In: RSA Conference 2006 Session DEV-203 (2006)

  17. Briongos, S., Irazoqui, G., Malagón, P., Eisenbarth, T.: CacheShield: protecting legacy processes against cache attacks. Preprint. arXiv:1709.01795 (2017)

  18. Brumley, D., Boneh, D.: Remote timing attacks are practical. Comput. Netw. 48(5), 701–716 (2005)

    Article  Google Scholar 

  19. Carluccio, D.: Electromagnetic side channel analysis for embedded crypto devices. Master’s Thesis, Ruhr Universität Bochum (2005)

  20. Chen, S., Zhang, X., Reiter, M.K., Zhang, Y.: Detecting privileged side-channel attacks in shielded execution with Déjá Vu. In: Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security. ACM (2017)

  21. Costan, V., Lebedev, I.A., Devadas, S.: Sanctum: minimal hardware extensions for strong software isolation. In: USENIX Security Symposium (2016)

  22. Daemen, J., Rijmen, V.: The Design of Rijndael: AES—The Advanced Encryption Standard. Springer, Berlin (2013)

    MATH  Google Scholar 

  23. Dierks, T., Rescorla, E.: The transport layer security (TLS) protocol version 1.2. RFC 5246 (2008). https://www.ietf.org/rfc/rfc5246.txt

  24. Diffie, W., Ledin, G.: SMS4 encryption algorithm for wireless networks. IACR Cryptology ePrint Archive (2008)

  25. Doychev, G., Köpf, B.: Rigorous analysis of software countermeasures against cache attacks. In: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation (2017)

  26. EMVCo: EMVCo overview. https://www.emvco.com/about/overview/

  27. EMVCo: Integrated Circuit Card Specifications for Payment Systems—Book 2: Security and Key Management, Version 4.3 (2011)

  28. Ge, Q., Yarom, Y., Cock, D., Heiser, G.: A Survey of microarchitectural timing attacks and countermeasures on contemporary hardware. IACR Cryptology ePrint Archive 2016/613 (2016)

  29. Ge, Q., Yarom, Y., Li, F., Heiser, G.: Contemporary processors are leaky–and there is nothing you can do about it. The Computing Research Repository (2016)

  30. Glowacz, C., Grosso, V., Poussier, R., Schueth, J., Standaert, F.X.: Simpler and more efficient rank estimation for side-channel security assessment. In: International Workshop on Fast Software Encryption, pp. 117–129. Springer (2015)

  31. Gruss, D., Maurice, C., Wagner, K., Mangard, S.: Flush\(+\)Flush: A Fast and Stealthy Cache Attack. In: Caballero, J., Zurutuza, U., Rodríguez, R. (eds.) Detection of Intrusions and Malware, and Vulnerability Assessment. DIMVA 2016. Lecture Notes in Computer Science, vol. 9721, pp. 279–299. Springer, Cham (2016)

  32. Gueron, S., Krasnov, V.: SM4 acceleration processors, methods, systems, and instructions. US Patent 9,513,913 (2016). https://www.google.com/patents/US9513913

  33. Gullasch, D., Bangerter, E., Krenn, S.: Cache games-bringing access-based cache attacks on AES to practice. In: 2011 IEEE Symposium on Security and Privacy (SP). IEEE (2011)

  34. Hankerson, D., López Hernandez, J., Menezes, A.: Software Implementation of Elliptic Curve Cryptography over Binary Fields. In: Koç, Ç.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems – CHES 2000. CHES 2000. Lecture Notes in Computer Science, vol. 1965, pp. 1–24 . Springer, Berlin, Heidelberg (2000)

  35. Inci, M.S., Gülmezoglu, B., Apecechea, G.I., Eisenbarth, T., Sunar, B.: Seriously, get off my cloud! cross-VM RSA Key Recovery in a Public Cloud. IACR Cryptology ePrint Archive (2015)

  36. Inci, M.S., Gulmezoglu, B., Irazoqui, G., Eisenbarth, T., Sunar, B.: Cache attacks enable bulk key recovery on the cloud. In: International Conference on Cryptographic Hardware and Embedded Systems. Springer (2016)

  37. Intel IPP linkage models-quick reference guide. https://intel.ly/2tGjLCw

  38. Intel: intel(R) software guard extensions for Linux* OS. https://github.com/01org/linux-sgx

  39. Intel: Intel 64 and IA-32 architectures optimization reference manual. https://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html

  40. Intel: Intel 64 and IA-32 architectures software developer manuals. https://software.intel.com/en-us/articles/intel-sdm

  41. Intel: Pin, dynamic binary instrumentation tool. https://software.intel.com/en-us/articles/pin-a-dynamic-binary-instrumentation-tool

  42. Symmetric cryptography primitive functions. https://software.intel.com/en-us/ipp-crypto-reference-symmetric-cryptography-primitive-functions

  43. Understanding CPU dispatching in the intel IPP libraries. https://intel.ly/2MxXkWY

  44. Irazoqui, G., Cong, K., Guo, X., Khattri, H., Kanuparthi, A., Eisenbarth, T., Sunar, B.: Did we learn from LLC side channel attacks? a cache leakage detection tool for crypto libraries. Preprint. arXiv:1709.01552 (2017)

  45. Irazoqui, G., Eisenbarth, T., Sunar, B.: S\$A: a shared cache attack that works across cores and defies VM sandboxing—and its application to AES. In: 2015 IEEE Symposium on Security and Privacy (SP) (2015)

  46. Irazoqui, G., Eisenbarth, T., Sunar, B.: MASCAT: stopping microarchitectural attacks before execution. IACR Cryptology ePrint Archive (2016)

  47. Kayaalp, M., Khasawneh, K.N., Esfeden, H.A., Elwell, J., Abu-Ghazaleh, N., Ponomarev, D., Jaleel, A.: RIC: relaxed inclusion caches for mitigating LLC side-channel attacks. In: Proceedings of the 54th Annual Design Automation Conference 2017. ACM (2017)

  48. Koç, C.K.: Analysis of sliding window techniques for exponentiation. Comput. Math. Appl. 30(10), 17–24 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  49. Kocher, P., Jaffe, J., Jun, B., Rohatgi, P.: Introduction to differential power analysis. J. Cryptogr. Eng. 1(1), 5–27 (2011)

    Article  Google Scholar 

  50. Lee, S., Shih, M.W., Gera, P., Kim, T., Kim, H., Peinado, M.: Inferring fine-grained control flow inside SGX enclaves with branch shadowing. Preprint. arXiv:1611.06952 (2016)

  51. Liu, F., Ge, Q., Yarom, Y., Mckeen, F., Rozas, C., Heiser, G., Lee, R.B.: Catalyst: defeating last-level cache side channel attacks in cloud computing. In: 2016 IEEE Symposium on High Performance Computer Architecture (HPCA) (2016)

  52. Marr, D., Binns, F., Hill, D., Hinton, G., Koufaty, D., et al.: Hyper-threading technology in the netburst® microarchitecture. 14th Hot Chips (2002)

  53. Moghimi, A., Eisenbarth, T., Sunar, B.: MemJam: a false dependency attack against constant-time crypto implementations. In: CT-RSA 2018. Springer (2018). arXiv:1711.08002

  54. Moghimi, A., Irazoqui, G., Eisenbarth, T.: Cachezoom: how SGX amplifies the power of cache attacks. Preprint. arXiv:1703.06986 (2017)

  55. National Institute of Standards and Technology: Federal Information Processing Standards (FIPS) Publication 46-3—Data Encryption Standard (DES) (1999). https://csrc.nist.gov/csrc/media/publications/fips/46/3/archive/1999-10-25/documents/fips46-3.pdf

  56. National Institute of Standards and Technology: Update to current use and deprecation of TDEA (2017). https://csrc.nist.gov/News/2017/Update-to-Current-Use-and-Deprecation-of-TDEA

  57. Nguyen, P.H., Rebeiro, C., Mukhopadhyay, D., Wang, H.: Improved differential cache attacks on SMS4. In: International Conference on Information Security and Cryptology, pp. 29–45. Springer (2012)

  58. Osvik, D.A., Shamir, A., Tromer, E.: Cache attacks and countermeasures: the case of AES. In: Cryptographers Track at the RSA Conference (2006)

  59. Page, D.: Defending against cache-based side-channel attacks. Inf. Secur. Tech. Rep. 8(1), 30–44 (2003). https://doi.org/10.1016/S1363-4127(03)00104-3. http://www.sciencedirect.com/science/article/pii/S1363412703001043

  60. Rane, A., Lin, C., Tiwari, M.: Raccoon: closing digital side-channels through obfuscated execution. In: USENIX Security Symposium, pp. 431–446 (2015)

  61. Rane, A., Lin, C., Tiwari, M.: Secure, precise, and fast floating-point operations on x86 processors. In: USENIX Security Symposium, pp. 71–86 (2016)

  62. Ristenpart, T., Tromer, E., Shacham, H., Savage, S.: Hey, you, get off of my cloud: exploring information leakage in third-party compute clouds. In: Proceedings of the 16th ACM Conference on Computer and Communications Security. ACM (2009)

  63. Schimmel, C.: UNIX Systems for Modern Architectures: Symmetric Multiprocessing and Caching for Kernel Programmers. Addison-Wesley, Reading (1994)

    Google Scholar 

  64. Shih, M.W., Lee, S., Kim, T., Peinado, M.: T-SGX: eradicating controlled-channel attacks against enclave programs. In: Proceedings of the 2017 Annual Network and Distributed System Security Symposium (NDSS), San Diego (2017)

  65. Sinha, R., Rajamani, S., Seshia, S.A.: A compiler and verifier for page access oblivious computation. Technical Report, Technical Report UCB/EECS-2017-124, EECS Department, University of California, Berkeley (2017)

  66. Sullivan, D., Arias, O., Meade, T., Jin, Y.: Microarchitectural minefields: 4K-aliasing covert channel and multi-tenant detection in IaaS clouds (2018)

  67. Tromer, E., Osvik, D.A., Shamir, A.: Efficient cache attacks on AES, and countermeasures. J. Cryptol. 23(1), 37–71 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  68. Tsunoo, Y., Saito, T., Suzaki, T., Shigeri, M., Miyauchi, H.: Cryptanalysis of DES implemented on computers with cache. In: International Workshop on Cryptographic Hardware and Embedded Systems. Springer (2003)

  69. Van Bulck, J., Weichbrodt, N., Kapitza, R., Piessens, F., Strackx, R.: Telling your secrets without page faults: stealthy page table-based attacks on enclaved execution. In: Proceedings of the 26th USENIX Security Symposium. USENIX Association (2017)

  70. Wang, S., Wang, P., Liu, X., Zhang, D., Wu, D.: CacheD: identifying cache-based timing channels in production software. In: 26th USENIX Security Symposium (USENIX Security 17), pp. 235–252. USENIX Association, Vancouver (2017). https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/wang-shuai

  71. Webster, A., Tavares, S.E.: On the design of S-boxes. In: Advances in Cryptology-CRYPTO’85: Proceedings. Springer (1986)

  72. Wolrich, G., Gopal, V., Yap, K., Feghali, W.: SMS4 acceleration processors, methods, systems, and instructions (2016). https://www.google.com/patents/US9361106. US Patent 9,361,106

  73. Xu, M., Thi, L., Phan, X., Choi, H.Y., Lee, I.: vCAT: Dynamic cache management using CAT virtualization. In: Real-Time and Embedded Technology and Applications Symposium (RTAS), 2017 IEEE. IEEE (2017)

  74. Xu, Y., Cui, W., Peinado, M.: Controlled-channel attacks: deterministic side channels for untrusted operating systems. In: 2015 IEEE Symposium on Security and Privacy (SP), pp. 640–656. IEEE (2015)

  75. Yap, K., Wolrich, G., Satpathy, S., Gulley, S., Gopal, V., Mathew, S., Feghali, W.: SMS4 acceleration hardware. US Patent 9,503,256 (2016). https://www.google.com/patents/US9503256

  76. Yarom, Y., Falkner, K.: FLUSH+RELOAD: a high resolution, low noise, L3 cache side-channel attack. In: USENIX Security (2014)

  77. Yarom, Y., Genkin, D., Heninger, N.: CacheBleed: a timing attack on OpenSSL constant-time RSA. J. Cryptogr. Eng. 7(2), 99–112 (2017)

    Article  Google Scholar 

  78. Zhang, T., Zhang, Y., Lee, R.B.: Cloudradar: a real-time side-channel attack detection system in clouds. In: International Symposium on Research in Attacks, Intrusions, and Defenses. Springer (2016)

  79. Zhang, Y., Juels, A., Reiter, M.K., Ristenpart, T.: Cross-VM side channels and their use to extract private keys. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. ACM (2012)

  80. Zhou, Z., Reiter, M.K., Zhang, Y.: A software approach to defeating side channels in last-level caches. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. ACM (2016)

Download references

Acknowledgements

This work is supported by the National Science Foundation, under Grant CNS-1618837.

Author information

Authors and Affiliations

  1. Worcester Polytechnic Institute, Worcester, MA, USA

    Ahmad Moghimi & Berk Sunar

  2. University of Lübeck, Lübeck, Germany

    Jan Wichelmann & Thomas Eisenbarth

Authors
  1. Ahmad Moghimi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan Wichelmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Thomas Eisenbarth
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Berk Sunar
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ahmad Moghimi.

Ethics declarations

Responsible disclosure

We have informed the Intel Product Security Incident Response Team of our findings. They have acknowledged the receipt and confirmed a work-in-progress patch for IPP library. Here is the time line for the responsible disclosure process: (1) 08/02/2017: We informed our findings to the Intel Product Security Incident Response Team (Intel PSIRT). (2) 08/04/2017: Intel PSIRT acknowledged the receipt. (3) 11/07/2017:Safe2Encrypt_RIJ128 was removed from the SGX SDK. (4) 11/17/2017: Intel PSIRT confirmed a work-in-progress patch for IPP library (CVE-2017-5737). (5) 05/10/2018: Intel PSIRT published an update for IPP library (CVE-2018-3691).

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This is an extended version of the paper that was presented in part at the RSA Conference Cryptographers Track (CT-RSA 2018, Springer LNCS) [53].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Moghimi, A., Wichelmann, J., Eisenbarth, T. et al. MemJam: A False Dependency Attack Against Constant-Time Crypto Implementations. Int J Parallel Prog 47, 538–570 (2019). https://doi.org/10.1007/s10766-018-0611-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10766-018-0611-9

Keywords

Search

Navigation