Two New Techniques of Side-Channel Cryptanalysis

[en] We describe two new techniques of side-channel cryptanalysis which we call the impossible collision attack and the multiset collision attack. These are inspired by the state-of-the-art cryptanalytic techniques of impossible differential attacks [BihamBS99] and partial-function collision attacks [GilbertM00] respectively. Using these techniques on an example of the AES we show that one has to mask all the rounds of a 128-bit key AES in order to prevent such attacks. For example these attacks can be used to break a recent proposal by Schramm et al. [SchrammP06] of high order masking for the AES, since it protects only 3 external rounds.

Disciplines :

Computer science

Identifiers :

UNILU:UL-ARTICLE-2007-003

Author, co-author :

Biryukov, Alex ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)

Khovratovich, Dmitry ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)

Language :

English

Title :

Two New Techniques of Side-Channel Cryptanalysis

Publication date :

2007

Event name :

Cryptographic Hardware and Embedded Systems - CHES 2007

Event date :

2007

Audience :

International

Main work title :

Cryptographic Hardware and Embedded Systems - CHES 2007

Pages :

195-208

Peer reviewed :

Peer reviewed

Additional URL :

http://www.springerlink.com

Available on ORBilu :

since 17 January 2014

Statistics

Number of views

145 (4 by Unilu)

Number of downloads

224 (4 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Akkar, M.-L., Bevan, R.. Goubin, L.: Two Power Analysis Attacks against One-Mask Methods. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 332-347. Springer, Heidelberg (2004)
Akkar, M.-L., Goubin, L.: A Generic Protection against High-Order Differential Power Analysis. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 192-205. Springer, Heidelberg (2003)
Biham, E., Biryukov, A., Shamir, A.: Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 12-23. Springer, Heidelberg (1999)
Brier, E., Clavier, C., Olivier, F.: Correlation Power Analysis with a Leakage Model. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 16-29. Springer, Heidelberg (2004)
Biham, E., Shamir, A.: Differential Cryptanalysis of DES-like Cryptosystems. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol 537, pp. 2-21. Springer, Heidelberg (1991)
Gilbert, H., Minier, M.: A Collision Attack on 7 Rounds of Rijndael. In: AES Candidate Conference, pp. 230-241 (2000)
Golic, J.Dj., Tymen, C.: Multiplicative Masking and Power Analysis of AES. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 198-212. Springer, Heidelberg (2003)
Handschuh, H., Preneel, B.: Blind Differential Cryptanalysis for Enhanced Power Attacks. In: Selected Areas of Cryptology 2006 (in appear)
Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M.J. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388-397. Springer, Heidelberg (1999)
Knuth, D.E.: The Art of Computer Programming: Enumeration and Backtracking. In: Generating all n-tuples, vol. 4A (2004)
Ledig, H., Muller, F., Valette, F.: Enhancing Collision Attacks. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 176-190. Springer, Heidelberg (2004)
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)
Oswald, E., Mangard, S., Pramstaller, N., Rijmen, V.: A Side-Channel Analysis Resistant Description of the AES S-Box. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 413-423. Springer, Heidelberg (2005)
Schramm, K.: Advanced Methods in Side Channel Cryptanalysis, Ph.D. thesis, University of Bochum (2006)
Schramm, K., Leander, G., Felke, P., Paar, C.: A Collision-Attack on AES: Combining Side Channel- and Differential-Attack. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 163-175. Springer, Heidelberg (2004)
Schramm, K., Paar, C.: Higher Order Masking of the AES. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol. 3860, pp. 208-225. Springer, Heidel-berg (2006)
Suzuki, D., Saeki, M., Ichikawa, T.: DPA Leakage Models for CMOS Logic Circuits. In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 366-382. Springer, Heidelberg (2005)
Schramm, K., Wollinger, T.J., Paar, C.: A New Class of Collision Attacks and Its Application to DES. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 206-222. Springer, Heidelberg (2003)
Waddle, J., Wagner, D.: Towards Efficient Second-Order Power Analysis. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 1-15. Springer, Heidelberg (2004)