A smart random code injection to mask power analysis based side channel attacks

ABSTRACT

One of the security issues in embedded system is the ability of an adversary to perform side channel attacks. Power analysis attacks are often very successful, where the power sequence dissipated by the system is observed and analyzed to predict secret keys. In this paper we show a processor architecture, which automatically detects the execution of the most common encryption algorithms, starts to scramble the power waveform by adding randomly placed instructions with random register accesses, and stops injecting instructions when it is safe to do so. Our technique prevents both Simple Power Analysis (SPA) and Differential Power Analysis (DPA). This approach has less overheads compared to previous solutions and avoids software instrumentation, allowing programmers with no special knowledge to use the system. Our processor model costs an additional area of 1.2%, and an average of 25% in runtime and 28.5% in energy overheads for industry standard cryptographic algorithms.

REFERENCES

• 1: Sourcebank. url: http://archive.devx.com/sourcebank.
• 2: The PEAS Team. ASIP Meister, 2002. Available at: http://www.edameister.org/asipmeister.
• 3: Mehdi-Laurent Akkar , Régis Bevan , Paul Dischamp , Didier Moyart, Power Analysis, What Is Now Possible..., Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.489-502, December 03-07, 2000
• 4: M. Barbosa and D. Page. On the automatic construction of indistinguishable operations. In Cryptography And Coding, pages 233--247. Springer-Verlag LNCS 3796, November 2005.
• 5: E. Brier, C. Clavier, and F. Olivier. Correlation power analysis with a leakagemodel. In CHES, pages 16--29, 2004.
• 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: 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
• 8: Christophe Clavier , Jean-Sébastien Coron , Nora Dabbous, Differential Power Analysis in the Presence of Hardware Countermeasures, Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, p.252-263, August 17-18, 2000
• 9: Jean-Sébastien Coron , Louis Goubin, On Boolean and Arithmetic Masking against Differential Power Analysis, Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, p.231-237, August 17-18, 2000
• 10: J. Daemen and V. Rijmen. Resistance against implementation attacks: a comparative study of the AES proposals, 1999.
• 11: B. S. David, C. Lap-Wai, and M. C. William. Cryptographic architecture with random instruction masking to thwart differential power analysis. U.S. Patent 20050271202, 2005.
• 12: C. Gebotys. A Table Masking Countermeasure for Low-Energy Secure Embedded Systems. IEEE Trans. on VLSI, 14(7):740--753, 2006.
• 13: Catherine H. Gebotys , Robert J. Gebotys, Secure Elliptic Curve Implementations: An Analysis of Resistance to Power-Attacks in a DSP Processor, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.114-128, August 13-15, 2002
• 14: Ann Gordon-Ross , Frank Vahid, Frequent loop detection using efficient non-intrusive on-chip hardware, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951728]
• 15: Louis Goubin , Jacques Patarin, DES and Differential Power Analysis (The "Duplication" Method), Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, p.158-172, August 12-13, 1999
• 16: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 17: J. Irwin , D. Page , N. P. Smart, Instruction Stream Mutation for Non-Deterministic Processors, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors, p.286, July 17-19, 2002
• 18: A. Janapsatya, A. Ignjatovic, and S. Parameswaran. Exploiting statistical information for implementation of instruction scratch memory in embedded system. IEEE Trans. on VLSI, 14(8):816--829, 2006.
• 19: S. Mangard. A Simple Power--Analysis (SPA) Attack on Implementations of the AES Key Expansion. In P. J. Lee and C. H. Lim, editors, icisc 2002, volume 2587 of Lecture Notes in Computer Science, pages 343--358. Springer, 2003.
• 20: David May , Henk L. Muller , Nigel P. Smart, Non-deterministic Processors, Proceedings of the 6th Australasian Conference on Information Security and Privacy, p.115-129, July 11-13, 2001
• 21: David May , Henk L. Muller , Nigel P. Smart, Random Register Renaming to Foil DPA, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.28-38, May 14-16, 2001
• 22: Matthew C. Merten , Andrew R. Trick , Ronald D. Barnes, An Architectural Framework for Runtime Optimization, IEEE Transactions on Computers, v.50 n.6, p.567-589, June 2001 [doi>10.1109/12.931894]
• 23: Thomas S. Messerges , Ezzat A. Dabbish , Robert H. Sloan, Examining Smart-Card Security under the Threat of Power Analysis Attacks, IEEE Transactions on Computers, v.51 n.5, p.541-552, May 2002 [doi>10.1109/TC.2002.1004593]
• 24: Radu Muresan , Catherine Gebotys, Current flattening in software and hardware for security applications, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016773]
• 25: Elisabeth Oswald , Manfred Aigner, Randomized Addition-Subtraction Chains as a Countermeasure against Power Attacks, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.39-50, May 14-16, 2001
• 26: E. Oswald, S. Mangard, C. Herbst, and S. Tillich. Practical Second-Order DPA Attacks for Masked Smart Card Implementations of Block Ciphers. In ct-rsa 2006, pages 192--207. Springer, 2006.
• 27: Paul Bourke. Cross Correlation: AutoCorrelation -- 2D Pattern Identification. url:http://astronomy.swin.edu.au/ pbourke/other/correlate/index.html, 1996.
• 28: J. J. Paul Kocher and B. Jun. Differential Power Analysis. 1998. First article on DPA.
• 29: 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
• 30: Girish B. Ratanpal , Ronald D. Williams , Travis N. Blalock, An On-Chip Signal Suppression Countermeasure to Power Analysis Attacks, IEEE Transactions on Dependable and Secure Computing, v.1 n.3, p.179-189, July 2004 [doi>10.1109/TDSC.2004.25]
• 31: H. Saputra , N. Vijaykrishnan , M. Kandemir , M. J. Irwin , R. Brooks , S. Kim , W. Zhang, Masking the Energy Behavior of DES Encryption, Proceedings of the conference on Design, Automation and Test in Europe, p.10084, March 03-07, 2003
• 32: Francois-Xavier Standaert , Eric Peeters , Jean-Jacques Quisquater, On the Masking Countermeasure and Higher-Order Power Analysis Attacks, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume I, p.562-567, April 04-06, 2005 [doi>10.1109/ITCC.2005.213]
• 33: K. Tiri , D. Hwang , A. Hodjat , B. Lai , S. Yang , P. Schaumont , I. Verbauwhede, A side-channel leakage free coprocessor IC in 0.18µm CMOS for embedded AES-based cryptographic and biometric processing, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065639]
• 34: J. Waddle and D. Wagner. Towards efficient second-order power analysis. In CHES, pages 1--15, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

General Terms:
Design, Measurement, Security

Keywords:
cross correlation, power analysis, random instruction injection, side channel attack, signture identification