An information-theoretic model for adaptive side-channel attacks

ABSTRACT

We present a model of adaptive side-channel attacks which we combine with information-theoretic metrics to quantify the information revealed to an attacker. This allows us to express an attacker's remaining uncertainty about a secret as a function of the number of side-channel measurements made. We present algorithms and approximation techniques for computing this measure. We also give examples of how they can be used to analyze the resistance of hardware implementations of cryptographic functions to both timing and power attacks.

REFERENCES

• 1: Johan Agat, Transforming out timing leaks, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.40-53, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325702]
• 2: G. Barthe, T. Rezk, and M. Warnier. Preventing Timing Leaks Through Transactional Branching Instructions. In Proc. QAPL '05, ENTCS, pages 33--55. Elsevier.
• 3: G. Basharin. On a Statistical Estimate for the Entropy of a Sequence of Independent Random Variables. Theory Probab. Appl., 47:333--336, 1959.
• 4: Tuǧkan Batu , Sanjoy Dasgupta , Ravi Kumar , Ronitt Rubinfeld, The complexity of approximating entropy, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510005]
• 5: Richard Bird, Introduction to Functional Programming, Pearson Education, 1998
• 6: 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
• 7: C. Cachin. Entropy Measures and Unconditional Security in Cryptography. PhD thesis, ETH Züurich, 1997.
• 8: J. Cathalo, F. Koeune, and J.-J. Quisquater. A New Type of Timing Attack: Application to GPS. In Proc. CARDIS '03, LNCS 2779, pages 291--303. Springer.
• 9: Suresh Chari , Charanjit S. Jutla , Josyula R. Rao , Pankaj Rohatgi, Towards Sound Approaches to Counteract Power-Analysis Attacks, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.398-412, August 15-19, 1999
• 10: Suresh Chari , Josyula R. Rao , Pankaj Rohatgi, Template Attacks, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.13-28, August 13-15, 2002
• 11: David Clark , Sebastian Hunt , Pasquale Malacaria, Quantitative Information Flow, Relations and Polymorphic Types, Journal of Logic and Computation, v.15 n.2, p.181-199, April 2005 [doi>10.1093/logcom/exi009]
• 12: Michael R. Clarkson , Andrew C. Myers , Fred B. Schneider, Belief in Information Flow, Proceedings of the 18th IEEE workshop on Computer Security Foundations, p.31-45, June 20-22, 2005 [doi>10.1109/CSFW.2005.10]
• 13: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 14: Marc Davio , J. P. Deschamps , A. Thayse, Digital Systems with Algorithm Implementation, John Wiley & Sons, Inc., New York, NY, 1983
• 15: Karine Gandolfi , Christophe Mourtel , Francis Olivier, Electromagnetic Analysis: Concrete Results, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.251-261, May 14-16, 2001
• 16: J. W. Gray. Toward a Mathematical Foundation for Information Flow Security. JCS, 1(3-4):255--294, 1992.
• 17: D. Hedin and D. Sands. Timing Aware Information Flow Security for a JavaCard-like Bytecode. In BYTECODE '05, ENTCS. Elsevier.
• 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: Paul C. Kocher , Joshua Jaffe , Benjamin Jun, Differential Power Analysis, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.388-397, August 15-19, 1999
• 20: B. Köpf and D. Basin. Timing-Sensitive Information Flow Analysis for Synchronous Systems. In Proc. ESORICS '06, LNCS 4189, pages 243--262. Springer.
• 21: Gavin Lowe, Quantifying Information Flow, Proceedings of the 15th IEEE workshop on Computer Security Foundations, p.18, June 24-26, 2002
• 22: J. L. Massey. Guessing and Entropy. In Proc. IEEE Int. Symp. on Info. Th. '94, page 204. IEEE.
• 23: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 24: Thomas S. Messerges , Ezzy A. Dabbish , Robert H. Sloan, Power Analysis Attacks of Modular Exponentiation in Smartcards, Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.144-157, August 12-13, 1999
• 25: S. Micali and L. Reyzin. Physically Observable Cryptography (Extended Abstract). In Proc. TCC '04, LNCS 2951, pages 278--296. Springer.
• 26: J. K. Millen. Covert Channel Capacity. In Proc. IEEE Symp. on Security and Privacy '87, pages 60--66. IEEE.
• 27: Farid N. Najm, A survey of power estimation techniques in VLSI circuits, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.446-455, Dec. 1994 [doi>10.1109/92.335013]
• 28: D. A. Osvik, A. Shamir, and E. Tromer. Cache Attacks and Countermeasures: the Case of AES. In Proc. CT-RSA '06, LNCS 3860, pages 1--20. Springer.
• 29: Alessandra Di Pierro , Chris Hankin , Herbert Wiklicky, Approximate Non-Interference, Proceedings of the 15th IEEE workshop on Computer Security Foundations, p.3, June 24-26, 2002
• 30: John O. Pliam, On the Incomparability of Entropy and Marginal Guesswork in Brute-Force Attacks, Proceedings of the First International Conference on Progress in Cryptology, p.67-79, December 10-13, 2000
• 31: Jean-Jacques Quisquater , David Samyde, ElectroMagnetic Analysis (EMA): Measures and Counter-Measures for Smart Cards, Proceedings of the International Conference on Research in Smart Cards: Smart Card Programming and Security, p.200-210, September 19-21, 2001
• 32: Andrei Sabelfeld , David Sands, Probabilistic Noninterference for Multi-Threaded Programs, Proceedings of the 13th IEEE workshop on Computer Security Foundations, p.200, July 03-05, 2000
• 33: Patrick Schaumont , Doris Ching , Ingrid Verbauwhede, An interactive codesign environment for domain-specific coprocessors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.1, p.70-87, January 2006 [doi>10.1145/1124713.1124719]
• 34: W. Schindler, K. Lemke, and C. Paar. A Stochastic Model for Differential Side-Channel Cryptanalysis. In Proc. CHES '05, LNCS 3659, pages 30--46. Springer.
• 35: C. Shannon. A Mathematical Theory of Communication. Bell System Technical Journal, 27:379--423 and 623--656, July and October 1948.
• 36: Geoffrey Smith , Dennis Volpano, Secure information flow in a multi-threaded imperative language, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.355-364, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268975]
• 37: F.-X. Standaert, E. Peeters, C. Archambeau, and J.-J. Quisquater. Towards Security Limits in Side-Channel Attacks. In Proc. CHES '06, LNCS 4249, pages 30--45. Springer.
• 38: T. Tolstrup. Language-based Security for VHDL. PhD thesis, Technical University of Denmark, 2007.
• 39: J. Wittbold and D. Johnson. Information flow in nondeterministic systems. In Proc. IEEE Symp. on Security and Privacy '90, pages 144--161. IEEE.
• 40: Lin Zhong , S. Ravi , A. Raghunathan , N. K. Jha, Power estimation for cycle-accurate functional descriptions of hardware, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.668-675, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382659]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Security