Abstract
Until now in cryptography the term collision was mainly associated with the surjective mapping of different inputs to an equal output of a hash function. Previous collision attacks were only able to detect collisions at the output of a particular function. In this publication we introduce a new class of attacks which originates from Hans Dobbertin and is based on the fact that side channel analysis can be used to detect internal collisions. We applied our attack against the widely used Data Encryption Standard (DES). We exploit the fact that internal collisions can be caused in three adjacent S-Boxes of DES [DDQ84] in order to gain information about the secret key-bits. As result, we were able to exploit an internal collision with a minimum of 140 encryptions yielding 10.2 key-bits. Moreover, we successfully applied the attack to a smart card processor.
Chapter PDF
Similar content being viewed by others
References
Agrawal, D., Archambeault, B., Rao, J.R., Rohatgi, P.: The EM side-channel(s). In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 29–45. Springer, Heidelberg (2003)
Anderson, R., Kuhn, M.: Tamper Resistance - a Cautionary Note. In: Second Usenix Workshop on Electronic Commerce, November 1996, pp. 1–11 (1996)
Briceno, M., Goldberg, I., Wagner, D.: An Implementation of the GSM A3A8 algorithm (1998), http://www.scard.org/gsm/a3a8.txt
Briceno, M., Goldberg, I., Wagner, D.: GSM cloning (1998), http://www.isaac.cs.berkely.edu/isaac/gsm–faq.html
Clavier, C., Coron, J.-S.: On Boolean and Arithmetic Masking against Differential Power Analysis. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 231–237. Springer, Heidelberg (2000)
Clavier, C., Coron, J.S., Dabbous, N.: Differential Power Analysis in the Presence of Hardware Countermeasures. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 252–263. Springer, Heidelberg (2000)
Clavier, C., Coron, J.-S., Dabbour, N.: Differential Power Anajlysis in the Presence of Hardware Countermeasures. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 252–263. Springer, Heidelberg (2000)
Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: A Cauttionary Note Regarding the Evaluation of AES Condidates on Smart Cards. In: Proceedings: Second AES Candidate Conference (AES2), Rome, Italy (March 1999)
Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards Sound Approaches to Counteract Power-Analysis Attacks. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 398–412. Springer, Heidelberg (1999)
Coppersmith, D.: The Data Encryption Standard (DES) and its Strength Against Attacks. Technical report rc 186131994, IBM Thomas J. Watson Research Center (December 1994)
Coron, J.-S.: Resistance against Differentail Power Analysis for Elliptic Curve Cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999)
den Boer, B., Bosselaers, A.: Collisions for the Compression Function of MD5. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 293–304. Springer, Heidelberg (1994)
Davio, M., Desmedt, Y., Quisquater, J.-J.: Propagation Characteristics of the DES. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 62–74. Springer, Heidelberg (1985)
Dobbertin, H.: RIPEMD with two-round compress function is not collisionfree. Journal of Cryptology 10, 51–68 (1997)
Dobbertin, H.: Cryptanalysis of md4. Journal of Cryptology 11, 253–271 (1998)
Fahn, P.N., Rearson, P.K.: IPA: A New Class of Power Attacks. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 173–186. Springer, Heidelberg (1999)
Goubin, L., Patarin, J.: DES and Differential Power Analysis. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 158–172. Springer, Heidelberg (1999)
Technical Information – GSM System Security Study (1998), http://jya.com/gsm061088.htm
Kocher, P., Jaffe, J., Jun, B.: Introduction to Differential Power Analysis and Related Attacks. Manuscript, Cryptography Research, Inc. (1998), http://www.cryptography.com/dpa/technical
Kocher, P., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Messerges, T.S., Dabbish, E.A., Sloan, R.H.: Investigations of Power Analysis Attacks on Smartcards. In: USENIX Workshop on Smartcard Technology, pp. 151–162 (1999)
Messerges, T.S.: Using Second-Order Power Analysis to Attack DPA Resistant Software. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 238–251. Springer, Heidelberg (2000)
Mayer-Sommer, R.: Smartly Analyzing the Simplicity and the Power of Simple Power Analysis on Smart Cards. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 78–92. Springer, Heidelberg (2000)
Muir, J.A.: Techniques of Side Channel Cryptanalysis. Master thesis, University of Waterloo, Canada (2001)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1997)
NIST FIPS PUB 46-3. Data Encryption Standard. Federal Information Processing Standards, National Bureau of Standards, U.S. Department of Commerce, Washington D.C (1977)
NIST FIPS PUB 180-1. Secure Hash Standard. Federal Information Processing Standards, National Bureau of Standards, U.S. Department of Commerce, Washington D.C. (April 1995)
R. Rivest. RFC 1320: The MD4 Message-Digest Algorithm. Corporation for National Research Initiatives, Internet Engineering Task Force, Network Working Group, Reston, Virginia, USA (April 1992)
Rivest, R.L., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21(2), 120–126 (1978)
Shamir, A.: Protecting Smart Cards form Power Analysis with Detached Power Supplies. In: Paar, C., Koç, Ç.K. (eds.) CHES 2000. LNCS, vol. 1965, pp. 71–77. Springer, Heidelberg (2000)
Vaudenay, S.: On the need of Multipermutations: Cryptanalysis of MD4 and SAFER. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 286–297. Springer, Heidelberg (1995)
Wiemers, A.: Partial Collision Search by Side Channel Analysis. In: Presentation at the Workshop: Smartcards and Side Channel Attacks, Horst Goertz Institute, Bochum, Germany (January 2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schramm, K., Wollinger, T., Paar, C. (2003). A New Class of Collision Attacks and Its Application to DES. In: Johansson, T. (eds) Fast Software Encryption. FSE 2003. Lecture Notes in Computer Science, vol 2887. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39887-5_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-39887-5_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20449-7
Online ISBN: 978-3-540-39887-5
eBook Packages: Springer Book Archive