Abstract
The latency gap between caches and main memory has been successfully exploited for recovering sensitive input to programs, such as cryptographic keys from implementation of AES and RSA. So far, there are no practical general-purpose countermeasures against this threat. In this paper we propose a novel method for automatically deriving upper bounds on the amount of information about the input that an adversary can extract from a program by observing the CPU’s cache behavior. At the heart of our approach is a novel technique for efficient counting of concretizations of abstract cache states that enables us to connect state-of-the-art techniques for static cache analysis and quantitative information-flow. We implement our counting procedure on top of the AbsInt TimingExplorer, one of the most advanced engines for static cache analysis. We use our tool to perform a case study where we derive upper bounds on the cache leakage of a 128-bit AES executable on an ARM processor. We also analyze this implementation with a commonly suggested (but until now heuristic) countermeasure applied, obtaining a formal account of the corresponding increase in security.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
AbsInt aiT Worst-Case Execution Time Analyzers, http://www.absint.com/a3/
Arm7tdmi datasheet, http://infocenter.arm.com/help/topic/com.arm.doc.ddi0234b/DDI0234.pdf
PolarSSL, http://polarssl.org/
The Haskell Programming Language, http://www.haskell.org/
The Open Source toolkit for SSL/TSL, http://www.openssl.org/
Acıiçmez, O., Brumley, B.B., Grabher, P.: New Results on Instruction Cache Attacks. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 110–124. Springer, Heidelberg (2010)
Acıiçmez, O., Koç, Ç.K.: Trace-Driven Cache Attacks on AES (Short Paper). In: Ning, P., Qing, S., Li, N. (eds.) ICICS 2006. LNCS, vol. 4307, pp. 112–121. Springer, Heidelberg (2006)
Acıiçmez, O., Koç, Ç.K., Seifert, J.-P.: Predicting Secret Keys Via Branch Prediction. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 225–242. Springer, Heidelberg (2007)
Acıiçmez, O., Schindler, W., Koç, Ç.K.: Cache Based Remote Timing Attack on the AES. In: Abe, M. (ed.) CT-RSA 2007. LNCS, vol. 4377, pp. 271–286. Springer, Heidelberg (2007)
Agat, J.: Transforming out Timing Leaks. In: POPL, pp. 40–53. ACM (2000)
Backes, M., Köpf, B., Rybalchenko, A.: Automatic Discovery and Quantification of Information Leaks. In: SSP, pp. 141–153. IEEE (2009)
Bernstein, D.J.: Cache-timing attacks on AES. Technical report (2005)
Braun, C., Chatzikokolakis, K., Palamidessi, C.: Quantitative notions of leakage for one-try attacks. In: MFPS. ENTCS, vol. 249, pp. 75–91. Elsevier (2009)
Brumley, D., Boneh, D.: Remote timing attacks are practical. Computer Networks 48(5), 701–716 (2005)
Clark, D., Hunt, S., Malacaria, P.: A static analysis for quantifying information flow in a simple imperative language. JCS 15(3), 321–371 (2007)
Coppens, B., Verbauwhede, I., Bosschere, K.D., Sutter, B.D.: Practical mitigations for timing-based side-channel attacks on modern x86 processors. In: SSP, pp. 45–60. IEEE (2009)
Cousot, P., Cousot, R.: Abstract interpretation: a unified lattice model for static analysis of programs by construction of approximation of fixpoints. In: POPL, pp. 238–252 (1977)
Cousot, P., Cousot, R., Mauborgne, L.: A Scalable Segmented Decision Tree Abstract Domain. In: Manna, Z., Peled, D.A. (eds.) Pnueli Festschrift. LNCS, vol. 6200, pp. 72–95. Springer, Heidelberg (2010)
Dziembowski, S., Pietrzak, K.: Leakage-Resilient Cryptography. In: FOCS, pp. 293–302. IEEE (2008)
Ferdinand, C., Martin, F., Wilhelm, R., Alt, M.: Cache behavior prediction by abstract interpretation. Science of Computer Programming 35(2), 163–189 (1999)
Grund, D.: Static Cache Analysis for Real-Time Systems – LRU, FIFO, PLRU. PhD thesis, Saarland University (2012)
Gullasch, D., Bangerter, E., Krenn, S.: Cache games - bringing access-based cache attacks on aes to practice. In: SSP, pp. 490–505. IEEE (2011)
Hedin, D., Sands, D.: Timing Aware Information Flow Security for a JavaCard-like Bytecode. ENTCS 141(1), 163–182 (2005)
Heusser, J., Malacaria, P.: Quantifying information leaks in software. In: ACSAC, pp. 261–269. ACM (2010)
Käsper, E., Schwabe, P.: Faster and Timing-Attack Resistant AES-GCM. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 1–17. Springer, Heidelberg (2009)
Kocher, P.: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Köpf, B., Basin, D.: An Information-Theoretic Model for Adaptive Side-Channel Attacks. In: CCS, pp. 286–296. ACM (2007)
Köpf, B., Dürmuth, M.: A Provably Secure And Efficient Countermeasure Against Timing Attacks. In: CSF, pp. 324–335. IEEE (2009)
Köpf, B., Mauborgne, L., Ochoa, M.: Automatic quantification of cache side-channels. Cryptology ePrint Archive, Report 2012/034 (2012)
Köpf, B., Rybalchenko, A.: Approximation and Randomization for Quantitative Information-Flow Analysis. In: CSF, pp. 3–14. IEEE (2010)
Köpf, B., Smith, G.: Vulnerability Bounds and Leakage Resilience of Blinded Cryptography under Timing Attacks. In: CSF, pp. 44–56. IEEE (2010)
Mauborgne, L., Rival, X.: Trace Partitioning in Abstract Interpretation Based Static Analyzers. In: Sagiv, M. (ed.) ESOP 2005. LNCS, vol. 3444, pp. 5–20. Springer, Heidelberg (2005)
Meng, Z., Smith, G.: Calculating bounds on information leakage using two-bit patterns. In: PLAS. ACM (2011)
Newsome, J., McCamant, S., Song, D.: Measuring channel capacity to distinguish undue influence. In: PLAS, pp. 73–85. ACM (2009)
Osvik, D.A., Shamir, A., Tromer, E.: Cache Attacks and Countermeasures: the Case of AES. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 1–20. Springer, Heidelberg (2006)
Page, D.: Theoretical use of cache memory as a cryptanalytic side-channel (2002)
Percival, C.: Cache missing for fun and profit. In: BSDCan (2005)
Reineke, J.: Caches in WCET Analysis. PhD thesis, Saarland University (2008)
Rényi, A.: On measures of entropy and information. In: Berkeley Symp. on Mathematics, Statistics and Probability, pp. 547–561 (1961)
Smith, G.: On the Foundations of Quantitative Information Flow. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol. 5504, pp. 288–302. Springer, Heidelberg (2009)
Tiri, K., Acıiçmez, O., Neve, M., Andersen, F.: An Analytical Model for Time-Driven Cache Attacks. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 399–413. Springer, Heidelberg (2007)
Wang, Z., Lee, R.B.: New cache designs for thwarting software cache-based side channel attacks. In: ISCA, pp. 494–505. ACM (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Köpf, B., Mauborgne, L., Ochoa, M. (2012). Automatic Quantification of Cache Side-Channels. In: Madhusudan, P., Seshia, S.A. (eds) Computer Aided Verification. CAV 2012. Lecture Notes in Computer Science, vol 7358. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31424-7_40
Download citation
DOI: https://doi.org/10.1007/978-3-642-31424-7_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31423-0
Online ISBN: 978-3-642-31424-7
eBook Packages: Computer ScienceComputer Science (R0)