Strength of two data encryption standard implementations under timing attacks

ABSTRACT

We study the vulnerability of two implementations of the Data Encryption Standard (DES) cryptosystem under a timing attack. A timing attack is a method, recently proposed by Paul Kocher, that is designed to break cryptographic systems. It exploits the engineering aspects involved in the implementation of cryptosystems and might succeed even against cryptosys-tems that remain impervious to sophisticated cryptanalytic techniques. A timing attack is, essentially, a way of obtaining some users private information by carefully measuring the time it takes the user to carry out cryptographic operations. In this work, we analyze two implementations of DES. We show that a timing attack yields the Hamming weight of the key used by both DES implementations. Moreover, the attack is computationally inexpensive. We also show that all the design characteristics of the target system, necessary to carry out the timing attack, can be inferred from timing measurements.

REFERENCES

• 1: BIHAM,E.AND SHAMIR, A. 1991. Differential cryptanalysis of DES-like cryptosystems. J. Cryptology 4, 1, 3-72.
• 2: Eli Biham , Adi Shamir, Differential Cryptanalysis of the Full 16-Round DES, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.487-496, August 16-20, 1992
• 3: BIHAM,E.AND SHAMIR, A. 1997. Differential fault analysis of secret key cryptosystems. CS0910. Electrical Engineering Department, Technion:Israel Institute of Technology, Haifa, Israel.
• 4: BONEH, D., DEMILLO,R.A.,AND LIPTON, R. J. 1997. On the importance of checking cryptographic protocols for faults. In Proceedings of the Conference on Advances in Cryptology (EUROCRYPT'97), W. Fumy, Ed. Springer-Verlag, New York, 37-51.
• 5: CHAUM, D. 1983. Blind signatures for untraceable payments. In Proceedings of the Conference on Advances in Cryptology (CRYPTO'82, Santa Barbara, CA), D. Chaum, R. L. Rivest, and A. T. Sherman, Eds. Plenum Press, New York, NY, 199-203.
• 6: Jean-François Dhem , François Koeune , Philippe-Alexandre Leroux , Patrick Mestré , Jean-Jacques Quisquater , Jean-Louis Willems, A Practical Implementation of the Timing Attack, Proceedings of the The International Conference on Smart Card Research and Applications, p.167-182, September 14-16, 1998
• 7: DIFFIE,W.AND HELLMAN, M. E. 1976. New directions in cryptography. IEEE Trans. Inf. Theor. 22, 6 (Nov.), 644-654.
• 8: Erin English , Scott Hamilton, Network Security Under Siege: The Timing Attack, Computer, v.29 n.3, p.95-97, March 1996 [doi>10.1109/2.485898 ]
• 9: FELLER, W. 1966. An Introduction to Probability Theory and its Applications. 2nd ed. John Wiley & Sons, Inc., New York, NY.
• 10: Helena Handschuh , Howard M. Heys, A Timing Attack on RC5, Proceedings of the Selected Areas in Cryptography, p.306-318, August 17-18, 1998
• 11: HAZEWINKEL, M., Ed 1988. Encyclopedia of Mathematics: An updated and annotated translation of the Soviet "Mathematical Encyclopaedia". Encyclopedia of Mathematics, vol. 1. Kluwer Academic Publishers, Hingham, MA.
• 12: HEIDENSTROM, K. 1995. FAQ/application notes: Timing on the PC family under DOS. (ftp://garbo.uwasa.fi/pc/programming/pctim003.zip).
• 13: Helena Handschuh , Howard M. Heys, A Timing Attack on RC5, Proceedings of the Selected Areas in Cryptography, p.306-318, August 17-18, 1998
• 14: HOGG,R.AND TANIS, E. 1997. Probability and Statistical Inference. 5th ed. Prentice-Hall, New York, NY.
• 15: KAPP, J. S. A. 1996. RSAEuro: A cryptographic toolkit. Ver. 1.04. Internet Rel. Distrib..
• 16: 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
• 17: LOUKO, A. 1992. DES package. Helsinki Univ. Tech., Helsinki, Finland. ftp://kampi.hut.fi.
• 18: MARKOFF, J. 1996. Potential flaw seen in cash card security. The New York Times.
• 19: Mitsuru Matsui, The First Experimental Cryptanalysis of the Data Encryption Standard, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.1-11, August 21-25, 1994
• 20: Mitsuru Matsui, Linear cryptanalysis method for DES cipher, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.386-397, January 1994, Lofthus, Norway
• 21: MENEZES,A.J.,VAN OORSCHOT,P.C.,AND VANSTONE, S. A. 1997. Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton, FL. NBS 1977. NBS FIPS PUB 46, Data Encryption Standard. U.S. Department of Commerce.
• 22: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 23: ROSS, S. 1988. A First Course in Probability. 3rd ed. Macmillan Publishing Co., Inc., Indianapolis, IN.
• 24: Bruce Schneier, Applied cryptography (2nd ed.): protocols, algorithms, and source code in C, John Wiley & Sons, Inc., New York, NY, 1995
• 25: Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, Inc., Boca Raton, FL, 1995
• 26: ZACKS, S. 1971. The Theory of Statistical Inference. John Wiley & Sons, Inc., New York, NY.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Code breaking

Additional Classification:
  C. Computer Systems Organization

General Terms:
Security

Keywords:
cryptanalysis, cryptography, data encryption standard, timing attack