Abstract
In September 1996 Boneh, Demillo, and Lipton from Bellcore announced a new type of cryptanalytic attack which exploits computational errors to find cryptographic keys. Their attack is based on algebraic properties of modular arithmetic, and thus it is applicable only to public key cryptosystems such as RSA, and not to secret key algorithms such as the Data Encryption Standard (DES).
In this paper, we describe a related attack, which we call Differential Fault Analysis, or DFA, and show that it is applicable to almost any secret key cryptosystem proposed so far in the open literature. Our DFA attack can use various fault models and various cryptanalytic techniques to recover the cryptographic secrets hidden in the tarn per-resistant device. In particular, we have demonstrated that under the same hardware fault model used by the Bellcore researchers, we can extract the full DES key from a sealed tamper-resistant DES encryptor by analyzing between 50 and 200 ciphertexts generated from unknown but related plaintexts.
In the second part of the paper we develop techniques to identify the keys of completely unknown ciphers (such as Skipjack) sealed in tamper-resistant devices, and to reconstruct the complete specification of DES-like unknown ciphers.
In the last part of the paper, we consider a different fault model, based on permanent hardware faults, and show that it can be used to break DES by analyzing a small number of ciphertexts generated from completely unknown and unrelated plaintexts.
Chapter PDF
Similar content being viewed by others
References
Ross Anderson, Markus Kuhn, Tamper Resistance — a Cautionary Note, proceedings of the Second Usenix Workshop on Electronic Commerce, pp. 1–11, November 1996.
Ross Anderson, Markus Kuhn, Low Cost Attacks on Tamper Resistant Devices, proceedings of the 1997 Security Protocols Workshop, Paris, April 7–9, 1997.
Eli Biham, New Types of Cryptanalytic Attacks Using Related Keys, Journal of Cryptology, Vol. 7, No. 4, pp. 229–246, 1994.
Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.
Dan Boneh, Richard A. Demillo, Richard J. Lipton, On the Importance of Checking Cryptographic Protocols for Faults, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT97, pp. 37–51, 1997.
Lawrence Brown, Josef Pieprzyk, Jennifer Seberry, LOKI — A Cryptographic Primitive for Authentication and Secrecy Applications, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of AUSCRYPT90, pp. 229–236, 1990.
John Kelsey, Bruce Schneier, David Wagner, Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO'96, pp. 237–251, 1996.
Paul C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO'96, pp. 104–113, 1996.
Xuejia Lai, James L. Massey, Sean Murphy, Markov Ciphers and Differential Cryptanalysis, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT91, pp. 17–38, 1991.
Susan K. Langford, Martin E. Hellman, Differential-linear cryptanalysis, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO'94, pp. 17–25, 1994.
John Markoff, Potential Flaw Seen in Cash Card Security, New York Times, September 26, 1996.
Mitsuru Matsui, Linear Cryptanalysis Method for DES Cipher, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT'93, pp. 386–397, 1993.
Ralph C. Merkle, Fast Software Encryption Functions, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO'90, pp. 476–501, 1990.
Shoji Miyaguchi, FEAL-N specifications, technical note, NTT, 1989.
Shoji Miyaguchi, The FEAL cipher family, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO'90, pp. 627–638, 1990.
Shoji Miyaguchi, Akira Shiraishi, Akihiro Shimizu, Fast Data Encryption Algorithm FEAL-8, Review of electrical communications laboratories, Vol. 36, No. 4, pp. 433–437, 1988.
National Bureau of Standards, Data Encryption Standard, U.S. Department of Commerce, FIPS pub. 46, January 1977.
Bart Preneel, Marnix Nuttin, Vincent Rijmen, Johan Buelens, Cryptanalysis of the CFB Mode of the DES with a Reduced Number of Rounds, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of CRYPTO'93, pp. 212–223, 1993.
Ronald L. Rivest, The RC5 Encryption Algorithm, proceedings of Fast Software Encryption, Leuven, Lecture Notes in Computer Science, pp. 86–96, 1994.
Bruce Schneier, Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish), proceedings of Fast Software Encryption, Cambridge, Lecture Notes in Computer Science, pp. 191–204, 1993.
Akihiro Shimizu, Shoji Miyaguchi, Fast Data Encryption Algorithm FEAL, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT'87, pp. 267–278. 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag
About this paper
Cite this paper
Biham, E., Shamir, A. (1997). Differential fault analysis of secret key cryptosystems. In: Kaliski, B.S. (eds) Advances in Cryptology — CRYPTO '97. CRYPTO 1997. Lecture Notes in Computer Science, vol 1294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052259
Download citation
DOI: https://doi.org/10.1007/BFb0052259
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63384-6
Online ISBN: 978-3-540-69528-8
eBook Packages: Springer Book Archive