Strength of Two Data Encryption Standard Implementations under Timing Attacks

Authors: Alejandro Hevia and Marcos Kiwi

Abstract: We study the vulnerability of several implementations of the Data Encryption Standard (DES) cryptosystem under a timing attack. A timing attack is a method designed to break cryptographic systems that was recently proposed by Paul Kocher. It exploits the engineering aspects involved in the implementation of cryptosystems and might succeed even against cryptosystems that remain impervious to sophisticated cryptanalytic techniques. A timing attack is, essentially, a way of obtaining some user's 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.

Ref: In ACM Transactions on Information and System Security, vol.2, n.4, Nov 1999, pp. 416-437, ACM Press.
A preliminar version of this work appeared in Proceedings of 3-rd Latin American Symposium on Theoretical Informatics - LATIN'98, LNCS 1380, pages 192-205, Springer-Verlag, 1998.

Full version: Available as Compressed Postscript, Postscript, and PDF.

Presentation: There is a video (youtube) of the presentation available performed by (a much younger) Alejandro at the Crypto'98 Rump Session. (Note: Ten years after the presentation, I found out someone was actually recording it!)